Research map / Reinforcement learning / Policy gradient and actor-critic
Policy Evaluation for Variance in Average Reward Reinforcement Learning
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.
Designs a two-trajectory TD-style linear stochastic approximation algorithm to estimate the asymptotic variance of rewards under a fixed policy in average-reward MDPs, with finite-sample O~(1/k) MSE bounds in tabular and linear function approximation settings.
Problem
Policy evaluation for the asymptotic variance (a variance risk measure) of rewards in average-reward reinforcement learning, where transition dynamics are unknown and finite-sample guarantees are lacking.
Approach
Expresses the asymptotic variance via the solution of the Poisson equation and estimates it with a TD-like linear stochastic approximation that uses two independent trajectories to remove correlation terms, with projection to handle non-unique Poisson solutions.
Key results
- Tabular policy evaluation for asymptotic variance achieves O~(1/k) finite-time mean-squared error rate under diminishing step sizes (Theorem 4.3(b)).
- Linear function approximation version achieves O~(1/k) rate toward a limit point kappa* with an approximation error bounded by 16 r_max^2 E^2 / (1-lambda^2) (Proposition 5.3, Theorem 5.2).
- Corollary 4.5 gives sample complexity O~(log^2(1/eps)/eps^2) times L||Q*||^2/Delta_1^4 for mean estimation error eps.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed TD-like linear SA algorithm for tabular policy evaluation | Average-reward policy evaluation · Tabular setting | mean-squared error: ˜O(1/k) | Helped |
| Use the proposed TD-like linear SA algorithm with linear function approximation | Average-reward policy evaluation · Linear function approximation setting | mean-squared error: ˜O(1/k) | Helped |
Surprising findings
- Prior average-reward variance work (Prashanth & Ghavamzadeh 2016) uses only the per-step variance term as a surrogate, which ignores temporal correlation that is non-negligible in Markov settings.
Limitations
- Algorithm requires two independent trajectories, doubling sample requirements.
- Linear function approximation incurs an approximation error that is characterized but not eliminated.
- Constant step size yields an asymptotic error floor; diminishing step sizes needed for O~(1/k) rate.
Experimental setup
Metrics: mean-squared error
Builds on: TD learning for average reward (Tsitsiklis & Van Roy 1999) Zhang et al. 2021 average-reward TD finite-sample analysis Tamar et al. 2013 variance TD Prashanth & Ghavamzadeh 2016
Closest papers by meaning
- Variance Penalized On-Policy and Off-Policy Actor-Critic (AAAI 2021 · similarity 0.91)
- Efficient Policy Evaluation with Safety Constraint for Reinforcement Learning (ICLR 2025 · similarity 0.89)
- Sample Complexity of Distributionally Robust Average-Reward Reinforcement Learning (NeurIPS 2025 · similarity 0.88)
- A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach (ICML 2025 · similarity 0.88)
- Averaging $n$-step Returns Reduces Variance in Reinforcement Learning (ICML 2024 · similarity 0.87)
- Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL (NeurIPS 2025 · similarity 0.87)
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.