Abstract
In reinforcement learning (RL), off-policy actor-critic algorithms are widely used but often diverge from theoretical prescriptions. Specifically, while the Policy Gradient Theorem necessitates the use of density ratios to correct for state distribution mismatch between behavior and target policies, practitioners frequently omit these corrections to maintain stability. This paper provides a theoretical foundation for this common practice. We establish the global optimality and finite-sample convergence rates for a softmax off-policy actor-critic algorithm in a tabular setting that lacks density ratio correction. By employing a three-timescale update scheme and decaying Kullback–Leibler (KL) regularization, we demonstrate that the algorithm converges to the optimal policy, overcoming the challenges of stochastic, approximate updates and time-inhomogeneous Markov chains.
Introduction
Off-policy reinforcement learning allows an agent to learn a target policy while following a different behavior policy. This is essential for sample efficiency and safety. However, a significant discrepancy exists between RL theory and large-scale applications. Theoretical frameworks typically rely on the "density ratio"—the ratio between the state distribution of the target policy and that of the behavior policy—to ensure unbiased gradient estimates. In practice, estimating these ratios is computationally expensive and introduces high variance, leading many successful implementations (e.g., AlphaStar or OpenAI Five) to ignore them entirely.
This research addresses a fundamental question: Can an off-policy actor-critic algorithm reach global optimality without density ratio correction? We prove that it can, providing a finite-sample analysis that aligns theoretical guarantees with empirical success.
The Softmax Off-Policy Actor-Critic Algorithm
The analyzed algorithm departs from standard off-policy methods in several key ways to better reflect practical implementations:
1. Omission of Density Ratios
The update step intentionally omits the state distribution correction. This "naive" approach is more stable and aligns the theory with common practice in deep RL where density ratios are often ignored to prevent training instability.
2. Three-Timescale Update Scheme
To manage the interaction between value estimation and policy improvement, the algorithm operates on three distinct speeds:
- Critic Update (Fastest): The critic updates value estimates to track the current policy's performance.
- Actor Update (Middle): The actor updates policy parameters based on the signal provided by the critic.
- Regularization Decay (Slowest): The regularization weight ($\lambda_k$) gradually decreases, shifting the agent from exploration to exploitation over time.
3. Decaying KL Regularization
The algorithm incorporates a Kullback–Leibler (KL) divergence penalty between a uniform policy and the current policy. This regularization acts as a "safety net," preventing the policy from becoming deterministic too quickly. This ensures the agent continues to visit enough states to eventually discover the optimal path, even if the behavior policy's distribution is biased.
Theoretical Framework and Finite Sample Analysis
The core contribution of this work is a new framework for analyzing stochastic approximation algorithms. Unlike previous works that assume exact policy gradients or fixed Markov chains, this analysis accounts for the complexity of real-world updates:
- Stochasticity: Updates are performed only for the current state-action pair at each step.
- Approximation: The actor uses a learned critic rather than the true value function.
- Time-Inhomogeneity: Both the update operators and the underlying Markov chains change over time as the policy evolves.
By utilizing a generalized Moreau envelope to construct a Lyapunov function, the authors establish that the suboptimality of the learned policy vanishes at a rate of $\mathcal{O}(\lambda_k)$. Under specific hyperparameter settings, the probability of the policy being near-optimal approaches 1 at a rate of approximately $1 - \mathcal{O}(t^{-1/4})$. Notably, this analysis removes restrictive assumptions common in previous literature, such as the requirement for a unique optimal policy or the need for the initial state distribution to cover the entire state space.
Empirical Validation: The Chain Domain
The theoretical findings were validated using the "Chain Domain," a synthetic Markov Decision Process (MDP) designed to be deceptive. In this environment, immediate rewards lure agents toward suboptimal policies, making it a rigorous test for global optimality. The experiments confirmed that the proposed algorithm, using KL-based regularization, successfully found the optimal policy across various decay rates, proving more robust than standard entropy-regularized approaches in the off-policy context.
Conclusion and Future Directions
This work bridges a critical gap in RL literature by proving that density ratio correction is not a prerequisite for global optimality in tabular off-policy actor-critic methods. These results offer a robust theoretical backing for modern RL practices. Future research will focus on extending these guarantees to linear function approximation and deep neural networks, as well as further optimizing the convergence rates for complex environments.
Reference: Zhang, S., Tachet des Combes, R., & Laroche, R. (2022). Global Optimality and Finite Sample Analysis of Softmax Off-Policy Actor Critic under State Distribution Mismatch. Journal of Machine Learning Research, 23(1), 1-91.
Summary updated