Abstract
In this paper, we provide finite-sample convergence guarantees for an off-policy variant of the natural actor-critic (NAC) algorithm based on Importance Sampling. In particular, we show that the algorithm converges to a global optimal policy with a sample complexity of $\mathcal{O}(\epsilon^{-3}\log^2(1/\epsilon))$ under an appropriate choice of stepsizes. In order to overcome the issue of large variance due to Importance Sampling, we propose the $Q$-trace algorithm for the critic, which is inspired by the V-trace algorithm. This enables us to explicitly control the bias and variance, and characterize the trade-off between them. As an advantage of off-policy sampling, a major feature of our result is that we do not need any additional assumptions, beyond the ergodicity of the Markov chain induced by the behavior policy.
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 fixed "behavior" policy). Off-policy learning is essential for high-stakes fields like healthcare or robotics, where you cannot simply let an untrained agent "explore" and potentially cause harm.
However, off-policy learning is mathematically difficult. To correct for the difference between the behavior policy and the target policy, researchers use Importance Sampling (IS). These IS ratios can explode, leading to massive variance that makes the algorithm unstable. While empirical successes are plenty, the theoretical "finite-sample" behavior—exactly how many samples you need to guarantee a good policy—has remained an open question for off-policy Natural Actor-Critic algorithms.
Methods: The Q-Trace Algorithm
The authors propose an off-policy variant of the Natural Actor-Critic (NAC). NAC is a specific type of actor-critic algorithm that uses "natural" gradients (preconditioned with Fisher information) to achieve faster and more stable policy updates. The core innovation is the Q-trace algorithm for the critic:
- Inspired by V-trace: It adapts the popular V-trace algorithm to estimate Q-functions rather than V-functions.
- Dual Truncation: It introduces two distinct truncation levels ($\bar{ ho}$ and $\bar{c}$) for the importance sampling ratios. This allows the user to explicitly trade off between truncation bias (introduced by capping the ratios) and variance (caused by uncapped ratios).
- Single Trajectory: Unlike many theoretical models that require the agent to "restart" from random states, this analysis works on a single, continuous trajectory of data, which is much closer to how real-world data is collected.
Key Results and Complexity
The paper proves that the algorithm converges to the global optimal policy, not just a local stationary point. To reach an $\epsilon$-optimal policy, the algorithm requires $\mathcal{O}(\epsilon^{-3} \log^2(1/\epsilon))$ samples.
Surprisingly, the off-policy bound $\mathcal{O}(\epsilon^{-3})$ is better than the best-known on-policy NAC bounds (often $\mathcal{O}(\epsilon^{-4})$ or worse). The authors attribute this to the fact that off-policy sampling from a fixed, ergodic behavior policy ensures "natural exploration," preventing the agent from getting stuck in local optima—a common pitfall for on-policy methods. The only major assumption required is that the behavior policy is "ergodic" (it eventually visits all state-action pairs).
Empirical Validation
As a theoretical paper, the authors validate their theory using a synthetic 5-state, 3-action Markov Decision Process (MDP). The behavior policy is uniform (random), while the reward structure incentivizes a specific optimal action.
These experiments demonstrate that the algorithm converges almost monotonically and confirm the impact of different truncation levels on performance, supporting the theoretical findings regarding global convergence.
Limitations and Future Work
- Tabular Setting: The current proof is limited to the "tabular" setting, where states and actions are finite. Extending this analysis to function approximation (like Neural Networks) is a major next step, as off-policy TD learning in that regime is notoriously unstable.
- Last-Iterate Convergence: The current guarantee applies to a policy chosen randomly from the agent's history. Proving that the very last policy produced is optimal remains a future challenge.
- State-Action Space Dependence: While the $\epsilon$ dependence is strong, the complexity still scales with the size of the state and action spaces ($|S|^3 |A|^5$), which could be prohibitive for very large environments.
Summary updated