# Provably Efficient Reinforcement Learning with Aggregated States

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Dec 2019.

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

- [Bilinear Classes: A Structural Framework for Provable Generalization in RL](https://mlsanity.com/paper/2103.10897/) (2021)
- [On the Complexity of Adversarial Decision Making](https://mlsanity.com/paper/2206.13063/) (2022)
- [Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature](https://mlsanity.com/paper/2102.04168/) (2021)
- [A General Framework for Sample-Efficient Function Approximation in Reinforcement Learning](https://mlsanity.com/paper/2209.15634/) (2022)
- [Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient](https://mlsanity.com/paper/2301.08215/) (2023)
- [Regret Minimization Experience Replay in Off-Policy Reinforcement Learning](https://mlsanity.com/paper/2105.07253/) (2021)
- [Deciding What to Model: Value-Equivalent Sampling for Reinforcement Learning](https://mlsanity.com/paper/2206.02072/) (2022)
- [Model-Free Reinforcement Learning with the Decision-Estimation Coefficient](https://mlsanity.com/paper/2211.14250/) (2022)
- [Improved Algorithms for Misspecified Linear Markov Decision Processes](https://mlsanity.com/paper/2109.05546/) (2021)
- [Learning to Order for Inventory Systems with Lost Sales and Uncertain Supplies](https://mlsanity.com/paper/2207.04550/) (2022)
- [The RL Perceptron: Generalisation Dynamics of Policy Learning in High Dimensions](https://mlsanity.com/paper/2306.10404/) (2023)
- [Planning to the Information Horizon of BAMDPs via Epistemic State Abstraction](https://mlsanity.com/paper/2210.16872/) (2022)
- [Exponential Hardness of Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2302.12940/) (2023)
- [Demystifying Linear MDPs and Novel Dynamics Aggregation Framework](https://mlsanity.com/paper/2410.24089/) (2024)
- [Computational-Statistical Gaps in Reinforcement Learning](https://mlsanity.com/paper/2202.05444/) (2022)
- [Finding Safe Zones of policies Markov Decision Processes](https://mlsanity.com/paper/2202.11593/) (2022)
- [Reinforcement Learning with Markov Risk Measures and Multipattern Risk Approximation](https://mlsanity.com/paper/2605.00654/) (2026)
- [Commit to the Bit: Reactive Reinforcement Learning Done Right](https://mlsanity.com/paper/2605.28276/) (2026)
- [Concurrent Learning with Aggregated States via Randomized Least Squares Value Iteration](https://mlsanity.com/paper/2501.13394/) (2025)
- [Mini-Batch Risk-Averse Deep Q-Learning: A Robot Navigation Case Study](https://mlsanity.com/paper/2609.07998/) (2026)

## Abstract (arXiv)

We establish that an optimistic variant of Q-learning applied to a fixed-horizon episodic Markov decision process with an aggregated state representation incurs regret tildeO(√H5 M K + ε HK), where H is the horizon, M is the number of aggregate states, K is the number of episodes, and ε is the largest difference between any pair of optimal state-action values associated with a common aggregate state. Notably, this regret bound does not depend on the number of states or actions and indicates that asymptotic per-period regret is no greater than ε, independent of horizon. To our knowledge, this is the first such result that applies to reinforcement learning with nontrivial value function approximation without any restrictions on transition probabilities.