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

arXiv: https://arxiv.org/abs/2010.12163 · HTML: https://mlsanity.com/paper/2010.12163/

## Key facts

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

## Built on by (most cited first, 19 of 19)

- [Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learning](https://mlsanity.com/paper/2110.00871/) (2021)
- [Randomized Exploration for Reinforcement Learning with General Value Function Approximation](https://mlsanity.com/paper/2106.07841/) (2021)
- [A Provably Efficient Model-Free Posterior Sampling Method for Episodic Reinforcement Learning](https://mlsanity.com/paper/2208.10904/) (2022)
- [Towards Deployment-Efficient Reinforcement Learning: Lower Bound and Optimality](https://mlsanity.com/paper/2202.06450/) (2022)
- [A Self-Play Posterior Sampling Algorithm for Zero-Sum Markov Games](https://mlsanity.com/paper/2210.01907/) (2022)
- [Near-Optimal Randomized Exploration for Tabular Markov Decision Processes](https://mlsanity.com/paper/2102.09703/) (2021)
- [Exponential Family Model-Based Reinforcement Learning via Score Matching](https://mlsanity.com/paper/2112.14195/) (2021)
- [Computationally Efficient RL under Linear Bellman Completeness for Deterministic Dynamics](https://mlsanity.com/paper/2406.11810/) (2024)
- [Posterior Sampling with Delayed Feedback for Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2310.18919/) (2023)
- [Provably Efficient and Agile Randomized Q-Learning](https://mlsanity.com/paper/2506.24005/) (2025)
- [Reinforcement Learning for Markovian Bandits: Is Posterior Sampling more Scalable than Optimism?](https://mlsanity.com/paper/2106.08771/) (2021)
- [Dyadic Reinforcement Learning](https://mlsanity.com/paper/2308.07843/) (2023)
- [Near-Optimal Reinforcement Learning with Shuffle Differential Privacy](https://mlsanity.com/paper/2411.11647/) (2024)
- [Q-learning with Posterior Sampling](https://mlsanity.com/paper/2506.00917/) (2025)
- [Tuning the burn-in phase in training recurrent neural networks improves their performance](https://mlsanity.com/paper/2602.10911/) (2026)
- [Concurrent Learning with Aggregated States via Randomized Least Squares Value Iteration](https://mlsanity.com/paper/2501.13394/) (2025)
- [End-to-End Efficient RL for Linear Bellman Complete MDPs with Deterministic Transitions](https://mlsanity.com/paper/2603.23461/) (2026)
- [Randomized Least Squares Value Iteration itself is Joint Differentially Private](https://mlsanity.com/paper/2606.01952/) (2026)
- [Mathematical methods of reinforcement learning](https://mlsanity.com/paper/2607.06935/) (2026)

## 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.