mlsanityData to 7 Oct 2026

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

arXiv 2102.07301 ↗First posted 15 Feb 2021cs.LG math.OC stat.MLcited by 18

Not on the map. Why?

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.

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

Builds on

23 of 50 references.

References · 23

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  3. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  4. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  5. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  6. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  7. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  8. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  9. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  10. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
  11. 2019Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processescited by 81
  12. 2017Learning Unknown Markov Decision Processes: A Thompson Sampling Approachcited by 65
11 more
  1. 2018Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learningcited by 65
  2. 2020Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 48
  3. 2019Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Functioncited by 43
  4. 2018Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPscited by 41
  5. 2018Regret Bounds for Reinforcement Learning via Markov Chain Concentrationcited by 19
  6. 2020Improved Analysis of UCRL2 with Empirical Bernstein Inequalitycited by 18
  7. 2018Near Optimal Exploration-Exploitation in Non-Communicating Markov Decision Processescited by 14
  8. 2018Feature-Based Aggregation and Deep Reinforcement Learning: A Survey and Some New Implementationscited by 12
  9. 2020Adaptive Approximate Policy Iterationcited by 9
  10. 2019Exploration-Enhanced POLITEXcited by 8
  11. 2020A Model-free Learning Algorithm for Infinite-horizon Average-reward MDPs with Near-optimal Regretcited by 7

Built on by

Cited by year

Citing papers per year: 2021: 6; 2022: 2; 2023: 3; 2024: 6; 2025: 1.

18 papers.

Sort:

  1. 2021Reward-Free Model-Based Reinforcement Learning with Linear Function Approximationcited by 29
  2. 2021Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPscited by 28
  3. 2021Learning Stochastic Shortest Path with Linear Function Approximationcited by 23
  4. 2022Understanding the Limits of Poisoning Attacks in Episodic Reinforcement Learningcited by 21
  5. 2021Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximationcited by 15
  6. 2021Near-Optimal Reward-Free Exploration for Linear Mixture MDPs with Plug-in Solvercited by 13
  7. 2021Locally Differentially Private Reinforcement Learning for Linear Mixture Markov Decision Processescited by 13
  8. 2024Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPscited by 7
  9. 2024Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximationcited by 6
  10. 2024Kernel-Based Function Approximation for Average Reward Reinforcement Learning: An Optimist No-Regret Algorithmcited by 6
  11. 2023Langevin Thompson Sampling with Logarithmic Communication: Bandits and Reinforcement Learningcited by 5
  12. 2023Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedbackcited by 4
6 more
  1. 2025No-Regret Thompson Sampling for Finite-Horizon Markov Decision Processes with Gaussian Processescited by 3
  2. 2022Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPscited by 2
  3. 2023Reinforcement Learning in a Birth and Death Process: Breaking the Dependence on the State Spacecited by 2
  4. 2024Infinite-Horizon Reinforcement Learning with Multinomial Logistic Function Approximationcited by 2
  5. 2024Predictive Control and Regret Analysis of Non-Stationary MDP with Look-ahead Informationcited by 2
  6. 2024Learning Infinite-Horizon Average-Reward Linear Mixture MDPs of Bounded Spancited by 1