mlsanityData to 14 Oct 2026

Policy Zooming: Adaptive Discretization-based Infinite-Horizon Average-Reward Reinforcement Learning

arXiv 2405.18793 ↗First posted 29 May 2024cs.LGcited by 1

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

We study the infinite-horizon average-reward reinforcement learning (RL) for continuous space Lipschitz MDPs in which an agent can play policies from a given set Phi. The proposed algorithms efficiently explore the policy space by ''zooming'' into the ''promising regions'' of Phi, thereby achieving adaptivity gains in the performance. We upper bound their regret as tildeObig(T^1 - deff.-1big), where deff. = d^Phiz+2 for model-free algoritahm textitPZRL-MF and deff. = 2dS + d^Phiz + 3 for model-based algorithm textitPZRL-MB. Here, dS is the dimension of the state space, and d^Phiz is the zooming dimension given a set of policies Phi. d^Phiz is an alternative measure of the complexity of the problem, and it depends on the underlying MDP as well as on Phi. Hence, the proposed algorithms exhibit low regret in case the problem instance is benign and/or the agent competes against a low-complexity Phi (that has a small d^Phiz). When specialized to the case of finite-dimensional policy space, we obtain that deff. scales as the dimension of this space under mild technical conditions; and also obtain deff. = 2, or equivalently tildeO(√T) regret for textitPZRL-MF, under a curvature condition on the average reward function that is commonly used in the multi-armed bandit (MAB) literature.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 27 of its 53 references that are in the map. First posted on arXiv 29 May 2024.

Builds on

27 of 53 references.

Closest ancestors · 2

Same direction, newest first

  1. 2024Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs10 May
  2. 2024No-Regret Reinforcement Learning in Smooth MDPs6 Feb

Other references · 25

  1. 2022R3M: A Universal Visual Representation for Robot Manipulationcited by 694
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  3. 2021RMA: Rapid Motor Adaptation for Legged Robotscited by 508
  4. 2019Introduction to Multi-Armed Banditscited by 481
  5. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
  6. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 223
  7. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
  8. 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
  9. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 105
  10. 2020Information Theoretic Regret Bounds for Online Nonlinear Controlcited by 90
  11. 2017Learning Unknown Markov Decision Processes: A Thompson Sampling Approachcited by 65
  12. 2013Bandits and Experts in Metric Spacescited by 63
13 more
  1. 2020Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 48
  2. 2022VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximationcited by 44
  3. 2019On Online Learning in Kernelized Markov Decision Processescited by 35
  4. 2020Kernel-Based Reinforcement Learning: A Finite-Time Analysiscited by 23
  5. 2019Efficient Model-free Reinforcement Learning in Metric Spacescited by 18
  6. 2013Online Regret Bounds for Undiscounted Continuous Reinforcement Learningcited by 17
  7. 2019Adaptive Discretization for Episodic Reinforcement Learning in Metric Spacescited by 16
  8. 2019Near-optimal Optimistic Reinforcement Learning using Empirical Bernstein Inequalitiescited by 15
  9. 2023Optimal Sample Complexity for Average Reward Markov Decision Processescited by 15
  10. 2020Reward Biased Maximum Likelihood Estimation for Reinforcement Learningcited by 11
  11. 2024Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximationcited by 6
  12. 2020Provably adaptive reinforcement learning in metric spacescited by 4
  13. 2023Optimal Scheduling Policies for Remote Estimation of Autoregressive Markov Processes over Time-Correlated Fading Channelcited by 1

Built on by

Cited by year

Citing papers per year: 2024: 1.

1 paper.

  1. 2024Provably Adaptive Average Reward Reinforcement Learning for Metric Spacescited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs
  2. 2025A Computationally Efficient Algorithm for Infinite-Horizon Average-Reward Linear MDPs
  3. 2024Provably Efficient Infinite-Horizon Average-Reward Reinforcement Learning with Linear Function Approximation
  4. 2024A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach
  5. 2026Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs
  6. 2024Infinite-Horizon Reinforcement Learning with Multinomial Logistic Function Approximation
  7. 2024On the Global Convergence of Policy Gradient in Average Reward Markov Decision Processes
  8. 2025Efficient Q-Learning and Actor-Critic Methods for Robust Average-Reward Reinforcement Learning