Restless Bandits with Average Reward: Breaking the Uniform Global Attractor Assumption
Authors: Yige Hong
Qiaomin Xie
Yudong Chen
Weina Wang
Venue: NeurIPS 2023 spotlight (2023)
Keywords: restless bandits
average reward MDP
simulation-based method
asymptotic optimality
TL;DR: We study the average reward restless bandits, and propose the first asymptotically optimal policy that does not make the uniform global attractor assumption.

Abstract: We study the infinite-horizon restless bandit problem with the average reward criterion, in both discrete-time and continuous-time settings.
A fundamental goal is to efficiently compute policies that achieve a diminishing optimality gap as the number of arms, $N$, grows large. 
Existing results on asymptotic optimality all rely on the uniform global attractor property (UGAP), a complex and challenging-to-verify assumption. 
In this paper, we propose a general, simulation-based framework, Follow-the-Virtual-Advice, that converts any single-armed policy into a policy for the original $N$-armed problem. 
This is done by simulating the single-armed policy on each arm and carefully steering the real state towards the simulated state. 
Our framework can be instantiated to produce a policy with an $O(1/\sqrt{N})$ optimality gap. 
In the discrete-time setting, our result holds under a simpler synchronization assumption, which covers some problem instances that violate UGAP. 
More notably, in the continuous-time setting, we do not require \emph{any} additional assumptions beyond the standard unichain condition. 
In both settings, our work is the first asymptotic optimality result that does not require UGAP.

Restless Bandits with Average Reward: Breaking the Uniform Global Attractor Assumption
Yige Hong
Qiaomin Xie² Yudong Chen² Carnegie Mellon University University of Wisconsin-Madison [yigeh, weinaw] cmu, edu {qi qqiammin.c laaammi.iii xie, yudong. chen)@visc.edu
Weina Wang'
Abstract
We study the infinite-horiza restless bandit problem with the average reward crite- rion, in both discrete-time and continuous settings. A fundamental goal efficiently compute policies that achieve diminishing optimality gap the num- ber arms, N, grows large. Existing results on asymptotic optimality all rely on the uniform global attractor property (UGAP), complex and Challenging-to-ertee assumption. In this paper, we propose a general, simulation-bed based framework, Follow- Virtual- Advice, that converts any single-arme policy into pol- icy for the original N -armed problem. This is done by simulating the single-armed policy on each arm and carefully steering the real state towards the simulated state. Our framework optimality gap. In the discrete- time setting, our result holds under a simpler syn- chronization assumption, which covers some problem instances that violate UGAP. More notably, in the continuous-time setting, we do not require any additional assumptions beyond the standard unichain condition. In both settings, work is the first asymptotic optimality result that does not require UGAP.
be instantiated to produce a policy with an ((1/VN)
Introduction
The restless bandit (RB) problem is a dynamic decision decision-making problem that involves number of Markov decision processes (MDPs) coupled by constraint. Each MDP, referred to as an arm, has binary action space, (passive, active). At every decision epoch, the decision maker is constrained to select fixed number of arms activate, with the goal of maximizing the expected reward accrued. The RB problem finds applications across a spectrum of domains, including wireless communication [LTT1]] congestion control [AAD]ı]] queueing models [ABG09], crawling web content [AB19]. machine maintenance [GM005, clinical trials [VBW15) to name few.
In this paper, focus infinite-horizon RBs with the average-reward criterion. Since the exact optimal policy is PSPACE- to compute [PT99), it is of great theoretical and practical interest focus on policies that approximately achieve the optimal value and compute such policies in an efficient matter. The optimality gap of a policy is defined as the difference between its average reward per arm and that of an optimal policy. In a typical asymptotic regime where the number of arms, N, grows large, we say that a policy is asymptotically optimal if its optimality gap is o(1) as N - oc.
Prior work and the uniform global attractor property assumption. Prior work has studied the celebrated Whittle index policy [Whi88] and LP- Priority policies (Ver1ó) and established sufficient conditions for their asymptotic optimality [WW90] /erl6, GGY20 GGY22). One key assumption underpinning all prior work is the uniform global attractor property (UGAP) -lso known as globally asymptotic stability which pertains to the mean-field/fum limit of the restless bandit system in the
"Corresponding author
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Paper
Policy
Optimality Gap
Conditions
GGG20
Whitte Index
((exp(-ci)
UGAP & Non-singular
Discrete-time setting
GGY22
LP-Priority
O(exp(-cN)
UGAP & Non-degenerate
This paper
FTVA(TT)
O(1/vN)
SA
WW9
Whittle Index
o(1)
UGAP
Continuous- time setting
Ver16
LP-Priority
o(1)
UGAP
GGY20
Whittle Index
((exp(-cN))
UGAP & Non-singular
GGY22
LP-Priority
O(exp(-cNV)
UGAP & Non-degenerate
This paper
FIVA-CT(""") O(1/VN)
Table I: Optimality gap results and conditions. "All papers require the standard unichain assumption.
asymptotic limit N + UGAP stipulates that the system's 's state distribution in the mean-field limit converges to the optimal state distribution attaining the maximum reward, from any initial distribution. It has been well recognized that UGAP is highly technical assumption and challenging to verify: the primary way to test UGAP is numerical simulations; see [GGY20 for a detailed discussion.
More recent work studies the rate at which the optimality gap converges to zero. The work [GGY20) and [GGY222 prove striking ((exp(-eN)) optimality gap for the Whittle index policy and LP- Priority policies, respectively, where is constant. In addition to UGAP, these results require non-singularity or non-degenerate condition. We are not aware of any rate convergence result without assuming UGAP or non-singullariy/ddeeeennn See Table[[for summary.
Therefore, prior work on average- reward restlest bandit leaves two fundamental questions open:
1. Is it possible to achieve asymptotic optimality without UGAP?
2. Is is possible to establish non-trivial convergence rate for the optimality gap in the absence of the non-singularnoo--eeennee
assumption (and UGAP)?
Our contributions. We consider both the discrete-time and continuous-time settings of the average-reward restless bandit problem. We propose a general, simulation- based framework, Follow- Mallow-the-Vee wwweeherrtallaaaaeeeee Advice (FTVA) and its continuous-time variant FTVA-CT, which convert any single-armed policy into a policy for the original N-armed problem, with a vanishing performance loss. Our framework can be instantiated to produce policy with an 0(1/v/) optimality gap, under the conditions summarized in Table which we elaborate later.
Under our framework, computing an asymptotically optimal policy is efficient since it reduces to deriving an optimal single-armed policy, whose complexity is independent of N. The resultant policy can be implemented with a linear-in-N computational cost and some of its subroutines can be implemented in a distributed fashion over the arms (see Appendix B for more details).
Our results can also be extended to RBs with heterogeneous arms. See Appendix Hor details.
We now elaborate on the conditions in Table 1 the discrete-time setting, result holds under condition called the Synchronization Assumption (SA), in addition the standard unichain assumption required by all prior work. The SA condition, which is imposed on the MDP associated with single arm, admits several intuitive suf- ficient conditions. While it is unclear whether SA sub- sumes UGAP, we show that there exist problem instances that violate UGAP but satisfy SA. Figure [ shows one such instance (constructed by GGY20) described Ap- pendix G for ease of reference), in which the Whittle Index and LP-Priority policies coincide and have a non- diminishing optimality gap, whereas our policy, named as FTVA(T")) ), is asymptotically optimal. In addition, our O(1/VN N) bound on the optimality gap does not require a htwpllarriiioooonddeneeeeeee assumption.
0.125
0.120
Avg Reward
0.115
0.110
0.105
Upper bound
0.100
policy: FTVA(R")
Whittle Index/1 P-Priority
0.095
400
600
800
1000
N
Figure 1: An discrete-time RB problem that satisfies SA but not UGAP.

---

More notably, in the continuous-time setting, we completely eliminate the UGAP assumption. We show that our policy FTVA-CT(T*) achieves an O(1/VN) optimality gap under only the standard unichain assumption (which is required by all prior work).
In both settings, our results are the first asymptotic optimality results that do not require UGAP. We point out that UGAP is considered necessary for LP-Priority policies [Vee16 GGY22 Our policy, FTVA(""), ) is not a priority policy. As such, we hope our results open up new directions for developing new classes of RB algorithms that achieve asymptotic optimality without relying on UGAP.
Intuitions. Our algorithm and many existing approaches solve an LP relaxation of the original problem. The solution of the LP induces a policy and gives an "ideal" distribution for the system state. Existing approaches directly apply the LP policy to the current system state, and then perform simple rounding of the resulting actions so as to satisfy the budget constraint. When the current system state is far from the ideal distribution, the actual actions after rounding may deviate substantially from the LP solution and thus, in the absence of UGAP, would fail to drive the system to the optimum.
Our FTVA framework, in contrast, prioritizes constraint satisfaction. We apply the LP solution to the state of simulated system, which constructed carefully so that the resulting actions satisfy the constraint after a minimal amount of rounding. Consequently, starting from any initial state, our policy steers the system towards the ideal distribution and hence approximates the optimal value.
This method is inspired by the approach in [3XW23], which also involves a simulated system, but for a stochastic bin-packing problem.
Other related work. Another condition extensively discussed in the RB literature is the indexability condition [Whi88], which is necessary for the Whittle index policy to be well-defined, but not required by I.-Priority policies [Ver16]. However, indexability alone does not guarantee the asymptotic optimality of Whittle index.
So far we have discussed prior work on infinite-horizon RBs with average reward. For the related setting of finite-horizon total reward RBs, a line of recent work has established an O(1/vN /N) opti- mality gap (HF17 ZCCWI9 BS20 GNITTKK and ((exp(-c.V) gap assuming non-degeneracy [ZF21 GGY22). For the infinite- horiiznn discounted reward setting. [ZF22, GNJT23] propose poli-
cies with O(1/VN optimality gap without assuming indexability and UGAP. While these results framework can be applied to their settings. For more detailed discussion of prior work, see Appendix A
are not directly comparable to ours, it is of future interest see if our simulation-
Paper Organization. While our continuous result stronger, the discrete-time setting is more accessible. Therefore, we first discuss the discrete-time setting, which includes the problem statement in Section our proposed framework, Follow-
in Section 3 and our results on the optimality gap in Section 4 Results for the continuous-time setting are presented in Section 5
We conclude the paper in Section 6 Proofs and additional discussion are given in the appendices.
2 Problem Setup
Consider the fefinit-hoorionn discrete-tine time restless bandit problem with N arms indexed by [N] A (1,2...., .N.. Each arm is associated with an MDP described by the tuple (S, A, P,r). Here S is the state space, assumed to be finite; A {0, 1} is the action set, and we say the arm is activated or pulled when action is applied; P : S x A x S - [0, 1] is the transition kernel, where P(s, a, 8') is the probability of transitioning from state s to state s' upon taking action a; (r(s, Ses. is the reward function, where r(x, a) is the reward for taking action a in state 8. Throughout the paper, we assume that the transition kernel P unichain [Put05]: that is. under any Markov policy for this single-armed MDP (S, A, P. r), the induced Markov chain has single recurrent class. The unichain assumption is standard in most existing work on restless bandits (WW90 GGY20 GGY22 Verló We will discuss relaxing the unichain assumption in Appendix D
In the above setting, we subject to a budger constraint that exactly aN arms must be activated in each time step, where a E (0, 1) is a given constant and aN is assumed to be an integer for simplicity. This Narmed RB problem can be represented by the tuple (N, S.N A.N P, r, NNN).
policy æ for the -aamedd problem specifies the action for each of the N arms based on the history of states and actions. Under policy π, let S (t) E S denote the state of the ith arm at time t, and we
3

---

call (t) - (t) E SN the system state. Similarly, let A E A denote the action applied the äth arm at time f, and let (t) & (AT()))E(N) E A denote the joint action vector.
The controller's goal is to find a policy that maximizes the long-run average of the total expected reward from all N arms, subject to the budget constraint, assuming full knowledge of the model:
N
maximize policy
V
lim T-2
B (1),
t=
N Σ
subject to
(t) - aN, A4 1220 0.
Under the unichain assumption, the value V of any policy is independent of the initial state. Let VV & sup, V denote the optimal value. The optimality gap of i is defined Vi= VN- We say policy π is asymptotically optimal if its optimality gap converges to 0 as - Do.
Classical theory guarantees that for finite-state Markov decision process like an RB, there exists an optimal policy that is Markovian and stationary [Put05]. Nevertheless, the policies we propose are not Markovian policies; rather, they have internal states. Under such policy the system state S (t) together with the internal state form Markov chain, and the action A (t) depends on both the system and internal states. We design policy such that this Markov chain has stationary distribution. Let S" (Do) and A (oo) denote the random elements that follow the stationary distributions of ST S*((t and A (t), respectively. Then the average reward of ı is equal to Vţ= N E E (r(5) (co), A (oc))). In later sections, when the context is clear, we drop the superscript from S and AT
3
A simulation-based framework
In this section, we present our framework, sallow-the-Virtuale single-armed problem, which involves "average arm" from the original N-armed problem. We then use the optimal single-armed policy to construct the proposed policy FTVA(#*).
(FTVA). We first describe
3.1 Single-armed problem
The single-armed problem involves the MDP (S, A. P,r) associated with single arm (say arm 1 without loss of generality), where the budget is satisfied on average. Formally, consider the problem:
T-1
maximize policy R
lim
E ((((ST())
T
t=0
subject to
lim T- T
Σ 1-0
E [AT(O)] =
(4)
The constraint (4) stipulates that the average rate of applying the active action must equal Various equivalent forms of this single-armed problem have been considered prior work [WW90] GGY20 GGY22 [er16])
By virtue of the unichain assumption, the single-armed problem can be equivalently rewritten as the following linear program, where each decision variable y(s, a) represents the steady-state probability that the arm is in state s taking action a:
maximize (CC..
Σ r(s,a)y(s,) eES,eEA
(LP)
subject to
Σ yss 1) = =a
(5)
Σ v(s', P(s' a, a) Σ u(ss,), VsEs
(6)
e'ES,aEA
aEk
Σ v(s,a) = 1, v(3,a) 2 0, A.
(7)

---

Algorithm Folloo--the-Virtuulll--ddda (FTVA): A simulation-based framework
Input: N-armed problem (N, AN, P,r, aN), initial states S(0), single-armed policy क Initialize: Virtual states (()) are N ii.d. samples following the stationary distribution of ा
1: for t= 0, 0, 2... do
2: Independently sample (,(t) x(-1S((t) for each arm i E [N] Generate virtual actions
3: if ".= (t) 2 aN then
b Select a set of oN arms to activate
4:
A - a set of a.V arms chosen from {i: (,) 1} (any tic-breaking)
5:
else
6:
B - set of oN - E (t(t) arms chosen from fd: (t) = 0} (any tie-breaking)
7:
A + (i: A.(t) - UB
8:
Apply A,(t) = 1 and observe S,(t + 1) for each arm E A
9:
Apply Ax(t) 0 and observe S,(t + 1) for each arm & A
10:
for i = 1,2.3.... do
> Progress virtual processes
11:
if (t) (t) and (t) = (t) then
Couple virtual and real states
12:
1) S1 +1)
13:
else
14:
Independently sample St(t + 1) from the distribution ((())),
Here (5) corresponds to the relaxed budget constraint, (6) is the flow balance equation, and 6 guarantee that y(s, a)'s are valid steady-state probabilities.
By standard results for average reward MDPs [Pur05] optimal solution (v"(s, sES.EEE to LP
induces an optimal policy म* the single-armed problem via the following formula:
(als) = f (s" (s, vs,, 11/2
if yf v 0, yf (s.
forseS, (8)
Let Vid Vi8 be the optimal value of (LP and the single-armed problem.
(LP be viewed policy π and set ss,, a) to be the fraction of arms in state taking action a in steady state under n,
relaxation of the N-armed problem. To this, take any N-armed
ie., v(s,a) E [ Eim (())())===.A(()))))))
Whevener и satisfies the budget constraint (2) {v(s, a}} satisfies the relaxed constraint (5) and the consistency constraints
Therefore, the
optimal value of (LP) is an upper bound of the optimal value of the N-armed problem: Viel Z V
3.2 Constructing the N-armed policy
a simulation framework for the N-armed problem. FTVA takes as input any single-armed policy that satisfies the relaxed budget constraint 4 and converts it into --armed policy, denoted by FTVA(T). Of particular interest is when म is an optimal single-armed policy, which leads to our result on the optimality gap. Below we introduce general framework of FTVA without imposing any restriction on the input policy म.
We now present
The proposed policy FTVA(T) has main components:
Virtual single-armed processes. Each arm i simulates a virtual single-armed process, whose state is denoted as (t), with action (t) chosen according to म. To make the distinction conspicuous, we sometimes refer to the state St(t) and action (t) in the original N -armedd problem as the real state/action. The virtual processes associated with different arms independent.
Follow the virtual actions. At each time step t, choose the real actions A,(t)'s to best match the virtual actions (t)''s, ss the extent allowed by the budget constraint ΣN Ai(t) aN.
FTVA is presented in detail in Algorithm 1 Note that we use appropriate coupling in Algorithm 1 to ensure that the virtual processes (t), At()))s are independent and each follows the Markov chain induced by the single-armed policy म. FTVA is designed to steer the real states to be close to
the virtual states, thereby ensuring small conversion loss V -V V- FTVA(R) Here recall that V is the

---

7/8
state
61
518
state
2/8
1/5
250
265
278
time slot
Figure 2: Time evolution of the fraction of arms in each state under LP-Priority (upper), or after switching to FTVA(# (lower) since time slot 250. The x-axis represents the time slot, which ranges from 250 to 289: the y-axis represents the states; the color represents the fraction of arms in each state at each time slot. The colors and magnitudes of the arrows represent the average directions and rates at which the arms move away from each state.
average reward achieved by the input policy स in the single-armed problem, and that VN FFTAA(() the average reward per arm achieved by policy FTVA(T) in the N-armed problem.
3.3 Discussion on FTVA and the role of virtual processes
In this subsection, we provide insights into the mechanism of FTVA and explain the crucial role of the virtual processes. In particular, we contrast FTVA with the alternative approach of directly using the real states to choose actions, e.g., by applying the single-armed policy म each arm's 'ss real state. We note that existing policies are essentially real-state-basee so the insights here can also explain why UGAP is necessary for existing policies to have asymptotic optimality.
We first observe that the above two approaches are equivalent the absence the budget constraint. In particular, even if the initial virtual state and real state of arm are different, they will synchronize (i.e., become identical) in finite time by chance under mild assumptions (see Section 4.1.. After this event, if there (t) (t) (t) for all f, and the virtual states will remain identical to real states.
constraint, each arm will consistently follow the virtual actions, i.e.,
In the presence of the budget constraint, the arms may not remain synchronized, so the virtual pro- cesses become crucial: they guarantee that the virtual actions (t म (t)( nearly satisfy budget constraint, which allows the real system approximately follow the virtual actions remain syn- chronized. see this, note that regardless of the current real states, the N virtual states Si,..., SN independently follow the single-armed policy म", so, in the long run, each (S,(Do), (oo)) is dis- tributed per y" (.,,,, the optimal solution to (P)) For large N, the sum Σ Á,(oo) concentrates around its expectation N NE. y/" (/"
V and thus tightly satisfy the budget constraint. In contrast, the actions generated by applying स to the real states are likely to significantly violate the constraint, especially when the empirical distribution of the current real states deviates from y (:))).
An example. We provide a concrete example illustrating the above arguments. Suppose the state space for each arm is E {0, I...., 7). We label action 1 the preferred action for states and action ( for the other states. For an arm in state s, applying the preferred action moves the arm to state (s 1) mod 8 with probability P.R, and applying the other action moves the arm state (s - 1) with probability P..:; the arm stays at state otherwise. One unit of reward is generated when the arm goes from state to state We assume that the budget N/2 and set {pS,R, P..1.) such that the optimal solution of (LP) is y (s. 1) = 1/8 for = 0, 1, 2, and y/ (s. 0) 1/8 for 4, 5, 6, 7. That is, the optimal state distribution is uniform(S), and the optimal single-armed policy #* always takes the preferred action so to traverse state often possible.

---

To see why this MDP makes the corresponding N a-areed system tricky to control, consider the situation where Ps.1. >> Ps,R and most arms are in state 0. Those arms prefer actions 1 to move towards state 7. However, there are only 2/2 units of budget. If we break ties uniformly at random, each arm is not pulled with probability 1/2 each time slot and is likely to return to before they leave (0, 1, 3). This phenomenon can be seen from Figure 7b in Appendix G
A similar phenomenon can be observed for LP-Priority poli- cies. Here we consider an LP-Priority in H [BS20] GGY22 that breaks ties based on the Lagrangian-optimma index. In Figure we generate and visualize sample path under LP-Priority from time 250 to 289, and contrast with the sample path if the system switches to FTVA("") from time 250 onwards. We can see that under I.P-Priorit, al- though the arms have strong tendency to move up from state to state 5, they move back when they reach state 5 and thus get stuck at state 4. In contrast, when switching to (FTV(=**, the arrows gradually change to the correct di- rection, which helps the arms escape from state 4 and converge to the uniform distribution over the state space. Intuitively, under FTVA(#*), increasing number of arms couple their real states with virtual states over time, which allows these arms to consistently apply the preferred actions afterward. In Appendix G.4 we include more visualizations of the policies.
0.014
0.012
Avg Reward
0.010
Upper bound
0.008
Our policy: FTVA(T"))
0.006
Random tie-breaking
LP Priarity
0.004
0.002
0.000
200
400
600
800
1000
Figure 3:
Comparing policies based virtual states and real states
In Figure we compare the average reward of FTVA(#*) with those of the random tie-breaking policy and the LP-Priority policy discussed above. We can see that FTVA(#") is near-optimal, while the other two policies have nearly zero rewards. Further details are provided in Appendix G Note that while a different tie-breaking rule may solve this particular example with real states, currently there is no known rule that works general.
4 Theoretical result on optimality gap
In this section, we present main theoretical result, an upper bound on the conversion loss V V F=)V for any given single-armed policy æ. Setting म to be an optimal single-armed policy म² then leads to upper bound the optimality gap of our N-armed policy FTVA(#*), Our result holds under the Synchronization Assumption (SA), which we formally introduce below.
4.1 Synchronization Assumption
SA is imposed on given single-armed policy म. To describe SA, we first define a two-armed system called the
system, which consists of a leader arm and a follower arm. Fach arm associated with the MDP (S, A, P. r). At each time step t 2 1, the leader arm is in state S(t) and uses the policy मे to chooses an action A(t) based on S(1): the follower arm is in state S(t), and takes the action A(t) A(t) regardless of S(t). The state transitions of the two arms are coupled as follows. If (t)= S(t), then S(t + 1) S(t + 1). If ((1) o S(1), then S(t + 1) and S(t + 1) sampled independently from P(S()), A(1,.)) and P(3(1), A(t).), .), respectively. Note that once the states of the two arms become identical, they stay identical indefinitely.
Given the initial states and actions (S(0), A(0). SO0), A())) = (s, 3, 2) E A x x A, we define the synchronization time as the first time the two states become identical:
syne (s, a, 8, a) A min (1 2 0: S() $(1)
Assumption 1 (Synchromization Assumption (SA) for policy T). We say that a single-armed policy satisfies the Synchronization Assumption (SA) if for any initial states and actions (s, a, 8, a) E S x A x 8 x A, the synchronization time 5yne (s, a, 8, @) is stopping time and satisfies
[ syne (s, a, a)] co.
(10)
We view SA as an appealing alternative to UGAP for two reasons. First, there are some instances that satisfy SA but not UGAP. Two such examples are given in Figures and 3 (GG220) provides more
7

---

examples that violate UGAP, all of which can be verified to satisfy SA. Second. SA is easier to verify than UGAP. has been acknowledged in many prior papers that UGAP lacks intuitive sufficient conditions and can only be checked numerically. In contrast, SA can be efficiently verified in several ways, which is discussed Appendix C
4.2 Bounds on conversion loss and optimality gap
We are now ready to state our main theorem.
Theorem Consider an N N-armed RB problem (N, AN P.r. aN) under the single-armed unichain assumption. Let ā be any single-armed policy satisfying SA. For any N 2 1, the conversion loss of FTVA satisfies the upper bound
VT
V (T)
T 7'max
(11)
VN
where Tmax max (r(s, a) and T J..... E (T a, a..,33.0 3.
Consequently, given any optimal single-armed policy #* satisfying SA, for all any N the optimality gap of FTVA((") is upper bounded as
VN
FTVA(=*) VNN
SV
PTV)(##)
sync Tmax 7 max
(12)
N
VN
Proof sketch. The proof of Theorem is given in Appendix E Here sketch the main ideas of the proof, whose key step involves bounding the conversion loss V - VN v=FTva(*) using a fundamental tool from queueing theory, the Little's Law [Kl775]. Specifically, we start with the upper bound
V
(TVA(())
(51(20), Σ A(00(0)))A
max
Σ { (S)(o)), A((o0) # (S.(20), A(
(13)
N
((())) of each arm follows the single-armed policy т. We say arm is bad arm time if (S,(t), (t)) # A.((t)))(t))) and good arm otherwise. Then E
which holds since the virtual process
EN i{ (0))), A.())) # (o)) (co)) I. # bad arms] in steady state.
By Little's Law, we have the following relationship:
E (# bad arms] = (rate of generating bad arms) [ime duration bad arm]
suffices bound the terms on the right hand side. Note that the virtual actions A,(t)'s are i.idd with mean [t). = as a standard concentration inequality shows that at most Σ (t aN 2 O(VN) bad arms generated per time slot. On the other hand, each bad arm stays bad until its real state becomes identical to its virtual state, which occurs in (1) time by virtue of SA.
Continuous-time restless bandits
In this section, we consider the continuous-time setting. The setup, policy, and theoretical results for this setting parallel those for the discrete-time setting, except that longer require SA. Detailed proofs are provided in Appendix F
Problem setup. The continuous-tinn restless bandit (CTRB) problem similar to its discrete-ting time counterpart (cf. Section except that each single-armer armed MDP runs in continuous time. In particular, an -arrmed CTRB given by a tuple (N, &. AN G, r, aN), where $ is the finite state space and A = (0, } is the action space of single arm. In continuous time, each arms dynamics is governed by the transition rates (rather than probabilities) G (G(s, a, s.ss/ where G(s, a, s') is the rate of transitioning from state to state s' a upon taking action a. We again assume that the

---

transition kernel G of each arm is unichain. Given the states and actions of all arms, the transitions of different arms are independent from each other. Similarly, r(s, a) is the instantaneous rate of accumulating reward while taking action in state 8. The budget constraint now requires that at any moment of time, the total number of arms taking the active action is equal to a.N.
The objective is again maximizing the long-run average reward, that is,
maximize policy x
A
lim T-000
N Σ
(14)
T
subject to
Σ (t) = aN
Vt 2 0.
(15)
Let V = supx V2 denote the optimal value of the above optimization problem.
Single-armed problem. The aingle-armed problem for CTRB is defined analogously as its discrete- time counterpart (3) This single-armed problem can again be written as a linear program, where the decision variable y8, a) represents the steady-state probability of being in state taking action
maximize (CB.cA
Σ r(s,a)y(ss,) sES,aEA
(LP-CT)
subject to
Σ ys, 1)= =a SES
(16)
Σ of EEEEE
a(d',)) V
(17)
a(s 1; u(s,a) 20 Vs S &ES,
Σ
(18)
In we use the convention that G(x,, a, -(s a G(s, a, 8'). Again, the optimal
value of (LP-CT) upper bounds the optimal value for the N-armed problem, i.e., Vi =V' V
where म is any optimal single-armed policy and can be computed using the same formula in (8).
Note that in continuous time, the optimal policy n" is carried out through uniformization (Pur05..
Our policy. Our framework for the CTRB, presented in Algorithm 2 FTVA-CT works similar fashion as its discrete-time counterpart. takes single-armedt policy स as input, and each arm i independently simulates virtual single-armed process (S,(t) (t)))) following म. FTVA-CT then chooses the real actions (t)'ss to match the virtual actions (1)ss to the extent allowed by the budget constraint ΣN A,(1) a..
Aevice--CC CT (FTVA-CT), is
To run FTVA-CT in continuous time for the Naammed problem, we use the following uniformization to set discrete decision epochs [t= for updating the actions and virtual processes. We 2.Nomax uniformize at rate 2NN fmax with Jmax = max G(s.a), which is an upper bound on the
total transition rate of the real and virtual states in an N-armed system. We generate decision epoch either when a real state transitions, or when an independent exponential timer with rate 2.N 9max Em G(S,(t), (t))) ticks.
The definitions of conversion loss, optimality gap, and asymptotic optimality are the same as the discrete-time setting.
Conversion loss and optimality gap. For given single-armed policy म. we consider a continuous- time version of the fndlllwed system (cf. Section (.1). For technical reasons, the initial actions are specified differently from the discrete-tine time setting. Specifically, we assume that the initial action A(0) of the leader arm is chosen by स based on S()), and the follower's 's initial action A(0) equals A(O). As before, the follower arm always takes the same action as the leader arm regardless of its state. Given initial states (5(0), S()) (s, the synchronization time is defined as
y (s. 3) A inf 2 0: S(t) Š(t))
(19)
We no longer need to impose the Synchronization Assumption, since the unichain assumption automatically implics E (ys (s, 3)] < in continuous time-sed see Lemma 5 in Appendix F

---

Algorithm 2 Folllow-hhe-Viiruul---ddr-----e (FTVA-CT)
Input: (N,8%, AN, G,r, a.N), initial states S(0), single-armed policy म, max transition rate Jmax
Initialize: Virtual states (0) are N ii.d. samples following the stationary distribution of म; to = 0
1: for k= 1,,,,. do
2: Independently sample (t+) (tx)) for each arm i [N] & Generate virtual actions
3: if E (ttt)) 2 aN then
& Select a set of oN arms to activate
4:
A + a set of a.V arms chosen from {i: (txt)) = 1 (any tie-breaking)
5: else
6:
B s set of oN - E (tt) arms chosen from {ú: (txt)) 0} (any tie-breaking)
7:
A {i: A.(tx) = 1 UB
8:
Apply Ax(tx)
for each arm E A, and apply (,tt)) = for each arm & A The section below progresses the system to the next decision epoch and updates states
9:
9k real E N (ta), A((t))
11:
t.+1 < 1x- sample from the distribution (2p Imax - 9
real
12:
if there is an arm 8 whose real state transitions before [++1 then
13:
(14+1, St- (1-(()+))) x- (transition time, real state) if S (1x) = S1-(1x) (1x) and A (tx) = A:- (4x) then S (tx+1) + Si- (tx+1)
14:
Couple virtual and real states
15:
16:
else
No transitions transitions of virtual states of uncoupled arms
17:
t++1 f- Ext1
18:
virtual
En (13) ((())) (S.(1A) # S.(te) or A,(te) * Ac(tz))
91 vemee
19:
With probability
continue
2N Denux og
Sample a pair (i", E [N] x with probability (();- (tx), 0')-133-- (1x)
20:
2N 2Namax 5
21:
if S (tx) # Sj- (tx) or Å, (t&) * (ta(t)) then Sy- (tx+1) t
22:
Other real and virtual states stay unchanged
Theorem Consider an N -armed CTRB (N, NN AN G.r,aN) aN) under the single-armes unichain assumption. For any singlearmen policy T, the conversion loss of FTVA-CT is upper bounded as
V
V FTV)
Tmax 1 + 20max T
=yyne max
V
(20)
VN
where Tmax max [r(s, a)}. syyc max
E
[ STC (s.
Consequently, for any optimal single-armed armed policy H", the optimality gap FTVA-CTT( satisfies
(TVA-CT(**) -V* VPTVA-C((*")
Tiax (1 29max
Tlyne
AA 2
(21)
VN
Theorem 2 establishes an O(I/VN) optimality gap without requiring UGAP or any additional assumptions beyond the standard unichain condition.
6 Conclusion
In this paper, we study the average-reward restless bandit problem. We propose a simulation-bart based framework called Follow-the- the-Virtual-AAve that converts a single-armed optimal policy into a policy the original N-arm system with an O //N) optimality gap. the discrete-time setting, our results hold under the Synchronization Assumption (SA), a mild and easy-to-verify assumption that covers some problem instances that do not satisfy UGAP. In the continuous-time setting, our results do not require any additional assumptions beyond the standard unichain condition. In both settings, our work is the first to achieve asymptotic optimality without assuming UGAP. It will be interesting in future work to explore the possibility of achieving optimality gaps smaller than O(1/VN) without relying UGAP the non-degenerate condition.
10

---

Acknowledgement. Y. Hong and W. Wang are supported in part by NSF grants CNS-200773 and ECCS-2145713. Q. Xie is supported in part by NSF grant CNS-1955997 and J.P. Morgan Faculty Research Award. Y. Chen is supported in part by NSF grants CCF-1704828 and CCF-2233152 This project started when Q. Xie, Y. Chen, and W. Wang were attending the Data-Driven Decision Processes program of the Simons Institute for the Theory of Computing.
References
[AAD]13] Konstantin Avrachenkov, Urtzi Ayesta, Josu Doncel, and Peter Jacko. Congestion control of tep flows in internet routers by means of index policy. Computer Networks, 57(17):3463-3477 2013.
[AB19] Konstantin Avrachenkov and Vivek Borkar. A learning algorithm for the whittle index policy for scheduling web crawlers. In Proc. Ann. Allerton Conf. Communication, Control and Computing, pages 1001-1006, Monticello, IL, 2019.
[ABG09] T. W. Archibald, D. Black, and K. D. Glazebrook. Indexability and index heuristics for simple class of inventory routing problems. Oper. Res., 57(2):314-326, 2009.
[ALT19] Samuli Aalto, Pasi Lassila, and lanire Taboada. Whittle index approach to opportunistic scheduling with partial channel information. Perform. Eval., 136:102052 2019.
[BS20] David Brown and James E. Smith. Index policies and performance bounds for dynamic selection problems. Management Science, 66(7):3029-3550, 2020.
[GGWI1] John C. Gittins, K. D. Glazebrook, and Richard Weber. Multi-armed bandit allocation indices. John Wiley Sons, 2011.
[GGY20] Nicolas Gast, Bruno Gaujal, and Chen Yan. Exponential convergence rate for the asymptotic optimality of whittle index policy. arXiv:2012.09064 [cs.PF], 2020.
[GGY22] Nicolas Gast, Bruno Gaujal, and Chen Yan. LP-based policies for restless bandits: Necessary and sufficient conditions for (exponentially fast) asymptotic optimality. arXiv:2106.1006 Saath.OC), 2022.
[Git79] John C. Gittins. Bandit processes and dynamic allocation indices. Journal of the Royal Statistical Society: Series B (Methodological), 41(2))148-16)) 1979.
[GJ74] John C. Gittins and D. M. Jones. A dynamic allocation index for the sequential design of experiments. Gani, editor, Progress Statistics, pages 241-266. North-Hollann Amsterdam, 1974.
[GMA05] K. D. Glazebrook, H. M. Mitchell, and P. S. Ansell. Index policies for the maintenance of collection of machines by a set of repairmen. European Journal of Operational Research, 165(1):267-288)) 2005.
[GNJT23] Abheek Ghosh, Dheeraj Nagaraj. Manish Jain, and Milind Tambe. Indexability is not enough for whittle: Improved, near-optimal algorithms for restless bandits. In Proc. Int. Conf. Autonomous Agents and Multiagent Syst., page 1294-1302, Richland, SC, 2023.
[HF17] Weici Hu and Peter Frazier, An asymptotically optimal index policy for finite-horizon restless bandits. arXiv: 177.001777000000 [math. OC), 2017.
[HXW23] Yige Hong, Qiaomin Xie, and Weina Wang. Near-optimal stochastic bin-packing in large service systems with time-varying item sizes. Proc. ACM Meas. Anal. Comput. Syst., 7(3), 2023.
[Kle75] Leonard Kleinrock. Queueing Systems. John Wiley & Son, 1975.
[LS20] Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
[PT99] Christos H. Papadimitriou and John N. Tsitsiklis. The complexity of optimal queuing network control. Math. Oper. Res., 24(2):293-355, 1999.

---

[Put05] Martin L Puterman. Markov decision processes: Discrete stochastic dynamic program- ming. John Wiley & Sons, 2005.
[VBW15] Soffa S. Villar, Jack Bowden, and James Wason. Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challenges. Statistical Science, 30(2):199 -215, 2015.
[Ver16] M. Verloop. Asymptotically optimal priority policies for indexable and nonindexable restless bandits. Ann. Appl. Probab., 26(4):1947-1995 2016.
[Whi88] Peter Whittle, Restless bandits: activity allocation changing world. Appl. Probab., 25:287 298, 1988.
[WW90]] Richard R. Weber and Gideon Weiss. On an index policy for restless bandits. J. Appl. Probab., 2773)6637-644, 1990.
[ZCJW19] Gabriel Zayas- Cabán, Stefanus Jasin, and Guihua Wang. An asymptotically optimal heuristic for general nonstationary finite-horizon restless multi-armed multi-action ban- dits. Advances in Applied Probability, 51:745-772, 772, 2019.
[ZF21] Xiangyu Zhang and Peter Frazier. Restless bandits with many arms: Beating the central limit theorem. arXiv:2107.11911 [math. OCJ, 2021.
[ZF22] Xiangyu Zhang and Peter I. Frazier. Near-optimality for infinite-horizon restless bandits with many arms. arXiv:2203. 15853 [cs.LG], 2022.
12

---

Appendices
A More related work
In this section, we provide additional discussion on related work.
Relationship between the infinite-horizon average-reward setting and the finite-horizon to- tal-rewar/infniie-horiii discounted-rewarc setting. While infinite-horizon average-reward RBs, unite-horizon total-reward RBs, and infinite-horizon discounted-reward RBs are three different settings, one may think that the approaches in the other two settings apply to the infinite-horizon average-reward setting by taking a large enough horizon in the finite-horizon setting or letting the discount factor to go to 1 in the infinite-horizon discounted-reward setting. Here we briefly discuss the fundamental difference between the infinite-horizon average-reward setting and the other two settings for RB problems. For simplicity, we will refer to the other two settings as the hwte--oorroooddissutteeeeeeewe
setting. From the algorithm design perspective, the mniic--brizoondiicouutteeerr reward setting focuses on optimizing the transient performance, while the anfinite-horizon average reward setting focuses on optimizing the steady-state performance. This distinction has a big impact on the algorithm design and the complexity. To see this, we note that both the hitee-hotzoooddisouuteeeeeeeee
setting [HF17, 19JW19, BS20, GNJT23 2F21 ZF22 GGY22 and the mafinite-horizon average- reward setting [Wii88] WW90 Verl6 GGY20 GGY22 utilize certain forms of linear programming (LP) relaxations to design algorithms. However, the LPs utilized differ substantially. In the finite- horizon/discounted-rewww
setting, the LP optimizes the future trajectory for a predetermined number of time steps. In contrast, in the state-action frequency in steady state, which can be seen as a fixed point rather than a trajectory. As result, the number of variables and constraints of the LP for the setting scales with the number of time steps, which is not the case for the fiinite-horizon average- reward setting. On the other hand, because the LP relaxation for the anfinitehhorzzn average-reward setting does not take into account the transient behavior, it provides less information, making the algorithm design more tricky. Consequently, the policies in prior work require the strong assumption of UGAP to achieve asymptotic optimality.
average- reward setting. the LP solves for the optimal
wwwizoo/discounnedd reward
From the analysis perspective, the infinite-horizon average-reward setting requires a more careful analysis of the long-term effect of actions. To see this, note that the optimality gap bounds in the htrehhorrzzoomdisoueeee---ee
setting have at Icast quadratic dependency on the (effective) horizon [see, c.g. ZF22 GGY22 Consequently, when translated to the bounds on the optimality gap of average reward per time slot, those bounds diverge infinity as the time horizon goes infinity.
Relationship between the RB problem and other bandit problems. While the exact optimality of the RB problem is in general intractable, there is a special case that has been solved optimally. Specifically, consider the case when an arm stays in the same state when it is not pulled, and only one arm is pulled at a time. The optimal policy for this special case is the celebrated Gittins index policy GJ77 Git79.. A more recent reference on this topic is [GWII].
The RB problem falls within the broader class of bandit problems, for which different formulations exist including stochastic bandits, adversarial bandits, and Bayesian bandits. The common theme in these formulations is to find reward- maximiiinn strategy of pulling arms in the presence of uncertainty in the arms' rewards; see the book [LS20] for a comprehensive overview. Among these formulations, closely related RBs is the Bayesian bandit problem, where Bayesian posteriors are used to model knowledge of unknown reward distributions. The Bayesian posterior can be seen as state with known transition probabilities. hence the Bayesian bandit problem can be analyzed by applying tools from RBs. Examples demonstrating this connection can be found in [B220].
B Discussion on the computational costs of FTVA
FTVA defined in Algorithm I can be computed and implemented efficiently.
First, computing FTVA requires solving (T.)) once. Given that (P)) does not depend on N, the computational cost here is constant.
13

---

Next, we examine the computational cost of implementing FTVA.
Each arm simulates virtual process. Because the computation required for each simulation does not scale with N, the overall computational cost here is linear in N.
In each time step, FTVA selects arms from a subset of arms to determine the real actions. The computational cost for this selection process scales linearly with N.
Combining these components, we can see that the computational cost of implementing FTVA is linear in N.
Additionally, we note that the simulation of the virtual processes independent across the arms, so they can be implemented in a fully distributed manner. However, when taking real actions, the policy needs to know the virtual actions from all arms, so this step cannot be implemented distributedly.
C Sufficient conditions for Synchronization Assumption (SA)
Recall that for the discrete-time setting, our bound on the conversion loss in Theorem Tholds when the input single-armed policy मे satisfies the Synchronization Assumption (SA). SA stipulates that the two arms in the sader-and-followee
system (cf. Section 4.1) under the policy म will reach the same state in finite expected time. All other existing work requires the UGAP assumption, which pertains to the global behavior of a non-linear dynamic system and has no known sufficient conditions that are easily checkable. In comparison, SA is a reachability assumption imposed on a finite stute Markov chain and thus substantially simpler.
To provide a more intuitive understanding SA, in this section we present several sufficient conditions for SA to hold. These conditions involve the recurrent classes in the Markov chains induced by certain single-armed policies as well as the existence of self-loops or cycles the corresponding transition diagrams. Such conditions can be verified, often in a straightforward manner, by inspecting the transition probabilities. As self-loops and cycles are common in many classes of MDPs, these conditions showcase that SA is relatively mild assumption. We emphasize that the sufficient conditions presented in this section are exhaustive. They serve as illustrative examples of when SA holds and offer insights on the nature of synchronization.
The discussion in this section pertains the discrete-time setting. We reiterate that our results for the continuous-time setting do not require SA.
C.1 Preliminaries
Before presenting the sufficient conditions, we first prove a few preliminary facts. The first one is basic property of unichain MDPs.
Proposition 1. Consider two arbitrary Markovian policies ß and n' for the unichain MDP (S, A, P.r). Let the recurrent classes of the two policies ß. and म' be S and S', respectively, Then Sns' # 0.
Proof. We prove this proposition by contradiction. Suppose S S' = 0. We define new policy #" as
([als), if
n" (als))
for 8 E S, A. (a(ass), otherwise.
Then S and S' are two distinct recurrent classes under H", because by definition of æ", an arm with the initial state in S remains in S, so it cannot reach S": similarly The existence of two recurrent classes under x" contradicts the unichain condition. Therefore, we must have S S' + V.
cannot reach S from S'.
The next proposition provides a convenient way for verifying SA and is used for establishing other sufficient conditions.
Proposition 2. Consider the seuuer--nddfoolloer system under the policy n. If there exists some ( < such that for all initial states and actions (s, a, 8, E x A x 8 x h. (y (s, a, 3, ā) < t) > 0,
then Synchronization Assumption holds for the policy π.
14

---

Proof. We claim that for any (s, a. 8, E A
P a,
kt)
max 3..0
P ( (s
2 21)
(22)
where the maxs',e', is taken over 3 x x We prove this claim by induciton on k. The base case of k = is given. Suppose have proved 22 for certain then
P ( (s, a, 3,
(ke + 1)t)
P (T 8.
IV IV kt) syn as, a, 2 (k: + 1)t
J sye (s. a, (, 2 kt)
P (+ 8,
kt) syyc (S(kt) A(kt), S(k)) A(t)) 2 211 + S(kt)
S IP (+ (s, a.
IV
kt) max P (s', 2.',''00 ",)) 2t)
<( max s' 3', a
IP (T
a')
b+1
where in the second equality have used the Markov property of the system, and in the last inequality we apply the induction hypothesis. We have proved (22).
The bound on the expectation E [7 (s, 8, a)] follows by summing the tail bound 22 over k:
E a, a) <
UP (T (8, 3,0, 2 kt)
k=0
max 3 (TSyne (8', 3'',,,,0 2()
t
< 80.
m P (T a a <
We have established SA and thereby finished the proof.
Remark 1. Proposition 2 implies that SA only requires that the Markov chain of the leader-and- follower system, (S(t), (()), can reach the subset of states {(s,3) S2: 3) from any initial state. As a result, SA can be efficiently verified using path-finding graph algorithms on the state transition diagram of the Markov chain.
C.2 Sufficient conditions based on self-loops
The unichain condition and Proposition D guaranteee that there are some states that the leader arm and the follower arm will both visit for positive fraction of times [ If we can further show that the two arms have a positive probability to visit one of those states at the same time, then Proposition 2 can be applied verify SA. natural sufficient condition is the existence of self-loops, which guarantees that with a positive probability, the arm reaching those states first will wait for the other arm to come the same state.
Proposition 3. Consider the armed problem with the unichain MDP E (0, 1). Let गे be a single-armed policy with recurrent class S. If Ps,,0, > a 1,),188)> for all S, then Synchronization Assumption holds for the policy n.
and budget
assumee that all states in the recurrent class of the policy मे have self-loops. We can actually require fewer self-loops if we can characterize the recurrent states of the follower arm. In particular, let ग. denote the all-one policy, the policy that applies action 1 in all states. Observe that the leader arm applies action for sufficiently long time, the follower arm will also apply action 1 and effectively follows 71. The recurrent class of the policy मn must intersect the recurrent class of म, so it suffices to have self-loops in the intersection of these two recurrent classes. The idea is formalized in Proposition 4
Proposition 3
2 FAlhhough the follower arm does not follow Markovian policy since copies actions from the leader arm, by standard results on average reward MDP, the set of states which the follower arm spends positive fraction of time is the same the recurrent class of some Markovian policy (cf. Chapter 8.9 of (Put05]). This class of states must intersect with S Proposition] and the unichain condition.
15

---

leader
leader
<......
2
follower
follower
1
S
S1
S
S
Figure 4: The illustration of the positive probability sample paths that lead to synchronization in In each figure, the dotted arrows correspond to the
Proposition f (left) and Proposition sample path of the leader arm's 's state, while the solid arrows correspond to the sample path of the follower arm's state. The numbers near the arrows denote the temporal order of the transition events.
Proposition 4. Consider the single-armed problem with the unichain MDP (8, A, P,r) and budget a E (0, 1). Let be a single-armed policy with recurrent class S. Let the recurrent class of the all-one policy R1 be denoted Sy. If the following conditions hold:
1. There exists s E S such that क (1|ss)) ) > and P(s", 57) > 0;
2. There exists s E S S1 such that P(s.,0. s²) > 0 and P(s", 1..11,1.. 1. 0.
then Synchronization Assumption holds for the policy म.
Proposition 5 below gives another sufficient condition, which only requires one self-loop. Note that this condition does not subsume the one in Proposition 4
Proposition 5. Consider the single-armed armed problem with the unichain MDP (S, A, P,r) and budget a E 1). Let ā be single-armed policy with recurrent class Let the recurrent class of the all-one policy be denoted S₁. If there exists s* S n S1 such that #(1ss") > 0 and P(s", 11s*) > O, then Synchronization Assumption holds for the policy म.
We remark that Propositions and have analogous versions that are stated in terms of the all-zero policy ao. the policy that applies action 0 in all states. We omit the details.
Now we prove the above propositions. Note that Proposition is strictly weaker than Proposition 4 because the singlearrme policy मे satisfies the budget constraint with a E (0, 1). there must be state s" E S such that म (1(s") 0. Therefore, only need to prove Propositions and and
Proof of Proposition Given any initial states and actions (S(0), A(0), S(0),, A())) (s, a, 3,,3000 3, x x A. we construct a sequence positive probability events that leads to S(t) = S(t):
1. The leader arm reaches the state s" E S after t time slots;
2. The leader arm stays in state 8 and keeps applying action 1 for le times slots; meanwhile, the follower arm also applies action and reaches the state 8² Sns
3. The leader arm reaches the state 8 in another ts time slots; meanwhile, the follower arm stays in the state s², so the two arms synchronize.
The transitions of the two arms during the above sequence of events are illustrated in Figure We argue that there exists suitably large (, 12, la such that the above three events happen with a positive probability. The first event can happen for suitably large ( because the leader arm follows the policy म. and 8 is in the recurrent class of म. the second event, the leader arm can stay state g and keep applying action because 7 (1|s²) )) > 0 and P(s s*) > 0. The follower arm can reach s² after a suitably large tz time slots because it keeps applying action 1 and s is in the recurrent class of the all-one policy #1. In the third event, the leader arm can reach s² after a suitably large ty time slots because s² is also in the recurrent class of न.. Meanwhile, the follower arm can stay in s because P(s", 0, 0, ")= > and P(s", 1, > 0. Therefore, we have proved that for any (8, a, 8, a),
P ( (s, s. < t1 t2 + ta) 0.
16

---

By Proposition 2 we establish SA.
Proof of Proposition
Given any initial states and actions (S(0), A(0), 3 A(0)) = (s. 8,0) A, we construct a sequence positive probability events that leads to S(1) S(1):
S
1. The leader arm reaches the state 8 after / time slots;
2. The leader arm stays in the state s" and keeps applying action 1 for t2 time slots; meanwhile, the follower arm also applies action 1 and reaches the state s*, the two arms synchronize.
The transitions of the two arms during the above sequence of events are illustrated in Figure We argue that there exists suitable and f2 such that the above two events happen with positive probability. The first event can happen for a suitably large 4 because 8* is in the recurrent class of и. In the second event, the leader arm stay in the state s* and keeps applying action because T (1]ss)) >> and P(s", 1,8*) > O. Meanwhile, the follower arm can reach s* after a suitably large t2 time slots because s* is also in the recurrent class of the all-one policy T1. Therefore, have proved that for any (s, a, 3, a),
(y (8, 0, S + (2) >
By Proposition 2 we establish SA.
C.3 Sufficient conditions based on cycles
The above sufficient conditions are based on self-loops, which can be viewed as cycles of minimal length. These conditions can be generalized to longer cycles, formally defined below.
Definition (Cycle). Consider the MDP A.r.P,r) We call ordered set of states C cycle under the Markovian policy म if there is a positive probability of transi- tioning from 8y to 8y+1 for j under the policy क (we identify SL+1 with sy). We call the ordered set C' a cycle under any policy if there is a positive probability of transitioning from s, to 8j-1 for all j under any policy. In both cases, we call the length of the cycle C.
(so, , St)
We give two sufficient conditions based on eycles. These conditions relaxations of the conditions in Proposition 4 5
Proposition 6. Consider the single-armed problem with the unichain MDP (8, A. P,r) and budget E (0, 1). Let be single-armed policy with recurrent class S. Let the recurrent class of the all-one policy in be denoted as St. the following conditions hold:
1. There exists a cycle C under the policy S, and #(1ss) 0frr all C%;
2. There exists cycle Oh under any policy in S S1;
3. The lengths of the two cycles C and Ch are relatively prime.
then Synchronization Assumplion holds for the policy T.
Proposition 7. Consider the single-arme problem with the unichain MDP (S, A. P,r) and budget E (0, 1). Let be single-arme armed policy with recurrent class S. Let the recurrent class of the all-one policy #i be denoted as St. If the following conditions hold:
1. There exists a cycle C under the policy ß in Sr. and #({ss) > for all E C";
2. The policy गi is aperiodic.
then Synchronization Assumption holds for the policy n.
Similarly Propositions and 5. Propositions 6nd have analogous version that stated in terms of the all-zero policy To- We omit the details.
Now prove Propositions 6 and
17

---

leader
leader
<-.....
<-.....
C
2
follower
follower
C
2
3
S
S
S
S
Figure 5: The illustration of the positive probability sample paths that lead to synchronization in Proposition [ (left) and Proposition (right). In each figure, the dotted arrows correspond to the sample path of the leader arm's 's state, while the solid arrows correspond to the sample path of the follower arm's state. The numbers near the arrows denote the temporal order of the transition events.
Proof of Proposition 0 Given any initial states and actions (5(0), A(0). S()), A(O)) = a, S x A. x 8 x A. we construct a sequence of positive probability events that leads to 5(L) = S(1):
1. The leader arm reaches the cycle C after 1 time slots;
2. The leader arm transitions along the cycle and keeps applying action 1; meanwhile, the follower arm also applies action 1 and reaches the cycle Ch; this happens &2 times slots; let the states of the leader and follower arm at this moment be 8 and sh;
3. The leader arm transitions along the cycle C for another laps, for some positive integer c, and then spends another ty time slots to go from s" to sh; meanwhile, the follower arm transitions along the cycle C for another d laps, for some positive integer d.
The transition the arms during the sequence of events are as illustrated in Figure 5 We argue that there exists some suitable &1, i2, ta, c, and d such that the above four events happen with positive probability, and the arms synchronize after the four events.
The first event happens with a positive probability for suitably large t1 because C is in S. The second event can happen for suitably large ty because (11ss) > 0 for all C", and Ch is in St.
After the first two events, suppose the state of the leader arm is 8", and the state of the follower arm is sh, then s E C and 8 E Ch. Because both cycles are in S, there exists positive probability path from 8 to d under Let 13 be the length of the path. Let I,a and T.P the length of cycles C and Ch. Because I and I. are relatively prime, we can take and d such that dI, cI i3. With this choice c, d, and f3, the two arms will synchronize after the third and fourth events.
Now we argue that the third and fourth events happen with a positive probability. Because C is cycle under the policy म, the leader arm can transition along the cycle for an arbitrary number of time slots. Similarly, because Ch is a cycle under any policy, the follower arm can transition along the cycle for an arbitrary number of time slots; the leader arm can reach s from s" because of the positive probability path described in the last paragraph.
Therefore, have proved that for any (s,a, 8,
( (s, a, अ, 54 + cL + +12) 0.
By Proposition we establish SA.
Proof of Proposition Given any initial states and actions (S(0), A(O). 3(0), A(0)) = (8, a, 8,0) S x A x S x A, we construct a sequence of positive probability events that leads to S(t) S(t):
1. The leader arm reaches the cycle C* after i time slots;
2. The leader arm transitions along the cycle and keeps applying action 1; meanwhile, the follower arm also applies action and reaches the same state the leader arm after la time slots.
18

---

The transition of the arms during the sequence of events are as illustrated in Figure 5 We argue that the above two events happen with a positive probability for suitable t and tz. The first event can happen for suitably large ( because the leader arm follows the policy स the cycle C* is in the recurrent class of π.. After reaching C the leader arm can remain on C because C* is cycle under the policy म., and it (1][s) > 0 for all E C The follower arm can reach the same state as the leader arm because the cycle C is also in the recurrent class of Tt, and मn is aperiodic. Therefore, we have proved that for any (s, a, 5, a),
P P (8, 8, S t1 + 12) >0. 0.
By Proposition we establish SA.
D On relaxing the unichain condition
Throughout this paper, we have imposed the (all-policy) unichain condition, i.c., all Markovian single-armed policies have a single recurrent class. Making this blanket assumption simplifies our presentation, but can be substantially relaxed for many our results, as we discuss below.
The main change caused by dropping the unichain assumption is the definition of the single-armed problem, because there could be multiple recurrent classes under single-armed policy, each cor- responding to different long-run average reward. To adapt to this change, we can let both the single-armed policy गे and the initial state distribution y be optimization variables of the single-armed problem. We denote the average reward given and μ as V.T.P, We still denote the optimal value of the single-armed problem Viel. Note that the single-armed problem still be solved by the same linear program in (LP) or (LP-CT): The optimal initial state distribution μ² can be taken as the optimal stationary state distribution (y (s, y ys(s, 0)) given the optimal solution of LP, y²
The definitions of FTVA and FTVA-CT do not require any change, considering that they are already using the stationary distribution of म to initialize the virtual states. The conversion losses, now denoted as VIS. VV FTV and v V (TTT)-CT(T..)) have the same bound as what we currently have in [ for discrete-time RBs and equation (20) in Theorem f continuous-time RBs. These bounds hold as long as the given input policy म has finite expected synchronization times, which can be seen by inspecting the proofs of the theorems given in Appendix E and Appendix F
equation (T] in Theorem
The optimality gap bounds in (12) in Theorem ! and 21 in Theorem 2 still follow from the conversion loss bounds when the unichain assumption is dropped. To see this, for each of the discrete- -aerete-timeeaaee and continuous timii settings, consider an optimal single-armed policy म and optimal initial state distribution μ=" Note that V .," = =Viel 2 V If If -1"" FTVA(* ,²) () then V/ FTVA((" ,(") O(1/VN); if V V --PTVA-CT(F ,x O(1/VN).
FTVA-CT(""
O(I/VN), then Vğ-
In the discrete-time setting, our sufficient conditions for finite expected synchronization times, presented in Propositions 4 S
and 7 are valid as long as each of the two policies ग and म, has a single recurrent class and two classes intersect. Similarly, Lemma 5 Appendix F which establishes finite expected synchronization times for the continuous-tin time setting, holds under the same condition on म and 1
E Proofs for discrete-time RBs
E.1
Overview
In this section, we focus on proving the bound 11 on the conversion loss V/8 (F)) for any single-armed policy म The asymptotic optimality result (12) Theorem will be a direct consequence of (II) if we take स to be any optimal single-armed policy #"
N
We first show that under FTVA(#) defined in Algorithm I
each virtual process is an independent Markov chain induced by applying ã to the single-armed system (S, A, P, r), stated in Lemma below. We will rigorously prove in the next subsection.
19

---

Lemma 1. Under FTVA(T) given in Algorithm 1 for each 0,1,2.... i [N 3 E S and
AEA.
IP (Ā(() (A())={((()...) S())) -()))
II क (a.))S((1) iE|N]
(23)
P
II (())))).A(())))) [EIN]
(24)
Let (u(s, u) aEE be the steady-state state-action distribution of the single-armed system under т.
By 23 for each 2 0, (,(()))((t))))))) for E [N] are i.i.d with the distribution (y(s, a) SES.EAE
Next, sketched in Section
4.2
we bound
Vi* V
FTVA(())
N
N
VN
(TVA(())
E
r (S)(20), Ac(oo))
Σ ((S((00).
N
2rmax
N
1 (Si(00), A((o)) + (8,(20), (, 1
E
13
N
i==
We say an arm i bad arm at time t (S, (() + (S,(t), A())), and a good arm otherwise.
E> 1{ (3)), + (. E # bad arms] in steady state.
Then E
By Little's Law, we have the following relationship:
E [# bad arms] (rate of generating bad arms) time duration of bad arm]
To make the quantities in the above expression precise, we make the following definitions.
We say there is a disagreement event of the arm i happening at time L if Ā.(!) * A,(() The disagreement events are the only cause that turms good arms into bad arms because otherwise by the construction of our algorithm, (,) will remain the same as (t).). The number of disagreement events in each time slot is determined by how much the budget required by virtual actions violates the constraint. We call the expected number of disagreement events when the virtual states are & the instantaneous disagreement rale, denoted d()).
We also define disagreement period of the arm i as continuous period of time when arm i a bad arm, separated by disagreement events. Formally,
Definition 2 (Disagreement period). Given sample path of the arm i's real states and virtual states (t), (t)) define the disagreement period of the arm i as time interval [eeginn fend 1] such that
Al(loin))) * Ab(bngin:: A,(t) A.(t) and S.(t) + St(t) Vt E [Uneiin + 1, tend 1];
Ac(lena) + A, (lena) or Se(nnn)) = Si(lend).
We use Davg to denote the long-run average length of the disagreement periods, i.c., the average of fend - Abegin of all disagreement periods.
With the definitions, we can state Little's Law in the context of disagreement periods. We omit its proof since is a direct consequence of Little's Law.
Lemma (Little's Law for disagreement periods).
E Σ
((((())) # (S.(0)). =E [d($(20)) Davgs (25)
where d(x) denotes the instantaneous disagreement rate when the virtual states are S(1) 8; D Dayg denotes the long-run average length of the disagreement periods.
20

---

E.2 Lemmas and the proof of Theorem 1
In this section, we will prove Theorem 1 We first rigorously prove Lemma]
Proof of [ The first equation 23 is obvious because each virtual action (t) sampled
from * (()):(()) independent of anything else. We only need to show (24). Recall that by the definition of FTVA(T), (t + 1) could either be equal to S,(t + 1) if (S,(t), (,)))) = (S,(t),,,(t))
generated afresh independent of anything else if (S,(1), A.(1)) # (S,(1, (1)). Let Igoood (t) {i: (,) = (S.(t), Then
IP (Š(1 + 1) $(), A ((0)),,(((())))))))) A(0) P (( (.))
S(0),
II (EI
II 1 (t)
II P(()))) (1)
II ((0).)
(ETzuu(()
= II KE[N]
(()) 8)).
where the last equality is by the definition of [g)od(t).
Combining (23) and (4). we have confirmed that each virtual process an independent single- armed process with transition kernel and policy s. Because the initial virtual states (0)))) sampled i.i.d from the stationary distribution of न. (EE()) also i.idd. with the same distribution. Therefore, (t), A((t)) are i.i.d. with distribution (y(s, aE)
LI
The next two lemmas bound the two quantities in Lemma 2 the long-run average disagreement rate and the long-run average length of the disagreement periods.
Lemma (Average disagreement rates). The instantaneous disagreement rate equal
N
8
E
Σ
-
7.0
|((() 8
(26)
The long-run nun-run average disagreement rate is bounded as
E dd( (((S()))) S VN.
(27)
Proof. We first prove the expression of instantancous disagreement rate in (26). By definition, the instantaneous disagreement rate equal to the expected number of arms such that A;()) + Ā,()) conditioning on the virtual states being 8. Because FTVA tries to match as many A,(t)'s to (,)')ss as possible, there are exactly E Ac(() - aN\ arms such that A,(() # A,))). This proves 26
To bound the average disagreement rate, letting & = $(00) in 26 and taking expectation, we have
N Ax(x)) aN
E [(((S(<0))]
=
==1
(x0) aN)2 :) 1/2
<
I
(28)
By Lemma 1 the virtual actions (oo))s 's are i.i.d. binomial random variables such that IP (o0)
1) = E.er g(, 1) = a, Σn (,c) has distribution Binomial a.), whose mean and variance
1/2
are a. and Na(1-a) < N/4. Therefore the expression in (28) is equal to Var EN A,(c0)
vN 1/2
21

---

Lemma 4 (Average length of disagreement periods).
Dave <
(29)
max
Proof. To bound Davg. it suffices to bound the expected length of a disagreement period with arbitrary initial states. Without loss of generality, consider a disagreement period on arm i that starts time leggin 0, with initial states (S) S,) A, (0) = (s, a, s, S, During the disagreement period, the i-th arm can be seen a geader-and-follower system, where the real state-action pair (S) (:))) corresponds to the follower arm and the virtual state-action pair (t), (.) corresponds to the leader arm. By Assumption I the leader arm and the follower arm will synchronize in finite expected time. When they synchronize, the disagreement period stops, which means lend S 7 (s, 0, 8, a). Therefore, the expected length of the disagreement period satisfies
B [end
/bogin| = E (kend) I TE (T (8, (1, 8, 8,0)) S Tlyne
This holds for arbitrary initial states (s, a, 8, @) Davg S
7lyac max-
Given the three lemmas above, we can prove Theorem
Proof of Theorem
7
Combining Lemma 2 4 and 3
we have
E
Σ 1
(8:(00), * (S.())),
1 syne VN.
2
Plugging the above inequality into the bound conversion loss in
13 we get
N
N
VF=
N
(F)
E
Σ
Σ r(S((x)), (,
N
2r maxx
E
Σ i{ ( * (Si(00), A,(00))
N
syne r maxx 7 max
This finishes the proof.
F
Proofs for continuous-time RBs
F1 Preliminary: finite synchronization time
In this section, we prove that the synchronization time has finite expectation in the continuous-time setting. Unlike the discrete-time setting, we do not need to make any additional assumptions other than the standard unichain condition. Our proof is based on the observation that the holding time distribution of a continuous-time Markov chain has support on the whole positive real line, so an arbitrary number of transitions can happen in any time interval, which, from the uniformization perspective, implies self-loops in all states. We can thus prove that synchronization time has a finite expectation using similar logic as the proof of Proposition and
Lemma 5 (Synchronization in continuous time). Consider the single-armed policy क and the corresponding souder-and-follae system. Given the initial states ((()), (s. 3), the synchronization time is bounded as
E sy 3)] < oc.
Proof of Lemma
Consider the always-1 policy मं given by
1,
if 1,
म (als)
for E S,a E A.
0, if 0.
22

---

By the unichain property, 1 only has single recurrent class, which we denote as Sj. We denote the recurrent class under स as S.
We first prove by contradiction that S SnS1 A 0. Suppose S SnS; = 0. Then we define a new policy n'
F'(ass = (a]s), E for 8 E a न. (als), otherwise.
Then S and S are two distinct recurrent classes under म'. This is because by definition of म', an arm with the initial state in S remains in S, so it cannot reach S similarly an arm cannot reach & from St. The existence of two recurrent classes contradicts the unichain condition. Therefore, we must have 8 n S1 + 0.
We show that given any pair of initial states s, S, the probability that 7 3) is positive. We construct a sequence of positive probability events that leads to S(t = St) before time 3:
1. The leader arm reaches state s" such that # #11[s)) > 0 by time 1 and chooses action 1;
2. The leader arm has no transition during [1,2], so (t) s and A(t) 1 for all E [1, 2]:
3. The follower applies the same action the leader arm during [1, so A(t) 1 for all
[1, and reaches the state s by time for some s² E S1;
4. The follower arm stays at s during [2, and the leader arm reaches sh by time so the two arms synchronize.
The first two events have positive probabilities because the policy म applies action 1 with positive fraction of time. To see why the third event has a positive probability, observe that the follower arm applies action 1 for all traverse all states in Sj. The fourth event has a positive probability because the leader arm under π are implicitly assuming that the two
[1.2] regardless of its state, it is effectively under policy म and could
can traverse all states in S. Note that in the above arguments, arms do not synchronize in the middle of the four events, because otherwise we are done. Also, we the fact that in continuous-time Markov chain, there can be arbitrary number of transitions during any time interval. Therefore, we have proved that for all 8, 8 E S,
IP (T (s, 8) < <3) >
Now we prove by induction that for all 8, 3 E S and h: = 0, 1, 2,....
P ST (s, 3) 2 3k) <
max IP ( (s', 3) 2 3))* E'SSS
(30)
The base case is already known. Suppose we have proved 30 for a certain k; then
P (7 3(k: + 1)) P (7 (s. 3) 3k) P (7 (s, 3) 3(k 1) syne (s. 2 3k)
P (7 (s, 8) 3k) P
S(3k) 5(3)) # S(3k)
P (7 (s, 3) 3k) max P (- (6'88)) 2 3)
''E'SS
< max P (T (8. 3' 3) 6+1 E8
where in the second equality we have used the Markov property of the system, and in the last inequality we apply the induction hypothesis. This proves 30
The bound on the expectation E [-sy (s, 3)] follows summing the tail bound (30 over 0, 0, 2,
E syne (s, 6)] <
3IP (7 syne (s, (x,3) 2 3k)
k=
3
max Ee IP (T 3') 2 3)
where the second inequality is due to 30 and the fact that max (17990 S1
miny ee P (55900 8') < 3) < 1. This finishes the proof.
23

---

F.2 Overview of the proof of Theorem 2
In this section, we focus on proving the bound 20 on the conversion loss V/2 any single-armed policy म. The asymptotic optimality result (2I) in Theorem 2 consequence of (20) we take स to be any optimal single-armed policy π².
VN
V for
will be direct
We first show that under FTVA-CT(T) defined in Algorithm 2 {(S(t), (())) is continuous-time Markov chain and each virtual process is an independent Markov chain induced by applying to the single-armed system, as stated Lemma below. We will prove it in the next subsection.
Lemma 6. Under the (TVA-CT(T) defined in Algorithm 2
we have the following:
(1) ((5(t), S(t))) is continuous-timg Markov chain.
(2) (5,10) for E [N] are N independent Markov chains, whose transition rate from state 8 is E.cA G(s, a, (a(s))) for 8, 8,8' & + s'
Let (y(s, eESEER be the steady-stat state state-action distribution of the single-armed system under Then the second result above implies that for each l. 2 O, (5,((),((())) for i E [N] are ii.d. with the distribution (y(s, a)) sE..E...
Next, we can upper bound the conversion loss V/² VN
FTVA-CT(FF)
N
N Σ ((S(()))
V
VN
(T(*)
r (S,) A,(00))
N
N
2 max
1 { (S1(00), A((oo)) # (5:(00), A((00)13
E
N
2 max
(0000) # S(00)) + Σ 1 E (A<))) + |
E
Σ
(31)
N
The bound slightly different from the 13) since we want separately deal with the number of arms whose real and virtual states do not agree and those whose real and virtual actions do not agree, as shown in the lemma below.
Lemma 7. It holds that
E
Σ
& +((00))
< 2mmxx max
Tyyc E
Σ A1( aN
(32)
E
(A((0)) + A(000)
Σ A,00)) oN
(33)
Before showing the proof of Lemma 7 will first use Lemma
7 to prove Theorem
Proof of Theurem Combining and Lemma we have
V FTVA-CT(3T)
2fmax N
(1 + 28taax Tayne
)E
N Σ i=1
A,(20)
AN
By Lemma 6 the virtual actions (oo)'ss are i.i.d. binomial random variables such that (0)) = 1) E.es (() a) a, so the distribution of ENV, A:(co) is Binomial(N, whose mean and variance are o.N and Na(1 a) < N/4. Therefore,
N
N Σ i=1
(,0)) -00) )
1/2
E
Σ
A((x)) aN
S E
24

---

1/2
Var
(00)
1
$ VN.
Combining the above calculations, we get
VI= V (T()))
mmax (1 + 20maxx
7
N
F33 Proof of Lemma 6
Proof. We first show that ((S(),, (()) is a continuous-time Markov chain. Observe that ((t()), F(2)) is piecewise constant between decision epochs { so it suffices to consider the time between the decision epochs f++1 - t& and the states at the decision epochs (S(t)), (tx)) for k = 0, 2....
We claim that each decision epoch te, the time until the next decision epoch fx+1 f is expo- nentially distributed conditioned on (S(ta), (tz))). Observe from the pseudo-code in Algorithm 2 that at the decision epoch 12. conditioned on (S(tz), At&)), S(t+)), )), the time until the next deci- sion epoch 1 is the minimum of two independent exponential random variables, correspond- ing to the exponential timer and the transition of real states. The rates of the two exponential random variables are 2.Ngmax ghal and real where 9%
-i=1 G(S,(ta), (txx) There- fore, conditioned on (S(t)), A(ta), (tx)), tk+1 - tx has an exponential distribution with rate 2.N Imax 9x + gxxوl = 2NN 9max. Because the rate 2N Imax is a constant, if we take expectation real
over Atx)) and only conditioned (S(tx), (tu)),, the time until the next decision epoch 44+1 fx is still exponentially distributed with rate 2. gmax-
Also, it is obvious from the pseudo-code in Algorithm that conditioned on (S((k), (tt))) the distribution of (S((++1), S( ((2++)))) 1) is independent of [x+11 - 1s and (S((), ((t) for < 4. Therefore, we conclude that (t))) ((t))reo a continuous-time Markov chain.
Next, we show that the (t,) for i E [N] are N independent Markov chains, whose tran- sition rate from state s to s' is Eaer G(s, a, (a)s( for s' * 8. Beeause we have shown that ((S(1), (22)) is a continuous-time Markov chain with a constant transition rate, suffices to focus on the embedded chain that change the virtual states (txx). Note that between two decision epochs tx and tx+1, there is at most one such that (t))) changes. Let Igood (4x) = {i [N]: (t,)) = (12), A,(tx) = A. (fx). (f&). the transitions of its virtual and real states coupled, which implies
((ta))
and examine the probability of the transitions
For any arm i Igaou
that the probability that S, (1x+1) = s' the same as the probability that (t(++1) = s', for any s' # (,(4)), conditioned on the states and actions at lg. Formally,
P (S.(tt+)) = s|s((t), A(ta), S(tw), 1 E [t)o
= = = S(ta), A, A(tx)) A(te,, 1 [to))
A(ta)
G(S,(1k), A.(l)),,)) Lii (t)3
2N
G(Š,(ta), A,(tx), 8¹) 1fi (ggood(44))
(34)
2N
where the second equality uses the fact that the transition probability after uniformization is equal to the ratio between the transition rate and the uniformization rate; the last equality is by the definition of (good(ta). For & (tx) and s' * St(t)), we have St(t++1) s' only when the exponential
25

---

clock ticks and the pair (i, s') is sampled, so
IP (1((++1) = 5()))) A(4)), S(4)), A(4x) ( 1 & (2ma((4))
2N Imax
Real G(St(tt)A((tt)s))))
A(te), S(4)), A(ta) 1 [t)na(te)
=E
2N 2Nomax
2N Smax
((S,(t)), A,(tx), 8')
1f0 Igood(tx)) (fx)}
(35)
2N gmax
Summing up 34 35 we have that for any i E [N] and s' s'* #Bx(tt),
A(k,, S(te, A(ts)) G(S.(ta). A((t),
P ((S((te+1) = s(s( =
(36)
2N 2N Jmax
Because (44) independently sampled from the distribution (+-),((tx),, taking expectation over (A(tx), A(tx)) in the above equation, we get
((S.(tt+11) = S(tw), ((t)) = Enca (
(37)
2N 9max
for any E [N] and + (tx). Because the uniformization rate is 2N 9max. the rate for (t( to transition to is equal to Eaca ((),((), ",)') (a)) conditioned on (S(1), S()). Observe that this transition rate only depends on (t), which implies that (tt''ss for e [N] are N i..d
Markov chains.
Finally, recall that initialize the virtual states 3,(')'s N i.i.d. samples from the stationary distribution of the single-armed system under the policy म. Since we have proved that (S,(t)).20 are N i..dd Markov chains induced by applying मे to the single-armed systems, for each t 2 0, (t)'s remain stationary and i.i.d. Therefore, for each t 2 0, (t) (t))'s are i.i.d., and for each the distribution of (t), A.())) is equal the steady-state state-action distribution (y(s, a)) n
E44 Proof of Lemma 7
In this section, we prove the key intermediate result, Lemma 7 The second equation (33 Lemma] 7
is obvious from the definition of the policy. We can therefore focus on proving (32), i.e. bounding the long-run average number of arms whose real states are not equal to their virtual states. We call such arms bad arms, and the rest of the arms good arms.
We will use similar approach as Section E we invoke Little's Law to write the average number of bad arms as a product of the average disagreement rate and the average length of disagreement periods, based on suitable definition of the disagreement events.
We define the disagreement event in a different way than in the discrete-time RB setting, because unlike in the discrete-time time RB setting where (t) * At(t) can immediately cause S;(t) * St(t), in the continuous time RB setting, actions that last for only a short time may not have an effect on the states. Therefore, we say a disagreement event for arm i happens at time t only when arm i behaves differently than it would have behaved if A,(!) (t)
Specifically, the disagreement event of good arm can be defined as having a state transition that turns it into bad arm, since a good arm is supposed to remain good if we always have A, = A, (t); for bad arms, how the arm "would have behaved" need to be defined with the help of an extra structure, namely, exponential timers, as described below.
Definition 3 (Exponential timers for simulating the fander-and-follower system). For each i [NV, we run timer for each arm i that ticks every random amount of time. When the timer of arm i starts, it decides the time of its next tick based on the i-th arm (S:(1, A,()), Sa(1). A.())): if (t) A St(() and Ac(t) A Ac(t), the timer ticks after time that is exponentially distributed with rate (()) (1):: otherwise, the timer pauses. The timer restarts when ticks or when there any event happening in the system.
26

---

The purpose of the exponential timer is to simulate the transition time of the Seader-and-follon system, which characterizes how the arm would have behaved if A,(t) (t). Specifically, when arm i has (t) + (t()) (so it is a bad arm) and A,(t) # (t).). we construct an imaginary leader- and-follower system whose state-action pairs are (S.(t), ( (t). (t)). We let the transition times of the virtual state (t) in the two systems be identical, and the transition times of the real state (t) in the two systems be independent. Then the transition time of St(t) in the moder-and-followwe system has an exponential distribution with rate (t,, (t)),, which equal to the time that the exponential timer ticks.
Therefore, there are two ways that the transition of arm with St(t) + St(t) and A,(t) + (t) can deviate from the mader-and-followwe in the real state (t), when the exponential timer ticks. This statement is actually also true if (t) (t) and (t) # (t) because in that case, the exponential timer pauses.
system described above: either arm i itself has a transition
We can thus formally define the disagreement event of arm as below.
Definition 4 (Disagreement event for continuous-time RBs). For each [N], a disagreement event of arm i happens when its real state St(t) transitions or its exponential timer ticks, while (t) * (t).)
After defining the disagreement events, we can define the disagreement period of arm as the period of time when (t) * (t))), separated by disagreement events, formally stated below. Definition (Disagreement period for continuous time RBs). Given sample path of the arm i's real states and virtual states (t), (t)) and an exponential timer, we define the disagreement period of the arm i as time interval (fggin fend) such that
There is disagreement event at Inegini
There is no disagreement event during (Progin fend); and S,(t) * S,(t) for t E (fnegin: fend):
There is disagreement event at lend Si(lena) = (Lena))
We let d(s, 8) )) be the instantaneous rate of disagreement events (instantaneous disagreement rate) when the system has real and virtual states (S(I), S(1)) (8, 8). Let Davg be the long-run average length of the disagreement periods.
Observe that the number of bad arms (the arms such that St * (t) is the number of arms in disagreement periods, so we can apply Little's 's Law to the number of bad arms.
Lemma (Little's Law for disagreement periods, continuous-time version). It holds that
Σ 1(5((00) + [ =E [d(((())),
E
Dawg-
(38)
where d(s, 8) denotes the instantaneous disagreement rate when the virtual states are S(t) 3;
D Davg denotes the long-run average length of the disagreement periods. Lemma 9 (Average disagreement rates). The instantaneous disagreement rate is equal
d(s, 8) < 2gmax IE
Σ A,(1) aN |5()) =
(39)
Proof. For each arm i such that A,(t) # (t),, a disagreement event happens if its real state transitions, which happens at the rate G()) A,()), or if its exponential timer ticks, which happens
the rate 0 (if it is good arm) ((S,(t), (,))) (if it is bad arm). Therefore, the rate that disagreement events happen at arm i is no more than
G(S,(),, A.()) + G(S:(), Â.(1) S 20max-
||E Ā,(1) aN| | arms
By the definition of the policy, there are expectation with (t(t) * At(t). the instantaneous disagreement rate of the system is given in 39
O
27

---

Lemma 10 (Average length of disagreement periods). It holds that
D Dav-
7
(40)
Proof. To bound Dag. it suffices to bound the expected length of disagreement period with arbitrary initial states. Without loss of generality, consider disagreement period on arm that starts time fregin = O, with initial states (0), (()) = (s, 3). During the disagreement period, there is no disagreement event, so argued in the paragraph after Definition 3 the transitions of the i-th arm is identical to Seader-and-follower system. Therefore, amount of time, or have a disagreement event before that. In either case, lend S 7 (s, 8). Therefore, the expected length of the disagreement period satisfies
either have (L) (1) after 7 (8, 8)
fend /ocgin] = E [Lend] I E [T (8, (8,8) I
7-yne max
This holds for arbitrary initial states (s, Davg I
7-yne max-
Proof of Lemma
7
Combining Lemma 8 and 10, we have
N
((0))))) # 8((00)
= d(S((o)), S(co)) Davg
N
< 29max mux
sycc E
Σ
(oo) aN
This proves
Observe that by the definition of our algorithm, at any time t,
N
Σ [A+++00)))
Σ Ā,(1) - aN
a.8.
Taking the steady-state state expectation, get 33
G Experiment details and additional experiments
In this section, we include the details of the experiments in the main body, as well as some additional experiments. In Appendix [nd G.2] we describe the details of the experiments of Figure] and 3
We conduct the simulations of these two experiments with different initial points and present the
results in Appendix G.3 To give intuitive understanding of the difference between these policies. we also display more visualization of the sample paths under different policies in Appendix G.4
G.1 Experiment details of Figure
Restless bandits setting In Figure we consider the discrete-time N-arm restless bandits repre- sented by the tuple (N, SN A N P. r, Nv... We vary the number of arms N, and keep the rest the parameters fixed. The state space of each arm is S {1,2,3} 3}. The action space is A {0. 1). The transition kernel is given by
T0.02232142
0.10229283
0.87538575
P(;0,-) =
0.03426605
0.17175704
0.79397691
[0.52324756
0.45523298
0.02151947
10.14874601
0.30435809
0.546895891
P(,1,-) =
0.56845754
0.41117331
0.02036915
0.22565550
0.27310439
0.4742399
where the number in s-th row and s'thh column in each matrix represents P(s,0, or P(s, 1,8), for 8, s' 31, The reward function is given by
0(: = [0 0
0
Our simulation code be found in the link ht attps: :ttp:://giiiee http///gtttttttt/eeeeeeeee. htap:/thhwbbbcmm///ellonng/e/e/e bww.b-beaa..- wwtt-bbreee-----uueeeeeeee ftva-ftva
28

---

r(.1) [0.37401552 0.11740814 0.07866135].
where the s-th entry of each vector represents r(s, 0) or r(s, 1), for E (1.2.3). The budget parameter a 0.4, so 0.4.V arms are pulled in each time slot. This setting is taken from the Appendix of YG as counterexample to the UGAP assumption. We note that this RB problem obviously satisfies Synchronization Assumption for any policy: observe that a(s,a,s) > 0 for all s, E S, a E A, so two arms with any initial states have a positive probability of synchronizing in the next time slot, which implies finite synchronization time by Proposition 2
Simulation setting We plot the long-run average reward against the number of arms for different policies. The number of arms N varies from 100, 200, ..... 1000. Three policies are considered: our policy FTVA(#*), the Whittle's index policy [Whi88], and an LP-Priority policy [[er16]. For each data point, obtain the long-run average reward and its confidence interval by simulating 50 independent trajectories, each with a length of 1000 time slots. The initial states of all arms are simply chosen be because simulation results do not quite depend on the initial states (see Appendix G.3)
Detail of policies We implement Whittle index policy and I.P-Priority in the standard way. The resulting priorities of both policies turn out to be 1 > 2 > 3 (state 1 has the highest priority). This is not a coincidence given that the solution of the single-armed problem (LP) is:
0
0. 0.299433
y" (())) =
0.23768
0.10057 0
0.36233
where the s-th row represents (s, 0) and y (s, 1), for s E (1, This solution implies that a reasonable policy should almost always pull arms in state pull arms in state 2 for certain fraction of time, and almost never pull arms in state 3. Therefore the only reasonable priority in this RB 3.
setting is
Our policy FTVA(#*) is implemented according to the pseudocode in Section 3 The non-trivial detail here is the tie- breaking rule for selecting the set of arms to activate based the virtual actions. Our tic- breaking rule is to select (t))'s 's such that the number of good arms, i.c., the arms such that (t) S (t) and (t = (t), is maximized. We have experimented with alternative tie- breaking rules, whose performance matches our theoretical results, though sometimes their asymptotic optimality requires larger values of N to be observed. The relationship between various tie breebreg rules and their impact on finite-N performances remains unclear the present analysis, leaving it as a topic for future investigation.
G.2 Experiment details of Figure
Restless bandits setting In Figure 3
consider the discrete-time N N-ar bandits constructed as 7}. ......,).. Each state has preferred action, and action otherwise. For
below. Suppose the state space for each arm is S = {0. 1,...,
which is action 1 for states 0, 1,
in state s, applying the preferred action moves the arm to state (s + 1) mod 8 with probability Pa.R, and applying the other
action moves the arm to state (s - 1)* with probability Pe.L The probabilities p.R and p.L. are given by
P.R = 0011 0.1 0.1
0.1
0.1
0.1
0.1
0.1],
P.L [1.0 1.0
0.48
0.47
0.46
0.45
0.44
0.43).
When the arm transitions from 7 to 0, one unit of reward is generated. Equivalently, if we consider the expected reward of applying an action at a certain state, we can define the reward function as r(7, 0) P7.8. and r(s,a) = for all other E S, E A. The parameter 1/2, so N/2 arms are activated in each time slot.
Simulation setting We plot the long-run average reward against the number of arms for different policies. The number of arms N varies from 100, 200, ... 1000. Three policies are considered: our policy FTVA(#*) ), random tie-breaking policy, and particular LP-Priority policy that prioritizes arms with larger Lagrangian optimal indices (see the definition of Lagrangian optimal indices in
'eere the subscript L means "left", and R means "right". We are imagining the arms being lined up in row from state 0 to state 7, and the preferred action moves an arm the right.
29

---

[HFI7 BS20 GGY22), ). This particular LP-Priority policy is also referred to as the LP-Index policy the literature. But for simplicity, we just refer it as LP-Priority this paper. For each data point, we obtain the long-run average reward and its confidence interval by simulating 50 independent trajectories, each with length of 1000 time slots. The initial states for the simulations are fixed: N/3 arms are in state 1 and 2N/3 arms are in state 2. Note that we fix this initial point in the simulation of Figure B in order to demonstrate that both the random tie-breaking and LP-Priority can get nearly zero rewards in this example. For other choices of fixed points, there is also a strong separation between the performance of FTVA(#*) )) and random tie-breaking or LP-Priority, which we will show in the next section.
Details of policies The optimal solution of (L)) is y 1) 1/8 for & = 0, 1, 2,1,2,3.y* 0) = 1/8 for 4, 5, 6, 7, and y² (s,a)= 0 for other S and a E A. Note that the same y remains optimal even if we remove the budget constraint. The optimal LP solution suggests that reasonable policy should almost always pull arms in states 0, 1, 2, 3, and almost never pull arms in states 4, 5, 6,
The random tie- breakkn policy that we consider prioritizes arms whose states are in (0, 1, 2,3 over arms whose states are in {4, 5, 6, 7),, and it breaks ties uniformly at random when there are more than N/2 arms in either of the two sets.
The LP-Prioritty policy we consider prioritizes arms with larger Lagrangian optimal indices [BS20 GGY22 Specifically, involves solving the Lagrangian relaxation of the original LP, which replaces the budget constraint with a penalty term determined by the optimal Lagrange multiplier. In our setting, because the optimal solution y" remains optimal even without the budget constraint, we can simply remove the budget constraint to get the Lagrangian relaxation. The resulting Lagrangian optimal indices are given by:
[0.0125 0.1375 0.0725
0.07125
-0.07 - 0.06875 -0.0675 - 0006625),
and the priority is 2 3 0 > 7> 6> 5>
The implementation of our policy FTVA(#") is the same as in the last experiment.
Further discussions of the policies As shown in Figure 3 the random tie-breaking policy and the LP-Priority policy get nearly zero rewards. We have discussed why this happens for the random tie-breaking policy Section 3.3 For the LP-Priority policy based on the Lagrangian optimal index, the reason why it does not work is less obvious. Some sample paths suggest that under this policy, the arms will concentrate on {3, 4, 5} most of the time and thus cannot get a reward. Here is a possible explanation for why arms cannot easily escape from {3, 4, 5]: when some of the arms transition to state 6, by the priority 6 > 5 > 4, those arms in state are likely to be activated. Because states 6 do not prefer action 1, those arms will transition back to state 5 and thus get trapped.
In addition to the numerical results, we also note that our policy FTVA(#*) is provably asymptotically optimal in this RB problem even though its transition kernel is not unichain. This stems from the fact that the optimal single-armed policy म has a single recurrent class S, and satisfies Synchronization Assumption. See Appendix D for the discussion on the conditions under which Synchronization Assumption and Theorem hold when unichain is not assumed.
G.3 Varying the initial points of the Figure I and examples
In Figure T and Figure we have fixed one initial point for each simulation, for the ease of presentation. In this section, rerun the simulations for these two settings with more initial points. For the simulations of each setting, we generate initial states in the following way.
We first choose probability distribution on the state space S from all the possible probability distributions on uniformly at random. Let (s)) denote the probability of state s under the chosen distribution. This distribution is chosen independently across the 20 sets of simulations.
For each N-armed problem, we set the initial state such that N (s)) arms are in state s for each s, with proper rounding.
For each Narmed problem, we run all the policies with this initial state.
A nuance is that the optimal Lagrange multiplier for the budget constraint is not unique in this setting, so there can be different Lagrange relaxations. We focus the simplest one.
30

---

0.125
0.0200
FTVAGE"
min of 20 sets
0.120
0.0175
Rendom tie- breakinaknggg... mex of 20 sets
LP. JP.Priority max of 20 sets
Avg Reward
0.115
Avg Reward
0.0150
Upper bound
0.0125
0.110
0.0100
0.105
0.0075
0.100
FIVAIT ). min 20 sets
0.0050
Whittle Index/LP- P-rrrritty max of 20 sets
0.0025
0.095
Upper bound
0.0000
200
400
600
800
1000
200
400
600
800
1000
(a) The experiment Figure
(h) The experiment of Figure
Figure 6: We re-run the two experiments of Figure [ with 20 sets of simulation with randomly generated initial points. For FTVA, we calculate the minimum average reward over the 20 sets; for the other policies, calculate the maximum average reward over the 20 sets.
We illustrate the results of the 20 sets of simulations in the Figure ba and in the following way: For FTVA(#"), for each N, we take the minimum average reward over the 20 sets of simulations and plot them in the figure; For other policies, for each N, take the maximum average reward over the 20 sets of simulations. We can see that the min curve for FTVA(#*) ) still approaches the optimal value as N increases, whereas the max curves for other policies strictly separated from the optimal value.
G.4 Visualization of the policies
In Figure of Section 3.3 illustrate what LP-Priority and FTVA(#*) does differently by visualizing their sample paths. Here we include more such figures.
We still use the same example defined in Section 3.3
To recap, this example has 8 states, numbered as {0, 1, 2, 3, 4, 5, 6, 7]. The optimal single-armed policy always chooses the preferred action in each state, which is 1 for states 0, 1, 2, 3, and 0 for states 4, 5, 6, Under the optimal single-armed policy, each arm moves from state s to (s + 1) mod 8 with probability 0.1 or stays at s with probability 0.9. The optimal distribution for the single-armed system is uniform over the 8 states.
When simulating the policies the N-armed system, we can tell that policy is good if the fraction of arms in each state is roughly uniform, and bad if the arms concentrate on a small number of states. can also see why this happens by looking at whether the preferred action chosen, and whether the arms are moving from to (s + 1) mod 8.
The three heatmaps in Figure 7a illustrate how the fractions of arms each state change over time under the three policies: random tie-breaking, LP-Priority, and FTVA(T"). The x-axis represents the time slot, which ranges from larger fraction of arms in this state at this time, and the specific value represented by each color can be found in the color bar on the right.
499; the y-axis represents the states; the brighter color represents a
We can see that under the random tie-breaking, the arms concentrate around state O; under LP- Priority, the arms concentrate around states {3, 5) after burn-in period; under FTVA(T").. the arms uniformly spread out over the 8 states.
In Figure 7bl we take closer look at the sample path of the random bie-breaking policy from time 250 to 289 and contrast it with the sample path if the system uses FTVA(#*) from time 250 onwards. We also add some arrows indicating the drift of the arms, i.e., the average direction that the arms in this state are moving into. The colors of the arrows represent the direction: the blue arrow implies that the arm takes the preferred action and moves in the correct direction, while the red implies that the arm takes the non- non-preferred action and moves in the wrong direction. The magnitudes the arrows represent how fast they moving.
We can see that under random tie-breaking, although the arms have strong tendency to move up from state 0 to state 1, they move back when they reach state 1 and thus get stuck at state 0. In
31

---

78
68
58
28
1.6
160
time slot
(a) Time evolution of fractions arms each state under the three policies during the first 500 time slots. Top to bottom: Random l'c-Breaking, I.P-Priority, and FTVA("").
78
48
58
state
4-
3
20
1.8
time slot
(b) Time evolution the fraction of arms in state under Random Tie-Breaking (upper), or after switching to FTVA(#") ( (lower) since time slot 250. The color and magnitude the arrows represent the average movement of the arms in each state.
Figure Visualization of the sample paths under different policies for the example Section 3.3
contrast, when switching to FTVA(#"), most arrows point in the right direction, which implies that the arms consistently apply the preferred actions. As a result, FTVA(#*) helps the arms to escape from state 0 and converge the uniform distribution over the state space.
Figure Sa illustrates the fraction arms in state s taking action a in a few time slots after 250 the same sample path of the random tie- soebbraking policy in Figure /a For each and a. The upper bar plot is under the random tie-breaking policy, while the lower bar plot is after switching to FTVA( The x-axis represents the state; the y-axis represents the fraction; there
four bars in each state, corresponding to time-steps. Each bar has two segments, where the length of the blue segment indicates the fraction of arms taking the preferred action in this state, and the length of the red segment indicates the fraction of arms taking the non-pue non-preferred action in this state; the lower segment of the bar corresponds to action O, and the higher segment of the bar corresponds action
We can see that under FTVA(#*). more arms choose the preferred actions for state than under the random tie-breaking policy, which prevents the arms in state from moving back to state 0 in Figure 7b under the random tie-breaking policy.
except that the random tie-breaking policy is replaced by the I.P-Priority policy. We can again see that under I.-Priority there is force that causes the arms to concentrate state, whereas switching to FTVA(#")) helps the system to escape from that state.
Figure 8b is similar to Figures Sa
32

---

0.6
preferred action nen-preferred
preferred action
0.8
non-preferred action
0.6
0.3
0.4
0.2
0.0
preferred action non-preferred action
preferred action
0.8
non-preterred action
0.3
0.4
0
5
3
state
state
(a) The fraction of arms in each state taking each action in the time steps following time 250, under Ran-
(b) The fraction of arms in each state taking each ac- tion in the 4 time steps following time 250, under LP- Priority (upper plot) or after switching to FTVA(*") (lower plot).
dom Tie-Breaking (upper plot) or after switching to FTVA(#*) (lower plot).
Figure 8: Actions taken by different policies for the example in Section 3.3 In each bar plot, the X-axis represents the states; the Y-axis represents the fractions. Each state has bars for the 4 time steps. The blue segment of each bar is the fraction of arms taking the preferred action; the red segment corresponds to the non-preferred action. The lower segment of each bar corresponds to action O; the higher segment corresponds action
The common failure mode for random tie-breaking and LP-Priority in this setting that the arms concentrate on bad state which prevents the arms state (s + 1) from applying the preferred action due the budget constraint. This causes a livelock where the arms move back and forth between state and (s + 1), and fail to gain a reward by moving past state 7. FTVA(#*) solves this issue by letting more arms in state (s + 1) follow the preferred action, which breaks the livelock and helps all arms converge to the optimal distribution.
H Generalization to heterogeneous arms
In this section, we show how FTVA and its analysis can extended to the case with heterogenous arms. We focus the discrete-time case for simplicity. The continuous-time case can be analyzed in a similar fashion.
H.1 Setting and algorithm
Suppose the arms divided into K types, with N arms in each type k E (1,2...., K} - [K], and each type is associated with an MDP. The transition kernels and reward functions can be different across types. Suppose each arm is indexed by k(i). For any type k arm, we let (s a, s¹) be its probability of transitioning from state s to s' upon taking action a, and let rx(s, a) be its reward for taking action a in state s.
[N], and denote the type of the i-th arm as
Consider the linear program below, whose variables yo (s, a) represents the steady-state probability that type arm is in state taking action a, for k [K]. s E S, a E A.
maximize
ΣΣ
(LP-Het)
{ye (e.o) (e.o))))eee aEE
subject
Σ>
(sy 1) =a,
(41)
k
33

---

Ev (()),))s((s',.. a, Een(s, Ak [K], S,
(42)
Σ (x =1 Ak [
(43)
(s a) 2 O, E k E S,
where the three constraints 41 summations, we omit E [K]
42 and (43) correspond (5). and in LP when writing
S and A. for simplicity.
(LP-Het) can be viewed as relaxation of the N-armed problem. To this, take any N-armed policy и and set (8, a) to be the fraction of arms in state s taking action a among type k arms in steady state under n, i.e.,
()) N
E Σ (x)7))))
k(1)=k
Therefore, Whevener π satisfies the budget constraint (2). {yx (s, a) [e[[K] satisfies 41 43
the optimal value of (LP-Het), which we denote as VT is an upper bound of the optimal value of the N-armed problem, i.e., V Vi-
The optimal solution to Let). {ug(s, ()) induces a optimal single-armed policy Tg for each type & E [
(x, a) (3) 1/22
u 1)), if vf + (s, 0, if yZ 0) + (), =0 for E A.
T (als)
(44)
Standard argument in [Put05] show that if a type &o arm runs मे. it achieves the steady-state expected reward E.,. a)) (s, a), and requires E. 3/ (s, 1) unit of budget in steady-state. If each type arm could independently run the optimal single-armed policy of its type, since the fraction of type arms in the N-armed system is 3r. in steady state, the expected reward per arm would be V/rel, and the budget requirement per arm would be > E. (s, 1) a, which is analogous to the homogeneous case where the optimal policy of the relaxed problem in 3 achieves Viell reward and requires a expected budget steady-state.
To convert from the ainel policies to an N-armed policy, FTVA lets each arm of type k independently simulate virtual single-armed process following मt. Lines 3-14 of Algorithm stay the same. We denote the resulting policy as FTVA (TTAA((A)Ka)) (=()k)())) The resulting policy can be proved achieve (LL/VN) optimality gap. under the assumption that Synchronization Assumption is satisfied for each Ki. as stated below:
Theorem In restless bandits with heterogeneous arms, let {TE]kE[K] be the optimal single-armed armed policies induced by (L.-Het). Assume that for each k [K], #% satisfies Synchronization A Assumption (T2Th(s, with the synchronization times {T& (s, (,,,333 (s.))ss...))eexxxxx... For any N 2 1, the optimality gap of FTVA([#; (TVA((*)))E(K)) is upper bounded as
V
N
FTVA(((()<<(KK)
Tmax 7 syne
max VN
(45)
where Tmax maX [r(s, a) and syyne max
maX
[
sync
(s, 8, a.
H.2 Proof for Theorem 3
In this section, we prove Theorem
3
Since Viel 2 Vg. suffices to show that
Viel
( VN
Tmax Syne
(46)
VN
We start with inequality that has the same form as [13 in the homogeneous case:
Σ r
(31))))
(S((0)).
34

---

N Σ (3(((()))AA(00))) + (S/(00), (((00))
max
(47)
where in the first equality, we used the fact that the virtual processes are independently running the single-armed policy of the corresponding types, so they achieve the average reward Vi
Defining the disagreement events, disagreement periods, and disagreement rates in the same way as Appendix and applying Little's law, we have
((o)) (S.(0)). =E [d((((00))] Davg
E
(48)
where d(3) is the instantaneous disagreement rate, and Davg is the long-run average length of disagreement periods. With (47 and 48 it remains to bound E [d(S(oo)) and Davg.
By the definition of the policy, we have E [d(S(2o)) = E | (o0) aN) (oo))ss are independent Bernoulli random variables, and E [A0(00)
= 1/ (s, 1) if arm is of type k. As result,
N
E
( = Σ N Σ 1) Σ
3,a
Using the same Cauchy-Schwand Schwartz argument as in the proof of the homogeneous case in Appendix E is not hard to show that E. (d( (((S())) S vN/2.
As for Dang. it is not hard to see from the definition that the length of each disagreement period of type k arm is stochastically dominated by (s, a, ā), where (s, 3, a) are the initial states and actions of that disagreement period. Therefore, the average length of disagreement period is bounded by
max Davg (
E T
syne (s, a, 3, a)
syac
Combining the above calculations, get (46). which finishes the proof.
35


Reviews:
[{"review_id": "AXOToi4ftR", "reviewer": "Reviewer_JXov", "summary": "This paper studies the problem of optimizing a policy for restless bandits in the infinite horizon case. A new algorithm is proposed that can convert a single-arm policy into an N-arm policy using virtual trajectories of the states and actions of the single-arm policy. The main idea is to generate virtual actions using the single-arm policy and then attempt to match these virtual actions with real actions that match the budget constraint. The algorithm is shown to have suboptimality that degrades with N. Both discrete time and continuous time versions are given. One of the main contributions is that this paper forgoes the UGAP condition.\n\nThis is an emergency review. I am not familiar enough with this literature to definitively judge the significance and novelty.", "questions": "It is mentioned that Algorithm 1 should “steer” the trajectories towards the virtual trajectories but still respect the budget constraints. However, in Line 4, the selection of the smaller set to respect the budget does not appear to filter arms in any particular way. What prevents the same arms from being activated while starving others and thus causing the virtual trajectory to differ from the real one by a lot?\n\nSuggestion: the paper could benefit from further discussion of the last theorem and a conclusion.", "limitations": "No negative societal impact, but it would be helpful to have more discussion of limitations.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper appears to tackle an important problem in the literature broadly (restless bandits) and provides a potential solution to optimize policies with vanishing suboptimality as N increases. \n\nAchieving this without the UGAP condition that appears in prior work is interesting.\n\nOverall the paper is well written and generally easy to understand. The examples and organization of the paper help convey these results.", "weaknesses": "The main weakness appears to be that the entire premise hinges on the synchronization assumption that the real states and virtual states will eventually match, if the same actions are played, after which point they will remain identical. This seems reasonable in some settings, but a more clear contrast with conditions in other papers would be helpful.\n\nIn general, it would be helpful to better understand the significance of this change of assumptions and how this might translate into practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive comments.  Below we quote the reviewer's key comments and present our responses.\n\n> Compare the synchronization assumption (SA) with conditions in other papers, and better explain the significance of SA.\n    \nBefore presenting the comparison, we reiterate that for the continuous-time setting, our work *does not require SA*. Therefore, we focus on the discrete-time setting.\n\nAll prior work on discrete-time, infinite-horizon average-reward RBs relied on UGAP. We hence contrast SA and UGAP below. Most of the content below is in the paper, but we will make sure to better highlight the contrast and improve the exposition.\n    \n1. **There exist problem instances where SA holds but UGAP does not.**  \nIt is unclear whether SA subsumes UGAP. This is recognized (in lines 61-62) as a limitation of our work. However, there exist problem instances where SA holds but UGAP doesn’t. Two such examples are given in our paper (illustrated in Figures 1 and 2), where the first example is borrowed from [GGY20]. The work [GGY20] provides more examples that do not satisfy UGAP. One can easily see that these examples satisfy SA: all entries in the two transition matrices therein are positive, so two arms starting from any pair of initial states have a positive probability of synchronizing in one step (a formal argument is given in Proposition 2 in Appendix A). For these examples, FTVA achieves an $O(1/\\sqrt{N})$ optimality gap; previously, no policy was known to be asymptotically optimal. Another perspective to this comparison is that SA uncovers the feasibility of achieving asymptotic optimality for more problems.  \n\n    &nbsp;&nbsp;&nbsp;&nbsp; Another helpful comparison is the following. For any problem instance, we can make it satisfy SA by perturbing entries of its transition kernels by an arbitrarily small amount such that all the entries are strictly positive. This implies that the set of problem instances satisfying SA is dense in the problem space. In contrast, UGAP lacks this denseness property. In particular, UGAP assumes the existence of a global attractor. It can be shown that the set of instances that do not satisfy UGAP contains open sets.\n        \n2. **SA is easier to verify.**  \n\n    It has been well recognized in many prior papers that UGAP is tricky to verify. It lacks intuitive sufficient conditions. Prior work has assessed UGAP through numerical experiments, where one simulates the mean-field ODE with randomly generated initial states. However, since not all initial states can be covered, this method can confirm *violation* of UGAP but it cannot certify compliance of UGAP.\n        \n   &nbsp;&nbsp;&nbsp;&nbsp; In contrast, SA can be efficiently verified in several ways. By definition, SA involves the hitting time for the finite-state Markov chain $(S(t), \\widehat{S}(t))$ (eq. (10)) to reach the subset of states $\\lbrace (s,\\hat{s})\\colon s=\\hat{s} \\rbrace$. Therefore, SA can be efficiently verified using path-finding graph algorithms on the state transition diagram of the Markov chain. Additionally, we provide several intuitive sufficient conditions for SA in Appendix A, which can also be efficiently verified by identifying self-loops and cycles in the transition diagram.\n        \n> Can Algorithm 1 activate the same arms while starving others?\n    \nAlgorithm 1 will not activate the same arms while starving others for a significant amount of time.  \n    \nFirstly, it is important to observe that the set of arms $\\mathcal{A}$ activated in Line 4 of Algorithm 1 does not significantly deviate from the larger set, $\\lbrace i\\colon \\widehat{A}_i(t) = 1 \\rbrace$.  Indeed, we’ve shown that the cardinality of $\\lbrace i\\colon \\widehat{A}_i(t) = 1\\rbrace$ is $\\alpha N \\pm O(\\sqrt{N})$ (precise statement in Lemma 2 in Appendix B.2).\n    \nWe therefore only need to focus on the composition of the set $\\lbrace i\\colon \\widehat{A}_i(t) = 1\\rbrace$, which is a random set that varies from time slot to time slot.  Specifically, for each arm $i$, the virtual action $\\widehat{A}_i(t)$ is generated according to the solution of the LP in (5)-(7).  The constraints in the LP ensure that the arm generates $\\widehat{A}_i(t)=1$ for an $\\alpha<1$ fraction of time.  Therefore, each given arm stays in the set $\\lbrace i\\colon \\widehat{A}_i(t) = 1\\rbrace$ for an $\\alpha<1$ fraction of time.  This has two implications:\n    \n- The algorithm will not consistently activate the same set of arms:  the set $\\lbrace i\\colon \\widehat{A}_i(t) = 1\\rbrace$ cannot comprise a fixed set of arms since any given arm will leave the set when its virtual action is 0, which happens for a $1-\\alpha$ fraction of time.\n\n- No arm will be starved: the set $\\lbrace i\\colon \\widehat{A}_i(t) = 1\\rbrace$ will cycle through all arms, since each arm generates a virtual action of 1 for an $\\alpha$ fraction of time.\n\n> Suggestion for adding further discussion of the last theorem and a conclusion.\n\nThanks for the suggestion.  We will add the suggested discussion, highlighting the connection and differences compared with the discrete-time setting, and a conclusion."}, {"review_id": "K25IZn5OYZ", "reviewer": "Reviewer_k12y", "summary": "This work studies the restless bandit problem. In this setting the agent controls a set of $N$ arms modelled as Markov Decision Processes with two actions (active, inactive). The MDPs are coupled with a constraint that forces the agent to maintain a fixed arm activation rate. The authors propose a novel algorithm for this problem that does not use the commonly used uniform global attractor property (UGAP). The key insight of the approach is to transform a learned single arm policy to a $N$ armed policy. While this may lead to a discrepancy between the learned policy and what is actually played because of the constraint, the proposed algorithm aims to bring these two states closer together. The authors provide convergence guarantees and rates for both discrete and continuous time variants of the algorithm.", "questions": "See above for some suggestions.", "limitations": "All limitations are addressed.", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "To the best of my knowledge, the proposed algorithm is novel. The authors also presented very clearly the setup of the problem which is especially important given that many members of the community may not be familiar. While I did not follow all the technical details in this work, the synchronization assumption seems like a significantly weaker assumption than UGAP, indicating this a very strong contribution. On top of that, the way the algorithm solves the problem is itself highly non trivial.  ", "weaknesses": "I think clarifying a little bit more the importance of synchronization when we are using the constraint would be very helpful. I will try to outline my understanding in case it is helpful in improving the presentation:\n\n* In Section 4.1, based on the stated assumptions it is clear that achieving synchronization once is sufficient to achieve synchronization forever. But for the restless bandit setting it seems that the real and virtual states synchronize and desynchronize in a loop. Indeed the states start synchronized and some arms may immediately get desynchronized (become bad in the terminology of Theorem 1). \n* I understand that the the SA assumption helps us understand desynchronization is resolved in finite time. But if synchronization lasts only a single round, then the arms will still be bad most of the time. So SA alone is not sufficient.\n* Based on the proof sketch of Theorem 1, it seems like desynchronization is inherently rare for large $N$ so this is why SA is sufficient. Intuitively, SA is only needed to bound the effect of a single good-bad-good arm loop.\n\nIf my understanding is indeed correct, it would be helpful to make this more explicit somewhere in the text, preferably in the context of the example of Section 3.3.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for appreciating our work, and for the suggestion on further clarifying the role and importance of SA. Your understanding is well aligned with the intended role of SA and with our proofs. We will integrate your suggestion into Section 3.3, specifically within lines 185-193 and in the example."}, {"review_id": "OSz8NK27nw", "reviewer": "Reviewer_TkxD", "summary": "This paper studied, for both the discrete-time and continuous-time settings, the average-reward restless bandit problem without the uniform global attractor property. They proposed the simulation-based policies Follow-the-Virtual-Advice (FTVA) and FTVA-CT, which converts the optimal single-armed policy into the N-armed constrained policy by simulating a virtual process that follows the single-armed policy, and then by letting the real process act closely to the virtual process but satisfying the constraints. The policies provide vanishing performance loss.", "questions": "In the setup, the author assumed that all the arms with the same state and action have the same reward. With this assumption, the problem (with the \\alpha N constraint) is greatly simplified. This assumption makes me feel that even with the \\alpha N constraint, those arms are still acting very independently, not affecting each other too much. And this policy seems very hard to extend to the case where the arms have different reward functions.\n\nIf possible, instead of only the average reward comparison, I am also curious about how the FTVA action policy look like compared to other non-asymptotically optimal policies in the example. And is there any significant different actions on some special states that makes the policy be optimal?\n\nIn the beginning, the author said that FTVA policy can be implemented in a distributed manner for arms, could you add more about it after the algorithm descriptions?\n\nFigure1 is missing one label.", "limitations": "There is no negative societal impact. Discussion on limitations is not extensive.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Novelties: In this reviewer's knowledge, this paper is the first paper to provide an algorithm for the average reward constraint RB problem without uniform global attractor property, which is a property that is hard to verify. The proposed FTVA policy is quite straightforward and also easy to understand. The idea of using virtual processes in this problem seems original to me.\n\nPresentation: The paper is well-written, with precise language and clear structure. The paper is clear and easy to understand. And there are a lot of intuitive explanations.\n\nSignificance: The paper provides the first algorithm for the average reward constraint RB problem without uniform global attractor property.", "weaknesses": "The following assumption is very strong and important to this policy: the author assumed that all the arms with the same state and action have the same reward. And this policy seems very hard to extend to the case where the arms have different reward functions. (More comments in Questions.)\n\nThe paper feels incomplete, which prevents a clear conclusion at the end.\n\nThe simulation is not sufficient, the author only showed the average reward comparison for different policies, but I would also want to know how is the action look like for different policies or is there any intuition in it. \n\nThe paper presentation is too high-level and has missing details. The author claimed at first, but didn’t explain later, how the FTVA policy can be implemented in a distributed manner. The author claimed the algorithm can run at a linear computational cost but didn’t explain how, later.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive comments. We recap the comments and present our responses below. We will revise our paper accordingly.\n\n> Assumption of homogeneous arms.\n\nWe address this comment in the global rebuttal, as this is an important point. In a nutshell, our approach and results can be directly generalized to accommodate heterogeneous arms in a broad class of settings.\n\n> Lack of conclusion.\n\nWe will add a conclusion in the revision.\n\n> Simulations that demonstrate actions.\n\nWe thank the reviewer for this suggestion. We produce more illustrations for the example in Section 3.3 of our paper, which can be found in the pdf attached to the global rebuttal. In this example, we can tell that a policy is good if the fraction of arms in each state is roughly uniform, and bad if the arms concentrate on a small number of states. We can also see why this happens by looking at whether the preferred action is chosen, and whether the arms are moving from $s$ to $(s+1) \\text{ mod } 8$. \n\nThe three heatmaps in Figure R2(a) illustrate how the fractions of arms in each state change over time under the three policies: random tie-breaking, LP-Priority, and FTVA. We can see that the under the random tie-breaking and LP, the arms concentrate around a few states, whereas under FTVA, the arms are uniformly spread out over the 8 states. \n\nIn Figure R2(b), we take a closer look at the sample path under the random tie-breaking policy from time $250$ to $289$ and contrast it with the sample path if the system uses FTVA from time $250$ onwards. We also add arrows indicating the *drift* of the arms, i.e., the average direction that arms in this state are moving in. The colors of the arrows represent the direction: blue implies that the arm takes the preferred action and moves in the correct direction, while red implies that the arm takes the non-preferred action and moves in the wrong direction.  The magnitudes of the arrows represent moving speeds.\n\nWe can see that under random tie-breaking, although the arms have a strong tendency to move up from state $0$ to state $1$, it moves back when it reaches state $1$ and thus get stuck at state $0$. In contrast, when using FTVA, most arrows point in the right direction, which implies that the arms consistently apply the preferred actions. As a result, FTVA helps the arms to escape from state $0$ and converge to the uniform distribution over the state space. \n\nFigure R2(d) illustrates the fraction of arms in state $s$ taking action $a$ in $4$ time steps post time $250$. The upper and lower bar plots represent the random tie-breaking policy and FTVA, respectively. The x-axis denotes the state; the y-axis denotes the fraction; each state has $4$ bars for the $4$ time steps. Each bar has at most two segments, blue indicates the fraction for the preferred action, and red for the non-preferred.\n\nWe can see that under FTVA, more arms choose the preferred actions for state $1$ than under the random tie-breaking policy, which prevents the arms in state $1$ to move back to state $0$ as we see in Figure R2(b) under the random tie-breaking policy. \n\nFigures R2(c) and R2(e) demonstrate a similar comparison between LP-Priority and FTVA. \n    \nThe common failure mode for random tie-breaking and LP-Priority in this example is that the arms concentrate on a bad state $s$, which prevents the arms on state $s+1$ from applying the preferred action due to the budget constraint. This causes a *livelock* where the arms move back and forth between state $s$ and $s+1$, and fail to gain a reward by moving past state $7$. FTVA solves this issue by letting more arms in state $s+1$ follow the preferred action, which breaks the livelock and helps all arms converge to the optimal distribution.  \n\n> The paper presentation is too high-level and has missing details.\n\nWe appreciate the reviewer’s comments here as they help us improve our presentation.  We address the reviewer’s concerns on the implementation and the computational cost of FTVA below.  We are open to any further suggestions.\n- > How will the FTVA policy be implemented in a distributed manner?\n\n    We appreciate this question.  This is indeed a point that we would like to make more precise.  In the FTVA policy, each arm simulates a virtual single-armed process and generates a virtual action in each time step.  Since the virtual processes are independent across arms, these simulations can be implemented in a fully distributed manner.  When taking the real actions, the policy needs to know the virtual actions from all arms.  So this component cannot be distributed.  We will make sure to clarify this in the revision.\n\n- > Why does the algorithm have a linear computational cost?\n\n    We will also add the following explanation for the computational cost of FTVA after the policy description.\n    \n    To see why the computational cost of the FTVA policy is linear in N, we examine the cost component-by-component.\n    \n    - Firstly, FTVA needs to solve the LP in (5)-(7) once.  Given that this LP doesn’t depend on N, the computational cost here is a constant.\n    - Secondly, each arm simulates a virtual process.  As the computation required for each simulation doesn’t scale with N, the overall computational cost here is linear in N.\n    - Lastly, in each time step, FTVA selects $\\alpha N$ arms from a subset of arms to determine the real actions.  The computational cost for this selection process scales linearly with N.\n    \n    Combining these components, we can see that the computational cost of FTVA is linear in N.\n    \n> Figure 1 missing one label.\n\nWe believe that the reviewer refers to the line below the curve for Whittle Index.  That line is meant to indicate where the award under Whittle Index converges to as N becomes large.  We will remove it to avoid confusion."}, {"review_id": "yKqtZa9SLI", "reviewer": "Reviewer_s6TA", "summary": "In the late 80s and early 90s, Whittle formalized the restless multi-armed bandit framework and Weber & Weiss proved that Whittle’s index policy, which solves a relaxed version of the optimization problem, is asymptotically optimal under conditions of indexability. Since then, RMAB problems have attracted much attention for their wide application in diverse areas. This paper contributes a new technique that is not an index policy. Instead, the simulation framework requires a new “synchronization assumption” for the discretized time case. The contributions of this paper are purely theoretical, including a new algorithmic approach (Follow-the-Virtual-Advice) and optimality gap bounds.", "questions": "Are the authors aware of [1]? That paper also claims to contribute a novel new approach for the discrete-time problem. Not only do they consider average-reward, but also any discounted total expected reward in both the finite and infinite horizon case. How does your approach differ? How do your optimality guarantees differ?\n\n[1] Abheek Ghosh, Dheeraj Nagaraj, Manish Jain, and Milind Tambe. 2023. Indexability is Not Enough for Whittle: Improved, Near-Optimal Algorithms for Restless Bandits. In Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems (AAMAS '23). International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 1294–1302.\n", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "This paper introduces an original technique for solving two-action RMAB problems in both discretized and continuous time spaces, and provides bounds on conversion loss and gaps in optimality for both. It is clear that the only assumption that must be enforced in the discrete case is the new “synchronization assumption”. There is a nice discussion about this assumption and when it holds in the appendix for novice readers. The submission appears to be technically sound, and claims are well supported by theoretical analysis.\n", "weaknesses": "After decades of essentially little-to-no change in the state-of-the-art techniques that are deployed in practice, it is wonderful to see new approaches. The authors should be made aware of [1], which aims to address the same problem and also does so in a new, novel way.\n\nI am surprised by the use of “uniform global attractor property” rather than “indexability” throughout the paper. With regards to clarity, I encourage the authors to include more explanations to inform the reader. \n\nThe contributions of this paper are purely theoretical. Open-source code as well as empirical results comparing FTVA against other state-of-the-art implementations would be helpful for the research community.\n\n[1] Abheek Ghosh, Dheeraj Nagaraj, Manish Jain, and Milind Tambe. 2023. Indexability is Not Enough for Whittle: Improved, Near-Optimal Algorithms for Restless Bandits. In Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems (AAMAS '23). International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 1294–1302.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for recognizing our paper’s contribution and strengths, and for the constructive comments. We provide our detailed responses below.\n\n> Relation with Ghosh et al. (AAMAS 23).\n    \nWe thank the reviewer for pointing out this related work. We address this point in detail in our **global rebuttal**. We provide a brief summary here: Our work differs from Ghosh et al. (AAMAS 23) in terms of the problem setting (finite-horizon or discounted-reward in Ghosh et al, and infinite-horizon average-reward in our paper) and the algorithmic approach; moreover, significant challenges arise when one attempts to apply the techniques from Ghosh et al to our setting. We will add this discussion in the revised paper.\n    \n> Uniform global attractor property (UGAP) v.s. indexability\n    \nThanks for raising this point. There is indeed a nuanced distinction between UGAP and indexability, which should be made more explicit in the paper. Indexability is a condition specific to the Whittle Index Policy (WIP), but indexability alone is not enough to guarantee the asymptotic optimality of WIP [WW90]. In contrast, UGAP has been a condition imposed by prior work to prove the asymptotic optimality and bound the optimality gap of both WIP and the LP-Priority policy [WW90, Ver16, GGY20, GGY21]. Given that work on LP-Priority policy [Ver16,GGY22] has removed the reliance on indexability, we believe that UGAP is a more fundamental condition to existing policies. Therefore, we have focused on breaking UGAP. \n\nWe acknowledge the need for clearer differentiation between UGAP and Indexability, and we will include this explanation in our revision for better clarity.\n    \n> Open-source code and empirical results\n    \nThanks for this suggestion. We will make our source code and the empirical results available on GitHub. Our source code includes implementations of our proposed policy FTVA and two state-of-the-art policies, the Whittle Index Policy and LP-Priority policy."}, {"review_id": "3Q4bBFC8pN", "reviewer": "Reviewer_S8QK", "summary": "This paper presents an algorithm providing an asymptotically optimal policy to solve restless bandits with N arms when N goes to infinity without using classical assumptions on the expected deterministic dynamics (uniform global attractor).\n", "questions": "1. Can you change the initial conditions of the numerical experiments to make a fairer comparisons with existing solutions.\n\n2. Provide answers to the weak points listed above.", "limitations": "I did not see any limitations.\n", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "\n\n1. The idea to couple the actual trajectory under the relaxed policy with a virtual one, sampled independently for each bandit is a very nice idea.\n\n2. Removing the UGAP assumption is also a strong point, although this is not the only paper going in this direction (see for example Zhang X, Frazier PI (2022) Near-optimality for infinite-horizon restless bandits with many arms. arXiv preprint arXiv:2203.15853).\n\n\n3. The paper makes a good literature review and a good  use of previous work in this domain.", "weaknesses": "1. The discussion on the synchronization assumption, and especially the sufficient conditions could be made more precise. The link with UGAP is also missing.\nAlso there is a gap between the synchronization of each arm with the synchronization of the whole bandit (see for example the PhD thesis of Kimang Khun). \n\n2. The fact the algorithm is based on independent sampling of each arm makes the \\sqrt{N} bound tight, wuth little hope for improvement, while other approaches based on the fluid dynamics could still work with UGAP (using Cezaro averaging for example) with a higher chance to have a better convergence rate.\n\n3. The comparison with previous algorithms is a little unfair, especially because of initial conditions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for recognizing the strengths and contribution of our paper. Below we provide our responses to the comments.\n\n> Discussion on the synchronization assumption and its link with UGAP\n\nIn our rebuttal to Reviewer JXov, we give a detailed discussion on SA and UGAP. We repeat it here for ease of reference. This contrast is in the discrete-time, infinite-horizon, average-reward setting, given that we remove UGAP without assuming SA in the continuous-time setting. We’re open to more concrete feedback on improving the discussion.\n    \n1. **There exist problem instances where SA holds but UGAP doesn’t.**  \nOne limitation of our work is indeed that it is unclear whether SA subsumes UGAP (recognized in lines 61-62). However, there exist problem instances where SA holds but UGAP doesn’t. Two such examples are given in our paper (illustrated in Figures 1 and 2), where the first example is borrowed from [GGY20]. There are more examples provided in [GGY20] that do not satisfy UGAP. One can easily see that these examples satisfy SA: all entries in the two transition matrices are positive, so two arms starting from any pair of initial states have a positive probability of synchronizing in one step (a formal argument is given in Proposition 2 in Appendix A). For these examples, FTVA achieves an $O(1/\\sqrt{N})$ optimality gap, whereas previously, no policy was known to be asymptotically optimal. Another perspective to view this comparison is that SA uncovers the feasibility of achieving asymptotic optimality for more problems.  \n\n    Another possibly helpful comparison is the following. For any problem instance, we can make it satisfy SA by perturbing entries of its transition kernels by an arbitrarily small amount such that all the entries are strictly positive. This implies that the set of problem instances that satisfy SA is dense in the problem space. In contrast, UGAP assumes the existence of a global attractor. It can be shown that the set of instances that do not satisfy UGAP contains open sets.\n        \n2. **SA is easier to verify.**  \n\n    It has been acknowledged in many prior papers that UGAP is tricky to verify. It lacks intuitive sufficient conditions. UGAP has been assessed through numerical experiments where one simulates the mean-field ODE with randomly generated initial states. But since not all initial states are can be covered, this method can confirm *violations* of UGAP rather than compliances.\n        \n    In contrast, SA can be efficiently verified in several ways. By definition, SA is a hitting time for the finite-state Markov chain $(S(t), \\widehat{S}(t))$ (eq. (10)) to reach the subset of states $\\lbrace (s,\\hat{s})\\colon s=\\hat{s} \\rbrace$. Therefore, SA can be efficiently verified using path-finding graph algorithms on the state transition diagram of the Markov chain. Additionally, we provide several intuitive sufficient conditions for SA in Appendix A, which can also be efficiently verified by identifying self-loops and cycles.\n\n> Synchronization of each arm vs synchronization of the whole bandit\n\nWe unfortunately didn’t find any reference to this distinction in the PhD thesis of Kimang Khun. We would like to invite the reviewer to further elaborate on this point so we can have an opportunity to respond further. Our synchronization assumption is made in the context of a single arm.\n\n> Hope for improving upon the $\\sqrt{N}$ convergence rate\n\nWe've also been contemplating this very point raised by the reviewer. Indeed, the independent sampling is subject to an error of $\\Theta(\\sqrt{N})$ due to the central limit theorem. But it provides a way to break UGAP. A fluid-based policy can achieve an exponential convergence rate, but it relies on UGAP to converge to a neighborhood of the optimal point. It might be possible to design a hybrid policy that uses a sampling-based policy for its global convergence benefit, and switches to a fluid-based policy around the optimal point for a faster convergence rate.\n\n> Better comparison with previous algorithms\n\nWe thank the reviewer for raising this point. We have rerun the experiments demonstrated in Figure 1 and Figure 2 in our paper, and we illustrate the results in Figure R1(a) and Figure R1(b) in the pdf file attached to the global rebuttal. In each experiment, we perform 20 sets of simulations. For each set of simulation, we generate initial states in the following way.\n\n- We first choose a probability distribution on the state space $\\mathbb{S}$ from all the possible probability distributions on $\\mathbb{S}$ uniformly at random. Let $\\pi(s)$ denote the probability of state s under the chosen distribution. This distribution is chosen independently across the 20 sets of simulations.\n\n- For each N-armed bandit, we set the initial state such that $N\\cdot\\pi(s)$ arms are in state s for each s, with a proper rounding.\n\n- For each N-armed bandit, we run all the policies with this initial state.\n\nWe illustrate the results of the 20 sets of simulations in the figure in the following way. For the FTVA policy, for each N, we take the minimum average reward over the 20 sets of simulations, and plot them in the figure. For other policies, for each N, we take the maximum average reward over the 20 sets of simulations. We can see that the min curve for FTVA still approaches the optimal value as N increases, whereas the max curves for other policies are strictly separated from the optimal value."}, {"review_id": "x0IPh6ZWSX", "reviewer": "Reviewer_TTwr", "summary": "This paper studies the infinite-horizon restless bandits problem and proposed a simulation-based framework, i.e., Follow-the-Virtual-Advice, to leverage single armed policy to solve a multi-armed problem, which gets rid of the difficult-to-verify condition, i.e., the uniform global attractor property. Removing this pre-condition is a significant improvement for RMABs. ", "questions": "See comments in Weaknesses. ", "limitations": "no negative societal impact. ", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "This paper studies the infinite-horizon restless bandits problem and proposed a simulation-based framework, i.e., Follow-the-Virtual-Advice, to leverage single armed policy to solve a multi-armed problem, which gets rid of the difficult-to-verify condition, i.e., the uniform global attractor property. Removing this pre-condition is a significant improvement for RMABs. ", "weaknesses": "1. The arguments on FTVA in Section 3.3 look to be a bit hands-waving since there is no clear evidence to support their claims. Based on the reviewer’s understandings, those arguments are possibly wrong.  For example, in lines 181-184, the authors claim that even if the initial virtual state and real state of an arm are different, they will become identical in finite time by chance under mild assumptions in Section 4.1. However, Assumption 1 relies on the “observation” in lines 233-238, which is not true. All the transitions are stochastic, not deterministic. How could we guarantee that $S(t+1) =\\hat{S}(t+1)$ if $S(t)$ is different with $\\hat{S}(t)$?  If Assumption 1 fails, the argument in lines 183-184 does not hold. The arguments in lines 185-189 are also not true. Even when the virtual process can always satisfy the budget constraint, how do we guarantee that the real process following the virtual actions does not violate the budget constraints. \n\n2. The example in lines 194-215 is also not fully supported by evidence. The single-agent policy defined in eq. (8) is stationary stochastic policy, and agent selects actions according to certain probabilities. What do you mean by the preferred action at each state? Though this particular example may only have one action at each state, there is no preferred action in general. How to guarantee the descriptions in lines 207-209 to be true?  This example shows that the real and virtual process has different state distributions, which contradicts Section 3.3. See comment 1.\n\n3. A very important related work is missing. [Ghosh22] also gets rid of the global attractor assumption and considers a much more challenging setting with heterogeneous arms and multi-actions.  An outstanding limitation of this work is that all arms must be the same. \n\nGhosh, A., Nagaraj, D., Jain, M., & Tambe, M. (2022). Indexability is Not Enough for Whittle: Improved, Near-Optimal Algorithms for Restless Bandits. arXiv preprint arXiv:2211.00112.\n\n4. The references cited in this paper are not precise. For example, as far as the reviewer knows, [Ver16] does not consider the single-armed problem. Hence, the argument in lines 140-141 are not precise.  Another example is in lines 123-124. The reviewer is not aware of the meaning of these sentences. How are they related to the RMAB problem in eqs. (1)-(2)?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer’s time and effort put into the review. The reviewer has two main concerns: correctness of our results (Comments 1 and 2), and relationship with prior work by Ghosh et al. (ArXiv 22, AAMAS 23) (Comment 3). Regarding the correctness of our results, we believe that our proofs are rigorous, as explained in detail below. We look forward to further conversation with the reviewer, so that we can have an opportunity to resolve any remained confusion and answer additional questions. Moreover, we are open to suggestions that may improve the readability of our arguments. Regarding the relation with [Ghosh23] and a related comment on the homogeneous arms in our paper, we respond to these points in the **global rebuttal**.\n\n> Comment 1: Arguments on FTVA in Section 3.3.\n\nFirstly, we’d like to clarify that Section 3.3 is meant to provide insights and intuitions for FTVA. Rigorous proofs are provided in appendices. Building on that, we strive for making the presentation as informative and helpful as possible. Below we respond to specific concerns from the reviewer.\n\n- > Lines 181-184 and Assumption 1 in lines 233-238\n\n    We’d like to first clarify that lines 233-238 describe how we *define* the leader-and-follower system, rather than representing an observation. Next we’d like to better explain this system. As the reviewer noted, when $S(t) \\neq \\widehat{S}(t)$, it is possible that $S(t+1)\\neq\\widehat{S}(t+1)$ since they’re sampled independently and there’s randomness in the transitions. However, Assumption 1 does not require the real state and virtual state of an arm to become identical in just a single time step. The time duration needed for them to become identical again is random, and Assumption 1 only requires this random time duration to have a finite expectation. To make Assumption 1 easier to grasp, we have provided several sufficient conditions in Appendix A that are more intuitive and easier to verify.\n\n- > Even when the virtual process can always satisfy the budget constraint, how do we guarantee that the real process following the virtual actions does not violate the budget constraints.\n\n    By the design of FTVA (Algorithm 1), when the virtual actions satisfy the budget constraint at a time step t, the real actions will be identical to the virtual actions, thus satisfying the budget constraint as well. Even when the virtual actions do not satisfy the budget constraint, the real actions still always satisfy the budget constraint. This is guaranteed by lines 3-7 in the pseudocode of Algorithm 1. For the real actions, we apply action 1 to arms in the set $\\mathcal{A}$, which is a set of cardinality $\\alpha N$ (the budget).\n        \n> Comment 2: Example in lines 194-215.\n- > Preferred action\n\n    We apologize for the potential confusion caused by our wording \"preferred action\". In this example, each state has two possible actions, 1 and 0 (as in any restless bandit problem). We call action 1 the \"preferred action\" for states 0, 1, 2, 3; we call action 0 the \"preferred action\" for states 4, 5, 6, 7. We chose this naming since in this example, the optimal single-armed policy is to apply action 1 for states 0, 1, 2, 3, and apply action 0 for states 4, 5, 6, 7. (In the N-armed system, some arms may not be able to actually apply their preferred actions due to the budget constraint.) We will make sure to clarify this in the revision.\n        \n- > Lines 207-209\n\n    Lines 207-209 follow from the optimal solution of the LP in (5)-(7) and the induced optimal policy in (8). Under this optimal policy, one can verify that the state distribution in steady-state is uniform on $\\mathbb{S}$. Also note that the virtual processes are independent. Therefore, by law of large numbers, roughly N/2 arms have virtual states in the set $\\{4,5,6,7\\}$.\n        \n- > State distributions of real and virtual processes\n\n    Although the initial state distributions of the real and virtual processes are different, the state distributions will become the same in *steady state,* where the steady-state probability of being in each state is equal to the long-run fraction of time spent in that state.\n        \n> Comment 3: Relation with [Ghosh23] and assumption of homogeneous arms.\n\nWe thank the reviewer for bringing up this related work and the homogeneity assumption. We address these two important points in detail in our **global rebuttal**. For immediate reference, we provide a brief summary here: (1) Our work differs from [Ghosh23] in terms of problem setting (finite-horizon or discounted-reward in [Ghosh23], infinite-horizon average-reward in our paper) and algorithmic approach; moreover, significant challenges arise when one attempts to apply techniques from [Ghosh23] to our setting. (2) Our paper focuses on breaking the UGAP assumption for the infinite-horizon average-reward setting, which is challenging even with homogeneous arms. That said, our approach and results can be directly generalized to accommodate heterogeneous arms in a wide range of settings.\n\n> Comment 4: Single-armed problem in lines 140-141.\n\nAlthough some prior work may not use the term \"single-armed problem\", *equivalent* forms of this problem are used. In [Ver16], the LP in (4)-(7) can be viewed as a single-armed problem since there is a standard way to construct an optimal policy from the solution (see, e.g., Chapters 8.8 & 8.9 in [Put05]). The construction process is similar to our equation (8). We will make this connection between the LP and the single-armed problem more explicit in our revision.\n\n> Comment 4: Lines 123-124.\n\nThe RMAB problem in equations (1)-(2) is a finite-state MDP. As stated in lines 123-124, it is generally accepted that for finite-state MDPs, it suffices to consider Markovian stationary policies. This result is widely referenced; a proof can be found in, e.g., Chapter 5.5 of [Put05]. We included this point in our paper to make it clear that our approach deviates from some traditional approaches."}]

Author rebuttal:
We thank all the reviewers for their time and effort. In this global rebuttal, we address two points each raised by multiple reviewers. Our responses to each reviewer are provided in the individual rebuttals.

## Comparison with prior work by Ghosh et al. (@Reviewers s6TA, S8QK, TTwr)
We thank Reviewers s6TA and TTwr for pointing us to recent work by Ghosh et al. (ArXiv 2022, AAMAS 2023), referred to as [Ghosh23] below. We apologize for the omission and will add it as related work in our revision. A quick summary of the comparison between [Ghosh23] and our work is that: the settings differ (finite-horizon or discounted-reward vs infinite-horizon average-reward), the algorithmic approaches differ, and a crucial obstacle emerges if one tries to apply the techniques in [Ghosh23] to our setting. Below we elaborate on this comparison; comparison with some other prior work on finite-horizon/discounted-reward [ZF21, ZF22] is also mentioned along the way. 

### – Settings
[Ghosh23] focuses on the finite-horizon setting and the infinite-horizon discounted-reward setting, while our work considers the infinite-horizon average-reward setting.
 
### – Approaches
- While linear programs (LPs) are used in policy design in both the finite-horizon/discounted-reward setting (including [Ghosh23], [ZF21] and [ZF22]) and the infinite-horizon average-reward setting (including our work), the LPs utilized differ substantially. In the finite-horizon/discounted-reward setting, the LP optimizes the future trajectory for a predetermined number of time steps, hence the number of optimization variables scales linearly with the time steps. In contrast, in the infinite-horizon average-reward setting, the LP solves for the optimal state-action frequency in steady state, effectively removing any consideration of the number of time steps.
- [Ghosh23] directly takes actions according to the LP solution, while we simulate a virtual process and generate actions using the virtual process. We reiterate that the virtual process is a novel approach that plays a crucial role in breaking the UGAP assumption.

### – Obstacle
In general, the infinite-horizon average-reward setting faces difficulties due to the long-term effect of actions, whereas the finite-horizon and discounted-reward settings have bounded (effective) horizons. Standard results on MDPs show that one can use the discounted reward to approximate the infinite-horizon average reward by dividing the former by the effective horizon $1/(1-\gamma)$ and letting $\gamma\to 1$. Therefore, for an optimality gap bound in the discounted-reward setting to be useful for average reward, it should have at most linear dependence on $1/(1-\gamma)$. However, the bound in Theorem 3 of [Ghosh23] has a *quadratic* dependency on $1/(1-\gamma)$. In the finite-horizon setting, the bound on the additive optimality gap in Theorem 2 of [Ghosh23] also has a *quadratic* dependency on the time horizon T.

We believe that new techniques are required to improve the quadratic dependency on  $1/(1-\gamma)$ or T to a linear dependency. Our intuition is that a certain form of fast-mixing property of the system must be utilized. UGAP is one such fast-mixing property that has been assumed for 30 years. Our work takes an alternative approach by utilizing the fast mixing of real and virtual states.

## Assumption of homogeneous arms and extension to heterogeneous arms (@Reviewers TkxD, TTwr)
Reviewers TkxD and TTwr raised concerns on our assumption of homogeneous arms and applicability to settings with heterogeneous arms. We appreciate this point, since we too think that the heterogeneous setting is interesting. Our paper has focused on breaking the UGAP assumption for the infinite-horizon average-reward setting, for which the homogeneous-arm setting is used as an exemplary case. Our approach and results can be directly generalized to accommodate heterogeneous arms as follows.  

Suppose the arms are divided into $K$ types, with $\beta_k N$ arms in each type $k\in\{1,2,\dots,K\}\triangleq[K]$, and each type is associated with an MDP. The transition kernels and reward functions can be different across types. This is similar to the clustering setting in [Ghosh et al., AAMAS 2023]. When $K$ is a constant as $N$ increases, we generalize our approach as follows. The objective of the LP in (5)-(7) now becomes

$\text{maximize}\sum_{k=1}^K\sum_{s,a}\beta_kr_k(s,a)y_k(s,a)$

with variables $\lbrace y_k(s,a)\rbrace_{{k\in [K]},s\in\mathbb{S},a\in\mathbb{A}}$.

The constraint (5) becomes $\sum_{k=1}^K \beta_ky_k(s,1)=\alpha.$

The constraints (6) and (7) now need to hold for each $k$. Then the solution, $y_k(s,a)$, induces an optimal single-armed policy $\pi_k^*$ for an arm of type $k$. To convert from single-armed policies to an $N$-armed policy, FTVA lets each arm of type $k$ independently simulate a virtual single-armed process following $\pi_k^*$. Lines 3-14 of Algorithm 1 stay the same.

For this heterogenous setting, assuming the Synchronization Assumption for each arm type, the optimality gap remains $O(1/\sqrt{N})$, with the hidden constant depending on $K$. Except for the adaptation to incorporate multiple arm types, the proof structures are almost the same, with only minor changes needed. We will include this generalization in the appendix in our revision.

We acknowledge that in the setting where $K$ scales with $N$, or with multi-actions, more significant adaptations might be required. Nonetheless, we believe that our ideas of simulation-based policy design and prioritizing constraint satisfaction remain valid, and it is plausible that our FTVA approach will still be applicable.

Meta-review: This paper studies a key scalability bottleneck in multi-armed bandit problems with discrete but countably large number of actions, and identifies a way to reduce solving such problems to a scalable subset through an algorithm called Follow-the-Virtual-Advice. Performance bounds quantify the gap between the reduction and the original problem in terms of regret. During the discussion period, the authors addressed the majority of the reviewer concerns, and came to the conclusion that this work contributes an important development to the theory of multi-armed bandits. I recommend it be accepted.
Decision: Accept (spotlight)