Abstract
We study the constant regret guarantees in reinforcement learning (RL). Ourobjective is to design an algorithm that incurs only finite regret overinfinite episodes with high probability. We introduce an algorithm,Cert-LSVI-UCB, for misspecified linear Markov decision processes (MDPs) whereboth the transition kernel and the reward function can be approximated by somelinear function up to misspecification level $\zeta$. At the core ofCert-LSVI-UCB is an innovative certified estimator, which facilitates afine-grained concentration analysis for multi-phase value-targeted regression,enabling us to establish an instance-dependent regret bound that is constantw.r.t. the number of episodes. Specifically, we demonstrate that for an MDPcharacterized by a minimal suboptimality gap $\Delta$, Cert-LSVI-UCB has acumulative regret of $\tilde{\mathcal{O}}(d^3H^5/\Delta)$ with highprobability, provided that the misspecification level $\zeta$ is below$\tilde{\mathcal{O}}(\Delta / (\sqrt{d}H^2))$. Remarkably, this regret boundremains constant relative to the number of episodes $K$. To the best of ourknowledge, Cert-LSVI-UCB is the first algorithm to achieve a constant,instance-dependent, high-probability regret bound in RL with linear functionapproximation for infinite runs without relying on prior distributionassumptions. This not only highlights the robustness of Cert-LSVI-UCB to modelmisspecification but also introduces novel algorithmic designs and analyticaltechniques of independent interest.