TL;DR
In asynchronous multiplayer multi-armed bandits—where devices independently activate with probability $p$ and collide if multiple active users choose the same channel—previous algorithms suffered high $\mathcal{O}(T^{2/3})$ regret. This paper introduces Cautious Greedy, a centralized algorithm that achieves $\mathcal{O}(\log T)$ regret in general and constant $\mathcal{O}(1)$ regret when the optimal configuration allocates at least one player to every arm.
What Problem Does This Paper Address?
In cognitive radio networks and Internet of Things (IoT) systems, multiple communicating devices share a set of transmission channels (arms). Standard multiplayer bandit literature assumes synchronous play, but real-world IoT devices transmit asynchronously: at any time step, a device activates independently with probability $p$. If two or more active devices select the same channel, they interfere, resulting in a collision and zero reward; a reward is collected only if exactly one active device transmits on that channel.
Assigning multiple players to an arm alters collision likelihood: the probability of receiving an observation on an arm with $m$ assigned players is $g(m) = mp(1-p)^{m-1}$. Previous work using an explore-then-commit (ETC) approach only achieved a suboptimal regret of $\mathcal{O}(T^{2/3})$. Before attempting to decentralize communication, the theoretical benchmark for a centralized coordinator remained an open question: can we achieve $\mathcal{O}(\sqrt{T})$ or logarithmic regret?
Methods
The paper first shows that an adapted Centralized UCB baseline achieves minimax regret of $\mathcal{O}(\sqrt{TK \log(T)} \min(Mp, K))$. However, they improve on this significantly by developing Cautious Greedy:
- Greedy Optimization with Semi-Bandit Feedback: Because arm rewards are scaled by the known concave function $g(m)$, assigning at least one player to an arm yields information about that arm at every round. If every arm is played, the setting resembles full-information feedback, where pure greedy policies (Follow-The-Leader) are known to achieve constant regret.
- Confidence-Guided Arm Elimination: If arm qualities diverge widely, the optimal allocation might assign zero players to the worst arms (let $\nu^*$ be the number of such arms). A standard greedy strategy fails here because it stops exploring suboptimal arms prematurely. Cautious Greedy solves this by:
- Maintaining a conservative estimate $\nu \le \nu^*$ of the number of arms that should receive zero players.
- Eliminating arms only when confident (using lower and upper confidence bounds $\hat{\mu}^L, \hat{\mu}^H$).
- Rotating arms under "pressure" (candidates for zero allocations) in a round-robin schedule across active, unaccepted arms to guarantee every active arm gathers observations without starving.
Datasets
- Synthetic Benchmarks: No real-world datasets were used. The authors evaluated the methods on synthetic environments:
- Setting 1 ($\nu^* = 0$): $M = 30$ players, $K = 2$ arms, mean rewards $\mu = (0.8, 0.5)$, $p = 0.01$, and horizon $T = 10^4$ (optimal assignment is $(26, 4)$).
- Setting 2 ($\nu^* = 1$): $M = 3$ players, $K = 2$ arms, mean rewards $\mu = (0.99, 0.01)$, $p = 0.1$, and horizon $T = 10^4$ (optimal assignment is $(3, 0)$).
Key Insights and Ideas
- Full Information vs. Bandits Regime: When the optimal configuration allocates at least one player to every arm ($\nu^* = 0$), all arms are sampled with constant probability in expectation. Exploration is effectively "free," turning the bandit problem into an online full-information problem where constant $\mathcal{O}(1)$ regret is achievable.
- When is $\nu^* = 0$? The authors prove (Lemma B.1) that if the arm mean rewards are sufficiently close (e.g., within a factor of $1.3\exp(-\alpha)(1-\alpha)$ of the best arm, where $\alpha = Mp/K$), the optimal strategy never leaves an arm empty.
- Data-Dependent Optimality: Cautious Greedy achieves an upper bound of: $$\mathcal{O}\left(\frac{1}{r} + \sum_{j \le \nu^*} \frac{\log T}{\Delta_{(j)}}\right)$$ where $r$ is the minimum parameter perturbation required to alter the optimal assignment support, and $\Delta_{(j)}$ is the sub-optimality gap. Matching lower bounds established in the paper demonstrate that both the $\frac{1}{r}$ dependence for $\nu^* = 0$ and the $\frac{\log T}{\Delta}$ dependence for $\nu^* > 0$ are unimprovable.
Key Results
- Theoretical Bounds:
- When $\nu^* = 0$: Regret is strictly bounded by $\mathcal{O}(1/r)$, completely independent of the horizon $T$.
- When $\nu^* > 0$: Regret scales as $\mathcal{O}\left(\frac{1}{r} + \sum_{j=1}^{\nu^*} \frac{\log(K^2 T^2)}{\Delta_{(j)}}\right)$, matching the lower bound order.
- Empirical Performance:
- In the $\nu^* = 0$ experiment ($M=30, K=2$), Cautious Greedy levels off to flat, constant cumulative regret around $\approx 10$, heavily outperforming both Centralized UCB (which grows sublinearly $\approx 25$) and ETC (which reaches $\approx 60$).
- In the $\nu^* = 1$ regime, UCB eliminates suboptimal allocations faster and achieves lower regret ($\approx 50$), whereas Cautious Greedy spends extra rounds confirming that an arm should indeed receive 0 players before committing, ending with regret near $\approx 250$ (still vastly superior to ETC's $\approx 450$).
Limitations and Future Work
- Centralized Control: The primary limitation is the requirement of a central controller that assigns players to channels every round. Decentralizing this without incurring excessive communication or collision costs remains an open problem.
- Homogeneous Activation Probabilities: The current framework assumes all players share an identical activation probability $p$. Extending this to heterogeneous activation probabilities ($p_i \neq p_j$) introduces non-trivial combinatorial optimization challenges.
- Parameter Dependencies: While optimal in $T$, $r$, and $\Delta$, the constants depend heavily on $M$, $K$, and $p$ (e.g., polynomial dependencies that may be loose).
- Decentralized Communication Trade-offs: The authors suggest that decentralized variants could communicate via collisions, but in asynchronous regimes, transmitting a single bit reliably takes roughly $\mathcal{O}\left(\frac{\log T}{p^2}\right)$ time steps.
Summary updated