# Expected value of policy for an average reward MDP

We have that the average reward under a policy $\pi$ is defined as:

$r(\pi) \doteq \lim_{t\rightarrow \infty} \mathbb{E}[R_t\mid A_{0:t-1}\sim\pi]$

With corresponding average reward return $G_t$

$G_t \doteq R_{t+1} - r(\pi) + R_{t+2} - r(\pi) + R_{t+3} - r(\pi) + \ldots$

and value function

$v_\pi(s) \doteq \mathbb{E}[G_t\mid S_t=s]$.

Does this mean that the value, under expectation of the different starting states $s_0\in \mathbb{S}_0$, is 0? I.e.

$\sum_{\mathbb{S}_0} v(s_0) = 0$

• The formula for $G_t$ doesn't look familiar to me. Why subtract $r(\pi)$? – shimao Apr 15 '18 at 22:07
• @shimao It's an average reward formulation, which allows for optimizing over an infinite time horizon without biasing toward short-term rewards (as is done with discounting) while keeping the return bounded (see e.g. Sutton - Introduction to Reinforcement Learning 2nd ed, chap 10.4, a draft of which is available for free here: incompleteideas.net/book/the-book-2nd.html) – tsorn Apr 15 '18 at 22:56

## 1 Answer

Not quite. What matters is the limiting probability of being in each state, which for many MDPs is independent of the starting state. Assume the limiting probabilities given a policy $\pi$ are a vector $p_{\pi}(s;s_0)$ conditional upon the starting state $s_0$, then:

$$\sum_s v_{\pi}(s)p_{\pi}(s;s_0) = 0$$

i.e, the expected value of the value functions (normalized by subtracting the gain, as you have done) has to equal 0.

Note that for many chains "limiting probabilities" really are "long run average frequency of state occupation", not probabilities, as it may be, for example, that state A cannot be occupied on odd stages (e.g., stage # 1029111) but can be on even stages.

The "average reward" criterion implies (for well-behaved problems) that everything that happens when transiting to the steady state has no impact on the determination of the optimum policy, as its contribution to the average reward goes to zero as the stage $n \to \infty$. This is somewhat of an inverse to the "discounted reward" criterion, in which, if there are an infinite number of transitions to the steady state, it's the steady state that has no impact on the determination of the optimum policy.

• I think you mean "time step" (or stage) instead of epoch (which is often used to describe separate rollouts from any starting state). Otherwise great answer, thanks! – tsorn Apr 27 '18 at 18:36