Abstract
In this paper, we describe proximal gradient temporal difference learning, which provides a principled way for designing and analyzing true stochastic gradient temporal difference learning algorithms. We show how gradient TD (GTD) reinforcement learning methods can be formally derived, not with respect to their original objective functions as previously attempted, but rather with respect to primal-dual saddle-point objective functions. We also conduct a saddle-point error analysis to obtain finite-sample bounds on their performance. Previous analyses of this class of algorithms use stochastic approximation techniques to prove asymptotic convergence, and no finite-sample analysis had been attempted. An accelerated algorithm is also proposed, namely GTD2-MP, which use proximal "mirror maps" to yield acceleration. The results of our theoretical analysis imply that the GTD family of algorithms are comparable and may indeed be preferred over existing least squares TD methods for off-policy learning, due to their linear complexity. We provide experimental results showing the improved performance of our accelerated gradient TD methods.
Introduction: The Challenge of Off-Policy Learning
In Reinforcement Learning (RL), "off-policy" learning occurs when an agent learns about a target policy while following a different behavior policy—for instance, learning from historical data or a human expert. While essential for data efficiency, standard Temporal Difference (TD) methods are notoriously unstable in this setting.
To address this, researchers previously developed Gradient TD (GTD) algorithms. However, these were not "true" stochastic gradient methods. Their objective functions, such as the Mean Square Projected Bellman Error (MSPBE), involved a product of two expectations. In standard statistics, one cannot simply multiply two independent samples to obtain an unbiased estimate of a product of expectations. Previous GTD methods relied on an "ad-hoc" splitting of terms to circumvent this. This work addresses the lack of a principled theoretical foundation and the absence of finite-sample performance guarantees for these vital algorithms.
A Primal-Dual Perspective
The core contribution of this research is the transformation of standard RL objective functions (NEU and MSPBE) into a convex-concave saddle-point formulation: $$\min_{\theta} \max_{y} L(\theta, y)$$ Here, $\theta$ represents the value function parameters (the primal variable) and $y$ is an auxiliary "dual" variable.
By adopting this perspective, the authors prove that existing GTD and GTD2 algorithms are actually true stochastic gradient descent-ascent steps on this saddle-point objective. The "auxiliary variable" used in previous heuristic derivations is revealed to be the dual variable in this minimax optimization. This insight allows for the first finite-sample analysis of GTD algorithms, establishing a convergence rate of $O(1/\sqrt{n})$.
Accelerated Learning with Mirror Prox
Leveraging the saddle-point formulation, the authors introduce GTD2-MP (Mirror Prox). This algorithm applies the "Stochastic Mirror Prox" method, an "extra-gradient" technique that takes a "proximal" step to a mid-point before making the final update. This stabilizes the learning process and accelerates convergence toward the "optimal" stochastic saddle-point rate of $O(1/n + 1/\sqrt{n})$.
Experimental Evaluation
Baird’s Star Example
Baird’s Star is a classic 7-state synthetic MDP designed to make standard TD methods diverge. It serves as the "litmus test" for off-policy stability. In this benchmark, GTD2-MP demonstrated a significant reduction in both MSPBE and variance compared to the standard GTD2 algorithm.
Energy Management Domain
The algorithms were also evaluated in a more complex, practical simulation: the Energy Management Domain. Here, a decision-maker must buy or sell energy based on stochastic prices while managing battery degradation. This represents a real-world inventory management challenge with non-stationary dynamics.
As shown in the figures, GTD2-MP converged much faster during the initial "transient" states of the learning process, proving its utility in data-limited environments.
Discussion and Future Work
The transition to a primal-dual framework provides several key advantages:
- Linear Complexity: The new algorithms maintain linear computational complexity $O(d)$ relative to the number of features, making them more scalable than Least Squares TD (LSTD) methods, which scale quadratically $O(d^2)$.
- Theoretical Rigor: The use of "Mirror Prox" techniques allows the algorithms to be "almost dimension-free" in their convergence properties.
However, some limitations remain. The current analysis focuses on policy evaluation (predicting rewards for a fixed policy) rather than control (finding the optimal policy). Furthermore, the analysis assumes linear function approximation ($V \approx \Phi \theta$). Future work will explore how these saddle-point formulations behave when paired with non-linear approximators like deep neural networks and how they can be extended to full control problems.
Summary updated