Bridging the Gap Between Average and Discounted TD Learning

The analysis of Temporal Difference (TD) learning in the average-reward setting faces notable theoretical difficulties because the Bellman operator is not contractive with respect to any norm. This complicates standard analyses of stochastic updates that are effective in discounted settings. Although a considerable body of literature addresses these challenges, existing theoretical approaches come with limitations. We introduce a novel algorithm designed explicitly for policy evaluation in the average-reward setting, utilizing sampling from two Markovian trajectories. Our proposed method overcomes previous limitations by guaranteeing convergence to the unique solution of a properly defined projected Bellman equation. Notably, and in contrast to earlier work, our convergence analysis is uniformly applicable to both linear function approximation and tabular settings and does not involve explicit dimension-dependent terms in its convergence bounds. These results align with what is known to hold in the discounted setting. Furthermore, our algorithm achieves improved dependence on the problem's condition number, reducing the sample complexity from quartic, as in prior literature, to quadratic scaling, and thus matching the efficiency seen in the discounted setting.

Many real-world decision systems, such as robots, communication networks, and production systems, must perform well over a long period rather than only maximize short-term rewards. Reinforcement learning offers ways for such systems to learn from experience, but much of the clean theory for a common prediction-updating method, called temporal-difference learning, relies on discounting future rewards. Discounting makes the math easier, but it is not always the right objective when the goal is steady long-run performance. We study the average-reward setting, where standard analysis becomes difficult because the value estimate can be shifted by an arbitrary constant without changing the usual equation. Our main idea is to add a steady-state correction, estimated from data collected as the system runs, that fixes this ambiguity and gives the algorithm a unique target. We prove that the resulting methods work for both small problems that can be listed explicitly and larger problems described by features, with efficiency guarantees comparable to the better-understood discounted setting. This makes average-reward reinforcement learning easier to trust and analyze for continual decision-making problems where long-term performance matters.