两人盲拧游戏中无算法串通的托马斯・桑普林
该研究探讨了多人随机多臂赌博问题,其中玩家不能相互通信,且如果两个或两个以上的玩家拉动同一臂,就会发生碰撞并且涉及到的玩家将不会收到奖励,在此研究中,作者提出了两个反馈模型,即一种可以观察到碰撞是否发生和一种更难的模型,即没有碰撞信息。作者提出了一个算法可以实现对于后者的对数后悔度,以及一个不依赖于平均数之间差距的平方根后悔度型算法。对于前一模型,作者给出了第一个不依赖于差距的深度后悔度。基于这些想法,作者还提出了一种在随机反~协调博弈中快速达成近似纳什均衡的算法。
Aug, 2018
我们开发了一种基于 Thompson 抽样的算法,利用关于对手行动和奖励结构的信息来应对部分信息和多机构的挑战。在交通路由和雷达感知等实际应用中,我们的方法显著减少了实验预算,与基准算法相比,实现了超过十倍的减少。此外,本研究还引入了乐观 - 无悔框架,将我们提出的方法和领域中现有算法相结合。
Feb, 2024
该研究基于连续时间技术提出了一个理论模型,旨在研究适应性学习算法之间的策略互动。通过揭示算法之间的自发耦合机制,该研究证明了人工智能算法之间存在的勾结现象,并提出了一种足以消除算法间自发耦合的充分条件,以及设计学习鲁棒性策略的机制所必要的回馈机制。
Feb, 2022
文章提出了一种基于多臂赌博框架的在线顺序决策支持方法,利用 Thompson 抽样来平衡探索与利用的权衡,提出了两种算法用以解决多臂赌博问题,并在理论上给出了广义下界,通过实验证明了该方法在现实世界的数据集上表现的有效性。
Sep, 2022
本论文针对多人随机多臂老虎机问题中,玩家无法通信且产生碰撞时得分为零的情形。解决了不同玩家可能具有不同的均值的异质设置,并提出了一种新的有效算法,结合了强制碰撞的隐式通信和匹配消除的思路。并给出了有限时间分析,证明了该算法的次线性极大遗憾界,解决了 NeurIPS2018 的一个开放性问题。
Feb, 2019
研究了利用自我私利游戏玩家的多臂赌博机问题,提出了一种能够实现对恶意玩家具有鲁棒性的算法,并构建了两个不同设置下的鲁棒算法,其中一种包括隐式通信的算法,同时针对只能观察奖励或手臂平均值任意变化的情况进行了研究。
Feb, 2020
本研究探索人工智能定价算法在重复博弈中的表现,发现算法协作在人类行为偏好的影响下较为普遍,同时发现体验随机化、相对绩效影响和最新经验偏好都能增强算法协作,最后检测了不同因素下异质代理的表现和鲁棒性。
Feb, 2021
通过利用 Tsallis 熵正则化的值迭代方法,我们提出了一种合理且收敛的算法,在弱条件下以无耦合和单时间尺度算法的方式高效地实现了近似纳什均衡。该算法在多项式时间内学习近似纳什均衡,仅需要存在一个诱导不可约和非周期性马尔可夫链的策略对,从而明显减弱了过去的假设。我们的分析利用了负漂移不等式,并引入了 Tsallis 熵的新特性,这些特性具有独立的研究价值。
Dec, 2023
本研究主要探讨了潜在博弈、马尔可夫潜在博弈和 Frank-Wolfe 算法在随机成本和强盗反馈下的应用,提出了一种具有足够探索性和递归梯度估计的变种算法,能证明收敛于纳什均衡并对每个参与者实现亚线性遗憾。该算法同时在潜在博弈中实现了纳什遗憾和 $O (T^{4/5})$ 的遗憾上界,匹配了现有最佳结果,无需额外的投影步骤。通过精确平衡过去样本的重复使用和新样本的探索,我们将结果扩展到了马尔可夫潜在博弈中,将现有最佳纳什遗憾从 $O (T^{5/6})$ 改进至 $O (T^{4/5})$。此外,我们的算法不需要了解游戏的任何信息,如分布误差系数,这提供了更灵活的实际实施。实验结果证实了我们的理论发现,并强调了我们方法的实际有效性。
Apr, 2024