We consider the problem of efficient exploration in finite horizon MDPs.We show that an optimistic modification to model-based value iteration, can achieve a regret bound $\tilde{O}( \sqrt{HSAT} + H^2S^2A+H\sqrt{T})$ where $H$ is the time horizon, $S$ the number of states, $A$ the number of actions and $T$ the time elapsed. This result improves over the best previous known bound $\tilde{O}(HS \sqrt{AT})$ achieved by the UCRL2 algorithm.The key significance of our new results is that when $T\geq H^3S^3A$ and $SA\geq H$, it leads to a regret of $\tilde{O}(\sqrt{HSAT})$ that matches the established lower bounds of $\Omega(\sqrt{HSAT})$ up to a logarithmic factor. Our analysis contain two key insights. We use careful application of concentration inequalities to the optimal value function as a whole, rather than to the transitions probabilities (to improve scaling in $S$), and we use "exploration bonuses" based on Bernstein's inequality, together with using a recursive -Bellman-type- Law of Total Variance (to improve scaling in $H$).

本文研究了有限时间MDPs中探索的最优性问题，提出了一种基于值迭代的乐观算法，其探索奖励基于下一个状态的经验值的变化量，通过使用集中不等式提高算法的可伸缩性，取得了优于先前最佳算法的研究成果，可以实现与已知理论下限相匹配的后悔度。

强化学习的极小后悔界