Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon

Episodic reinforcement learning and contextual bandits are two widely studied\nsequential decision-making problems. Episodic reinforcement learning\ngeneralizes contextual bandits and is often perceived to be more difficult due\nto long planning horizon and unknown state-dependent transitions. The current\npaper shows that the long planning horizon and the unknown state-dependent\ntransitions (at most) pose little additional difficulty on sample complexity.\n We consider the episodic reinforcement learning with $S$ states, $A$ actions,\nplanning horizon $H$, total reward bounded by $1$, and the agent plays for $K$\nepisodes. We propose a new algorithm, \\textbf{M}onotonic \\textbf{V}alue\n\\textbf{P}ropagation (MVP), which relies on a new Bernstein-type bonus.\nCompared to existing bonus constructions, the new bonus is tighter since it is\nbased on a well-designed monotonic value function. In particular, the\n\\emph{constants} in the bonus should be subtly setting to ensure optimism and\nmonotonicity.\n We show MVP enjoys an $O\\left(\\left(\\sqrt{SAK} + S^2A\\right) \\poly\\log\n\\left(SAHK\\right)\\right)$ regret, approaching the\n$\\Omega\\left(\\sqrt{SAK}\\right)$ lower bound of \\emph{contextual bandits} up to\nlogarithmic terms. Notably, this result 1) \\emph{exponentially} improves the\nstate-of-the-art polynomial-time algorithms by Dann et al. [2019] and Zanette\net al. [2019] in terms of the dependency on $H$, and 2) \\emph{exponentially}\nimproves the running time in [Wang et al. 2020] and significantly improves the\ndependency on $S$, $A$ and $K$ in sample complexity.\n