# Learning in Restless Bandits under Exogenous Global Markov Process

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 64 references that are in the map.
- First posted on arXiv 17 Dec 2021.

## Builds on (most cited first, 6 of 6)

- [Federated Learning: A Signal Processing Perspective](https://mlsanity.com/paper/2103.17150/) (2021)
- [Learning in Restless Multi-Armed Bandits via Adaptive Arm Sequencing Rules](https://mlsanity.com/paper/1906.08120/) (2019)
- [Distributed Learning over Markovian Fading Channels for Stable Spectrum Access](https://mlsanity.com/paper/2101.11292/) (2021)
- [On Sequential Elimination Algorithms for Best-Arm Identification in Multi-Armed Bandits](https://mlsanity.com/paper/1609.02606/) (2016)
- [An order optimal policy for exploiting idle spectrum in cognitive radio networks](https://mlsanity.com/paper/1709.00237/) (2017)
- [Learning to Detect an Odd Restless Markov Arm with a Trembling Hand](https://mlsanity.com/paper/2105.03603/) (2021)

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

- [Client Selection for Generalization in Accelerated Federated Learning: A Multi-Armed Bandit Approach](https://mlsanity.com/paper/2303.10373/) (2023)
- [Multi-Flow Transmission in Wireless Interference Networks: A Convergent Graph Learning Approach](https://mlsanity.com/paper/2303.15544/) (2023)
- [Global Rewards in Restless Multi-Armed Bandits](https://mlsanity.com/paper/2406.00738/) (2024)
- [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)
- [Sparse Training for Federated Learning with Regularized Error Correction](https://mlsanity.com/paper/2312.13795/) (2023)
- [A Masked Pruning Approach for Dimensionality Reduction in Communication-Efficient Federated Learning Systems](https://mlsanity.com/paper/2312.03889/) (2023)
- [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 an extension to the restless multi-armed bandit (RMAB) problem with unknown arm dynamics, where an unknown exogenous global Markov process governs the rewards distribution of each arm. Under each global state, the rewards process of each arm evolves according to an unknown Markovian rule, which is non-identical among different arms. At each time, a player chooses an arm out of N arms to play, and receives a random reward from a finite set of reward states. The arms are restless, that is, their local state evolves regardless of the player's actions. Motivated by recent studies on related RMAB settings, the regret is defined as the reward loss with respect to a player that knows the dynamics of the problem, and plays at each time t the arm that maximizes the expected immediate value. The objective is to develop an arm-selection policy that minimizes the regret. To that end, we develop the Learning under Exogenous Markov Process (LEMP) algorithm. We analyze LEMP theoretically and establish a finite-sample bound on the regret. We show that LEMP achieves a logarithmic regret order with time. We further analyze LEMP numerically and present simulation results that support the theoretical findings and demonstrate that LEMP significantly outperforms alternative algorithms.