Jun, 2023

反馈图网络在线学习：损失函数的真实形态

PDF
TL;DR本论文主要介绍了一种基于反馈图的顺序学习问题，提出了一个名为 problem complexity 的新概念，并创建了一个既定算法，实现了对此设置的最小化失望度量的最优解。
sequential learningfeedback graphsminimax regret rateproblem complexityexploration strategy
发现论文，激发创造
  • 反馈图的在线学习：超越赌博机

    研究在线学习问题中的反馈问题，证明反馈图的结构控制引起的学习难度，并给出了三个类别的反馈图的理论极限表现和影响。

    Feb, 2015

  • 关于具备反馈图的在线学习的最小化后悔算法

    本文针对具有强可观测无向反馈图的在线学习问题，在回报上下界方面进行了改进，并使用 FTRL 与 q-Tsallis 熵对结果进行了证明；同时扩展了该技术应用于时间变化图的情形，并提供了适用于所有 alpha>1 的改良下界。

    May, 2023

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

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

    Nov, 2017

  • 了解反馈在在线学习中转换成本中的作用

    本文主要研究反馈在在线学习中的作用以及它对遗憾的影响，特别是在 bandit 学习中，我们充分表征了不同反馈类型下的 minimax 遗憾，并设计了算法框架以实现匹配上限。

    Jun, 2023

  • 具有图结构反馈的非随机多臂赌博机

    本文研究了一种名为 “部分信息” 的在线学习模型，提出了多种算法，通过信息反馈结构的组合特性，给出了紧密的遗憾界限。

    Sep, 2014

  • 未知序贯决策问题和游戏的无模型在线学习

    提出了一种适用于黑盒环境的极限情况的后悔最小化算法，通过以前保证仅实现的限制来实现亚线性的后悔率，并将其应用于逼近 Nash 均衡，学习最佳反应以及安全的对手利用等问题。

    Mar, 2021

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

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

    Feb, 2015

  • 具有时序反馈图的对抗在线学习

    基于分区策略，本研究提出了一种新的学习算法，用于预测与专家建议的问题并同时受限于反馈图结构，证明对于传递反馈图，该算法可以高效实现且达到最优遗憾界（与一个常数因子定量相近）的预测性能优化。

    Jun, 2024

  • 带切换成本的赌博机：T ^ {2/3} 遗憾

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

    Oct, 2013

  • 多智能体多臂赌博机中的遗憾下界

    在多臂赌博机领域，多智能体多臂赌博机方法已经受到了广泛关注，但对应的遗憾下界的研究相对较少。本文在不同情景下首次全面研究了遗憾下界，并证明了它们的紧密性。当图表现出良好的连通性和奖励是随机分布时，我们证明了实例相关上界的 O（log T）下界和平均差值独立上界的 sqrt（T）下界。在对抗奖励的假设下，我们建立了连接图的 O（T^（2/3））下界，从而弥合了以前工作中下界与上界之间的差距。当图表现为不连通时，我们还展示了线性的遗憾下界。与以前的研究相比，本文全面研究了这些情景下的紧密下界。

    Aug, 2023