# The Sample-Complexity of General Reinforcement Learning

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

## Key facts

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

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

- [Settling the Reward Hypothesis](https://mlsanity.com/paper/2212.10420/) (2022)
- [Tesseract: Tensorised Actors for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2106.00136/) (2021)
- [Markov Abstractions for PAC Reinforcement Learning in Non-Markov Decision Processes](https://mlsanity.com/paper/2205.01053/) (2022)
- [Benchmarking Quantum Reinforcement Learning](https://mlsanity.com/paper/2501.15893/) (2025)
- [BOFormer: Learning to Solve Multi-Objective Bayesian Optimization via Non-Markovian RL](https://mlsanity.com/paper/2505.21974/) (2025)
- [On the Convergence of Bounded Agents](https://mlsanity.com/paper/2307.11044/) (2023)
- [Modeling Others' Minds as Code](https://mlsanity.com/paper/2510.01272/) (2025)
- [Reinforcement Learning in Factored Action Spaces using Tensor Decompositions](https://mlsanity.com/paper/2110.14538/) (2021)
- [Quantum Natural Policy Gradients: Towards Sample-Efficient Reinforcement Learning](https://mlsanity.com/paper/2304.13571/) (2023)
- [Towards Efficient Risk-Sensitive Policy Gradient: An Iteration Complexity Analysis](https://mlsanity.com/paper/2403.08955/) (2024)
- [Logical Specifications-guided Dynamic Task Sampling for Reinforcement Learning Agents](https://mlsanity.com/paper/2402.03678/) (2024)
- [Tractable Offline Learning of Regular Decision Processes](https://mlsanity.com/paper/2409.02747/) (2024)
- [ProActor: Timing-Aware Reinforcement Learning for Proactive Task Scheduling Agents](https://mlsanity.com/paper/2605.24900/) (2026)
- [Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPs](https://mlsanity.com/paper/2205.09056/) (2022)
- [An Analysis of Model-Based Reinforcement Learning From Abstracted Observations](https://mlsanity.com/paper/2208.14407/) (2022)
- [Constructing Non-Markovian Decision Process via History Aggregator](https://mlsanity.com/paper/2506.24026/) (2025)
- [Precision Physical Activity Prescription via Reinforcement Learning for Functional Actions](https://mlsanity.com/paper/2605.19208/) (2026)
- [Adapting Actively on the Fly: Relevance-Guided Online Meta-Learning with Latent Concepts for Geospatial Discovery](https://mlsanity.com/paper/2602.17605/) (2026)

## 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.