Research map / Reinforcement learning / Policy gradient and actor-critic
Actor-Critics Can Achieve Optimal Sample Efficiency
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes NORA, an optimistic off-policy actor-critic with rare-switching critic updates targeting Q* and policy resets, achieving 1/eps^2 sample complexity and sqrt(T) regret under general function approximation, plus non-optimistic hybrid RL variants (NOAH) and small experiments.
Problem
Whether actor-critic or policy optimization methods can achieve 1/eps^2 sample complexity or sqrt(T) regret with general function approximation when strategic exploration is necessary, and whether hybrid offline-online data can enable optimism-free efficient actor-critics.
Approach
Combine optimism, off-policy critic learning on all data, a critic targeting Q* (instead of the current policy) so optimism holds and critic updates can be rare, plus policy resets at each critic update and a larger learning rate; the non-optimistic hybrid variant uses offline data coverage to replace optimism.
Key results
- NORA achieves sample complexity O(dH^5 log|A|/eps^2 + dH^4 log|F|/eps^2) and sqrt(T) regret under general function approximation when Bellman eluder dimension grows at most log T.
- On linear MDP Tetris over 30 trials, Algorithm 1 outperforms rare-switching LSVI-UCB in per-episode reward and cumulative regret, while Algorithm 2 achieves sqrt(T) regret.
- On antmaze-medium-diverse-v2, Algorithm 2H (approximate optimism via action sampling) outperforms Cal-QL and Algorithm 1H without pessimism.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use optimistic rare-switching critic updates that target Q* | NORA · General function approximation, online RL | sample complexity: 1/\epsilon^2 | Helped |
| Add offline data to optimistic rare-switching actor-critic | NORA · Hybrid RL | sample efficiency | Helped |
| Omit optimism and use sufficient offline coverage | NOAH-* · Hybrid RL | computational efficiency: N_{\operatorname{off}} \geq c_{\operatorname{off}}^*(\gF,\Pi)dH^4/\epsilon^2 | Helped |
| Use DOUHUA when the critic class is closed under truncated sums | DOUHUA · General function approximation, truncated-sum-closed class | regret | Helped |
| Remove policy resets and use action sampling for approximate optimism (ablation) | Algorithm 2H · antmaze-medium-diverse-v2 | performance | Mixed |
| Use NORA instead of rare-switching LSVI-UCB | Linear MDP Tetris · Linear MDP Tetris | per-episode reward | Helped |
| Use NORA instead of rare-switching LSVI-UCB | Linear MDP Tetris · Linear MDP Tetris | cumulative regret | Mixed |
| Use Algorithm 2H instead of Algorithm 1H | Deep hybrid actor-critic · antmaze-medium-diverse-v2 | performance | Helped |
| Use Algorithm 2H instead of Cal-QL | Deep hybrid actor-critic · antmaze-medium-diverse-v2 | performance | Helped |
| Use Algorithm 1H instead of Cal-QL | Deep hybrid actor-critic · antmaze-medium-diverse-v2 | performance | Hurt |
Surprising findings
- Algorithm 1 outperforms LSVI-UCB on Tetris despite the theory being about general function classes.
- Hybrid actor-critic without pessimism matches or exceeds Cal-QL on antmaze.
Limitations
- NORA is generally computationally inefficient and relies on optimistic planning over the function class.
- Regret still depends on the Bellman eluder dimension, which can scale with T in rare cases.
- Empirical experiments are small-scale and the deep variants are heuristic with no formal guarantee.
Experimental setup
Datasets: antmaze-medium-diverse-v2 Tetris linear MDP
Benchmarks: Tetris linear MDP antmaze-medium-diverse-v2
Metrics: cumulative regret per-episode reward normalized return
Baselines: LSVI-UCB Cal-QL
Builds on: GOLF Bellman eluder dimension sequential extrapolation coefficient LSVI-UCB Cal-QL DDPG
Closest papers by meaning
- Improving Sample Complexity Bounds for (Natural) Actor-Critic Algorithms (NeurIPS 2020 · similarity 0.94)
- Non-Asymptotic Analysis for Single-Loop (Natural) Actor-Critic with Compatible Function Approximation (ICML 2024 · similarity 0.91)
- ReLU to the Rescue: Improve Your On-Policy Actor-Critic with Positive Advantages (ICML 2024 · similarity 0.89)
- Finite-Time Convergence and Sample Complexity of Actor-Critic Multi-Objective Reinforcement Learning (ICML 2024 · similarity 0.89)
- Diffusion Actor-Critic: Formulating Constrained Policy Iteration as Diffusion Noise Regression for Offline Reinforcement Learning (ICLR 2025 · similarity 0.88)
- Closing the Gap: Achieving Global Convergence (Last Iterate) of Actor-Critic under Markovian Sampling with Neural Network Parametrization (ICML 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.