Deriving the Average-Reward Bellman Equation for Continuing Tasks

Set the discount factor to 1 in a continuing task and the return sum diverges. There is nothing finite left for a Bellman equation to solve for. Average reward is what you reach for when the horizon never ends and time preference was never the point.

Why Discounting Stops Working on a Continuing Task

A continuing task has no terminal state and no forced reset. The agent acts, the environment responds, and the process keeps going. There is no episode boundary to cut the return into a finite sum.

With $\gamma < 1$, the discounted return converges. That convergence is not free. It buys you a time-preferenced objective: reward now counts more than reward later, and the effective horizon is roughly $1/(1-\gamma)$ steps. That is a real objective, and sometimes it is the right one. If the task terminates, or if you genuinely prefer reward sooner, discounting is the correct tool.

The weak model is "just push $\gamma$ close to 1 and you approximate the undiscounted objective." You do not. As $\gamma \to 1$, the effective horizon stretches, and value magnitudes grow without bound because the sum is being asked to stay finite while the discounting that made it finite disappears. You have not recovered long-run performance. You have changed the objective and made the numbers harder to work with.

The decision boundary is worth naming plainly:

This article assumes you already know the discounted Bellman expectation and optimality relationships and the one-step return decomposition. We only need the one-step structure here, with one substitution.

Notation and the Average-Reward Objective

Reuse the standard MDP notation. States $s \in \mathcal{S}$, actions $a \in \mathcal{A}$, transition kernel $P(s' \mid s, a)$, reward function $r(s, a)$, and a stationary policy $\pi(a \mid s)$.

The average reward, or gain, of a policy is the limit of expected reward per step:

$g_\pi = \lim_{T \to \infty} \frac{1}{T} \mathbb{E}_\pi \left[ \sum_{t=0}^{T-1} r(s_t, a_t) \right].$

That limit is what makes the analysis harder than the discounted case. Discounting gave us a contraction and a unique fixed point. A rate does not.

The quantity that stays finite is the bias, the transient offset from the long-run rate. Define it as a finite-horizon limit of the centered sum:

$V_\pi(s) = \lim_{T \to \infty} \mathbb{E}_\pi \left[ \sum_{t=0}^{T-1} \big( r(s_t, a_t) - g_\pi \big) \,\middle|\, s_0 = s \right].$

Read this carefully, because the raw infinite sum of reward-minus-gain is not an ordinary convergent series. In a periodic chain the partial sums cycle instead of settling, so the limit above is the object that actually exists. It is the expected cumulative excess reward over the first $T$ steps, taken as $T$ grows. Subtracting the rate removes the linear drift that made the raw sum diverge, and what remains is bounded.

One assumption carries the whole formulation. The Markov chain induced by the policy must be unichain: a single recurrent class, so the gain does not depend on the starting state. Without it, the gain becomes state-dependent and a single scalar $g$ no longer describes the policy.

Deriving the Average-Reward Bellman Equation

Start from the bias definition and decompose it one step, exactly as in the discounted derivation but with reward-minus-gain in place of discounted reward. Pull off the first term:

$V_\pi(s) = \mathbb{E}_\pi \big[ r(s, a) - g_\pi \big] + \mathbb{E}_\pi \big[ V_\pi(s') \big].$

Take expectations over the policy and the transition kernel. This is the policy-evaluation form:

$V_\pi(s) = \sum_a \pi(a \mid s) \sum_{s'} P(s' \mid s, a) \big[ r(s, a) - g_\pi + V_\pi(s') \big].$

The gain term is a constant. It is the same $g_\pi$ at every state and every step, so it cancels the divergence that would otherwise accumulate. That cancellation is what keeps the bias finite.

Now replace the policy average with a max over actions. This is the optimality form:

$V^*(s) = \max_a \sum_{s'} P(s' \mid s, a) \big[ r(s, a) - g^* + V^*(s') \big].$

The structure mirrors the discounted optimality equation. The difference is the constant $g^*$ sitting inside the bracket instead of a discount factor multiplying the successor term.

One caveat matters. The solution is unique only up to an additive constant. If $V$ solves the equation, so does $V + c$ for any constant $c$, because the constant cancels on both sides. Bias is therefore defined relative to a reference state, and you fix that reference by convention.

Picture the backup: reward-minus-gain on the edge, bias on the successor node. Place it beside the discounted diagram and the only change is the edge label.

Worked Example: Gain and Bias on a Small Continuing Chain

Take a three-state chain with a single action and fixed transitions. State 1 goes to state 2. State 2 goes to state 3. State 3 goes back to state 1. Rewards are $r_1 = 0$, $r_2 = 1$, $r_3 = 2$.

The chain is a single cycle, so it is unichain and the gain is the average reward per step:

$g = \frac{0 + 1 + 2}{3} = 1.$

Now solve the bias equations. With one action, the Bellman relationship is $V(s) = r(s) - g + V(s')$:

• $V(1) = 0 - 1 + V(2)$
• $V(2) = 1 - 1 + V(3)$
• $V(3) = 2 - 1 + V(1)$

These are consistent but underdetermined, as expected. Fix the reference $V(1) = 0$. Then $V(2) = 1$ and $V(3) = 1$.

Verify by plugging back in. For state 2: $1 - 1 + V(3) = 0 + 1 = 1 = V(2)$. For state 3: $2 - 1 + V(1) = 1 + 0 = 1 = V(3)$. Both hold.

Notice what the bias values are not. They are not rewards, and they are not discounted values. They measure transient advantage relative to the long-run rate. State 1 has zero immediate reward and the lowest bias, because it sits one step from the high-reward region. States 2 and 3 carry the same bias even though their rewards differ, because each is one step from the same successor structure. Two states with different immediate reward can carry identical bias for exactly that reason.

What Gain and Bias Actually Tell You

Gain is the long-run reward rate the policy sustains. It is the quantity average-reward control optimizes.

Bias is the transient offset from that rate. Once the rate is fixed, bias decides which states are worth being in.

Two mistakes show up constantly.

Common mistake: Treating bias as a value function and comparing bias magnitudes across different policies. The additive constant makes that comparison meaningless. Two policies can have identical behavior and bias vectors that differ by a constant.

Common mistake: Assuming the gain is state-independent without checking the unichain condition. If the chain has two recurrent classes, the agent's long-run rate depends on where it starts, and the single-scalar formulation silently breaks.

The decision rule is short. If you care about steady-state throughput, cost per step, or uptime, optimize gain. If you care about reaching a goal or about near-term reward, the discounted or episodic formulation fits better.

Assumptions, Failure Modes, and When to Use This

Unichain is the load-bearing assumption. Multichain MDPs require a state-dependent gain or a more elaborate formulation, and the clean derivation above does not apply.

Average-reward algorithms usually need to estimate the gain online. That adds a moving target to the update and complicates convergence reasoning compared with the discounted contraction argument. Relative value iteration and related methods exist precisely because the plain Bellman operator is not a contraction in the average-reward setting.

When not to use this:

• Episodic tasks with natural termination.
• Tasks where near-term reward genuinely matters more.
• Settings where you cannot assume a single recurrent class.

Where it earns its place: inventory management, admission control, and other continuing operational problems with no reset and no reason to prefer reward now over reward later.

Where to Go Next

Turn the derivation into a decision rule. Check whether the task terminates. Check whether time preference is real. Check whether the induced chain is unichain. If the task continues and you care about steady-state rate, the average-reward Bellman relationship is the right formal object, and gain and bias are the two quantities to track.

The next practical step is to implement a relative value iteration loop on the three-state chain above. Watch the gain estimate settle toward 1 while the bias values shift by a constant. That shift is the additive-constant freedom made visible, and seeing it once will keep you from misreading bias as a value function later.