Provably Efficient Exploration for Off-Dynamic Restless Multi-Armed Bandits

We study online learning in Restless Multi-Armed Bandits (RMABs) under distributional shift: the agent has access to offline data from a source environment whose dynamics differ from the target by an unknown, arm-specific gap. Ignoring this data wastes a valuable signal and incurs high initial regret; blindly trusting it risks catastrophic failure when the gap is large. We propose ODR-IOB, the first provably safe and adaptive framework for off-dynamic RMABs, built around a Gap-Aware Intersection-of-Balls confidence set construction. The key idea is to maintain a pure-online ball as a safety net, and an offline-augmented ball whose size adapts to a data-driven estimate of the dynamics gap, and plan optimistically over their intersection. The framework is provably never worse than pure online learning, regardless of how large or misleading the gap turns out to be. When the gap is small and the source data is informative, the intersection contracts strictly, yielding a tighter optimistic model and lower regret. We formalize these properties as three simultaneous guarantees: the true dynamics always lie inside the intersection with high probability (coverage); performance never degrades below the pure-online baseline (safety); and regret improves proportionally to the fraction of the state-action space unaffected by the shift (acceleration). Experiments confirm that ODR-IOB significantly outperforms the pure online baseline under small gaps while gracefully degrading to it under large gaps.