Research map / Bandits and online learning / Multi-armed bandits
Robust Performance Incentivizing Algorithms for Multi-Armed Bandits with Strategic Agents
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Analyzes a strategic multi-armed bandit where arms are self-interested agents that can absorb or improve rewards at a cost, showing UCB1 is monotone and deriving budget-constrained best responses and pull bounds.
Problem
Stochastic multi-armed bandits where arms are strategic agents that can manipulate their rewards (absorbing or improving them at a cost) to attract pulls from the principal, which can make the platform's allocation non-robust.
Approach
Shows UCB1 satisfies a generalized monotonicity property under a blind information model, so strategic arms cannot gain pulls by unilaterally adding non-negative reward; uses this to bound equilibrium pulls and best-response utilities under a budget.
Key results
- Proves UCB1 satisfies generalized monotonicity under arm coupling, so non-negative reward boosts weakly increase expected pulls.
- With budget C_i=(1-mu_i)alpha n/k, the best-response strategy yields expected pulls E[T_i(n)] <= alpha n/k + o(n/k) under UCB1.
- Shows the best-response strategy with budget (1-mu_i) alpha n/k gives E[pulls] >= alpha n/k - o(n/k), so the depleting strategy is an o(n/k)-optimal best response.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the depletion strategy with budget (1-\mu_i) \alpha \frac{n}{k} | UCB1 when other arms use the best-performance strategy · Stochastic multi-armed bandits with strategic agents | expected pulls: \E[\totit{n}] \ge \alpha \frac{n}{k} - o(n/k) | Helped |
| Give arm i budget (1-\mu_i) \frac{\alpha n}{k} | UCB1 when other arms use the best-performance strategy · Stochastic multi-armed bandits with strategic agents | expected pulls of arm i: \E[T_i(n)] \leq \alpha \frac{n}{k} + o(n/k); \E[\totit{n}]=\alpha \frac{n}{k} + o(n/k) | Mixed |
| Increase arm i's rewards by a nonnegative amount at each pull | UCB1 · Stochastic multi-armed bandits with strategic agents | expected pulls of arm i | Helped |
| Use a finite effort budget and spend all effort until depleted | UCB1 with other arms using the best-performance strategy · Stochastic multi-armed bandits with strategic agents | utility: u_i(S^{\text{depleate}}_i,S^*_{-i}) \ge \meani \alpha \frac{n}{k} - o(n/k) | Helped |
Limitations
- Results are theoretical and rely on assumptions such as blind information model and other arms playing the best performance strategy.
- Some bounds assume n/k = omega(ln n) and mu_i bounded away from 1; the authors note the assumption may be modifiable.
- Nash equilibrium characterization is not fully tightened according to the authors.
Experimental setup
Builds on: UCB1
Closest papers by meaning
- The Intrinsic Robustness of Stochastic Bandits to Strategic Manipulation (ICML 2020 · similarity 0.91)
- Strategic Multi-Armed Bandit Problems Under Debt-Free Reporting (NeurIPS 2024 · similarity 0.89)
- Optimizing the coalition gain in Online Auctions with Greedy Structured Bandits (NeurIPS 2024 · similarity 0.87)
- Stochastic Bandits Robust to Adversarial Attacks (ICLR 2025 · similarity 0.86)
- Incentivized Learning in Principal-Agent Bandit Games (ICML 2024 · similarity 0.86)
- Near Optimal Best Arm Identification for Clustered Bandits (ICML 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.