mlsanityData to 7 Oct 2026

Adaptive Discretization in Online Reinforcement Learning

arXiv 2110.15843 ↗First posted 29 Oct 2021stat.ML cs.LGcited by 12

Not on the map. Why?

Abstract (arXiv)

Discretization based approaches to solving online reinforcement learning problems have been studied extensively in practice on applications ranging from resource allocation to cache management. Two major questions in designing discretization-based algorithms are how to create the discretization and when to refine it. While there have been several experimental results investigating heuristic solutions to these questions, there has been little theoretical treatment. In this paper we provide a unified theoretical analysis of tree-based hierarchical partitioning methods for online reinforcement learning, providing model-free and model-based algorithms. We show how our algorithms are able to take advantage of inherent structure of the problem by providing guarantees that scale with respect to the 'zooming dimension' instead of the ambient dimension, an instance-dependent quantity measuring the benignness of the optimal Qh^star function. Many applications in computing systems and operations research requires algorithms that compete on three facets: low sample complexity, mild storage requirements, and low computational burden. Our algorithms are easily adapted to operating constraints, and our theory provides explicit bounds across each of the three facets. This motivates its use in practical applications as our approach automatically adapts to underlying problem structure even when very little is known a priori about the system.

Key facts. Cited by 12 papers in the map (data through 7 Oct 2026). Builds on 34 of its 74 references that are in the map. First posted on arXiv 29 Oct 2021.

Builds on

34 of 74 references.

References · 34

  1. 2017Proximal Policy Optimization Algorithmscited by 14,441
  2. 2013Playing Atari with Deep Reinforcement Learningcited by 3,211
  3. 2016Asynchronous Methods for Deep Reinforcement Learningcited by 2,218
  4. 2017Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithmcited by 723
  5. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  6. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  7. 2018Is Q-learning Provably Efficient?cited by 485
  8. 2019Introduction to Multi-Armed Banditscited by 475
  9. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  10. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  11. 2018Competitive caching with machine learned advicecited by 194
  12. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
22 more
  1. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  2. 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
  3. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  4. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 104
  5. 2013Bandits and Experts in Metric Spacescited by 63
  6. 2020On Linear Convergence of Policy Gradient Methods for Finite MDPscited by 51
  7. 2020OR-Gym: A Reinforcement Learning Library for Operations Research Problemscited by 50
  8. 2019Tight Regret Bounds for Model-Based Reinforcement Learning with Greedy Policiescited by 38
  9. 2018Q-learning with Nearest Neighborscited by 37
  10. 2020Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimensioncited by 36
  11. 2021Metrics and continuity in reinforcement learningcited by 26
  12. 2020Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimationcited by 25
  13. 2019Explicit Explore-Exploit Algorithms in Continuous State Spacescited by 19
  14. 2019Efficient Model-free Reinforcement Learning in Metric Spacescited by 18
  15. 2019Adaptive Discretization for Episodic Reinforcement Learning in Metric Spacescited by 16
  16. 2020Adaptive Discretization for Model-Based Reinforcement Learningcited by 13
  17. 2021Estimating and Improving Dynamic Treatment Regimes With a Time-Varying Instrumental Variablecited by 13
  18. 2021Reinforcement Learning for Datacenter Congestion Controlcited by 11
  19. 2019Learning to Control in Metric Space with Optimal Regretcited by 9
  20. 2020Provably adaptive reinforcement learning in metric spacescited by 4
  21. 2020Single-partition adaptive Q-learningcited by 1
  22. 2020Control with adaptive Q-learningcited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 3; 2024: 5; 2025: 1; 2026: 1.

12 papers.

  1. 2022Artificial Replay: A Meta-Algorithm for Harnessing Historical Data in Banditscited by 12
  2. 2023Minimax Optimal Q Learning with Nearest Neighborscited by 8
  3. 2023Low-Rank MDPs with Continuous Action Spacescited by 4
  4. 2023Quantile-Based Deep Reinforcement Learning using Two-Timescale Policy Gradient Algorithmscited by 3
  5. 2024Reinforcement Learning for Intensity Control: An Application to Choice-Based Network Revenue Managementcited by 3
  6. 2022An Analysis of Model-Based Reinforcement Learning From Abstracted Observationscited by 2
  7. 2024Exploiting Exogenous Structure for Sample-Efficient Reinforcement Learningcited by 2
  8. 2024How does Your RL Agent Explore? An Optimal Transport Analysis of Occupancy Measure Trajectoriescited by 1
  9. 2025Quantizer Design for Finite Model Approximations, Model Learning, and Quantized Q-Learning for MDPs with Unbounded Spacescited by 1
  10. 2024How to discretize continuous state-action spaces in Q-learning: A symbolic control approachcited by 0
  11. 2024Provably Adaptive Average Reward Reinforcement Learning for Metric Spacescited by 0
  12. 2026Is Pure Exploitation Sufficient in Exogenous MDPs with Linear Function Approximation?cited by 0