在多臂赌博机领域，多智能体多臂赌博机方法已经受到了广泛关注，但对应的遗憾下界的研究相对较少。本文在不同情景下首次全面研究了遗憾下界，并证明了它们的紧密性。当图表现出良好的连通性和奖励是随机分布时，我们证明了实例相关上界的 O（log T）下界和平均差值独立上界的 sqrt（T）下界。在对抗奖励的假设下，我们建立了连接图的 O（T^（2/3））下界，从而弥合了以前工作中下界与上界之间的差距。当图表现为不连通时，我们还展示了线性的遗憾下界。与以前的研究相比，本文全面研究了这些情景下的紧密下界。

Aug, 2023

该研究针对连续状态空间中的无折扣强化学习问题，提出了一种结合状态聚合和使用置信上界实现面对不确定性乐观的算法，在 rewards 和 transition probabilities 保持 Holder 连续性的情况下，给出了子线性遗憾界。

Feb, 2013

该研究提供了敌对强盗算法必须遭受的遗憾的新的下界，并证明了对于最佳臂的总损失或损失的二次变化的上界是接近紧的。此外，研究还证明了两个不可能的结果，即单臂最优和遗憾不能随损失范围的提高而扩展。相比之下，在完全信息设置中这两个结果是可能的。

May, 2016

通过对经典多臂赌博机（Stochastic Multi-Armed Bandit）的研究，探讨了两种不同的准则下存在的遗憾下界。同时，研究了 UCB 等算法的变体，证明了这种情况下不可能设计一种自适应的策略来选择最优算法。

Dec, 2011

本文提出贝叶斯强化学习中近似最优的无记忆策略，用以计算相关效用较紧的下界， 使之得以应用于提高决策探索策略的鲁棒性。

Jun, 2011

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

Mar, 2017

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

May, 2019

任何强化学习算法的期望遗憾在无折扣回报情况下下界为 $\Omega\left (\sqrt {DXAT}\right)$，其中 $D$ 表示马尔科夫决策过程的直径，$X$ 表示状态空间的大小，$A$ 表示动作空间的大小，$T$ 表示时间步数。然而，这个下界是一般性的，考虑到问题结构的一些具体知识可以获得更小的遗憾。在本文中，我们考虑了一个具有 $m$ 个作业类和类依赖奖励和持有成本的 $M/M/c/S$ 队列的入场控制问题。排队系统的直径通常是缓冲区大小 $S$ 的指数级，这使得先前的下界在实际使用中变得困难。我们提出了一种受 UCRL2 启发的算法，并利用问题结构来上界有限服务器情况下的期望总遗憾为 $O (S\log T + \sqrt {mT \log T})$。在无限服务器情况下，我们证明了遗憾对 $S$ 的依赖性消失。

Jun, 2024

本研究基于鲁棒 Catoni 平均值估计器，提出一种新的鲁棒自归一化浓度界，解决了已有技术在大状态空间强化学习中无法获得遗憾上界的问题，并证明了在线性 MDP 设定下，可以获得与最优策略性能某种度量成比例的遗憾上界。

Dec, 2021

本文提出了一种自适应控制的方法，可用于处理 Linear Quadratic Regulator 中未知的线性系统和需求预测的问题，算法的时间复杂度为多项式级别，且在控制中有很好的保障。

May, 2018