# Provably Efficient Reinforcement Learning via Surprise Bound

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 57 references that are in the map.
- First posted on arXiv 22 Feb 2023.

## Builds on (most cited first, 30 of 31)

- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms](https://mlsanity.com/paper/2102.00815/) (2021)
- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Provably Efficient Exploration in Policy Optimization](https://mlsanity.com/paper/1912.05830/) (2019)
- [Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound](https://mlsanity.com/paper/1905.10389/) (2019)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Learning Near Optimal Policies with Low Inherent Bellman Error](https://mlsanity.com/paper/2003.00153/) (2020)
- [Bilinear Classes: A Structural Framework for Provable Generalization in RL](https://mlsanity.com/paper/2103.10897/) (2021)
- [Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?](https://mlsanity.com/paper/1910.03016/) (2019)
- [Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal](https://mlsanity.com/paper/1906.03804/) (2019)
- [Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition](https://mlsanity.com/paper/2004.10019/) (2020)
- [Optimism in Reinforcement Learning with Generalized Linear Function Approximation](https://mlsanity.com/paper/1912.04136/) (2019)
- [Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2005.12900/) (2020)
- [Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning](https://mlsanity.com/paper/1510.08906/) (2015)
- [Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering](https://mlsanity.com/paper/1807.04518/) (2018)
- [Practical Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/1803.01088/) (2018)
- [Policy Certificates: Towards Accountable Reinforcement Learning](https://mlsanity.com/paper/1811.03056/) (2018)
- [Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective](https://mlsanity.com/paper/2010.03104/) (2020)
- [Information Directed Sampling and Bandits with Heteroscedastic Noise](https://mlsanity.com/paper/1801.09667/) (2018)
- [Q-learning with Logarithmic Regret](https://mlsanity.com/paper/2006.09118/) (2020)
- [Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits](https://mlsanity.com/paper/1904.00242/) (2019)
- [Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?](https://mlsanity.com/paper/2005.00527/) (2020)
- [Posterior sampling for reinforcement learning: worst-case regret bounds](https://mlsanity.com/paper/1705.07041/) (2017)
- [√n-Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rank](https://mlsanity.com/paper/1909.02506/) (2019)

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

- [Efficient Prompt Caching via Embedding Similarity](https://mlsanity.com/paper/2402.01173/) (2024)
- [On Representation Complexity of Model-based and Model-free Reinforcement Learning](https://mlsanity.com/paper/2310.01706/) (2023)
- [Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oracles](https://mlsanity.com/paper/2309.09457/) (2023)
- [On the Limited Representational Power of Value Functions and its Links to Statistical (In)Efficiency](https://mlsanity.com/paper/2403.07136/) (2024)

## Abstract (arXiv)

Value function approximation is important in modern reinforcement learning (RL) problems especially when the state space is (infinitely) large. Despite the importance and wide applicability of value function approximation, its theoretical understanding is still not as sophisticated as its empirical success, especially in the context of general function approximation. In this paper, we propose a provably efficient RL algorithm (both computationally and statistically) with general value function approximations. We show that if the value functions can be approximated by a function class that satisfies the Bellman-completeness assumption, our algorithm achieves an widetildeO(poly(iota H)√T) regret bound where iota is the product of the surprise bound and log-covering numbers, H is the planning horizon, K is the number of episodes and T = HK is the total number of steps the agent interacts with the environment. Our algorithm achieves reasonable regret bounds when applied to both the linear setting and the sparse high-dimensional linear setting. Moreover, our algorithm only needs to solve O(Hlog K) empirical risk minimization (ERM) problems, which is far more efficient than previous algorithms that need to solve ERM problems for Omega(HK) times.