# Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 50 references that are in the map.
- First posted on arXiv 15 Feb 2021.

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

- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [Provably Efficient Exploration in Policy Optimization](https://mlsanity.com/paper/1912.05830/) (2019)
- [Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound](https://mlsanity.com/paper/1905.10389/) (2019)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [Optimism in Reinforcement Learning with Generalized Linear Function Approximation](https://mlsanity.com/paper/1912.04136/) (2019)
- [Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping](https://mlsanity.com/paper/2006.13165/) (2020)
- [Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensembles](https://mlsanity.com/paper/1910.10597/) (2019)
- [Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes](https://mlsanity.com/paper/1910.07072/) (2019)
- [Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learning](https://mlsanity.com/paper/1802.04020/) (2018)
- [Learning Unknown Markov Decision Processes: A Thompson Sampling Approach](https://mlsanity.com/paper/1709.04570/) (2017)
- [Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation](https://mlsanity.com/paper/2007.11849/) (2020)
- [Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function](https://mlsanity.com/paper/1906.05110/) (2019)
- [Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPs](https://mlsanity.com/paper/1803.01626/) (2018)
- [Regret Bounds for Reinforcement Learning via Markov Chain Concentration](https://mlsanity.com/paper/1808.01813/) (2018)
- [Improved Analysis of UCRL2 with Empirical Bernstein Inequality](https://mlsanity.com/paper/2007.05456/) (2020)
- [Near Optimal Exploration-Exploitation in Non-Communicating Markov Decision Processes](https://mlsanity.com/paper/1807.02373/) (2018)
- [Feature-Based Aggregation and Deep Reinforcement Learning: A Survey and Some New Implementations](https://mlsanity.com/paper/1804.04577/) (2018)
- [Adaptive Approximate Policy Iteration](https://mlsanity.com/paper/2002.03069/) (2020)
- [Exploration-Enhanced POLITEX](https://mlsanity.com/paper/1908.10479/) (2019)
- [A Model-free Learning Algorithm for Infinite-horizon Average-reward MDPs with Near-optimal Regret](https://mlsanity.com/paper/2006.04354/) (2020)

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

- [Reward-Free Model-Based Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2110.06394/) (2021)
- [Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPs](https://mlsanity.com/paper/2102.08940/) (2021)
- [Learning Stochastic Shortest Path with Linear Function Approximation](https://mlsanity.com/paper/2110.12727/) (2021)
- [Understanding the Limits of Poisoning Attacks in Episodic Reinforcement Learning](https://mlsanity.com/paper/2208.13663/) (2022)
- [Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximation](https://mlsanity.com/paper/2105.01593/) (2021)
- [Near-Optimal Reward-Free Exploration for Linear Mixture MDPs with Plug-in Solver](https://mlsanity.com/paper/2110.03244/) (2021)
- [Locally Differentially Private Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2110.10133/) (2021)
- [Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs](https://mlsanity.com/paper/2405.15050/) (2024)
- [Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation](https://mlsanity.com/paper/2404.12648/) (2024)
- [Kernel-Based Function Approximation for Average Reward Reinforcement Learning: An Optimist No-Regret Algorithm](https://mlsanity.com/paper/2410.23498/) (2024)
- [Langevin Thompson Sampling with Logarithmic Communication: Bandits and Reinforcement Learning](https://mlsanity.com/paper/2306.08803/) (2023)
- [Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedback](https://mlsanity.com/paper/2311.07876/) (2023)
- [No-Regret Thompson Sampling for Finite-Horizon Markov Decision Processes with Gaussian Processes](https://mlsanity.com/paper/2510.20725/) (2025)
- [Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPs](https://mlsanity.com/paper/2205.09056/) (2022)
- [Reinforcement Learning in a Birth and Death Process: Breaking the Dependence on the State Space](https://mlsanity.com/paper/2302.10667/) (2023)
- [Infinite-Horizon Reinforcement Learning with Multinomial Logistic Function Approximation](https://mlsanity.com/paper/2406.13633/) (2024)
- [Predictive Control and Regret Analysis of Non-Stationary MDP with Look-ahead Information](https://mlsanity.com/paper/2409.08434/) (2024)
- [Learning Infinite-Horizon Average-Reward Linear Mixture MDPs of Bounded Span](https://mlsanity.com/paper/2410.14992/) (2024)

## Abstract (arXiv)

We study reinforcement learning in an infinite-horizon average-reward setting with linear function approximation, where the transition probability function of the underlying Markov Decision Process (MDP) admits a linear form over a feature mapping of the current state, action, and next state. We propose a new algorithm UCRL2-VTR, which can be seen as an extension of the UCRL2 algorithm with linear function approximation. We show that UCRL2-VTR with Bernstein-type bonus can achieve a regret of tildeO(d√DT), where d is the dimension of the feature mapping, T is the horizon, and √D is the diameter of the MDP. We also prove a matching lower bound tildeOmega(d√DT), which suggests that the proposed UCRL2-VTR is minimax optimal up to logarithmic factors. To the best of our knowledge, our algorithm is the first nearly minimax optimal RL algorithm with function approximation in the infinite-horizon average-reward setting.