通过 von Neumann 最小极大定理，我们研究了在线凸优化游戏的最优策略的遗憾。我们证明了，在这种对抗性环境中，最优策略的遗憾与随机进程设置中经验最小化算法的行为密切相关:它等于最小期望损失的总和与最小经验损失之间的差的最大值。我们展示了最优策略的遗憾具有自然的几何解释，因为它可以被视为一个上凸函数的 Jensen 不等式中的差距。利用此表达式，我们对各种在线学习问题的最优策略给出了上下界限制。我们的方法提供了无需构建学习算法的上界，而提供了对抗者的明确最优策略的下界。

Mar, 2009

该研究提出了在线线性优化问题的带有bandit反馈的算法，并使用Mirror Descent算法在特定案例中获得具有最小二乘优化后退限制的计算高效性的策略，证明了计算上以及最小二乘上的结果优化，为输出结果减少了冗余的符号。

Feb, 2012

本文研究的是带有动作切换代价的敌对多臂赌博机问题，证明了在该问题下玩家T回合的最小極大后悔度为~Θ(T^2/3)，并研究了其他在线学习领域的开放问题，结果得到了一个多尺度随机游走的新随机化结构，该结构对如此困难的学习问题证明可能会有所帮助。

Oct, 2013

提出了一种新颖的算法，采用乐观性和适应性技术，结合在线镜像下降框架和特殊的对数障碍正则化器来解决对抗性多臂赌博机问题和组合半赌博问题，并在提高先前工作的同时，取得了多种新的数据依赖性遗憾界。

Jan, 2018

本文提出了对抗性SSP模型，包含时间上对成本的不良变化和未知转移，其开发了第一个对抗性SSP算法，并证明了高概率的回报上限。

Jun, 2020

本文主要研究随机最短路径问题中的对手成本和未知转移，并提出了一种新的算法，可以在有限的次数内找到最优解，此外，我们还提出了一种新的算法，可以在特定情景下近似达到最优解。

Feb, 2021

本文研究了随机最短路问题，提出了一种基于有限阶段马尔科夫决策过程的新算法，其中最小化代理与模型之间的遗憾的上界可达到$ \widetilde O(\sqrt{ (B_\star^2 + B_\star) |S| |A| K})$。根据实验，该算法大幅改善了Rosenberg等人的遗憾上界，并且对于期望成本小于1的情况，提出了一种完全匹配的下界。

Mar, 2021

本文旨在解决随机最短路径问题中的学习问题，并设计了一种名为EB-SSP的基于模型的算法。该算法通过探索奖励来诱导一个乐观的SSP问题，其值迭代方案已被证明会收敛，并获得与下限之间的效果。同时，该算法在不使用任何先前知识的情况下获得最小化后悔率，并在如正成本或一般成本等各种情况下均有所改善。

Apr, 2021

通过分析具有切换成本的对抗组合赌博问题，本论文推导了极小后悔的下界并设计了相应算法，同时考虑了赌博反馈和半赌博反馈两种情况。

Apr, 2024

本研究解决了低秩马尔可夫决策过程中的遗憾最小化问题，聚焦于未知转移的全信息损失反馈和带宽损失反馈的设置。论文提出改进的算法，使得在全信息未知转移情况下的遗憾界限达到$poly(d, A, H)T^{2/3}$，并首次探讨了在带宽损失反馈与未知转移的条件下的算法，揭示线性结构对带宽情况下的必要性，对比全信息情况下的不同表现。

Nov, 2024