# Learning in Restless Multi-Armed Bandits via Adaptive Arm Sequencing Rules

arXiv: https://arxiv.org/abs/1906.08120 · HTML: https://mlsanity.com/paper/1906.08120/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Jun 2019.

## Built on by (most cited first, 15 of 15)

- [Q-Learning Lagrange Policies for Multi-Action Restless Bandits](https://mlsanity.com/paper/2106.12024/) (2021)
- [Non-Stationary Representation Learning in Sequential Linear Bandits](https://mlsanity.com/paper/2201.04805/) (2022)
- [On learning Whittle index policy for restless bandits with scalable regret](https://mlsanity.com/paper/2202.03463/) (2022)
- [Learning in Restless Bandits under Exogenous Global Markov Process](https://mlsanity.com/paper/2112.09484/) (2021)
- [Deep Reinforcement Learning for Simultaneous Sensing and Channel Access in Cognitive Networks](https://mlsanity.com/paper/2110.14541/) (2021)
- [Client Selection for Generalization in Accelerated Federated Learning: A Multi-Armed Bandit Approach](https://mlsanity.com/paper/2303.10373/) (2023)
- [Restless and Uncertain: Robust Policies for Restless Bandits via Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2107.01689/) (2021)
- [Multi-Flow Transmission in Wireless Interference Networks: A Convergent Graph Learning Approach](https://mlsanity.com/paper/2303.15544/) (2023)
- [SINR-Aware Deep Reinforcement Learning for Distributed Dynamic Channel Allocation in Cognitive Interference Networks](https://mlsanity.com/paper/2402.17773/) (2024)
- [Restless Multi-Armed Bandits under Exogenous Global Markov Process](https://mlsanity.com/paper/2202.13665/) (2022)
- [Representation Learning for Context-Dependent Decision-Making](https://mlsanity.com/paper/2205.05820/) (2022)
- [DeepOFW: Deep Learning-Driven OFDM-Flexible Waveform Modulation for Peak-to-Average Power Ratio Reduction](https://mlsanity.com/paper/2603.23544/) (2026)
- [Partially-Observable Sequential Change-Point Detection for Autocorrelated Data via Upper Confidence Region](https://mlsanity.com/paper/2404.00220/) (2024)
- [Control-Optimized Deep Reinforcement Learning for Artificially Intelligent Autonomous Systems](https://mlsanity.com/paper/2507.00268/) (2025)
- [Distributed Learning in Markovian Restless Bandits over Interference Graphs for Stable Spectrum Sharing](https://mlsanity.com/paper/2512.17161/) (2025)

## Abstract (arXiv)

We consider a class of restless multi-armed bandit (RMAB) problems with unknown arm dynamics. At each time, a player chooses an arm out of N arms to play, referred to as an active arm, and receives a random reward from a finite set of reward states. The reward state of the active arm transits according to an unknown Markovian dynamics. The reward state of passive arms (which are not chosen to play at time t) evolves according to an arbitrary unknown random process. The objective is an arm-selection policy that minimizes the regret, defined as the reward loss with respect to a player that always plays the most rewarding arm. This class of RMAB problems has been studied recently in the context of communication networks and financial investment applications. We develop a strategy that selects arms to be played in a consecutive manner, dubbed Adaptive Sequencing Rules (ASR) algorithm. The sequencing rules for selecting arms under the ASR algorithm are adaptively updated and controlled by the current sample reward means. By designing judiciously the adaptive sequencing rules, we show that the ASR algorithm achieves a logarithmic regret order with time, and a finite-sample bound on the regret is established. Although existing methods have shown a logarithmic regret order with time in this RMAB setting, the theoretical analysis shows a significant improvement in the regret scaling with respect to the system parameters under ASR. Extensive simulation results support the theoretical study and demonstrate strong performance of the algorithm as compared to existing methods.