Research map / Learning theory and algorithms / Sample complexity
Two-Timescale Critic-Actor for Average Reward MDPs with 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.
Proposes the first two-timescale critic-actor algorithm with linear function approximation for long-run average reward MDPs, giving finite-time sample complexity Õ(ε^-(2+δ)) and almost-sure asymptotic convergence via differential inclusions.
Problem
Critic-actor (reversed-timescale actor-critic) methods lack function approximation, average-reward finite-time analysis, and asymptotic stability guarantees; existing two-timescale AC has sample complexity Õ(ε^-2.5) and single-timescale AC lacks asymptotic guarantees.
Approach
Reverse the usual AC timescales so the critic (TD(0) with linear function approximation) runs on the slowest timescale while the average-reward estimate and policy-gradient actor run faster; analyze with finite-time bounds and a differential-inclusion argument for almost-sure convergence under Markov noise.
Key results
- Critic-actor achieves sample complexity Õ(ε^-(2+δ)) for critic MSE, better than the Õ(ε^-2.5) of two-timescale AC; e.g., ν=0.5, σ=0.51 gives Õ(ε^-2.08).
- On Mountain Car Continuous, critic-actor reports -0.0084 ± 0.0001 average reward vs -0.009 for AC; on Frozen Lake, 0.00633 vs 0.0036 for AC.
- Critic-actor takes about half the training time of AC on two of three environments.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace Actor-Critic with Critic-Actor | Actor-Critic · Frozen Lake | average reward: 0.0036 ± 0.0027 -> 0.00633 ± 0.0034 | Helped |
| Replace DQN with Critic-Actor | DQN · Frozen Lake | average reward: 0.0028 ± 0.0023 -> 0.00633 ± 0.0034 | Helped |
| Replace PPO AC with Critic-Actor | PPO AC · Frozen Lake | average reward: 0.00207 ± 0.0009 -> 0.00633 ± 0.0034 | Helped |
| Replace PPO CA with Critic-Actor | PPO CA · Frozen Lake | average reward: 0.00194 ± 0.0005 -> 0.00633 ± 0.0034 | Helped |
| Replace Single Timescale AC with Critic-Actor | Single Timescale AC · Frozen Lake | average reward: 0.0035 ± 0.0028 -> 0.00633 ± 0.0034 | Helped |
| Replace Actor-Critic with Critic-Actor | Actor-Critic · Pendulum | average reward: -6.45 ± 0.324 -> -6.30 ± 0.41 | Helped |
| Replace DQN with Critic-Actor | DQN · Pendulum | average reward: -6.45 ± 0.316 -> -6.30 ± 0.41 | Helped |
| Replace PPO AC with Critic-Actor | PPO AC · Pendulum | average reward: -6.39 ± 0.38 -> -6.30 ± 0.41 | Helped |
| Replace PPO CA with Critic-Actor | PPO CA · Pendulum | average reward: -6.44 ± 0.51 -> -6.30 ± 0.41 | Helped |
| Replace Single Timescale AC with Critic-Actor | Single Timescale AC · Pendulum | average reward: -6.53 ± 0.42 -> -6.30 ± 0.41 | Helped |
| Replace Actor-Critic with Critic-Actor | Actor-Critic · Mountain Car Continuous | average reward: -0.009 ± 0.0002 -> -0.0084 ± 0.0001 | Helped |
| Replace DQN with Critic-Actor | DQN · Mountain Car Continuous | average reward: -0.036 ± 0.014 -> -0.0084 ± 0.0001 | Helped |
Surprising findings
- Reported Frozen Lake advantage is small and within overlapping standard errors, so the claim of best performance is weak.
- On Pendulum, critic-actor (-6.30) is only marginally better than AC (-6.45) with overlapping error bars.
Limitations
- Finite-time analysis uses a projected critic; bounds without projection are left open.
- Experiments are on small classic-control environments with only 10,000 training steps and modest margins over baselines.
- Assumes isolated local maxima of the actor objective for the strongest convergence result.
Experimental setup
Datasets: Frozen Lake Pendulum Mountain Car Continuous
Benchmarks: Frozen Lake Pendulum Mountain Car Continuous
Metrics: average reward training time sample complexity
Baselines: Actor-Critic (two-timescale AC) DQN PPO-AC PPO-CA Single Timescale AC
Builds on: actor-critic critic-actor algorithm (discounted, look-up table) policy gradient theorem two-timescale stochastic approximation
Closest papers by meaning
- Non-Asymptotic Analysis for Single-Loop (Natural) Actor-Critic with Compatible Function Approximation (ICML 2024 · similarity 0.92)
- On the Convergence of Single-Timescale Actor-Critic (NeurIPS 2025 · similarity 0.91)
- A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach (ICML 2025 · similarity 0.90)
- Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithm (NeurIPS 2025 · similarity 0.89)
- Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approach (NeurIPS 2025 · similarity 0.89)
- Towards Global Optimality for Practical Average Reward Reinforcement Learning without Mixing Time Oracles (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.