Does stochasticity of an environment necessarily mean non-stationarity in MDPs?

Question

Is a stochastic environment necessarily also non-stationary? To elaborate, consider a two-state environment ($s_1$ and $s_2$), with two actions $a_1$ and $a_2$. In $s_1$, taking action $a_1$ has a certain probability $p_1$ of transitioning you into $s_2$, and a probability $1-p_1$ of keeping you in $s_1$. There is also a similar probability for taking $a_2$ in $s_1$, and taking either action in $s_2$. Let's also say that there is a reward $r$ given only when a transition occurs from either state, and 0 otherwise. This is a stochastic environment. But isn't this non-stationary in one sense and stationary in another? I think it is stationary because the expected return from taking a particular action in a particular state converges to a constant value. But it is non-stationary in the sense that the reward obtained from taking a certain action in a given state may change at a given time. Which is really the case?

Answer 1

Is a stochastic environment necessarily also non-stationary?

No.

A stochastic environment (i.e. an MDP with a transition model $p(s', r \mid s, a)$) can be stationary (i.e. $p$ does not change over time) or non-stationary ($p$ changes over time). Similarly, a deterministic environment, i.e. the probabilities are $1$ or $0$, can also be either stationary or not. To emphasize that an MDP may be non-stationary, you could write $p$ as a function of time, i.e. $p_t$ (you also do the same thing for the reward function if it's separate from the transition function).

The same idea applies to a stochastic/deterministic policy, which can either be stationary or not.

A non-stationary environment may lead to a non-stationary policy (or may require you to relearn a model of the environment, if you need to learn a model of the environment) [1]. However, note that a stochastic environment (i.e. an MDP) does not necessarily imply a stochastic policy (actually, under some conditions, stationary and stochastic MDPs are known to have a deterministic optimal policy [1]).

In general, if something (e.g. environment, policy, value function or reward function) is non-stationary, it means that it changes over time. This can either be a function or a probability distribution. So, a probability distribution (the stochastic part of an MDP) can change or not over time. If it changes over time, then it makes the MDP non-stationary.

But it is non-stationary in the sense that the reward obtained from taking a certain action in a given state may change at a given time

Informally, you could say that the empirical reward obtained is non-stationary because it changes over time, due to the stochasticity of the reward function, behaviour policy, etc., but the dynamics (transition function and reward function) would still be fixed, so the environment would still be stationary. So, there's a difference between the environment and the experience that you collected so far (with some behaviour policy).