Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function

Abstract

We present an algorithm based on the \emph{Optimism in the Face of Uncertainty} (OFU) principle which is able to learn Reinforcement Learning (RL) modeled by Markov decision process (MDP) with finite state-action space efficiently. By evaluating the state-pair difference of the optimal bias function $h^{\ast }$, the proposed algorithm achieves a regret bound of $\tilde{O}(\sqrt{SAHT})$\footnote{The symbol $\tilde{O}$ means $O$ with log factors ignored. } for MDP with $S$ states and $A$ actions, in the case that an upper bound $H$ on the span of $h^{\ast }$, i.e., $sp(h^{\ast })$ is known. This result outperforms the best previous regret bounds $\tilde{O}(S\sqrt{AHT})$\citep{fruit2019improved} by a factor of $\sqrt{S}$. Furthermore, this regret bound matches the lower bound of $\Omega (\sqrt{SAHT})$\citep{jaksch2010near} up to a logarithmic factor. As a consequence, we show that there is a near optimal regret bound of $\tilde{O}(\sqrt{SADT})$ for MDPs with a finite diameter $D$ compared to the lower bound of $\Omega (\sqrt{SADT})$\citep{jaksch2010near}.

References in corpus (2)

• REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs
• Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds

Cited by in corpus (4)

• Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition
• Near-optimal Optimistic Reinforcement Learning using Empirical Bernstein Inequalities
• A Model-free Learning Algorithm for Infinite-horizon Average-reward MDPs with Near-optimal Regret
• Efficient Reinforcement Learning in Factored MDPs with Application to Constrained RL