Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function

By Zihan Zhang, Xiangyang Ji. 2019

80 citations recorded by the source corpus.

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^{*}$, 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^{*}$, i.e., $sp(h^{*})$ 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}.

Subfields: Artificial Intelligence, Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Reinforcement Learning

Citations in the corpus

Dueling RL: Reinforcement Learning with Trajectory Preferences (2021, background): “, 2020a; Lattimore and Hutter, 2012) and minimizing regret via balancing exploration and exploitation (Zhang and Ji, 2019; Azar et al., 2017; Ortner, 2020; Talebi and Maillard, 2018; Efroni et al., 2020; Domingues et al., 2020b).”
Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition (2020, methodology): “For the tabular setting, there are plenty of recent works on model-based algorithms under various settings (e.g., [Jaksch et al., 2010, Agrawal and Jia, 2017, Azar et al., 2017, Ouyang et al., 2017, Fruit et al., 2019, Simchowitz and Jamieson, 2019, Zanette and Brunskill, 2019, Zhang and Ji, 2019]).”
Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism (2020, methodology): “The minimax optimal algorithm is provided in (Zhang & Ji, 2019) although it is not computationally efﬁcient.”