mlsanityData to 7 Oct 2026

Horizon-Free and Instance-Dependent Regret Bounds for Reinforcement Learning with General Function Approximation

arXiv 2312.04464 ↗First posted 7 Dec 2023cs.LG stat.MLcited by 4

Not on the map. Why?

Abstract (arXiv)

To tackle long planning horizon problems in reinforcement learning with general function approximation, we propose the first algorithm, termed as UCRL-WVTR, that achieves both horizon-free and instance-dependent, since it eliminates the polynomial dependency on the planning horizon. The derived regret bound is deemed sharp, as it matches the minimax lower bound when specialized to linear mixture MDPs up to logarithmic factors. Furthermore, UCRL-WVTR is computationally efficient with access to a regression oracle. The achievement of such a horizon-free, instance-dependent, and sharp regret bound hinges upon (i) novel algorithm designs: weighted value-targeted regression and a high-order moment estimator in the context of general function approximation; and (ii) fine-grained analyses: a novel concentration bound of weighted non-linear least squares and a refined analysis which leads to the tight instance-dependent bound. We also conduct comprehensive experiments to corroborate our theoretical findings.

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

Builds on

30 of 42 references.

References · 30

  1. 2014Convex Optimization: Algorithms and Complexitycited by 569
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  3. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  4. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  5. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  6. 2021The Statistical Complexity of Interactive Decision Makingcited by 208
  7. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  8. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  9. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  10. 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
  11. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
  12. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
18 more
  1. 2018Practical Contextual Bandits with Regression Oraclescited by 92
  2. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
  3. 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
  4. 2022GEC: A Unified Framework for Interactive Decision Making in MDP, POMDP, and Beyondcited by 45
  5. 2021Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPscited by 44
  6. 2017Active Learning for Cost-Sensitive Classificationcited by 40
  7. 2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 39
  8. 2021First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approachcited by 38
  9. 2022A General Framework for Sample-Efficient Function Approximation in Reinforcement Learningcited by 31
  10. 2022A Provably Efficient Model-Free Posterior Sampling Method for Episodic Reinforcement Learningcited by 30
  11. 2023Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficientcited by 29
  12. 2022Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policiescited by 27
  13. 2023Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Explorationcited by 20
  14. 2021Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learningcited by 17
  15. 2023Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environmentscited by 17
  16. 2023Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function Approximation: Minimax Optimal and Instance-Dependent Regret Boundscited by 13
  17. 2023Instance-Optimality in Interactive Decision Making: Toward a Non-Asymptotic Theorycited by 12
  18. 2023Variance-aware robust reinforcement learning with linear function approximation under heavy-tailed rewardscited by 8

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 2; 2025: 1; 2026: 1.

4 papers.

  1. 2024Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithmscited by 24
  2. 2024Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Boundscited by 11
  3. 2025ORVIT: Near-Optimal Online Distributionally Robust Reinforcement Learningcited by 5
  4. 2026Best-of-Both-Worlds for Heavy-Tailed Markov Decision Processescited by 1