Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP

Abstract

This paper presents new \emph{variance-aware} confidence sets for linear bandits and linear mixture Markov Decision Processes (MDPs). With the new confidence sets, we obtain the follow regret bounds: For linear bandits, we obtain an $\tilde{O}(poly(d)\sqrt{1+{\sum }_{k=1}^K{\sigma }_k^2})$ data-dependent regret bound, where $d$ is the feature dimension, $K$ is the number of rounds, and ${\sigma }_k^2$ is the \emph{unknown} variance of the reward at the $k$-th round. This is the first regret bound that only scales with the variance and the dimension but \emph{no explicit polynomial dependency on $K$}. When variances are small, this bound can be significantly smaller than the $\tilde{\Theta }\left(d\sqrt{K}\right)$ worst-case regret bound. For linear mixture MDPs, we obtain an $\tilde{O}(poly(d,\log H)\sqrt{K})$ regret bound, where $d$ is the number of base models, $K$ is the number of episodes, and $H$ is the planning horizon. This is the first regret bound that only scales \emph{logarithmically} with $H$ in the reinforcement learning with linear function approximation setting, thus \emph{exponentially improving} existing results, and resolving an open problem in \citep{zhou2020nearly}. We develop three technical ideas that may be of independent interest: 1) applications of the peeling technique to both the input norm and the variance magnitude, 2) a recursion-based estimator for the variance, and 3) a new convex potential lemma that generalizes the seminal elliptical potential lemma.

arXiv comment31 pages

References in corpus (23)

• Empirical Bernstein Bounds and Sample Variance Penalization
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs
• Learning Near Optimal Policies with Low Inherent Bellman Error
• Model-based RL in Contextual Decision Processes: PAC bounds and Exponential Improvements over Model-free Approaches
• Optimism in Reinforcement Learning with Generalized Linear Function Approximation
• Provably efficient RL with Rich Observations via Latent State Decoding
• Provably Efficient $Q$-learning with Function Approximation via Distribution Shift Error Checking Oracle
• Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon
• Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms
• Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping
• Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?
• Logarithmic Regret for Reinforcement Learning with Linear Function Approximation
• Bilinear Classes: A Structural Framework for Provable Generalization in RL
• Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functions
• Improved Optimistic Algorithms for Logistic Bandits
• On Oracle-Efficient PAC RL with Rich Observations
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity
• Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learning
• UCB Momentum Q-learning: Correcting the bias without forgetting
• Efficient Planning in Large MDPs with Weak Linear Function Approximation
• Tight Regret Bounds for Infinite-armed Linear Contextual Bandits