mlsanityData to 14 Oct 2026

Uniform-PAC Bounds for Reinforcement Learning with Linear Function Approximation

arXiv 2106.11612 ↗First posted 22 Jun 2021cs.LG math.OC stat.MLcited by 14

Not on the map. Why?

Abstract (arXiv)

We study reinforcement learning (RL) with linear function approximation. Existing algorithms for this problem only have high-probability regret and/or Probably Approximately Correct (PAC) sample complexity guarantees, which cannot guarantee the convergence to the optimal policy. In this paper, in order to overcome the limitation of existing algorithms, we propose a new algorithm called FLUTE, which enjoys uniform-PAC convergence to the optimal policy with high probability. The uniform-PAC guarantee is the strongest possible guarantee for reinforcement learning in the literature, which can directly imply both PAC and high probability regret bounds, making our algorithm superior to all existing algorithms with linear function approximation. At the core of our algorithm is a novel minimax value function estimator and a multi-level partition scheme to select the training samples from historical observations. Both of these techniques are new and of independent interest.

Key facts. Cited by 14 papers in the map (data through 14 Oct 2026). Builds on 13 of its 35 references that are in the map. First posted on arXiv 22 Jun 2021.

Builds on

13 of 35 references.

References · 13

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  2. 2018Is Q-learning Provably Efficient?cited by 487
  3. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  4. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
  5. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
  6. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 195
  7. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 181
  8. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 176
  9. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  10. 2014Best-Arm Identification in Linear Banditscited by 100
  11. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
  12. 2019Sequential Experimental Design for Transductive Linear Banditscited by 91
1 more
  1. 2017Fully adaptive algorithm for pure exploration in linear banditscited by 43

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 1; 2022: 1; 2023: 5; 2024: 3; 2025: 3; 2026: 1.

14 papers.

Sort:

By area:

  1. 2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 40
  2. 2022Target Network and Truncation Overcome The Deadly Triad in Q-Learningcited by 31
  3. 2023On the Interplay Between Misspecification and Sub-optimality Gap in Linear Contextual Banditscited by 6
  4. 2025Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximationcited by 6
  5. 2023Learning the Pareto Front Using Bootstrapped Observation Samplescited by 5
  6. 2023Uniform-PAC Guarantees for Model-Based RL with Bounded Eluder Dimensioncited by 3
  7. 2023A Doubly Robust Approach to Sparse Reinforcement Learningcited by 3
  8. 2024Achieving Constant Regret in Linear Markov Decision Processescited by 3
  9. 2025Efficient Preference-Based Reinforcement Learning: Randomized Exploration Meets Experimental Designcited by 3
  10. 2024Variance-Dependent Regret Bounds for Non-stationary Linear Banditscited by 2
  11. 2024On shallow planning under partial observabilitycited by 1
  12. 2025Instance-Dependent Continuous-Time Reinforcement Learning via Maximum Likelihood Estimationcited by 1
2 more
  1. 2021Uncertainty-aware Low-Rank Q-Matrix Estimation for Deep Reinforcement Learningcited by 0
  2. 2026Frozen Policy Iteration: Computationally Efficient RL under Linear Qπ Realizability for Deterministic Dynamicscited by 0