mlsanityData to 7 Oct 2026

The Sample-Complexity of General Reinforcement Learning

arXiv 1308.4828 ↗First posted 22 Aug 2013cs.LGcited by 18

Not on the map. Why?

Abstract (arXiv)

We present a new algorithm for general reinforcement learning where the true environment is known to belong to a finite class of N arbitrary models. The algorithm is shown to be near-optimal for all but O(N log^2 N) time-steps with high probability. Infinite classes are also considered where we show that compactness is a key criterion for determining the existence of uniform sample-complexity bounds. A matching lower bound is given for the finite case.

Key facts. Cited by 18 papers in the map (data through 7 Oct 2026). First posted on arXiv 22 Aug 2013.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

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

18 papers.

Sort:

By area:

  1. 2022Settling the Reward Hypothesiscited by 33
  2. 2021Tesseract: Tensorised Actors for Multi-Agent Reinforcement Learningcited by 25
  3. 2022Markov Abstractions for PAC Reinforcement Learning in Non-Markov Decision Processescited by 10
  4. 2025Benchmarking Quantum Reinforcement Learningcited by 9
  5. 2025BOFormer: Learning to Solve Multi-Objective Bayesian Optimization via Non-Markovian RLcited by 9
  6. 2023On the Convergence of Bounded Agentscited by 7
  7. 2021Reinforcement Learning in Factored Action Spaces using Tensor Decompositionscited by 6
  8. 2023Quantum Natural Policy Gradients: Towards Sample-Efficient Reinforcement Learningcited by 6
  9. 2025Modeling Others' Minds as Codecited by 6
  10. 2024Towards Efficient Risk-Sensitive Policy Gradient: An Iteration Complexity Analysiscited by 5
  11. 2024Logical Specifications-guided Dynamic Task Sampling for Reinforcement Learning Agentscited by 3
  12. 2026ProActor: Timing-Aware Reinforcement Learning for Proactive Task Scheduling Agentscited by 3
6 more
  1. 2022Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPscited by 2
  2. 2022An Analysis of Model-Based Reinforcement Learning From Abstracted Observationscited by 2
  3. 2024Tractable Offline Learning of Regular Decision Processescited by 2
  4. 2025Constructing Non-Markovian Decision Process via History Aggregatorcited by 1
  5. 2026Adapting Actively on the Fly: Relevance-Guided Online Meta-Learning with Latent Concepts for Geospatial Discoverycited by 0
  6. 2026Precision Physical Activity Prescription via Reinforcement Learning for Functional Actionscited by 0