Average-Reward Control for Continuing Tasks

This builds on on-policy control with approximation, which carried the semi-gradient update over to action values $\hat{q}(s,a,\mathbf{w})$ and solved Mountain Car — an episodic, discounted task. That lesson ended on a warning: once the state space is too large to enumerate, discounting the future starts to come apart. This lesson makes that precise and supplies the replacement, the average-reward formulation of continuing control.

Average reward: a new problem setting

So far everything has been episodic and discounted. There is a third classical setting for the goal of an MDP, standing alongside them: the average-reward setting, which applies to continuing problems — interaction that goes on forever with no terminal state and no restarts. Unlike the discounted case there is no discounting; the agent cares just as much about delayed reward as immediate reward. This setting is central to the classical theory of dynamic programming and less common in reinforcement learning, but with function approximation it becomes necessary — for reasons the next section makes precise.¹

The idea in one line: instead of the total reward collected from a state (which needs discounting to stay finite), the objective is the rate of reward the policy sustains forever, and states are measured by how much better or worse than that rate they start out.

The quality of a policy $\pi$ is its long-run average reward per step, denoted $r(\pi )$:

where the expectations are conditioned on the start state $S_0$ and on actions following $\pi$ thereafter. Here ${\mu }_{\pi }$ is the steady-state distribution, ${\mu }_{\pi }(s)\doteq {\lim }_{t\to \infty }\mathrm{Pr}\{S_t=s\mid A_{0:t-1}\sim \pi \}$, assumed to exist for any $\pi$ and to be independent of the start state. That independence is the assumption of ergodicity: where the MDP starts, and any early decision, has only a temporary effect; in the long run the probability of being in a state depends only on the policy and the transition dynamics.

The steady-state distribution ${\mu }_{\pi }$ is the special distribution under which, if you select actions according to $\pi$, you stay in the same distribution:

Selecting an action under $\pi$ from a state drawn from ${\mu }_{\pi }$ leaves the next-state distribution equal to ${\mu }_{\pi }$ again — the distribution is stationary under the policy, and that stationarity is what makes the average rate of reward well defined.

Why discounting fails with approximation

Why abandon the discounted setting we have used all along? Because with function approximation it stops carrying information. Consider a continuing problem with no beginning or end and no clearly identified states — states represented only by feature vectors that may do little to distinguish one from another. In the extreme, imagine all the feature vectors are the same, so every state looks identical to the approximator. Then the only thing the problem can be judged on is the reward sequence, and performance must be assessed purely from that.

Now try to use discounting. At each step you could measure the discounted return; some returns are big and some small, so you would average them over a long interval — which is just the average-reward idea again. The decisive fact is what that average equals. For any policy $\pi$, the average of the discounted returns is proportional to the average reward:

The discount rate $\gamma$ enters only through the constant factor $1/(1-\gamma )$, which is the same for every policy. So it cancels out of any comparison: the ordering of all policies under the discounted objective is identical to their ordering under the undiscounted average-reward objective. The discount rate has no effect on which policy is best — it could be set to zero and the ranking would be unchanged.

Two arguments make this equality solid. The first is a symmetry count. Every time step is identical to every other, so with discounting each reward appears once in each position across the family of returns: the reward at step $t$ shows up undiscounted in the return that begins at $t-1$, discounted once in the return that begins at $t-2$, discounted $k$ times in the return that begins $k$ steps earlier. Its total weight across all returns is $1+\gamma +{\gamma }^2+\cdots =1/(1-\gamma )$. Since every reward carries that same weight, the average of the discounted returns is $1/(1-\gamma )$ times the average reward, $r(\pi )/(1-\gamma )$.

The second is a direct derivation that pins it exactly: the same fact follows from the Bellman equation in four lines. Define the objective as the discounted value averaged over the on-policy distribution, $J(\pi )={\sum }_s{\mu }_{\pi }(s)v_{\pi }(s)$, with $v_{\pi }$ the ordinary discounted value function. Expand $v_{\pi }$ by its Bellman equation and use the steady-state property of ${\mu }_{\pi }$:

The first reward term collapsed to $r(\pi )$ because ${\sum }_s{\mu }_{\pi }(s){\sum }_a\pi {\sum }_{s^{\prime },r}pr$ is precisely the definition of average reward; the inner double sum over $s,a$ in the second term collapsed to ${\mu }_{\pi }(s^{\prime })$ because ${\mu }_{\pi }$ is stationary under $\pi$. Unrolling $J(\pi )=r(\pi )+\gamma J(\pi )$ gives $J(\pi )=r(\pi )+\gamma r(\pi )+{\gamma }^{2}r(\pi )+\cdots =r(\pi )/(1-\gamma )$. The discount $\gamma$ appears only in that policy-independent constant, so it cannot change which policy maximizes $J$.

The general version of this argument shows that optimizing discounted value over the on-policy distribution is identical to optimizing undiscounted average reward — the value of $\gamma$ has no effect. So discounting has no role to play in the definition of the control problem with function approximation. One can still use $\gamma$ inside a solution method, turning it from a problem parameter into an algorithm parameter, but there is a deeper loss behind this.

The root cause of the difficulty is the policy improvement theorem. In the tabular case, improving the discounted value of one state is guaranteed to improve the overall policy; with function approximation, that guarantee is gone. Changing the weights to raise $\hat{q}$ at one state can lower it at others, because the states share parameters — so a greedy step is no longer certain to help. Without the improvement theorem the discounted control setting loses the property that justified it, and the average-reward setting is the natural replacement.

Differential returns and value functions

If there is no discounting, what plays the role of the return? In the average-reward setting the return is defined in terms of differences between each reward and the average reward $r(\pi )$. This is the differential return:

Subtracting $r(\pi )$ from every reward is what makes this infinite sum converge: a policy earning exactly its own average rate contributes zero on balance, and the differential return measures only the transient advantage or deficit of starting in a particular state. The corresponding value functions are the differential value functions, defined with the same expectations as before, $v_{\pi }(s)\doteq {\mathbb{E}}_{\pi }[G_t\mid S_t=s]$ and $q_{\pi }(s,a)\doteq {\mathbb{E}}_{\pi }[G_t\mid S_t=s,A_t=a]$, now with the differential return inside.

The differential value functions satisfy Bellman equations of the familiar shape, obtained from the discounted ones by two edits: drop every $\gamma$, and replace each reward $r$ by $r-r(\pi )$. For state values,

and for action values,

The optimality equations replace $r(\pi )$ by its maximum over policies, ${\max }_{\pi }r(\pi )$, and take the greedy max over next actions — the same edits applied to $v_{\ast }$ and $q_{\ast }$. There is also a differential TD error, again the discounted TD error with $\gamma$ removed and reward replaced by reward-minus-average. For action values,

where ${\bar{R}}_{t+1}$ is the current estimate at time $t$ of the average reward $r(\pi )$. (The state-value differential TD error is the same with $\hat{v}$ in place of $\hat{q}$.) With these definitions, most of the algorithms and theoretical results carry over to the average-reward setting unchanged.

Differential semi-gradient Sarsa

Assembling the pieces gives the control algorithm for the continuing, average-reward setting. The weight update is the average-reward version of semi-gradient Sarsa: exactly equation for one-step Sarsa, but with the differential TD error in place of the discounted one,

with ${\delta }_t$ the differential action-value TD error above. Two things are learned at once: the weights $\mathbf{w}$, as always, and the average-reward estimate $\bar{R}$, which is nudged by the same TD error. Because ${\delta }_t$ measures how much better the last transition was than expected, its running total signals whether $\bar{R}$ is set too low or too high.

There is no episode loop — the interaction is one unbroken stream of steps, which is what continuing means. The average-reward estimate uses its own step size $\beta$, typically smaller than $\alpha$, so $\bar{R}$ tracks the slow drift of the policy's reward rate while $\mathbf{w}$ adapts faster to individual states.

Worked example: the access-control queuing task

For example: ten servers face a single queue. Customers arrive with one of four priorities, paying $1$, $2$, $4$, or $8$ if admitted to a free server and $0$ if rejected. Each step the agent looks at the customer at the head of the queue and either accepts (assigns a free server, if one exists) or rejects (drops the customer for zero reward). Each busy server frees itself with probability $p=0.06$ per step. The queue never empties and priorities are uniform, so the state is just the pair (number of free servers, priority of the head customer) — $11\times 4=44$ states — and there are two actions. The goal is to maximize long-run reward with no discounting, which is what forces the average-reward setting.

Run differential semi-gradient Sarsa with $\alpha =0.01$, $\beta =0.01$, $\epsilon =0.1$, all action values and $\bar{R}$ starting at zero. The policy it finds is intuitive. When many servers are free, accept every customer — there is no reason to hold capacity. As free servers grow scarce, start rejecting the low-priority customers to hold capacity open for the high-priority ones still to come: with one or two free servers the agent rejects priority-$1$ and often priority-$2$ customers while still admitting priority-$4$ and priority-$8$. The threshold is a tradeoff — rejecting a priority-$1$ customer forfeits $1$ now but keeps a server open for a possible priority-$8$ later, and that gamble only pays when free servers are few enough that the wait for a replacement is short. As a byproduct $\bar{R}$ converges to the policy's true average reward, the per-step rate this accept/reject rule sustains.

The average-reward revival and continuous control

The differential machinery of this lesson has become more, not less, relevant as reinforcement learning has scaled to deep networks.

Average reward comes back for deep RL. This chapter argues the average-reward setting is the appropriate formulation for continuing problems under function approximation, and recent deep-RL work has taken that seriously. Naik et al. (2019), Discounted reinforcement learning is not an optimization problem, NeurIPS Optimization Foundations of RL workshop, sharpened the point that discounted control with function approximation is not optimizing a well-defined objective, and average-reward deep methods such as RVI-Q and differential Q-learning descendants (Wan, Naik & Sutton, 2021, Learning and planning in average-reward Markov decision processes, ICML) carry the differential-return machinery of this lesson into deep networks.² The $\bar{R}$ update — one scalar tracking the reward rate, nudged by the same TD error that trains the weights — carries over essentially unchanged.

Deterministic policy gradients for continuous control. When actions are continuous and the critic is differentiable, one can push the gradient of $\hat{q}$ through the action into a deterministic policy: DDPG (Lillicrap et al., 2016, Continuous control with deep reinforcement learning, ICLR) and its successor TD3 (Fujimoto et al., 2018, Addressing function approximation error in actor-critic methods, ICML) do exactly this, solving the Mountain-Car-like problem of continuous throttle that the discrete $\{-1,0,+1\}$ action set sidesteps.³ They inherit the off-policy instabilities the next lesson names, which is why they rely on target networks and replay.

What changed, and what comes next

The mechanical part of average-reward control is small — swap the discounted TD error for the differential one, track a running estimate $\bar{R}$ of the reward rate with its own step size, and drop the episode loop. What changed underneath is the whole justification. Function approximation broke discounting: the discounted objective ranks policies identically to the average-reward objective, so $\gamma$ carries no information, and the policy improvement theorem that justified greedy control is lost. The average-reward setting replaces it — the differential return, the differential value functions, and differential semi-gradient Sarsa give a control method for continuing tasks that never invokes a discount factor at all.

One assumption remains: all of this was on-policy. The data came from the very policy being evaluated. The next lesson lets the behavior and target policies diverge, and finds that off-policy learning, bootstrapping, and function approximation together form a deadly triad that can make the weights diverge — the sharpest instability in all of approximate reinforcement learning.