Answers.Body: <blockquote>
  <p>Is a stochastic environment necessarily also non-stationary?</p>
  </blockquote>
  <p>No.</p>
  <p>A stochastic environment (i.e. an MDP with a transition model <span class="math-container">$p(s', r \mid s, a)$</span>) can be stationary (i.e. <span class="math-container">$p$</span> does not change over time) or non-stationary (<span class="math-container">$p$</span> changes over time). Similarly, a deterministic environment, i.e. the probabilities are <span class="math-container">$1$</span> or <span class="math-container">$0$</span>, can also be either stationary or not. To emphasize that an MDP may be non-stationary, you could write <span class="math-container">$p$</span> as a function of time, i.e. <span class="math-container">$p_t$</span> (you also do the same thing for the reward function if it's separate from the transition function).</p>
  <p>The same idea applies to a <a href="https://ai.stackexchange.com/q/12274/2444">stochastic/deterministic policy</a>, which can either be <a href="https://ai.stackexchange.com/q/13088/2444">stationary or not</a>.</p>
  <p>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) [<a href="https://papers.nips.cc/paper/2019/file/859b00aec8885efc83d1541b52a1220d-Paper.pdf" rel="nofollow noreferrer">1</a>]. However, note that <a href="https://ai.stackexchange.com/q/10591/2444">a stochastic environment (i.e. an MDP) does not necessarily imply a stochastic policy</a> (actually, under some conditions, stationary and stochastic MDPs are known to have a deterministic optimal policy [<a href="https://papers.nips.cc/paper/2019/file/859b00aec8885efc83d1541b52a1220d-Paper.pdf" rel="nofollow noreferrer">1</a>]).</p>
  <p>In general, if something (e.g. environment, policy, value function or reward function) is <a href="https://en.wikipedia.org/wiki/Stationary_process" rel="nofollow noreferrer">non-stationary</a>, 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.</p>
  <blockquote>
  <p>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</p>
  </blockquote>
  <p>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).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-25T01:12:39.273Z
Answers.Text: Thank you very much @nbro. That is a well-explained point. In specific, your comment "Informally, you could say that the empirical reward obtained is non-stationary because it changes over time, ..." is very helpful. I believe in short, your point is for me to first identify the nature of the environment (stochastic or deterministic). Then based on the definition of the type of environment, I check to see if there are changes to the underlying feature (probability distribution for stochastic environment, and a single value for the deterministic case).
Answers.UserDisplayName: O'Jhene
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-25T00:54:10.403Z
Answers.LastActivityDate: 2021-02-25T01:18:39.333Z
Answers.LastEditDate: 2021-02-25T01:18:39.333Z
Answers.UserDisplayName: nbro
Body: <p>Is a stochastic environment necessarily also non-stationary? To elaborate, consider a two-state environment (<span class="math-container">$s_1$</span> and <span class="math-container">$s_2$</span>), with two actions <span class="math-container">$a_1$</span> and <span class="math-container">$a_2$</span>. In <span class="math-container">$s_1$</span>, taking action <span class="math-container">$a_1$</span> has a certain probability <span class="math-container">$p_1$</span> of transitioning you into <span class="math-container">$s_2$</span>, and a probability <span class="math-container">$1-p_1$</span> of keeping you in <span class="math-container">$s_1$</span>. There is also a similar probability for taking <span class="math-container">$a_2$</span> in <span class="math-container">$s_1$</span>, and taking either action in <span class="math-container">$s_2$</span>. Let's also say that there is a reward <span class="math-container">$r$</span> 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?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-02-24T23:49:06.700Z
Comments.Text: I don’t have time to write a full answer atm but I believe that if the $p_i$’s remain fixed then the problem is stationary.
Comments.UserDisplayName: David
Tags: <reinforcement-learning><markov-decision-process>
Title: Does stochasticity of an environment necessarily mean non-stationarity in MDPs?
UserDisplayName: O'Jhene
ThreadText: # Does stochasticity of an environment necessarily mean non-stationarity in MDPs?
  
  (Asked by: username_0 on 2021-02-24)
  
  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?
  
  **Tags:** reinforcement-learning, markov-decision-process
  
  > **Comments:**
  > **username_1**: I don’t have time to write a full answer atm but I believe that if the $p_i$’s remain fixed then the problem is stationary.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2021-02-25. Score: 5 | Accepted answer
  
  > 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](https://ai.stackexchange.com/q/12274/2444), which can either be [stationary or not](https://ai.stackexchange.com/q/13088/2444).
  
  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](https://papers.nips.cc/paper/2019/file/859b00aec8885efc83d1541b52a1220d-Paper.pdf)]. However, note that [a stochastic environment (i.e. an MDP) does not necessarily imply a stochastic policy](https://ai.stackexchange.com/q/10591/2444) (actually, under some conditions, stationary and stochastic MDPs are known to have a deterministic optimal policy [[1](https://papers.nips.cc/paper/2019/file/859b00aec8885efc83d1541b52a1220d-Paper.pdf)]).
  
  In general, if something (e.g. environment, policy, value function or reward function) is [non-stationary](https://en.wikipedia.org/wiki/Stationary_process), 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).
  
  > **Comments:**
  > **username_0**: Thank you very much @username_2. That is a well-explained point. In specific, your comment "Informally, you could say that the empirical reward obtained is non-stationary because it changes over time, ..." is very helpful. I believe in short, your point is for me to first identify the nature of the environment (stochastic or deterministic). Then based on the definition of the type of environment, I check to see if there are changes to the underlying feature (probability distribution for stochastic environment, and a single value for the deterministic case).  
  
  ---
  
  