干货| ICML 2023：多玩家多臂老虎机中可分享手臂场景的竞争问题
点击蓝字
关注我们
AI TIME欢迎每一位AI爱好者的加入！
作者介绍
徐韧喆
清华大学计算机科学与技术系四年级博士生，研究方向包括Algorithmic Fairness, Algorithmic Game Theory和Out-of-distribution Generalization
报告题目
多玩家多臂老虎机中可分享手臂场景的竞争问题
内容简介
长期以来人们一直在研究，在可共享和有限资源场景中不同agent的竞争行为。在现实中，agent通常需要同时学习收益函数并进行利益最大化的优化。为了设计每个agent的竞争策略，我们在一种全新的多人多臂老虎机（MPMAB）环境中对agent之间的竞争进行建模。我们假设玩家是自私的，旨在最大化自己的累计收益。此外，当多个agent选择同一条手臂时，我们假设这些玩家按预期平均分享手臂的收益。
在此背景下，我们首先分析已知收益时的纳什均衡。随后，我们提出了一种基于均衡的新型自私MPMAB平均分配（SMAA）方法。我们从理论上证明，当所有agent都遵循该算法时，SMAA可以为每个agent实现良好的regret保证。此外，我们证明，任何一个自私的agent都不能通过改变策略来显著增加他们的奖励，也不能在不给自己带来重大损失的情况下对其他agent的收益产生不利影响。我们最终在模拟实验中验证了该方法的有效性。
论文链接：https://arxiv.org/abs/2305.19158
代码链接：https://github.com/windxrz/smaa
01
Background
Incentive-aware machine learning
在网络平台或决策系统中，agent的行为通常是具有策略性的，他们往往为了自己利益的最大化从而调整自身的行为。那么我们要想将这种策略考虑进来，可能的研究问题有两种：第一种是建模，在复杂平台系统中建模每一个agent的策略性行为；第二种是从决策制定者的角度出发，设计一个平台能够在考虑到每个agent的策略性行为之后达到既定目标。
Motivating example-content providers in recommender systems
本文的工作聚焦在第一种方式，即研究在一个推荐系统场景中，如何建模不同agent的策略性行为。我们的研究动机来源于抖音等推荐系统中的内容提供者。内容提供者能够选择生成具有各种主题的内容，同时每个话题下的总流量对每个内容主题的需求是不变的，而内容提供商对于每个话题的总流量是未知的。因此，在这种场景中，不同的内容制造者就会竞争曝光量。
Basic setup
假设总流量是未知的，所以我们会用bandit去刻画这种问题，而我们又做出其中有多个内容制造者的假设，所以选择用多用户多臂老虎机（MPMAB）的场景去描述这种问题。
具体来说，N个agents代表内容制造者，K个arms代表话题，而每个arm的reward代表话题带来的流量。假设整个过程有T轮，在每一个时刻，每个agent自私地选择一条手臂来拉动，即每个内容制造者产生一个主题的内容。每个agent的目标是使自己的曝光量最大化。当多个agent选择同一手臂时，agent会平均分享手臂的收益，即内容制造者分享曝光率。
02
Related works—MPMAB
Motivated by cognitive radio networks
在通信网络的场景中，有很多信道，那么需要使用信号的用户就需要竞争信道来传输信息。
Non-strategic players
在这种场景中，传统工作往往假设每个agent是合作的，他们会共同合作最大化平台的总收益。
此外，在MPMAB框架中很核心的一点是碰撞模型。平台中有多个agent，可能会有多个agent选择同一个arm，在这种情况下，不同碰撞模型刻画了如何给这些agent分配这个arm的收益。在传统的场景中，假设一个信道最多被一个用户使用，那么在大多数标准下一旦发生碰撞，每一个agent都无法得到reward；第二种场景下，假设在匹配市场中，当多个用户选择同一个arm后，reward会分配给期望收益最高的agent。
Strategic players-they consider different collision models
如果我们考虑自私的有策略的用户行为，那么这种有策略的agent也可以分为两种：Jammer：希望平台越坏越好；Selfish player：最大化自己的长期收益。
Other works
还有一些相关工作分析了equilibria的性质，但是大多数工作并未考虑玩家的动态行为。少数工作考虑到了这种动态的收敛过程，但是他们假设玩家对不同话题的总流量有完整的信息，或者考虑到的另外一种场景也并不符合推荐系统的场景。
03
Problem formulation
在这样的场景中，有N个agent和K个arms对应内容制造者和话题，我们假设每个agent的目标是优化在T时刻后的总收益，或者每个arm有自己的期望收益，μk对应着一个话题期望意义上的流量。在每一个时刻t，假设每个agent可能选择armπj（t） ，并且这种策略是自私的，即优化自己的长期收益。在这个时刻，该用户得到收益Rj（t）。Rj（t）的设计是其中的重点，而在本文中我们假设另一种期望意义上均匀的分配机制。具体而言，假设在t时刻带来的收益是Xk（t），在此刻选择该arm的人数为Mk（t），那么每个选择该arm的agent期望意义上得到的reward就是Xk（t）除以Mk（t）。
基于这样的假设，我们希望达到以下目标：首先，为每个agent设计一个策略，当所有用户遵守策略，该策略最终能够收敛到纳什均衡；其次，每个agent的regret尽可能小，regret的标准定义是T时刻后每个agent的总收益与每一时刻理论上最优收益之间的差值；最后，进一步假设用户是自私的，则期望算法对自私agent的deviation是鲁棒的，也就是说即使一个自私的用户改变自己的策略，也不会给自己或别人带来较大的收益上的变化。
04
Proposed method
首先我们需要分析的是极限时刻的场景。假设每个arm的期望收益已知，在这种情况下，pure Nash equilibrium（PNE）是存在的，即在某一个时刻，agent会决定性地选择某个arm；此外，PNE还具有一个性质：选择每个arm的agent数量正比于该arm的期望收益。
本文中我们提出了一种在线策略的算法，它是一种经典地基于alternate exploration的方式。它的关键思想是在每一个时刻t，agent基于历史观测数据估计equilibrium的情况。估计完之后，每个agent在每一个时刻选择在equilibrium中 (t+j) mod N+1的arm，这样能够实现轮循的机制，而这种机制又可以实现regret的最小化。
经过前期的理论分析，可以得到我们的算法形式。我们可以证明，所提算法是收敛到纳什均衡的。即当所有的agent遵守策略时，非均衡状态的回合数是O(log T)。此外，每个agent的期望regret是O（log T）级别，并且它也在一定假设下匹配了regret的lower bound。我们可以进一步证明，单个agent的策略行为不会给自己和他人带来巨大的损失。
05
Synthetic experiments
我们从模拟实验上验证了所提出的方法。我们改变了不同的N和K以及每个reward的分布形式，并通过不同的baseline进行比较。在下图中，红色线是本文所提方法，可以看出我们的方法在不同场景中，regret、非纳什均衡的回合数都是优于baseline的。
06
Conclusion
在本文的工作中，(1) 我们研究在推荐场景中不同内容制造者的策略性行为，在考虑均匀分配机制的情况下提出一种全新的MPMAB框架；(2) 在该问题中，我们分析了每个时刻的纳什均衡，并基于纳什均衡提出一种在线学习策略；(3) 我们证明了当所有用户遵循算法，可以保证每个agent的regret值较小，还证明了该算法对自私用户的行为是鲁棒的，即使他改变自己的策略也不能够给自己或别人带来较大的收益变化。
提
醒
点击“阅读原文”跳转至02：44：45
可以查看回放哦！
往期精彩文章推荐
记得关注我们呀！每天都有新知识！
关于AI TIME
AI TIME源起于2019年，旨在发扬科学思辨精神，邀请各界人士对人工智能理论、算法和场景应用的本质问题进行探索，加强思想碰撞，链接全球AI学者、行业专家和爱好者，希望以辩论的形式，探讨人工智能和人类未来之间的矛盾，探索人工智能领域的未来。
迄今为止，AI TIME已经邀请了1100多位海内外讲者，举办了逾550场活动，超600万人次观看。
我知道你
在看
哦
~
点击 阅读原文 查看回放！