我们研究了表格设置下折扣马尔可夫决策过程（MDP）的强化学习问题。我们提出了一种基于模型的算法UCBVI-γ，该算法基于面对不确定性的乐观原则和伯恩斯坦型奖金。我们表明UCBVI-γ√ 卫星/（1− γ） 1.5遗憾，其中S是状态数，A是动作数，γ是折扣因子，T是步骤数。此外，我们构造了一类硬MDP，并表明对于任何算法，预期的遗憾至少是Ωe√ 卫星/（1− γ） 1.5.我们的上界与对数因子的极大极小下界相匹配，这表明UCBVI-γ几乎是折扣MDP的极大极小最优值。
强化学习（RL）的目标是设计算法，通过与未知动态环境的交互来学习最优策略。马尔可夫决策过程（MDP）由于其描述与时间无关的状态转移特性的能力，在强化学习中起着核心作用。更具体地说，折扣MDP是强化学习中的标准MDP之一，用于描述连续任务而不中断或重启。对于折扣MDP，使用生成模型[12]，已经提出了几种具有接近最优样本复杂度的算法。更具体地说，Azar等人[3]提出了一种经验QVI算法，该算法实现了最佳样本复杂度，以找到最佳值函数。Sidford等人[22]提出了一种次线性随机化值迭代算法，该算法实现了接近最优的样本复杂度，以找到最优策略，Sidfordd等人[23]进一步改进了该算法，以达到最优样本复杂度。由于生成模型是一个强大的预言机，它允许算法查询任何状态-动作对的奖励函数和下一个状态，因此很自然地会询问是否存在实现最优的在线RL算法（没有生成模型）。
