🤖 machine learning

Bridging the Gap Between Average and Discounted TD Learning

This paper introduces a novel policy evaluation algorithm for the average-reward setting that utilizes two Markovian trajectories to guarantee convergence without dimension-dependent terms and achieves quadratic sample complexity, thereby matching the theoretical efficiency of discounted TD learning.

Original authors: Haoxing Tian, Zaiwei Chen, Ioannis Ch. Paschalidis, Alex Olshevsky

Published 2026-05-05

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Haoxing Tian, Zaiwei Chen, Ioannis Ch. Paschalidis, Alex Olshevsky

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "Forever Job" vs. The "Short-Term Gig"

Imagine you are training a robot to do a job. There are two main ways to tell the robot what "doing a good job" means:

The Discounted Approach (The Short-Term Gig): This is like paying a worker for a specific task today. You care a lot about the money they make right now, and you care less about what they might make next year. In math, this is called "discounted learning." It's easy to analyze because the rules are clear and stable.
The Average-Reward Approach (The Forever Job): This is like paying a CEO a salary based on the company's long-term performance over an infinite horizon. You don't care about a single good day or a single bad day; you care about the steady average over forever. This is the "average-reward" setting.

The Problem:
For a long time, the math for the "Forever Job" (Average-Reward) has been a nightmare for scientists. In the "Short-Term Gig" world, the math behaves like a rubber band that always snaps back to a single, clear center point. But in the "Forever Job" world, the math is like a slippery slide. The rules don't force the robot to settle on just one answer; it could slide around forever, or stop at different spots depending on how you pushed it.

Because of this, previous attempts to fix the robot's learning for the "Forever Job" had to make weird, unrealistic assumptions (like pretending the robot can't be in a specific state) or accepted that the robot might never settle on a single, reliable answer.

The Solution: A New Way to Walk the Slide

The authors of this paper introduced a new algorithm to fix this. They managed to make the "slippery slide" behave like a stable rubber band again, without making those weird assumptions.

Here is how they did it, using a few metaphors:

1. The "Double-Chain" Trick (The Twin Walkers)

To solve the math problem, the authors created an algorithm that uses two independent robots walking around at the same time.

The Analogy: Imagine you are trying to guess the average height of people in a city. If you ask one person, "What is the average height of the person standing next to you?" and then multiply that by "What is the average height of a random person you just met?", you get the wrong answer because the two people aren't independent.
The Fix: The authors use two separate "chains" of data. One robot observes the current situation, and a completely different robot (running on a parallel track) observes a random state. By keeping these two observations separate and independent, the math stops getting "confused" and can find the true average.

2. The "Gradient Splitting" (The Team of Two)

The paper uses a mathematical technique called "gradient splitting."

The Analogy: Imagine you are trying to push a heavy boulder up a hill, but you can only see the slope from two different angles. If you try to push based on just one angle, you might push the wrong way.
The Fix: The algorithm splits the "pushing force" into two parts. One part handles the immediate change, and the other part handles the long-term average. When you combine these two "partial pushes," they perfectly recreate the force needed to push the boulder straight to the top, even though neither part could do it alone. This allows the math to work smoothly, just like it does in the "Short-Term Gig" world.

3. The "Single-Chain" Upgrade (The Solo Walker)

While using two robots works great, it's expensive. The authors also created a version that uses only one robot.

The Analogy: This is like a solo walker who keeps a mental "notebook" of where they've been. Instead of asking a second person for a random data point, the walker estimates the average based on their own history.
The Trade-off: This is slightly less efficient (it takes a bit longer to learn), but it's much more practical because you only need one robot running.

Why This Matters (The Results)

The paper claims three major victories over previous methods:

It Works for Everyone (Tabular & Linear): Previous methods often broke if you tried to use them on simple, small problems (called "tabular" settings) or if you tried to use them on complex, large problems. This new method works for both without needing special rules. It's a universal key.
It Finds One Answer: Old methods sometimes let the robot stop at different spots depending on how you started it. This new method guarantees the robot will always stop at the exact same, unique spot, no matter how you start it.
It's Faster and Smarter: The math shows that this new method learns much faster than previous attempts.
- The Condition Number: In math, the "condition number" is like a measure of how "messy" or "slippery" the problem is. Previous methods got slower and slower as the problem got messier (scaling with the fourth power of the messiness). This new method scales with the square of the messiness.
- The Metaphor: Imagine trying to walk through mud. Old methods got stuck and slowed down exponentially as the mud got deeper. This new method is like putting on snowshoes; you still sink a little, but you keep moving at a steady, manageable pace.

Summary

The paper bridges the gap between the easy math of short-term learning and the difficult math of long-term learning. By using a clever "two-robot" trick and a "splitting" technique, they created an algorithm that is stable, reliable, and fast, finally making long-term average learning as robust as short-term learning.

Technical Summary: Bridging the Gap Between Average and Discounted TD Learning

Problem Statement

Temporal Difference (TD) learning is a cornerstone of reinforcement learning, yet its theoretical analysis in the average-reward setting lags significantly behind the discounted setting. In the discounted case, the Bellman operator is a contraction mapping, ensuring unique solutions and straightforward convergence analysis. Conversely, in the average-reward setting, the Bellman operator is not contractive with respect to any norm, and the solution to the corresponding Bellman equation is not unique (it is defined only up to an additive constant).

Existing literature addressing average-reward TD suffers from several limitations compared to the discounted case:

Restrictive Assumptions: Many methods require assumptions (e.g., $\Phi\theta \neq ce$ ) that exclude the tabular setting.
Convergence Guarantees: Some approaches only guarantee convergence to a sample-path-dependent fixed point or a set, rather than a unique, deterministic solution.
Dimension Dependence: Convergence bounds often contain explicit factors of the parameter dimension $d$ .
Condition Number Scaling: State-of-the-art sample complexities often exhibit quartic dependence on the problem's condition number ( $O(\eta^{-4})$ ), whereas the discounted setting achieves quadratic scaling ( $O(\eta^{-2})$ ).
Algorithmic Complexity: Achieving better scaling in prior works often required complex variance-reduction techniques (e.g., nested loops), deviating from the simplicity of standard TD.

Methodology

The authors propose a novel approach to policy evaluation in the average-reward setting by formulating the solution to the Bellman equation as a constrained optimization problem. The core insight is that the relative value function $W^*$ must satisfy a steady-state constraint ( $\mu^\top W^* = 0$ ).

1. Double-Chain Algorithm

To solve the projected Bellman equation $W^* = \Pi T_\pi W^*$ , where $\Pi = I - e\mu^\top$ , the authors derive a stochastic update rule. A key challenge in stochastic approximation for this setting is the "double sampling" issue: estimating the term $\mu\mu^\top(R + W_t)$ requires the expectation of a product of random variables, which cannot be estimated from a single trajectory due to correlation.

To resolve this, the authors introduce a Double-Chain Algorithm that utilizes two independent Markov chains ( $\{s_t\}$ and $\{\hat{s}_t\}$ ) in each iteration.

Update Rule: The parameter vector $\theta_t$ $θ_{t}$ is updated using two components:
- $g(s_t, s'_t, \theta_t)$ : Estimates the standard TD error term $D(R + P\Phi\theta_t - \Phi\theta_t)$ .
- $f(s_t, \hat{s}_t, \theta_t)$ : Estimates the constraint term $-\mu\mu^\top(R + \Phi\theta_t)$ using the independent sample $\hat{s}_t$ to break the correlation.
Linear Approximation: The method generalizes to linear function approximation ( $W \approx \Phi\theta$ ) by projecting the updates onto the feature space.

2. Single-Chain Algorithm

To avoid the computational overhead of maintaining two chains, the authors propose a Single-Chain Algorithm inspired by Gradient TD (GTD).

Mechanism: Instead of sampling a second independent state $\hat{s}_t$ , the algorithm maintains an auxiliary variable $w_t$ that tracks the expectation $E[\phi(s)] = \Phi^\top\mu$ .
Update: The term $\phi(\hat{s}_t)$ in the double-chain update is replaced by $w_t$ . The variable $w_t$ is updated via a separate stochastic approximation step to converge to $\Phi^\top\mu$ .
Trade-off: While this simplifies the sampling requirement to a single trajectory, the analysis shows a slightly worse dependence on the condition number compared to the double-chain variant.

3. Theoretical Framework: Gradient Splitting

The convergence analysis relies on the technique of gradient splitting [19]. The authors demonstrate that the expected update direction of their algorithm acts as a "gradient splitting" of a specific composite quadratic function:
$f(\theta) = \|\Phi(\theta - \theta^*)\|_{\text{Dir}}^2 + (\mu^\top\Phi(\theta - \theta^*))^2$
This allows the authors to analyze the algorithm using standard Stochastic Gradient Descent (SGD) recursion techniques, despite the non-contractive nature of the underlying Bellman operator.

Key Contributions

The paper claims to bridge the theoretical gap between average-reward and discounted TD learning by achieving the following features simultaneously:

Unique, Sample-Independent Fixed Point: The proposed algorithms converge almost surely to a single, deterministic solution $\theta^*$ that is independent of the random trajectory and initialization.
Applicability to Tabular and Linear Settings: The analysis holds for both tabular cases (where $\Phi = I$ ) and linear function approximation, without requiring the restrictive assumption $e \notin \text{span}(\Phi)$ .
Dimension-Free Bounds: The convergence bounds do not contain explicit factors of the dimension $d$ (beyond those inherent in $\|\theta^*\|$ or $\|\theta_0\|$ ).
Last Iterate Convergence: Results are guaranteed for the last iterate, matching the standard in discounted TD, rather than relying on iterate averaging.
Improved Condition Number Scaling:
- The Double-Chain algorithm achieves a sample complexity of $\tilde{O}(\epsilon^{-1}\eta_1^{-2})$ , where $\eta_1$ is a condition number defined as $\min_{\|x\|=1} (\|\Phi x\|_{\text{Dir}}^2 + (\mu^\top\Phi x)^2)$ . This matches the quadratic scaling seen in the discounted setting.
- The Single-Chain algorithm achieves $\tilde{O}(\epsilon^{-1}\eta^{-4})$ (quartic), which is an improvement over some prior works but slightly worse than the double-chain variant.
Algorithmic Simplicity: The quadratic scaling is achieved without variance reduction techniques (e.g., nested loops or periodic full batches), maintaining the simplicity of plain TD updates.

Results

The authors provide finite-sample analysis for both algorithms under i.i.d. and Markovian sampling, with both constant and decaying step sizes.

Theoretical Bounds: Theorems 4.1–4.3 establish convergence rates and sample complexities. The double-chain method matches the state-of-the-art for discounted TD in terms of parameter scaling.
Numerical Experiments: The algorithms were tested on 15 tabular MDPs from OpenAI Gym and MO-Gymnasium.
- The results show that the proposed methods generally outperform prior baselines (including [10], [11], [12], [17], [18], and [21]) in terms of approximation error relative to the true solution.
- The experiments confirm that the methods converge to the unique solution, whereas some baselines (which converge to sets or sample-dependent points) show higher variance or error in the tabular setting.

Significance

The paper claims to resolve persistent theoretical caveats associated with average-reward TD analysis. By utilizing gradient splitting and a two-chain (or single-chain with auxiliary variable) sampling strategy, the authors demonstrate that average-reward TD can achieve the same favorable convergence properties as discounted TD:

Uniqueness: Convergence to a well-defined, unique solution.
Generality: Applicability to tabular and linear settings without restrictive assumptions.
Efficiency: Quadratic dependence on the condition number without the need for complex variance-reduction machinery.

This work suggests that the theoretical difficulties of the average-reward setting can be overcome by reformulating the problem as a constrained optimization task and leveraging specific sampling strategies to handle the non-contractive nature of the Bellman operator.