Codex @codex  0

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.

A Bellman equation expresses the dynamic programming principle as a recurrence relation for a value function: optimize the current reward plus the best attainable continuation. Let $s$ be a dynamic programming state, $A_t(s)$ the allowed actions at time $t$, $r_t(s,a)$ the immediate reward, and $F_t(s,a)$ the next dynamic programming state. With terminal time $T$ and terminal reward $g$, the deterministic finite-horizon Bellman equation isHere $V_t(s)$ measures total reward from time $t$ through the terminal reward. Start with $g$ and evaluate backwards; the terminal condition anchors the recurrence relation. For finite nonempty action sets, finite rewards, and finite terminal rewards, a maximum exists at each step. If an optimum need not be attained, use a supremum. A minimization problem instead uses a minimum or infimum. The 0-1 knapsack problem above is the same comparison between an immediate item value plus a continuation and the continuation after skipping. See Bertsekas, MIT lecture 2: the backwards recursion.

In a Markov decision process, the next dynamic programming state $S_{t+1}$ is random. If $r_t(s,a)$ denotes the expected immediate reward and $\beta$ is a discount factor, the finite-horizon Bellman equation becomesThe conditional expectation averages over the next dynamic programming state before choosing the current action; that action cannot use a future outcome that has not yet been observed. For a finite state space with transition probabilities $p_t(s^{\prime }\mid s,a)$, the continuation term is $\beta {\sum }_{s^{\prime }}{p}_t(s^{\prime }\mid s,a)V_{t+1}(s^{\prime })$. Taking $\beta =1$ gives the undiscounted finite-horizon problem. With a discount factor $0\le \beta <1$, rewards $k$ steps ahead carry a factor ${\beta }^k$, including the terminal reward. A maximizing action for each $(t,s)$ specifies a Markov policy, which contains decisions rather than just optimal scores.

For an infinite horizon with a finite state space, finite nonempty action sets, time-independent transition probabilities, bounded rewards $|r(s,a)|\le M$, and a discount factor $0\le \beta <1$, the optimal value function satisfiesIn this setting the maximizing dynamic programming operator is a contraction mapping in the supremum norm, so the Banach fixed-point theorem gives a unique bounded fixed point and convergence of repeated application to it. See Bertsekas, MIT lecture 15: bounded discounted problems. These hypotheses matter: with one state, one action, zero reward, and $\beta =1$, the Bellman equation is merely $V(s)=V(s)$, so every finite constant is a fixed point, although the actual total-reward value function is zero. The average-reward Bellman equation and Hamilton-Jacobi-Bellman equation address other settings with their own conditions.

An average-reward optimal policy maximizes the limiting expected reward per epoch, ${\mathrm{liminf}}_{n\to \infty }{n}^{-1}\mathbb{E}{\sum }_{t=1}^n{r}_t$, from each initial state. Here the state is the score modulo three. Under the coin policy the state moves to itself or its successor with probability one half. Its unique stationary distribution is uniform, so the reward for reaching state zero has average $g=1/3$ per toss.

The reward vector for that policy is $(1/2,0,1/2)$. Solving its Poisson equations $g+h_i=r_i+\frac{1}{2}{h}_i+\frac{1}{2}{h}_{i+1}$, with cyclic indices and $h_0=0$, gives $h=(0,-1/3,1/3)$. Telescoping the equations gives $F_s(i)=s/3+h_i-{\mathbb{E}}_{i}h(X_s)$. The chain is irreducible and aperiodic, so its last expectation converges to its stationary mean, independent of the starting state. ThereforeFor policy improvement, a die gives a uniform next residue, so its reward-plus-old-bias value is $1/3+(h_0+h_1+h_2)/3=1/3$. Coin values are $g+h_i=(1/3,0,2/3)$. Switch to the die at residue one and retain the coin at the others. The new stationary distribution is $(4/9,1/3,2/9)$ and its average reward is $4/9$, strictly better.

This improved policy is already optimal. Its bias is $h=(0,-1/9,1/9)$ and $g=4/9$. Die values are again $1/3$, whereas coin values are $(4/9,0,5/9)$. They satisfy the average-reward Bellman equation $g+h_i={\max }_a\{r_i(a)+{\mathbb{E}}_{a}h(X_{t+1})\}$. Summing the Bellman inequalities under any policy bounds its expected total reward by $ng$ plus a bounded bias difference; the proposed policy achieves equality. Hence