Settling Constant Regrets in Linear Markov Decision Processes

arXiv:2404.10745v1 Announce Type: new
Abstract: 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 …

abstract algorithm arxiv cs.lg decision design episodes kernel linear markov probability processes reinforcement reinforcement learning study transition type