TL;DR
This paper provides the first theoretical proof that off-policy actor-critic algorithms can achieve global optimality without using complex and unstable density ratios to correct for state distribution mismatches. By analyzing a three-timescale stochastic approximation framework, the authors bridge a long-standing gap between reinforcement learning theory and empirical practice, showing why the simpler algorithms favored by practitioners actually work.
What Problem Does This Paper Address?
In off-policy reinforcement learning (RL), an agent learns about a target policy (the ideal strategy) while collecting data using a different behavior policy (often a more exploratory strategy). This setup introduces two types of discrepancies: action selection mismatch and state distribution mismatch.
While correcting the action mismatch is straightforward using importance sampling, correcting the state distribution mismatch requires estimating a "density ratio"—the ratio of the state occupancy under the target policy versus the behavior policy. In theory, omitting this density ratio means the algorithm is no longer following a true gradient, invalidating standard convergence proofs. In practice, however, calculating density ratios is notoriously unstable, so deep RL practitioners usually just ignore them and still achieve excellent results.
Prior theoretical works either assumed exact gradients (ignoring the stochastic nature of real updates) or forced the use of density ratios. This paper tackles the challenge of proving whether an approximate, stochastic off-policy actor-critic algorithm can converge to a globally optimal policy without density ratio corrections.
Methods
The authors analyze an off-policy actor-critic algorithm in a tabular setting with a standard softmax policy parameterization. Their approach relies on a three-timescale stochastic approximation framework:
- Fastest Timescale (Critic): The critic estimates the action-value function using off-policy expected SARSA.
- Middle Timescale (Actor): The actor updates policy parameters without state distribution density ratios, aligning with practical implementations. Crucially, they introduce a Kullback-Leibler (KL) divergence regularization between a uniform random policy and the current policy to maintain exploration.
- Slowest Timescale (Regularization Weight): The weight of the KL regularization decays slowly over time, allowing the policy to eventually become deterministic and optimal.
Mathematically, the core innovation is a new finite-sample analysis for generic stochastic approximation algorithms that feature time-inhomogeneous update operators acting on time-inhomogeneous Markov chains. They leverage uniform contraction properties and generalized Moreau envelopes to construct a Lyapunov function that guarantees convergence.
Additionally, the authors extend this mathematical machinery to analyze the popular Soft Actor-Critic (SAC) framework under state distribution mismatch.
Datasets
The algorithms were evaluated empirically using the chain domain benchmark introduced by Laroche and Tachet (2021). This synthetic environment consists of $N$ non-terminal states designed specifically to challenge RL agents by offering immediate, deceptive rewards that pull the agent toward suboptimal policies. It serves as a diagnostic tool to verify if the algorithm can successfully bypass local minima to find the globally optimal policy.
Key Insights and Ideas
- Practitioners Were Right: The paper mathematically justifies the common practice of ignoring density ratio corrections for state distribution mismatches in tabular settings.
- Relaxing Restrictive Assumptions: Unlike previous seminal works (e.g., Agarwal et al., 2020), this analysis does not require the initial state distribution to cover the entire state space ($p_0(s) > 0$). The decaying KL regularization ensures the agent explores sufficiently regardless of the starting state.
- No Uniqueness Required: The proof does not assume that the MDP has a unique optimal policy, making the convergence guarantees much more broadly applicable.
- Uniform Contraction Over Negative-Definiteness: Instead of relying on the strict negative-definiteness of the limiting update matrix (which rarely holds in off-policy settings), the authors use the uniform contraction of the update operators to prove that the critic can accurately track the true value function.
Key Results
- Global Optimality Bound: The authors establish a non-asymptotic convergence rate for the actor (Theorem 5). For a chosen iteration $k$, the expected performance satisfies $J(\pi_{\theta_k}; p_0) \geq J(\pi_*; p_0) - O(k^{-\epsilon_\lambda})$ with high probability, confirming global optimality.
- SAC Convergence: Theorem 7 provides the first convergence rate to stationary points for Soft Actor-Critic with a decaying entropy regularization weight under state distribution mismatch.
- Empirical Validation: In experiments on the chain domain (for lengths $N=6$ to $N=9$), both the KL-regularized algorithm and the Expected SAC variant successfully converged close to the optimal policy, matching the theoretical predictions.
Limitations and Future Work
- Tabular Setting: The global optimality guarantees are restricted to the tabular setting. Extending this analysis to function approximation (like neural networks) remains an open challenge, though the authors note that compatible features could be a starting point for linear function approximation.
- Convergence Rate Optimization: The achieved convergence rates trade off suboptimality and probability bounds. The authors note that the rates are sufficient but likely conservative, leaving room for future optimization.
Summary updated