# Multi-armed Bandit Problems with Strategic Arms

arXiv: https://arxiv.org/abs/1706.09060 · HTML: https://mlsanity.com/paper/1706.09060/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Jun 2017.

## Built on by (most cited first, 16 of 16)

- [Learning with Exposure Constraints in Recommendation Systems](https://mlsanity.com/paper/2302.01377/) (2023)
- [Repeated Principal-Agent Games with Unobserved Agent Rewards and Perfect-Knowledge Agents](https://mlsanity.com/paper/2304.07407/) (2023)
- [Combinatorial Bandits under Strategic Manipulations](https://mlsanity.com/paper/2102.12722/) (2021)
- [Bandits Meet Mechanism Design to Combat Clickbait in Online Recommendation](https://mlsanity.com/paper/2311.15647/) (2023)
- [Pay for The Second-Best Service: A Game-Theoretic Approach Against Dishonest LLM Providers](https://mlsanity.com/paper/2511.00847/) (2025)
- [Multi-armed Bandit Algorithm against Strategic Replication](https://mlsanity.com/paper/2110.12160/) (2021)
- [Estimating and Incentivizing Imperfect-Knowledge Agents with Hidden Rewards](https://mlsanity.com/paper/2308.06717/) (2023)
- [Strategic Linear Contextual Bandits](https://mlsanity.com/paper/2406.00551/) (2024)
- [Contractual Reinforcement Learning: Pulling Arms with Invisible Hands](https://mlsanity.com/paper/2407.01458/) (2024)
- [Repeated Contracting with Multiple Non-Myopic Agents: Policy Regret and Limited Liability](https://mlsanity.com/paper/2402.17108/) (2024)
- [On the Robustness of Epoch-Greedy in Multi-Agent Contextual Bandit Mechanisms](https://mlsanity.com/paper/2307.07675/) (2023)
- [Robust and Performance Incentivizing Algorithms for Multi-Armed Bandits with Strategic Agents](https://mlsanity.com/paper/2312.07929/) (2023)
- [Learning in Markov Games with Adaptive Adversaries: Policy Regret, Fundamental Barriers, and Efficient Algorithms](https://mlsanity.com/paper/2411.00707/) (2024)
- [COBRA: Contextual Bandit Algorithm for Ensuring Truthful Strategic Agents](https://mlsanity.com/paper/2505.23720/) (2025)
- [Optimization-friendly generic mechanisms without money](https://mlsanity.com/paper/2106.07752/) (2021)
- [MESHA: Mechanism-Enforced Sequential Halving for Strategic Linear Bandits](https://mlsanity.com/paper/2607.14706/) (2026)

## Abstract (arXiv)

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 va and can choose an amount xa to pass on to the principal (keeping va-xa 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 (vat leftarrow Da), 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 D1,ldots,Dk 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 μ'T - o(T), where μ' is the second-largest of the means mathbbE[Da]. This algorithm maintains its guarantee if the arms are non-strategic (xa = va), and also if there is a mix of strategic and non-strategic arms.