Feb, 2015

组合半弦臂算法的一阶遗憾上界

PDF
TL;DR本文研究了在线组合优化问题中的半盲反馈，提出了一种优化算法来减少期望后悔。该算法以 L_T * 的平方根为增长率，在部分反馈方案中首次实现了此类保证，并在组合设置中首次实现了此类保证。
online combinatorial optimizationsemi-bandit feedbacklearning algorithmsexpected regretpartial-feedback scheme
发现论文，激发创造
  • 在线组合优化中的遗憾

    本文研究使用二进制向量表示决策者可能的选择时的在线线性优化问题及其反悔，探讨了决策者在不同反馈条件下的最优反悔幅度，并提出了一种使用镜像下降算法和隐式归一化预测策略的解决方案，获得了半强盗情形的最优界限，同时也证明了在线组合优化基准算法的次优性。

    Apr, 2012

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

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

    Nov, 2017

  • 组合赌博机与相对反馈

    本文围绕多项式逻辑选择模型，研究了在线学习中集合选择的组合优化问题及其相关算法，并通过实验验证了理论结果。

    Mar, 2019

  • 随机组合半赌博机的紧急遗憾上限

    本研究利用 UCB-like 算法解决计算和采样高效的随机组合半贝叶斯在线学习问题，并分析了其 $n$ 步遗憾的上界，这里的遗憾是指最优解和次优解之间的预期回报差距。

    Oct, 2014

  • 带有复合匿名反馈的非随机赌博机

    研究非随机赌博环境下的遗憾界，提出了基于 FTRL with Tsallis entropy 的算法转化方法。

    Dec, 2021

  • 面向具有悔恨的对抗性线性马尔可夫决策过程的最优化

    在线强化学习是研究的主题之一，尤其在线性 Markov 决策过程中使用了对抗性损失和强盗反馈，提出了两个算法以改善后悔性能。

    Oct, 2023

  • 具有 $\tilde {O}(\sqrt {T})$ 遗憾的高效在线贪心多分类学习

    我们提出了一种高效的二阶算法，用于处理带依赖的多分类问题，同时考虑了由 ETA 参数化的一系列损失函数与竞争者的范式限制。算法能够同时处理从铰链损失 (ETA=0) 到平方铰链损失 (ETA=1) 的这一系列损失函数，这解决了 Abernethy 和 Rakhlin 在 COLT 2009 中的一个开放性问题，并通过实验与早期算法得到了良好的效果。

    Feb, 2017

  • 具有切换成本的对抗组合赌博机

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

    Apr, 2024

  • 一种高效的半强化反馈学习算法

    研究在线组合优化问题下的半强化反馈，提出了一种结合 FPL 预测方法和新颖的损失估计程序（称为 Geometric Resampling）的学习算法，并且在能够进行高效离线组合优化的任何决策集合上可以有效实现。假设决策集合的元素可以用至多 m 个非零项的 d 维二进制向量来描述，证明了我们算法的期望遗憾在 T 轮后是 O (m sqrt (dT log d))，并且在全信息设置中也改进了 FPL 的最佳遗憾限制。

    May, 2013

  • 计数型赌博机的完整策略遗憾界

    研究了限制对手策略的措施，旨在实现最强版本的策略后悔，即完全策略后悔。提出概念式为 “计票老虎机” 的在线学习算法，并针对该算法提供了一种具有可接受保证的算法，证明了算法的近似最优性。

    Apr, 2022