Frequentist Regret Bounds for Randomized Least-Squares Value Iteration

Abstract

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

Minor bug fixes

References in corpus (10)

• Further Optimal Regret Bounds for Thompson Sampling
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• Learning Near Optimal Policies with Low Inherent Bellman Error
• Online Regret Bounds for Undiscounted Continuous Reinforcement Learning
• Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?
• Sample-Optimal Parametric Q-Learning Using Linearly Additive Features
• Comments on the Du-Kakade-Wang-Yang Lower Bounds
• Learning with Good Feature Representations in Bandits and in RL with a Generative Model
• Worst-Case Regret Bounds for Exploration via Randomized Value Functions

Cited by in corpus (3)

• Logarithmic Regret for Reinforcement Learning with Linear Function Approximation
• Provably Efficient Reinforcement Learning with Aggregated States
• Adaptive Approximate Policy Iteration