Sep, 2015

在线睡眠组合优化问题的难度

HTML
PDF
TL;DR我们研究了几个在线组合优化问题的睡眠设置版本，并证明其至少与PAC学习DNF表达式一样困难。我们证明了Online Shortest Paths问题的困难性结果，解决了COLT 2015提出的一个开放问题。
发现论文，激发创造
  • 具有马尔可夫奖励的组合多臂赌博机问题

    本文研究用多臂赌博机问题的方法，解决用户和资源之间的最佳匹配问题，采用马尔科夫链的状态演变，采用匹配学习算法实现。

    Dec, 2010

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

    本文研究了在线组合优化问题中的半盲反馈，提出了一种优化算法来减少期望后悔。该算法以L_T*的平方根为增长率，在部分反馈方案中首次实现了此类保证，并在组合设置中首次实现了此类保证。

    Feb, 2015

  • 高效使用近似算法的在线线性优化

    本文讨论在线线性优化问题，考虑可行操作集通过近似线性优化预言机具有α乘性逼近保证的情况，给出了新算法并提出了显著改进甚至多项式对数的预言机复杂度，同时得到了常数c>0的alpha遗憾界。

    Sep, 2017

  • 具公平约束的组合式睡眠赌博机

    提出针对多臂赌博机模型（MAB）的新型组合睡眠MAB模型。通过扩展在线学习算法UCB以处理利用和探索之间的权衡，同时采用虚拟队列技术来正确处理公平性约束。最终提出一种名为LFG的新算法，可保证可行性最优，具有受时间平均后悔上限约束的时间复杂度，并进行了广泛的模拟以证明其有效性。

    Jan, 2019

  • 在图上学习组合优化问题：一份调查及其在网络中的应用

    介绍了解决图上组合优化问题的现有方法存在的问题，调查了与计算复杂性相关的机器学习研究的发展，并组织和比较了解决组合优化问题的学习结构。

    May, 2020

  • Restless-UCB，在线不安定赌博机的高效低复杂度算法

    提出了一种名为Restless-UCB的在线学习策略来解决在线探索期望最大化问题，在Restless-UCB中，利用前期的探索来做出更好地决策，证明了期望最大化问题在合理的标准下得到了可行的上界，相较于现有算法，使用一种新的对于状态转移进行利用的方法来消除在泊松极限中出现的指数因子，同时也能用于优化现有算法。

    Nov, 2020

  • 在线斯坦纳树学习增强算法

    本文考虑了将机器学习与在线算法设计相结合的新型“超越最坏情况”算法分析模型在在线Steiner树问题上的应用，其中预测的终端节点可能不正确，算法性能取决于错误预测的数量，可以通过正确预测来突破在线下界并且具有良好的竞争比，同时实验证明该理论具有预测性。

    Dec, 2021

  • 利用不完美预测进行平滑的在线组合优化

    研究了具有预测模型的平滑在线组合优化问题，提出一种在线算法在规划窗口和开关代价之间实现平衡，通过对合成在线分布流问题进行实证，证明在累积规避中取得了显着的改进。

    Apr, 2022

  • 通过 Frank-Wolfe 的改进 Metarounding 算法

    通过使用metarounding算法，我们提出了一种将线性优化的近似算法转化为同一类别的在线线性优化算法的新方法，该算法在理论和实践方面都更加高效。

    Oct, 2023

  • 睡眠赌徒的近最佳每个动作的遗憾界

    我们使用广义版本的EXP3、EXP3-IX和FTRL与Tsallis熵直接最小化每次行动的遗憾，从而获得了接近最优的$ O(√{TAln⁡K})$和$ O(√{T√{AK}})$的界限，并将我们的结果推广到了从睡眠专家那里寻求建议的强盗情境，从而得到了一些现有自适应和跟踪遗憾上限的新证明，并通过推广我们的结果到专家报告信心的强盗版本，得到了主要依赖于专家信心之和的置信遗憾上限。

    Mar, 2024