Oct, 2021

通过根对数正则化实现Minimax最优分位数和半对抗性遗憾

HTML
PDF
TL;DR利用FTRL算法具有不同的正则化器降低Quantile和KL regret bounds，与 NormalHedge 和其变体相比，成功完成对抗数据中对大多数专家而不是最佳专家进行竞争，并在半对抗范式中使用自适应最小值的算法来适应真实、未知的约束条件，导致了统一改进的regret上限。
发现论文，激发创造
  • 通过极小极大对偶视角看最优遗憾的随机观点

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

    Mar, 2009

  • 将对抗保证与随机快速率结合应用于在线学习

    本研究考虑在线学习算法在对抗环境中可以保证最坏情况下的后悔率，而在有利的随机环境下能够自适应地表现良好，并通过Bernstein条件量化随机环境的友好程度，证明了两种最近的算法自适应于随机环境的Bernstein参数，并证明这些算法在其各自的环境中都具有快速的期望和高概率率。

    May, 2016

  • 对抗性赌博机的改进下界

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

    May, 2016

  • 带部分信息的在线学习小损失界

    研究了拥有部分信息反馈的对抗(非随机)在线学习问题，在黑盒模型下能够获得如上小损失的概率，而其独特的设计使它在更多应用如半强盗问题和上下文强盗问题中得到有效的应用，并且能够提供一些之前无法获得的最优保证。

    Nov, 2017

  • 更多适应性算法用于对抗式赌博机

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

    Jan, 2018

  • 在随机和对抗半臂匪中的最优解决方案

    开发出新的半强化学习算法，不需要先验信息，可同时在随机环境和对抗环境下获得对数级和平方级的遗憾，并通过在合成数据上的实验证明了其性能的一致性和优越性。

    Jan, 2019

  • 针对零阶对抗性Bandit凸优化的改进遗憾

    以信息论为基础，改进探索性分布以在零阶对抗性bandit凸优化的minimax regret的信息理论上界上证明其为O(d^{2.5} 根号n 对数(n))，并提高Bubeck等人(2017)的O(d^{9.5}根号n 对数(n)^{7.5}上界。

    May, 2020

  • 除去偏见：针对对抗性赌博机和MDPs的高概率数据依赖性遗憾边界

    发展了一种新的方法，使用标准无偏估计量，并依赖于简单的递增的学习速率表和对数单调自协调障碍以及加强的弗里德曼不等式，以获取高概率遗憾边界。

    Jun, 2020

  • 医生对口罩使用的结论：有用但需辩证看待

    本研究提出了一种广义的最好结果算法以及如何通过规范化导向跟随和在线镜像下降算法实现在线学习中的最好结果，将这种算法应用于上下文、图和表马尔科夫决策过程中。

    Feb, 2023

  • 基于混合正则化的优化探索: 针对偏向监控的对数遗憾与对抗鲁棒性

    通过优化的探索，局部监控问题的新型逼近算法提供了在随机和对抗环境中近乎最佳的悔恨界限。

    Feb, 2024