mlsanityData to 7 Oct 2026

Frequentist Regret Bounds for Randomized Least-Squares Value Iteration

arXiv 1911.00567 ↗First posted 1 Nov 2019cs.LG stat.MLcited by 100

Not on the map. Why?

Abstract (arXiv)

We consider the exploration-exploitation dilemma in finite-horizon reinforcement learning (RL). When the state space is large or continuous, traditional tabular approaches are unfeasible and some form of function approximation is mandatory. In this paper, we introduce an optimistically-initialized variant of the popular randomized least-squares value iteration (RLSVI), a model-free algorithm where exploration is induced by perturbing the least-squares approximation of the action-value function. Under the assumption that the Markov decision process has low-rank transition dynamics, we prove that the frequentist regret of RLSVI is upper-bounded by widetilde O(d2 H2 √T) where d are the feature dimension, H is the horizon, and T is the total number of steps. To the best of our knowledge, this is the first frequentist regret analysis for randomized exploration with function approximation.

Key facts. Cited by 100 papers in the map (data through 7 Oct 2026). First posted on arXiv 1 Nov 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2020: 1; 2021: 26; 2022: 21; 2023: 18; 2024: 12; 2025: 14; 2026: 8.

100 papers.

Sort:

By area:

  1. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learningcited by 109
  2. 2021Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learningcited by 65
  3. 2022Unpacking Reward Shaping: Understanding the Benefits of Reward Engineering on Sample Complexitycited by 59
  4. 2021Exploration in Deep Reinforcement Learning: From Single-Agent to Multiagent Domaincited by 57
  5. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  6. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
  7. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
  8. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 51
  9. 2021Randomized Exploration for Reinforcement Learning with General Value Function Approximationcited by 49
  10. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  11. 2022Leveraging Offline Data in Online Reinforcement Learningcited by 42
  12. 2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 39
38 more
  1. 2021A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Costcited by 38
  2. 2021First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approachcited by 38
  3. 2022Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Designcited by 33
  4. 2022Model-based RL with Optimistic Posterior Sampling: Structural Conditions and Sample Complexitycited by 31
  5. 2021Robust Policy Gradient against Strong Data Corruptioncited by 30
  6. 2021Minimax Regret for Stochastic Shortest Pathcited by 30
  7. 2022Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximationcited by 30
  8. 2022A Provably Efficient Model-Free Posterior Sampling Method for Episodic Reinforcement Learningcited by 30
  9. 2021Reward-Free Model-Based Reinforcement Learning with Linear Function Approximationcited by 29
  10. 2023Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlocited by 29
  11. 2021Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPscited by 28
  12. 2021Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisitingcited by 27
  13. 2021Principled Exploration via Optimistic Bootstrapping and Backward Inductioncited by 26
  14. 2021Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Gamescited by 25
  15. 2024Distributionally Robust Off-Dynamics Reinforcement Learning: Provable Efficiency with Linear Function Approximationcited by 25
  16. 2020Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficientcited by 24
  17. 2022Regret Bounds for Information-Directed Reinforcement Learningcited by 24
  18. 2021Learning Stochastic Shortest Path with Linear Function Approximationcited by 23
  19. 2022Near-Optimal Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 22
  20. 2021On Reward-Free RL with Kernel and Neural Function Approximations: Single-Agent MDP and Markov Gamecited by 20
  21. 2023Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Explorationcited by 20
  22. 2023Kernelized Reinforcement Learning with Order Optimal Regret Boundscited by 20
  23. 2021Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Modelcited by 18
  24. 2021Reinforcement Learning in Linear MDPs: Constant Regret and Representation Selectioncited by 17
  25. 2025Langevin Soft Actor-Critic: Efficient Exploration through Uncertainty-Driven Critic Learningcited by 17
  26. 2023Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximationcited by 16
  27. 2021Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximationcited by 15
  28. 2024Upper and Lower Bounds for Distributionally Robust Off-Dynamics Reinforcement Learningcited by 15
  29. 2021Near-Optimal Randomized Exploration for Tabular Markov Decision Processescited by 14
  30. 2021Improved No-Regret Algorithms for Stochastic Shortest Path with Linear MDPcited by 14
  31. 2022A Self-Play Posterior Sampling Algorithm for Zero-Sum Markov Gamescited by 14
  32. 2023Improved Regret Bounds for Linear Adversarial MDPs via Linear Optimizationcited by 14
  33. 2023A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximationcited by 14
  34. 2021An L2 Analysis of Reinforcement Learning in High Dimensions with Kernel and Neural Network Approximationcited by 13
  35. 2022Model-Based Reinforcement Learning with Multinomial Logistic Function Approximationcited by 13
  36. 2022Optimistic Posterior Sampling for Reinforcement Learning with Few Samples and Tight Guaranteescited by 12
  37. 2022Bilinear Exponential Family of MDPs: Frequentist Regret Bound with Tractable Exploration and Planningcited by 12
  38. 2024More Efficient Randomized Exploration for Reinforcement Learning via Approximate Samplingcited by 12

50 most cited of 100 All 100 (JSON)