Multi-armed Bandit Problems with Strategic Arms
Multi-armed Bandit Problems with Strategic Arms
复制标题
DOI：
--
复制
发表时间：
2017-06
期刊：
影响因子：
--
通讯作者：
M. Braverman;Jieming Mao;Jon Schneider;S. Weinberg
中科院分区：
文献类型：
--
作者：
M. Braverman;Jieming Mao;Jon Schneider;S. Weinberg
我们研究了多臂强盗问题的一个战略版本，其中每个手臂都是一个单独的战略代理人，而我们作为委托人，每一轮都拉一只手臂。当被拉动时，手臂会获得一些私人奖励$v_a$，并可以选择一个金额$x_a$传递给主体(将$v_a-x_a$保留为自己)。所有未被拉出的手臂将获得0美元的奖励。每个战略部门都试图在每一轮新台币的回合中最大化自己的效用。我们的目标是为校长设计一种算法，激励这些手臂尽可能多地传递他们的私人奖励。当每轮($v_a^t\leftarrow D_a$)随机抽取私人奖励时，我们证明了：-在经典的对抗性多臂强盗环境中表现良好的算法必然表现得很差：对于所有在对抗性环境中保证低遗憾的算法，存在分布$D_1，\ldots，D_k$，以及当委托人获得奖励$o(T)$时，手臂的近似纳什均衡。-尽管如此，对于委托人来说，仍然存在一种算法，它可以在手臂之间诱导一场游戏，其中每个手臂都有一个主导策略。当每个手臂发挥其主导策略时，委托人看到预期回报$\Mu‘t-o(T)$，其中$\Mu’$是第二大均值$\mathbb{E}[D_{a}]$。如果武器是非战略武器($x_a=v_a$)，并且如果存在战略武器和非战略武器的混合，则该算法维持其保证。
We study a strategic version of the multi-armed bandit problem, where each arm is an individual strategic agent and we, the principal, pull one arm each round. When pulled, the arm receives some private reward $v_a$ and can choose an amount $x_a$ to pass on to the principal (keeping $v_a-x_a$ for itself). All non-pulled arms get reward $0$. Each strategic arm tries to maximize its own utility over the course of $T$ rounds. Our goal is to design an algorithm for the principal incentivizing these arms to pass on as much of their private rewards as possible. When private rewards are stochastically drawn each round ($v_a^t \leftarrow D_a$), we show that: - Algorithms that perform well in the classic adversarial multi-armed bandit setting necessarily perform poorly: For all algorithms that guarantee low regret in an adversarial setting, there exist distributions $D_1,\ldots,D_k$ and an approximate Nash equilibrium for the arms where the principal receives reward $o(T)$. - Still, there exists an algorithm for the principal that induces a game among the arms where each arm has a dominant strategy. When each arm plays its dominant strategy, the principal sees expected reward $\mu'T - o(T)$, where $\mu'$ is the second-largest of the means $\mathbb{E}[D_{a}]$. This algorithm maintains its guarantee if the arms are non-strategic ($x_a = v_a$), and also if there is a mix of strategic and non-strategic arms.