mlsanityData to 7 Oct 2026

Provably Adaptive Average Reward Reinforcement Learning for Metric Spaces

arXiv 2410.19919 ↗First posted 25 Oct 2024cs.LG cs.AIcited by 0

Not on the map. Why?

Abstract (arXiv)

We study infinite-horizon average-reward reinforcement learning (RL) for Lipschitz MDPs, a broad class that subsumes several important classes such as linear and RKHS MDPs, function approximation frameworks, and develop an adaptive algorithm ZoRL with regret bounded as Obig(T^1 - deff.-1big), where deff.= 2dS + dz + 3, dS is the dimension of the state space and dz is the zooming dimension. In contrast, algorithms with fixed discretization yield deff. = 2(dS + dA) + 2, dA being the dimension of action space. ZoRL achieves this by discretizing the state-action space adaptively and zooming into ''promising regions'' of the state-action space. dz, a problem-dependent quantity bounded by the state-action space's dimension, allows us to conclude that if an MDP is benign, then the regret of ZoRL will be small. The zooming dimension and ZoRL are truly adaptive, i.e., the current work shows how to capture adaptivity gains for infinite-horizon average-reward RL. ZoRL outperforms other state-of-the-art algorithms in experiments, thereby demonstrating the gains arising due to adaptivity.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 24 of its 47 references that are in the map. First posted on arXiv 25 Oct 2024.

Builds on

24 of 47 references.

References · 24

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  2. 2021RMA: Rapid Motor Adaptation for Legged Robotscited by 430
  3. 2021How to Train Your Robot with Deep Reinforcement Learning; Lessons We've Learnedcited by 201
  4. 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
  5. 2020Information Theoretic Regret Bounds for Online Nonlinear Controlcited by 87
  6. 2017Learning Unknown Markov Decision Processes: A Thompson Sampling Approachcited by 65
  7. 2018Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learningcited by 65
  8. 2020Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 48
  9. 2018Q-learning with Nearest Neighborscited by 37
  10. 2019On Online Learning in Kernelized Markov Decision Processescited by 32
  11. 2020Kernel-Based Reinforcement Learning: A Finite-Time Analysiscited by 23
  12. 2018Regret Bounds for Reinforcement Learning via Markov Chain Concentrationcited by 19
12 more
  1. 2019Efficient Model-free Reinforcement Learning in Metric Spacescited by 18
  2. 2013Online Regret Bounds for Undiscounted Continuous Reinforcement Learningcited by 17
  3. 2019Adaptive Discretization for Episodic Reinforcement Learning in Metric Spacescited by 16
  4. 2019Near-optimal Optimistic Reinforcement Learning using Empirical Bernstein Inequalitiescited by 15
  5. 2023Optimal Sample Complexity for Average Reward Markov Decision Processescited by 13
  6. 2021Adaptive Discretization in Online Reinforcement Learningcited by 12
  7. 2023On the Effectiveness of Offline RL for Dialogue Response Generationcited by 6
  8. 2024No-Regret Reinforcement Learning in Smooth MDPscited by 6
  9. 2024Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximationcited by 6
  10. 2024Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPscited by 5
  11. 2020Provably adaptive reinforcement learning in metric spacescited by 4
  12. 2024Policy Zooming: Adaptive Discretization-based Infinite-Horizon Average-Reward Reinforcement Learningcited by 1

Built on by

Not cited yet.