Feb, 2024

具备调解者反馈的赌博机信息容量遗憾界限

PDF
TL;DR这项研究针对中介反馈问题，提出了一个信息论度量，称为策略集能力，用于衡量策略集的复杂性。研究在对抗性和随机性环境中采用了经典的 EXP4 算法，提供了与策略集能力相关的新后悔上界，并且改进了相关的专家建议问题。此外，针对线性赌博反馈，我们还证明了一种不可能利用策略之间的相似性的下界，并且提供了一个与策略集的信息半径相关的全信息变种的后悔上界。
mediator feedback problembandit gamepolicy set capacityregret boundsinformation radius
发现论文，激发创造
  • 带专家建议的强盗问题的改进遗憾界限

    通过受限反馈模型，本研究提供了关于 “专家建议问题” 的最坏情况后悔度的新的下界和上界，其中下界为 O (sqrt (KT ln (N/K)))，上界与之相匹配，并改进了现有最佳下界 sqrt (KT (ln N) / (ln K))。同时，对于标准反馈模型，本研究提供了一种新的基于实例的上界，该上界取决于专家之间的一致性，并相比之前的结果提供了对数级的改进。

    Jun, 2024

  • 除去偏见：针对对抗性赌博机和 MDPs 的高概率数据依赖性遗憾边界

    发展了一种新的方法，使用标准无偏估计量，并依赖于简单的递增的学习速率表和对数单调自协调障碍以及加强的弗里德曼不等式，以获取高概率遗憾边界。

    Jun, 2020

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

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

    Sep, 2014

  • 高斯过程赌博中的信息增益与遗憾界限

    研究连续性赌博机问题下高斯过程与多种学习算法（GP-UCB、GP-TS）的误差性能，通过独立的贝叶斯和频率学派来分析多项式差距，得出了均价核的特殊化，进一步提高了误差性能。

    Sep, 2020

  • 针对多种动作的汤普森取样的信息论分析

    本论文提供了一种新的、基于编码的方法，用于证明 Russo 和 Van RoyBayesian 遗憾界制度对先验不确定性的依赖性，其通过熵以及由于动作数量的不断增加，熵可以变得无限大。通过引入率失真的概念，建立了新的界，从而通过信息理论的方法来推导线性选择组失策问题的几乎最优界，并提供了逻辑选择组失策问题的一个界，比以前提供的界显著改善。

    May, 2018

  • 对抗性赌博机的改进下界

    该研究提供了敌对强盗算法必须遭受的遗憾的新的下界，并证明了对于最佳臂的总损失或损失的二次变化的上界是接近紧的。此外，研究还证明了两个不可能的结果，即单臂最优和遗憾不能随损失范围的提高而扩展。相比之下，在完全信息设置中这两个结果是可能的。

    May, 2016

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

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

    Apr, 2022

  • 博弈中协作学习的最优遗憾界

    我们研究了在一个通用的协作多智能体多臂老虎机模型中的遗憾最小化问题，在该模型中，每个智能体面临一个有限的臂集，并可以通过一个中央控制器与其他智能体进行通信。该模型中每个智能体的最优臂是具有最大期望混合奖励的臂，其中每个臂的混合奖励是其在所有智能体之间的奖励的加权平均，这使得智能体之间的通信至关重要。尽管在这个协作模型下已知最优臂识别的近似复杂度，但最优遗憾问题仍然是开放的。在这项工作中，我们解决了这个问题，并提出了第一个在这个协作老虎机模型下具有最优遗憾界限的算法。此外，我们还展示了只需要一个小的常数期望通信轮数。

    Dec, 2023

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

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

    Feb, 2013

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

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

    Aug, 2023