# Performance Bounds for Policy-Based Average Reward Reinforcement Learning Algorithms

arXiv: https://arxiv.org/abs/2302.01450 · HTML: https://mlsanity.com/paper/2302.01450/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 33 references that are in the map.
- First posted on arXiv 2 Feb 2023.

## Builds on (most cited first, 6 of 6)

- [On the Global Convergence Rates of Softmax Policy Gradient Methods](https://mlsanity.com/paper/2005.06392/) (2020)
- [Learning and Planning in Average-Reward Markov Decision Processes](https://mlsanity.com/paper/2006.16318/) (2020)
- [Average-Reward Off-Policy Policy Evaluation with Function Approximation](https://mlsanity.com/paper/2101.02808/) (2021)
- [Target Network and Truncation Overcome The Deadly Triad in Q-Learning](https://mlsanity.com/paper/2203.02628/) (2022)
- [Improved Regret Bound and Experience Replay in Regularized Policy Iteration](https://mlsanity.com/paper/2102.12611/) (2021)
- [The Role of Lookahead and Approximate Policy Evaluation in Reinforcement Learning with Linear Value Function Approximation](https://mlsanity.com/paper/2109.13419/) (2021)

## Built on by (most cited first, 7 of 7)

- [Order-Optimal Regret with Novel Policy Gradient Approaches in Infinite-Horizon Average Reward MDPs](https://mlsanity.com/paper/2404.02108/) (2024)
- [On the Global Convergence of Policy Gradient in Average Reward Markov Decision Processes](https://mlsanity.com/paper/2403.06806/) (2024)
- [Performance of NPG in Countable State-Space Average-Cost RL](https://mlsanity.com/paper/2405.20467/) (2024)
- [RL-Selector: Reinforcement Learning-Guided Data Selection via Redundancy Assessment](https://mlsanity.com/paper/2506.21037/) (2025)
- [On the Convergence of Policy Mirror Descent with Temporal Difference Evaluation](https://mlsanity.com/paper/2509.18822/) (2025)
- [Natural Policy Gradient for Average Reward Non-Stationary RL](https://mlsanity.com/paper/2504.16415/) (2025)
- [Sharp Convergence and Sample Complexity of Policy Mirror Descent for Average-Reward MDPs](https://mlsanity.com/paper/2610.04117/) (2026)

## Abstract (arXiv)

Many policy-based reinforcement learning (RL) algorithms can be viewed as instantiations of approximate policy iteration (PI), i.e., where policy improvement and policy evaluation are both performed approximately. In applications where the average reward objective is the meaningful performance metric, discounted reward formulations are often used with the discount factor being close to 1, which is equivalent to making the expected horizon very large. However, the corresponding theoretical bounds for error performance scale with the square of the horizon. Thus, even after dividing the total reward by the length of the horizon, the corresponding performance bounds for average reward problems go to infinity. Therefore, an open problem has been to obtain meaningful performance bounds for approximate PI and RL algorithms for the average-reward setting. In this paper, we solve this open problem by obtaining the first finite-time error bounds for average-reward MDPs, and show that the asymptotic error goes to zero in the limit as policy evaluation and policy improvement errors go to zero.