mlsanityData to 14 Oct 2026

Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation

arXiv 2007.11849 ↗First posted 23 Jul 2020cs.LG stat.MLcited by 48

Not on the map. Why?

Abstract (arXiv)

We develop several new algorithms for learning Markov Decision Processes in an infinite-horizon average-reward setting with linear function approximation. Using the optimism principle and assuming that the MDP has a linear structure, we first propose a computationally inefficient algorithm with optimal widetildeO(√T) regret and another computationally efficient variant with widetildeO(T3/4) regret, where T is the number of interactions. Next, taking inspiration from adversarial linear bandits, we develop yet another efficient algorithm with widetildeO(√T) regret under a different set of assumptions, improving the best existing result by Hao et al. (2020) with widetildeO(T2/3) regret. Moreover, we draw a connection between this algorithm and the Natural Policy Gradient algorithm proposed by Kakade (2002), and show that our analysis improves the sample complexity bound recently given by Agarwal et al. (2020).

Key facts. Cited by 48 papers in the map (data through 14 Oct 2026). First posted on arXiv 23 Jul 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 14; 2022: 4; 2023: 11; 2024: 8; 2025: 7; 2026: 4.

48 papers.

Sort:

By area:

  1. 2021Understanding Domain Randomization for Sim-to-real Transfercited by 80
  2. 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 57
  3. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 52
  4. 2022Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraintscited by 29
  5. 2023Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processescited by 29
  6. 2021Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisitingcited by 28
  7. 2023Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processescited by 26
  8. 2024Distributionally Robust Off-Dynamics Reinforcement Learning: Provable Efficiency with Linear Function Approximationcited by 25
  9. 2021Efficient Local Planning with Linear Function Approximationcited by 23
  10. 2021Average-Reward Reinforcement Learning with Trust Region Methodscited by 19
  11. 2023Refined Regret for Adversarial MDPs with Linear Function Approximationcited by 19
  12. 2021Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 18
36 more
  1. 2021Improved Regret Bound and Experience Replay in Regularized Policy Iterationcited by 18
  2. 2021Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Modelcited by 18
  3. 2021Online Learning for Unknown Partially Observable MDPscited by 17
  4. 2023Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximationcited by 17
  5. 2023Best of Both Worlds Policy Optimizationcited by 17
  6. 2021Online Learning for Stochastic Shortest Path Model via Posterior Samplingcited by 16
  7. 2021Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximationcited by 15
  8. 2021Improved No-Regret Algorithms for Stochastic Shortest Path with Linear MDPcited by 14
  9. 2021Provably Efficient Representation Selection in Low-rank Markov Decision Processes: From Online to Offline RLcited by 12
  10. 2021Adjacency constraint for efficient hierarchical reinforcement learningcited by 10
  11. 2024On Convergence of Average-Reward Q-Learning in Weakly Communicating Markov Decision Processescited by 9
  12. 2022Efficient Global Planning in Large MDPs via Stochastic Primal-Dual Optimizationcited by 8
  13. 2023Optimistic Planning by Regularized Dynamic Programmingcited by 8
  14. 2025Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approachcited by 7
  15. 2023Efficient Planning in Combinatorial Action Spaces with Applications to Cooperative Multi-Agent Reinforcement Learningcited by 6
  16. 2023Delay-Adapted Policy Optimization and Improved Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 6
  17. 2024Towards Global Optimality for Practical Average Reward Reinforcement Learning without Mixing Time Oraclescited by 6
  18. 2024Kernel-Based Function Approximation for Average Reward Reinforcement Learning: An Optimist No-Regret Algorithmcited by 6
  19. 2025Average-Reward Soft Actor-Criticcited by 6
  20. 2023Langevin Thompson Sampling with Logarithmic Communication: Bandits and Reinforcement Learningcited by 5
  21. 2023ACPO: A Policy Optimization Algorithm for Average MDPs with Constraintscited by 4
  22. 2025An Improved Algorithm for Adversarial Linear Contextual Bandits via Reductioncited by 4
  23. 2025No-Regret Thompson Sampling for Finite-Horizon Markov Decision Processes with Gaussian Processescited by 4
  24. 2023Provable Reset-free Reinforcement Learning by No-Regret Reductioncited by 3
  25. 2022Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPscited by 2
  26. 2024Infinite-Horizon Reinforcement Learning with Multinomial Logistic Function Approximationcited by 2
  27. 2025Finite-Time Bounds for Average-Reward Fitted Q-Iterationcited by 2
  28. 2026Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regretcited by 2
  29. 2024Policy Zooming: Adaptive Discretization-based Infinite-Horizon Average-Reward Reinforcement Learningcited by 1
  30. 2024Learning Infinite-Horizon Average-Reward Linear Mixture MDPs of Bounded Spancited by 1
  31. 2025A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Modelcited by 1
  32. 2026Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Costcited by 1
  33. 2024Provably Adaptive Average Reward Reinforcement Learning for Metric Spacescited by 0
  34. 2025Influential Bandits: Pulling an Arm May Change the Environmentcited by 0
  35. 2026Finite Constant Frontiers and Auditable Regret Certificates for Average-Reward Reinforcement Learningcited by 0
  36. 2026Learning Infinite-Horizon Average-Reward CMDPs via State Augmentationcited by 0