Improved Algorithms for Misspecified Linear Markov Decision Processes

Abstract

For the misspecified linear Markov decision process (MLMDP) model of Jin et al. [2020], we propose an algorithm with three desirable properties. (P1) Its regret after $K$ episodes scales as $K\max \{{\epsilon }_{\text{mis}},{\epsilon }_{\text{tol}}\}$, where ${\epsilon }_{\text{mis}}$ is the degree of misspecification and ${\epsilon }_{\text{tol}}$ is a user-specified error tolerance. (P2) Its space and per-episode time complexities remain bounded as $K\to \infty$. (P3) It does not require ${\epsilon }_{\text{mis}}$ as input. To our knowledge, this is the first algorithm satisfying all three properties. For concrete choices of ${\epsilon }_{\text{tol}}$, we also improve existing regret bounds (up to log factors) while achieving either (P2) or (P3) (existing algorithms satisfy neither). At a high level, our algorithm generalizes (to MLMDPs) and refines the Sup-Lin-UCB algorithm, which Takemura et al. [2021] recently showed satisfies (P3) for contextual bandits. We also provide an intuitive interpretation of their result, which informs the design of our algorithm.

This version adds an intuitive explanation in Section 3

References in corpus (11)

• Model-Based Reinforcement Learning with Value-Targeted Regression
• Optimism in Reinforcement Learning with Generalized Linear Function Approximation
• Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces
• Regret Bound Balancing and Elimination for Model Selection in Bandits and RL
• Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration
• Provably Efficient Reinforcement Learning with Aggregated States
• Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model
• Low-rank Bandits with Latent Mixtures
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation
• Efficient Local Planning with Linear Function Approximation