1 Introduction↩︎

The restless bandit (RB) problem is a dynamic decision-making problem that involves a number of Markov decision processes (MDPs) coupled by a constraint. Each MDP, referred to as an arm, has a binary action space, \(\{\text{passive, active}\}\). At every decision epoch, the decision maker is constrained to select a fixed number of arms to activate, with the goal of maximizing the expected reward accrued. The RB problem finds applications across a spectrum of domains, including wireless communication [1], congestion control [2], queueing models [3], crawling web content [4], machine maintenance [5], clinical trials [6], to name a few.

In this paper, we focus on infinite-horizon RBs with the average-reward criterion. Since the exact optimal policy is PSPACE-hard to compute [7], it is of great theoretical and practical interest to 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\to\infty\).

1.0.0.1 Prior work and the uniform global attractor property assumption.

Prior work has studied the celebrated Whittle index policy [8] and LP-Priority policies [9] and established sufficient conditions for their asymptotic optimality [9]–[12]. One key assumption underpinning all prior work is the uniform global attractor property (UGAP)—also known as globally asymptotic stability—which pertains to the mean-field/fluid limit of the restless bandit system in the asymptotic limit \(N\to\infty\). UGAP stipulates that the system’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 a highly technical assumption and challenging to verify: the primary way to test UGAP is numerical simulations; see [11] for a detailed discussion.

More recent work studies the rate at which the optimality gap converges to zero. The work [11] and [12] prove a striking \(O(\exp(-cN))\) optimality gap for the Whittle index policy and LP-Priority policies, respectively, where \(c\) is a constant. In addition to UGAP, these results require a non-singularity or non-degenerate condition. We are not aware of any rate of convergence result without assuming UGAP or non-singularity/degeneracy. See Table 1 for a 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 a non-trivial convergence rate for the optimality gap in the absence of the non-singular/non-degenerate assumption (and UGAP)?

1.0.0.2 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-the-Virtual-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 a policy with an \(O(1/\sqrt{N})\) optimality gap, under the conditions summarized in Table 1, which we elaborate on 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 8 for more details).

Our results can also be extended to RBs with heterogeneous arms. See Appendix 14 for details.

We now elaborate on the conditions in Table 1. In the discrete-time setting, our result holds under a condition called the Synchronization Assumption(SA), in addition to the standard unichain assumption required by all prior work. The SA condition, which is imposed on the MDP associated with a single arm, admits several intuitive sufficient conditions. While it is unclear whether SA subsumes UGAP, we show that there exist problem instances that violate UGAP but satisfy SA. Figure 1 shows one such instance (constructed by [11], described in Appendix 13 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(\({\bar{\pi}}^*\)), is asymptotically optimal. In addition, our \(O(1/\sqrt{N})\) bound on the optimality gap does not require a non-singularity/non-degeneracy assumption.

More notably, in the continuous-time setting, we completely eliminate the UGAP assumption. We show that our policy FTVA-CT(\({\bar{\pi}}^*\)) achieves an \(O(1/\sqrt{N})\) 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 [9], [12]. Our policy, FTVA(\({\bar{\pi}}^*\)), 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.

1.0.0.3 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 a 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 a simulated system, which is 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 [13], which also involves a simulated system, but for a stochastic bin-packing problem.

1.0.0.4 Other related work.

Another condition extensively discussed in the RB literature is the indexability condition [8], which is necessary for the Whittle index policy to be well-defined, but not required by LP-Priority policies [9]. 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/\sqrt{N})\) optimality gap [14]–[17], and an \(O(\exp(-cN))\) gap assuming non-degeneracy [12], [18]. For the infinite-horizon discounted reward setting, [17], [19] propose policies with \(O(1/\sqrt{N})\) optimality gap without assuming indexability and UGAP. While these results are not directly comparable to ours, it is of future interest to see if our simulation-based framework can be applied to their settings. For a more detailed discussion of prior work, see Appendix 7.

1.0.0.5 Paper Organization.

While our continuous-time result is stronger, the discrete-time setting is more accessible. Therefore, we first discuss the discrete-time setting, which includes the problem statement in Section 2, our proposed framework, Follow-the-Virtual-Advice, 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 infinite-horizon, discrete-time restless bandit problem with \(N\) arms indexed by \([N] \triangleq \{1,2,\dots,N\}\). Each arm is associated with an MDP described by the tuple \((\mathbb{S}, \mathbb{A}, P, r)\). Here \(\mathbb{S}\) is the state space, assumed to be finite; \(\mathbb{A}= \{0, 1\}\) is the action set, and we say the arm is activated or pulled when action \(1\) is applied; \(P:\mathbb{S}\times\mathbb{A}\times\mathbb{S}\to [0,1]\) is the transition kernel, where \(P(s,a,s')\) is the probability of transitioning from state \(s\) to state \(s'\) upon taking action \(a\); \(r = \{r(s, a)\}_{s\in\mathbb{S}, a\in\mathbb{A}}\) is the reward function, where \(r(s,a)\) is the reward for taking action \(a\) in state \(s\). Throughout the paper, we assume that the transition kernel \(P\) is unichain [20]; that is, under any Markov policy for this single-armed MDP \((\mathbb{S}, \mathbb{A}, P, r)\), the induced Markov chain has a single recurrent class. The unichain assumption is standard in most existing work on restless bandits [9]–[12]. We will discuss relaxing the unichain assumption in Appendix 10.

In the above setting, we are subject to a budget constraint that exactly \(\alpha N\) arms must be activated in each time step, where \(\alpha\in(0,1)\) is a given constant and \(\alpha N\) is assumed to be an integer for simplicity. This \(N\)-armed RB problem can be represented by the tuple \((N, \mathbb{S}^N, \mathbb{A}^N, P, r, \alpha N)\).

A policy \(\pi\) for the \(N\)-armed problem specifies the action for each of the \(N\) arms based on the history of states and actions. Under policy \(\pi\), let \(S_i^\pi(t) \in \mathbb{S}\) denote the state of the \(i\)th arm at time \(t\), and we call \(\boldsymbol{S}^\pi(t) \triangleq (S_i^\pi(t))_{i\in[N]} \in \mathbb{S}^N\) the system state. Similarly, let \(A_i^\pi(t) \in \mathbb{A}\) denote the action applied to the \(i\)th arm at time \(t\), and let \(\boldsymbol{A}^\pi(t) \triangleq (A_i^\pi(t))_{i\in[N]} \in \mathbb{A}^N\) 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: \[\begin{align} \tag{1} \underset{\text{policy } \pi}{\text{maximize}} & \quad V^\pi_N \triangleq \lim_{T\to\infty } \frac{1}{T} \sum_{t=0}^{T-1} \frac{1}{N} \sum_{i=1}^N\mathbb{E}\left[r(S_i^\pi(t), A_i^\pi(t))\right]\\ \text{subject to} &\quad \sum_{i=1}^N A_i^\pi(t) = \alpha N,\quad \forall t\ge 0. \tag{2} \end{align}\] Under the unichain assumption, the value \(V_N^\pi\) of any policy \(\pi\) is independent of the initial state. Let \(V^*_N \triangleq \sup_{\pi} V_N^\pi\) denote the optimal value. The optimality gap of \(\pi\) is defined as \(V^*_N - V^\pi_N\). We say a policy \(\pi\) is asymptotically optimal if its optimality gap converges to \(0\) as \(N\to\infty\).

Classical theory guarantees that for a finite-state Markov decision process like an RB, there exists an optimal policy that is Markovian and stationary [20]. Nevertheless, the policies we propose are not Markovian policies; rather, they have internal states. Under such a policy \(\pi\), the system state \(\boldsymbol{S}^\pi(t)\) together with the internal state form a Markov chain, and the action \(\boldsymbol{A}^{\pi}(t)\) depends on both the system and internal states. We design a policy such that this Markov chain has a stationary distribution. Let \(\boldsymbol{S}^\pi(\infty)\) and \(\boldsymbol{A}^\pi(\infty)\) denote the random elements that follow the stationary distributions of \(\boldsymbol{S}^\pi(t)\) and \(\boldsymbol{A}^\pi(t)\), respectively. Then the average reward of \(\pi\) is equal to \(V^\pi_N=\frac{1}{N} \sum_{i=1}^N\mathbb{E}\left[r(S_i^\pi(\infty), A_i^\pi(\infty))\right]\).

In later sections, when the context is clear, we drop the superscript \(\pi\) from \(S_i^\pi\) and \(A_i^\pi\).

3 Follow-the-Virtual-Advice: A simulation-based framework↩︎

In this section, we present our framework, Follow-the-Virtual-Advice(FTVA). We first describe a single-armed problem, which involves an “average arm” from the original \(N\)-armed problem. We then use the optimal single-armed policy to construct the proposed policy FTVA(\({\bar{\pi}}^*\)).

3.1 Single-armed problem↩︎

The single-armed problem involves the MDP \((\mathbb{S}, \mathbb{A}, P, r)\) associated with a single arm (say arm \(1\) without loss of generality), where the budget is satisfied on average. Formally, consider the problem: \[\begin{align} \tag{3} \underset{\text{policy } {\bar{\pi}}}{\text{maximize}} & \quad V^{\bar{\pi}}_1 \triangleq \lim_{T\to\infty } \frac{1}{T} \sum_{t=0}^{T-1} \mathbb{E}\left[r(S_1^{\bar{\pi}}(t), A_1^{\bar{\pi}}(t))\right]\\ \text{subject to} &\quad \lim_{T\to\infty} \frac{1}{T} \sum_{t=0}^{T-1} \mathbb{E}\left[A_1^{\bar{\pi}}(t)\right] = \alpha. \tag{4} \end{align}\] The constraint 4 stipulates that the average rate of applying the active action must equal \(\alpha\). Various equivalent forms of this single-armed problem have been considered in prior work [9]–[12].

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\): \[\begin{align} \tag{5}\underset{\{y(s, a)\}_{s\in\mathbb{S},a\in\mathbb{A}}}{\text{maximize}} \mspace{12mu}&\sum_{s\in\mathbb{S},a\in\mathbb{A}} r(s, a) y(s, a) \\ \text{subject to}\mspace{25mu} &\mspace{15mu}\sum_{s\in\mathbb{S}} y(s, 1) = \alpha \tag{6}\\ & \sum_{s'\in\mathbb{S}, a\in\mathbb{A}} y(s', a) P(s', a, s) = \sum_{a\in\mathbb{A}} y(s,a), \; \forall s\in\mathbb{S}\tag{7}\\ &\mspace{3mu}\sum_{s\in\mathbb{S}, a\in\mathbb{A}} y(s,a) = 1, \quad y(s,a) \geq 0, \; \forall s\in\mathbb{S}, a\in\mathbb{A}. \tag{8} \end{align}\] Here 6 corresponds to the relaxed budget constraint, 7 is the flow balance equation, and 7 –8 guarantee that \(y(s,a)\)’s are valid steady-state probabilities.

By standard results for average reward MDPs [20], an optimal solution \(\{y^*(s, a)\}_{s\in\mathbb{S},a\in\mathbb{A}}\) to 5 induces an optimal policy \({\bar{\pi}}^*\) for the single-armed problem via the following formula: \[\label{eq:single-arm-opt-def} {\bar{\pi}}^*(a | s) = \begin{cases} y^*(s, a) / (y^*(s, 0) + y^*(s,1)), & \text{if } y^*(s, 0) + y^*(s,1) > 0, \\ 1/2, & \text{if } y^*(s, 0) + y^*(s,1) = 0. \end{cases} \quad \text{for s\in\mathbb{S}, a\in\mathbb{A}.}\tag{9}\] Let \(V_1^\mathrm{rel}=V_1^{{\bar{\pi}}^*}\) be the optimal value of 5 and the single-armed problem.

5 can be viewed as a relaxation of the \(N\)-armed problem. To see this, take any \(N\)-armed policy \(\pi\) and set \(y(s,a)\) to be the fraction of arms in state \(s\) taking action \(a\) in steady state under \(\pi\), i.e., \(y(s,a)=\mathbb{E}\big[\frac{1}{N}\sum_{i=1}^N\mathbb{1}_{\{S_i^{\pi}(\infty)=s,A_i^{\pi}(\infty)=a\}}\big]\). Whevener \(\pi\) satisfies the budget constraint 2 , \(\{y(s,a)\}\) satisfies the relaxed constraint 6 and the consistency constraints 7 –8 . Therefore, the optimal value of 5 is an upper bound of the optimal value of the \(N\)-armed problem: \(V^\mathrm{rel}_1 \ge V^*_N\).

3.2 Constructing the \(N\)-armed policy↩︎

We now present Follow-the-Virtual-Advice, a simulation-based framework for the \(N\)-armed problem. FTVAtakes as input any single-armed policy \({\bar{\pi}}\) that satisfies the relaxed budget constraint 4 and converts it into a \(N\)-armed policy, denoted by FTVA(\({\bar{\pi}}\)). Of particular interest is when \({\bar{\pi}}\) is an optimal single-armed policy, which leads to our result on the optimality gap. Below we introduce the general framework of FTVAwithout imposing any restriction on the input policy \({\bar{\pi}}.\)

The proposed policy FTVA(\({\bar{\pi}}\)) has two main components:

• Virtual single-armed processes. Each arm \(i\) simulates a virtual single-armed process, whose state is denoted as \(\widehat{S}_i(t)\), with action \(\widehat{A}_i(t)\) chosen according to \({\bar{\pi}}\). To make the distinction conspicuous, we sometimes refer to the state \(S_i(t)\) and action \(A_i(t)\) in the original \(N\)-armed problem as the real state/action. The virtual processes associated with different arms are independent.

• Follow the virtual actions. At each time step \(t\), we choose the real actions \(A_i(t)\)’s to best match the virtual actions \(\widehat{A}_i(t)\)’s, to the extent allowed by the budget constraint \(\sum_{i=1}^NA_i(t)=\alpha N\).

FTVAis presented in detail in Algorithm 2. Note that we use an appropriate coupling in Algorithm 2 to ensure that the virtual processes \((\widehat{S}_i(t),\widehat{A}_i(t))\)’s are independent and each follows the Markov chain induced by the single-armed policy \({\bar{\pi}}\). FTVA is designed to steer the real states to be close to the virtual states, thereby ensuring a small conversion loss \(V_1^{{\bar{\pi}}}-V_N^{\mathrm{\texttt{FTVA}}({\bar{\pi}})}\). Here recall that \(V_1^{{\bar{\pi}}}\) is the average reward achieved by the input policy \({\bar{\pi}}\) in the single-armed problem, and that \(V_N^{\mathrm{\texttt{FTVA}}({\bar{\pi}})}\) is the average reward per arm achieved by policy FTVA(\({\bar{\pi}}\)) 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 \({\bar{\pi}}^*\) to each arm’s real state. We note that existing policies are essentially real-state-based, 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 in the absence of the budget constraint. In particular, even if the initial virtual state and real state of an arm \(i\) 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 were no constraint, each arm \(i\) will consistently follow the virtual actions, i.e., \(A_i(t) = \widehat{A}_i(t) = {\bar{\pi}}\big(\widehat{S}_i(t)\big)\) for all \(t\), and the virtual states will remain identical to real states.

In the presence of the budget constraint, the arms may not remain synchronized, so the virtual processes become crucial: they guarantee that the virtual actions \(\widehat{A}_i(t) = {\bar{\pi}}\big(\widehat{S}_i(t)\big)\) nearly satisfy budget constraint, which allows the real system to approximately follow the virtual actions to remain synchronized. To see this, note that regardless of the current real states, the \(N\) virtual states \(\widehat{S}_1,\ldots, \widehat{S}_N\) independently follow the single-armed policy \({\bar{\pi}}^*\), so, in the long run, each \((\widehat{S}_i(\infty), \widehat{A}_i(\infty))\) is distributed per \(y^*(\cdot, \cdot)\), the optimal solution to 5 . For large \(N\), the sum \(\sum_{i=1}^N\widehat{A}_i(\infty)\) concentrates around its expectation \(N \sum_{s\in\mathbb{S}} y^*(s,1) = \alpha N\) and thus tightly satisfy the budget constraint. In contrast, the actions generated by applying \({\bar{\pi}}\) to the real states are likely to significantly violate the constraint, especially when the empirical distribution of the current real states deviates from \(y^*(\cdot, \cdot)\).

An example.   We provide a concrete example illustrating the above arguments. Suppose the state space for each arm is \(\mathbb{S}=\{0,1,\ldots,7\}\). We label action \(1\) as the preferred action for states \(0, 1, 2, 3\), and action \(0\) for the other states. For an arm in state \(s\), applying the preferred action moves the arm to state \((s+1) \bmod 8\) with probability \(p_{s,\text{R}}\), and applying the other action moves the arm to state \((s-1)^+\) with probability \(p_{s,\text{L}}\); the arm stays at state \(s\) otherwise. One unit of reward is generated when the arm goes from state \(7\) to state \(0\). We assume that the budget is \(N/2\) and set \(\{p_{s,\text{R}},p_{s,\text{L}}\}\) such that the optimal solution of 5 is \(y^*(s,1) = 1/ 8\) for \(s=0,1,2,3\) and \(y^*(s,0)=1 / 8\) for \(s=4,5,6,7\). That is, the optimal state distribution is uniform\((\mathbb{S})\), and the optimal single-armed policy \({\bar{\pi}}^*\) always takes the preferred action so as to traverse state \(7\) as often as possible.

To see why this MDP makes the corresponding \(N\)-armed system tricky to control, consider the situation where \(p_{s,\text{L}} >> p_{s,\text{R}}\) and most arms are in state \(0\). Those arms prefer actions \(1\) to move towards state \(7\). However, there are only \(N/2\) units of budget. If we break ties uniformly at random, each arm is not pulled with probability \(1/2\) in each time slot and is likely to return to \(0\) before they leave \(\{0,1,2,3\}\). This phenomenon can be seen from Figure 9 (b) in Appendix 13.

A similar phenomenon can be observed for LP-Priority policies. Here we consider an LP-Priority in [12], [14], [16] that breaks ties based on the Lagrangian-optimal index. In Figure 3, we generate and visualize a sample path under LP-Priority from time \(250\) to \(289\), and contrast it with the sample path if the system switches to \(\mathrm{\texttt{FTVA}}({\bar{\pi}}^*)\) from time \(250\) onwards. We can see that under LP-Priority, although the arms have a strong tendency to move up from state \(4\) to state \(5\), they move back when they reach state \(5\) and thus get stuck at state \(4\). In contrast, when switching to \(\mathrm{\texttt{FTVA}}({\bar{\pi}}^*)\), the arrows gradually change to the correct direction, which helps the arms to escape from state \(4\) and converge to the uniform distribution over the state space. Intuitively, under \(\mathrm{\texttt{FTVA}}({\bar{\pi}}^*)\), an 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 13.4, we include more visualizations of the policies.

In Figure 4, we compare the average reward of \(\mathrm{\texttt{FTVA}}({\bar{\pi}}^*)\) with those of the random tie-breaking policy and the LP-Priority policy discussed above. We can see that \(\mathrm{\texttt{FTVA}}({\bar{\pi}}^*)\) is near-optimal, while the other two policies have nearly zero rewards. Further details are provided in Appendix 13. Note that while a different tie-breaking rule may solve this particular example with real states, currently there is no known rule that works in general.

4 Theoretical result on optimality gap↩︎

In this section, we present our main theoretical result, an upper bound on the conversion loss \(V_1^{{\bar{\pi}}}-V_N^{\mathrm{\texttt{FTVA}}({\bar{\pi}})}\) for any given single-armed policy \({\bar{\pi}}\). Setting \({\bar{\pi}}\) to be an optimal single-armed policy \({\bar{\pi}}^*\) then leads to an upper bound on the optimality gap of our N-armed policy \(\mathrm{\texttt{FTVA}}({\bar{\pi}}^*)\). Our result holds under the Synchronization Assumption(SA), which we formally introduce below.

4.1 Synchronization Assumption↩︎

SA is imposed on a given single-armed policy \({\bar{\pi}}\). To describe SA, we first define a two-armed system called the leader-and-follower system, which consists of a leader arm and a follower arm. Each arm is associated with the MDP \((\mathbb{S}, \mathbb{A}, P, r)\). At each time step \(t\ge 1\), the leader arm is in state \(\widehat{S}(t)\) and uses the policy \({\bar{\pi}}\) to chooses an action \(\widehat{A}(t)\) based on \(\widehat{S}(t)\); the follower arm is in state \(S(t)\), and it takes the action \(A(t)=\widehat{A}(t)\) regardless of \(S(t)\). The state transitions of the two arms are coupled as follows. If \(S(t)=\widehat{S}(t)\), then \(S(t+1)=\widehat{S}(t+1)\). If \(S(t)\neq\widehat{S}(t)\), then \(S(t+1)\) and \(\widehat{S}(t+1)\) are sampled independently from \(P(S(t),A(t),\cdot)\) and \(P(\widehat{S}(t),\widehat{A}(t),\cdot)\), 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), \widehat{S}(0), \widehat{A}(0)) = (s, a, \widehat{s}, \widehat{a}) \in \mathbb{S}\times \mathbb{A}\times \mathbb{S}\times \mathbb{A}\), we define the synchronization time as the first time the two states become identical: \[\label{eq:synctime} \tau^{\mathrm{sync}}(s,a,\widehat{s},\widehat{a}) \triangleq \min\{t\ge 0\colon S(t)=\widehat{S}(t)\}.\tag{10}\]

We view SAas 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 1 and 4. [11] provides more examples that violate UGAP, all of which can be verified to satisfy SA. Second, SAis easier to verify than UGAP. It has been acknowledged in many prior papers that UGAP lacks intuitive sufficient conditions and can only be checked numerically. In contrast, SAcan be efficiently verified in several ways, which is discussed in Appendix 9.

4.2 Bounds on conversion loss and optimality gap↩︎

We are now ready to state our main theorem.

4.2.0.1 Proof sketch.

The proof of Theorem 1 is given in Appendix 11. Here we sketch the main ideas of the proof, whose key step involves bounding the conversion loss \(V^{\bar{\pi}}_1 - V^{\mathrm{\texttt{FTVA}}({\bar{\pi}})}_N\) using a fundamental tool from queueing theory, the Little’s Law [21]. Specifically, we start with the upper bound \[\begin{align} V^{\bar{\pi}}_1 - V^{\mathrm{\texttt{FTVA}}({\bar{\pi}})}_N &= \frac{1}{N} \mathbb{E}\left[\sum_{i=1}^Nr\big(\widehat{S}_i(\infty), \widehat{A}_i(\infty)\big) - \sum_{i=1}^Nr\big(S_i(\infty), A_i(\infty)\big)\right] \nonumber \\ &\leq \frac{2r_{\max}}{N} \mathbb{E}\left[\sum_{i=1}^N\mathbb{1}\!\left\{\big(\widehat{S}_i(\infty), \widehat{A}_i(\infty)\big) \neq \big(S_i(\infty), A_i(\infty)\big)\right\}\right], \label{eq:bound-by-disagreement-number} \end{align}\tag{13}\] which holds since the virtual process \(\big(\widehat{S}_i(t),\widehat{A}_i(t)\big)\) of each arm \(i\) follows the single-armed policy \({\bar{\pi}}\). We say an arm \(i\) is a bad arm at time \(t\) if \(\big(\widehat{S}_i(t), \widehat{A}_i(t)\big) \neq \big(S_i(t), A_i(t)\big)\), and a good arm otherwise. Then \(\mathbb{E}\left[\sum_{i=1}^N\mathbb{1}\!\left\{\big(\widehat{S}_i(\infty), \widehat{A}_i(\infty)\big) \neq \big(S_i(\infty), A_i(\infty)\big)\right\}\right]=\mathbb{E}\big[\text{\# bad arms}\big]\) in steady state.

By Little’s Law, we have the following relationship: \[\begin{align} \mathbb{E}\left[\text{\# bad arms}\right]=\text{(rate of generating bad arms)} \times \mathbb{E}\left[\text{time duration of a bad arm}\right]. \end{align}\] It suffices to bound the two terms on the right hand side. Note that the virtual actions \(\widehat{A}_i(t)\)’s are i.i.d.with mean \(\mathbb{E}[\widehat{A}_i(t)]=\alpha\); a standard concentration inequality shows that at most \(\big|\sum_{i=1}^N\widehat{A}_i(t)-\alpha N\big|\approx O(\sqrt{N})\) bad arms are 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 \(O(1)\) time by virtue of SA.

5 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 we no longer require SA. Detailed proofs are provided in Appendix 12.

5.0.0.1 Problem setup.

The continuous-time restless bandit (CTRB) problem is similar to its discrete-time counterpart (cf. Section 2), except that each single-armed MDP runs in continuous time. In particular, an \(N\)-armed CTRB is given by a tuple \((N, \mathbb{S}^N, \mathbb{A}^N, G, r, \alpha N)\), where \(\mathbb{S}\) is the finite state space and \(\mathbb{A}=\{0,1\}\) is the action space of a single arm. In continuous time, each arms dynamics is governed by the transition rates (rather than probabilities) \(G= \{G(s,a,s')\}_{s,s'\in\mathbb{S}, a\in\mathbb{A}}\), where \(G(s,a,s')\) is the rate of transitioning from state \(s\) to state \(s'\neq s\) 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 \(a\) in state \(s\). The budget constraint now requires that at any moment of time, the total number of arms taking the active action \(1\) is equal to \(\alpha N\).

The objective is again maximizing the long-run average reward, that is, \[\begin{align} \tag{14} \underset{\text{policy } \pi}{\text{maximize}} & \quad V^\pi_N \triangleq \lim_{T\to\infty } \frac{1}{T} \int_0^T \frac{1}{N} \sum_{i=1}^N\mathbb{E}\left[r(S_i^\pi(t), A_i^\pi(t))\right]dt\\ \text{subject to} &\quad \sum_{i=1}^N A_i^\pi(t) = \alpha N \quad \forall t\ge 0. \tag{15} \end{align}\] Let \(V^*_N = \sup_\pi V^\pi_N\) denote the optimal value of the above optimization problem.

5.0.0.2 Single-armed problem.

The single-armed problem for CTRB is defined analogously as its discrete-time counterpart 3 –4 . This single-armed problem can again be written as a linear program, where the decision variable \(y(s,a)\) represents the steady-state probability of being in state \(s\) taking action \(a\): \[\begin{align} \tag{16}\underset{\{y(s, a)\}_{s\in\mathbb{S},a\in\mathbb{A}}}{\text{maximize}} \mspace{12mu}&\sum_{s\in\mathbb{S},a\in\mathbb{A}} r(s, a) y(s, a) \\ \text{subject to}\mspace{25mu} &\mspace{15mu}\sum_{s\in\mathbb{S}} y(s, 1) = \alpha \tag{17}\\ & \sum_{s'\in\mathbb{S}, a\in\mathbb{A}} y(s', a) G(s', a, s) = 0 \quad \forall s\in\mathbb{S}\tag{18}\\ &\mspace{3mu}\sum_{s\in\mathbb{S}, a\in\mathbb{A}} y(s,a) = 1; \quad y(s,a) \geq 0 \;\; \forall s\in\mathbb{S}, a\in\mathbb{A}. \tag{19} \end{align}\] In 18 , we use the convention that \(G(s,a,s)=-G(s,a)\triangleq -\sum_{s'\neq s}G(s,a,s')\). Again, the optimal value of 16 upper bounds the optimal value for the \(N\)-armed problem, i.e., \(V^\mathrm{rel}_1=V^{{\bar{\pi}}^*}_1 \ge V^*_N\), where \({\bar{\pi}}^*\) is any optimal single-armed policy and can be computed using the same formula in 9 . Note that in continuous time, the optimal policy \({\bar{\pi}}^*\) is carried out through uniformization [20].

5.0.0.3 Our policy.

Our framework for the CTRB, Follow-the-Virtual-Advice-CT(FTVA-CT), is presented in Algorithm 5. FTVA-CTworks in a similar fashion as its discrete-time counterpart. It takes a single-armed policy \({\bar{\pi}}\) as input, and each arm \(i\) independently simulates a virtual single-armed process \((\widehat{S}_i(t),\widehat{A}_i(t))\) following \({\bar{\pi}}\). FTVA-CTthen chooses the real actions \(A_i(t)\)’s to match the virtual actions \(\widehat{A}_i(t)\)’s to the extent allowed by the budget constraint \(\sum_{i=1}^NA_i(t)=\alpha N\).

To run FTVA-CT in continuous time for the \(N\)-armed problem, we use the following uniformization to set discrete decision epochs \(\{t_k\}_{k=0,1,\dots}\) for updating the actions and virtual processes. We uniformize at rate \(2Ng_{\max}\) with \(g_{\max}= \max_{s\in\mathbb{S}, a\in\mathbb{A}} 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 a decision epoch either when a real state transitions, or when an independent exponential timer with rate \(2N g_{\max}- \sum_{i=1}^NG(S_i(t), A_i(t))\) ticks.

The definitions of conversion loss, optimality gap, and asymptotic optimality are the same as the discrete-time setting.

5.0.0.4 Conversion loss and optimality gap.

For a given single-armed policy \({\bar{\pi}}\), we consider a continuous-time version of the leader-and-follower system (cf.Section 4.1). For technical reasons, the initial actions are specified differently from the discrete-time setting. Specifically, we assume that the initial action \(\widehat{A}(0)\) of the leader arm is chosen by \({\bar{\pi}}\) based on \(\widehat{S}(0)\), and the follower’s initial action \(A(0)\) equals \(\widehat{A}(0)\). As before, the follower arm always takes the same action as the leader arm regardless of its own state. Given initial states \((S(0),\widehat{S}(0)) = (s,\widehat{s})\), the synchronization time is defined as \[\tau^{\mathrm{sync}}(s,\widehat{s}) \triangleq \inf\{t\ge 0\colon S(t)=\widehat{S}(t)\}.\] We no longer need to impose the Synchronization Assumption, since the unichain assumption automatically implies \(\mathbb{E}\left[\tau^{\mathrm{sync}}(s,\widehat{s})\right] < \infty\) in continuous time—see Lemma 5 in Appendix 12.

Theorem 2 establishes an \(O(1/\sqrt{N})\) 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-based framework called Follow-the-Virtual-Advice that converts a single-armed optimal policy into a policy in the original \(N\)-arm system with an \(O(1/\sqrt{N})\) optimality gap. In 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/\sqrt{N})\) without relying on UGAP or the non-degenerate condition.

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 a 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.

7 More related work↩︎

In this section, we provide additional discussion on related work.

7.0.0.1 Relationship between the infinite-horizon average-reward setting and the finite-horizon total-reward/infinite-horizon discounted-reward setting.

While infinite-horizon average-reward RBs, finite-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 finite-horizon/discounted-reward setting.

From the algorithm design perspective, the finite-horizon/discounted-reward setting focuses on optimizing the transient performance, while the infinite-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 finite-horizon/discounted-reward setting [12], [14]–[19] and the infinite-horizon average-reward setting [8]–[12] utilize certain forms of linear programming (LP) relaxations to design algorithms. However, 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. In contrast, in the infinite-horizon average-reward setting, the LP solves for the optimal state-action frequency in steady state, which can be seen as a fixed point rather than a trajectory. As a result, the number of variables and constraints of the LP for the finite-horizon/discounted-reward setting scales with the number of time steps, which is not the case for the infinite-horizon average-reward setting. On the other hand, because the LP relaxation for the infinite-horizon 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.

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 finite-horizon/discounted-reward setting have at least a quadratic dependency on the (effective) horizon [12], [19]. Consequently, when translated to the bounds on the optimality gap of average reward per time slot, those bounds diverge to infinity as the time horizon goes to infinity.

7.0.0.2 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 [22], [23]. A more recent reference on this topic is [24].

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 a reward-maximizing strategy of pulling arms in the presence of uncertainty in the arms’ rewards; see the book [25] for a comprehensive overview. Among these formulations, closely related to 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 a 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 [16].

8 Discussion on the computational costs of FTVA↩︎

FTVAdefined in Algorithm 2 can be computed and implemented efficiently.

First, computing FTVArequires solving 5 once. Given that 5 does not depend on \(N\), the computational cost here is a constant.

Next, we examine the computational cost of implementing FTVA.

• Each arm simulates a 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, FTVAselects 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 FTVAis linear in \(N\).

Additionally, we note that the simulation of the virtual processes is 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.

9 Sufficient conditions for Synchronization Assumption(SA)↩︎

Recall that for the discrete-time setting, our bound on the conversion loss in Theorem 1 holds when the input single-armed policy \({\bar{\pi}}\) satisfies the Synchronization Assumption (SA). SA stipulates that the two arms in the leader-and-follower system (cf.Section 4.1) under the policy \({\bar{\pi}}\) 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 state Markov chain and thus substantially simpler.

To provide a more intuitive understanding of 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 in 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 a relatively mild assumption. We emphasize that the sufficient conditions presented in this section are not exhaustive. They serve as illustrative examples of when SA holds and offer insights on the nature of synchronization.

The discussion in this section pertains to the discrete-time setting. We reiterate that our results for the continuous-time setting do not require SA.

9.1 Preliminaries↩︎

Before presenting the sufficient conditions, we first prove a few preliminary facts. The first one is a basic property of unichain MDPs.

The next proposition provides a convenient way for verifying SA and is used for establishing other sufficient conditions.

9.2 Sufficient conditions based on self-loops↩︎

The unichain condition and Proposition 1 guarantee that there are some states that the leader arm and the follower arm will both visit for a 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 to verify SA. A 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 to the same state.

Proposition 3 assumes that all states in the recurrent class of the policy \({\bar{\pi}}\) have self-loops. We can actually require fewer self-loops if we can characterize the recurrent states of the follower arm. In particular, let \({{\bar{\pi}}_1}\) denote the all-one policy, the policy that applies action \(1\) in all states. Observe that if the leader arm applies action \(1\) for a sufficiently long time, the follower arm will also apply action \(1\) and effectively follows \({{\bar{\pi}}_1}\). The recurrent class of the policy \({{\bar{\pi}}_1}\) must intersect the recurrent class of \({\bar{\pi}}\), so it suffices to have self-loops in the intersection of these two recurrent classes. The idea is formalized in Proposition 4.

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.

We remark that Propositions 4 and 5 have analogous versions that are stated in terms of the all-zero policy \({{\bar{\pi}}_0}\), the policy that applies action \(0\) in all states. We omit the details.

Now we prove the above propositions. Note that Proposition 3 is strictly weaker than Proposition 4: because the single-armed policy \({\bar{\pi}}\) satisfies the budget constraint with \(\alpha \in (0,1)\), there must be a state \(s^a\in \mathcal{S}\) such that \({\bar{\pi}}(1|s^a) >0\). Therefore, we only need to prove Propositions 4 and 5.

9.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.

We give two sufficient conditions based on cycles. These conditions are relaxations of the conditions in Proposition 4 and 5.

Similarly to Propositions 4 and 5, Propositions 6 and 7 have analogous version that are stated in terms of the all-zero policy \({{\bar{\pi}}_0}\). We omit the details.

Now we prove Propositions 6 and 7.

10 On relaxing the unichain condition↩︎

Throughout this paper, we have imposed the (all-policy) unichain condition, i.e., all Markovian single-armed policies have a single recurrent class. Making this blanket assumption simplifies our presentation, but it can be substantially relaxed for many of 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 a single-armed policy, each corresponding to a different long-run average reward. To adapt to this change, we can let both the single-armed policy \({\bar{\pi}}\) and the initial state distribution \(\mu\) be optimization variables of the single-armed problem. We denote the average reward given \({\bar{\pi}}\) and \(\mu\) as \(V_1^{{\bar{\pi}}, \mu}\). We still denote the optimal value of the single-armed problem as \(V_1^\mathrm{rel}\). Note that the single-armed problem can still be solved by the same linear program in 5 or 16 : The optimal initial state distribution \(\mu^*\) can be taken as the optimal stationary state distribution \((y^*(s, 1) + y^*(s,0))_{s\in\mathbb{S}}\), given the optimal solution of LP, \(y^*\).

The definitions of FTVAand FTVA-CTdo not require any change, considering that they are already using the stationary distribution of \({\bar{\pi}}\) to initialize the virtual states. The conversion losses, now denoted as \(V^{{\bar{\pi}}, \mu}_1 - V^{\mathrm{\texttt{FTVA}}({\bar{\pi}}, \mu)}_N\) and \(V^{{\bar{\pi}}, \mu}_1 - V^{\mathrm{\texttt{FTVA-CT}}({\bar{\pi}}, \mu)}_N\), have the same bound as what we currently have in equation 11 in Theorem 1 for discrete-time RBs and equation 20 in Theorem 2 for continuous-time RBs. These bounds hold as long as the given input policy \({\bar{\pi}}\) has finite expected synchronization times, which can be seen by inspecting the proofs of the theorems given in Appendix 11 and Appendix 12.

The optimality gap bounds in 12 in Theorem 1 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-time and continuous-time settings, consider an optimal single-armed policy \({\bar{\pi}}^*\) and optimal initial state distribution \(\mu^*\). Note that \(V_1^{{\bar{\pi}}^*, \mu^*} = V_1^\mathrm{rel}\geq V_N^*\). If \(V_1^{{\bar{\pi}}^*, \mu^*} - V^{\mathrm{\texttt{FTVA}}({\bar{\pi}}^*, \mu^*)}_N = O(1/\sqrt{N})\), then \(V_N^* - V^{\mathrm{\texttt{FTVA}}({\bar{\pi}}^*, \mu^*)}_N = O(1/\sqrt{N})\); if \(V_1^{{\bar{\pi}}^*, \mu^*} - V^{\mathrm{\texttt{FTVA-CT}}({\bar{\pi}}^*, \mu^*)}_N = O(1/\sqrt{N})\), then \(V_N^* - V^{\mathrm{\texttt{FTVA-CT}}({\bar{\pi}}^*, \mu^*)}_N = O(1/\sqrt{N})\).

In the discrete-time setting, our sufficient conditions for finite expected synchronization times, presented in Propositions 4, 5, 6 and 7, are valid as long as each of the two policies \({\bar{\pi}}\) and \({\bar{\pi}}_1\) has a single recurrent class and the two classes intersect. Similarly, Lemma 5 in Appendix 12, which establishes finite expected synchronization times for the continuous-time setting, holds under the same condition on \({\bar{\pi}}\) and \({\bar{\pi}}_1\).

11 Proofs for discrete-time RBs↩︎

11.1 Overview↩︎

In this section, we focus on proving the bound 11 on the conversion loss \(V^{\bar{\pi}}_1 - V^{\mathrm{\texttt{FTVA}}({\bar{\pi}})}_N\) for any single-armed policy \({\bar{\pi}}\) . The asymptotic optimality result 12 in Theorem 1 will be a direct consequence of 11 if we take \({\bar{\pi}}\) to be any optimal single-armed policy \({\bar{\pi}}^*\).

We first show that under FTVA(\({\bar{\pi}}\)) defined in Algorithm 2, each virtual process is an independent Markov chain induced by applying \({\bar{\pi}}\) to the single-armed system \((\mathbb{S}, \mathbb{A}, P, r)\), as stated in Lemma 1 below. We will rigorously prove it in the next subsection.

Next, as sketched in Section 4.2, we bound \(V^{\bar{\pi}}_1 - V^{\mathrm{\texttt{FTVA}}({\bar{\pi}})}_N\) as \[\begin{align} V^{\bar{\pi}}_1 - V^{\mathrm{\texttt{FTVA}}({\bar{\pi}})}_N &= \frac{1}{N} \mathbb{E}\left[\sum_{i=1}^Nr(\widehat{S}_i(\infty), \widehat{A}_i(\infty)) - \sum_{i=1}^Nr(S_i(\infty), A_i(\infty))\right] \nonumber \\ &\leq \frac{2r_{\max}}{N} \mathbb{E}\left[\sum_{i=1}^N\mathbb{1}\!\left\{(\widehat{S}_i(\infty), \widehat{A}_i(\infty)) \neq (S_i(\infty), A_i(\infty))\right\}\right]. } \end{align}\] We say an arm \(i\) is a bad arm at time \(t\) if \(\big(\widehat{S}_i(t), \widehat{A}_i(t)\big) \neq \big(S_i(t), A_i(t)\big)\), and a good arm otherwise. Then \(\mathbb{E}\left[\sum_{i=1}^N\mathbb{1}\!\left\{\big(\widehat{S}_i(\infty), \widehat{A}_i(\infty)\big) \neq \big(S_i(\infty), A_i(\infty)\big)\right\}\right]=\mathbb{E}\big[\text{\# bad arms}\big]\) in steady state.

By Little’s Law, we have the following relationship: \[\begin{align} \mathbb{E}\left[\text{\# bad arms}\right]=\text{(rate of generating bad arms)} \times \mathbb{E}\left[\text{time duration of a bad arm}\right]. \end{align}\] 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 \(t\) if \(\widehat{A}_i(t) \neq A_i(t)\). The disagreement events are the only cause that turns good arms into bad arms because otherwise by the construction of our algorithm, \(\widehat{S}_i(t)\) will remain the same as \(S_i(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 \(\widehat{\boldsymbol{s}}\) the instantaneous disagreement rate, denoted as \(d(\widehat{\boldsymbol{s}})\).

We also define disagreement period of the arm \(i\) as a continuous period of time when arm \(i\) is a bad arm, separated by disagreement events. Formally,

We use \(D_\text{avg}\) to denote the long-run average length of the disagreement periods, i.e., the average of \(t_\mathrm{end}- t_\mathrm{begin}\) of all disagreement periods.

With the definitions, we can state Little’s Law in the context of disagreement periods. We omit its proof since it is a direct consequence of Little’s Law.

11.2 Lemmas and the proof of Theorem 1↩︎

In this section, we will prove Theorem 1. We first rigorously prove Lemma 1.

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.

Given the three lemmas above, we can prove Theorem 1.

12 Proofs for continuous-time RBs↩︎

12.1 Preliminary: finite synchronization time↩︎

In this section, we prove that the synchronization time has a 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 in the proof of Proposition 3 and 4.

12.2 Overview of the proof of Theorem 2↩︎

In this section, we focus on proving the bound 20 on the conversion loss \(V^{\bar{\pi}}_1 - V^{\mathrm{\texttt{FTVA-CT}}({\bar{\pi}})}_N\) for any single-armed policy \({\bar{\pi}}\). The asymptotic optimality result 21 in Theorem 2 will be a direct consequence of 20 if we take \({\bar{\pi}}\) to be any optimal single-armed policy \({\bar{\pi}}^*\).

We first show that under FTVA-CT(\({\bar{\pi}}\)) defined in Algorithm 5, \(\{(\boldsymbol{S}(t), \widehat{\boldsymbol{S}}(t))\}_{t\geq 0}\) is a continuous-time Markov chain and each virtual process is an independent Markov chain induced by applying \({\bar{\pi}}\) to the single-armed system, as stated in Lemma 6 below. We will prove it in the next subsection.

Next, we can upper bound the conversion loss \(V^{\bar{\pi}}_1 - V^{\mathrm{\texttt{FTVA-CT}}({\bar{\pi}})}_N\) as \[\begin{align} V^{\bar{\pi}}_1 - V^{\mathrm{\texttt{FTVA-CT}}({\bar{\pi}})}_N &= \frac{1}{N} \mathbb{E}\left[\sum_{i=1}^Nr(\widehat{S}_i(\infty), \widehat{A}_i(\infty)) - \sum_{i=1}^Nr(S_i(\infty), A_i(\infty))\right] \nonumber \\ &\leq \frac{2r_{\max}}{N} \mathbb{E}\left[\sum_{i=1}^N\mathbb{1}\!\left\{(\widehat{S}_i(\infty), \widehat{A}_i(\infty)) \neq (S_i(\infty), A_i(\infty))\right\}\right] \nonumber \\ &\leq \frac{2r_{\max}}{N} \mathbb{E}\left[\sum_{i=1}^N\mathbb{1}\!\left\{\widehat{S}_i(\infty)\neq S_i(\infty)\right\} + \sum_{i=1}^N\mathbb{1}\!\left\{\widehat{A}_i(\infty)\neq A_i(\infty)\right\}\right]. \label{eq:bound-by-disagreement-number-cont} \end{align}\tag{29}\] The bound is slightly different from the 13 since we want to 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.

Before showing the proof of Lemma 7, we will first use Lemma 7 to prove Theorem 2.

12.3 Proof of Lemma 6↩︎

12.4 Proof of Lemma 7↩︎

In this section, we prove the key intermediate result, Lemma 7. The second equation 31 in Lemma 7 is obvious from the definition of the policy. We can therefore focus on proving 30 , 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 a similar approach as Section 11: 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 a 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 RB setting where \(A_i(t) \neq \widehat{A}_i(t)\) can immediately cause \(S_i(t) \neq \widehat{S}_i(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_i(t) = \widehat{A}_i(t)\).

Specifically, the disagreement event of a good arm can be defined as having a state transition that turns it into a bad arm, since a good arm is supposed to remain good if we always have \(A_i(t) = \widehat{A}_i(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.

The purpose of the exponential timer is to simulate the transition time of the leader-and-follower system, which characterizes how the arm would have behaved if \(A_i(t)=\widehat{A}_i(t)\). Specifically, when arm \(i\) has \(S_i(t) \neq \widehat{S}_i(t)\) (so it is a bad arm) and \(A_i(t) \neq \widehat{A}_i(t)\), we construct an imaginary leader-and-follower system whose state-action pairs are \((S_i(t), \widehat{A}_i(t), \widehat{S}_i(t), \widehat{A}_i(t))\). We let the transition times of the virtual state \(\widehat{S}_i(t)\) in the two systems be identical, and the transition times of the real state \(S_i(t)\) in the two systems be independent. Then the transition time of \(S_i(t)\) in the leader-and-follower system has an exponential distribution with rate \(G(S_i(t), \widehat{A}_i(t))\), which is equal to the time that the exponential timer ticks.

Therefore, there are two ways that the transition of arm \(i\) with \(S_i(t) \neq \widehat{S}_i(t)\) and \(A_i(t) \neq \widehat{A}_i(t)\) can deviate from the leader-and-follower system described above: either arm \(i\) itself has a transition in the real state \(S_i(t)\), or when the exponential timer ticks. This statement is actually also true if \(S_i(t) = \widehat{S}_i(t)\) and \(A_i(t) \neq \widehat{A}_i(t)\) because in that case, the exponential timer pauses.

We can thus formally define the disagreement event of arm \(i\) as below.

After defining the disagreement events, we can define the disagreement period of arm \(i\) as the period of time when \(S_i(t) \neq \widehat{S}_i(t)\), separated by disagreement events, formally stated below.

We let \(d(\boldsymbol{s}, \widehat{\boldsymbol{s}})\) be the instantaneous rate of disagreement events (instantaneous disagreement rate) when the system has real and virtual states \((\boldsymbol{S}(t), \widehat{\boldsymbol{S}}(t)) = (\boldsymbol{s}, \widehat{\boldsymbol{s}})\). Let \(D_\text{avg}\) be the long-run average length of the disagreement periods.

Observe that the number of bad arms (the arms such that \(S_i(t) \neq \widehat{S}_i(t)\)) is the number of arms in disagreement periods, so we can apply Little’s Law to the number of bad arms.

13 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 13.1 and 13.2, we describe the details of the experiments of Figure 1 and 4. We conduct the simulations of these two experiments with different initial points and present the results in Appendix 13.3. To give an intuitive understanding of the difference between these policies, we also display more visualization of the sample paths under different policies in Appendix 13.4. ³

13.1 Experiment details of Figure 1↩︎

13.1.0.1 Restless bandits setting

In Figure 1, we consider the discrete-time \(N\)-arm restless bandits represented by the tuple \((N, \mathbb{S}^N, \mathbb{A}^N, P, r, \alpha N)\). We vary the number of arms \(N\), and keep the rest of the parameters fixed. The state space of each arm is \(\mathbb{S}= \{1,2,3\}\). The action space is \(\mathbb{A}=\{0,1\}\). The transition kernel \(P\) is given by \[\begin{align} P( \cdot ,0,\cdot ) \;&=\;\begin{bmatrix} 0.02232142 & 0.10229283 & 0.87538575\\ 0.03426605 & 0.17175704 & 0.79397691\\ 0.52324756 & 0.45523298 & 0.02151947 \end{bmatrix}, \\ P( \cdot ,1,\cdot ) \;&=\;\begin{bmatrix} 0.14874601 & 0.30435809 & 0.54689589\\ 0.56845754 & 0.41117331 & 0.02036915\\ 0.25265570 & 0.27310439 & 0.4742399 \end{bmatrix}, \end{align}\] where the number in \(s\)-th row and \(s'\)-th column in each matrix represents \(P(s, 0, s')\) or \(P(s, 1, s')\), for \(s,s'\in \{1,2,3\}\). The reward function \(r\) is given by \[\begin{align} r( \cdot , 0) \;&= \;\begin{bmatrix} 0 & 0 & 0 \end{bmatrix}, \\ r( \cdot , 1) \;&= \;\begin{bmatrix} 0.37401552 & 0.11740814 & 0.07866135 \end{bmatrix}, \end{align}\] where the \(s\)-th entry of each vector represents \(r(s, 0)\) or \(r(s,1)\), for \(s \in \{1,2,3\}\). The budget parameter \(\alpha = 0.4\), so \(0.4 N\) arms are pulled in each time slot. This setting is taken from the Appendix E of [11] as a counterexample to the UGAP assumption. We note that this RB problem obviously satisfies Synchronization Assumption for any policy: observe that \(P(s,a,s')>0\) for all \(s,s'\in\mathbb{S}, a\in\mathbb{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.

13.1.0.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, \dots, 1000\). Three policies are considered: our policy FTVA(\({\bar{\pi}}^*\)), the Whittle’s index policy [8], and an LP-Priority policy [9]. For each data point, we 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 to be \(1\), because simulation results do not quite depend on the initial states (see Appendix 13.3).

13.1.0.3 Detail of policies

We implement Whittle index policy and LP-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 5 is: \[y^*( \cdot ,\cdot ) \;=\;\begin{bmatrix} 0 & 0.29943\\ 0.23768 & 0.10057\\ 0.36232 & 0 \end{bmatrix},\] where the \(s\)-th row represents \(y^*(s,0)\) and \(y^*(s, 1)\), for \(s\in \{1,2,3\}\). This solution implies that a reasonable policy should almost always pull arms in state \(1\), pull arms in state \(2\) for a certain fraction of time, and almost never pull arms in state \(3\). Therefore the only reasonable priority in this RB setting is \(1 > 2 > 3\).

Our policy FTVA(\({\bar{\pi}}^*\)) 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 on the virtual actions. Our tie-breaking rule is to select \(A_i(t)\)’s such that the number of good arms, i.e., the arms such that \(S_i(t) = \widehat{S}_i(t)\) and \(A_i(t) = \widehat{A}_i(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-breaking rules and their impact on finite-\(N\) performances remains unclear in the present analysis, leaving it as a topic for future investigation.

13.2 Experiment details of Figure 4↩︎

13.2.0.1 Restless bandits setting

In Figure 4, we consider the discrete-time \(N\)-arm bandits constructed as below. Suppose the state space for each arm is \(\mathbb{S}=\{0,1,\ldots,7\}\). Each state has a preferred action, which is action \(1\) for states \(0, 1, 2, 3\), and action \(0\) otherwise. For an arm in state \(s\), applying the preferred action moves the arm to state \((s+1) \bmod 8\) with probability \(p_{s,\text{R}}\), and applying the other action moves the arm to state \((s-1)^+\) with probability \(p_{s,\text{L}}\).⁴ The probabilities \(p_{\cdot, \text{R}}\) and \(p_{\cdot, \text{L}}\) are given by \[\begin{align} p_{\cdot , \text{R}} &= \begin{bmatrix} 0.1 & 0.1 & 0.1 & 0.1 & 0.1 & 0.1 & 0.1 & 0.1 \end{bmatrix}, \\ p_{\cdot , \text{L}} &= \begin{bmatrix} 1.0 & 1.0 & 0.48 & 0.47 & 0.46 & 0.45 & 0.44 & 0.43 \end{bmatrix}. \end{align}\] 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) = p_{7, \text{R}}\), and \(r(s,a)=0\) for all other \(s\in\mathbb{S},a\in\mathbb{A}\). The parameter \(\alpha= 1/2\), so \(N/2\) arms are activated in each time slot.

13.2.0.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, \dots, 1000\). Three policies are considered: our policy FTVA(\({\bar{\pi}}^*\)), a random tie-breaking policy, and a particular LP-Priority policy that prioritizes arms with larger Lagrangian optimal indices (see the definition of Lagrangian optimal indices in [12], [14], [16]). This particular LP-Priority policy is also referred to as the LP-Index policy in the literature. But for simplicity, we just refer to it as LP-Priority in this paper. For each data point, we 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 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 4 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(\({\bar{\pi}}^*\)) and random tie-breaking or LP-Priority, which we will show in the next section.

13.2.0.3 Details of policies

The optimal solution of 5 is \(y^*(s,1) = 1/ 8\) for \(s=0,1,2,3\), \(y^*(s,0)=1 / 8\) for \(s=4,5,6,7\), and \(y^*(s,a)=0\) for other \(s\in\mathbb{S}\) and \(a\in\mathbb{A}\). Note that the same \(y^*\) remains optimal even if we remove the budget constraint. The optimal LP solution suggests that a reasonable policy should almost always pull arms in states \(0,1,2,3\), and almost never pull arms in states \(4,5,6,7\).

The random tie-breaking 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-Priority policy we consider prioritizes arms with larger Lagrangian optimal indices [12], [16]. Specifically, it 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: \[\begin{bmatrix} 0.0125 & 0.1375 & 0.0725 & 0.07125 & -0.07 -0.06875 & -0.0675 & -0.06625 \end{bmatrix},\] and the priority is \(1 > 2 > 3 > 0 > 7 > 6 > 5 > 4\).

The implementation of our policy FTVA(\({\bar{\pi}}^*\)) is the same as in the last experiment.

13.2.0.4 Further discussions of the policies

As shown in Figure 4, 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 in 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 \(6\) 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(\({\bar{\pi}}^*\)) 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 \({\bar{\pi}}^*\) has a single recurrent class \(\mathbb{S}\), and satisfies Synchronization Assumption. See Appendix 10 for the discussion on the conditions under which Synchronization Assumption and Theorem 1 hold when unichain is not assumed.

13.3 Varying the initial points of the Figure 1 and 4 examples↩︎

In Figure 1 and Figure 4, we have fixed one initial point for each simulation, for the ease of presentation. In this section, we 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 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.

• For each \(N\)-armed problem, we set the initial state such that \(N\cdot\pi(s)\) arms are in state s for each s, with proper rounding.

• For each \(N\)-armed problem, we run all the policies with this initial state.

We illustrate the results of the \(20\) sets of simulations in the Figure 8 (a) and 8 (b) in the following way: For \(\mathrm{\texttt{FTVA}}({\bar{\pi}}^*)\), 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 \(\mathrm{\texttt{FTVA}}({\bar{\pi}}^*)\) still approaches the optimal value as \(N\) increases, whereas the max curves for other policies are strictly separated from the optimal value.

13.4 Visualization of the policies↩︎

In Figure 3 of Section 3.3, we illustrate what LP-Priority and \(\mathrm{\texttt{FTVA}}({\bar{\pi}}^*)\) 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,7\). Under the optimal single-armed policy, each arm moves from state \(s\) to \((s+1) \text{ 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 in the \(N\)-armed system, 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\).

The three heatmaps in Figure 9 (a) illustrate how the fractions of arms in each state change over time under the three policies: random tie-breaking, LP-Priority, and \(\mathrm{\texttt{FTVA}}({\bar{\pi}}^*)\). The x-axis represents the time slot, which ranges from \(0\) to \(499\); the y-axis represents the states; the brighter color represents a 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.

We can see that under the random tie-breaking, the arms concentrate around state \(0\); under LP-Priority, the arms concentrate around states \(\{3,4,5\}\) after a burn-in period; under \(\mathrm{\texttt{FTVA}}({\bar{\pi}}^*)\), the arms uniformly spread out over the \(8\) states.

In Figure 9 (b), we take a closer look at the sample path of the random tie-breaking policy from time \(250\) to \(289\) and contrast it with the sample path if the system uses \(\mathrm{\texttt{FTVA}}({\bar{\pi}}^*)\) 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 arm implies that the arm takes the non-preferred action and moves in the wrong direction. The magnitudes of the arrows represent how fast they are moving.

We can see that under random tie-breaking, although the arms have a 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 contrast, when switching to \(\mathrm{\texttt{FTVA}}({\bar{\pi}}^*)\), most arrows point in the right direction, which implies that the arms consistently apply the preferred actions. As a result, \(\mathrm{\texttt{FTVA}}({\bar{\pi}}^*)\) helps the arms to escape from state \(0\) and converge to the uniform distribution over the state space.

Figure 10 (a) illustrates the fraction of arms in state \(s\) taking action \(a\) in a few time slots after \(250\) in the same sample path of the random tie-breaking policy in Figure 9 (a). For each \(s\) and \(a\). The upper bar plot is under the random tie-breaking policy, while the lower bar plot is after switching to \(\mathrm{\texttt{FTVA}}({\bar{\pi}}^*)\). The x-axis represents the state; the y-axis represents the fraction; there are four bars in each state, corresponding to \(4\) 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-preferred action in this state; the lower segment of the bar corresponds to action \(0\), and the higher segment of the bar corresponds to action \(1\).

We can see that under \(\mathrm{\texttt{FTVA}}({\bar{\pi}}^*)\), more arms choose the preferred actions for state \(1\) than under the random tie-breaking policy, which prevents the arms in state \(1\) from moving back to state \(0\) as we see in Figure 9 (b) under the random tie-breaking policy.

Figure 10 (b) is similar to Figures 10 (a), except that the random tie-breaking policy is replaced by the LP-Priority policy. We can again see that under LP-Priority there is a force that causes the arms to concentrate on a state, whereas switching to \(\mathrm{\texttt{FTVA}}({\bar{\pi}}^*)\) helps the system to escape from that state.

The common failure mode for random tie-breaking and LP-Priority in this setting 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\). \(\mathrm{\texttt{FTVA}}({\bar{\pi}}^*)\) 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.

14 Generalization to heterogeneous arms↩︎

In this section, we show how FTVAand its analysis can be extended to the case with heterogenous arms. We focus on the discrete-time case for simplicity. The continuous-time case can be analyzed in a similar fashion.

14.1 Setting and algorithm↩︎

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. Suppose each arm is indexed by \(i\in[N]\), and we denote the type of the \(i\)-th arm as \(k(i)\). For any type \(k\) arm, we let \(P_k(s,a,s')\) be its probability of transitioning from state \(s\) to \(s'\) upon taking action \(a\), and let \(r_k(s,a)\) be its reward for taking action \(a\) in state \(s\).

Consider the linear program below, whose variables \(y_k(s,a)\) represents the steady-state probability that a type \(k\) arm is in state \(s\) taking action \(a\), for \(k\in[K], s\in\mathbb{S}, a\in\mathbb{A}\). \[\begin{align} \tag{35}\underset{\{y_k(s,a)\}_{k\in[K],s\in\mathbb{S}, a\in\mathbb{A}}} {\text{maximize}} & \sum_{k} \sum_{s,a} \beta_k r_k(s,a)y_k(s,a) \\ \text{subject to}\mspace{25mu} &\mspace{15mu} \sum_{k} \sum_{s}\beta_k y_k(s,1)=\alpha, \tag{36}\\ & \sum_{s', a} y_k(s', a) P_k(s', a, s) = \sum_{a} y_k(s,a), \quad \forall k\in[K], s\in\mathbb{S}, \tag{37}\\ \begin{aligned} &\sum_{s, a} y_k(s,a) = 1 \;\; \forall k\in[K]; \\ &y_k(s,a) \geq 0, \;\; \forall k\in[K], s\in\mathbb{S}, a\in\mathbb{A}. \tag{38} \end{aligned} \end{align}\] where the three constraints 36 , 37 , and 38 correspond to 6 , 7 , and 8 in 5 ; when writing summations, we omit \(\in[K]\), \(\in\mathbb{S}\) and \(\in\mathbb{A}\) for simplicity.

35 can be viewed as a relaxation of the \(N\)-armed problem. To see this, take any \(N\)-armed policy \(\pi\) and set \(y_k(s,a)\) to be the fraction of arms in state \(s\) taking action \(a\) among type \(k\) arms in steady state under \(\pi\), i.e., \[y_k(s,a)= \frac{1}{\beta_k N}\mathbb{E}\big[\sum_{k(i)=k} \mathbb{1}_{\{S_i^{\pi}(\infty)=s,A_i^{\pi}(\infty)=a\}}\big].\] Whevener \(\pi\) satisfies the budget constraint 2 , \(\{y_k(s,a)\}_{k\in[K], s\in\mathbb{S}, a\in\mathbb{A}}\) satisfies 36 –38 . Therefore, the optimal value of 35 , which we denote as \(V_1^\mathrm{rel}\), is an upper bound of the optimal value of the \(N\)-armed problem, i.e., \(V^\mathrm{rel}_1 \ge V^*_N\).

The optimal solution to 35 , \(\{y_k^*(s,a)\}_{k\in[K], s\in\mathbb{S}, a\in\mathbb{A}}\), induces a optimal single-armed policy \({\bar{\pi}}_k^*\) for each type \(k\in[K]\): \[\label{eq:single-arm-opt-def-het} {\bar{\pi}}_k^*(a | s) = \begin{cases} y_k^*(s, a) / (y_k^*(s, 0) + y_k^*(s,1)), & \text{if } y_k^*(s, 0) + y_k^*(s,1) > 0, \\ 1/2, & \text{if } y_k^*(s, 0) + y_k^*(s,1) = 0. \end{cases} \quad \text{for s\in\mathbb{S}, a\in\mathbb{A}.}\tag{39}\] Standard argument in [20] show that if a type \(k\) arm runs \({\bar{\pi}}_k^*\), it achieves the steady-state expected reward \(\sum_{s,a} r_k(s,a)y_k^*(s,a)\), and requires \(\sum_s y_k^*(s,1)\) unit of budget in steady-state. If each type \(k\) arm could independently run the optimal single-armed policy of its type, since the fraction of type \(k\) arms in the \(N\)-armed system is \(\beta_k\), in steady state, the expected reward per arm would be \(V_1^\mathrm{rel}\), and the budget requirement per arm would be \(\sum_{k=1}^K \sum_s y_k^*(s,1) = \alpha\), which is analogous to the homogeneous case where the optimal policy of the relaxed problem in 3 achieves \(V_1^\mathrm{rel}\) reward and requires \(\alpha\) expected budget in steady-state.

To convert from the single-armed policies to an \(N\)-armed policy, FTVAlets each arm of type \(k\) independently simulate a virtual single-armed process following \({\bar{\pi}}_k^*\). Lines 3-14 of Algorithm 2 stay the same. We denote the resulting policy as \(\mathrm{\texttt{FTVA}}(\{{\bar{\pi}}_k^*\}_{k\in[K]})\). The resulting policy can be proved to achieve \(O(1/\sqrt{N})\) optimality gap, under the assumption that Synchronization Assumption is satisfied for each \({\bar{\pi}}_k^*\), as stated below:

14.2 Proof for Theorem 3↩︎

In this section, we prove Theorem 3.

Since \(V_1^\mathrm{rel}\geq V_N^*\), it suffices to show that \[\label{eq:het-pf-goal} V_1^\mathrm{rel}- V^{\mathrm{\texttt{FTVA}}(\{{\bar{\pi}}_k^*\}_{k\in[K]})}_N \leq \frac{r_{\max}\overline{\tau}^{\mathrm{sync}}_{\max}}{\sqrt{N}}.\tag{41}\] We start with an inequality that has the same form as 13 in the homogeneous case: \[\begin{align} V_1^\mathrm{rel}- V^{\mathrm{\texttt{FTVA}}(\{{\bar{\pi}}_k^*\}_{k\in[K]})}_N &= \frac{1}{N} \mathbb{E}\left[\sum_{i=1}^Nr\big(\widehat{S}_i(\infty), \widehat{A}_i(\infty)\big) - \sum_{i=1}^Nr\big(S_i(\infty), A_i(\infty)\big)\right] \nonumber \\ &\leq \frac{2r_{\max}}{N} \mathbb{E}\left[\sum_{i=1}^N\mathbb{1}\!\left\{\big(\widehat{S}_i(\infty), \widehat{A}_i(\infty)\big) \neq \big(S_i(\infty), A_i(\infty)\big)\right\}\right], \label{eq:bound-by-disagreement-number-het} \end{align}\tag{42}\] 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 \(V^\mathrm{rel}_1\).

Defining the disagreement events, disagreement periods, and disagreement rates in the same way as Appendix 11 and applying Little’s law, we have \[\label{eq:disagree-littles-law-het} \mathbb{E}\left[\sum_{i=1}^N\mathbb{1}\!\left\{(\widehat{S}_i(\infty), \widehat{A}_i(\infty)) \neq (S_i(\infty), A_i(\infty))\right\}\right] = \mathbb{E}\left[d(\widehat{\boldsymbol{S}}(\infty))\right] \cdot D_\text{avg},\tag{43}\] where \(d(\widehat{\boldsymbol{s}})\) is the instantaneous disagreement rate, and \(D_\text{avg}\) is the long-run average length of disagreement periods. With 42 and 43 , it remains to bound \(\mathbb{E}\left[d(\widehat{\boldsymbol{S}}(\infty))\right]\) and \(D_\text{avg}\).

By the definition of the policy, we have \(\mathbb{E}\left[d(\boldsymbol{\widehat{S}}(\infty))\right] = \mathbb{E}\left[\left\lvert\sum_{i=1}^N\widehat{A}_i(\infty) - \alpha N\right\rvert\right]\), \(\widehat{A}_i(\infty)\)’s are independent Bernoulli random variables, and \(\mathbb{E}\left[\widehat{A}_i(\infty)\right] = y_k^*(s,1)\) if arm \(i\) is of type \(k\). As a result, \[\mathbb{E}\left[\sum_{i=1}^N\widehat{A}_i(\infty)\right] = \sum_{k} \beta_k N \sum_{s,a} y_k^*(s,1) = \alpha N.\] Using the same Cauchy-Schwartz argument as in the proof of the homogeneous case in Appendix 11, it is not hard to show that \(\mathbb{E}\left[d(\boldsymbol{\widehat{S}}(\infty))\right] \leq \sqrt{N} / 2\).

As for \(D_\text{avg}\), it is not hard to see from the definition that the length of each disagreement period of a type \(k\) arm is stochastically dominated by \(\tau^{\mathrm{sync}}_k(s, a, \widehat{s}, \widehat{a})\), where \((s,a,\widehat{s},\widehat{a})\) are the initial states and actions of that disagreement period. Therefore, the average length of disagreement period is bounded by \[D_\text{avg}\leq \max_{k\in[K], (s, a, \widehat{s}, \widehat{a}) \in \mathbb{S}\times \mathbb{A}\times \mathbb{S}\times \mathbb{A}} \mathbb{E}\left[\tau^{\mathrm{sync}}_k(s,a,\widehat{s},\widehat{a})\right] = \overline{\tau}^{\mathrm{sync}}_{\max}.\]

Combining the above calculations, we get 41 , which finishes the proof.

References↩︎

---

1. Corresponding author↩︎

2. Although the follower arm does not follow a Markovian policy since it copies actions from the leader arm, by standard results on average reward MDP, the set of states in which the follower arm spends a positive fraction of time is the same as the recurrent class of some Markovian policy (cf. Chapter 8.9 of [20]). This class of states must intersect with \(\mathcal{S}\) by Proposition 1 and the unichain condition.↩︎

3. Our simulation code can be found in the link https://github.com/YigeHong/rb-break-ugap-ftva.↩︎

4. Here the subscript \(\text{L}\) means “left”, and \(\text{R}\) means “right”. We are imagining the arms being lined up in a row from state \(0\) to state \(7\), and the preferred action moves an arm to the right.↩︎

5. 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 on the simplest one.↩︎