# Best Arm Identification in Restless Markov Multi-Armed Bandits

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 35 references that are in the map.
- First posted on arXiv 29 Mar 2022.

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

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [Bandits with Switching Costs: T^{2/3} Regret](https://mlsanity.com/paper/1310.2997/) (2013)
- [Optimal Best Markovian Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1912.00636/) (2019)
- [Probabilistic Sequential Shrinking: A Best Arm Identification Algorithm for Stochastic Bandits with Corruptions](https://mlsanity.com/paper/2010.07904/) (2020)
- [Best-Arm Identification in Correlated Multi-Armed Bandits](https://mlsanity.com/paper/2109.04941/) (2021)
- [Sequential Controlled Sensing for Composite Multihypothesis Testing](https://mlsanity.com/paper/1910.12697/) (2019)
- [Best Arm Identification for Cascading Bandits in the Fixed Confidence Setting](https://mlsanity.com/paper/2001.08655/) (2020)
- [Detecting an Odd Restless Markov Arm with a Trembling Hand](https://mlsanity.com/paper/2005.06255/) (2020)
- [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, 3 of 3)

- [Federated Best Arm Identification with Heterogeneous Clients](https://mlsanity.com/paper/2210.07780/) (2022)
- [Optimal Best Arm Identification with Fixed Confidence in Restless Bandits](https://mlsanity.com/paper/2310.13393/) (2023)
- [Graph Feedback Bandits on Similar Arms: With and Without Graph Structures](https://mlsanity.com/paper/2501.14314/) (2025)

## Abstract (arXiv)

We study the problem of identifying the best arm in a multi-armed bandit environment when each arm is a time-homogeneous and ergodic discrete-time Markov process on a common, finite state space. The state evolution on each arm is governed by the arm's transition probability matrix (TPM). A decision entity that knows the set of arm TPMs but not the exact mapping of the TPMs to the arms, wishes to find the index of the best arm as quickly as possible, subject to an upper bound on the error probability. The decision entity selects one arm at a time sequentially, and all the unselected arms continue to undergo state evolution (em restless arms). For this problem, we derive the first-known problem instance-dependent asymptotic lower bound on the growth rate of the expected time required to find the index of the best arm, where the asymptotics is as the error probability vanishes. Further, we propose a sequential policy that, for an input parameter R, forcibly selects an arm that has not been selected for R consecutive time instants. We show that this policy achieves an upper bound that depends on R and is monotonically non-increasing as R→∞. The question of whether, in general, the limiting value of the upper bound as R→∞ matches with the lower bound, remains open. We identify a special case in which the upper and the lower bounds match. Prior works on best arm identification have dealt with (a) independent and identically distributed observations from the arms, and (b) rested Markov arms, whereas our work deals with the more difficult setting of restless Markov arms.