Settling Constant Regrets in Linear Markov Decision Processes
Weitong Zhang Zhiyuan Fan Jiafan He Quanquan Gu
We study the constant regret guarantees in reinforcement learning (RL). Our
objective is to design an algorithm that incurs only finite regret over
infinite episodes with high probability. We introduce an algorithm,
Cert-LSVI-UCB, for misspecified linear Markov decision processes (MDPs) where
both the transition kernel and the reward function can be approximated by some
linear function up to misspecification level $\zeta$. At the core of
Cert-LSVI-UCB is an innovative certified estimator, which facilitates a
fine-grained concentration analysis for multi-phase value-targeted regression,
enabling us to establish an instance-dependent regret bound that is constant
w.r.t. the number of episodes. Specifically, we demonstrate that for an MDP
characterized by a minimal suboptimality gap $\Delta$, Cert-LSVI-UCB has a
cumulative regret of $\tilde{\mathcal{O}}(d^3H^5/\Delta)$ with high
probability, provided that the misspecification level $\zeta$ is below
$\tilde{\mathcal{O}}(\Delta / (\sqrt{d}H^2))$. Remarkably, this regret bound
remains constant relative to the number of episodes $K$. To the best of our
knowledge, Cert-LSVI-UCB is the first algorithm to achieve a constant,
instance-dependent, high-probability regret bound in RL with linear function
approximation for infinite runs without relying on prior distribution
assumptions. This not only highlights the robustness of Cert-LSVI-UCB to model
misspecification but also introduces novel algorithmic designs and analytical
techniques of independent interest.