Achieving Constant Regret in Linear Markov Decision Processes
This provides a theoretical breakthrough for RL practitioners by enabling finite regret guarantees in infinite-horizon settings without prior distribution assumptions.
The paper tackles the problem of achieving constant regret in reinforcement learning for linear Markov decision processes with misspecification, introducing the Cert-LSVI-UCB algorithm that attains a cumulative regret of \tilde{\mathcal{O}}(d^3H^5/Δ) independent of the number of episodes, provided the misspecification level is below \tilde{\mathcal{O}}(Δ/(√dH^2)).
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 $ζ$. At the core of Cert-LSVI-UCB is an innovative \method, 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 a linear MDP characterized by a minimal suboptimality gap $Δ$, Cert-LSVI-UCB has a cumulative regret of $\tilde{\mathcal{O}}(d^3H^5/Δ)$ with high probability, provided that the misspecification level $ζ$ is below $\tilde{\mathcal{O}}(Δ/ (\sqrt{d}H^2))$. Here $d$ is the dimension of the feature space and $H$ is the horizon. Remarkably, this regret bound is independent of 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 without relying on prior distribution assumptions.