MDP Average Reward independent of Initial State

Question

Asking this 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!

Answer 1

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 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.