Answers.Body: <p>In the <em>infinite</em> horizon MDP case, your so called optimal average (1-step) reward metric can be proved to be independent of any starting state <span class="math-container">$s_0$</span> for any policy with <em>exploration</em> such as <span class="math-container">$\epsilon$</span>-greedy policy, which needs to use the usual expectation definition of reward instead of your deterministic function <span class="math-container">$R_a(s)$</span>, since contrary to your assumption, the next state <span class="math-container">$s′∈S$</span> is <em>not</em> a deterministic function of <span class="math-container">$s$</span> and <span class="math-container">$a$</span> under MDP environment. If all your rewards are deterministic function of the current state and action, then it apparently makes no sense to discuss the possible stationary distribution of random state in the context of ergodic stochastic process.</p>
  <p>Intuitively any state is <em>communicating</em> to any other state including itself in an exploring policy, thus the resulting Markov chain becomes <a href="https://en.wikipedia.org/wiki/Markov_chain#Properties" rel="nofollow noreferrer">irreducible</a> since there is only one communicating class as the state space. Therefore, under the additional conditions of  <em>aperiodic</em> and <em>positive recurrent</em> of the communicating class, it's ergodic and doesn't depend on any initial state <span class="math-container">$s_0$</span>, even for you continuous state space case.</p>
  <blockquote>
  <p>Periodicity, transience, recurrence and positive and null recurrence are class properties — that is, if one state has the property then all states in its communicating class have the property... A state i is said to be ergodic if it is aperiodic and positive recurrent... If all states in an irreducible Markov chain are ergodic, then the chain is said to be ergodic.</p>
  </blockquote>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-15T06:50:29.787Z
Answers.LastActivityDate: 2024-04-15T06:50:29.787Z
Answers.UserDisplayName: cinch
Body: <p>Asking <a href="https://mathoverflow.net/questions/469030/mdp-average-reward-independent-of-initial-state#comment1217952_469030">this</a> question of mine in MathOverflow here since AI StackExchange appears to be a more appropriate place.</p>
  <p>Consider a Markov Decision Process where the state space <span class="math-container">$S$</span> and the action space <span class="math-container">$A$</span> are <strong>continuous</strong> and compact.</p>
  <p>In state <span class="math-container">$s$</span>, if action <span class="math-container">$a$</span> is chosen and the next state becomes <span class="math-container">$s'$</span>, the corresponding reward is denoted by <span class="math-container">$R_a(s,s')$</span>.</p>
  <p>Assume that when in state <span class="math-container">$s \in S$</span> if action <span class="math-container">$a \in A$</span> is played, then the next state <span class="math-container">$s' \in S$</span> is a deterministic function of <span class="math-container">$s$</span> and <span class="math-container">$a$</span>, i.e., <span class="math-container">$s' = f(s,a) \ \forall s\in S, a\in A$</span>. Notice that this implies that the reward too is a function of <span class="math-container">$a$</span> and <span class="math-container">$s$</span> only, i.e., we can write <span class="math-container">$R_a(s,s') = R_a(s)$</span>.</p>
  <p>Fix an initial state <span class="math-container">$s_0 \in S$</span>. For a given time-horizon <span class="math-container">$N \in \mathbb N$</span>, the <span class="math-container">$N$</span>-step average reward obtained from actions <span class="math-container">$\mathbf a = (a_1, a_2, \ldots, a_N)$</span> and the corresponding evolution of states <span class="math-container">$\mathbf s(\mathbf a) = (s_1,s_2,\ldots,s_N)$</span> is</p>
  <p><span class="math-container">\begin{align}
  R_N(\mathbf a) &amp;:= \frac 1 N \sum_{t=1}^N R_{a_t}(s_{t-1},s_t)\\
  &amp;\ = \frac 1 N \sum_{t=1}^N R_{a_t}(s_{t-1}).
  \end{align}</span></p>
  <p>For each <span class="math-container">$N$</span>, there is an <em>optimal average-reward</em> <span class="math-container">$\hat R_N := \max\limits_{\mathbf a} R_N(\mathbf a)$</span>. We are interested in the limiting quantity <span class="math-container">$\hat R_\infty := \lim_{N\to\infty} \hat R_N$</span> (provided that it exists).</p>
  <p><strong>Question:</strong> When is <span class="math-container">$\hat R_\infty$</span> independent of the initial state <span class="math-container">$s_0$</span>? What are some conditions that are sufficient for this?</p>
  <p>It is clear that if the states are <em>connected</em>, i.e., if any state can be reached by any other state by finitely many actions, then the initial state does not affect <span class="math-container">$\hat R_\infty$</span>. I am looking for answers assuming that connectivity in this sense does not hold. It is quite intuitive that even if connectivity does not hold, under some mild conditions, in the infinite-horizon the initial state <span class="math-container">$s_0$</span> should not matter.</p>
  <p>Any answer/reference would be highly appreciated. Thanks in advance!</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-04-14T20:02:30.380Z
Comments.Text: I mean, take an MDP with 3 possible initial states, and these 3 states are connected to disjoint sets of states, then the average reward depends on the distribution of the initial states, so for sure you need some sort of ergodicity of the MC
Comments.UserDisplayName: Alberto
Tags: <markov-decision-process>
Title: MDP Average Reward independent of Initial State
UserDisplayName: Euclid
ThreadText: # MDP Average Reward independent of Initial State
  
  (Asked by: username_0 on 2024-04-14)
  
  Asking [this](https://mathoverflow.net/questions/469030/mdp-average-reward-independent-of-initial-state#comment1217952_469030) question of mine in MathOverflow here since AI StackExchange appears to be a more appropriate place.
  
  Consider a Markov Decision Process where the state space $S$ and the action space $A$ are **continuous** and compact.
  
  In state $s$, if action $a$ is chosen and the next state becomes $s'$, the corresponding reward is denoted by $R\_a(s,s')$.
  
  Assume that when in state $s \in S$ if action $a \in A$ is played, then the next state $s' \in S$ is a deterministic function of $s$ and $a$, i.e., $s' = f(s,a) \ \forall s\in S, a\in A$. Notice that this implies that the reward too is a function of $a$ and $s$ only, i.e., we can write $R\_a(s,s') = R\_a(s)$.
  
  Fix an initial state $s\_0 \in S$. For a given time-horizon $N \in \mathbb N$, the $N$-step average reward obtained from actions $\mathbf a = (a\_1, a\_2, \ldots, a\_N)$ and the corresponding evolution of states $\mathbf s(\mathbf a) = (s\_1,s\_2,\ldots,s\_N)$ is
  
  \begin{align}
  R\_N(\mathbf a) &:= \frac 1 N \sum\_{t=1}^N R\_{a\_t}(s\_{t-1},s\_t)\\
  &\ = \frac 1 N \sum\_{t=1}^N R\_{a\_t}(s\_{t-1}).
  \end{align}
  
  For each $N$, there is an *optimal average-reward* $\hat R\_N := \max\limits\_{\mathbf a} R\_N(\mathbf a)$. We are interested in the limiting quantity $\hat R\_\infty := \lim\_{N\to\infty} \hat R\_N$ (provided that it exists).
  
  **Question:** When is $\hat R\_\infty$ independent of the initial state $s\_0$? What are some conditions that are sufficient for this?
  
  It is clear that if the states are *connected*, i.e., if any state can be reached by any other state by finitely many actions, then the initial state does not affect $\hat R\_\infty$. I am looking for answers assuming that connectivity in this sense does not hold. It is quite intuitive that even if connectivity does not hold, under some mild conditions, in the infinite-horizon the initial state $s\_0$ should not matter.
  
  Any answer/reference would be highly appreciated. Thanks in advance!
  
  **Tags:** markov-decision-process
  
  > **Comments:**
  > **username_1**: I mean, take an MDP with 3 possible initial states, and these 3 states are connected to disjoint sets of states, then the average reward depends on the distribution of the initial states, so for sure you need some sort of ergodicity of the MC  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2024-04-15. Score: 2
  
  In the *infinite* horizon MDP case, your so called optimal average (1-step) reward metric can be proved to be independent of any starting state $s\_0$ for any policy with *exploration* such as $\epsilon$-greedy policy, which needs to use the usual expectation definition of reward instead of your deterministic function $R\_a(s)$, since contrary to your assumption, the next state $s′∈S$ is *not* a deterministic function of $s$ and $a$ under MDP environment. If all your rewards are deterministic function of the current state and action, then it apparently makes no sense to discuss the possible stationary distribution of random state in the context of ergodic stochastic process.
  
  Intuitively any state is *communicating* to any other state including itself in an exploring policy, thus the resulting Markov chain becomes [irreducible](https://en.wikipedia.org/wiki/Markov_chain#Properties) since there is only one communicating class as the state space. Therefore, under the additional conditions of *aperiodic* and *positive recurrent* of the communicating class, it's ergodic and doesn't depend on any initial state $s\_0$, even for you continuous state space case.
  
  > Periodicity, transience, recurrence and positive and null recurrence are class properties — that is, if one state has the property then all states in its communicating class have the property... A state i is said to be ergodic if it is aperiodic and positive recurrent... If all states in an irreducible Markov chain are ergodic, then the chain is said to be ergodic.
  
  
  ---
  
  