mlsanityData to 7 Oct 2026

Provably Efficient Reinforcement Learning via Surprise Bound

arXiv 2302.11634 ↗First posted 22 Feb 2023cs.LGcited by 4

Not on the map. Why?

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.

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

Builds on

31 of 57 references.

References · 31

  1. 2013Playing Atari with Deep Reinforcement Learningcited by 3,211
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  3. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  4. 2018Is Q-learning Provably Efficient?cited by 485
  5. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  6. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  7. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  8. 2021The Statistical Complexity of Interactive Decision Makingcited by 208
  9. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  10. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  11. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  12. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
19 more
  1. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  2. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  3. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  4. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  5. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 124
  6. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  7. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 108
  8. 2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 105
  9. 2018Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clusteringcited by 94
  10. 2018Practical Contextual Bandits with Regression Oraclescited by 92
  11. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  12. 2020Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspectivecited by 78
  13. 2018Information Directed Sampling and Bandits with Heteroscedastic Noisecited by 75
  14. 2020Q-learning with Logarithmic Regretcited by 59
  15. 2019Nearly Minimax-Optimal Regret for Linearly Parameterized Banditscited by 54
  16. 2020Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?cited by 34
  17. 2017Posterior sampling for reinforcement learning: worst-case regret boundscited by 28
  18. 2019√n-Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rankcited by 20
  19. 2020Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexitycited by 19

Built on by

Cited by year

Citing papers per year: 2023: 2; 2024: 2.

4 papers.

  1. 2024Efficient Prompt Caching via Embedding Similaritycited by 9
  2. 2023On Representation Complexity of Model-based and Model-free Reinforcement Learningcited by 6
  3. 2023Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oraclescited by 5
  4. 2024On the Limited Representational Power of Value Functions and its Links to Statistical (In)Efficiencycited by 0