本文提供了一种算法，用于在未知的弱交流 Markov 决策过程（MDP）中实现最佳的后悔率。该算法通过利用最优偏差向量跨度的正则化，在每个周期中选择一个策略。对于具有 S 个状态和 A 个动作的 MDP，其最优偏差向量的跨度受到 H 的限制，我们显示出～O (HSpAT) 的后悔界限。我们还将其跨度与 MDP 相关的各种直径类似的量联系起来，证明了我们的结果如何改善先前的后悔限制。

May, 2012

本研究提出了一种基于方差置信区间的简单算法 UCRL-V，能够有效降低在未知有限通信 MDP 中的最优遗憾，并在多种环境下的实验证明 UCRL-V 算法优于现有算法。

May, 2019

该研究探讨了马尔可夫决策过程中的无标度学习问题，提出了一个通用的算法框架（SCB），并在对抗性多臂赌博机和对抗性马尔可夫决策过程中应用该框架，从而实现了无标度对抗性多臂赌博机的首个鲁棒（最小化）期望遗憾上界和首个高概率遗憾上界，并产生了第一个具有 $\tilde {\mathcal {O}}(\sqrt {T})$ 高概率遗憾保证的无标度强化学习算法。

Mar, 2024

我们研究了对所有政策类 Pi 进行不可知 PAC 强化学习问题：在与一个未知的具有潜在庞大状态和动作空间的 MDP 交互的情况下，需要多少轮才能学习到相对于 Pi 的 epsilon - 次优政策？为此，我们引入了一种新的复杂性度量，称为生成能力，它仅依赖于政策类 Pi 而与 MDP 动力学无关。通过一个生成模型，我们证明了对于任何政策类 Pi，有界的生成能力表征了 PAC 可学习性。然而，对于在线 RL 来说，情况要复杂些。我们展示了存在一个具有有界生成能力的政策类 Pi，需要超多项式数量的样本来进行学习。这揭示了在生成访问和在线访问模型之间（以及在线访问下的确定性 / 随机 MDPs 之间）对于不可知学习能力的令人惊讶的区别。在积极方面，我们确定了一种额外的向日葵结构，它与有界生成能力一起，通过一种名为 POPLER 的新算法实现了统计高效的在线 RL，该算法借鉴了经典的重要性采样方法以及无奖励探索中可达状态识别和政策评估技术。

Oct, 2023

该论文介绍了一种新算法 TUCRL，它能够在任何有限马尔可夫决策过程 (MDP) 中进行高效的勘探和利用，而不需要任何形式的先前知识。该算法不同于乐观算法和正则算法，以及后验抽样或分段算法在弱通信 MDP 中的低效表现。最后，数值模拟支持了该论文的理论发现，并显示了 TUCRL 如何克服现有技术的限制。

Jul, 2018

研究了基于有限状态和行动空间的强化学习问题，探讨了如何最小化次优（状态、行动）对的探索率。得出特定于问题的遗憾下限，并提出一种新的学习算法 DEL （Directed Exploration Learning），让算法的性能达到遗憾下限，且对于 Lipschitz 连续性的 MDP，简化版 DEL 算法仍能高效利用其结构。

Jun, 2018

分析了应用 Empirical Bernstein 不等式的 UCRL2 算法在探索和开发问题上的应用，结果表明在通信 Markov 决策过程中，UCRL2B 算法的损失被限制在 $\widetilde {O}(\sqrt {D\Gamma SAT})$。

Jul, 2020

我们提出了一种新的遗憾最小化算法，用于具有稀疏线性马尔可夫决策过程（SMDP）的情节性问题，其中状态转移分布是观察特征的线性函数。

Oct, 2023

基于 “面对不确定性的乐观原则” 的算法，使用有限状态 - 动作空间的、用马尔可夫决策过程（MDP）建模的强化学习（RL）有效学习。通过评估最佳偏置函数 $h^{*}$ 的状态对差异，该算法在已知 $sp (h^{*})$ 的情况下实现 MDP 的遗憾界为 $\tilde {O}(\sqrt {SAHT})$，这个结果超过了先前的最佳遗憾界 $\tilde {O}(S\sqrt {AHT})$，并且匹配了遗憾下界。此外，对于有限直径 $D$ 的 MDP，我们证明了 $ ilde {O}(\sqrt {SADT})$ 接近于最佳遗憾上界。

Jun, 2019

这篇论文介绍了一种具有最小最大后悔度的可行算法，该算法通过使用一种新颖的子程序，即 Projected Mitigated Extended Value Iteration（PMEVI），来高效地计算偏差受限最优策略。同时，该算法不需要先前关于偏差函数的信息。

Jun, 2024