This paper presents the first non-asymptotic result showing that a model-free
algorithm can achieve a logarithmic cumulative regret for episodic tabular
reinforcement learning if there exists a strictly positive sub-optimality gap
in the optimal $Q$-function. We prove that the optimistic $Q$-learning studied
in [Jin et al. 2018] enjoys a ${\mathcal{O}}\left(\frac{SA\cdot
\mathrm{poly}\left(H\right)}{\Delta_{\min}}\log\left(SAT\right)\right)$
cumulative regret bound, where $S$ is the number of states, $A$ is the number
of actions, $H$ is the planning horizon, $T$ is the total number of steps, and
$\Delta_{\min}$ is the minimum sub-optimality gap. This bound matches the
information theoretical lower bound in terms of $S,A,T$ up to a
$\log\left(SA\right)$ factor. We further extend our analysis to the discounted
setting and obtain a similar logarithmic cumulative regret bound.

该论文展示了第一个非渐近结果，证明了如果最优 $Q$- 函数存在严格正的次优性差，则无模型算法可以实现每段落的表格强化学习的对数累积后悔，并且我们将我们的分析扩展到折扣设置，并获得类似的对数累积后悔界限。