Strategic Multi-Armed Bandit Problems Under Debt-Free Reporting
This addresses strategic manipulation in bandit problems, which is incremental as it extends classical settings with game-theoretic elements.
The paper tackles the multi-armed bandit problem with strategic arms that may withhold rewards, introducing a mechanism to enforce truthful reporting and achieve the second-highest average reward, with regret bounds of O(log(T)/Δ) or O(√(T log(T))).
We consider the classical multi-armed bandit problem, but with strategic arms. In this context, each arm is characterized by a bounded support reward distribution and strategically aims to maximize its own utility by potentially retaining a portion of its reward, and disclosing only a fraction of it to the learning agent. This scenario unfolds as a game over $T$ rounds, leading to a competition of objectives between the learning agent, aiming to minimize their regret, and the arms, motivated by the desire to maximize their individual utilities. To address these dynamics, we introduce a new mechanism that establishes an equilibrium wherein each arm behaves truthfully and discloses as much of its rewards as possible. With this mechanism, the agent can attain the second-highest average (true) reward among arms, with a cumulative regret bounded by $O(\log(T)/Δ)$ (problem-dependent) or $O(\sqrt{T\log(T)})$ (worst-case).