mlsanityData to 7 Oct 2026

Provably Efficient Reinforcement Learning with Aggregated States

arXiv 1912.06366 ↗First posted 13 Dec 2019stat.ML cs.LG math.OCcited by 20

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 4; 2022: 8; 2023: 3; 2024: 1; 2025: 1; 2026: 3.

20 papers.

Sort:

  1. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  2. 2021Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvaturecited by 32
  3. 2022On the Complexity of Adversarial Decision Makingcited by 32
  4. 2022A General Framework for Sample-Efficient Function Approximation in Reinforcement Learningcited by 31
  5. 2023Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficientcited by 29
  6. 2021Regret Minimization Experience Replay in Off-Policy Reinforcement Learningcited by 25
  7. 2022Deciding What to Model: Value-Equivalent Sampling for Reinforcement Learningcited by 19
  8. 2022Model-Free Reinforcement Learning with the Decision-Estimation Coefficientcited by 11
  9. 2021Improved Algorithms for Misspecified Linear Markov Decision Processescited by 6
  10. 2022Learning to Order for Inventory Systems with Lost Sales and Uncertain Suppliescited by 5
  11. 2023The RL Perceptron: Generalisation Dynamics of Policy Learning in High Dimensionscited by 5
  12. 2022Planning to the Information Horizon of BAMDPs via Epistemic State Abstractioncited by 4
8 more
  1. 2023Exponential Hardness of Reinforcement Learning with Linear Function Approximationcited by 4
  2. 2024Demystifying Linear MDPs and Novel Dynamics Aggregation Frameworkcited by 4
  3. 2022Computational-Statistical Gaps in Reinforcement Learningcited by 3
  4. 2022Finding Safe Zones of policies Markov Decision Processescited by 1
  5. 2026Reinforcement Learning with Markov Risk Measures and Multipattern Risk Approximationcited by 1
  6. 2026Commit to the Bit: Reactive Reinforcement Learning Done Rightcited by 1
  7. 2025Concurrent Learning with Aggregated States via Randomized Least Squares Value Iterationcited by 0
  8. 2026Mini-Batch Risk-Averse Deep Q-Learning: A Robot Navigation Case Studycited by 0