Research map / Reinforcement learning / Policy gradient and actor-critic
Non-Asymptotic Analysis for Single-Loop (Natural) Actor-Critic with Compatible Function Approximation
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.
Gives tightest non-asymptotic single-loop analyses of actor-critic and natural actor-critic with compatible linear function approximation, removing the critic approximation error and achieving O(eps^-2) (AC) and O(eps^-3) (NAC) sample complexity under a single Markovian trajectory.
Problem
Non-asymptotic convergence of single-loop, single-trajectory actor-critic and natural actor-critic methods suffers from a non-vanishing critic approximation error when the critic uses fixed linear features; the compatible function approximation setting with time-varying policy-dependent features has
Approach
Use compatible (policy-dependent linear) function approximation in the critic via k-step TD with compatible features, so the critic approximation error vanishes; handle the time-varying feature and policy in the eligibility trace by constructing auxiliary Markov chains and fixed-feature auxiliary traces, and bound tracking error and optimality gap recursively in terms of each other.
Key results
- AC with compatible function approximation reaches an epsilon-stationary point with O(epsilon^-2) sample complexity, with no critic approximation error term (only the epsilon term).
- NAC with compatible function approximation attains an epsilon + sqrt(eps_actor) neighborhood of the global optimum with O(epsilon^-3) sample complexity in the single-loop setting, the first such result.
- Under step sizes set to O(T^-2/3 log^-1 T), the NAC optimality gap bound is O(T^-1/3 log^3 T) + O(sqrt(eps_actor)).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use compatible function approximation in place of a fixed critic function class | AC · General MDP, single-loop single-trajectory | convergence error bound: \epsilon+\varepsilon_{\text{critic}} -> \epsilon | Helped |
| Use compatible function approximation in place of a fixed critic function class | NAC · General MDP, single-loop single-trajectory | convergence error bound: \epsilon+\varepsilon_{\text{critic}}+\sqrt{\varepsilon_{\text{actor}}} -> \epsilon+\sqrt{\varepsilon_{\text{actor}}} | Helped |
| Analyze NAC in the single-loop setting with a single Markovian trajectory instead of a nested-loop setting | NAC with compatible function approximation · General MDP | sample complexity: \mathcal{O}(\epsilon^{-6}) -> \mathcal{O}(\epsilon^{-3}) | Helped |
Limitations
- AC analysis requires additional smoothness assumptions (bounded Hessian and third derivatives of the policy) that NAC does not need.
- Requires uniform ergodicity and a concentrability-type assumption on the state-action distribution ratio (C_infinity) for NAC.
- Still leaves a sqrt(eps_actor) approximation error from policy class expressiveness for NAC.
Experimental setup
Metrics: gradient norm optimality gap sample complexity
Baselines: nested-loop actor-critic analyses (Kumar et al. style) single-loop NAC tabular analysis (Wu et al., 2020) nested-loop NAC analysis (Chen et al., 2022)
Builds on: natural actor-critic k-step TD compatible function approximation
Closest papers by meaning
- Two-Timescale Critic-Actor for Average Reward MDPs with Function Approximation (AAAI 2025 · similarity 0.92)
- On the Convergence of Single-Timescale Actor-Critic (NeurIPS 2025 · similarity 0.92)
- Actor-Critics Can Achieve Optimal Sample Efficiency (ICML 2025 · similarity 0.91)
- Closing the Gap: Achieving Global Convergence (Last Iterate) of Actor-Critic under Markovian Sampling with Neural Network Parametrization (ICML 2024 · similarity 0.91)
- A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach (ICML 2025 · similarity 0.89)
- ReLU to the Rescue: Improve Your On-Policy Actor-Critic with Positive Advantages (ICML 2024 · similarity 0.89)
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.