In reinforcement learning (RL), a long-standing theoretical divide has separated value-based methods (such as Q-learning) from policy-based methods (such as policy gradients and actor-critic frameworks). In practice, policy optimization is highly favored for its stability under dense rewards and its natural extension to continuous action spaces. Mathematically, however, its sample complexity bounds historically lagged far behind.
Value-based methods routinely achieve the information-theoretic minimax optimal sample complexity of $\mathcal{O}(\epsilon^{-2})$ or a regret bound of $\mathcal{O}(\sqrt{T})$. Meanwhile, early theoretical analyses of policy-based methods often yielded loose, practical-defying bounds like $\mathcal{O}(\epsilon^{-4})$, $\mathcal{O}(\epsilon^{-6})$, or even $\mathcal{O}(\epsilon^{-9})$ when accounting for the sample cost of escaping saddle points (Long Yang et al.).
This discrepancy raised a fundamental question: Is policy optimization inherently less sample-efficient, or has our theoretical analysis simply been too conservative? A recent wave of research has decisively proven the latter. By rethinking algorithm design and leveraging hidden optimization structures, researchers have closed the "policy-value efficiency gap," establishing sample efficiency parity across on-policy, off-policy, offline, and multi-agent competitive settings.
Unlocking Optimal Rates via Single-Timescale Updates
To understand why early actor-critic analyses yielded poor sample complexity, one must look at how the interaction between the actor and the critic was modeled. Historically, theorists relied on two-timescale frameworks (where the critic learns at a significantly faster rate than the actor) or nested loops (where the critic must run to convergence before the actor can take a single step). While mathematically convenient for proving convergence, these architectures introduce massive sample overhead.
The shift toward optimal $\mathcal{O}(\epsilon^{-2})$ complexity required analyzing single-timescale or single-loop algorithms, where the actor and the critic update simultaneously using a single sample per step. Zuyue Fu et al. demonstrated that this simultaneous progression allows the algorithm to naturally reuse historical data, accelerating the global convergence rate to $\mathcal{O}(\epsilon^{-2})$.
Historical Two-Timescale Approach (Inefficient):
[Critic Updates to Convergence] -> [Actor Takes One Step] -> Repeat
Result: High sample overhead O(ε⁻⁴)
Modern Single-Timescale Approach (Optimal):
[Critic Update] ↔ [Actor Update] (Simultaneous, Single-Loop)
Result: Data reuse and hidden smoothness unlock O(ε⁻²)
The underlying mathematical reason for this efficiency was uncovered by Tianyi Chen et al., who reframed single-timescale actor-critic as a stochastic bilevel optimization problem. The authors proved that the nested objective possesses a "hidden smoothness" property. By exploiting this smoothness, a simple alternating stochastic gradient method matches the optimal rate of standard SGD for non-nested problems, improving the known sample complexity bound from $\mathcal{O}(\epsilon^{-5/2})$ to $\mathcal{O}(\epsilon^{-2})$. This explains why single-sample, single-timescale updates are so effective even in continuous state-action spaces like the Linear Quadratic Regulator (LQR), where they achieve global optimality without complex multi-loop schedules (Jingliang Duan et al.).
Taming Off-Policy Variance and Data Reuse
Off-policy learning is vital for sample efficiency because it allows an agent to learn from historical transitions or external behavioral data. However, off-policy policy gradients suffer from explosive variance caused by importance sampling weights—the ratio between the target and behavior policies.
To achieve sample parity in off-policy settings, algorithms must control this variance without introducing significant bias. Junyu Zhang et al. solved this by introducing a gradient truncation mechanism (TSIVR-PG). By clipping extreme importance weights, the authors eliminated the traditional "uncheckable assumptions" regarding weight variance, proving that variance-reduced policy gradients can hit the global $\mathcal{O}(\epsilon^{-2})$ optimality threshold. Furthermore, advanced off-policy evaluation operators (such as Retrace or Q-trace) can be modeled as contraction mappings under generalized Bellman operators. This perspective guarantees that learning from external data distributions does not inherently degrade the fundamental $\mathcal{O}(\epsilon^{-2})$ convergence speed relative to on-policy methods (Zaiwei Chen et al.).
The geometry of the policy parameterization itself also dictates how effectively data can be reused. Natural Policy Gradient (NPG) methods paired with softmax or log-linear policies are particularly powerful here. Rui Yuan et al. proved that NPG with log-linear policies achieves linear convergence (exponential error reduction) without requiring entropy regularization, matching the $\mathcal{O}(\epsilon^{-2})$ sample efficiency of value-based methods.
In constrained RL settings, this softmax-based geometry enables far more effective data reuse during off-policy evaluation than greedy update methods, allowing algorithms to maintain a polynomial sample complexity of $\mathcal{O}(\epsilon^{-3})$ when using linear function approximation (Tian Tian et al.).
Parity in Competitive and Offline Environments
The historical sample efficiency gap was perhaps widest in multi-agent competitive settings, such as two-player zero-sum Markov games. Early theoretical bounds suggested that policy gradient methods required orders of magnitude more samples than value-based variants to find a Nash Equilibrium.
Recent work has bridged this gap by combining policy optimization with structured game-theoretic frameworks:
- Fictitious Play: By focusing on games with structured transitions (such as single-controller or factored independent models), Shuang Qiu et al. designed a Fictitious Play policy optimization algorithm that achieves a tight $\mathcal{O}(\sqrt{T})$ regret bound. This proved that the decentralized scalability of policy optimization does not require sacrificing the sample efficiency guarantees of value-based alternatives.
- Bias-Controlled Actor-Critic: For general zero-sum Markov games, Ahmet Alacaoglu et al. introduced a Natural Actor-Critic framework that utilizes sophisticated bias-control techniques to match the optimal $\mathcal{O}(\epsilon^{-2})$ sample complexity, proving that the perceived inefficiency of policy gradients in competitive games was an artifact of sub-optimal analysis.
Finally, this parity extends to purely offline reinforcement learning, where agents must learn from a fixed dataset under partial data coverage. While older offline policy-based methods suffered from an inefficient $\mathcal{O}(\epsilon^{-4})$ rate, Kihyuk Hong et al. developed a primal-dual policy optimization algorithm for linear MDPs. By reparameterizing the problem into a low-dimensional space using Barycentric spanners, the authors achieved the optimal $\mathcal{O}(\epsilon^{-2})$ sample complexity.
Conclusion
The convergence of these diverse lines of research demonstrates that the "policy-value efficiency gap" is not a fundamental limitation of policy-based learning. Whether through exploiting the hidden smoothness of single-timescale updates, bounding off-policy variance via truncation, or leveraging the favorable geometry of natural gradients, policy optimization can achieve the exact same information-theoretic sample efficiency limits as value iteration and Q-learning.
Key Foundational Work
Provably Efficient Fictitious Play Policy Optimization for Zero-Sum Markov Games with Structured Transitions (2021) — contributed 3 concept elements to this direction.
Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithm (2021) — contributed 2 concept elements to this direction.
On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method (2021) — contributed 2 concept elements to this direction.