Feb, 2024

在线多类别分类的强化学习反馈算法：变体和权衡

PDF
TL;DR多类分类中，我们研究了在对抗性在线环境中依赖强化学习反馈与完全信息之间的差异对最佳错误界限的影响，提供了几乎严格的答案。我们还研究了随机化学习者与确定性学习者之间以及适应性对手与无意识对手之间在强化学习反馈环境下的差距，并与完全信息场景进行了对比。此外，我们的结果表明，在某些情况下，最佳随机化错误界限接近于其确定性对应界限的平方根。
multiclass classificationadversarial online settingbandit feedbackmistake bound modelrandomized learner
发现论文，激发创造
  • 多类别分类中的强盗信息真实价格

    经作者研究，本论文主要探讨基于强化学习反馈的多类别分类问题，特别关注类别数量 K 对于 T 步的后悔度上界是否能够超过现有算法的√(KT) 依赖性，作者提出了一种新的分类算法以获得对于适度大小的假设类别集合维度的后悔度结果 O (|H|+√(T))，并证明了理论上限范围内（除去对数项）上界的紧密性。

    May, 2024

  • 有限误差在线学习中反馈价格的界限

    改进了几种在线学习场景的最坏情况边界，包括延迟模糊强化学习、函数族组合学习、犹豫学习等，并解决了多类学习中反馈价格问题和多输入延迟模糊强化学习的边界问题。

    Jan, 2024

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

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

    Sep, 2014

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

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

    Nov, 2017

  • 多分类问题下的在线可学习性研究

    我们研究基于强化学习反馈的在线多类别分类。我们扩展了 (daniely2013price) 的结果，通过展示在标签空间无限的情况下，强化学习小石维度的有限性是在线多类别可学习性的必要和充分条件。我们的结果补充了 (hanneke2023multiclass) 的最近工作，他们证明了在标签空间无限的情况下小石维度描述了全信息设置中的在线多类别可学习性。

    Aug, 2023

  • 多类别 PAC 型强盗分类的快速速率

    我们研究了具有强化学习反馈的多分类 PAC 学习问题，提出了一种新颖的学习算法将样本复杂度降低到 O ((poly (K) + 1/ε²) log (|H|/δ))，改进了现有问题的边界，同时在一般类别情况下也得到了类似的样本复杂度边界，算法利用随机优化技术通过 Frank-Wolfe 更新计算低方差探索分布。

    Jun, 2024

  • 反馈图的在线学习：超越赌博机

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

    Feb, 2015

  • 具有切换成本和其他自适应对手的在线学习

    本文研究了预测中的不同类型自适应（非固定的）对手的强度，使用新概念的策略遗憾去衡量玩家的表现，特别关注记忆和切换成本的自适应对手，具有均摊 2/3 次幂的速率且强度显著较弱。

    Feb, 2013

  • 组合赌博机与相对反馈

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

    Mar, 2019

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

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

    Jun, 2023