# Unichain and Aperiodicity are Sufficient for Asymptotic Optimality of
Average-Reward Restless Bandits

Yige Hong<EMAIL_ADDRESS>0000-0001-8534-1063 Carnegie Mellon
UniversityPittsburghPennsylvaniaUSA15213 ,  Qiaomin Xie<EMAIL_ADDRESS>0000-0003-2834-6866 University of Wisconsin-MadisonMadisonWisconsinUSA53706 ,
Yudong Chen<EMAIL_ADDRESS>0000-0002-6416-5635 University of Wisconsin-
MadisonMadisonWisconsinUSA53706 and  Weina Wang<EMAIL_ADDRESS>0000-0001-6808-0156 Carnegie Mellon UniversityPittsburghPennsylvaniaUSA15213

(2024)

###### Abstract.

We consider the infinite-horizon, average-reward restless bandit problem in
discrete time. We propose a new class of policies that are designed to drive a
progressively larger subset of arms toward the optimal distribution. We show
that our policies are asymptotically optimal with an $O(1/\sqrt{N})$
optimality gap for an $N$-armed problem, provided that the single-armed
relaxed problem is unichain and aperiodic. Our approach departs from most
existing work that focuses on index or priority policies, which rely on the
Uniform Global Attractor Property (UGAP) to guarantee convergence to the
optimum, or a recently developed simulation-based policy, which requires a
Synchronization Assumption (SA).

††copyright: acmcopyright††journalyear: 2024††doi: XXXXXXX.XXXXXXX

##  1\. Introduction

Restless Bandits (RBs) (Whittle, 1988) is a class of stochastic sequential
decision-making problems with coupled components. An RB problem consists of
multiple arms, each associated with a Markov Decision Process (MDP) with two
actions: activating/pulling the arm or idling the arm. At each time step, the
decision maker, who has knowledge of the MDP parameters, observes the states
of all arms and decides which arms to activate. This decision is subject to a
_budget constraint_ , which requires that a fixed number of arms is activated
at every time step. The objective is to maximize the reward from all arms,
where the reward from each arm is a function of its state and action. We
illustrate the problem in Figure 1. The RB problem has a rich history and
wide-reaching applications. We refer the readers to the recent survey paper
(Niño-Mora, 2023) for a comprehensive overview of the literature.

Figure 1. The restless bandit problem with $N$ arms.

Solving for an optimal policy for the RB problem is known to be PSPACE-hard
(Papadimitriou and Tsitsiklis, 1999). However, it is possible to find
_asymptotically optimal_ policies in a computationally efficient manner in the
regime where the number of arms, $N$, grows large. A policy is said to be
asymptotically optimal if its _optimality gap_ is $o(1)$ as $N\to\infty$,
where the optimality gap is the difference between the average reward per arm
achieved by an optimal policy and that achieved by this policy. This large $N$
regime, introduced in the seminal papers on the renowned Whittle index policy
(Whittle, 1988; Weber and Weiss, 1990), has recently regained significant
attention. There has been a growing body of work that proposes new policies
and provides refined analysis of their optimality gaps, both in the infinite-
horizon average-reward setting and the finite-horizon or discounted-reward
setting (Verloop, 2016; Hu and Frazier, 2017; Zayas-Cabán et al., 2019; Brown
and Smith, 2020; Zhang and Frazier, 2021, 2022; Gast et al., 2023a, b; Hong et
al., 2023).

In this paper, we consider the $N$-armed RB problem where the budget
constraint requires $\alpha N$ arms to be activated for a fixed number
$\alpha\in(0,1)$. We focus on the _infinite-horizon, average-reward_ setting.
Most existing policies for this setting, including the Whittle index policy
(Whittle, 1988) and the more general LP-Priority policies (Verloop, 2016),
rely on an assumption called Uniform Global Attractor Property (UGAP) to
achieve asymptotic optimality (Weber and Weiss, 1990; Verloop, 2016; Gast et
al., 2023a, b). Roughly speaking, UGAP requires global convergence of the
mean-field dynamics for the RB system as $N\to\infty$. UGAP is a technical
condition and known to be difficult to verify for a given RB instance and
policy. Moreover, there are documented RB instances where the Whttile-index
and LP-priority policies fail to satisfy UGAP and are asymptotically
suboptimal (Gast et al., 2023a; Hong et al., 2023).

Recent work (Hong et al., 2023) takes a first step towards relaxing the long-
established UGAP assumption. This work proposes a policy named Follow-The-
Virtual-Advice (FTVA), which is asymptotic optimal under an alternative
condition named the synchronization assumption (SA). As argued in (Hong et
al., 2023), SA is more intuitive and easier-to-verify than UGAP. However, the
reliance on SA is still unsatisfactory; in particular, there exist RB
instances where SA is not satisfied and FTVA is suboptimal. We provide such an
example in Appendix A. More discussion on the roles of UGAP and SA is given in
Section 4.

The need for additional assumptions like UGAP and SA limits the applicability
of existing policies. More importantly, it highlights a critical gap in our
fundamental understanding of the restless bandit problem. As such, the
literature on RBs leaves open the following fundamental question: _Is it
possible to efficiently find a policy that achieves asymptotic optimality in
infinite-horizon, average-reward RBs under only standard unichain and
aperiodicity assumptions, without imposing any additional conditions?_

### Our contributions

#### Answer to the question.

In this paper, we give a definitive, affirmative answer to this long-standing
question. We propose three policies that are asymptotically optimal with an
$O(1/\sqrt{N})$ optimality gap under only standard unichain and aperiodicity
assumptions.

#### Policy design.

Our proposed policies depart from the prevalent _priority-based_ design of
most existing policies. A priority-based policy specifies a fixed priority
order over all the _states_ of a single arm. At each time step, the policy
pulls arms from states of higher priority to those of lower priority, until
the budget constraint is met. In contrast, each of our proposed policies
selects a subset of arms based on the _empirical distribution_ of their states
and lets the selected arms take their _ideal actions_ as much as possible.
These ideal actions are computed using the solution of a single-armed, budget-
relaxed problem. The subset selection is constructed in a way such that most
arms in the subset can take their ideal actions and the subset expands over
time.

#### Proof techniques.

We analyze the three proposed policies by viewing them as instances of a
broader class of policies we term _focus-set policies_. We establish a meta-
theorem that provides sufficient conditions for the asymptotic optimality of a
focus-set policy. The proof of the meta-theorem highlights a class of
bivariate Lyapunov functions we term _subset Lyapunov functions_ , along with
a global Lyapunov function constructed dynamically from one of the subset
Lyapunov functions. Using these Lyapunov functions, we show that, under the
stipulated sufficient conditions, the state-action distribution of arms in the
selected subset converges to the optimal distribution, and the subset
eventually expands to cover most arms. This meta-theorem allows us to prove
the asymptotic optimality of the three proposed policies by verifying the
stipulated sufficient conditions.

### Paper organization

The remainder of the paper is organized as follows. In Section 2, we set up
the problem of average-reward restless bandits and introduce the single-armed
problem. In Section 3, we present our main results, where we propose three
policies and establish their $O(1/\sqrt{N})$ optimality. In Section 4, we
discuss the UGAP and SA assumptions in prior work and the challenges in
relaxing them. In Section 5, we set up a framework: we first introduce a
broader class of policies termed focus-set policies, which includes our three
proposed policies as instances; we then present a meta-theorem, which provides
sufficient conditions for $O(1/\sqrt{N})$ optimality of focus-set policies. In
Section 6, we use this framework to prove the optimality of our first proposed
policy, the ID policy. Due to space constraints, the optimality results for
the other two policies are detailed in the appendices.

##  2\. Problem Setup

In this section, we set up the average-reward restless bandits problem and its
single-armed relaxation, and introduce the assumptions and notations used
throughout the paper.

###  2.1. The restless bandits problem

We consider the discrete-time, infinite-horizon restless bandit problem with
the average-reward criterion. The RB problem consists of $N$ homogeneous arms
and is henceforth referred to as the $N$-armed problem. Each arm is associated
with an MDP called the single-armed MDP, which is defined by the tuple
$(\mathbb{S},\mathbb{A},P,r)$. Here $\mathbb{S}$ is the state space, which is
a finite set; $\mathbb{A}=\\{0,1\\}$ is the action space, where the action $1$
is interpreted as activating or pulling the arm;
$P:\mathbb{S}\times\mathbb{A}\times\mathbb{S}\to[0,1]$ is the transition
kernel, where $P(s,a,s^{\prime})$ is the probability of transitioning to state
$s^{\prime}$ in the next time step conditioned on taking action $a$ at state
$s$ in the current step; $r:\mathbb{S}\times\mathbb{A}\to\mathbb{R}$ is the
reward function, where $r(s,a)$ is the expected reward for taking action $a$
in state $s$. Let $r_{\max}=\max_{s\in\mathbb{S},a\in\mathbb{A}}\left\lvert
r(s,a)\right\rvert$. The RB problem has a _budget constraint_ , which requires
that exactly $\alpha N$ arms must be pulled at every time step for some given
constant $\alpha\in(0,1)$. Here $\alpha N$ is assumed to be an integer for
simplicity. We focus on the setting where all the model parameters,
$\mathbb{S},\mathbb{A},P,r,\alpha$, are known.

We index the arms in an $N$-armed bandit by $[N]$, where
$[n]\triangleq\\{1,2,\dots,n\\}$. We refer to the index $i$ of Arm $i$ as its
_ID_ , to avoid confusion with the Whittle index or other index notions.

A policy $\pi$ for the $N$-armed problem chooses in each time step the action
for each of the $N$ arms, based on the current states of all arms and possibly
an internal state maintained by the policy. All the policies considered in
this paper have at most finitely many possible internal states.

Under a policy $\pi$, we use the _state vector_
$\bm{S}_{t}^{\pi}\triangleq(S_{t}^{\pi}(i))_{i\in[N]}\in\mathbb{S}^{N}$ to
represent the states of all arms, where $S_{t}^{\pi}(i)\in\mathbb{S}$ denotes
the state of the $i$-th arm at time $t$. Similarly, the _action vector_ is
defined as
$\bm{A}_{t}^{\pi}\triangleq(A_{t}^{\pi}(i))_{i\in[N]}\in\mathbb{A}^{N}$, where
$A_{t}^{\pi}(i)\in\mathbb{A}$ denotes the action applied to the $i$-th arm at
time $t$. We use $\bm{S}_{\infty}^{\pi}$ and $\bm{A}_{\infty}^{\pi}$ to denote
random elements following the steady-state distributions of $\bm{S}_{t}^{\pi}$
and $\bm{A}_{t}^{\pi}$, respectively.

The objective of the RB problem is to find a policy that maximizes the long-
run average of the expected reward from all $N$ arms:

(1) $\displaystyle\underset{\text{policy }\pi}{\text{maximize}}$
$\displaystyle\quad
R(\pi,N)\triangleq\lim_{T\to\infty}\frac{1}{T}\sum_{t=0}^{T-1}\frac{1}{N}\sum_{i\in[N]}\mathbb{E}\left[r(S_{t}^{\pi}(i),A_{t}^{\pi}(i))\right]$
(2) subject to $\displaystyle\quad\sum_{i\in[N]}A_{t}^{\pi}(i)=\alpha
N,\quad\forall t\geq 0.$

The objective can be equivalently written as
$R(\pi,N)=\frac{1}{N}\sum_{i\in[N]}\mathbb{E}\left[r(S_{\infty}^{\pi}(i),A_{\infty}^{\pi}(i))\right]$.
Let $R^{*}(N)\triangleq\sup_{\pi}R(\pi,N)$ denote the optimal value. The
optimality gap of a policy $\pi$ is defined as $R^{*}(N)-R(\pi,N)$. We say
that a policy $\pi$ is _asymptotically optimal_ if its optimality gap vanishes
as $N\to\infty$, i.e., $R^{*}(N)-R(\pi,N)=o(1)$.

We comment that although $R(\pi,N)$ and $R^{*}(N)$ may potentially depend on
the initial state vector $\bm{S}_{0}$, all our optimality gap upper bounds are
independent of $\bm{S}_{0}$. For simplicity we omit writing the dependency of
$R(\pi,N)$ and $R^{*}(N)$ on the $\bm{S}_{0}$.

###  2.2. Scaled state-count vector

We introduce an alternative way, used extensively in the paper, for
representing the information contained in the state vector $\bm{S}_{t}^{\pi}$.
For each subset $D\subseteq[N]$, we define the _scaled state-count vector on
$D$_ as $X_{t}^{\pi}(D)=(X_{t}^{\pi}(D,s))_{s\in\mathbb{S}}$, where

$X_{t}^{\pi}(D,s)=\frac{1}{N}\sum_{i\in
D}\mathbbm{1}\\!\left\\{S_{t}^{\pi}(i)=s\right\\}.$

Note that each entry of the vector $X_{t}^{\pi}(D)$ is the number of arms in
$D$ in a given state scaled by $1/N$. When $D=[N]$ is the set of all arms, we
simply call $X_{t}^{\pi}([N])$ the _scaled state-count vector_.

Sometimes we view $X_{t}^{\pi}(D)$ as a vector-valued function of
$D\subseteq[N]$. We refer to this function $X_{t}$ as the _system state_ at
time $t$. The system state $X_{t}^{\pi}$ contains the same information as the
state vector $\bm{S}_{t}^{\pi}$ does; in particular, from $X_{t}^{\pi}$ one
can deduce the state of each arm.

###  2.3. Single-armed problem

In this section, we discuss a relaxed version of the $N$-armed problem, which
plays an important role in our policy design and analysis. This relaxed
problem, which we called the _single-armed problem_ , aims to optimize the
long-run average reward in the single-armed MDP $(\mathbb{S},\mathbb{A},P,r)$
subject to a long-run average budget constraint. Specifically, the single-
armed problem is given by

(3) $\displaystyle\underset{{\bar{\pi}}}{\text{maximize}}$
$\displaystyle\quad\lim_{T\to\infty}\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\left[r(S_{t}^{\bar{\pi}}(1),A_{t}^{\bar{\pi}}(1))\right]$
(4) subject to
$\displaystyle\quad\lim_{T\to\infty}\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\left[A_{t}^{\bar{\pi}}(1)\right]=\alpha.$

Here ${\bar{\pi}}=({\bar{\pi}}(a|s))_{s\in\mathbb{S},a\in\mathbb{A}}$ denotes
a randomized Markovian policy for the single-armed MDP, where
${\bar{\pi}}(a|s)$ is the probability of taking action $a$ at state $s$;
$S_{t}^{\bar{\pi}}(1)$ and $A_{t}^{\bar{\pi}}(1)$ denote the state and action
of a typical arm (say, arm 1, without loss of generality) at time $t$. The
constraint (4) requires that the _average_ rate of applying the active action
is $\alpha$. The single-armed problem and its equivalent forms have been
considered in prior work (Weber and Weiss, 1990; Gast et al., 2023a, b;
Verloop, 2016).

For a single-armed policy ${\bar{\pi}}$, let $P_{\bar{\pi}}$ be the transition
kernel of the single-armed Markov chain induced by ${\bar{\pi}}$. Throughout
the paper, we impose the following assumption.

###### Assumption 1 (Unichain and aperiodicity).

The single-armed problem is unichain, i.e., any policy ${\bar{\pi}}$ of the
single-armed problem induces a unichain $P_{{\bar{\pi}}}$ on $\mathbb{S}$.
Moreover, any optimal policy ${{\bar{\pi}}^{*}}$ of the single-armed problem
induces an aperiodic unichain $P_{{{\bar{\pi}}^{*}}}$ on $\mathbb{S}$.

Under 1, the single-armed problem has been shown to be a relaxation of the
$N$-armed problem (1)–(2) (see, e.g., (Gast et al., 2023a)). Specifically, let
$R^{\textup{rel}}$ be the optimal value of the single-armed problem and recall
that $R^{*}(N)$ is the optimal value of the $N$-armed problem. Then we have
$R^{*}(N)\leq R^{\textup{rel}}$.

Here we comment on the roles of the unichain and the aperiodicity assumptions
in 1. The unichain assumption in 1 assumes that all policies induce unichains
in the single-armed problem. This ensures that the optimal value and the
optimal policy do not depend on the initial state distribution, which avoids
delving into the complication of multichain MDPs. We discuss relaxing this
all-policy unichain assumption in Appendix B. Additionally, aperiodicity is
necessary for the gap $R^{\textup{rel}}-R^{*}(N)$ to diminish as $N\to\infty$.
We give an example to demonstrate this necessity in Appendix C.

In the rest of this paper, we use ${{\bar{\pi}}^{*}}$ to denote an arbitrary
optimal single-armed policy; our results apply to any such
${{\bar{\pi}}^{*}}$. For any optimal single-armed policy ${{\bar{\pi}}^{*}}$,
we denote its steady-state distribution by
$\mu^{*}=(\mu^{*}(s))_{s\in\mathbb{S}}$, where $\mu^{*}(s)$ is the steady-
state probability of state $s$. The corresponding state-action distribution is
denoted by $y^{*}=(y^{*}(s,a))_{s\in\mathbb{S},a\in\mathbb{A}}$, where
$y^{*}(s,a)=\mu^{*}(s){{\bar{\pi}}^{*}}(a|s)$ is the steady-state probability
of the state-action pair $(s,a)$. Note that the relaxed budget constraint (4)
implies that $\sum_{s\in\mathbb{S}}y^{*}(s,1)=\alpha$.

With the notation above, the optimality gap of any $N$-armed policy $\pi$ can
be upper bounded as

(5) $R^{*}(N)-R(\pi,N)\leq
R^{\textup{rel}}-R(\pi,N)=\sum_{s\in\mathbb{S},a\in\mathbb{A}}r(s,a)y^{*}(s,a)-\frac{1}{N}\sum_{i\in[N]}\mathbb{E}\left[r(S_{\infty}^{\pi}(i),A_{\infty}^{\pi}(i))\right].$

#### Solving the single-armed problem via linear programming

By standard results on average-reward MDPs (Puterman, 2005), under 1, the
single-armed problem (3)–(4) is equivalent to the following linear program
(LP), where each decision variable $y(s,a)$ represents the steady-state
probability that the arm is in state $s$ and takes action $a$:

(LP)
$\displaystyle\underset{\\{y(s,a)\\}_{s\in\mathbb{S},a\in\mathbb{A}}}{\text{maximize}}\mspace{12.0mu}$
$\displaystyle\sum_{s\in\mathbb{S},a\in\mathbb{A}}r(s,a)y(s,a)$ (6) subject to
$\displaystyle\mspace{15.0mu}\sum_{s\in\mathbb{S}}y(s,1)=\alpha,$ (7)
$\displaystyle\sum_{s^{\prime}\in\mathbb{S},a\in\mathbb{A}}y(s^{\prime},a)P(s^{\prime},a,s)=\sum_{a\in\mathbb{A}}y(s,a),\quad\forall
s\in\mathbb{S},$ (8)
$\displaystyle\mspace{3.0mu}\sum_{s\in\mathbb{S},a\in\mathbb{A}}y(s,a)=1,\quad
y(s,a)\geq 0,\;\;\forall s\in\mathbb{S},a\in\mathbb{A}.$

Here (6) is the relaxed budget constraint, and (7)–(8) ensures that
$(y(s,a))_{s\in\mathbb{S},a\in\mathbb{A}}$ is a valid steady-state
distribution. Given an optimal solution
$\\{y^{*}(s,a)\\}_{s\in\mathbb{S},a\in\mathbb{A}}$ to the above LP, one can
construct an optimal policy single-armed policy ${{\bar{\pi}}^{*}}$ as
follows:

(9)
${{\bar{\pi}}^{*}}(a|s)=\begin{cases}y^{*}(s,a)/(y^{*}(s,0)+y^{*}(s,1)),&\text{if
}y^{*}(s,0)+y^{*}(s,1)>0,\\\ 1/2,&\text{if
}y^{*}(s,0)+y^{*}(s,1)=0.\end{cases}\quad\text{for $s\in\mathbb{S}$,
$a\in\mathbb{A}$.}$

###  2.4. Additional notation

For a subset $D\subseteq[N]$, we let $m(D)=|D|/N$ denote the fraction of arms
contained in $D$. We introduce a convenient shorthand
$[0,1]_{N}=\\{0,1/N,2/N,\dots,1\\}$. Then $m(D)\in[0,1]_{N}$ for any $D$. Let
$\Delta(\mathbb{S})$ denote the set of probability distributions on the state
space $\mathbb{S}$. We treat each distribution $v\in\Delta(\mathbb{S})$ as a
row vector. Recall that $\pi$ denotes a policy for the $N$-armed problem. In
later sections, when the context is clear, we drop the superscript $\pi$ from
the vectors $\bm{S}_{t}^{\pi}$, $\bm{A}_{t}^{\pi}$, and $X_{t}^{\pi}$.

##  3\. Main results: Policies and Optimality Guarantees

In this section, we propose policies for the average-reward RB problems and
bound their optimality gaps. Before delving into the $N$-armed restless bandit
system, we first study the distributional convergence in the single-armed
system, which provides a conceptual basis for our policy design in the
$N$-armed system. We then present the three proposed policies for the
$N$-armed problem: the ID policy, the set-expansion policy, and the set-
optimization policy. We show that under the unichain and aperiodicity
assumption, all three policies are $O(1/\sqrt{N})$ optimal.

###  3.1. Convergence to the optimal steady-state distribution in the single-
armed system

Consider the single-armed system and any optimal single-armed policy
${{\bar{\pi}}^{*}}$. Since the transition kernel $P_{{\bar{\pi}}^{*}}$ is an
aperiodic unichain by 1, we know that starting from any initial distribution
in $\Delta(\mathbb{S})$, the state distribution of the Markov chain
$P_{{\bar{\pi}}^{*}}$ converges to the steady-state distribution $\mu^{*}$. In
our analysis, it is convenient to witness this convergence in each time step
and quantify the convergence rate. For this purpose, we introduce a matrix $W$
and consider the $W$-weighted $L_{2}$ norm on $\mathbb{S}$.

###### Definition 0.

Let $W$ be an $|\mathbb{S}|$-by-$|\mathbb{S}|$ matrix given by

(10)
$W=\sum_{k=0}^{\infty}(P_{{\bar{\pi}}^{*}}-\Xi)^{k}(P_{{\bar{\pi}}^{*}}^{\top}-\Xi^{\top})^{k},$

where $\Xi$ is an $|\mathbb{S}|$-by-$|\mathbb{S}|$ matrix with each row being
$\mu^{*}$. Let $\lambda_{W}$ denote maximal eigenvalue of $W$.

The matrix $W$ is well-defined and positive definite with eigenvalues in the
range $[1,\lambda_{W}]$, as shown in Section D.1. Lemma 2 below states a
refined convergence result that we use in our analysis. In particular, it
implies that the distance to the steady-state distribution shrinks in every
time step. This lemma is proved in Section D.1 using basic matrix analysis
arguments.

###### Lemma 0 (Pseudo-contraction under the $W$-weighted $L_{2}$ norm).

Suppose $P_{{\bar{\pi}}^{*}}$ is an aperiodic unichain on $\mathbb{S}$. For
any distribution $v\in\Delta(\mathbb{S})$, we have

(11)
$\left\lVert(v-\mu^{*})P_{{\bar{\pi}}^{*}}\right\rVert_{W}\leq\Big{(}1-\frac{1}{2\lambda_{W}}\Big{)}\left\lVert
v-\mu^{*}\right\rVert_{W},$

where $\left\lVert\cdot\right\rVert_{W}$ is the $W$-weighted $L_{2}$ norm,
i.e., $\left\lVert u\right\rVert_{W}=\sqrt{uWu^{\top}}$ for any row vector
$u$.

#### Algorithmic idea based on convergence under kernel $P_{{\bar{\pi}}^{*}}$.

Our policies for the $N$-armed problem are inspired by the following
observation based on the convergence to the optimal state distribution
$\mu^{*}$ under the kernel $P_{{\bar{\pi}}^{*}}$. Let us ignore the budget
constraint for now and let the $N$ arms independently follow
${{\bar{\pi}}^{*}}$. Then the state-action distribution of each arm converges
to the steady-state distribution
$y^{*}(s,a)=\mu^{*}(s){{\bar{\pi}}^{*}}(a|s)$. As a result, each arm’s
expected reward converges to
$\sum_{s\in\mathbb{S},a\in\mathbb{A}}r(s,a)y^{*}(s,a)=R^{\textup{rel}}$ and
its expected budget usage converges to
$\sum_{s\in\mathbb{S}}y^{*}(s,1)=\alpha$. Moreover, the total budget usage of
the $N$ arms concentrates around $\alpha N$ due to their independence.
Therefore, after a burn-in period, the $N$ arms achieve the reward upper bound
$R^{\textup{rel}}$ while approximately meeting the hard budget constraint.
Note that this convergence does not require assumptions beyond the unichain
and aperiodicity assumption.

Inspired by this observation, a natural idea is to let most arms in the
$N$-armed system follow ${{\bar{\pi}}^{*}}$. However, the hard budget
constraint limits the number of arms that can carry out ${{\bar{\pi}}^{*}}$.
Our idea is to first prioritize a smaller subset of $n<N$ arms and guarantee
that most arms in this subset are able to follow ${{\bar{\pi}}^{*}}$. Once
these arms’ state distributions converge to $\mu^{*}$, their budget usage
concentrates around $\alpha n$, which leaves budget to allow more arms to
follow ${{\bar{\pi}}^{*}}$. This way, we progressively expand the subset of
arms that can follow ${{\bar{\pi}}^{*}}$. To materialize this idea, the
primary challenge lies in choosing the correct subset of arms to follow
${{\bar{\pi}}^{*}}$, a problem we address through our policies.

To implement the idea of “prioritizing a subset of arms to follow
${{\bar{\pi}}^{*}}$”, each of our policies samples an _ideal action_
$\widehat{A}_{t}(i)$ using ${{\bar{\pi}}^{*}}$ for each arm $i\in[N]$ based on
its state $S_{t}(i)$ at time $t$. Then the policy selects a subset of arms and
gives them precedence to set $A_{t}(i)=\widehat{A}_{t}(i)$.

###  3.2. The ID Policy

We first introduce the ID policy, the most straightforward among the three
proposed policies. The pseudocode is given in Algorithm 1. As described in the
previous section, the policy first samples an ideal action
$\widehat{A}_{t}(i)$ for each arm $i\in[N]$ using ${{\bar{\pi}}^{*}}$. To
decide the actual actions $A_{t}(i)$’s, the ID policy prioritizes arms with
smaller IDs (i.e., smaller $i$’s). In particular, the policy goes through the
arms $i=1,2,\dots,N$ sequentially and assigns $A_{t}(i)=\widehat{A}_{t}(i)$
for as many arms as allowed by the budget constraint. The assignment continues
until the remaining arms with larger IDs are forced to all take one action
($0$ or $1$). This procedure of deciding $A_{t}(i)$’s based on
$\widehat{A}_{t}(i)$’s is referred to as _action rectification_.

Algorithm 1 ID policy

Input: number of arms $N$, budget $\alpha N$, an optimal single-armed policy
${{\bar{\pi}}^{*}}$,

initial system state $X_{0}$, initial state vector $\bm{S}_{0}$

1:for $t=0,1,\dots$ do

2: Independently sample
$\widehat{A}_{t}(i)\sim{{\bar{\pi}}^{*}}(\cdot|S_{t}(i))$ for $i\in[N]$
$\triangleright$ _Action sampling_

3: if $\sum_{i\in[N]}\widehat{A}_{t}(i)\geq\alpha N$ then $\triangleright$
_Action rectification_

4: $N^{{\bar{\pi}}^{*}}_{t}\leftarrow\max\\{n\leq
N\colon\sum_{i\in[n]}\widehat{A}_{t}(i)\leq\alpha N\\}$

5: $A_{t}(i)\leftarrow\widehat{A}_{t}(i)$ for $i\in[N^{{\bar{\pi}}^{*}}_{t}]$,
$A_{t}(i)\leftarrow 0$ for $i\notin[N^{{\bar{\pi}}^{*}}_{t}]$

6: else

7: $N^{{\bar{\pi}}^{*}}_{t}\leftarrow\max\\{n\leq
N\colon\sum_{i\in[n]}(1-\widehat{A}_{t}(i))\leq(1-\alpha)N\\}$

8: $A_{t}(i)\leftarrow\widehat{A}_{t}(i)$ for $i\in[N^{{\bar{\pi}}^{*}}_{t}]$,
$A_{t}(i)\leftarrow 1$ for $i\notin[N^{{\bar{\pi}}^{*}}_{t}]$

9: Apply $A_{t}(i)$ for each arm $i\in[N]$ and observe $S_{t+1}(i)$

###### Theorem 3 (Optimality gap of ID policy).

Consider an $N$-armed restless bandit problem with the single-armed MDP
$(\mathbb{S},\mathbb{A},P,r)$ and budget $\alpha N$ for $0<\alpha<1$. Assume
that the single-armed problem is unichain and any optimal single-armed policy
induces an aperiodic unichain (1). Let $\pi$ be the ID policy (Algorithm 1).
The optimality gap of $\pi$ is bounded as

(12)
$R^{*}(N)-R(\pi,N)\leq\frac{672r_{\max}\lambda_{W}^{5/2}|\mathbb{S}|^{3/2}}{\beta^{3}\sqrt{N}},$

where $\beta=\min\\{\alpha,1-\alpha\\}$, and $\lambda_{W}$ is the largest
eigenvalue of the matrix $W$ (Definition 1).

The optimality gap in Theorem 3 is $O(1/\sqrt{N})$. Here we did not seek to
optimize the dependency on the constants.

The ID policy stands out for its simplicity and asymptotic optimality.
However, the reliance on arm IDs may be perceived as somewhat artificial and
rigid. In response to this limitation, our next two policies are designed to
be ID-oblivious.

###  3.3. Set-expansion policy

We introduce the second policy, the set-expansion policy, given in Algorithm
2. The policy explicitly maintains a subset $D_{t}$, referred to as a _focus
set_ , and prioritizes letting arms in $D_{t}$ follow ${{\bar{\pi}}^{*}}$. In
each time step, the policy attempts to expand $D_{t}$ from $D_{t-1}$ based on
a quantity called _slack_. The slack is a function of a system state $x$ and a
subset $D\subseteq[N]$, defined as

(13) $\delta(x,D)=\beta(1-m(D))-\left\lVert x(D)-m(D)\mu^{*}\right\rVert_{1},$

where we recall that $m(D)=|D|/N$. The policy aims to choose $D_{t}$ such that
$D_{t}\supseteq D_{t-1}$ and $D_{t}$ is a maximal set with
$\delta(X_{t},D_{t})\geq 0$. But sometimes this is impossible, in which case
the policy settles for the largest set $D_{t}$ with $D_{t}\subseteq D_{t-1}$
and $\delta(X_{t},D_{t})\geq 0$.

The action rectification in the set-expansion policy ensures that $\sum_{i\in
D_{t}}A_{t}(i)\leq\alpha N$ and $\sum_{i\in
D_{t}}(1-A_{t}(i))\leq(1-\alpha)N$, so that it is possible to choose
$A_{t}(i)$’s for $i\notin D_{t}$ to satisfy $\sum_{i\in[N]}A_{t}(i)=\alpha N$.

Algorithm 2 Set-expansion policy

Input: number of arms $N$, budget $\alpha N$, an optimal single-armed policy
${{\bar{\pi}}^{*}}$,

initial system state $X_{0}$, initial state vector $\bm{S}_{0}$, initial focus
set $D_{-1}=\emptyset$

1:for $t=0,1,\dots$ do

2: if $\delta(X_{t},D_{t-1})>0$ then $\triangleright$ _Set update_

3: Let $D_{t}$ be any maximal set such that $D_{t}\supseteq D_{t-1}$ and
$\delta(X_{t},D_{t})\geq 0$

4: else

5: Let $D_{t}$ be any set with the largest $m(D_{t})$ such that
$D_{t}\subseteq D_{t-1}$ and $\delta(X_{t},D_{t})\geq 0$

6: Independently sample
$\widehat{A}_{t}(i)\sim{{\bar{\pi}}^{*}}(\cdot|S_{t}(i))$ for $i\in[N]$
$\triangleright$ _Action sampling_

7: if $\sum_{i\in D_{t}}\widehat{A}_{t}(i)\geq\alpha N$ then $\triangleright$
_Action rectification_

8: Uniformly select $\big{\lceil}\sum_{i\in D_{t}}\widehat{A}_{t}(i)-\alpha
N\big{\rceil}$ arms in $D_{t}$ with $\widehat{A}_{t}(i)=1$, set
$A_{t}(i)\leftarrow 0$

9: For the rest of $i\in D_{t}$, set $A_{t}(i)\leftarrow\widehat{A}_{t}(i)$

10: else

11: Uniformly select $\big{\lceil}\big{(}\sum_{i\in
D_{t}}(1-\widehat{A}_{t}(i))-(1-\alpha)N\big{)}^{+}\big{\rceil}$ arms in
$D_{t}$ with $\widehat{A}_{t}(i)=0$

12: For selected arms in $D_{t}$, set $A_{t}(i)\leftarrow 1$

13: For the rest of $i\in D_{t}$, set $A_{t}(i)\leftarrow\widehat{A}_{t}(i)$

14: Set $A_{t}(i)$’s for $i\notin D_{t}$ such that
$\sum_{i\in[N]}A_{t}(i)=\alpha N$

15: Apply $A_{t}(i)$ for each arm $i\in[N]$ and observe $S_{t+1}(i)$

As will be made precise in our analysis (Appendix F), the non-negativity of
the slack ensures that most arms in the $D_{t}$ can follow
${{\bar{\pi}}^{*}}$; moreover, since the $L_{1}$ distance $\left\lVert
x(D)-m(D)\mu^{*}\right\rVert_{1}$ used to define the slack is non-expansive
under $P_{{\bar{\pi}}^{*}}$, the focus set $D_{t}$ is almost non-shrinking in
expectation. We remark that the focus set is a common structure in our three
policies, even though its use is not immediately obvious in the ID policy. The
above properties of the focus set are also shared by the three policies. We
will establish a unified framework in Section 5 to analyze these policies.

###### Theorem 4 (Optimality gap of set-expansion policy).

Consider an $N$-armed restless bandit problem with the single-armed MDP
$(\mathbb{S},\mathbb{A},P,r)$ and budget $\alpha N$ for $0<\alpha<1$. Assume
that the single-armed problem is unichain and any optimal single-armed policy
induces an aperiodic unichain (1). Let $\pi$ be the set-expansion policy
(Algorithm 2). The optimality gap of $\pi$ is bounded as

(14)
$R^{*}(N)-R(\pi,N)\leq\frac{524r_{\max}\lambda_{W}^{2}|\mathbb{S}|^{2}}{\beta^{2}\sqrt{N}},$

where $\beta=\min\\{\alpha,1-\alpha\\}$, and $\lambda_{W}$ is the largest
eigenvalue of the matrix $W$ (Definition 1).

Theorem 4 again shows an $O(1/\sqrt{N})$ optimality gap. The proof is given in
Section F.

###  3.4. Set-optimization policy

To motivate our third policy, we make an observation on the ID policy and the
set-expansion policy. As the $N$ arms are homogeneous, one would expect that
the state of the system at time $t$ is fully captured by the scaled state-
count vector $X_{t}([N])$, which is the empirical distribution of arm states.
These two policies, however, operate in an augmented state space: in addition
to $X_{t}([N])$, the ID policy relies on the arm IDs, and the set-expansion
policy maintains the focus set $D_{t}$ as part of its state. It is then
natural to ask whether there exists an asymptotically optimal policy that
makes decisions solely based on $X_{t}([N])$.

We propose such a policy, the set-optimization policy, given in Algorithm 3.
The set-optimization policy is similar to the set-expansion policy in that
they both choose a focus set $D_{t}$ in each time step and give priority to
arms in $D_{t}$ to follow their ideal actions. However, they differ in how
$D_{t}$ is chosen. In the set-optimization policy, $D_{t}$ is updated by
solving an optimization problem (15)-(16). In this problem, $h_{W}(x,D)$ is a
function of system state $x$ and subset $D\subseteq[N]$ given by
$h_{W}(x,D)=\left\lVert X_{t}(D)-m(D)\mu^{*}\right\rVert_{W}$,
$L_{W}=2\lambda_{W}^{1/2}$, and the slack $\delta(x,D)$ is the same notion as
in (13). Importantly, $D_{t}$ is chosen to be a _maximal_ optimal solution in
the sense that there is no other optimal solution $D^{\prime}$ that contains
$D_{t}$. When there are multiple maximal optimal solutions, $D_{t}$ is picked
uniformly at random.

We remark that it appears that the optimization problem (15)-(16) requires
evaluating $X_{t}(D)$ for a specific subset $D$ and selecting arms by their
IDs. However, a closer examination can reveal that this problem can be solved
solely based on $X_{t}([N])$, leading to an ID-oblivious solution. To see
this, observe that $h_{W}(x,D)$ only depends on state counts, and $m(D)$ is
determined by the number of arms in $D$. Therefore, the solution boils down to
a sequence of numbers representing the numbers of arms in different states.

Algorithm 3 Set-optimization policy

Input: number of arms $N$, budget $\alpha N$, an optimal single-armed policy
${{\bar{\pi}}^{*}}$,

initial system state $X_{0}$, initial state vector $\bm{S}_{0}$

1:for $t=0,1,\dots$ do

2: Let $D_{t}$ be a maximal optimal solution to the problem below:
$\triangleright$ _Set update_ (15) $\displaystyle D_{t}\leftarrow$
$\displaystyle\arg\min_{D\subseteq[N]}h_{W}(X_{t},D)+L_{W}\big{(}1-m(D)\big{)}$
(16) $\displaystyle\text{subject to }\delta(X_{t},D)\geq 0$

3: Run the same action sampling and action rectification as in lines 6–14 of
Algorithm 2

4: Apply $A_{t}(i)$ for each arm $i\in[N]$ and observe $S_{t+1}(i)$

###### Theorem 5 (Optimality gap of set-optimization policy).

Consider an $N$-armed restless bandit problem with the single-armed MDP
$(\mathbb{S},\mathbb{A},P,r)$ and budget $\alpha N$ for $0<\alpha<1$. Assume
that the single-armed problem is unichain and any optimal single-armed policy
induces an aperiodic unichain (1). Let $\pi$ be the set-optimization policy
(Algorithm 3). The optimality gap of $\pi$ is bounded as

(17)
$R^{*}(N)-R(\pi,N)\leq\frac{524r_{\max}\lambda_{W}^{2}|\mathbb{S}|^{2}}{\beta^{2}\sqrt{N}},$

where $\beta=\min\\{\alpha,1-\alpha\\}$, and $\lambda_{W}$ is the largest
eigenvalue of the matrix $W$ (Definition 1).

Theorem 5 again shows an $O(1/\sqrt{N})$ optimality gap. The proof is given in
Section G.

##  4\. Roles of UGAP and SA in Prior Work

In this section, we discuss why previous work relies on additional assumptions
like UGAP and SA to establish asymptotic optimality.

#### Priority-based policies and the uniform global asstractor (UGAP)
assumption

As previously mentioned, most existing work on average-reward RBs focuses on
policies that set a priority order over single-armed states (Whittle, 1988;
Weber and Weiss, 1990; Verloop, 2016; Gast et al., 2023a, b). These policies
require the UGAP assumption to achieve asymptotic optimality. UGAP is a
condition on the mean-field dynamics under a policy, typically in the form of
a difference equation $\mu_{t+1}-\mu_{t}=\mu_{t}\cdot f(\mu_{t})$ for some
function $f(\cdot)$. Here $\mu_{t}\in\Delta(\mathbb{S})$ can be thought of as
the state distribution of a randomly chosen arm at time $t$. The optimal state
distribution, $\mu^{*}$, is an equilibrium of this difference equation. But
this difference equation may have other equilibria. UGAP essentially requires
that $\mu^{*}$ is the only equilibrium and $\mu_{t}\to\mu^{*}$ as $t\to\infty$
in a uniform sense. In the context of restless bandits, without UGAP, if the
scaled state-count vector $X_{t}([N])$ deviates from $\mu^{*}$ too much, the
policy may not be able to drive it back to $\mu^{*}$. Instead, $X_{t}([N])$
may converge to a suboptimal steady-state distribution (see Section 3.3 of
(Hong et al., 2023)) or to a limit cycle (see Appendix E of (Gast et al.,
2023a)). We comment that global attractor conditions are commonly required
(either assumed or proved) in the mean-field analysis of large stochastic
systems (see, e.g., (Ying, 2016; Gast, 2017; Gast and Van Houdt, 2017;
Mukherjee et al., 2017; Vasantam et al., 2019; Rutten and Mukherjee, 2023)).

#### Follow-the-virtual-advice (FTVA) and the synchronization assumption (SA)

Recent work (Hong et al., 2023) proposes a new, non-priority-based policy
named Follow-the-Virtual-Advice (FTVA), which achieves asymptotic optimality
without UGAP but under an alternative assumption termed SA. FTVA is a
simulation-based policy; it simulates a virtual $N$-armed system where each
arm independently follows the single-armed optimal policy ${{\bar{\pi}}^{*}}$,
without any budget constraints. FTVA then lets the real actions follow the
virtual actions as much as possible, driving the real states of most arms to
be equal to their virtual states. However, due to the hard budget constraint,
some arms may not be able to align their real actions with virtual actions.
Then the real states of these arms may deviate from their virtual states. For
these “bad arms”, FTVA does not carry out any special treatment when
determining the real actions. Rather, it waits for them to turn “good” on
their own, which is guaranteed to happen soon enough by SA.

In contrast, the policies we propose in this paper take a more active approach
towards reducing the number of arms that cannot follow ${{\bar{\pi}}^{*}}$.
Roughly speaking, once the arms in a focus set converge to the optimal state
distribution $\mu^{*}$, a proposed policy makes use of the residual budget to
let additional arms outside of the focus set follow ${{\bar{\pi}}^{*}}$,
transitioning them to a “good” status. Our proposed policies carefully control
this focus-set process and are able to expand the focus set to cover most arms
in steady state, relying solely on the unichain and aperiodicity assumption.
The effectiveness of this approach proves that conditions like UGAP and SA are
not necessary for achieving $O(1/\sqrt{N})$ optimality.

##  5\. The focus-set approach and a meta-theorem

In this section, we introduce a general class of policies called _focus-set
policies_ , which subsumes the three policies defined in Section 3. Unlike
priority policies, which focus on the states of individual arms, the focus-set
policies center around a set of arms and the joint distribution of their
states. We establish a meta-theorem, Theorem 2, which provides sufficient
conditions for a focus-set policy to have an $O(1/\sqrt{N})$ optimality gap.

In the subsequent sections, we verify that these conditions are satisfied by
the ID policy and the set-expansion policy under the unichain and aperiodicity
assumption, thereby proving the optimality gap bounds in Theorem 3 and Theorem
4. While Theorem 5 for the set-optimization policy is not formally a corollary
of the meta-theorem, its proof uses the same ideas and in particular follows
from a comparison argument with the set-expansion policy.

###  5.1. Focus-set policies

In Algorithm 4, we provide the general template for focus-set policies. In
each time step $t$, the policy chooses a set $D_{t}$ of arms called _focus
set_ (Line 2), and for each arm $i\in D_{t}$ it samples an ideal action
$\widehat{A}_{t}(i)$ by applying the single-armed optimal policy
${{\bar{\pi}}^{*}}$ to the state of the arm (Line 3). The policy then tries to
let the arms in $D_{t}$ take the actions $\widehat{A}_{t}(i)$ from
${{\bar{\pi}}^{*}}$, but may need to adjust the actions for some arms due to
the budget constraint (Line 4). Finally, the policy chooses the actions for
the remaining arms outside $D_{t}$ in a way that obeys the budget constraint
(19), which is always doable when the requirement (18) on line 4 is satisfied.

Algorithm 4 Focus-set policies

Input: number of arms $N$, budget $\alpha N$, an optimal single-armed policy
${{\bar{\pi}}^{*}}$,

initial system state $X_{0}$, initial state vector $\bm{S}_{0}$, initial focus
set $D_{-1}$

1:for $t=0,1,\dots$ do

2: Choose a _focus set_ $D_{t}\subseteq[N]$ based on $X_{t}$ and $D_{t-1}$
$\triangleright$ _Set update_

3: Independently sample
$\widehat{A}_{t}(i)\sim{{\bar{\pi}}^{*}}(\cdot|S_{t}(i))$ for $i\in[N]$
$\triangleright$ _Action sampling_

4: Pick $A_{t}(i)$ for $i\in D_{t}$ based on $\widehat{\bm{A}}_{t},X_{t}$ and
$D_{t}$ such that $\triangleright$ _Action rectification_ (18) $\alpha
N-(N-|D_{t}|)\leq\sum_{i\in D_{t}}A_{t}(i)\leq\alpha N$

5: Pick $A_{t}(i)$ for $i\in D_{t}^{c}$ based on $X_{t}$ and $D_{t}$ such that
(19) $\sum_{i\in[N]}A_{t}(i)=\alpha N$

6: Apply $A_{t}(i)$ for each arm $i\in[N]$ and observe the new state
$\bm{S}_{t+1}$

Each specific focus-set policy is defined by specifying how the focus set
$D_{t}$ is chosen and how the rectification and action selection outside
$D_{t}$ are done. The most crucial step is choosing $D_{t}$. A good choice is
such that most arms in $D_{t}$ can take the actions generated by
${{\bar{\pi}}^{*}}$ under the budget constraint and that the set $D_{t}$
eventually expands to contain almost all $N$ arms.

It is easy to see that the set-expansion and set-optimization policies in
Section 3 belong to the class of focus-set policies. The same is true but less
obvious for the ID policy, which does not explicitly specify the set $D_{t}$.
Roughly speaking, the ID policy chooses $D_{t}$ to be approximately a subset
of $[N^{{\bar{\pi}}^{*}}_{t}]$, where $N^{{\bar{\pi}}^{*}}_{t}$ is defined in
Algorithm 1 and corresponds to the largest number such that the first
$N^{{\bar{\pi}}^{*}}_{t}$ arms can all follow ${{\bar{\pi}}^{*}}$; we postpone
the exact expression of $D_{t}$ to Section 6.2.

###  5.2. Meta-theorem on the $O(1/\sqrt{N})$ optimality gap of focus-set
policies

We now state a set of conditions which, once satisfied by a focus-set policy,
guarantees an $O(1/\sqrt{N})$ optimality gap.

To begin with, we define a class of functions called the subset Lyapunov
functions, which are indexed by a collection of subsets $D\subseteq[N]$. The
subset Lyapunov function indexed by $D$ upper bounds the distance between
$x(D)$ and $m(D)\mu^{*}$, and decreases geometrically if the arms in $D$
follow the optimal single-armed policy ${{\bar{\pi}}^{*}}$ indefinitely. In
the definition below, recall that $X_{t}$ denotes the system state at time
$t$.

###### Definition 0 (Subset Lyapunov functions).

Let $\mathcal{D}$ be a collection of subsets of $[N]$. Consider a class of
functions $\\{h(\cdot,D)\colon D\in\mathcal{D}\\}$, where each $h(\cdot,D)$
maps a system state $x$ to a real value _that depends only on the states of
the arms in $D$._ This class of functions is called the _subset Lyapunov
functions_ for the policy ${{\bar{\pi}}^{*}}$ if they satisfy the following
conditions:

  1. (1)

(Drift condition for a fixed $D$). There exist constants $\rho_{2}\in(0,1)$
and $K_{\textup{drift}}>0$ such that for any $D\in\mathcal{D}$ and any system
state $x$,

(20)
$\mathbb{E}\big{[}h(X_{1},D)\,\big{|}\,X_{0}=x,A_{0}(i)\sim{{\bar{\pi}}^{*}}(\cdot|S_{0}(i))\,\forall
i\in D\big{]}\leq\rho_{2}h(x,D)+\frac{K_{\textup{drift}}}{\sqrt{N}}.$

  2. (2)

(Distance domination). There exists a constant $K_{\textup{dist}}>0$ such that
for any $D\in\mathcal{D}$ and any system state $x$,

(21) $h(x,D)\geq K_{\textup{dist}}\left\lVert
x(D)-m(D)\mu^{*}\right\rVert_{1}.$

  3. (3)

(Lipschitz continuity in $D$). There exists a constant $L_{h}>0$ such that for
any $D,D^{\prime}\in\mathcal{D}$ with $D\subseteq D^{\prime}$ and any system
state $x$,

(22) $\left\lvert h(x,D^{\prime})-h(x,D)\right\rvert\leq
L_{h}\big{(}m(D^{\prime})-m(D)\big{)}.$

As an example, the class of functions $\\{h_{W}(x,D)\\}_{D\subseteq[N]}$ with
$h_{W}(x,D)=\left\lVert x(D)-m(D)\mu^{*}\right\rVert_{W}$ satisfies the
definition of subset Lyapunov functions, which we verify in Section D.2.

While the subset Lyapunov function $h(\cdot,D)$ is constructed to witness the
convergence of $X_{t}(D)$ to $m(D)\mu^{*}$ for a _fixed_ set $D$, in a focus-
set policy, the set $D_{t}$ is not fixed but rather is chosen dynamically.
Below we introduce three conditions on $D_{t}$, which would allow us to use
the subset Lyapunov functions to establish the asymptotic optimality of a
focus set policy.

Condition 1 requires that most arms in the focus set $D_{t}$ conform to the
actions sampled from ${{\bar{\pi}}^{*}}$.

###### Condition 1 (Majority conformity).

Let $K_{\textup{conf}}>0$ be a constant. For any $t\geq 0$, with probability
$1$, there exists $D_{t}^{\prime}\subseteq D_{t}$ such that for any $i\in
D_{t}^{\prime}$, the policy chooses $A_{t}(i)=\widehat{A}_{t}(i)$, and

(23) $\mathbb{E}\big{[}m(D_{t}\backslash
D_{t}^{\prime})\,\big{|}\,X_{t},D_{t}\big{]}\leq\frac{K_{\textup{conf}}}{\sqrt{N}}\quad
a.s.$

Condition 2 requires that $D_{t}$ changes in a set-inclusive manner and does
not shrink much in expectation.

###### Condition 2 (Almost non-shrinking).

For any $t\geq 0$, either $D_{t+1}\supseteq D_{t}$ or $D_{t+1}\subseteq
D_{t}$. Moreover, there exists a constant $K_{\textup{mono}}>0$ such that for
any $t\geq 0$,

(24)
$\mathbb{E}\big{[}\big{(}m(D_{t})-m(D_{t+1})\big{)}^{+}\,\big{|}\,X_{t},D_{t}\big{]}\leq\frac{K_{\textup{mono}}}{\sqrt{N}}\quad
a.s.$

Condition 3 requires that $m(D_{t})$, the fraction of arms covered by $D_{t}$,
is sufficiently large with respect to a subset Lyapunov function on $D_{t}$.

###### Condition 3 (Sufficient coverage).

There exist a class of subset Lyapunov functions $\\{h(\cdot,D)\colon
D\in\mathcal{D}\\}$ and constants $L_{\textup{cov}}>0,K_{\textup{cov}}>0$ such
that for any $t\geq 0$,

(25) $1-m(D_{t})\leq
L_{\textup{cov}}h(X_{t},D_{t})+\frac{K_{\textup{cov}}}{\sqrt{N}}\quad a.s.$

Note that Conditions 1 and 2 are generally easier to satisfy when the focus
set $D_{t}$ is small, where Condition 3 requires $D_{t}$ to be large.

We are now ready to state the meta-theorem, which establishes an
$O(1/\sqrt{N})$ bound on the optimality gap of a focus-set policy that
satisfies the above conditions.

###### Theorem 2 (Meta-theorem on optimality gap of set-focus policies).

Consider an $N$-armed restless bandit problem with the single-armed MDP
$(\mathbb{S},\mathbb{A},P,r)$ and budget $\alpha N$ for $0<\alpha<1$. Assume
that the single-armed problem is unichain and any optimal single-armed policy
induces an aperiodic unichain (1). Let $\pi$ be a focus-set policy given in
Algorithm 4. If $\pi$ satisfies Conditions 1, 2, and 3 for a class of subset
Lyapunov functions $\\{h(\cdot,D)\\}_{D\in\mathcal{D}}$, then

(26) $R^{*}(N)-R(\pi,N)\leq
r_{\max}\left(\Big{(}\frac{1}{K_{\textup{dist}}}+\frac{2}{L_{h}}\Big{)}\frac{K_{1}}{1-\rho_{1}}+2K_{\textup{conf}}\right)\frac{1}{\sqrt{N}},$

where $\rho_{1}=1-\frac{1-\rho_{2}}{1+L_{h}L_{\textup{cov}}}$ and
$K_{1}=K_{\textup{drift}}+2L_{h}K_{\textup{conf}}+2L_{h}K_{\textup{mono}}+\frac{1-\rho_{2}}{1+L_{h}L_{\textup{cov}}}K_{\textup{cov}}$.

###  5.3. Proof of Theorem 2

###### Proof of Theorem 2.

Our proof is structured into two steps: understanding the optimality gap, and
bounding the Lyapunov function.

##### Understanding the optimality gap.

Recall that the optimality gap can be upper bounded as $R^{*}(N)-R(\pi,N)\leq
R^{\textup{rel}}-R(\pi,N)$, where $R^{\textup{rel}}$ is the expected reward
associated with the optimal steady-state state-action distribution
$y^{*}=(y^{*}(s,a))_{s\in\mathbb{S},a\in\mathbb{A}}$. Then

$\displaystyle\mspace{23.0mu}R^{*}(N)-R(\pi,N)$ $\displaystyle\leq
R^{\textup{rel}}-R(\pi,N)$
$\displaystyle=\sum_{s\in\mathbb{S},a\in\mathbb{A}}r(s,a)y^{*}(s,a)-\frac{1}{N}\sum_{i\in[N]}\mathbb{E}\Big{[}r(S_{\infty}(i),A_{\infty}(i))\Big{]}$
$\displaystyle\leq\sum_{s\in\mathbb{S},a\in\mathbb{A}}r(s,a)y^{*}(s,a)-\frac{1}{N}\sum_{i\in[N]}\mathbb{E}\Big{[}r(S_{\infty}(i),\widehat{A}_{\infty}(i))\Big{]}+2r_{\max}\mathbb{E}\Big{[}\frac{1}{N}\sum_{i\in[N]}\mathbbm{1}\\!\left\\{\widehat{A}_{\infty}(i)\neq
A_{\infty}(i)\right\\}\Big{]}$
$\displaystyle\leq\sum_{s\in\mathbb{S},a\in\mathbb{A}}r(s,a)y^{*}(s,a)-\sum_{s\in\mathbb{S},a\in\mathbb{A}}r(s,a){{\bar{\pi}}^{*}}(a|s)\mathbb{E}\big{[}X_{\infty}([N],s)\big{]}+2r_{\max}\mathbb{E}\big{[}1-m(D_{\infty}^{\prime})\big{]}$
$\displaystyle\leq\sum_{s\in\mathbb{S},a\in\mathbb{A}}r(s,a)y^{*}(s,a)-\sum_{s\in\mathbb{S},a\in\mathbb{A}}r(s,a){{\bar{\pi}}^{*}}(a|s)\mathbb{E}\big{[}X_{\infty}([N],s)\big{]}+2r_{\max}\mathbb{E}\big{[}1-m(D_{\infty})\big{]}+\frac{2r_{\max}K_{\textup{conf}}}{\sqrt{N}}$
$\displaystyle=\sum_{s\in\mathbb{S},a\in\mathbb{A}}r(s,a){{\bar{\pi}}^{*}}(a|s)\Big{(}\mu^{*}(s)-\mathbb{E}\big{[}X_{\infty}([N],s)\big{]}\Big{)}+2r_{\max}\mathbb{E}\big{[}1-m(D_{\infty})\big{]}+\frac{2r_{\max}K_{\textup{conf}}}{\sqrt{N}}$
(27) $\displaystyle\leq
r_{\max}\mathbb{E}\big{[}\big{\lVert}\mu^{*}-\mathbb{E}\big{[}X_{\infty}([N])\big{]}\big{\rVert}_{1}\big{]}+2r_{\max}\mathbb{E}\big{[}1-m(D_{\infty})\big{]}+\frac{2r_{\max}K_{\textup{conf}}}{\sqrt{N}},$

where $D_{\infty}^{\prime}$ is the set assumed in 1, and the forth inequality
is by 1. Therefore, to bound the optimality gap, it suffices to bound
$\mathbb{E}\big{[}\big{\lVert}\mu^{*}-\mathbb{E}\big{[}X_{\infty}([N])\big{]}\big{\rVert}_{1}\big{]}$,
which is the distributional distance, and
$\mathbb{E}\big{[}1-m(D_{\infty})\big{]}$, which is the size of the complement
of the focus set.

In this proof, we construct a Lyapunov function that can be viewed as an upper
bound on a weighted sum of the two terms in (27). In particular, consider the
following Lyapunov function

(28) $V(x,D)=h(x,D)+L_{h}(1-m(D)).$

Let us first see how the terms in (27) are upper bounded by
$\mathbb{E}\left[V(X_{\infty},D_{\infty})\right]$. For the first term, it is
easy to see that
$K_{\textup{dist}}\left\lVert\mu^{*}_{1}-X_{\infty}([N])\right\rVert\leq
h(X_{\infty},[N])$ by the distance domination property of $h$. Then by the
Lipschitz continuity of $h$, we have $h(X_{\infty},[N])\leq
h(X_{\infty},D_{\infty})+L_{h}(1-m(D_{\infty}))=V(X_{\infty},D_{\infty})$.
Thus,
$\mathbb{E}\big{[}\big{\lVert}\mu^{*}-\mathbb{E}\big{[}X_{\infty}([N])\big{]}\big{\rVert}_{1}\big{]}\leq\mathbb{E}\big{[}V(X_{\infty},D_{\infty})\big{]}/K_{\textup{dist}}$.
For the second term, clearly
$\mathbb{E}\big{[}1-m(D_{\infty})\big{]}\leq\mathbb{E}\big{[}V(X_{\infty},D_{\infty})\big{]}/L_{h}$.
Therefore, the upper bound in (27) can be further bounded as

(29) $R^{*}(N)-R(\pi,N)\leq
r_{\max}\left(\frac{1}{K_{\textup{dist}}}+\frac{2}{L_{h}}\right)\mathbb{E}\big{[}V(X_{\infty},D_{\infty})\big{]}+\frac{2r_{\max}K_{\textup{conf}}}{\sqrt{N}},$

which makes it sufficient to bound
$\mathbb{E}\big{[}V(X_{\infty},D_{\infty})\big{]}$.

##### Bounding the Lyapunov function.

We establish an upper bound on
$\mathbb{E}\big{[}V(X_{\infty},D_{\infty})\big{]}$ by proving the following
drift condition: for any $t\geq 0$ and any pair $(x,D)$ for which the event
$(X_{t},D_{t})=(x,D)$ has a positive probability,

(30)
$\mathbb{E}\big{[}V(X_{t+1},D_{t+1})\,\big{|}\,X_{t}=x,D_{t}=D\big{]}\leq\rho_{1}V(x,D)+\frac{K_{1}}{\sqrt{N}},$

for some constants $\rho_{1}\in(0,1)$ and $K_{1}>0$.

We now prove (30). Consider a time step $t\geq 0$ and condition on
$(X_{t},D_{t})=(x,D)$. Then

$\displaystyle V(X_{t+1},D_{t+1})$
$\displaystyle=h(X_{t+1},D_{t+1})+L_{h}(1-m(D_{t+1}))$
$\displaystyle\leq\Bigl{(}h(X_{t+1},D)+L_{h}\big{\lvert}m(D_{t+1})-m(D)\big{\rvert}\Bigr{)}+\Bigl{(}L_{h}(1-m(D))+L_{h}(m(D)-m(D_{t+1}))\Bigr{)}$
(31)
$\displaystyle=h(X_{t+1},D)+L_{h}(1-m(D))+2L_{h}\big{(}m(D)-m(D_{t+1})\big{)}^{+},$

where we have used the facts that $D_{t+1}\supseteq D$ or $D_{t+1}\subseteq D$
(2) and the Lipschitz continuity of $h(x,D)$ in $D$. Subtracting $V(x,D)$ and
taking expectation, we obtain

(32)
$\displaystyle\mathbb{E}\big{[}V(X_{t+1},D_{t+1})\,\big{|}\,X_{t}=x,D_{t}=D\big{]}-V(x,D)$
$\displaystyle\leq\mathbb{E}\big{[}h(X_{t+1},D)\,\big{|}\,X_{t}=x,D_{t}=D\big{]}-h(x,D)$
(33)
$\displaystyle\mspace{14.0mu}+2L_{h}\mathbb{E}\big{[}\big{(}m(D)-m(D_{t+1})\big{)}^{+}\,\big{|}\,X_{t}=x,D_{t}=D\big{]}.$

Below we bound the terms in (32) and (33) separately.

We first bound the drift term
$\mathbb{E}\big{[}h(X_{t+1},D)\,\big{|}\,X_{t}=x,D_{t}=D\big{]}-h(x,D)$ in
(32). Note that this drift term would be immediately upper bounded by the
drift condition of subset Lyapunov functions if all the arms in $D$ were to
follow the ideal actions. However, it is not guaranteed that all the arms in
$D$ can follow the ideal actions. Nevertheless, the majority conformity
property of the focus set $D_{t}$ (1) guarantees that _most arms_ in $D_{t}=D$
can follow the ideal actions. Formally, there exists $D_{t}^{\prime}\subseteq
D_{t}$ such that for any $i\in D_{t}^{\prime}$, the policy chooses
$A_{t}(i)=\widehat{A}_{t}(i)$, and $\mathbb{E}\left[m(D_{t}\backslash
D_{t}^{\prime})|X_{t},D_{t}\right]=O(1/\sqrt{N})$. Let $X_{t+1}^{\prime}$ be a
random element denoting the system state at time $t+1$ if
$A_{t}(i)=\widehat{A}_{t}(i)$ for all $i\in D_{t}$. We couple $X_{t+1}$ with
$X_{t+1}^{\prime}$ such that they have the same states on the set
$D_{t}^{\prime}$, and thus
$h(X_{t+1},D_{t}^{\prime})=h(X_{t+1}^{\prime},D_{t}^{\prime})$. Then

$\displaystyle\mspace{21.0mu}\mathbb{E}\big{[}h(X_{t+1},D)\,\big{|}\,X_{t}=x,D_{t}=D\big{]}$
$\displaystyle=\mathbb{E}\big{[}h(X_{t+1}^{\prime},D)\,\big{|}\,X_{t}=x,D_{t}=D\big{]}+\mathbb{E}\big{[}h(X_{t+1},D)-h(X_{t+1}^{\prime},D)\,\big{|}\,X_{t}=x,D_{t}=D\big{]}$
$\displaystyle\leq\rho_{2}h(x,D)+\frac{K_{\textup{drift}}}{\sqrt{N}}+\mathbb{E}\big{[}h(X_{t+1},D)-h(X_{t+1}^{\prime},D)\,\big{|}\,X_{t}=x,D_{t}=D\big{]}$
$\displaystyle=\rho_{2}h(x,D)+\frac{K_{\textup{drift}}}{\sqrt{N}}+\mathbb{E}\big{[}h(X_{t+1},D)-h(X_{t+1},D_{t}^{\prime})+h(X_{t+1}^{\prime},D_{t}^{\prime})-h(X_{t+1}^{\prime},D)\,\big{|}\,X_{t}=x,D_{t}=D\big{]}$
$\displaystyle\leq\rho_{2}h(x,D)+\frac{K_{\textup{drift}}}{\sqrt{N}}+\mathbb{E}\big{[}2L_{h}m(D\backslash
D_{t}^{\prime})\,\big{|}\,X_{t}=x,D_{t}=D\big{]}$
$\displaystyle\leq\rho_{2}h(x,D)+\frac{K_{\textup{drift}}+2L_{h}K_{\textup{conf}}}{\sqrt{N}},$

where we have used the drift condition and the Lipschitz continuity of $h$. It
follows that

(34)
$\mathbb{E}\big{[}h(X_{t+1},D)\,\big{|}\,X_{t}=x,D_{t}=D\big{]}-h(x,D)\leq-(1-\rho_{2})h(x,D)+\frac{K_{\textup{drift}}+2L_{h}K_{\textup{conf}}}{\sqrt{N}}.$

The term in (33) can be bounded by simply applying 2:

(35)
$2L_{h}\mathbb{E}\big{[}\big{(}m(D)-m(D_{t+1})\big{)}^{+}\,\big{|}\,X_{t}=x,D_{t}=D\big{]}\leq\frac{2L_{h}K_{\textup{mono}}}{\sqrt{N}}.$

Combining the above bounds for (32) and (33), we obtain

$\displaystyle\mspace{21.0mu}\mathbb{E}\big{[}V(X_{t+1},D_{t+1})\,\big{|}\,X_{t}=x,D_{t}=D\big{]}-V(x,D)$
$\displaystyle\leq-(1-\rho_{2})h(x,D)+(K_{\textup{drift}}+2L_{h}K_{\textup{conf}}+2L_{h}K_{\textup{mono}})\frac{1}{\sqrt{N}}.$

We now bound the negative term $-(1-\rho_{2})h(x,D)$ in terms $V(x,D)$. Note
that the sufficient coverage condition (3) implies that for $X_{t}=x,D_{t}=D$,

$\displaystyle V(x,D)$
$\displaystyle=h(x,D)+L_{h}(1-m(D))\leq(1+L_{h}L_{\textup{cov}})h(x,D)+\frac{L_{h}K_{\textup{cov}}}{\sqrt{N}}.$

Therefore,

$\displaystyle\mspace{23.0mu}\mathbb{E}\big{[}V(X_{t+1},D_{t+1})\,\big{|}\,X_{t}=x,D_{t}=D\big{]}-V(x,D)$
$\displaystyle\leq-\frac{1-\rho_{2}}{1+L_{h}L_{\textup{cov}}}V(x,D)+\Bigl{(}K_{\textup{drift}}+2L_{h}K_{\textup{conf}}+2L_{h}K_{\textup{mono}}+\frac{1-\rho_{2}}{1+L_{h}L_{\textup{cov}}}L_{h}K_{\textup{cov}}\Bigr{)}\frac{1}{\sqrt{N}},$

and thus

(36)
$\mathbb{E}\big{[}V(X_{t+1},D_{t+1})\,\big{|}\,X_{t}=x,D_{t}=D\big{]}\leq\rho_{1}V(x,D)+\frac{K_{1}}{\sqrt{N}},$

where $\rho_{1}=1-\frac{1-\rho_{2}}{1+L_{h}L_{\textup{cov}}}$ and
$K_{1}=K_{\textup{drift}}+2L_{h}K_{\textup{conf}}+2L_{h}K_{\textup{mono}}+\frac{1-\rho_{2}}{1+L_{h}L_{\textup{cov}}}L_{h}K_{\textup{cov}}$.
This is the bound in (30) that we set out to prove.

Now with (30), $\mathbb{E}\left[V(X_{\infty},D_{\infty})\right]$ can be
bounded as follows. We take expectations on both sides of (30) with $x$ and
$D$ following the distributions of $X_{t}$ and $D_{t}$, and let $t\to\infty$.
We get

$\mathbb{E}\left[V(X_{\infty},D_{\infty})\right]\leq\rho_{1}\mathbb{E}\left[V(X_{\infty},D_{\infty})\right]+\frac{K_{1}}{\sqrt{N}},$

which implies that

(37)
$\mathbb{E}\left[V(X_{\infty},D_{\infty})\right]\leq\frac{K_{1}}{(1-\rho_{1})\sqrt{N}}.$

This completes the proof of Theorem 2. ∎

###### Remark 0.

We conclude this section by a remark on our use of the bivariate Lyapunov
functions $h(x,D)$ and $V(x,D)=h(x,D)+L_{h}(1-m(D))$. By definition, the
subset Lyapunov function $h(x,D)$ depends on the system state $x$ only through
$x(D).$ This means that for fixed $D$, the drifts of $h(x,D)$ and $V(x,D)$
only depend on the state transitions of the arms in $D$. When $D$ is chosen
appropriately, most arms in $D$ can follow ${{\bar{\pi}}^{*}}$ under the
budget constraint, thus inheriting the convergence and concentration
properties of the aperiodic unichain induced by ${{\bar{\pi}}^{*}}$.
Therefore, the auxiliary variable $D$ provides the flexibility of focusing on
a subset of arms so that the drift is easy to bound and expanding the subset
gradually to the entire system.

For the ID policy and the set-optimization policy, $D_{t}$ is determined by
the system state $X_{t}$, and hence $h(X_{t},D_{t})$ can be written as a
function of $X_{t}$ alone. Even in this case, using a bivariate $h$ is
beneficial, as it allows us to decouple the two variables—in particular,
quantities like $h(X_{t+1},D_{t})$ play a prominent role in our proof of
Theorem 2.

Our use of bivariate Lyapunov functions departs from most prior work on RB
(Whittle, 1988; Weber and Weiss, 1990; Verloop, 2016; Gast et al., 2023a, b),
whose analysis is in terms of the full system state $X_{t}([N])$, under which
the dynamics of arms in a subset is less visible. We expect that our approach
is useful for a broader class of problems where the system state consists of
multiple components, a subset of which have a more tractable dynamic at a
given time. In this case, one may construct a Lyapunov function that can zoom
into this more tractable subset and seek to gradually expand it.

##  6\. Proof of Theorem 3 (Optimality gap of ID Policy)

In this section, we prove Theorem 3 using the framework established in Section
5. This section is organized as follows. We first define the subset Lyapunov
functions for the ID policy in Section 6.1. We then justify that the ID policy
is an instance of a focus-set policy in Section 6.2. In Section 6.3, we
present three lemmas verifying that the ID policy satisfies Conditions 1, 2
and 3, respectively, and prove Theorem 3 by combining these three lemmas and
citing Theorem 2 in our framework. We prove the lemma that verifies 1 in
Sections 6.4. The proofs of the lemmas verifying Conditions 2 and 3 are given
in Appendix E.1 and E.2, respectively, due to the space constraint.

###  6.1. Subset Lyapunov functions

We now define a class of functions
$\\{h_{\textnormal{ID}}(\cdot,D)\\}_{D\in\mathcal{D}}$ with
$\mathcal{D}=\\{[n]\colon n\in[N]\\}$, which will be used as the subset
Lyapunov functions. Let $W$ be the positive definite matrix defined in
Definition 1. For each $m\in[0,1]_{N}$, let

$h_{W}(x,[Nm])=\left\lVert x([Nm])-m\mu^{*}\right\rVert_{W},$

which measures the distance between $x([Nm])$, the scaled state-count vector
for arms in $[Nm]$, and $m\mu^{*}$, the correspondingly scaled optimal steady-
state distribution. Then we take a non-decreasing “envelope” of
$h_{W}(x,[Nm])$ to define $h_{\textnormal{ID}}(x,[Nm])$ as follows: for each
$m\in[0,1]_{N}$,

(38) $\displaystyle
h_{\textnormal{ID}}(x,[Nm])=\max_{\begin{subarray}{c}m^{\prime}\in[0,1]_{N}\\\
m^{\prime}\leq m\end{subarray}}h_{W}(x,[Nm^{\prime}]).$

Note that both $h_{W}(x,[Nm])$ and $h_{\textnormal{ID}}(x,[Nm])$ depend only
on the states of the arms in $[Nm]$, as required by the definition of subset
Lyapunov functions. In the rest of the paper, we write $h_{W}(x,m)$ and
$h_{\textnormal{ID}}(x,m)$ as shorthands for $h_{W}(x,[Nm])$ and
$h_{\textnormal{ID}}(x,[Nm])$.

###### Lemma 0.

The class of functions $\\{h_{\textnormal{ID}}(\cdot,m)\\}_{m\in[0,1]_{N}}$
defined in (38) satisfies that for any system state $x$ and any
$m,m^{\prime}\in[0,1]_{N}$,

(39)
$\displaystyle\mathbb{E}\Big{[}\Big{(}h_{\textnormal{ID}}(X_{1},m)-\big{(}1-\frac{1}{2\lambda_{W}}\big{)}h_{\textnormal{ID}}(x,m)\Big{)}^{+}\,\Big{|}\,X_{0}=x,A_{0}(i)\sim{{\bar{\pi}}^{*}}(\cdot|S_{0}(i))\forall
i\in[Nm]\Big{]}\leq\frac{4\lambda_{W}^{1/2}}{\sqrt{N}},$ (40) $\displaystyle
h_{\textnormal{ID}}(x,m)\geq\frac{1}{|\mathbb{S}|^{1/2}}\left\lVert
x([Nm])-m\mu^{*}\right\rVert_{1},$ (41) $\displaystyle\left\lvert
h_{\textnormal{ID}}(x,m)-h_{\textnormal{ID}}(x,m^{\prime})\right\rvert\leq
2\lambda_{W}^{1/2}\left\lvert m^{\prime}-m\right\rvert,$

These inequalities imply the drift condition, distance dominance property, and
Lipschitz continuity in Definition 1, respectively. Consequently,
$\\{h_{\textnormal{ID}}(x,m)\\}_{m\in[0,1]_{N}}$ are subset Lyapunov functions
for ${{\bar{\pi}}^{*}}$.

The proof of Lemma 1 is provided in Section D.2. We note that the inequality
(39) is stronger than the drift condition required by the definition of
feature Lyapunov functions. This stronger version is needed for later
analysis.

###  6.2. Focus set

The ID policy, as previously noted, does not explicitly specify focus sets
within its algorithm. Nonetheless, for analysis purposes, we can introduce a
set $D_{t}$ at each time step $t$, effectively serving as the focus set for
the ID policy. Specifically, let $D_{t}=[Nm_{d}(X_{t})]$, where $m_{d}(\cdot)$
is a function that maps a system state to a number in
$[0,1]_{N}=\\{1/n,\dots,1\\}$. This function $m_{d}(\cdot)$ is formally
defined as follows:

(42) $m_{d}(x)=\max\\{m\in[0,1]_{N}\colon
K_{c/h}h_{\textnormal{ID}}(x,m)\leq\beta(1-m)\\},$

where $\beta\triangleq\min\\{\alpha,1-\alpha\\}$ and $K_{c/h}$ is a constant.
More concretely, the constant $K_{c/h}=\left\lVert
c_{{\bar{\pi}}^{*}}\right\rVert_{W^{-1}}$, where $c_{{\bar{\pi}}^{*}}$ denotes
the row vector $({{\bar{\pi}}^{*}}(1|s))_{s\in\mathbb{S}}$ and $W$ is the
weight matrix given by Lemma 2.

The definition of $m_{d}(x)$ has a nice geometric representation, as shown in
Figure 2(a). For a system state $x$, note that $h_{\textnormal{ID}}(x,[0])=0$
and recall that $h_{\textnormal{ID}}(x,[Nm])$ is non-decreasing in $m$. Then
$m_{d}(x)$ is the value of $m$ at which the curve $m\mapsto
K_{c/h}h_{\textnormal{ID}}(x,[Nm])$ intersects with the line
$m\mapsto\beta(1-m)$, ignoring the discretization effect.

(a) Subset Lyapunov functions and focus set.

(b) Illustration of the proof of Lemma 2.

Figure 2. (2(a)) Suppose the current system state is $X_{t}=x$. The function
$h_{\textnormal{ID}}(x,m)$, a shorthand for $h_{\textnormal{ID}}(x,[Nm])$, is
a subset Lyapunov function on the subset $[Nm]$. The set $[m_{d}(x)]$ is the
focus set.
(2(b)) The three curves illustrated are central to the proof of Lemma 2, e.g.,
see the inequality (52). Take the bottom curve $m\mapsto\max_{m^{\prime}\leq
m}\lvert C_{{\bar{\pi}}^{*}}(x,[Nm^{\prime}])-\alpha m^{\prime}\rvert$ as the
baseline. We show that the red curve based on the subset Lyapunov function
$m\mapsto K_{c/h}h_{\textnormal{ID}}(x,[Nm])$ is always above the bottom
curve, and that the curve $m\mapsto\max_{m^{\prime}\leq
m}\lvert\frac{1}{N}\sum_{i\in[Nm^{\prime}]}\widehat{A}_{t}(i)-\alpha
m^{\prime}\rvert$ deviates from the bottom curve by $O(1/\sqrt{N})$ in
expectation. Since $N^{{\bar{\pi}}^{*}}_{t}/N$ is always to the right of the
blue dot, we have $(Nm_{d}(X_{t})-N^{{\bar{\pi}}^{*}}_{t})^{+}=O(1/\sqrt{N})$
in expectation.

###  6.3. Lemmas for verifying Conditions 1, 2 and 3 and the proof of Theorem
3

Having defined the subset Lyapunov functions
$\\{h_{\textnormal{ID}}(x,D)\\}_{D\in\mathcal{D}}$ and the focus set
$D_{t}=[Nm_{d}(X_{t})]$, we proceed to establish Lemmas 2, 3 and 4, which
verify that the ID policy satisfies Conditions 1, 2 and 3, respectively. Then
we apply Theorem 2 to prove Theorem 3.

###### Lemma 0 (ID policy satisfies Condition 1).

Consider the ID policy in Algorithm 1. For any $t\geq 0$, let
$D_{t}^{\prime}=[\min(N^{{\bar{\pi}}^{*}}_{t},Nm_{d}(X_{t}))]$, where recall
that $N^{{\bar{\pi}}^{*}}_{t}\in[N]$ is defined in Algorithm 1 as the largest
number such that for any $i\in[N^{{\bar{\pi}}^{*}}_{t}]$,
$A_{t}(i)=\widehat{A}_{t}(i)$. Then

(43) $\mathbb{E}\big{[}m(D_{t}\backslash
D_{t}^{\prime})\,\big{|}\,X_{t},D_{t}\big{]}=\frac{1}{N}\mathbb{E}\big{[}(Nm_{d}(X_{t})-N^{{\bar{\pi}}^{*}}_{t})^{+}\,\big{|}\,X_{t}\big{]}\leq\frac{2}{\beta\sqrt{N}}+\frac{1}{N}\quad
a.s.$

###### Lemma 0 (ID policy satisfies 2).

Consider the ID policy in Algorithm 1. For any $t\geq 0$,

$\displaystyle\mathbb{E}\big{[}\big{(}m(D_{t})-m(D_{t+1})\big{)}^{+}\big{|}X_{t},D_{t}\big{]}$
$\displaystyle=\mathbb{E}\big{[}(m_{d}(X_{t})-m_{d}(X_{t+1}))^{+}\big{|}X_{t}\big{]}$
(44)
$\displaystyle\leq\frac{4K_{c/h}\lambda_{W}^{1/2}(1+\beta)}{\beta^{2}\sqrt{N}}+\frac{2K_{c/h}\lambda_{W}^{1/2}+\beta}{\beta
N}\quad a.s.$

###### Lemma 0 (ID policy satisfies 3).

Consider the ID policy in Algorithm 1. For any $t\geq 0$,

(45)
$1-m(D_{t})\leq\frac{K_{c/h}}{\beta}h_{\textnormal{ID}}(X_{t},D_{t})+\frac{2K_{c/h}\lambda_{W}^{1/2}+\beta}{\beta
N}\quad a.s.$

###### Proof of Theorem 3.

By Lemma 2, 3 and 4, the ID policy satisfies Conditions 1, 2 and 3 with the
subset Lyapunov functions $\\{h_{\textnormal{ID}}(x,D)\\}_{D\in\mathcal{D}}$.
We apply Theorem 2 to obtain the optimality gap bound stated in Theorem 3.
Note that we bound $K_{c/h}$ by $|\mathbb{S}|^{1/2}$, and relax all $1/N$
factors to $1/\sqrt{N}$ when deriving the bound. ∎

###  6.4. Proof of Lemma 2

Before delving into the proof, we first offer a high-level understanding of
Lemma 2. Recall that $[N^{{\bar{\pi}}^{*}}_{t}]$ is defined to be the largest
set of arms that always follow their ideal actions under the ID policy. Then
Lemma 2 states that the focus set we define, $D_{t}=[Nm_{d}(X_{t})]$, is close
to $[N^{{\bar{\pi}}^{*}}_{t}]$, differing by only $O(\sqrt{N})$ elements. Note
that whether a set of arms $[Nm]$ can follow their ideal actions or not is
determined by the amount of budget required by them, i.e., the number of
action $1$’s in their ideal actions. Our proof of Lemma 2 utilizes the
relationship between the budget requirement by arms in $[Nm]$ and the
distributional distance $\left\lVert x([Nm])-m\mu^{*}\right\rVert_{W}$.

###### Proof of Lemma 2.

Consider a time step $t\geq 0$ and condition on $X_{t}=x$. We first derive a
property of $N^{{\bar{\pi}}^{*}}_{t}$ by relating whether the arms in a set
$[n]$ can follow their ideal actions with the quantity
$\sum_{i\in[n]}\widehat{A}_{t}(i)$, referred to as their budget requirement.
For any $n\leq N$, the arms in $[n]$ can follow their ideal actions if and
only if

(46) $\displaystyle\sum_{i\in[n]}\widehat{A}_{t}(i)\leq\alpha N,$ (47)
$\displaystyle\sum_{i\in[n]}(1-\widehat{A}_{t}(i))\leq(1-\alpha)N.$

Here (46) requires that the number of action $1$’s is within budget. For the
condition (47), the easiest way to understand it is that it requires the
number of action $0$’s to be within $(1-\alpha)N$, where $(1-\alpha)N$ can be
interpreted as the “budget for idling actions”. As a result, a sufficient
condition for the arms in $[n]$ to follow their ideal actions is

(48) $\Big{\lvert}\sum_{i\in[n]}\widehat{A}_{t}(i)-\alpha
n\Big{\rvert}\leq\beta\big{(}N-n\big{)},$

where recall that $\beta=\min\\{\alpha,1-\alpha\\}$. In this proof, we use a
further sufficient condition for the inequality (48) above, which is

(49) $\max_{n^{\prime}\leq
n}\Big{\lvert}\sum_{i\in[n^{\prime}]}\widehat{A}_{t}(i)-\alpha
n^{\prime}\Big{\rvert}\leq\beta\big{(}N-n\big{)}.$

Therefore, by the definition of $N^{{\bar{\pi}}^{*}}_{t}$,

$\displaystyle N^{{\bar{\pi}}^{*}}_{t}$ $\displaystyle\geq\max\Big{\\{}n\leq
N\colon\max_{n^{\prime}\leq
n}\Big{\lvert}\sum_{i\in[n^{\prime}]}\widehat{A}_{t}(i)-\alpha
n^{\prime}\Big{\rvert}\leq\beta\big{(}N-n\big{)}\Big{\\}}$ (50)
$\displaystyle=\max\Big{\\{}Nm\colon
m\in[0,1]_{N},\max_{\begin{subarray}{c}m^{\prime}\in[0,1]_{N}\\\
m^{\prime}\leq
m\end{subarray}}\Big{\lvert}\frac{1}{N}\sum_{i\in[Nm^{\prime}]}\widehat{A}_{t}(i)-\alpha
m^{\prime}\Big{\rvert}\leq\beta\big{(}1-m\big{)}\Big{\\}}.$

We next consider the quantity $\max_{m^{\prime}\in[0,1]_{N},m^{\prime}\leq
m}\lvert\frac{1}{N}\sum_{i\in[Nm^{\prime}]}\widehat{A}_{t}(i)-\alpha
m^{\prime}\rvert$ and relate it to $h_{\textnormal{ID}}(x,m)$ by relating
$\lvert\frac{1}{N}\sum_{i\in[Nm^{\prime}]}\widehat{A}_{t}(i)-\alpha
m^{\prime}\rvert$ to $\left\lVert
x([Nm^{\prime}])-m^{\prime}\mu^{*}\right\rVert_{W}$. Consider the scaled
expected budget requirement for arms in a set $D$, defined as

(51) $C_{{\bar{\pi}}^{*}}(x,D)\triangleq\frac{1}{N}\mathbb{E}\Big{[}\sum_{i\in
D}\widehat{A}_{t}(i)\Big{|}X_{t}=x\Big{]}=\sum_{s\in\mathbb{S}}x(D,s){{\bar{\pi}}^{*}}(1|s)=x(D)c_{{\bar{\pi}}^{*}}^{\top},$

where recall that $c_{{\bar{\pi}}^{*}}$ is the row vector
$({{\bar{\pi}}^{*}}(1|s))_{s\in\mathbb{S}}$. Then for any $m\in[0,1]_{N}$,

$\displaystyle\mspace{20.0mu}\max_{\begin{subarray}{c}m^{\prime}\in[0,1]_{N}\\\
m^{\prime}\leq
m\end{subarray}}\Big{\lvert}\frac{1}{N}\sum_{i\in[Nm^{\prime}]}\widehat{A}_{t}(i)-\alpha
m^{\prime}\Big{\rvert}$
$\displaystyle\leq\max_{\begin{subarray}{c}m^{\prime}\in[0,1]_{N}\\\
m^{\prime}\leq
m\end{subarray}}\biggl{(}\Big{\lvert}C_{{\bar{\pi}}^{*}}(x,[Nm^{\prime}])-\alpha
m^{\prime}\Big{\rvert}+\Big{\lvert}\frac{1}{N}\sum_{i\in[Nm^{\prime}]}\widehat{A}_{t}(i)-C_{{\bar{\pi}}^{*}}(x,[Nm^{\prime}])\Big{\rvert}\biggr{)}$
(52) $\displaystyle\leq\max_{\begin{subarray}{c}m^{\prime}\in[0,1]_{N}\\\
m^{\prime}\leq
m\end{subarray}}\Big{\lvert}C_{{\bar{\pi}}^{*}}(x,[Nm^{\prime}])-\alpha
m^{\prime}\Big{\rvert}+\max_{m^{\prime}\in[0,1]_{N}}\Big{\lvert}\frac{1}{N}\sum_{i\in[Nm^{\prime}]}\widehat{A}_{t}(i)-C_{{\bar{\pi}}^{*}}(x,[Nm^{\prime}])\Big{\rvert},$

where the second term can be viewed as a noise term, which will be bounded
later. Consider the first term. Note that

$\displaystyle\left\lvert C_{{\bar{\pi}}^{*}}(x,[Nm^{\prime}])-\alpha
m^{\prime}\right\rvert$
$\displaystyle=(x([Nm^{\prime}])-m^{\prime}\mu^{*})c_{{\bar{\pi}}^{*}}^{\top}$
$\displaystyle=(x([Nm^{\prime}])-m^{\prime}\mu^{*})W^{1/2}{W}^{-1/2}c_{{\bar{\pi}}^{*}}^{\top}$
$\displaystyle\leq\left\lVert
x([Nm^{\prime}])-m^{\prime}\mu^{*}\right\rVert_{W}\left\lVert
c_{{\bar{\pi}}^{*}}\right\rVert_{W^{-1}}$ (53)
$\displaystyle=K_{c/h}h_{W}(x,m^{\prime}).$

Thus

$\displaystyle\max_{\begin{subarray}{c}m^{\prime}\in[0,1]_{N}\\\
m^{\prime}\leq m\end{subarray}}\Big{\lvert}C_{{\bar{\pi}}^{*}}(x,[Nm])-\alpha
m\Big{\rvert}$ $\displaystyle\leq
K_{c/h}\max_{\begin{subarray}{c}m^{\prime}\in[0,1]_{N}\\\ m^{\prime}\leq
m\end{subarray}}h_{W}(x,m^{\prime})=K_{c/h}h_{\textnormal{ID}}(x,m).$

As a result, for any $m\leq m_{d}(x)$,

(54) $\displaystyle\max_{\begin{subarray}{c}m^{\prime}\in[0,1]_{N}\\\
m^{\prime}\leq
m\end{subarray}}\Big{\lvert}\frac{1}{N}\sum_{i\in[Nm^{\prime}]}\widehat{A}_{t}(i)-\alpha
m^{\prime}\Big{\rvert}$
$\displaystyle\leq\beta(1-m_{d}(x))+\max_{m^{\prime}\in[0,1]_{N}}\Big{\lvert}\frac{1}{N}\sum_{i\in[Nm^{\prime}]}\widehat{A}_{t}(i)-C_{{\bar{\pi}}^{*}}(x,[Nm^{\prime}])\Big{\rvert},$

where we have used the definition of $m_{d}(x)$.

We now utilize the property of $N^{{\bar{\pi}}^{*}}_{t}$ in (50) and the upper
bound (54) to bound $(Nm_{d}(x)-N^{{\bar{\pi}}^{*}}_{t})^{+}$. Note that the
upper bound (54) does not depend on $m$. Now consider the property of
$N^{{\bar{\pi}}^{*}}_{t}$ in (50). Then it is not hard to see that

$\displaystyle\mspace{21.0mu}\min\bigg{\\{}Nm_{d}(x),\Big{\lfloor}N-\frac{N}{\beta}\Big{(}\beta(1-m_{d}(x))+\max_{m^{\prime}\in[0,1]_{N}}\Big{\lvert}\frac{1}{N}\sum_{i\in[Nm^{\prime}]}\widehat{A}_{t}(i)-C_{{\bar{\pi}}^{*}}(x,[Nm^{\prime}])\Big{\rvert}\Big{)}\Big{\rfloor}\bigg{\\}}$
(55) $\displaystyle\in\Big{\\{}Nm\colon
m\in[0,1]_{N},\max_{\begin{subarray}{c}m^{\prime}\in[0,1]_{N}\\\
m^{\prime}\leq
m\end{subarray}}\Big{\lvert}\frac{1}{N}\sum_{i\in[Nm^{\prime}]}\widehat{A}_{t}(i)-\alpha
m^{\prime}\Big{\rvert}\leq\beta\big{(}1-m\big{)}\Big{\\}}.$

Therefore,

$\displaystyle N^{{\bar{\pi}}^{*}}_{t}$
$\displaystyle\geq\min\bigg{\\{}Nm_{d}(x),\Big{\lfloor}N-\frac{N}{\beta}\Big{(}\beta(1-m_{d}(x))+\max_{m^{\prime}\in[0,1]_{N}}\Big{\lvert}\frac{1}{N}\sum_{i\in[Nm^{\prime}]}\widehat{A}_{t}(i)-C_{{\bar{\pi}}^{*}}(x,[Nm^{\prime}])\Big{\rvert}\Big{)}\Big{\rfloor}\bigg{\\}}$
$\displaystyle\geq\min\bigg{\\{}Nm_{d}(x),N-\frac{N}{\beta}\Big{(}\beta(1-m_{d}(x))+\max_{m^{\prime}\in[0,1]_{N}}\Big{\lvert}\frac{1}{N}\sum_{i\in[Nm^{\prime}]}\widehat{A}_{t}(i)-C_{{\bar{\pi}}^{*}}(x,[Nm^{\prime}])\Big{\rvert}\Big{)}-1\bigg{\\}}$
$\displaystyle=\min\bigg{\\{}Nm_{d}(x),Nm_{d}(x)-1-\frac{1}{\beta}\max_{m^{\prime}\in[0,1]_{N}}\Big{\lvert}\frac{1}{N}\sum_{i\in[Nm^{\prime}]}\widehat{A}_{t}(i)-C_{{\bar{\pi}}^{*}}(x,[Nm^{\prime}])\Big{\rvert}\bigg{\\}}$
$\displaystyle=Nm_{d}(x)-1-\frac{1}{\beta}\max_{n^{\prime}\leq
N}\Big{\lvert}\sum_{i\in[n^{\prime}]}\widehat{A}_{t}(i)-NC_{{\bar{\pi}}^{*}}(x,[n^{\prime}])\Big{\rvert}.$

Rearranging the terms and taking expectation, we get

(56)
$\mathbb{E}\Big{[}(Nm_{d}(x)-N^{{\bar{\pi}}^{*}}_{t})^{+}\,\Big{|}\,X_{t}=x\Big{]}\leq
1+\frac{1}{\beta}\mathbb{E}\Big{[}\max_{n^{\prime}\leq
N}\Big{\lvert}\sum_{i\in[n^{\prime}]}\widehat{A}_{t}(i)-NC_{{\bar{\pi}}^{*}}(x,[n^{\prime}])\Big{\rvert}\,\Big{|}\,X_{t}=x\Big{]}.$

Now it suffices to prove

(57) $\mathbb{E}\Big{[}\max_{n\leq
N}\Big{\lvert}\sum_{i\in[n]}\widehat{A}_{t}(i)-NC_{{\bar{\pi}}^{*}}(x,[n])\Big{\rvert}\,\Big{|}\,X_{t}=x\Big{]}\leq
2\sqrt{N}.$

We prove this bound using Doob’s maximum inequality for martingales (Durrett,
2019). Let
$\xi(i)=\widehat{A}_{t}(i)-\mathbb{E}\big{[}\widehat{A}_{t}(i)\,\big{|}\,X_{t}=x\big{]}$
and recall that
$C_{{\bar{\pi}}^{*}}(x,[n])=\sum_{i\in[n]}\mathbb{E}\big{[}\widehat{A}_{t}(i)\,\big{|}\,X_{t}=x\big{]}$.
Then

(58) $\mathbb{E}\Big{[}\max_{n\leq
N}\Big{\lvert}\sum_{i\in[n]}\widehat{A}_{t}(i)-NC_{{\bar{\pi}}^{*}}(x,[n])\Big{\rvert}\,\Big{|}\,X_{t}=x\Big{]}=\mathbb{E}\Big{[}\max_{n\leq
N}\Big{\lvert}\sum_{i\in[n]}\xi(i)\Big{\rvert}\,\Big{|}\,X_{t}=x\Big{]}.$

We argue that $(\sum_{i\in[n]}\xi(i))_{n}$ is a martingale (conditioned on
$X_{t}=x$):

  * •

Independence: conditioned on $X_{t}=x$, the ideal actions
$\widehat{A}_{t}(i)$’s are independently sampled, so $\xi(i)$’s are
independent.

  * •

Zero-mean: $\mathbb{E}\big{[}\xi(i)\,\big{|}\,X_{t}=x\big{]}=0$.

  * •

Bounded:
$\big{\lvert}\xi(i)\big{\rvert}=\big{\lvert}\widehat{A}_{t}(i)-\mathbb{E}\big{[}\widehat{A}_{t}(i)\,\big{|}\,X_{t}=x\big{]}\big{\rvert}\leq
1$.

Then by Doob’s $L_{2}$ maximum inequality (Durrett, 2019),

(59) $\mathbb{E}\Big{[}\max_{n\leq
N}\Big{\lvert}\sum_{i\in[n]}\xi(i)\Big{\rvert}^{2}\,\Big{|}\,X_{t}=x\Big{]}\leq
4\mathbb{E}\Big{[}\Big{|}\sum_{i\in[N]}\xi(i)\Big{|}^{2}\,\Big{|}\,X_{t}=x\Big{]}.$

Therefore,

$\displaystyle\mathbb{E}\Big{[}\max_{n\leq
N}\Big{\lvert}\sum_{i\in[n]}\xi(i)\Big{\rvert}\,\Big{|}\,X_{t}=x\Big{]}$
$\displaystyle\leq\mathbb{E}\Big{[}\max_{n\leq
N}\Big{|}\sum_{i\in[n]}\xi(i)\Big{|}^{2}\,\Big{|}\,X_{t}=x\Big{]}^{1/2}$
$\displaystyle\leq\biggl{(}4\mathbb{E}\Big{[}\Big{|}\sum_{i\in[N]}\xi(i)\Big{|}^{2}\,\Big{|}\,X_{t}=x\Big{]}\biggr{)}^{1/2}$
$\displaystyle=\biggl{(}4\sum_{i\in[N]}\mathbb{E}\Big{[}\xi(i)^{2}\,\Big{|}\,X_{t}=x\Big{]}\biggr{)}^{1/2}$
$\displaystyle\leq 2\sqrt{N}.$

This completes the proof. ∎

##  7\. Conclusion and discussions

In this paper, we considered the infinite-horizon, average-reward restless
bandit problem. We introduced a new class of policies that are asymptotically
optimal with $C/\sqrt{N}$ optimality gaps, provided that the single-armed
problem is unichain and any optimal single-armed policy induces an aperiodic
chain. Our result is the first to show that asymptotic optimality can be
achieved without any additional assumptions like UGAP and SA.

Our policy design and analysis highlight the use of multiple, bivariate
Lyapunov functions. This novel approach holds promises beyond restless
bandits, showing potential for a broader class of large stochastic systems
consisting of many coupled components. In such complex systems, it can be
challenging to directly design a policy that steers the whole system towards
optimality or to construct a Lyapunov function that certifies such
convergence.

Several directions are of interest for future research. Up to the
multiplicative factor $C$ in our results, the three policies have the same
optimality gap bound. It is however natural to conjecture that the set-
optimization policy may potentially have better performance due to optimizing
the choice of $D_{t}$. It is desirable to develop a more fine-grained analysis
that differentiates the performance of these policies. Further directions of
interest include generalizing our results to restless bandit problems with
heterogeneous arms, general state space, and to the more general problem of
weakly coupled MDPs. Achieving asymptotic optimality when the MDP model
parameters are unknown is another important research problem.

## References

  * (1)
  * Brown and Smith (2020) David B. Brown and James E. Smith. 2020.  Index Policies and Performance Bounds for Dynamic Selection Problems.  _Management Science_ 66, 7 (2020), 3029–3050.
  * Durrett (2019) Rick Durrett. 2019\.  _Probability: Theory and Examples_ (5 ed.).  Cambridge University Press.
  * Gast (2017) Nicolas Gast. 2017\.  Expected Values Estimated via Mean-Field Approximation are 1/N-Accurate. In _Proc. ACM Meas. Anal. Comput. Syst._ , Vol. 45. ACM, 50–50.
  * Gast et al. (2023a) Nicolas Gast, Bruno Gaujal, and Chen Yan. 2023a.  Exponential asymptotic optimality of Whittle index policy.  _Queueing Systems_ 104, 1 (2023), 107–150.
  * Gast et al. (2023b) Nicolas Gast, Bruno Gaujal, and Chen Yan. 2023b.  Linear Program-Based Policies for Restless Bandits: Necessary and Sufficient Conditions for (Exponentially Fast) Asymptotic Optimality.  _Math. Oper. Res._ (2023).
  * Gast and Van Houdt (2017) Nicolas Gast and Benny Van Houdt. 2017.  TTL approximations of the cache replacement algorithms LRU(m) and h-LRU.  _Perform. Eval._ 117 (2017), 33 – 57.
  * Hong et al. (2023) Yige Hong, Qiaomin Xie, Yudong Chen, and Weina Wang. 2023\.  Restless Bandits with Average Reward: Breaking the Uniform Global Attractor Assumption. In _Conf. Neural Information Processing Systems (NeurIPS)_.
  * Hu and Frazier (2017) Weici Hu and Peter Frazier. 2017.  An Asymptotically Optimal Index Policy for Finite-Horizon Restless Bandits.  _arXiv:1707.00205 [math.OC]_ (2017).
  * Mukherjee et al. (2017) Debankur Mukherjee, Souvik Dhara, Sem C. Borst, and Johan S.H. van Leeuwaarden. 2017.  Optimal Service Elasticity in Large-Scale Distributed Systems.  _Proc. ACM Meas. Anal. Comput. Syst._ 1, 1, Article 25 (June 2017), 28 pages.
  * Niño-Mora (2023) José Niño-Mora. 2023\.  Markovian Restless Bandits and Index Policies: A Review.  _Mathematics_ 11, 7 (2023).
  * Papadimitriou and Tsitsiklis (1999) Christos H. Papadimitriou and John N. Tsitsiklis. 1999.  The Complexity of Optimal Queuing Network Control.  _Math. Oper. Res._ 24, 2 (1999), 293–305.
  * Puterman (2005) Martin L Puterman. 2005\.  _Markov decision processes: Discrete stochastic dynamic programming_.  John Wiley & Sons.
  * Rutten and Mukherjee (2023) Daan Rutten and Debankur Mukherjee. 2023.  Mean-field Analysis for Load Balancing on Spatial Graphs.  _ACM SIGMETRICS Perform. Evaluation Rev._ 51, 1 (June 2023), 27–28.
  * Vasantam et al. (2019) Thirupathaiah Vasantam, Arpan Mukhopadhyay, and Ravi R. Mazumdar. 2019.  Insensitivity of the mean field limit of loss systems under SQ(d) routeing.  _Adv. Appl. Probab._ 51, 4 (2019), 1027–1066.
  * Verloop (2016) I. M. Verloop. 2016\.  Asymptotically Optimal Priority Policies for Indexable and Nonindexable Restless Bandits.  _Ann. Appl. Probab._ 26, 4 (2016), 1947–1995.
  * Weber and Weiss (1990) Richard R. Weber and Gideon Weiss. 1990.  On an Index Policy for Restless Bandits.  _J. Appl. Probab._ 27, 3 (1990), 637–648.
  * Whittle (1988) Peter Whittle. 1988\.  Restless bandits: activity allocation in a changing world.  _J. Appl. Probab._ 25 (1988), 287 – 298.
  * Ying (2016) Lei Ying. 2016.  On the Approximation Error of Mean-Field Models. In _Proc. ACM SIGMETRICS Int. Conf. Measurement and Modeling of Computer Systems_. Antibes Juan-les-Pins, France.
  * Zayas-Cabán et al. (2019) Gabriel Zayas-Cabán, Stefanus Jasin, and Guihua Wang. 2019\.  An asymptotically optimal heuristic for general nonstationary finite-horizon restless multi-armed, multi-action bandits.  _Advances in Applied Probability_ 51 (2019), 745–772.
  * Zhang and Frazier (2021) Xiangyu Zhang and Peter I. Frazier. 2021.  Restless Bandits with Many Arms: Beating the Central Limit Theorem.  _arXiv:2107.11911 [math.OC]_ (2021).
  * Zhang and Frazier (2022) Xiangyu Zhang and Peter I. Frazier. 2022.  Near-optimality for infinite-horizon restless bandits with many arms.  _arXiv:2203.15853 [cs.LG]_ (2022).

##  Appendix A Counterexample for Synchronization Assumption

In this section, we give a counterexample where the Synchronization Assumption
(SA) in (Hong et al., 2023) is not satisfied. In this example, the FTVA policy
in (Hong et al., 2023) is not asymptotically optimal but our proposed policies
are.

Consider a single-armed MDP whose transition structure is given in Figure 3.
The figure consists of a set of cycles denoting states and a set of arrows in
solid lines and dashed lines. The states are indexed as $0,1,2,\dots,7$. Each
solid arrow is labeled by an action $0$ or $1$. In each time step, an arm
takes an action. When an arm takes an action that is labeled on one of the
solid-line arrows going out from the current state, it picks such an arrow
labeled by the action uniformly at random and transitions along the arrow to a
nearby state. When an arm takes an action that does not exist on any of its
solid-line arrows that go out from its current state, it transitions along the
dashed-line arrow, i.e., jumps to state $0$. For example, if an arm takes
action $1$ at state $7$, it goes to state $6$ with probability $1$; if an arm
takes action $0$ at state $6$, it goes to state $7$ or $4$ each with
probability $0.5$; if an arm takes action $0$ at state $2$, it jumps to state
$0$ with probability $1$.

The reward is $1$ if an arm is in states $\\{4,5,6,7\\}$ and takes the action
on an outward solid-line arrow at its current state. Otherwise, the reward is
zero. We let $\alpha=7/12$, i.e., the arm is activated for $7/12$ fraction of
the time in the long run.

One can verify that the only optimal policy in this single-armed problem
${{\bar{\pi}}^{*}}$ always takes the actions labeled on the solid-line arrows.
This policy ${{\bar{\pi}}^{*}}$ achieves a long-run average reward of $1$. The
policy ${{\bar{\pi}}^{*}}$ induces an aperiodic unichain, with the recurrent
class $\\{4,5,6,7\\}$. However, ${{\bar{\pi}}^{*}}$ violates SA. To see this,
consider the leader-and-follower system in the SA, which consists of two arms,
the leader arm and the follower arm. The state of the leader arm is denoted as
$\widehat{S}_{t}$; the state of the follower arm is denoted as $S_{t}$. The
leader arm takes the action
$\widehat{A}_{t}\sim{{\bar{\pi}}^{*}}(\cdot|\widehat{S}_{t})$, and the
follower arm takes the action $A_{t}=\widehat{A}_{t}$. SA requires that the
stopping time $\tau=\inf\\{t\colon S_{t}=\widehat{S}_{t}\\}$ has a finite
expectation for possible pairs of initial states. However, if we initialize
the pair of states as $S_{0}=0$ and $\widehat{S}_{0}=7$, $\widehat{S}_{t}$
will remain in states $\\{4,5,6,7\\}$ under ${{\bar{\pi}}^{*}}$. There are no
more than two subsequent $1$’s in the action sequences applied by both arms.
Consequently, $S_{t}$ always falls back to the state $0$ before reaching state
$3$. Therefore, the two arms never reach the same state, and $\tau=\infty$.

Note that although this single-armed MDP violates the all-policy unichain
assumption in this paper, as we mention in Appendix B, we can relax the all-
policy unichain assumption and only require all optimal single-armed policies
to induce aperiodic unichains, which is satisfied in this example. As a
result, the three policies we propose are asymptotically optimal.

Figure 3. A counterexample to Synchronization Assumption in (Hong et al.,
2023). Each cycle denotes a state, indexed by $0,1,2,\dots,7$. Each arrow
denotes a possible transition. The numbers labeled on the solid-line arrows
denote actions. If an arm takes an action that is labeled on one of the
outward solid-line arrows at its current state, it picks such an arrow labeled
by the action uniformly at random and transitions to a nearby state along the
arrow; otherwise, the arm jumps to state $0$. The reward is $1$ if an arm is
in states $\\{4,5,6,7\\}$ and takes the action on an outward solid-line arrow
at its current state. Otherwise, the reward is zero.

##  Appendix B Discussion on relaxing the unichain assumption

In this section, we discuss how the all-policy unichain assumption in 1 can be
relaxed. In particular, we relax the assumption that any policy ${\bar{\pi}}$
of the single-armed problem (3)–(4) induces a unichain $P_{{\bar{\pi}}}$.

We first revise the single-armed problem. When the all-policy unichain
assumption is not satisfied, we can still define the single-armed problem in a
way similar to (3)–(4), but we now put the initial distribution also as an
optimization variable, i.e., we optimize over pairs of the initial
distribution $\mu_{0}$ and the policy ${\bar{\pi}}$. Specifically, we define
the following revised-single-armed problem:

(60) $\displaystyle\underset{\mu_{0},\,{\bar{\pi}}}{\text{maximize}}$
$\displaystyle\quad\lim_{T\to\infty}\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\left[r(S_{t}^{\bar{\pi}}(1),A_{t}^{\bar{\pi}}(1))\right]$
(61) subject to
$\displaystyle\quad\lim_{T\to\infty}\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\left[A_{t}^{\bar{\pi}}(1)\right]=\alpha.$

One can prove that the optimal value of this revised-single-armed problem is
an upper bound on the optimal value of the $N$-armed problem.

We now relax the unichain assumption to be the following. We consider any
optimal solution $(\mu_{0}^{*},{{\bar{\pi}}^{*}})$ to the revised-single-armed
problem (60)–(61). We assume that ${{\bar{\pi}}^{*}}$ induces an unichain. To
complete the relaxation of the entire 1, we also assume that the Markov chain
induced by ${{\bar{\pi}}^{*}}$ is aperiodic.

##  Appendix C Discussion on the necessity of aperiodicity

In this section, we provide an example showing that without aperiodicity, the
gap between the optimal value of the $N$-armed RB problem, $R^{*}(N)$, and the
optimal value of its single-armed relaxation, $R^{\textup{rel}}$, can be non-
diminish as $N\to\infty$.

Consider a single-armed problem with two states, $A$ and $B$. At each time
step, the arm transitions to the other state with probability $1$, regardless
of the action applied. The reward function is given by $r(A,0)=r(B,1)=1$ and
$r(A,1)=r(B,0)=0$. Let $\alpha$ be $\frac{1}{2}$ in the relaxed budget
constraint, i.e., the arm is pulled half of the time in the long run. It is
not hard to see that an optimal policy ${{\bar{\pi}}^{*}}$ of the single-armed
problem is given by ${{\bar{\pi}}^{*}}(0|A)=1={{\bar{\pi}}^{*}}(1|B)=1$ and
${{\bar{\pi}}^{*}}(1|A)={{\bar{\pi}}^{*}}(0|B)=0$, and it achieves the optimal
value $R^{\textup{rel}}=1$. Note that any policies in this single-armed
problem induce a _periodic_ unichain.

Now we consider the RB system consisting of $N$ copies of the single-armed MDP
defined above, with budget constraint $\alpha N=N/2$. Suppose all arms of the
RB system are initialized in state $A$. Then at any time $t$, either all arms
are in state $A$ or all arms are in state $B$. In this case, all policies have
the same outcome: when all arms are in state $A$, $N/2$ arms take action $0$
and generate $N/2$; when all arms are in state $B$, $N/2$ arms take action $1$
and generate $N/2$ reward. Therefore, under any policy, the long-run average
reward per time step and arm is $1/2$, which has a non-diminishing gap with
the upper bound $R^{\textup{rel}}=1$.

##  Appendix D Preliminary lemmas and proofs

In this section, we provide lemmas and proofs that serve as preliminaries for
analyzing our policies. In Section D.1, we prove the properties of the $W$ and
the $W$-weighted $L_{2}$-norms claimed in Section 3.1. In particular, we prove
Lemma 2, which claims that the state distribution of the Markov chain
$P_{{\bar{\pi}}^{*}}$ converges to the steady-state distribution $\mu^{*}$
geometrically fast under the $W$-weighted $L_{2}$ norm. Then in Section D.2,
we show that two classes of functions, $\\{h_{W}(x,D))\\}_{D\subseteq[N]}$ and
$\\{h_{\textnormal{ID}}(\cdot,m)\\}_{m\in[0,1]_{N}}$, are subset Lyapunov
functions. Finally, in Section D.3, we prove two lemmas about the $L_{1}$ norm
that are useful for analyzing the set-expansion and the set-optimization
policies.

###  D.1. Lemmas and proofs about the matrix $W$ and $W$-weighted $L_{2}$ norm

We first show that $W$ given in Definition 1 is well-defined and positive
definite. For ease of reference, we restate the definition of $W$ below.

See 1

###### Lemma 0.

The matrix $W$ given in Definition 1 is well-defined. Moreover, $W$ is
positive definite whose eigenvalues are lower bounded by $1$.

###### Proof of Lemma 1.

Since ${{\bar{\pi}}^{*}}$ is assumed to induce an aperiodic unichain, the
spectral radius (the largest absolute value of eigenvalues) of
$P_{{\bar{\pi}}^{*}}-\Xi$ is strictly less than $1$. By the property of
spectral radius, we have

$\lim_{k\to\infty}\left\lVert(P_{{\bar{\pi}}^{*}}-\Xi)^{k}\right\rVert_{2}^{1/k}<1,$

where the norm $\left\lVert\cdot\right\rVert_{2}$ represents the spectral
norm, i.e., the largest singular value of a matrix.

Let us consider the sum of the spectral norm of all terms in the definition of
$W$:

$\sum_{k=0}^{\infty}\left\lVert(P_{{\bar{\pi}}^{*}}-\Xi)^{k}(P_{{\bar{\pi}}^{*}}^{\top}-\Xi^{\top})^{k}\right\rVert_{2}.$

By assumption, there exist $k_{0}\in\mathbb{N}^{+}$ and $\bar{\rho}<1$ such
that
$\left\lVert(P_{{\bar{\pi}}^{*}}-\Xi)^{k_{0}}\right\rVert_{2}=\bar{\rho}$. We
have

$\displaystyle\sum_{k=0}^{\infty}\left\lVert(P_{{\bar{\pi}}^{*}}-\Xi)^{k}(P_{{\bar{\pi}}^{*}}^{\top}-\Xi^{\top})^{k}\right\rVert_{2}$
$\displaystyle=\sum_{j=0}^{\infty}\sum_{k=jk_{0}}^{(j+1)k_{0}-1}\left\lVert(P_{{\bar{\pi}}^{*}}-\Xi)^{k}(P_{{\bar{\pi}}^{*}}^{\top}-\Xi^{\top})^{k}\right\rVert_{2}$
$\displaystyle=\sum_{j=0}^{\infty}\sum_{k=0}^{k_{0}-1}\left\lVert(P_{{\bar{\pi}}^{*}}-\Xi)^{jk_{0}}(P_{{\bar{\pi}}^{*}}-\Xi)^{k}(P_{{\bar{\pi}}^{*}}^{\top}-\Xi^{\top})^{k}(P_{{\bar{\pi}}^{*}}^{\top}-\Xi^{\top})^{jk_{0}}\right\rVert_{2}$
$\displaystyle\leq\sum_{j=0}^{\infty}\sum_{k=0}^{k_{0}-1}\left\lVert(P_{{\bar{\pi}}^{*}}-\Xi)^{k_{0}}\right\rVert_{2}^{j}\left\lVert(P_{{\bar{\pi}}^{*}}-\Xi)^{k}(P_{{\bar{\pi}}^{*}}^{\top}-\Xi^{\top})^{k}\right\rVert_{2}\left\lVert(P_{{\bar{\pi}}^{*}}^{\top}-\Xi^{\top})^{k_{0}}\right\rVert_{2}^{j}$
$\displaystyle=\sum_{j=0}^{\infty}\bar{\rho}^{2j}\sum_{k=0}^{k_{0}-1}\left\lVert(P_{{\bar{\pi}}^{*}}-\Xi)^{k}(P_{{\bar{\pi}}^{*}}^{\top}-\Xi^{\top})^{k}\right\rVert_{2}$
$\displaystyle=\frac{C_{0}}{1-\bar{\rho}^{2}}<\infty,$

where
$C_{0}=\sum_{k=0}^{k_{0}-1}\left\lVert(P_{{\bar{\pi}}^{*}}-\Xi)^{k}(P_{{\bar{\pi}}^{*}}^{\top}-\Xi^{\top})^{k}\right\rVert_{2}$.
Therefore, the infinite sum is absolutely convergent.

To show that $W$ is positive definite, observe that each term in its
definition,
$(P_{{\bar{\pi}}^{*}}-\Xi)^{k}(P_{{\bar{\pi}}^{*}}^{\top}-\Xi^{\top})^{k}$, is
positive semi-definite; and its first term is the identity matrix. Therefore,
for any row vector $v\in\mathbb{R}^{\left\lvert\mathbb{S}\right\rvert}$ such
that $v\neq 0$, $vWv^{\top}\geq vv^{\top}$. Therefore, $W$ is positive
definite and its eigenvalues are lower bounded by $1$. ∎

Next, we restate and prove Lemma 2.

See 2

###### Proof of Lemma 2.

We let $\lambda_{W}$ be the largest eigenvalue of $W$. By the definition of
$W$ in Definition 1, the eigenvalues of $W$ is in the range $[1,\lambda_{W}]$.

Next, we show (11). It is not hard to see from the definition that $W$
satisfies

$(P_{{\bar{\pi}}^{*}}-\Xi)W(P_{{\bar{\pi}}^{*}}^{\top}-\Xi^{\top})-W+I=0.$

Then

$\displaystyle\left\lVert(v-\mu^{*})P_{{\bar{\pi}}^{*}}\right\rVert_{W}-\left\lVert
v-\mu^{*}\right\rVert_{W}$
$\displaystyle\leq\frac{(v-\mu^{*})P_{{\bar{\pi}}^{*}}WP_{{\bar{\pi}}^{*}}^{\top}(v-\mu^{*})^{\top}-(v-\mu^{*})W(v-\mu^{*})^{\top}}{2\left\lVert
v-\mu^{*}\right\rVert_{W}}$
$\displaystyle=\frac{(v-\mu^{*})(P_{{\bar{\pi}}^{*}}-\Xi)W(P_{{\bar{\pi}}^{*}}-\Xi)^{\top}(v-\mu^{*})^{\top}-(v-\mu^{*})W(v-\mu^{*})^{\top}}{2\left\lVert
v-\mu^{*}\right\rVert_{W}}$
$\displaystyle=\frac{(v-\mu^{*})(W-I)(v-\mu^{*})^{\top}-(v-\mu^{*})W(v-\mu^{*})^{\top}}{2\left\lVert
v-\mu^{*}\right\rVert_{W}}$ (62) $\displaystyle=-\frac{\left\lVert
v-\mu^{*}\right\rVert_{2}^{2}}{2\left\lVert v-\mu^{*}\right\rVert_{W}},$

where the inequality is due to the concavity of the function
$x\mapsto\sqrt{x}$. To change the norm in the numerator of the RHS of (62) to
$W$-weighted $L_{2}$ norm, we use the following observation: let $\lambda_{W}$
be the maximal eigenvalue of $W$, then

$\left\lVert
v-\mu^{*}\right\rVert_{W}^{2}=(v-\mu^{*})W(v-\mu^{*})^{\top}\leq\lambda_{W}\left\lVert
v-\mu^{*}\right\rVert_{2}^{2}.$

Therefore,

$\displaystyle\left\lVert(v-\mu^{*})P_{{\bar{\pi}}^{*}}\right\rVert_{W}-\left\lVert
v-\mu^{*}\right\rVert_{W}$
$\displaystyle\leq-\frac{1}{2\lambda_{W}}\left\lVert
v-\mu^{*}\right\rVert_{W},$

After rearranging the terms, we finish the proof. ∎

###  D.2. Lemmas and proofs about subset Lyapunov functions

In this section, we consider two classes of functions,
$\\{h_{W}(x,D)\\}_{D\subseteq[N]}$ and
$\\{h_{\textnormal{ID}}(\cdot,m)\\}_{m\in[0,1]_{N}}$. We prove two lemmas
verifying that these two classes of functions are subset Lyapunov functions.

For any system state $x$ and subset $D\subseteq[N]$, we define $h_{W}(x,D)$ as

(63) $\displaystyle h_{W}(x,D)$ $\displaystyle=\left\lVert
x(D)-m(D)\mu^{*}\right\rVert_{W},$

where $W$ is the matrix defined in Definition 1; $\left\lVert
u\right\rVert_{W}=\sqrt{uWu^{\top}}$ for any row vector $u$. Note that when
$D=[Nm]$ for some $m\in[0,1]_{N}$, $h_{W}(x,D)$ is the same function as
$h_{W}(x,[Nm])$ defined in Section 6.1.

The lemma below shows that $\\{h_{W}(x,D)\\}_{D\subseteq[N]}$ are subset
Lyapunov functions.

###### Lemma 0.

The class of functions $\\{h_{W}(x,D)\\}_{D\subseteq[N]}$ defined in (63)
satisfies that for any system state $x$ and any pair of subsets
$D,D^{\prime}\subseteq[N]$ with $D\subseteq D^{\prime}$,

(64)
$\displaystyle\mathbb{E}[h_{W}(X_{1},D)\,|\,X_{0}=x,A_{0}(i)\sim{{\bar{\pi}}^{*}}(\cdot|S_{0}(i))\forall
i\in
D]\leq\big{(}1-\frac{1}{2\lambda_{W}}\big{)}h_{W}(x,D)+\frac{2\lambda_{W}^{1/2}}{\sqrt{N}}$
(65) $\displaystyle h_{W}(x,D)\geq\frac{1}{|\mathbb{S}|^{1/2}}\left\lVert
x(D)-m(D)\mu^{*}\right\rVert_{1}$ (66) $\displaystyle\left\lvert
h_{W}(x,D)-h_{W}(x,D^{\prime})\right\rvert\leq L_{W}(m(D^{\prime})-m(D)),$

where the Lipschitz constant $L_{W}=2\lambda_{W}^{1/2}$. These inequalities
imply the drift condition, distance dominance property, and Lipschitz
continuity in Definition 1, respectively. Consequently,
$\\{h_{W}(x,D)\\}_{D\subseteq[N]}$ are subset Lyapunov functions for
${{\bar{\pi}}^{*}}$.

###### Proof of Lemma 2.

We first prove (39). Let $X_{1}^{\prime}$ be the system state after one step
of transition if $A_{0}(i)\sim{{\bar{\pi}}^{*}}(\cdot|S_{0}(i))$ for any $i\in
D$. Then

$\displaystyle
h_{W}(X_{1}^{\prime},D)-\big{(}1-\frac{1}{2\lambda_{W}}\big{)}h_{W}(x,D)$
$\displaystyle=\left\lVert
X_{1}^{\prime}(D)-m(D)\mu^{*}\right\rVert_{W}-\big{(}1-\frac{1}{2\lambda_{W}}\big{)}\left\lVert
x(D)-m(D)\mu^{*}\right\rVert_{W}$ $\displaystyle\leq\lVert
X_{1}^{\prime}(D)-m(D)\mu^{*}\rVert_{W}-\left\lVert
x(D)P_{{\bar{\pi}}^{*}}-m(D)\mu^{*}\right\rVert_{W}$ (67)
$\displaystyle\leq\lVert
X_{1}^{\prime}(D)-x(D)P_{{{\bar{\pi}}^{*}}}\rVert_{W}.$

where the first inequality follows from applying Lemma 2 with $v=x(D)/m(D)$;
the second inequality is due to the triangular inequality. For any
$i\in[Nm_{d}(x)]$, define the random vector
$\xi(i)\in\mathbb{R}^{\left\lvert\mathbb{S}\right\rvert}$ as

$\xi(i)=X_{1}^{\prime}(\\{i\\})-x(\\{i\\})P_{{\bar{\pi}}^{*}}.$

We denote the $s$-th entry of the vector $\xi(i)$ as $\xi(i,s)$. We rewrite
$\lVert X_{1}^{\prime}(D)-x(D)P_{{{\bar{\pi}}^{*}}}\rVert_{W}$ as

(68)
$\big{\lVert}X_{1}^{\prime}(D)-x(D)P_{{{\bar{\pi}}^{*}}}\big{\rVert}_{W}=\big{\lVert}\sum_{i\in
D}\xi(i)\big{\rVert}_{W}.$

Observe that conditioned on $X_{0}=x$, we have the following facts about
$\xi(i)$’s

  * •

$\xi(i)$’s are independent across $i\in D$;

  * •

For each $i\in D$ and $s\in\mathbb{S}$,
$\mathbb{E}\left[\xi(i,s)|X_{0}=x\right]=0$.

Conditioned on $X_{0}=x$, we bound the expectation of $\lVert\sum_{i\in
D}\xi(i)\rVert_{W}^{2}$ as follows:

$\displaystyle\mathbb{E}\Big{[}\Big{\lVert}\sum_{i\in
D}\xi(i)\Big{\rVert}_{W}^{2}\,\Big{|}\,X_{0}=x\Big{]}$
$\displaystyle\leq\lambda_{W}\mathbb{E}\Big{[}\Big{\lVert}\sum_{i\in
D}\xi(i)\Big{\rVert}_{2}^{2}\,\Big{|}\,X_{0}=x\Big{]}$
$\displaystyle=\lambda_{W}\mathbb{E}\Big{[}\sum_{s\in\mathbb{S}}\Big{(}\sum_{i\in
D}\xi(i,s)^{2}+2\sum_{0\leq i<i^{\prime}\leq
Nm_{d}(x)-1}\xi(i,s)\xi(i^{\prime},s)\Big{)}\,\Big{|}\,X_{0}=x\Big{]}$
$\displaystyle=\lambda_{W}\sum_{s\in\mathbb{S}}\sum_{i\in
D}\mathbb{E}\left[\xi(i,s)^{2}\,\Big{|}\,X_{0}=x\right]$
$\displaystyle\leq\lambda_{W}\sum_{i\in
D}\mathbb{E}\Big{[}\Big{(}\sum_{s\in\mathbb{S}}\left\lvert\xi(i,s)\right\rvert\Big{)}^{2}\,\Big{|}\,X_{0}=x\Big{]}$
(69) $\displaystyle\leq\frac{4\lambda_{W}}{N},$

where the first inequality uses from the fact that $\left\lVert
v\right\rVert_{W}\leq\lambda_{W}^{1/2}\left\lVert v\right\rVert_{2}$ for any
$v\in\mathbb{R}^{|\mathbb{S}|}$; the first equality is by the definition of
$\left\lVert\cdot\right\rVert_{2}$ on
$\mathbb{R}^{\left\lvert\mathbb{S}\right\rvert}$; the second equality is
because $\xi(i,s)$’s are independent across $i\in D$ and have zero means; the
last inequality uses the fact that
$\sum_{s\in\mathbb{S}}\left\lvert\xi(i,s)\right\rvert=\lVert\xi(i)\rVert_{1}\leq\lVert
X_{1}^{\prime}(\\{i\\})\rVert_{1}+\lVert
x(\\{i\\})P_{{\bar{\pi}}^{*}}\rVert_{1}=2/N$. By the Cauchy-Schwartz
inequality, it follows from (69) that

(70) $\mathbb{E}\Big{[}\Big{\lVert}\sum_{i\in
D}\xi(i)\Big{\rVert}_{W}\,\Big{|}\,X_{0}=x\Big{]}\leq\mathbb{E}\Big{[}\Big{\lVert}\sum_{i\in
D}\xi(i)\Big{\rVert}_{W}^{2}\,\Big{|}\,X_{0}=x\Big{]}^{1/2}\leq\frac{2\lambda_{W}^{1/2}}{\sqrt{N}}.$

Therefore, by combining the above calculations, we get

$\displaystyle\mathbb{E}\Big{[}h_{W}(X_{1}^{\prime},D)-\big{(}1-\frac{1}{2\lambda_{W}}\big{)}h_{W}(x,D)\,\Big{|}\,X_{0}=x\Big{]}$
$\displaystyle\leq\mathbb{E}\Big{[}\lVert
X_{1}^{\prime}(D)-x(D)P_{{{\bar{\pi}}^{*}}}\rVert_{W}\,\Big{|}\,X_{0}=x\Big{]}$
$\displaystyle=\mathbb{E}\Big{[}\Big{\lVert}\sum_{i\in
D}\xi(i)\Big{\rVert}_{W}\,\Big{|}\,X_{0}=x\Big{]}$
$\displaystyle\leq\frac{2\lambda_{W}^{1/2}}{\sqrt{N}},$

which implies (64).

Next, we show (65). Because the eigenvalues of $W$ are at least $1$,

$h_{W}(x,D)=\left\lVert x(D)-m(D)\mu^{*}\right\rVert_{W}\geq\left\lVert
x(D)-m(D)\mu^{*}\right\rVert_{2}\geq\frac{1}{|\mathbb{S}|^{1/2}}\left\lVert
x(D)-m(D)\mu^{*}\right\rVert_{1}.$

Finally, we show (66).

$\displaystyle\big{\lvert}h_{W}(x,D)-h_{W}(x,D^{\prime})\big{\rvert}$
$\displaystyle=\big{\lvert}\left\lVert
x(D)-m(D)\mu^{*}\right\rVert_{W}-\left\lVert
x(D^{\prime})-m(D)^{\prime}\mu^{*}\right\rVert_{W}\big{\rvert}$
$\displaystyle\leq\left\lVert
x(D)-m(D)\mu^{*}-x(D^{\prime})+m(D^{\prime})\mu^{*}\right\rVert_{W}$
$\displaystyle=\left\lVert x(D^{\prime}\backslash
D)-m(D^{\prime}\backslash)\mu^{*}\right\rVert_{W}$
$\displaystyle\leq\left\lVert x(D^{\prime}\backslash
D)\right\rVert_{W}+m(D^{\prime}\backslash
D)\left\lVert\mu^{*}\right\rVert_{W}.$

Note that for any $v\in\mathbb{R}^{|\mathbb{S}|}$, $\left\lVert
v\right\rVert_{W}\leq\lambda_{W}^{1/2}\left\lVert
v\right\rVert_{2}\leq\lambda_{W}^{1/2}\left\lVert v\right\rVert_{1}$. Because
$\left\lVert x(D^{\prime}\backslash D)\right\rVert_{1}=m(D^{\prime})-m(D)$,
and $\left\lVert\mu^{*}\right\rVert_{1}=1$, we have

$\left\lVert x(D^{\prime}\backslash D)\right\rVert_{W}+m(D^{\prime}\backslash
D)\left\lVert\mu^{*}\right\rVert_{W}\leq
2\lambda_{W}^{1/2}(m(D^{\prime})-m(D)).$

∎

Recall the definition of $h_{\textnormal{ID}}(x,m)$ from Section 6.1: for any
system state $x$ and $m\in[0,1]_{N}$,

(38) $\displaystyle
h_{\textnormal{ID}}(x,m)=\max_{\begin{subarray}{c}m^{\prime}\in[0,1]_{N}\\\
m^{\prime}\leq m\end{subarray}}h_{W}(x,[Nm^{\prime}]).$

Next, we restate and prove Lemma 1, which verifies that
$\\{h_{\textnormal{ID}}(\cdot,m)\\}_{m\in[0,1]_{N}}$ are subset Lyapunov
functions. See 1

###### Proof.

We first show (39). Let $X_{1}^{\prime}$ be the system state after one step of
transition if $A_{0}(i)\sim{{\bar{\pi}}^{*}}(\cdot|S_{0}(i))$ for all $i\in
D$. Then

$\displaystyle h_{\textnormal{ID}}(X_{1}^{\prime},m)-h_{\textnormal{ID}}(x,m)$
$\displaystyle=\max_{\begin{subarray}{c}m^{\prime}\in[0,1]_{N},m^{\prime}\leq
m\end{subarray}}h_{W}(X_{1}^{\prime},m^{\prime})-\max_{\begin{subarray}{c}m^{\prime}\in[0,1]_{N},m^{\prime}\leq
m\end{subarray}}h_{W}(x,m^{\prime})$
$\displaystyle\leq\max_{\begin{subarray}{c}m^{\prime}\in[0,1]_{N},m^{\prime}\leq
m\end{subarray}}\big{(}h_{W}(X_{1}^{\prime},m^{\prime})-h_{W}(x,m^{\prime})\big{)}$
(71)
$\displaystyle\leq\max_{\begin{subarray}{c}m^{\prime}\in[0,1]_{N},m^{\prime}\leq
m\end{subarray}}\lVert
X_{1}^{\prime}([Nm^{\prime}])-x([Nm^{\prime}])P_{{{\bar{\pi}}^{*}}}\rVert_{W},$

where the last inequality can be justified using the same argument as (67).
Therefore,

(72)
$\Big{(}h_{\textnormal{ID}}(X_{1}^{\prime},m)-\big{(}1-\frac{1}{2\lambda_{W}}\big{)}h_{\textnormal{ID}}(x,m)\Big{)}^{+}\leq\max_{\begin{subarray}{c}m^{\prime}\in[0,1]_{N},m^{\prime}\leq
m\end{subarray}}\lVert
X_{1}^{\prime}([Nm^{\prime}])-x([Nm^{\prime}])P_{{{\bar{\pi}}^{*}}}\rVert_{W}.$

For any $i\in[Nm]$, define the random vector
$\xi(i)\in\mathbb{R}^{\left\lvert\mathbb{S}\right\rvert}$ as

$\xi(i)=X_{1}^{\prime}(\\{i\\})-x(\\{i\\})P_{{\bar{\pi}}^{*}}.$

We denote the $s$-th entry of the vector $\xi(i)$ as $\xi(i,s)$. We rewrite
the term on the RHS of (72) as

(73) $\max_{\begin{subarray}{c}m^{\prime}\in[0,1]_{N},m^{\prime}\leq
m\end{subarray}}\big{\lVert}X_{1}^{\prime}([Nm^{\prime}])-x([Nm^{\prime}])P_{{{\bar{\pi}}^{*}}}\big{\rVert}_{W}=\max_{n\in[Nm]}\big{\lVert}\sum_{i\in[n]}\xi(i)\big{\rVert}_{W}.$

Therefore, to prove the bound in (39), it suffices to show that

(74)
$\mathbb{E}\Big{[}\max_{n\in[Nm]}\big{\lVert}\sum_{i\in[n]}\xi(i)\big{\rVert}_{W}\,\Big{|}\,X_{0}=x\Big{]}\leq\frac{4\lambda_{W}^{1/2}}{\sqrt{N}}.$

Conditioned on $X_{0}=x$, we argue that
$\left\lVert\sum_{i\in[n]}\xi(i)\right\rVert_{W}$ is a sub-martingale in $n$
so that we can invoke Doob’s $L_{2}$ maximal inequality to bound the RHS of
(73) (see, e.g., Theorem 4.4.4 of (Durrett, 2019)). Observe that

  * •

$\xi(i)$’s are independent across $i\in[Nm]$;

  * •

For each $i\in[Nm]$ and $s\in\mathbb{S}$,
$\mathbb{E}\left[\xi(i,s)|X_{0}=x\right]=0$.

Therefore, $\sum_{i\in[n]}\xi(i)$ is a martingale in $n$. Because
$\left\lVert\cdot\right\rVert_{W}$ is a convex function,
$\left\lVert\sum_{i\in[n]}\xi(i)\right\rVert_{W}$ is a sub-martingale in $n$.
We apply Doob’s $L_{2}$ maximal inequality to
$\left\lVert\sum_{i\in[n]}\xi(i)\right\rVert_{W}$ to get

(75)
$\mathbb{E}\Big{[}\Big{(}\max_{n\in[Nm]}\Big{\lVert}\sum_{i\in[n]}\xi(i)\Big{\rVert}_{W}\Big{)}^{2}\,\Big{|}\,X_{0}=x\Big{]}\leq
4\mathbb{E}\Big{[}\Big{\lVert}\sum_{i\in[Nm]}\xi(i)\Big{\rVert}_{W}^{2}\,\Big{|}\,X_{0}=x\Big{]}.$

Applying Holder’s inequality to the LHS of (75), we get

(76)
$\displaystyle\mathbb{E}\Big{[}\max_{n\in[Nm]}\Big{\lVert}\sum_{i\in[n]}\xi(i)\Big{\rVert}_{W}\,\Big{|}\,X_{0}=x\Big{]}$
$\displaystyle\leq\mathbb{E}\Big{[}\Big{(}\max_{n\in[Nm]}\Big{\lVert}\sum_{i\in[n]}\xi(i)\Big{\rVert}_{W}\Big{)}^{2}\,\Big{|}\,X_{0}=x\Big{]}^{1/2}$

Using the same argument in (69) with $D=[Nm]$, we bound the RHS of (75) as

(77)
$4\mathbb{E}\Big{[}\Big{\lVert}\sum_{i\in[Nm]}\xi(i)\Big{\rVert}_{W}^{2}\,\Big{|}\,X_{0}=x\Big{]}\leq\frac{16\lambda_{W}}{N}.$

Plugging (76) and (77) into two sides of (75), we get

(78)
$\mathbb{E}\Big{[}\max_{n\in[Nm]}\Big{\lVert}\sum_{i\in[n]}\xi(i)\Big{\rVert}_{W}\,\Big{|}\,X_{0}=x\Big{]}\leq\frac{4\lambda_{W}^{1/2}}{\sqrt{N}},$

which implies (39).

Next, we show (40). By the definition of $h_{\textnormal{ID}}(x,m)$ and the
fact that the eigenvalues of $W$ are at least $1$,

$h_{\textnormal{ID}}(x,m)\geq\left\lVert
x([Nm])-m\mu^{*}\right\rVert_{W}\geq\left\lVert
x([Nm])-m\mu^{*}\right\rVert_{2}\geq\frac{1}{|\mathbb{S}|^{1/2}}\left\lVert
x([Nm])-m\mu^{*}\right\rVert_{1}.$

Finally, we show (41). For simplicity, we omit $m\in[0,1]_{N}$ in the
subscripts. Consider any $m,m^{\prime}\in[0,1]_{N}$. Without loss of
generality, we assume that $m\leq m^{\prime}$. By definition, we rewrite
$h_{\textnormal{ID}}(x,m)$ and $h_{\textnormal{ID}}(x,m^{\prime})$ in the
following form:

$\displaystyle
h_{\textnormal{ID}}(x,m)=\max\big{\\{}h_{\textnormal{ID}}(x,m),h_{W}(x,m)\big{\\}}$
$\displaystyle
h_{\textnormal{ID}}(x,m^{\prime})=\max\big{\\{}h_{\textnormal{ID}}(x,m),\max_{m^{\prime\prime}\in[m,m^{\prime}]}h_{W}(x,m^{\prime\prime})\big{\\}}.$

Observe that for any $a,b,c\in\mathbb{R}$, we have
$\lvert\max\\{a,b\\}-\max\\{a,c\\}\rvert\leq\lvert b-c\rvert$. Letting
$a=h_{\textnormal{ID}}(x,m)$, $b=h_{W}(x,m)$, and
$c=\max_{m^{\prime\prime}\in[m,m^{\prime}]}h_{W}(x,m^{\prime\prime})$, we get

(79)
$\Big{\lvert}h_{\textnormal{ID}}(x,m)-h_{\textnormal{ID}}(x,m^{\prime})\Big{\rvert}\leq\Big{\lvert}\max_{m^{\prime\prime}\in[m,m^{\prime}]}h_{W}(x,m^{\prime\prime})-h_{W}(x,m)\Big{\rvert}.$

We further bound the RHS of (79) as

$\displaystyle\Big{\lvert}\max_{m^{\prime\prime}\in[m,m^{\prime}]}h_{W}(x,m^{\prime\prime})-h_{W}(x,m)\Big{\rvert}$
$\displaystyle\leq\max_{m^{\prime\prime}\in[m,m^{\prime}]}\lvert
h_{W}(x,m^{\prime\prime})-h_{W}(x,m)\rvert$
$\displaystyle\leq\max_{m^{\prime\prime}\in[m,m^{\prime}]}2\lambda_{W}^{1/2}\lvert
m^{\prime\prime}-m\rvert$ (80) $\displaystyle=2\lambda_{W}^{1/2}\lvert
m^{\prime}-m\rvert,$

where in the second inequality we used (66), the Lipschitz continuity of
$h_{W}(x,D)$ in $D$ that we have proved in Lemma 2. Combining (79) and (80),
we have proved (41). ∎

###  D.3. Lemmas and proofs about $L_{1}$ norm

In this subsection, we prove two lemmas about the $L_{1}$ norm that are useful
for the analysis of the set-expansion and set-optimization policies,
considering that they select sets based on the slack $\delta(x,D)$ whose
definition involves $L_{1}$ norm.

We first show that if an optimal single-armed policy ${{\bar{\pi}}^{*}}$
induces an aperiodic unichain, right-multiplying $P_{{\bar{\pi}}^{*}}$ is non-
expansive under the $L_{1}$ norm.

###### Lemma 0 (Non-expansiveness of $P_{{\bar{\pi}}^{*}}$ under the $L_{1}$
norm).

Suppose $P_{{\bar{\pi}}^{*}}$ is an aperiodic unichain. For any distribution
$v\in\Delta(\mathbb{S})$,

(81) $\left\lVert(v-\mu^{*})P_{{\bar{\pi}}^{*}}\right\rVert_{1}\leq\left\lVert
v-\mu^{*}\right\rVert_{1}.$

###### Proof.

For any $v\in\Delta(\mathbb{S})$,

$\displaystyle\left\lVert(v-\mu^{*})P_{{\bar{\pi}}^{*}}\right\rVert_{1}$
$\displaystyle=\sum_{s^{\prime}\in\mathbb{S}}\left\lvert\sum_{s\in\mathbb{S}}(v(s)-\mu^{*}(s))P_{{\bar{\pi}}^{*}}(s,s^{\prime})\right\rvert$
$\displaystyle\leq\sum_{s^{\prime}\in\mathbb{S}}\sum_{s\in\mathbb{S}}\left\lvert
v(s)-\mu^{*}(s)\right\rvert P_{{\bar{\pi}}^{*}}(s,s^{\prime})$
$\displaystyle=\sum_{s\in\mathbb{S}}\left\lvert
v(s)-\mu^{*}(s)\right\rvert\sum_{s^{\prime}\in\mathbb{S}}P_{{\bar{\pi}}^{*}}(s,s^{\prime})$
$\displaystyle=\sum_{s\in\mathbb{S}}\left\lvert v(s)-\mu^{*}(s)\right\rvert$
$\displaystyle=\left\lVert v-\mu^{*}\right\rVert_{1}.$

∎

Next, we show that if all arms in a subset $D$ follow ${{\bar{\pi}}^{*}}$, the
$L_{1}$ distance between the scaled state-count vector $X_{t}(D)$ and the
scaled optimal steady-state distribution $m(D)\mu^{*}$ only increases by a
small amount.

###### Lemma 0.

For any system state $x$ and any subset $D\subseteq[N]$,

(82) $\displaystyle\mathbb{E}\big{[}(\lVert
X_{1}(D)-m(D)\mu^{*}\rVert_{1}-\lVert
x(D)-m(D)\mu^{*}\rVert_{1})^{+}\,\big{|}\,X_{0}=x,A_{0}(i)\sim{{\bar{\pi}}^{*}}(\cdot|S_{0}(i))\forall
i\in D\big{]}\leq\frac{2|\mathbb{S}|^{1/2}}{\sqrt{N}}$

###### Proof.

Let $X_{1}^{\prime}$ be the system state after one step of transition if
$A_{0}(i)\sim{{\bar{\pi}}^{*}}(\cdot|S_{0}(i))$ for any $i\in D$. Then

$\displaystyle\mspace{20.0mu}\left\lVert
X_{1}^{\prime}(D)-m(D)\mu^{*}\right\rVert_{1}-\left\lVert
x(D)-m(D)\mu^{*}\right\rVert_{1}$ $\displaystyle\leq\lVert
X_{1}^{\prime}(D)-m(D)\mu^{*}\rVert_{1}-\left\lVert
x(D)P_{{\bar{\pi}}^{*}}-m(D)\mu^{*}\right\rVert_{1}$ (83)
$\displaystyle\leq\lVert
X_{1}^{\prime}(D)-x(D)P_{{{\bar{\pi}}^{*}}}\rVert_{1},$

where the first inequality follows from applying Lemma 3 with $v=x(D)/m(D)$;
the second inequality is due to the triangular inequality. Therefore,

(84) $\big{(}\left\lVert
X_{1}^{\prime}(D)-m(D)\mu^{*}\right\rVert_{1}-\left\lVert
x(D)-m(D)\mu^{*}\right\rVert_{1}\big{)}^{+}\leq\lVert
X_{1}^{\prime}(D)-x(D)P_{{{\bar{\pi}}^{*}}}\rVert_{1}.$

For any $i\in[Nm_{d}(x)]$, define the random vector
$\xi(i)\in\mathbb{R}^{\left\lvert\mathbb{S}\right\rvert}$ as

$\xi(i)=X_{1}^{\prime}(\\{i\\})-x(\\{i\\})P_{{\bar{\pi}}^{*}}.$

We denote the $s$-th entry of the vector $\xi(i)$ as $\xi(i,s)$. We rewrite
$\lVert X_{1}^{\prime}(D)-x(D)P_{{{\bar{\pi}}^{*}}}\rVert_{1}$ as

(85)
$\big{\lVert}X_{1}^{\prime}(D)-x(D)P_{{{\bar{\pi}}^{*}}}\big{\rVert}_{1}=\big{\lVert}\sum_{i\in
D}\xi(i)\big{\rVert}_{1}.$

Observe that conditioned on $X_{0}=x$, we have the following facts about
$\xi(i)$’s

  * •

$\xi(i)$’s are independent across $i\in D$;

  * •

For each $i\in D$ and $s\in\mathbb{S}$,
$\mathbb{E}\left[\xi(i,s)|X_{0}=x\right]=0$.

Conditioned on $X_{0}=x$, we bound the expectation of $\lVert\sum_{i\in
D}\xi(i)\rVert_{1}^{2}$ as follows:

$\displaystyle\mathbb{E}\Big{[}\Big{\lVert}\sum_{i\in
D}\xi(i)\Big{\rVert}_{1}^{2}\,\Big{|}\,X_{0}=x\Big{]}$
$\displaystyle\leq|\mathbb{S}|\,\mathbb{E}\Big{[}\Big{\lVert}\sum_{i\in
D}\xi(i)\Big{\rVert}_{2}^{2}\,\Big{|}\,X_{0}=x\Big{]}$
$\displaystyle=|\mathbb{S}|\,\mathbb{E}\Big{[}\sum_{s\in\mathbb{S}}\Big{(}\sum_{i\in
D}\xi(i,s)^{2}+2\sum_{0\leq i<i^{\prime}\leq
Nm_{d}(x)-1}\xi(i,s)\xi(i^{\prime},s)\Big{)}\,\Big{|}\,X_{0}=x\Big{]}$
$\displaystyle=|\mathbb{S}|\,\sum_{s\in\mathbb{S}}\sum_{i\in
D}\mathbb{E}\left[\xi(i,s)^{2}\,\Big{|}\,X_{0}=x\right]$
$\displaystyle\leq|\mathbb{S}|\,\sum_{i\in
D}\mathbb{E}\Big{[}\Big{(}\sum_{s\in\mathbb{S}}\left\lvert\xi(i,s)\right\rvert\Big{)}^{2}\,\Big{|}\,X_{0}=x\Big{]}$
(86) $\displaystyle\leq\frac{4|\mathbb{S}|}{N},$

where the first inequality uses from the fact that $\left\lVert
v\right\rVert_{1}\leq|\mathbb{S}|^{1/2}\left\lVert v\right\rVert_{2}$ for any
$v\in\mathbb{R}^{|\mathbb{S}|}$; the first equality is by the definition of
$\left\lVert\cdot\right\rVert_{2}$ on
$\mathbb{R}^{\left\lvert\mathbb{S}\right\rvert}$; the second equality is
because $\xi(i,s)$’s are independent across $i\in D$ and have zero means; the
last inequality uses the fact that
$\sum_{s\in\mathbb{S}}\left\lvert\xi(i,s)\right\rvert=\lVert\xi(i)\rVert_{1}\leq\lVert
X_{1}^{\prime}(\\{i\\})\rVert_{1}+\lVert
x(\\{i\\})P_{{\bar{\pi}}^{*}}\rVert_{1}=2/N$. By the Cauchy-Schwartz
inequality, it follows from (86) that

(87) $\mathbb{E}\Big{[}\Big{\lVert}\sum_{i\in
D}\xi(i)\Big{\rVert}_{1}\,\Big{|}\,X_{0}=x\Big{]}\leq\mathbb{E}\Big{[}\Big{\lVert}\sum_{i\in
D}\xi(i)\Big{\rVert}_{1}^{2}\,\Big{|}\,X_{0}=x\Big{]}^{1/2}\leq\frac{2|\mathbb{S}|^{1/2}}{\sqrt{N}}.$

Combining the above calculations, we get

$\displaystyle\mathbb{E}\big{[}\big{(}\left\lVert
X_{1}^{\prime}(D)-m(D)\mu^{*}\right\rVert_{1}-\left\lVert
x(D)-m(D)\mu^{*}\right\rVert_{1}\big{)}^{+}\,\big{|}\,X_{0}=x\big{]}$
$\displaystyle\leq\mathbb{E}\big{[}\lVert
X_{1}^{\prime}(D)-x(D)P_{{{\bar{\pi}}^{*}}}\rVert_{1}\,\big{|}\,X_{0}=x\big{]}$
$\displaystyle=\mathbb{E}\Big{[}\Big{\lVert}\sum_{i\in
D}\xi(i)\Big{\rVert}_{1}\,\Big{|}\,X_{0}=x\Big{]}$
$\displaystyle\leq\frac{2|\mathbb{S}|^{1/2}}{\sqrt{N}},$

which implies (82).

∎

##  Appendix E Deferred proofs for the ID policy

In this section, we include the proofs of Lemma 3 and 4 deferred from Section
6. We restate them here for the ease of reference.

See 3

See 4

###  E.1. Proof of Lemma 3

Here we prove Lemma 3. To provide some intuition, we consider Figure 2(a) and
view $m_{d}(x)$ as a measure of the fraction of the curve $m\mapsto
h_{\textnormal{ID}}(X_{t},m)$ below the line $m\mapsto\beta(1-m)$. Observe
that $m\mapsto h_{\textnormal{ID}}(X_{t},m)$ is non-decreasing with a bounded
slope and the line $m\mapsto\beta(1-m)$ is strictly decreasing. If we can show
that the curve $m\mapsto h_{\textnormal{ID}}(X_{t},m)$ generally moves
downward in some sense, then $m_{d}(X_{t})$ should be approximately non-
decreasing. More specifically, we show that the part of the curve $m\mapsto
h_{\textnormal{ID}}(X_{t},m)$ below $m\mapsto\beta(1-m)$ does not move upward
by much, by bounding the difference
$h_{\textnormal{ID}}(X_{t+1},m_{d}(X_{t}))-h_{\textnormal{ID}}(X_{t},m_{d}(X_{t}))$,
as we can see in the proof below.

###### Proof of Lemma 3.

Observe that under the ID policy, we clearly have that $D_{t+1}\supseteq
D_{t}$ or $D_{t+1}\subseteq D_{t}$ because both $D_{t+1}$ and $D_{t}$ are of
the form $[n]$. Therefore, to show that the ID policy satisfies 2, it suffices
to bound
$\mathbb{E}\big{[}\big{(}m(D_{t})-m(D_{t+1})\big{)}^{+}\,\big{|}\,X_{t},D_{t}\big{]}=\mathbb{E}\big{[}(m_{d}(X_{t})-m_{d}(X_{t+1}))^{+}\,\big{|}\,X_{t}\big{]}$.

Consider a time step $t\geq 0$ and condition on $X_{t}=x$. We first prove the
following inequality, which will be used to establish an upper bound on
$\mathbb{E}\big{[}(m_{d}(X_{t})-m_{d}(X_{t+1}))^{+}\,\big{|}\,X_{t}=x\big{]}$:

(88) $m_{d}(X_{t+1})\geq
m_{d}(x)-\frac{K_{c/h}}{\beta}\big{(}h_{\textnormal{ID}}(X_{t+1},m_{d}(x))-h_{\textnormal{ID}}(x,m_{d}(x))\big{)}^{+}-\frac{1}{N}.$

By the maximality of $m_{d}(X_{t+1})$, it suffices to show
$K_{c/h}h_{\textnormal{ID}}(X_{t+1},\overline{m})\leq\beta(1-\overline{m})$
for any $\overline{m}\in[0,1]_{N}$ with $\overline{m}\leq
m_{d}(x)-\frac{K_{c/h}}{\beta}\big{(}h_{\textnormal{ID}}(X_{t+1},m_{d}(x))-h_{\textnormal{ID}}(x,m_{d}(x))\big{)}^{+}$.
For any such $\overline{m}$,

$\displaystyle\beta(1-\overline{m})$
$\displaystyle\geq\beta(1-m_{d}(x))+K_{c/h}\big{(}h_{\textnormal{ID}}(X_{t+1},m_{d}(x))-h_{\textnormal{ID}}(x,m_{d}(x))\big{)}^{+}$
$\displaystyle\geq
K_{c/h}h_{\textnormal{ID}}(x,m_{d}(x))+K_{c/h}\big{(}h_{\textnormal{ID}}(X_{t+1},m_{d}(x))-h_{\textnormal{ID}}(x,m_{d}(x))\big{)}^{+}$
$\displaystyle\geq K_{c/h}h_{\textnormal{ID}}(X_{t+1},m_{d}(x))$
$\displaystyle\geq K_{c/h}h_{\textnormal{ID}}(X_{t+1},\overline{m}),$

where the second inequality is because
$K_{c/h}h_{\textnormal{ID}}(x,m_{d}(x))\leq\beta(1-m_{d}(x))$, and the last
inequality is because $h_{\textnormal{ID}}(x,m)$ is _non-decreasing in $m$_
and $\overline{m}\leq m_{d}(x)$. This proves (88).

The inequality (88) implies that

(89)
$\mathbb{E}\big{[}(m_{d}(x)-m_{d}(X_{t+1}))^{+}\,\big{|}\,X_{t}=x\big{]}\leq\frac{K_{c/h}}{\beta}\mathbb{E}\big{[}\big{(}h_{\textnormal{ID}}(X_{t+1},m_{d}(x))-h_{\textnormal{ID}}(x,m_{d}(x))\big{)}^{+}\,\big{|}\,X_{t}=x\big{]}+\frac{1}{N}.$

We now upper bound
$\mathbb{E}\big{[}\big{(}h_{\textnormal{ID}}(X_{t+1},m_{d}(x))-h_{\textnormal{ID}}(x,m_{d}(x))\big{)}^{+}\,\big{|}\,X_{t}=x\big{]}$
by coupling $X_{t+1}$ with a random element $X_{t+1}^{\prime}$ constructed
below. Conditioned on $X_{t}=x$, let $X_{t+1}^{\prime}$ be a random element
denoting the system state at time $t+1$ if we were able to set
$A_{t}(i)=\widehat{A}_{t}(i)$ for all $i\in[Nm_{d}(x)]$. By the drift property
of the subset Lyapunov function $h_{\textnormal{ID}}(\cdot,D)$ established as
(39) in Lemma 1,

$\displaystyle\mspace{23.0mu}\mathbb{E}\big{[}\big{(}h_{\textnormal{ID}}(X_{t+1}^{\prime},m_{d}(x))-h_{\textnormal{ID}}(x,m_{d}(x))\big{)}^{+}\,\big{|}\,X_{t}=x\big{]}$
(90)
$\displaystyle\leq\mathbb{E}\big{[}\big{(}h_{\textnormal{ID}}(X_{t+1}^{\prime},m_{d}(x))-\big{(}1-\frac{1}{2\lambda_{W}}\big{)}h_{\textnormal{ID}}(x,m_{d}(x))\big{)}^{+}\,\big{|}\,X_{t}=x\big{]}\leq\frac{4\lambda_{W}^{1/2}}{\sqrt{N}}.$

We couple $X_{t+1}^{\prime}$ and $X_{t+1}$ such that
$X_{t+1}^{\prime}(\\{i\\})=X_{t+1}(\\{i\\})$ for all
$i\leq\min(Nm_{d}(x),N^{{\bar{\pi}}^{*}}_{t})$. Then

$\displaystyle\mspace{22.0mu}\mathbb{E}\big{[}\big{(}h_{\textnormal{ID}}(X_{t+1},m_{d}(x))-h_{\textnormal{ID}}(x,m_{d}(x))\big{)}^{+}-\big{(}h_{\textnormal{ID}}(X_{t+1}^{\prime},m_{d}(x))-h_{\textnormal{ID}}(x,m_{d}(x))\big{)}^{+}\,\big{|}\,X_{t}=x\big{]}$
$\displaystyle\leq\mathbb{E}\big{[}\big{(}h_{\textnormal{ID}}(X_{t+1},m_{d}(x))-h_{\textnormal{ID}}(X_{t+1}^{\prime},m_{d}(x))\big{)}^{+}\,\big{|}\,X_{t}=x\big{]}$
$\displaystyle=\mathbb{E}\Big{[}\Big{(}\max_{m^{\prime}\in[0,1]_{N},m^{\prime}\leq
m_{d}(x)}h_{W}(X_{t+1},m^{\prime})-\max_{m^{\prime}\in[0,1]_{N},m^{\prime}\leq
m_{d}(x)}h_{W}(X_{t+1}^{\prime},m^{\prime})\Big{)}^{+}\,\Big{|}\,X_{t}=x\Big{]}$
$\displaystyle\leq\mathbb{E}\Big{[}\max_{m^{\prime}\in[0,1]_{N},m^{\prime}\leq
m_{d}(x)}(h_{W}(X_{t+1},m^{\prime})-h_{W}(X_{t+1}^{\prime},m^{\prime}))^{+}\,\Big{|}\,X_{t}=x\Big{]}$
$\displaystyle\leq\mathbb{E}\Big{[}\max_{m^{\prime}\in[0,1]_{N},m^{\prime}\leq
m_{d}(x)}\left\lVert
X_{t+1}([Nm^{\prime}])-X_{t+1}^{\prime}([Nm^{\prime}])\right\rVert_{W}\,\Big{|}\,X_{t}=x\Big{]}$
$\displaystyle\leq\mathbb{E}\big{[}\big{\lVert}X_{t+1}([Nm_{d}(x)]\backslash[N^{{\bar{\pi}}^{*}}_{t}])\big{\rVert}_{W}+\big{\lVert}X_{t+1}^{\prime}([Nm_{d}(x)]\backslash[N^{{\bar{\pi}}^{*}}_{t}])\big{\rVert}_{W}\,\big{|}\,X_{t}=x\big{]}$
(91)
$\displaystyle\leq\frac{2\lambda_{W}^{1/2}}{N}\mathbb{E}\big{[}(Nm_{d}(x)-N^{{\bar{\pi}}^{*}}_{t})^{+}\,\big{|}\,X_{t}=x\big{]}$
(92)
$\displaystyle\leq\frac{4\lambda_{W}^{1/2}}{\beta\sqrt{N}}+\frac{2\lambda_{W}^{1/2}}{N},$

where (91) follows from the facts $\left\lVert
v\right\rVert_{W}\leq\lambda_{W}^{1/2}\left\lVert v\right\rVert_{1}$ for any
vector $v$ and that $\left\lVert X_{t+1}(D)\right\rVert_{1}=\left\lVert
X_{t+1}^{\prime}(D)\right\rVert_{1}=m(D)$ for any $D\subseteq[N]$, and (92)
applies the bound on
$\mathbb{E}\big{[}(Nm_{d}(x)-N^{{\bar{\pi}}^{*}}_{t})^{+}\,\big{|}\,X_{t}=x\big{]}$
in Lemma 2.

Combining (89), (90) and (92), we get

(93)
$\mathbb{E}\big{[}(m_{d}(x)-m_{d}(X_{t+1}))^{+}\,\big{|}\,X_{t}=x\big{]}\leq\frac{4K_{c/h}\lambda_{W}^{1/2}(1+\beta)}{\beta^{2}\sqrt{N}}+\frac{2K_{c/h}\lambda_{W}^{1/2}+\beta}{\beta
N}.$

∎

###  E.2. Proof of Lemma 4

###### Proof of Lemma 4.

Lemma 4 almost follows directly from the definition $D_{t}=[Nm_{d}(X_{t})]$
with

(94) $m_{d}(X_{t})=\max\\{m\in[0,1]_{N}\colon
K_{c/h}h_{\textnormal{ID}}(X_{t},m)\leq\beta(1-m)\\}.$

We just need to handle the discretization effect where $m_{d}(X_{t})$ is a
multiple of $1/N$.

It suffices to focus on the case $m_{d}(X_{t})<1$. By (94),

(95)
$K_{c/h}h_{\textnormal{ID}}\Big{(}X_{t},m_{d}(X_{t})+\frac{1}{N}\Big{)}>\beta\Big{(}1-m_{d}(X_{t})-\frac{1}{N}\Big{)}.$

By the Lipschitz continuity of $h_{\textnormal{ID}}(x,m)$ stated in (41),

(96)
$K_{c/h}h_{\textnormal{ID}}\Big{(}X_{t},m_{d}(X_{t})+\frac{1}{N}\Big{)}\leq
K_{c/h}h_{\textnormal{ID}}\Big{(}X_{t},m_{d}(X_{t})\Big{)}+\frac{2K_{c/h}\lambda_{W}^{1/2}}{N}.$

Combining (95) with (96), we get

$\beta(1-m_{d}(X_{t}))<K_{c/h}h_{\textnormal{ID}}(x,m_{d}(X_{t}))+\frac{2K_{c/h}\lambda_{W}^{1/2}+\beta}{N}.$

∎

##  Appendix F Proof of Theorem 4 (Optimality gap of Set-Expansion Policy)

In this section, we prove Theorem 4 using the framework established in Section
5. This section is organized as follows. In Section F.1, we define the subset
Lyapunov functions for the set-expansion policy. In Section F.2, we recall the
definition of the focus set of the set-expansion policy. In Section F.3, we
present three lemmas verifying that the set-expansion policy satisfies
Conditions 1, 2 and 3, respectively, and prove Theorem 4 by citing Theorem 2
in our framework. These three lemmas are subsequently proved in Sections F.4,
F.5 and F.6, respectively.

###  F.1. Subset Lyapunov functions

Here we use the class of functions $\\{h_{W}(x,D)\\}_{D\subseteq[N]}$ defined
in Section D.2 as subset Lyapunov functions. Recall that for any system state
$x$ and $D\subseteq[N]$,

(63) $\displaystyle h_{W}(x,D)$ $\displaystyle=\left\lVert
x(D)-m(D)\mu^{*}\right\rVert_{W},$

where $W$ is the matrix defined in Definition 1; $\left\lVert
u\right\rVert_{W}=\sqrt{uWu^{\top}}$ for any row vector $u$. Lemma 2 proved in
Section D.2 verifies that $\\{h_{W}(x,D)\\}_{D\subseteq[N]}$ are subset
Lyapunov functions. We restate the lemma below.

See 2

###### Remark 0.

We provide further insights into working with our focus-set approach by
discussing the factors and constraints that result in different choices subset
Lyapunov functions in the analysis of the set-expansion policy and the
analysis of the ID policy. In the analysis of the set-expansion policy, the
subset Lyapunov functions are only used to apply Theorem 2; any subset
Lyapunov functions work as long as they satisfy Definition 1. We stick to
$\\{h_{W}(x,D)\\}_{D\subseteq[N]}$ to make our argument concrete.

In contrast, in the analysis of the ID policy, the subset Lyapunov functions
are not only used to apply Theorem 2, but also used to define the focus set.
Consequently, in addition to Definition 1, the subset Lyapunov functions for
the ID policy, $\\{h_{\textnormal{ID}}(x,m)\\}_{m\in[0,1]_{N}}$, is carefully
constructed to satisfy additional properties. One such property is being non-
decreasing in $m$, which is essential to ensure that the focus-set
$[Nm_{d}(X_{t})]$ defined based on
$\\{h_{\textnormal{ID}}(x,m)\\}_{m\in[0,1]_{N}}$ can be proved to satisfy 2
(see the proof of Lemma 3).

###  F.2. Focus set

The focus-set $D_{t}$ of the set-expansion policy has been defined in the
pseudo-code of the set-expansion policy in Algorithm 2. For the ease of
reference, we repeat this definition below.

The focus set $D_{t}$ is updated in each time step based on the current system
state $X_{t}$ and the previous focus set $D_{t-1}$, where we let
$D_{-1}=\emptyset$. For any $t\geq 0$, $D_{t}$ either expands or shrinks
compared with $D_{t-1}$, i.e., either $D_{t}\supseteq D_{t-1}$ or
$D_{t}\subseteq D_{t-1}$. When $D_{t}$ expands, it is chosen as a maximal set
among all sets $D$ such that $\delta(X_{t},D)\geq 0$, where

$\delta(X_{t},D)=\beta(1-m(D))-\left\lVert
X_{t}(D)-m(D)\mu^{*}\right\rVert_{1}.$

When $D_{t}$ shrinks, it is chosen as a set with the largest $m(D)$ among all
sets $D$ such that $\delta(X_{t},D)\geq 0$.

###  F.3. Lemmas for verifying Conditions 1, 2 and 3, and the proof of Theorem
4

Next, we establish Lemma 1, 2 and 3, which verify that the set-expansion
policy in Algorithm 2 satisfies Conditions 1, 2 and 3, respectively. Then we
apply Theorem 2 in our framework to prove Theorem 4.

###### Lemma 0 (Set-expansion policy satisfies 1).

Consider the set-expansion policy in Algorithm 2. For any $t\geq 0$, there
exists a subset $D_{t}^{\prime}\subseteq D_{t}$ such that for any $i\in
D_{t}^{\prime}$, the policy chooses $A_{t}(i)=\widehat{A}_{t}(i)$, and

(97) $\mathbb{E}\big{[}m(D_{t}\backslash
D_{t}^{\prime})\,\big{|}\,X_{t},D_{t}\big{]}\leq\frac{1}{\sqrt{N}}+\frac{1}{N}\quad
a.s.$

###### Lemma 0 (Set-expansion policy satisfies 2).

Consider the set-expansion policy in Algorithm 2. For any $t\geq 0$,

(98)
$\mathbb{E}\big{[}(m(D_{t})-m(D_{t+1}))^{+}\,\big{|}\,X_{t},D_{t}\big{]}\leq\frac{2|\mathbb{S}|^{1/2}+2}{\beta\sqrt{N}}+\frac{2+(\beta+2)|\mathbb{S}|}{\beta
N}\quad a.s.$

###### Lemma 0 (Set-expansion policy satisfies 3).

Consider the set-expansion policy in Algorithm 2. For any $t\geq 0$,

(99)
$1-m(D_{t})\leq\frac{|\mathbb{S}|^{1/2}}{\beta}h_{W}(X_{t},D_{t})+\frac{3}{\beta
N}\quad a.s.$

###### Proof of Theorem 4.

By Lemma 1, 2 and 3, the set-expansion policy satisfies Conditions 1, 2 and 3
with the subset Lyapunov functions $\\{h_{W}(x,D)\\}_{D\subseteq[N]}$. We
apply Theorem 2 to obtain the optimality gap bound stated in Theorem 4. Note
that we relax all $1/N$ factors to $1/\sqrt{N}$ when deriving the bound. ∎

###  F.4. Proof of Lemma 1

###### Proof of Lemma 1.

Recall that in the action rectification step, the set-expansion policy selects
$\lceil\sum_{i\in D_{t}}A_{t}(i)-\alpha N\rceil$ arms to set
$A_{t}(i)\neq\widehat{A}_{t}(i)$ if $\sum_{i\in D_{t}}A_{t}(i)\geq\alpha N$,
and selects $\lceil\sum_{i\in D_{t}}(1-A_{t}(i))-(1-\alpha)N\rceil$ arms to
set $A_{t}(i)\neq\widehat{A}_{t}(i)$ if $\sum_{i\in
D_{t}}(1-A_{t}(i))\leq(1-\alpha)N$. For all unselected arms in $D_{t}$, we
have $A_{t}(i)=\widehat{A}_{t}(i)$. We choose $D_{t}^{\prime}$ to be the
unselected arms. Then it suffices to show that for any $t\geq 0$ and $(x,D)$
such that $(X_{t},D_{t})=(x,D)$ with a positive probability,

(100) $\displaystyle\mathbb{E}\Big{[}\big{(}\sum_{i\in
D}\widehat{A}_{t}(i)-\alpha N\big{)}^{+}+\big{(}\sum_{i\in
D}(1-\widehat{A}_{t}(i))-(1-\alpha)N\big{)}^{+}\,\Big{|}\,X_{t}=x,D_{t}=D\Big{]}$
$\displaystyle\leq\sqrt{N}$

Observe that given $X_{t}=x$ and $D_{t}=D$, $\widehat{A}_{t}(i)$ are
independent for each $i\in D$. Moreover, $\mathbb{E}\big{[}\sum_{i\in
D}\widehat{A}_{t}(i)|X_{t}=x,D_{t}=D\big{]}=NC_{{\bar{\pi}}^{*}}(x,D)$, where
$C_{{\bar{\pi}}^{*}}(x,D)=\sum_{s\in\mathbb{S}}x(D,s){{\bar{\pi}}^{*}}(1|s)$.
By Cauchy-Schwartz,

$\displaystyle\mathbb{E}\Big{[}\Big{\lvert}\sum_{i\in
D}\widehat{A}_{t}(i)-NC_{{\bar{\pi}}^{*}}(x,D)\Big{\rvert}\,\Big{|}\,X_{t}=x,D_{t}=D\Big{]}$
$\displaystyle\leq\mathbb{E}\Big{[}\big{(}\sum_{i\in
D}\widehat{A}_{t}(i)-NC_{{\bar{\pi}}^{*}}(x,D)\big{)}^{2}\,\Big{|}\,X_{t}=x,D_{t}=D\Big{]}^{\frac{1}{2}}$
$\displaystyle=\Big{(}\sum_{i\in
D}\text{Var}{\big{[}\widehat{A}_{t}(i)\,\big{|}\,X_{t}=x,D_{t}=D\big{]}}\Big{)}^{\frac{1}{2}}$
$\displaystyle\leq\sqrt{N}.$

Also, for each $(x,D)$ such that $(X_{t},D_{t})=(x,D)$ with a positive
probability, $\delta(x,D)\geq 0$, so we have $\left\lVert
x(D)-m(D)\mu^{*}\right\rVert_{1}\leq\beta(1-m(D))$. We can bound $\left\lvert
C_{{\bar{\pi}}^{*}}(x,D)-\alpha m(D)\right\rvert$ as

(101) $\displaystyle\left\lvert C_{{\bar{\pi}}^{*}}(x,D)-\alpha
m(D)\right\rvert$
$\displaystyle=\sum_{s\in\mathbb{S}}(x(D,s)-m(D)\mu^{*}(s)){{\bar{\pi}}^{*}}(1|s)$
$\displaystyle\leq\left\lVert x(D)-m(D)\mu^{*}\right\rVert_{1}$ (102)
$\displaystyle\leq\beta(1-m(D)),$

where (101) uses the fact that
$\sum_{s\in\mathbb{S}}\mu^{*}(s){{\bar{\pi}}^{*}}(1|s)=\alpha$. By (102), we
have $NC_{{\bar{\pi}}^{*}}(x,D)\in[\alpha N-(N-|D|),\alpha N]$. Therefore,

$\displaystyle\mspace{20.0mu}\mathbb{E}\Big{[}\big{(}\sum_{i\in
D}\widehat{A}_{t}(i)-\alpha N\big{)}^{+}+\big{(}\sum_{i\in
D}(1-\widehat{A}_{t}(i))-(1-\alpha)N\big{)}^{+}\,\Big{|}\,X_{t}=x,D_{t}=D\Big{]}$
$\displaystyle=\mathbb{E}\Big{[}\big{(}\sum_{i\in D}\widehat{A}_{t}(i)-\alpha
N\big{)}^{+}+\big{(}\alpha N-(N-|D|)-\sum_{i\in
D}\widehat{A}_{t}(i)\big{)}^{+}\,\Big{|}\,X_{t}=x,D_{t}=D\Big{]}$
$\displaystyle\leq\mathbb{E}\Big{[}\Big{\lvert}\sum_{i\in
D}\widehat{A}_{t}(i)-NC_{{\bar{\pi}}^{*}}(x,D)\Big{\rvert}\,\Big{|}\,X_{t}=x,D_{t}=D\Big{]}$
$\displaystyle\leq\sqrt{N}.$

∎

###  F.5. Proof of Lemma 2

###### Proof of Lemma 2.

Observe that we obviously have $D_{t+1}\supseteq D_{t}$ or $D_{t+1}\subseteq
D_{t}$ by the definition of the set-expansion policy in Algorithm 2.
Therefore, we only need to show that

(98)
$\mathbb{E}\big{[}(m(D_{t})-m(D_{t+1}))^{+}\,\big{|}\,X_{t},D_{t}\big{]}\leq\frac{2|\mathbb{S}|^{1/2}+2}{\beta\sqrt{N}}+\frac{2+(\beta+2)|\mathbb{S}|}{\beta
N}\quad a.s.$

We fix $t\geq 0$ and take $(x,D)$ such that $(X_{t},D_{t})=(x,D)$ with a
positive probability. First, we claim that conditioned on
$(X_{t},D_{t})=(x,D)$,

(103)