Jul, 2013

从强盗到专家：一场统治与独立的故事

PDF
TL;DR本研究考虑 Mannor 和 Shamir 引入的部分可观测性模型，利用 Exp3 算法在可观测性图上高效运行，以支配和独立数来描述定向可观测性模型的遗憾（regret），并证明在无向情况下，学习者可以在选择行动之前甚至不访问可观测性图前实现最佳遗憾。
partial observabilitymulti-armed banditsregretexp3 algorithmobservability graph
发现论文，激发创造
  • 从强盗到专家：浅谈旁观价值

    本文探讨了一种对抗性在线学习情境，其中决策者可以在每个阶段选择一个行动，并观察到给定行动的奖励，同时还能获取有关选择其他行动所获得的奖励的信息。研究者们开发出具有可证明的后悔保证的实用算法，这些算法依赖于非平凡的图论信息反馈结构特性。

    Jun, 2011

  • 反馈图和转移成本下的赌博机

    本研究探讨了对抗多臂赌博问题，其中有部分的观测可用，并且除了每个行动所造成的损失外，还会产生一种新的代价。我们提出了一种新的算法，其遗憾保证仅取决于图的支配数。我们进一步通过引入下界来增加该结果。最后，我们还提出了一种新的算法，当有部分反事实的反馈时，可以改善政策遗憾边界。

    Jul, 2019

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

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

    Sep, 2014

  • 带图反馈的赌博机理解

    本文提出了分数弱支配数和最大独立集数量两个概念分别反映了图结构对 Bandit 问题的最大遗憾上限的上下界，并通过这两个概念提出了线性规划，它们各自对应于弱支配集与其对偶下的分数顶点包集，并证明了最大遗憾上限的一般上界和下界，这些界对于包括树和度数有界图在内的具有界整数间隙的图是紧密最优的。

    May, 2021

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

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

    Feb, 2015

  • 不观测冲突信息的多人赌博机

    该研究探讨了多人随机多臂赌博问题，其中玩家不能相互通信，且如果两个或两个以上的玩家拉动同一臂，就会发生碰撞并且涉及到的玩家将不会收到奖励，在此研究中，作者提出了两个反馈模型，即一种可以观察到碰撞是否发生和一种更难的模型，即没有碰撞信息。作者提出了一个算法可以实现对于后者的对数后悔度，以及一个不依赖于平均数之间差距的平方根后悔度型算法。对于前一模型，作者给出了第一个不依赖于差距的深度后悔度。基于这些想法，作者还提出了一种在随机反～协调博弈中快速达成近似纳什均衡的算法。

    Aug, 2018

  • 合作非随机多臂老虎机中的个体遗憾

    研究通过交换信息在底层网络上通信的代理，以优化共同的非随机多臂赌博问题中各自的遗憾。我们推导出遗憾最小化算法，其中保证每个代理 v 的期望遗憾都是（1+K/|N (v)|)^T 的平方根量级。

    Jul, 2019

  • 利用随机赌博机的侧观察优化

    本文提出一种考虑了副观测数据的随机赌博机模型，并基于上界置信度 (UCBs) 提供了高效的算法，用于在社交网络中推荐内容，实现了比传统算法更好的效果。

    Oct, 2012

  • 探索先行，利用随后：强盗问题中后悔的真实形状

    本文研究多臂老虎机问题的遗憾下界，并利用 Kullback-Leibler 分歧的已知特性证明了非相对论、分布依赖的限制。这些限制特别表明，在初始阶段遗憾几乎线性增长，并且在最后阶段仅出现知名的对数增长。证明技术突出了信息理论论证的本质，并去除了所有不必要的复杂性。

    Feb, 2016

  • 不确定性下的奖励最大化：利用网络的相关观察

    设计考虑了存在网络结构情况下对多臂赌博问题的解决方案，提出两个基于网络结构的策略，并在真实社交网络和路由网络的数据上测试，证明相比于现有策略获得了更多的好处。

    Apr, 2017