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

2020/10/23 by Priyank Agrawal, Agrawal, Priyank, Jing‐Lin Chen +4 · 3 citations
Computer Science · Decision Sciences · Mathematics · #Advanced Bandit Algorithms Research #Adversarial Robustness in Machine Learning #Applied mathematics #Artificial intelligence #Clipping (morphology) #Combinatorics #Computer science #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Markov decision process #Markov process #Mathematical optimization #Mathematics #Regret #Reinforcement Learning in Robotics #Reinforcement learning #Statistics #Value (mathematics) #cs.LG #stat.ML

paper · pdf · doi:10.48550/arxiv.2010.12163

Updated version, bug fixed

openalex publication_date 2020/10/23 · arxiv created 2021/11/09 · arxiv updated 2021/11/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

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 O(H²S√(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.

Cited by

• Provably Efficient and Agile Randomized Q-Learning
• Q-learning with Posterior Sampling
• Mathematical methods of reinforcement learning

Related

• Frequentist Regret Bounds for Randomized Least-Squares Value Iteration
• Worst-Case Regret Bounds for Exploration via Randomized Value Functions
• Posterior sampling for reinforcement learning: worst-case regret bounds
• Near-Optimal Randomized Exploration for Tabular Markov Decision Processes
• Achieving Constant Regret in Linear Markov Decision Processes