mlsanityData to 14 Oct 2026

Improving Reinforcement Learning Sample-Efficiency using Local Approximation

arXiv 2507.12383 ↗First posted 16 Jul 2025cs.LGcited by 1

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

In this study, we derive Probably Approximately Correct (PAC) bounds on the asymptotic sample-complexity for RL within the infinite-horizon Markov Decision Process (MDP) setting that are sharper than those in existing literature. The premise of our study is twofold: firstly, the further two states are from each other, transition-wise, the less relevant the value of the first state is when learning the ε-optimal value of the second; secondly, the amount of 'effort', sample-complexity-wise, expended in learning the ε-optimal value of a state is independent of the number of samples required to learn the ε-optimal value of a second state that is a sufficient number of transitions away from the first. Inversely, states within each other's vicinity have values that are dependent on each other and will require a similar number of samples to learn. By approximating the original MDP using smaller MDPs constructed using subsets of the original's state-space, we are able to reduce the sample-complexity by a logarithmic factor to O(SA log A) timesteps, where S and A are the state and action space sizes. We are able to extend these results to an infinite-horizon, model-free setting by constructing a PAC-MDP algorithm with the aforementioned sample-complexity. We conclude with showing how significant the improvement is by comparing our algorithm against prior work in an experimental setting.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 9 of its 24 references that are in the map. First posted on arXiv 16 Jul 2025.

Builds on

9 of 24 references.

References · 9

  1. 2017Learning Complex Dexterous Manipulation with Deep Reinforcement Learning and Demonstrationscited by 715
  2. 2018Is Q-learning Provably Efficient?cited by 487
  3. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 176
  4. 2024Deep Reinforcement Learning for Robotics: A Survey of Real-World Successescited by 176
  5. 2019Variance-reduced Q-learning is minimax optimalcited by 73
  6. 2019Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDPcited by 55
  7. 2020Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexitycited by 28
  8. 2019Efficient Model-free Reinforcement Learning in Metric Spacescited by 18
  9. 2019Adaptive Discretization for Episodic Reinforcement Learning in Metric Spacescited by 16

Built on by

Cited by year

Citing papers per year: 2025: 1.

1 paper.

  1. 2025HAMMER: Hamiltonian Curiosity Augmented Large Language Model Reinforcementcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learning
  2. 2024Sample and Oracle Efficient Reinforcement Learning for MDPs with Linearly-Realizable Value Functions
  3. 2025Primal-Dual Sample Complexity Bounds for Constrained Markov Decision Processes with Multiple Constraints
  4. 2024Achieving Instance-dependent Sample Complexity for Constrained Markov Decision Process
  5. 2024Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs
  6. 2026Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learning
  7. 2025Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL
  8. 2025The Sample Complexity of Online Reinforcement Learning: A Multi-model Perspective