Core idea. Discounted reinforcement learning values near-term reward more than distant reward. In many continuing systems, however, there is no natural terminal time and no natural discount factor. The mathematically natural objective is the long-run average reward:
when the limit exists. Average-reward theory replaces discounted value functions by two objects: the gain\(\rho^{\pi}\), which measures long-run reward per time step, and the bias or differential value\(h^{\pi}\), which measures transient advantage relative to that long-run rate.
24.1 Learning goals
After reading this chapter, students should be able to:
distinguish discounted, finite-horizon, and average-reward objectives;
define the average reward, gain, and bias functions for a fixed policy;
compute average reward from the stationary distribution of a policy-induced Markov chain;
derive the Poisson equation for the bias function;
explain why the bias function is unique only up to an additive constant;
solve the average-reward policy-evaluation equation by imposing a normalization condition;
state the average-reward Bellman optimality equation;
implement relative value iteration and average-reward policy iteration in finite examples;
connect average-reward values to the limiting behavior of discounted values as \(\gamma\uparrow 1\);
explain unichain and multichain issues;
implement a simple sample-based average-reward learning method;
use AI tools to audit recurrence assumptions, normalizations, and algorithmic update equations.
Discounting is mathematically convenient because it makes the Bellman operator a contraction. But in a continuing system, discounting may introduce an artificial preference for short-term reward. Examples include queueing systems, inventory control, machine maintenance, online recommendation, server allocation, and repeated portfolio rebalancing. In such settings, the system does not naturally terminate; it runs indefinitely.
The average-reward objective asks for reward per unit time:
In discounted RL, the main unknown is a value function. In average-reward RL, the main unknowns are a scalar long-run reward rate \(\rho\) and a relative value function \(h\).
The interactive figure compares the discounted value scale with the average-reward scale. As \(\gamma\) approaches one, discounted values often grow like \(\rho/(1-\gamma)\). The average reward \(\rho\) remains finite.
24.3 21.2 Fixed-policy average reward
Consider a finite MDP
\[
\mathcal M=(\mathcal S,\mathcal A,P,r),
\]
where \(\mathcal S=\{1,\ldots,n\}\) and \(\mathcal A(s)\) is finite. A stationary randomized policy \(\pi(a\mid s)\) induces a Markov chain with transition matrix
This formula is one of the cleanest mathematical facts in average-reward RL. It says that the long-run reward is the stationary average of the one-step reward.
Average reward under an ergodic policy. Suppose \(P_{\pi}\) is irreducible and aperiodic on a finite state space, with stationary distribution \(d_{\pi}\). Then
Reason. The Markov chain spends asymptotic fraction \(d_{\pi}(x)\) of time in state \(x\). Therefore the long-run average reward is the stationary expectation of \(r_{\pi}\).
This result explains why average-reward RL requires more Markov-chain structure than discounted RL. Discounted values are well defined for every bounded reward function and every finite transition matrix when \(\gamma<1\). Average reward depends on limiting state frequencies.
24.3.1 Python example: stationary distribution and average reward
The average reward \(\rho^{\pi}\) tells us the long-run reward per step. It does not tell us which states are temporarily better or worse. For this we need the bias function, also called the differential value function.
when this centered infinite sum is well defined. The summand subtracts the long-run average reward rate. The bias therefore measures transient advantage relative to steady-state behavior.
This is a discrete Poisson equation for the Markov chain.
The bias function is not unique. If \(h^{\pi}\) solves the Poisson equation, then \(h^{\pi}+c\mathbf 1\) also solves it for any constant \(c\). Only differences \(h^{\pi}(s)-h^{\pi}(x)\) are meaningful.
To obtain a unique solution, impose a normalization such as
\[
h^{\pi}(s_0)=0
\]
for a reference state \(s_0\), or
\[
d_{\pi}^T h^{\pi}=0.
\]
The plot shows reward, centered reward, and bias. Positive bias means that starting from that state gives a favorable transient position compared with the average long-run reward rate.
24.4.1 Python example: solving the Poisson equation
The following example imposes the normalization \(h(s_0)=0\) by replacing one equation with the constraint.
import numpy as npP = np.array([ [0.70, 0.25, 0.05], [0.20, 0.60, 0.20], [0.10, 0.30, 0.60]])r = np.array([1.0, 2.0, 4.0])n =len(r)A = np.vstack([P.T - np.eye(n), np.ones(n)])b = np.append(np.zeros(n), 1.0)d, *_ = np.linalg.lstsq(A, b, rcond=None)rho = d @ r# Solve (I - P) h = r - rho 1 with h[0] = 0.M = np.eye(n) - Pc = r - rho * np.ones(n)M[0, :] =0.0M[0, 0] =1.0c[0] =0.0h = np.linalg.solve(M, c)print("rho:", round(rho, 4))print("bias h with h[0]=0:", np.round(h, 4))print("Poisson residual:", np.round(rho + h - (r + P @ h), 12))
rho: 2.1404
bias h with h[0]=0: [0. 3.1579 7.0175]
Poisson residual: [0. 0. 0.]
24.5 21.4 Matrix form and the fundamental matrix
For an ergodic finite chain, define the rank-one matrix
\[
\Pi=\mathbf 1 d_{\pi}^T.
\]
The matrix \(\Pi\) maps any vector to a constant vector equal to its stationary mean. The centered reward vector is
\[
g=r_{\pi}-\rho^{\pi}\mathbf 1.
\]
Since \(d_{\pi}^Tg=0\), the Poisson equation can be solved on the subspace of mean-zero functions. A common formula uses the fundamental matrix
This formula is useful theoretically, but for large state spaces one usually avoids forming the inverse. Instead, iterative methods and stochastic approximation methods are used.
24.5.1 Python example: mean-zero bias using the fundamental matrix
This relationship is useful pedagogically because it shows that average-reward RL is not unrelated to discounted RL. It is the limiting case where the discount factor approaches one, but the limit must be normalized correctly.
24.6.1 Python example: discounted values approaching gain and bias
For control, we want a policy with maximal long-run average reward. Under appropriate finite unichain assumptions, there exists a scalar \(\rho^*\) and a bias function \(h^*\) satisfying the average-reward Bellman optimality equation
import numpy as npP = np.array([ [[0.70, 0.25, 0.05], [0.40, 0.50, 0.10]], [[0.20, 0.60, 0.20], [0.10, 0.60, 0.30]], [[0.10, 0.30, 0.60], [0.05, 0.25, 0.70]]])r = np.array([ [1.0, 0.8], [2.0, 2.4], [3.0, 3.2]])n_states, n_actions = r.shaperef =0policy = np.zeros(n_states, dtype=int)def evaluate_policy(policy): P_pi = np.array([P[s, policy[s]] for s inrange(n_states)]) r_pi = np.array([r[s, policy[s]] for s inrange(n_states)])# Unknowns are rho and h. Use equations rho + h - P h = r,# plus h[ref] = 0. A = np.zeros((n_states +1, n_states +1)) b = np.zeros(n_states +1)for s inrange(n_states): A[s, 0] =1.0 A[s, 1+ s] =1.0 A[s, 1:] -= P_pi[s] b[s] = r_pi[s] A[n_states, 1+ ref] =1.0 sol, *_ = np.linalg.lstsq(A, b, rcond=None)return sol[0], sol[1:]for it inrange(20): rho, h = evaluate_policy(policy) q = np.zeros((n_states, n_actions))for s inrange(n_states):for a inrange(n_actions): q[s, a] = r[s, a] + P[s, a] @ h new_policy = q.argmax(axis=1)print(f"iter {it}: rho={rho:.4f}, policy={policy}, h={np.round(h, 3)}")if np.array_equal(new_policy, policy):break policy = new_policyprint("final policy:", policy)
iter 0: rho=1.8947, policy=[0 0 0], h=[-0. 2.632 4.737]
iter 1: rho=2.5951, policy=[1 1 1], h=[-0. 2.732 4.293]
final policy: [1 1 1]
24.10 21.9 Unichain and multichain issues
Average-reward MDPs are more delicate than discounted MDPs because the long-run average may depend on which recurrent class is reached.
A policy-induced Markov chain is unichain if it has one recurrent class, possibly with transient states. An MDP is often called unichain if every stationary deterministic policy induces a unichain Markov chain.
In a unichain setting, the average reward of a fixed policy is independent of the initial state after transients disappear. In a multichain setting, a policy may have several recurrent classes with different average rewards. Then
\[
\rho^{\pi}(s)
\]
may depend on \(s\).
The figure contrasts an ergodic chain, where all initial distributions lead to the same average reward, with a multichain example, where different initial states may enter different recurrent classes.
For a first graduate course, it is reasonable to focus on finite unichain average-reward MDPs. This avoids many technical cases while preserving the main mathematical ideas: gain, bias, Poisson equations, and relative dynamic programming.
24.11 21.10 Learning from samples: differential TD and R-learning
When the transition probabilities are unknown, the average reward and bias must be learned from data. For policy evaluation, a differential TD update has the form
These algorithms are stochastic approximation methods for the average-reward optimality equations. Their convergence theory requires careful assumptions about exploration, step sizes, recurrence, and boundedness.
24.11.1 Python example: a tiny R-learning experiment
but the asymptotic variance includes autocorrelation terms. Positive autocorrelation reduces the effective sample size.
Third, regenerative cycles provide a clean estimation idea. If the chain repeatedly returns to a reference state \(s_0\), define cycle lengths and rewards by
final running average: 2.1579
first 5 running averages: [1. 1. 1.3333 1.5 1.6 ]
last 5 running averages: [2.1575 2.1576 2.1577 2.1578 2.1579]
24.13 21.12 Average reward versus discounting in modeling
When should one use average reward rather than discounting?
Use average reward when:
the task is continuing and has no natural terminal time;
performance is naturally measured per unit time;
delaying reward should not automatically make it less important;
the system is expected to operate in steady state;
recurrence and stability assumptions are reasonable.
Use discounting when:
near-term reward should be preferred by design;
the modeler wants a contraction mapping with simple error bounds;
long-range predictions are highly uncertain;
the task is episodic or effectively finite-horizon;
algorithmic stability is more important than exact steady-state interpretation.
Average reward is not simply discounted reward with \(\gamma=1\). It requires a different normalization, a different value object, and stronger recurrence assumptions.
24.14 21.13 AI-assisted learning components
24.14.1 AI prompt: check recurrence assumptions
Ask an AI assistant:
I have a finite MDP and want to use an average-reward objective. What recurrence assumptions should I check before using the equation \(\rho+h=Th\)? Explain unichain and multichain behavior with a small example.
Then verify that the response distinguishes discounted well-posedness from average-reward well-posedness.
24.14.2 AI prompt: audit a Poisson-equation solution
Ask:
Here are \(P\), \(r\), \(\rho\), and \(h\). Check whether \(\rho\mathbf 1+h=r+Ph\) and whether the normalization is stated clearly. Do not assume \(h\) is unique.
This is a useful way to catch the common mistake of treating \(h\) as an absolute value function.
24.14.3 AI prompt: compare objectives
Ask:
Give one application where discounted reward is more appropriate and one application where average reward is more appropriate. For each, state the mathematical reason.
A good answer should mention time preference, stationarity, continuing operation, and recurrence.
24.15 21.14 Summary
Average-reward MDPs replace discounted cumulative value by long-run reward per time step. For a fixed policy, the gain is often computed as a stationary expectation:
\[
\rho^{\pi}=d_{\pi}^T r_{\pi}.
\]
The transient part is described by a bias function satisfying the Poisson equation
The bias is defined only up to an additive constant, so relative value iteration and policy evaluation require normalization. Compared with discounted RL, average-reward RL is mathematically more delicate because recurrence and ergodicity assumptions matter.
24.16 Exercises
24.16.1 Conceptual exercises
Explain why discounting can distort a continuing control problem.
What is the difference between gain and bias?
Why is the bias function not unique?
What does the span seminorm measure, and why is it appropriate for average-reward algorithms?
Explain why multichain behavior is a problem for average-reward theory.
24.16.2 Mathematical exercises
Let \(P_{\pi}\) be an irreducible finite Markov chain with stationary distribution \(d_{\pi}\). Prove that \(\rho^{\pi}=d_{\pi}^Tr_{\pi}\).
Starting from the definition of the centered return, derive the Poisson equation for \(h^{\pi}\).
Show that if \(h\) solves \(\rho\mathbf 1+h=r+Ph\), then \(h+c\mathbf 1\) also solves it.
Prove that \(d^T(r-\rho\mathbf 1)=0\) when \(\rho=d^Tr\).
Verify that \(Z=(I-P+\mathbf 1d^T)^{-1}\) gives a mean-zero solution of the Poisson equation under ergodicity.
Derive the average-reward Bellman optimality equation from one-step decomposition.
Show that relative value iteration is invariant under adding a constant to \(h_k\).
For a two-state Markov chain, compute \(\rho\) and \(h\) explicitly.
24.16.3 Computational exercises
Modify the policy-evaluation Python code to use normalization \(d^T h=0\) instead of \(h(0)=0\).
Implement relative value iteration for a four-state MDP.
Compare the greedy policies obtained from discounted value iteration for \(\gamma=0.9,0.99,0.999\) with the average-reward greedy policy.
Simulate a Markov chain and estimate average reward by a running average. Plot convergence.
Implement R-learning for the three-state MDP and study sensitivity to \(\alpha\), \(\beta\), and \(\epsilon\).
Construct a multichain example where \(\rho^{\pi}(s)\) depends on \(s\).
Estimate the effective sample size of a reward trajectory using empirical autocorrelation.
24.16.4 AI-assisted exercises
Ask an AI tool to explain the difference between discounted value and bias. Identify any places where it incorrectly treats the bias as an absolute value.
Give an AI tool a transition matrix and reward vector. Ask it to compute \(\rho\) and \(h\). Verify the result in Python.
Ask an AI tool to produce a multichain counterexample. Check whether the example truly has multiple recurrent classes.
Ask an AI tool to compare relative value iteration and discounted value iteration. Add corrections using the span seminorm and normalization.
Ask an AI tool to audit your R-learning code for off-by-one errors in the TD target.
24.17 Notes for instructors
This chapter is a natural bridge between stochastic processes and reinforcement learning. For MA Applied Math students, emphasize Poisson equations, invariant measures, and relative dynamic programming. For MS Statistics students, emphasize dependent data, stationary averages, autocorrelation, and estimation uncertainty. A good lecture sequence is:
start with stationary distributions and long-run reward;
derive the Poisson equation;
explain nonuniqueness of the bias;
implement relative value iteration;
discuss statistical estimation from one long trajectory;
contrast discounted and average-reward modeling choices.