Optimal Best Arm Identification with Fixed Confidence in Restless
  Bandits
P. N. Karthik Vincent Y. F. Tan Arpan Mukherjee Ali Tajer
We study best arm identification in a restless multi-armed bandit setting
with finitely many arms. The discrete-time data generated by each arm forms a
homogeneous Markov chain taking values in a common, finite state space. The
state transitions in each arm are captured by an ergodic transition probability
matrix (TPM) that is a member of a single-parameter exponential family of TPMs.
The real-valued parameters of the arm TPMs are unknown and belong to a given
space. Given a function $f$ defined on the common state space of the arms, the
goal is to identify the best arm -- the arm with the largest average value of
$f$ evaluated under the arm's stationary distribution -- with the fewest number
of samples, subject to an upper bound on the decision's error probability
(i.e., the fixed-confidence regime). A lower bound on the growth rate of the
expected stopping time is established in the asymptote of a vanishing error
probability. Furthermore, a policy for best arm identification is proposed, and
its expected stopping time is proved to have an asymptotic growth rate that
matches the lower bound. It is demonstrated that tracking the long-term
behavior of a certain Markov decision process and its state-action visitation
proportions are the key ingredients in analyzing the converse and achievability
bounds. It is shown that under every policy, the state-action visitation
proportions satisfy a specific approximate flow conservation constraint and
that these proportions match the optimal proportions dictated by the lower
bound under any asymptotically optimal policy. The prior studies on best arm
identification in restless bandits focus on independent observations from the
arms, rested Markov arms, and restless Markov arms with known arm TPMs. In
contrast, this work is the first to study best arm identification in restless
bandits with unknown arm TPMs.