# Adaptive Discretization for Model-Based Reinforcement Learning

arXiv: https://arxiv.org/abs/2007.00717 · HTML: https://mlsanity.com/paper/2007.00717/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jul 2020.

## Built on by (most cited first, 13 of 13)

- [UCB Momentum Q-learning: Correcting the bias without forgetting](https://mlsanity.com/paper/2103.01312/) (2021)
- [Lipschitz Bandits with Batched Feedback](https://mlsanity.com/paper/2110.09722/) (2021)
- [Adaptive Discretization in Online Reinforcement Learning](https://mlsanity.com/paper/2110.15843/) (2021)
- [Q-Learning for MDPs with General Spaces: Convergence and Near Optimality via Quantization under Weak Continuity](https://mlsanity.com/paper/2111.06781/) (2021)
- [Overcoming the Long Horizon Barrier for Sample-Efficient Reinforcement Learning with Latent Low-Rank Structure](https://mlsanity.com/paper/2206.03569/) (2022)
- [No-Regret Reinforcement Learning in Smooth MDPs](https://mlsanity.com/paper/2402.03792/) (2024)
- [Local Linearity: the Key for No-regret Reinforcement Learning in Continuous MDPs](https://mlsanity.com/paper/2410.24071/) (2024)
- [Reinforcement Learning for Intensity Control: An Application to Choice-Based Network Revenue Management](https://mlsanity.com/paper/2406.05358/) (2024)
- [Coarse-Grained Smoothness for RL in Metric Spaces](https://mlsanity.com/paper/2110.12276/) (2021)
- [Rethinking the Intermediate Features in Adversarial Attacks: Misleading Robotic Models via Adversarial Distillation](https://mlsanity.com/paper/2411.15222/) (2024)
- [Data-driven Acceleration of MPC with Guarantees](https://mlsanity.com/paper/2511.13588/) (2025)
- [How to discretize continuous state-action spaces in Q-learning: A symbolic control approach](https://mlsanity.com/paper/2406.01548/) (2024)
- [Improved Model-based Reinforcement Learning with Smooth Kernels](https://mlsanity.com/paper/2605.07218/) (2026)

## Abstract (arXiv)

We introduce the technique of adaptive discretization to design an efficient model-based episodic reinforcement learning algorithm in large (potentially continuous) state-action spaces. Our algorithm is based on optimistic one-step value iteration extended to maintain an adaptive discretization of the space. From a theoretical perspective we provide worst-case regret bounds for our algorithm which are competitive compared to the state-of-the-art model-based algorithms. Moreover, our bounds are obtained via a modular proof technique which can potentially extend to incorporate additional structure on the problem. From an implementation standpoint, our algorithm has much lower storage and computational requirements due to maintaining a more efficient partition of the state and action spaces. We illustrate this via experiments on several canonical control problems, which shows that our algorithm empirically performs significantly better than fixed discretization in terms of both faster convergence and lower memory usage. Interestingly, we observe empirically that while fixed-discretization model-based algorithms vastly outperform their model-free counterparts, the two achieve comparable performance with adaptive discretization.