Oblivious players can learn shared rewards but face coordination limits
Characterizing Oblivious Common-Reward Multi-Player Bandits: Universal Stationarity, Coordination Traps, and Certified Global Rates
Machine Learning
Summary
This paper studies a game where multiple players pick choices without knowing what others do, and all get one shared score. The authors show that even without any communication, players can learn strategies that stop improving too much, but these strategies might not be the best possible. They also find conditions where players can reach the best group outcome and provide ways to check if this is happening. This helps understand how independent players might coordinate to share rewards even when they don’t see each other’s actions.
What this means in practice
- •For autonomous agent developers: Design agents that learn joint behaviors from shared rewards without observing others’ actions.
- •For distributed sensor network engineers: Use coordination certificates to improve collective performance in sensor networks that share global feedback only.
A theory result. No direct application yet.
Authors
Mingxiao Li, Wenhai Lai, Hongyu Wang
Abstract
This paper presents a theoretical analysis of the oblivious common-reward multi-player multi-armed bandit (OC-MPMAB), a minimal multi-player bandit model in which multiple players select arms simultaneously and observe only a shared reward. Crucially, the players are fully oblivious: they do not observe the actions of other players and do not even know whether any other players exist. The contributions of this work are threefold. First, we prove that the independent gradient-bandit updates applied by the players jointly form an unbiased stochastic gradient estimator of a hidden product-policy objective. This property then yields a universal finite-time first-order stationarity guarantee for every instance. Second, we show that stationarity cannot, in general, be strengthened to global optimality. To illustrate this, we identify a product-policy trap obstruction that rules out the guarantee of global optimality. Third, we show that global optimality can be recovered under structural assumptions on the reward table. To make global optimality achievable, we introduce finite-table certificates that separately characterize product-gradient dominance and self-bounding stochastic noise. We then establish certificate-conditioned bounds on the product-policy gap and pseudo-regret. Consequently, the standard $O(1/t)$ product-policy gap and $O(\log T)$ pseudo-regret rates hold when the certificates are uniform.