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 { ε_mis, ε_tol }, where ε_mis is the degree of misspecification and ε_tol is a user-specified error tolerance. (P2) Its space and per-episode time complexities remain bounded as K → ∞. (P3) It does not require ε_mis as input. To our knowledge, this is the first algorithm satisfying all three properties. For concrete choices of ε_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.