mlsanityData to 7 Oct 2026

Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation

arXiv 2404.12648 ↗First posted 19 Apr 2024cs.LG stat.MLcited by 6

Not on the map. Why?

Abstract (arXiv)

We study infinite-horizon average-reward Markov decision processes (AMDPs) in the context of general function approximation. Specifically, we propose a novel algorithmic framework named Local-fitted Optimization with OPtimism (LOOP), which incorporates both model-based and value-based incarnations. In particular, LOOP features a novel construction of confidence sets and a low-switching policy updating scheme, which are tailored to the average-reward and function approximation setting. Moreover, for AMDPs, we propose a novel complexity measure -- average-reward generalized eluder coefficient (AGEC) -- which captures the challenge of exploration in AMDPs with general function approximation. Such a complexity measure encompasses almost all previously known tractable AMDP models, such as linear AMDPs and linear mixture AMDPs, and also includes newly identified cases such as kernel AMDPs and AMDPs with Bellman eluder dimensions. Using AGEC, we prove that LOOP achieves a sublinear tildeO(poly(d, sp(V^*)) √Tβ ) regret, where d and β correspond to AGEC and log-covering number of the hypothesis class respectively, sp(V^*) is the span of the optimal state bias function, T denotes the number of steps, and tildeO (·) omits logarithmic factors. When specialized to concrete AMDP models, our regret bounds are comparable to those established by the existing algorithms designed specifically for these special cases. To the best of our knowledge, this paper presents the first comprehensive theoretical framework capable of handling nearly all AMDPs.

Key facts. Cited by 6 papers in the map (data through 7 Oct 2026). Builds on 38 of its 58 references that are in the map. First posted on arXiv 19 Apr 2024.

Builds on

38 of 58 references.

References · 38

  1. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  2. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  3. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  4. 2021The Statistical Complexity of Interactive Decision Makingcited by 208
  5. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  6. 2014Taming the Monster: A Fast and Simple Algorithm for Contextual Banditscited by 200
  7. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  8. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  9. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  10. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  11. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  12. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
26 more
  1. 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
  2. 2019Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processescited by 81
  3. 2019Provably Efficient Q-Learning with Low Switching Costcited by 77
  4. 2021Understanding Domain Randomization for Sim-to-real Transfercited by 69
  5. 2017Learning Unknown Markov Decision Processes: A Thompson Sampling Approachcited by 65
  6. 2018Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learningcited by 65
  7. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  8. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
  9. 2022GEC: A Unified Framework for Interactive Decision Making in MDP, POMDP, and Beyondcited by 45
  10. 2022VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximationcited by 44
  11. 2019Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Functioncited by 43
  12. 2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 39
  13. 2020A Kernel-Based Approach to Non-Stationary Reinforcement Learning in Metric Spacescited by 32
  14. 2022A General Framework for Sample-Efficient Function Approximation in Reinforcement Learningcited by 31
  15. 2022A Provably Efficient Model-Free Posterior Sampling Method for Episodic Reinforcement Learningcited by 30
  16. 2023Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficientcited by 29
  17. 2023A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processescited by 28
  18. 2023Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processescited by 28
  19. 2022Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDPcited by 25
  20. 2018Regret Bounds for Reinforcement Learning via Markov Chain Concentrationcited by 19
  21. 2021Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 18
  22. 2021Improved Regret Bound and Experience Replay in Regularized Policy Iterationcited by 18
  23. 2023Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function Approximation: Minimax Optimal and Instance-Dependent Regret Boundscited by 13
  24. 2022Provable Sim-to-real Transfer in Continuous Domain with Partial Observationscited by 9
  25. 2023Variance-aware robust reinforcement learning with linear function approximation under heavy-tailed rewardscited by 8
  26. 2023A General Framework for Sequential Decision-Making under Adaptivity Constraintscited by 6

Built on by

Cited by year

Citing papers per year: 2024: 5; 2025: 1.

6 papers.

  1. 2025Optimistically Optimistic Exploration for Provably Efficient Infinite-Horizon Reinforcement and Imitation Learningcited by 12
  2. 2024Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPscited by 7
  3. 2024Infinite-Horizon Reinforcement Learning with Multinomial Logistic Function Approximationcited by 2
  4. 2024Policy Zooming: Adaptive Discretization-based Infinite-Horizon Average-Reward Reinforcement Learningcited by 1
  5. 2024Learning Infinite-Horizon Average-Reward Linear Mixture MDPs of Bounded Spancited by 1
  6. 2024Provably Adaptive Average Reward Reinforcement Learning for Metric Spacescited by 0