Answers.Body: <p>Indeed your idealized problem is an edge case which is less studied. Most practical problem-solving RL literature assumes that induced MCs from MDPs are ergodic which simplifies both theory and practice.</p>
  <p>In many practical MDPs, even if there're non-ergodicity due to non existence of a single communicating class as you've perhaps known, the stationary distributions for policies don't split in such a clear-cut manner as you also imagined.</p>
  <p>In RL policy performance is usually evaluated across many sampled induced trajectories which <em>inherently</em> handles your concerned stochasticity in transitions without <em>explicitly</em> decomposing into multiple stationary distributions.</p>
  <p>Finally your approach requires explicit knowledge of environment's transition dynamics which is not directly accessible in most popular model-free RL methods such as all policy gradient based methods.</p>
  <p>Having said that, Baumann et al (2023) <a href="https://arxiv.org/abs/2310.11335" rel="nofollow noreferrer">&quot;<em>Non-ergodicity in reinforcement learning: robustness via ergodicity transformations</em>&quot;</a> studies non-ergodic RL in terms of reliability via ergodic transformation which might suggest it's actually an important problem for some real world applications in terms of learned optimal policy's reliability when non-ergodicity does occur.</p>
  <blockquote>
  <p>A significant challenge hindering the adoption of RL methods in these domains is the non-robustness of conventional algorithms. In this paper, we argue that a fundamental issue contributing to this lack of robustness lies in the focus on the expected value of the return as the sole <span class="math-container">``</span>correct'' optimization objective. The expected value is the average over the statistical ensemble of infinitely many trajectories. For non-ergodic returns, this average differs from the average over a single but infinitely long trajectory. Consequently, optimizing the expected value can lead to policies that yield exceptionally high returns with probability zero but almost surely result in catastrophic outcomes.</p>
  </blockquote>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-12-05T23:34:26.470Z
Answers.Text: Thanks for your answer! So, isn't there any discussion (even in terms "this is challenging") in the literature? Also, I am not sure my formalization would require to know the dynamics. Even in the classic one, $\mu$ is just approximated with samples, so the same can be done with $p(\mu)$. I'm not sure how the policy gradient would look like, or even if it could be derived like the classic one. But anyway, I was just looking for referneces that, at least, discuss failure cases like mine (with multiple stationary distributions).
Answers.UserDisplayName: Simon
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-12-06T00:17:13.560Z
Answers.Text: Very few references. See S&B book exercise 10.6: *Technically, this violates ergodicity; there is no stationary limiting distribution... Nevertheless, the average reward (10.6) is well defined... To repair this, one could alternatively define the differential value of a state as...* So it's challenging unless in some definite *average reward* case you can define a new state value function with double limits, which might not be applicable to your more general case. Also per your request I added a recent reference explicitly deals with RL non-ergodicity when it does matter. Hope this clarifies.
Answers.UserDisplayName: cinch
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-12-05T20:29:11.203Z
Answers.LastActivityDate: 2024-12-06T00:14:24.513Z
Answers.LastEditDate: 2024-12-06T00:14:24.513Z
Answers.UserDisplayName: cinch
Body: <p><a href="https://i.sstatic.net/ffq88z6t.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/ffq88z6t.png" alt="enter image description here" /></a></p>
  <p>Consider the chainworld above with two actions, move (in red) and stay (in blue). Moving in A is stochastic: the agent moves to B with probability <span class="math-container">$p$</span> and to C with probability <span class="math-container">$1-p$</span>. Moving or staying in B and C is irrelevant.<br />
  Clearly, there exists an optimal policy depending on the reward in A, B, C, the probability <span class="math-container">$p$</span>, and the discount factor <span class="math-container">$\gamma$</span>.</p>
  <p><strong>However, can the policy performance be defined?</strong> Consider the policy that does &quot;move&quot; in A: the induced Markov chain has two stationary state distributions <span class="math-container">$\mu_\pi$</span> (agent stays forever in B or C). Is the policy performance of this policy <span class="math-container">$J^\pi = \sum_s \mu_\pi(s) V^\pi(s)$</span> defined? We know that is it defined when the MDP is ergodic and <span class="math-container">$\mu_\pi(s)$</span> exists and is unique, but what about this scenario? The problem I see is that there are two <span class="math-container">$\mu_\pi(s)$</span> but <span class="math-container">$J^\pi$</span> does not account for that. Intuitively, I would simply weigh the sum by the probability that the agent induces the stationary distributions, i.e.,
  <span class="math-container">$J^\pi = \sum_{\mu_\pi} p(\mu_\pi) \sum_s \mu_\pi(s) V^\pi(s)$</span>. In the example above, <span class="math-container">$p(\mu_\pi)$</span> would just be <span class="math-container">$p$</span>, but in more complex MPDs it may depend on multiple probabilities.</p>
  <p>I haven't found anything like that in RL literature, and I was wondering why.</p>
  
Tags: <reinforcement-learning><markov-decision-process><stationary-policy>
Title: Policy performance when the stationary state distribution is not unique in RL
UserDisplayName: Simon
ThreadText: # Policy performance when the stationary state distribution is not unique in RL
  
  (Asked by: username_0 on 2024-12-05)
  
  [![enter image description here](https://i.sstatic.net/ffq88z6t.png)](https://i.sstatic.net/ffq88z6t.png)
  
  Consider the chainworld above with two actions, move (in red) and stay (in blue). Moving in A is stochastic: the agent moves to B with probability $p$ and to C with probability $1-p$. Moving or staying in B and C is irrelevant.  
  Clearly, there exists an optimal policy depending on the reward in A, B, C, the probability $p$, and the discount factor $\gamma$.
  
  **However, can the policy performance be defined?** Consider the policy that does "move" in A: the induced Markov chain has two stationary state distributions $\mu\_\pi$ (agent stays forever in B or C). Is the policy performance of this policy $J^\pi = \sum\_s \mu\_\pi(s) V^\pi(s)$ defined? We know that is it defined when the MDP is ergodic and $\mu\_\pi(s)$ exists and is unique, but what about this scenario? The problem I see is that there are two $\mu\_\pi(s)$ but $J^\pi$ does not account for that. Intuitively, I would simply weigh the sum by the probability that the agent induces the stationary distributions, i.e.,
  $J^\pi = \sum\_{\mu\_\pi} p(\mu\_\pi) \sum\_s \mu\_\pi(s) V^\pi(s)$. In the example above, $p(\mu\_\pi)$ would just be $p$, but in more complex MPDs it may depend on multiple probabilities.
  
  I haven't found anything like that in RL literature, and I was wondering why.
  
  **Tags:** reinforcement-learning, markov-decision-process, stationary-policy
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2024-12-05. Score: 2 | Accepted answer
  
  Indeed your idealized problem is an edge case which is less studied. Most practical problem-solving RL literature assumes that induced MCs from MDPs are ergodic which simplifies both theory and practice.
  
  In many practical MDPs, even if there're non-ergodicity due to non existence of a single communicating class as you've perhaps known, the stationary distributions for policies don't split in such a clear-cut manner as you also imagined.
  
  In RL policy performance is usually evaluated across many sampled induced trajectories which *inherently* handles your concerned stochasticity in transitions without *explicitly* decomposing into multiple stationary distributions.
  
  Finally your approach requires explicit knowledge of environment's transition dynamics which is not directly accessible in most popular model-free RL methods such as all policy gradient based methods.
  
  Having said that, Baumann et al (2023) ["*Non-ergodicity in reinforcement learning: robustness via ergodicity transformations*"](https://arxiv.org/abs/2310.11335) studies non-ergodic RL in terms of reliability via ergodic transformation which might suggest it's actually an important problem for some real world applications in terms of learned optimal policy's reliability when non-ergodicity does occur.
  
  > A significant challenge hindering the adoption of RL methods in these domains is the non-robustness of conventional algorithms. In this paper, we argue that a fundamental issue contributing to this lack of robustness lies in the focus on the expected value of the return as the sole ``correct'' optimization objective. The expected value is the average over the statistical ensemble of infinitely many trajectories. For non-ergodic returns, this average differs from the average over a single but infinitely long trajectory. Consequently, optimizing the expected value can lead to policies that yield exceptionally high returns with probability zero but almost surely result in catastrophic outcomes.
  
  > **Comments:**
  > **username_0**: Thanks for your answer! So, isn't there any discussion (even in terms "this is challenging") in the literature? Also, I am not sure my formalization would require to know the dynamics. Even in the classic one, $\mu$ is just approximated with samples, so the same can be done with $p(\mu)$. I'm not sure how the policy gradient would look like, or even if it could be derived like the classic one. But anyway, I was just looking for referneces that, at least, discuss failure cases like mine (with multiple stationary distributions).  
  > **username_1**: Very few references. See S&B book exercise 10.6: *Technically, this violates ergodicity; there is no stationary limiting distribution... Nevertheless, the average reward (10.6) is well defined... To repair this, one could alternatively define the differential value of a state as...* So it's challenging unless in some definite *average reward* case you can define a new state value function with double limits, which might not be applicable to your more general case. Also per your request I added a recent reference explicitly deals with RL non-ergodicity when it does matter. Hope this clarifies.  
  
  ---
  
  