Research map / Bandits and online learning / Multi-armed bandits
Strategic Multi-Armed Bandit Problems Under Debt-Free Reporting
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.
Studies strategic multi-armed bandits where arms retain part of their reward under debt-free reporting, and proposes a bonus-payment successive-elimination algorithm (S-SE) whose truthful reporting is a dominant-strategy SPE, achieving log(T)/Δ or sqrt(KT log T) regret.
Problem
Multi-armed bandits with strategic arms that may withhold part of their reward; the player must learn despite arms misreporting, with arms restricted to reporting no more than the observed reward (debt-free reporting).
Approach
A strategic successive-elimination algorithm with a carefully calibrated bonus payment at the end of the game makes truthful reporting a dominant-strategy SPE; adaptive elimination limits the savings a dishonest arm can accumulate, reducing the required bonus and improving regret from O(T^{2/3}) to log(T)/Δ.
Key results
- Algorithm S-SE has a dominant-strategy SPE where truthful reporting is optimal for each arm, shown in the incentive-compatibility theorem.
- Regret bound O(sum_{k>=2} log(T)/Δ_{1k} + sum_{k>=3} log(T)/Δ_{2k}) problem-dependent.
- Worst-case regret O(sqrt(KT log T)), improving on the O(T^{2/3}) of S-ETC under debt-free reporting.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use adaptive successive elimination with the proposed payment bonus instead of S-ETC | Strategic MAB under debt-free reporting · Strategic MAB, debt-free reporting | regret: \mathcal{O}(T^{2/3}) -> \mathcal{O}(\log(T)/\Delta) (problem-dependent); \mathcal{O}(\sqrt{KT\log(T)}) (problem-independ | Helped |
| Use S-SE with its bonus function to incentivize truthful reporting | Strategic MAB arms · Strategic MAB, debt-free reporting | truthful reporting as a dominant strategy | Helped |
Surprising findings
- Adaptive elimination reduces the bonus needed for truthfulness, so the regret does not incur the extra O(T^{2/3}) cost of fixed-design exploration.
- Replacing bonus rounds with bonus payments does not change the regret order, since bonuses count against player revenue either way.
Limitations
- Adapting UCB-style no-regret algorithms with incentives appears challenging because truthful mechanisms may need exploration separation.
- General-profile analysis requires an extra assumption that cumulative savings are bounded by M.
- Regret is measured against mu_2, which is the best achievable under debt-free reporting, not mu_1.
Experimental setup
Metrics: cumulative regret
Baselines: S-ETC
Builds on: successive elimination S-ETC (strategic explore-then-commit)
Closest papers by meaning
- The Intrinsic Robustness of Stochastic Bandits to Strategic Manipulation (ICML 2020 · similarity 0.91)
- Competing for Shareable Arms in Multi-Player Multi-Armed Bandits (ICML 2023 · similarity 0.90)
- Multi-Armed Bandits With Best-Action Queries (NeurIPS 2026 · similarity 0.89)
- Robust Performance Incentivizing Algorithms for Multi-Armed Bandits with Strategic Agents (AAAI 2025 · similarity 0.89)
- Nash Social Welfare for Multi Armed Bandits: Trajectory-wise Expected and High Probability Regret (NeurIPS 2026 · similarity 0.89)
- Greedy Algorithms for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failure (NeurIPS 2025 · similarity 0.88)
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.