Achieving $\epsilon^{-2}$ Sample Complexity for Single-Loop Actor-Critic under Minimal Assumptions

Technical Summary: Achieving $\tilde{O}(\epsilon^{-2})$ Sample Complexity for Single-Loop Actor-Critic under Minimal Assumptions

Problem Statement
Reinforcement learning (RL) aims to solve Markov Decision Processes (MDPs) through data-driven methods. While value-space methods like Q-learning have established $\tilde{O}(\epsilon^{-2})$ sample complexity under minimal assumptions (specifically, the existence of an irreducible behavior policy), policy-space methods like actor-critic have historically lagged in theoretical guarantees. Existing actor-critic analyses achieving $\tilde{O}(\epsilon^{-2})$ complexity typically rely on two restrictive conditions:

1. Nested-loop implementations: Where the critic updates multiple times while the actor remains fixed, a structure distinct from practical single-loop algorithms.
2. Strong, algorithm-dependent assumptions: Such as requiring all policies encountered during the algorithm's trajectory (or the entire policy class) to induce irreducible and aperiodic Markov chains with uniformly bounded mixing rates and exploration properties.

These assumptions create a circular dependency: verifying the mixing properties requires controlling the policy sequence generated by the algorithm, which is precisely the object of the convergence analysis. Furthermore, practical actor-critic algorithms operate in a single-loop, single-timescale manner with off-policy learning, where the critic tracks a time-varying target policy. This introduces challenges regarding coupled update equations and potentially unbounded iterates due to importance sampling, which existing theoretical frameworks struggle to address without strong assumptions.

Methodology
The authors propose a single-loop, single-timescale off-policy actor-critic algorithm where the actor and critic are updated simultaneously at each iteration. The actor employs incremental updates toward a target policy $\tilde{\pi}_t$ derived via approximate policy iteration (API) or natural policy gradient (NPG), while the critic performs off-policy temporal-difference (TD) learning. The authors consider two critic variants:

• Importance Sampling (IS): Corrects distribution mismatch using an importance weight ratio.
• Expected Temporal Difference (ETD): Directly computes the expected Q-function at the next state, avoiding explicit importance weights.

The core technical innovation lies in the analysis framework. To handle the coupling between the actor and critic updates and the unbounded nature of off-policy iterates, the authors employ a coupled Lyapunov drift framework.

1. Lyapunov Functions: They construct separate Lyapunov functions for the actor ($V_t = \|Q^* - Q_{\pi_t}\|_\infty^2$) and the critic ($W_t = \|Q_t - Q_{\pi_t}\|_\nu^2$).
2. Drift Inequalities: They establish negative drift inequalities for both functions. Crucially, these inequalities contain cross-terms representing the error from the coupled system (e.g., the critic error appearing in the actor's drift and vice versa).
3. Cross-Domination: The analysis relies on a "cross-domination" property. By carefully selecting stepsize ratios and ensuring the coupling error terms are dominated by the negative drift terms of the respective systems, the authors combine the two drift inequalities into a single recursion for $V_t + W_t$. This approach is inspired by small-gain theory in dynamical systems but is adapted here to handle Markovian noise, time-varying targets, and unbounded iterates in a unified manner.

Key Contributions and Results
The paper establishes the first last-iterate convergence rates for a single-loop actor-critic algorithm that achieves $\tilde{O}(\epsilon^{-2})$ sample complexity under minimal assumptions.

• Minimal Assumptions: The only assumption required is the existence of a policy that induces an irreducible Markov chain over the state space. This policy need not be visited by the algorithm, nor does the algorithm need to control the mixing properties of the policies it generates. This stands in contrast to prior works requiring uniform ergodicity across the trajectory or the entire policy class.
• Sample Complexity: Under this minimal assumption, the algorithm achieves an $\tilde{O}(\epsilon^{-2})$ sample complexity to find an $\epsilon$-optimal policy. This rate is near-minimax optimal with respect to $\epsilon$.
• Stepsize Schemes: The results hold for constant, harmonic, and polynomial stepsize sequences. Specifically, using harmonic stepsizes with appropriate parameters yields the optimal rate.
• Algorithm Variants: The analysis covers both IS-based and ETD-based critics. While both achieve the same complexity order, the ETD variant exhibits milder dependence on problem parameters (state space size $n$, action space size $m$, and discount factor $\gamma$) because it avoids the additional stochasticity introduced by importance sampling ratios.
• Unbounded Iterates: The framework successfully handles the potentially unbounded iterates induced by off-policy learning (particularly with IS), a challenge that often necessitates strong boundedness assumptions in previous literature.

Significance and Claims
The authors claim that this work bridges a significant theoretical gap between value-space and policy-space methods. By demonstrating that actor-critic methods can achieve minimax-optimal sample complexity without nested loops or strong, algorithm-dependent mixing assumptions, the paper challenges the notion that policy-space methods are inherently less sample-efficient or require stronger conditions.

The analytical framework based on coupled Lyapunov drift and cross-domination is presented as a contribution of independent interest, potentially applicable to other coupled iterative algorithms with unbounded iterates. The paper explicitly notes that while the dependence on $\epsilon$ is near-optimal, the dependence on problem-specific constants ($n, m, (1-\gamma)^{-1}$) may be suboptimal compared to value-based methods, suggesting that variance reduction techniques could be a direction for future improvement. The work avoids making claims about function approximation settings (the "deadly triad") or specific empirical applications, focusing strictly on the tabular setting and theoretical guarantees.