Average-reward optimal policy ($g={\mathrm{liminf}}_{n\to \infty }{n}^{-1}\mathbb{E}{\sum }_{j=1}^n{r}_j$)

An average-reward optimal policy maximizes long-run expected reward per time step. In a finite recurrent Markov chain, a stationary policy's gain is its expected one-step reward under the stationary distribution. Initial-state effects are encoded by a bias function rather than by the gain. In a communicating finite control problem, the average-reward Bellman equation certifies a policy that is optimal from every initial state.

The gain $g$ and bounded bias $h$ in this equation give an upper bound on average reward for every policy: summing its action inequalities telescopes the bias, leaving total expected reward at most $ng+h(i)-\mathbb{E}h(X_n)$. A stationary maximizing action at each state attains equality and hence the gain $g$. Policy improvement computes the current gain and bias, then switches to actions with greater reward-plus-expected-bias value.