mlsanityData to 7 Oct 2026

Improved Worst-Case Regret Bounds for Randomized Least-Squares Value Iteration

arXiv 2010.12163 ↗First posted 23 Oct 2020cs.LG stat.MLcited by 19

Not on the map. Why?

Abstract (arXiv)

This paper studies regret minimization with randomized value functions in reinforcement learning. In tabular finite-horizon Markov Decision Processes, we introduce a clipping variant of one classical Thompson Sampling (TS)-like algorithm, randomized least-squares value iteration (RLSVI). Our tildeO(H2S√AT) high-probability worst-case regret bound improves the previous sharpest worst-case regret bounds for RLSVI and matches the existing state-of-the-art worst-case TS-based regret bounds.

Key facts. Cited by 19 papers in the map (data through 7 Oct 2026). First posted on arXiv 23 Oct 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

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

19 papers.

Sort:

  1. 2021Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learningcited by 65
  2. 2021Randomized Exploration for Reinforcement Learning with General Value Function Approximationcited by 49
  3. 2022A Provably Efficient Model-Free Posterior Sampling Method for Episodic Reinforcement Learningcited by 30
  4. 2022Towards Deployment-Efficient Reinforcement Learning: Lower Bound and Optimalitycited by 24
  5. 2021Near-Optimal Randomized Exploration for Tabular Markov Decision Processescited by 14
  6. 2022A Self-Play Posterior Sampling Algorithm for Zero-Sum Markov Gamescited by 14
  7. 2021Exponential Family Model-Based Reinforcement Learning via Score Matchingcited by 5
  8. 2024Computationally Efficient RL under Linear Bellman Completeness for Deterministic Dynamicscited by 5
  9. 2023Posterior Sampling with Delayed Feedback for Reinforcement Learning with Linear Function Approximationcited by 3
  10. 2025Provably Efficient and Agile Randomized Q-Learningcited by 2
  11. 2021Reinforcement Learning for Markovian Bandits: Is Posterior Sampling more Scalable than Optimism?cited by 1
  12. 2023Dyadic Reinforcement Learningcited by 1
7 more
  1. 2024Near-Optimal Reinforcement Learning with Shuffle Differential Privacycited by 1
  2. 2025Q-learning with Posterior Samplingcited by 1
  3. 2026Tuning the burn-in phase in training recurrent neural networks improves their performancecited by 1
  4. 2025Concurrent Learning with Aggregated States via Randomized Least Squares Value Iterationcited by 0
  5. 2026End-to-End Efficient RL for Linear Bellman Complete MDPs with Deterministic Transitionscited by 0
  6. 2026Randomized Least Squares Value Iteration itself is Joint Differentially Privatecited by 0
  7. 2026Mathematical methods of reinforcement learningcited by 0