Skip to main content

Multi-armed Bandit Problems with Strategic Arms

Author(s): Braverman, Mark; Mao, Jieming; Schneider, Jon; Weinberg, S Matthew

To refer to this page use:
Abstract: 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 𝑣𝑎 and can choose an amount 𝑥𝑎 to pass on to the principal (keeping 𝑣𝑎−𝑥𝑎 for itself). All non-pulled arms get reward 0. Each strategic arm tries to maximize its own utility over the course of 𝑇 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 (𝑣𝑡𝑎←𝐷𝑎), we show that: \begin{itemize} \item 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 $o(T)$-approximate Nash equilibrium for the arms where the principal receives reward $o(T)$. \item There exists an algorithm for the principal that induces a game among the arms where each arm has a dominant strategy. Moreover, for every $o(T)$-approximate Nash equilibrium, the principal receives 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. \end{itemize}
Publication Date: 2019
Citation: Braverman, Mark, Jieming Mao, Jon Schneider, and S. Matthew Weinberg. "Multi-armed Bandit Problems with Strategic Arms." In Conference on Learning Theory 99 (2019): pp. 383-416.
ISSN: 2640-3498
Pages: 383 - 416
Type of Material: Conference Article
Journal/Proceeding Title: Conference on Learning Theory
Version: Final published version. Article is made available in OAR by the publisher's permission or policy.

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.