本文研究了在线组合优化问题中的半盲反馈,提出了一种优化算法来减少期望后悔。该算法以 L_T * 的平方根为增长率,在部分反馈方案中首次实现了此类保证,并在组合设置中首次实现了此类保证。
Feb, 2015
该论文提出了当对手可以适应在线算法的动作时,标准遗憾定义变得不再有效,定义了替代的政策遗憾概念,用于测量在线算法在适应性对手下的性能,并研究了在线赌徒问题的情况,表明任何赌徒算法都无法针对带有无界内存的适应性对手保证次线性的政策遗憾,但同时提出了将标准遗憾限制在次线性边界以下的任何赌徒算法转换为政策遗憾限制在次线性边界以下的算法的一般技术, 并将这一结果扩展到其他遗憾变体。
Jun, 2012
研究了一个权重计数的赌博算法,其中动作损失与最近 $m$ 个时间步骤中该动作被播放的次数的加权求和有关,并引入了 “重复暴露最优性” 的条件来最小化完备策略遗憾,提出了简单的修改后的连续消除算法,并对其进行了理论和实验分析。
May, 2023
在多臂赌博机领域,多智能体多臂赌博机方法已经受到了广泛关注,但对应的遗憾下界的研究相对较少。本文在不同情景下首次全面研究了遗憾下界,并证明了它们的紧密性。当图表现出良好的连通性和奖励是随机分布时,我们证明了实例相关上界的 O(log T)下界和平均差值独立上界的 sqrt(T)下界。在对抗奖励的假设下,我们建立了连接图的 O(T^(2/3))下界,从而弥合了以前工作中下界与上界之间的差距。当图表现为不连通时,我们还展示了线性的遗憾下界。与以前的研究相比,本文全面研究了这些情景下的紧密下界。
Aug, 2023
研究非随机赌博环境下的遗憾界,提出了基于 FTRL with Tsallis entropy 的算法转化方法。
Dec, 2021
本文介绍了一种算法来解决不安分的马尔科夫赌臂问题,并证明了基于指数的策略在这个问题中一定是次优的。该算法可以在不需要假设马尔可夫链除了不可约的任何情况下,经过 T 步后实现相对于知道所有赌臂分布的最佳策略的 O (√T) 的悔恨。
Sep, 2012
这篇论文研究了流式赌博机问题,建立了时间上界、臂数、游戏轮数的算法紧确的最劣后悔下限,并证明了与分析算法复杂度上限的样本复杂性分析问题的关系。
Jun, 2023
在线强化学习是研究的主题之一,尤其在线性 Markov 决策过程中使用了对抗性损失和强盗反馈,提出了两个算法以改善后悔性能。
Oct, 2023
研究了随机多臂赌博问题中期望值和尾部风险之间的权衡,提出了一种新的策略以实现任何遗憾阈值的最优遗憾尾部概率,该策略在最坏情况下和实例相关情况下分别实现了 $\alpha$- 最优和 $\beta$- 一致,探究了最差情况和实例相关情况下的遗憾期望和遗憾尾部风险之间的权衡,同时表明在知道规划时间范围时,尾部风险可以降低。
Apr, 2023
我们使用广义版本的 EXP3、EXP3-IX 和 FTRL 与 Tsallis 熵直接最小化每次行动的遗憾,从而获得了接近最优的 $ O (√{TAlnK})$ 和 $ O (√{T√{AK}})$ 的界限,并将我们的结果推广到了从睡眠专家那里寻求建议的强盗情境,从而得到了一些现有自适应和跟踪遗憾上限的新证明,并通过推广我们的结果到专家报告信心的强盗版本,得到了主要依赖于专家信心之和的置信遗憾上限。
Mar, 2024