conftrace_

2021 AAAI AAAI 2021

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

Abstract

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 $\tilde{\mathrm{O}}(H^2S\sqrt{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.

🌉 Interdisciplinary Bridge - Artificial Intelligence and Reinforcement Learning

Authors

Priyank Agrawal, Jinglin Chen, Nan Jiang

Topics

Machine Learning > Optimization & Theory > Learning Theory Reinforcement Learning > Methods > Deep RL Machine Learning > Learning Types > Reinforcement Learning Machine Learning > Optimization & Theory > Stochastic Methods Machine Learning > Learning Types > Exploration

Keywords

reinforcement learning markov decision process value iteration thompson sampling regret bound worst-case regret randomized value function randomized least-squares value iteration tabular rl

More from AAAI 2021

All AAAI 2021 papers →

Testing Independence Between Linear Combinations for Causal Discovery

SWIFT: Scalable Wasserstein Factorization for Sparse Nonnegative Tensors

DART: Adaptive Accept Reject Algorithm for Non-Linear Combinatorial Bandits

Semi-supervised Sequence Classification through Change Point Detection

Learning Invariant Representations using Inverse Contrastive Loss

Learned Bi-Resolution Image Coding using Generalized Octave Convolutions