Introduction
Reinforcement Learning (RL) agents typically learn in one of two ways: on-policy (learning from their own current actions) or off-policy (learning from historical data or a different "behavior" policy). While on-policy methods are easier to analyze, off-policy learning is essential for real-world applications like healthcare or robotics, where we cannot afford to let an untrained agent experiment freely.
However, off-policy learning faces two major hurdles. First, using Importance Sampling (IS) to correct for the difference between the behavior policy and the target policy often leads to massive spikes in variance, making learning unstable. Second, most existing Actor-Critic theory focuses on local convergence or requires "restarting" the environment frequently. There has been a lack of rigorous proof that off-policy Natural Actor-Critic (NAC) can converge to a global optimum using a single trajectory of data.
This paper provides the first finite-sample convergence analysis for an off-policy NAC algorithm, proving it reaches a global optimum. By introducing a novel critic algorithm called Q-trace, the authors achieve a state-of-the-art sample complexity, outperforming existing on-policy NAC bounds while requiring fewer restrictive assumptions about environment exploration.
The Q-Trace Algorithm
The authors propose an off-policy variant of the Natural Actor-Critic. NAC is powerful because it uses "preconditioning"—inspired by the Fisher Information Matrix—to take more effective steps toward the optimal policy compared to standard gradient ascent.
The core innovation enabling this analysis is the Q-trace algorithm for the critic:
- Inspired by V-trace: It adapts the V-trace approach (originally for state-value functions) to estimate the action-value function ($Q$).
- Dual Truncation: Q-trace uses two different truncation levels ($\bar{\rho}$ and $\bar{c}$) for Importance Sampling ratios. This dual approach is the key to stability: $\bar{\rho}$ allows the authors to control the bias of the final solution, while $\bar{c}$ allows them to aggressively squash variance without shifting the algorithm's fixed point.
- Single Trajectory Analysis: Unlike many theoretical frameworks that assume the agent can teleport to any state to start a new trial, this analysis works on a single, continuous stream of data from a behavior policy.
Key Insights and Results
By carefully balancing bias and variance through Q-trace, the authors demonstrate that off-policy NAC actually achieves a better theoretical sample complexity of $\tilde{O}(\epsilon^{-3})$ than the best-known on-policy NAC results ($\epsilon^{-4}$). To reach an $\epsilon$-optimal policy, the algorithm requires $\tilde{O}(\epsilon^{-3} \log^2(1/\epsilon))$ samples.
Furthermore, exploration comes "for free." In on-policy learning, researchers often have to add exploration noise or make strong assumptions that the current policy visits every state. In this off-policy setting, as long as the behavior policy is ergodic (visits everything eventually), exploration is guaranteed, simplifying the requirements for global convergence.
To validate the theory, the authors conducted numerical experiments on a synthetic 5-state, 3-action Markov Decision Process (MDP). They demonstrated that the algorithm converges almost monotonically toward the optimal value in practice, perfectly matching their theoretical predictions.
Limitations and Future Work
While a significant theoretical step forward, the paper notes a few limitations:
- Tabular Restriction: The current proof is situated in the "tabular" setting, assuming a finite number of states and actions that can be stored in a table.
- Function Approximation: Real-world RL often uses neural networks. Extending these finite-sample guarantees to function approximation is a major open challenge, especially given that off-policy TD learning can be notoriously unstable in this regime (the "Deadly Triad").
- Last-Iterate Convergence: The current bounds apply to a policy sampled randomly from the learning history. Proving that the very last policy reached by the agent is always the optimal one remains a goal for future research.
Summary updated