Research map / Bandits and online learning / Multi-armed bandits

The Bandit Whisperer: Communication Learning for Restless Bandits

AAAI 2025 · Bandits and online learning › Multi-armed bandits · approach: Non-stationary and structured-reward bandits · 1 citations (OpenAlex)

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.

Proposes a communication-learning approach for restless multi-armed bandits with systematically noisy arms, where arms receive Q-network parameters from similar arms and a decomposed VDN-style communication Q-network learns when to communicate.

Problem

Restless multi-armed bandits trained with deep RL suffer when some arms have systematic reward errors (e.g., from heterogeneous data collection or differential-privacy noise), which can create false optima and suboptimal central-planner allocations.

Approach

Arms learn binary communication actions: a receiving arm adopts a sender's Q-network as a softmax behavior policy to collect exploratory samples for its own Q-learning. The communication reward is the difference in planner return with and without messages, and a linearly decomposed communication Q-network (VDN-style) makes the joint action selection tractable.

Key results

• On Synthetic (N=21, B=15), Comm reaches 75% of normalized return versus 62% for No Comm and 21% for Fixed Comm at 100% noise level.
• On ARMMAN (N=48, B=20), Comm reaches 77% versus 63% for No Comm; Random Comm falls to -22%.
• When noisy arms increase from 15 to 17 on Synthetic, Comm drops only 3% while Fixed Comm drops 42 percentage points.

Measured effects reported in the paper

Surprising findings

• Fixed communication from non-noisy to noisy arms, despite oracle noise knowledge, often performs worse than No Comm.
• Noise-free-to-noisy communication can be exponentially harmful in sample complexity in some constructed RMABs (Lemma on useless channels).

Limitations

• Experiments are purely simulated; the ARMMAN and SIS settings are simulators built from real data, not field deployments.
• Theoretical results rely on concentratability and mixing-time assumptions and worst-case constructions.

Experimental setup

Datasets: ARMMAN call listenership logs (anonymized, used to estimate transitions) synthetic continuous-state RMAB SIS epidemic simulator

Benchmarks: Synthetic RMAB (N=21, B=15) SIS epidemic model (N=32, B=16) ARMMAN maternal healthcare (N=48, B=20)

Metrics: return normalized to No Noise and Comm interquartile mean return standard error over seeds

Baselines: No Comm Fixed Comm Nearest Neighbor Comm Random Comm No Noise

Builds on: deep Q-learning for RMABs Whittle index / Lagrangian relaxation value decomposition networks (VDN) multi-agent MDP

Closest papers by meaning

• Provably Efficient Reinforcement Learning for Adversarial Restless Multi-Armed Bandits with Unknown Transitions and Bandit Feedback (ICML 2024 · similarity 0.89)
• DOPL: Direct Online Preference Learning for Restless Bandits with Preference Feedback (ICLR 2025 · similarity 0.87)
• Reinforcement learning with combinatorial actions for coupled restless bandits (ICLR 2025 · similarity 0.87)
• Online Restless Multi-Armed Bandits with Long-Term Fairness Constraints (AAAI 2024 · similarity 0.86)
• Achieving $\tilde{\mathcal{O}}(1/N)$ Optimality Gap in Restless Bandits through Gaussian Approximation (NeurIPS 2025 · similarity 0.86)
• Global Rewards in Restless Multi-Armed Bandits (NeurIPS 2024 · similarity 0.86)