1 Introduction↩︎

Large-scale decision-making problems with shared resources arise throughout modern engineering systems, including online advertising [1], [2], machine maintenance [3], job scheduling [4], surveillance [5], and healthcare operations [6]. A common modeling paradigm for these complex systems is a weakly-coupled Markov decision process (WCMDP) [7], which comprises \(N\) arms/subsystems, each of which itself is an MDP. In a heterogeneous WCMDP, each arm evolves according to its own dynamics, yet their actions are coupled through several global constraints. The goal is to find a policy that maximizes the long-term average reward over an infinite time horizon. A prominent special case is the (homogeneous) restless bandit (RB) model [8], where all arms share the same MDP model with a binary action space (active/passive). In RBs, there is only one constraint that limits the total number of active arms at each time step.

Learning in WCMDPs and RBs is challenging: when viewed as a single MDP, the state-action space \(\boldsymbol{\mathcal{S}} \times \boldsymbol{\mathcal{A}}\) of a WCMDP/RB is the product of the state-action spaces of the arms and thus has cardinality exponentially large in the number of arms \(N\). Recent work has essentially resolved the sample complexity of tabular average-reward MDPs and established the necessity of a \(\Theta(|\boldsymbol{\mathcal{S}} \times \boldsymbol{\mathcal{A}}|)\) sample size [9]–[12]. Naively applying these results to WCMDPs and RBs, which ignores the weakly coupling structure, yields a sample complexity exponential in \(N\). Even the planning problem—finding the exact optimal policy when the transition dynamics are known—is computationally intractable due to large spaces. Nonetheless, recent work has made notable progress on the planning problem and developed near-optimal policies that can be computed efficiently [13]–[17].

This paper considers the learning setting and addresses the following key question:

How can one learn a near-optimal policy in average-reward WCMDPs (or RBs) without incurring exponential dependence on the number of arms \(N\)?

We answer this question for both fully heterogeneous WCMDPs and homogeneous RBs with access to a generative model, showing that polynomial-in-\(N\) complexities are possible by exploiting the weakly coupled structure. In particular, we develop a plug-in approach, which applies an efficient planning algorithm—specifically the ID policy [13] for WCMDPs and two-set policy [14] for RBs—to the empirical model estimated from data. For fully heterogeneous WCMDPs, we establish the first finite-sample (PAC) optimality-gap guarantee, where both sample and computational complexities scale polynomially in \(N\) for obtaining a near-optimal policy with an \(O(1/\sqrt{N})\) optimality gap. For RBs, we further show that an optimality gap of \(O(1/N^\beta)\) is achievable for any \(\beta>0\) under mild structural assumptions.

A main technical contribution of the paper is a new Lyapunov-based analysis framework. Classical sample complexity analysis for the plug-in approach uses the standard simulation lemma, which relies on the bias function (a.k.a.relative value function) of the MDP [18]–[20]. The bias function is typically implicit and difficult to control, especially under the sophisticated planning algorithms we adopt. Our approach replaces the role of the bias function with an explicitly constructed Lyapunov function. Specifically, our framework first performs a Lyapunov drift analysis of the adopted planning algorithm in the true system, and then employs a drift transfer technique that allows us to analyze the empirical system by explicitly bounding the norm of the Lyapunov function. This framework applies whenever the planning algorithm admits a Lyapunov drift analysis, thus providing a powerful tool for analyzing the plug-in approach in average-reward weakly-coupled systems. We present the details of this framework in Section 5.

As a key step in implementing our Lyapunov framework, we develop a fine-grained perturbation analysis for the linear program (LP) relaxation associated with the RB. The analysis is applicable whenever the LP is solved with perturbed inputs, including but not limited to sampling-based estimates. Beyond serving as a technical tool in our proofs, this perturbation result reveals an intrinsic robustness property of policies constructed using this LP: under appropriate technical conditions, such a policy is stable against perturbed input, in the sense that the actions remain unchanged in all but one state, in which the action probabilities are adjusted to satisfy the constraints under perturbation. Since many control schemes for WCMDPs and RBs rely on solving variants of this LP relaxation, our perturbation results can be used as a robustness module in analyzing other algorithms, including various index and LP-priority policies that are extensively studied in the WCMDP and RB literature [17], [21]–[23].

1.0.0.1 Related work.

We review related work along the following three dimensions.

Planning for average-reward RBs/WCMDPs. For RBs, a classical starting point is the Whittle index policy [8], [21], which is derived from a Lagrangian relaxation and yields an index rule when the problem is indexable. However, indexability may fail or be difficult to verify in general, and even when it holds, the Whittle index policy is not guaranteed to be optimal for finite systems. Recent work has made progress on asymptotic optimality under average reward: [15] show that unichain/aperiodicity conditions are sufficient for asymptotic optimality, while [14] obtains an exponential asymptotic optimality gap without global attractor assumptions. Moving beyond RBs to general WCMDPs, [24] propose Markov task decomposition with greedy two-phase heuristics, and recent Lyapunov-based analyses obtain optimality gaps such as \(O(1/\sqrt N)\) for fully heterogeneous WCMDPs [13]. These results are in the planning regime and do not directly provide finite-sample learning guarantees when the arm dynamics are unknown.

Learning for average-reward RBs/WCMDPs. One line of work studies online learning for average-reward RBs, focusing on regret guarantees. Early papers considered weak regret against a simple benchmark policy [25]–[27]. Other results obtain sublinear regret against stronger benchmarks but either incur exponential computational complexity [28] or apply to special RB classes such as birth-death arms [29]. In multi-action average-reward RBs, [30] develop an LP-based index policy that is asymptotically optimal and design learning algorithms with \(\widetilde{O}(\sqrt T)\) regret against that index policy. Thompson-sampling based algorithms have also been studied [31]. These regret results do not imply the PAC/sample-complexity guarantees studied here, since there is no general regret-to-PAC conversion for average-reward MDPs [32]. Several papers study convergence of learning algorithms for RBs [33]–[35] and WCMDPs [36], but they do not provide finite-sample optimality-gap bounds. Recent Q-learning methods with function approximation aim to learn Whittle index policies [37], [38]; their finite-time convergence results do not translate directly to sample-complexity bounds for the optimality gap considered here. For finite-horizon or discounted objectives, methods based on Lagrangian relaxation, Q-learning, and deep RL have also been proposed [35], [39]–[42], but the guarantees are largely asymptotic or tailored to different performance criteria.

Sample complexity of tabular average-reward MDPs. Recent work has obtained sharp sample-complexity bounds for single-arm tabular average-reward MDPs. For uniformly mixing or uniformly ergodic MDPs with mixing-time bound \(t_{\mathrm{mix}}\), [43] obtain a minimax-optimal sample complexity \(\widetilde{O}(SA t_{\mathrm{mix}}/\varepsilon^2)\), matching lower bounds up to logarithmic factors; see also [44]. For weakly communicating MDPs, [11] establish a minimax-optimal bound \(\widetilde{O}(SAH/\varepsilon^2)\), where \(H=\mathrm{sp}(h^\star)\) is the span of the optimal bias function. Earlier work by [9] gave related upper and lower bounds, and the most general multichain setting has been characterized using a transient-time parameter. Parameter-free and adaptive algorithms have also been developed [12], [18], [32], [45], [46]. These PAC/sample-complexity guarantees are for single-arm tabular MDPs; applying them naively to an \(N\)-armed WCMDP or RB leads to exponential dependence on \(N\) because the joint state-action space is exponentially large.

2 Problem Setup↩︎

2.1 Weakly-coupled MDPs↩︎

A weakly-coupled MDP consists of \(N\) arms. Each arm \(i \in [N]\triangleq \{1,2,\dots,N\}\) itself is associated with an MDP \(\mathcal{M}_i = (\mathcal{S}, \mathcal{A}, P_i, r_i, (c_{k,i})_{k \in [K]})\). Here \(\mathcal{S}\) and \(\mathcal{A}\) are the state and action spaces, respectively, which are finite sets with \(|\mathcal{S}|=S, |\mathcal{A}|=A\); \(P_i(s'_i \mid s_i,a_i)\) is the transition probability from state \(s_i\) to state \(s'_i\) under action \(a_i\); \(r_i\) is the reward function; \(c_{k,i}\)’s are cost functions (\(K\) types of costs in total). When arm \(i\) is in state \(s_i\) and takes action \(a_i\), it generates reward \(r_i(s_i,a_i)\) and cost \(c_{k,i}(s_i,a_i)\) of each type \(k\). We assume that the reward functions take values in \([0,r_{\max}]\) for \(r_{\max}>0\), and the cost functions take values in \([0,c_{\max}]\) for \(c_{\max}>0\).

For the overall \(N\)-armed MDP, its state space is \(\mathcal{S}^N\) and action space is \(\mathcal{A}^N\), where the state is the joint state of all arms, denoted as \(\boldsymbol{s}=(s_1,\ldots,s_N)\), the action is the joint action of all arms, denoted as \(\boldsymbol{a}=(a_1,\ldots,a_N)\), and the reward is the sum of rewards from all arms. Given actions, the arms make state transitions independently, i.e., \(\boldsymbol{P}(\boldsymbol{s}'\mid\boldsymbol{s},\boldsymbol{a}) = \prod\nolimits_{i\in[N]} P_i(s'_i\mid s_i,a_i).\) The arms are coupled by the following cost constraints on their joint action: \[\sum\nolimits_{i\in[N]} c_{k,i}(s_i,a_i) \le \alpha_k N, \quad \forall k\in[K],\] where \(\alpha_k N\) is referred to as the budget for the cost of type \(k\). We assume that for every arm, the action \(0\), paired with any state, does not incur any cost of any type, and thus there always exists a feasible action \(\boldsymbol{a}=(0,0,\dots,0)\).

In this paper, we vary the number of arms \(N\) but keep the following constant: the number of cost types \(K\), the budgets \(\alpha_k\)’s, the reward upper bound \(r_{\max}\), and the cost upper bound \(c_{\max}\).

2.1.0.1 Performance criterion.

We consider the infinite-horizon average-reward criterion. For the \(N\)-armed system, let \(\boldsymbol{S}_t = (S_{i,t})_{i\in[N]}\) denote the state at time \(t\), where \(S_{i,t}\) is the state of arm \(i\); let \(\boldsymbol{A}_t = (A_{i,t})_{i\in[N]}\) denote the action at time \(t\), where \(A_{i,t}\) is arm \(i\)’s action. For any stationary policy \(\pi\), the long-run average reward, also referred to as the gain, from an initial state \(\boldsymbol{s}_0\) is defined as \[\rho^\pi(\boldsymbol{s}_0) \triangleq \lim_{T \to \infty} \frac{1}{T} \sum_{t=0}^{T-1} \frac{1}{N} \sum_{i \in [N]} \mathbb{E}^{\pi} \left[ r_i(S_{i,t}, A_{i,t}) \right],\] where we have used the superscript \(^\pi\) to indicate that the law is induced by the policy \(\pi\). Note that this limit exists due to the finite state and action spaces.

Classical MDP theory shows that it suffices to seek optimal policies within stationary policies (see, e.g., [47], Theorem 9.1.8). Therefore, the WCMDP aims to solve \[\begin{align} \label{eq:opt95problem} \max_{\pi\colon \text{stationary}} \;\rho^\pi(\boldsymbol{s}_0) \quad\; \text{s.t.} \;\sum\nolimits_{i \in [N]} c_{k,i}(S_{i,t}, A_{i,t}) \leq \alpha_{k} N, \;\forall k \in [K], \forall t \geq 0, \text{ under }\pi. \end{align}\tag{1}\] Denote the optimal value by \(\rho^\star(\boldsymbol{s}_0)\).

In this paper, besides stationary policies, we also consider policies with an augmented, but still finite, state space. Such policies maintain some extra state variables in addition to the system state \(\boldsymbol{S}_t\), and they are stationary with respect to the augmented state. The Markov chain induced by such a policy still has a finite state space and thus its long-run average reward is still well-defined.

2.2 LP relaxation↩︎

As we explain momentarily, the linear program (LP) below is a relaxation of the \(N\)-armed WCMDP. This LP plays an important role in the policy design in existing work [13]. \[\tag{2} \begin{align} \max_{(y_i(s,a))_{i\in[N],\,s\in\mathcal{S},\,a\in\mathcal{A}}} &\frac{1}{N} \sum\nolimits_{i\in[N]} \sum\nolimits_{s\in\mathcal{S},\,a\in\mathcal{A}} y_i(s,a) r_i(s,a)\tag{3} \\ \text{subject to} \qquad &\frac{1}{N} \sum\nolimits_{i\in[N]} \sum\nolimits_{s\in\mathcal{S},\,a\in\mathcal{A}} y_i(s,a) c_{k,i}(s,a) \leq \alpha_k, \quad \forall k\in[K] \tag{4} \\ &\sum\nolimits_{s'\in\mathcal{S},\,a'\in\mathcal{A}} P_i(s \mid s',a') y_i(s',a') = \sum\nolimits_{a\in\mathcal{A}} y_i(s,a), \;\; \forall s\in\mathcal{S}, i\in[N] \tag{5} \\ &\sum\nolimits_{s'\in\mathcal{S},\,a'\in\mathcal{A}} y_i(s',a') = 1, \quad y_i(s,a)\geq 0, \quad \forall s\in\mathcal{S},\, a\in\mathcal{A},\, i\in[N]. \tag{6} \end{align}\] Here the optimization variables \(y_i(s, a)\)’s can be thought of as the long-run fraction of time arm \(i\) spends in state \(s\) taking action \(a\). Then the constraint 4 is a constraint on the long-run average costs, which relaxes the hard constraint on the costs for each time step.

Let \((y_i^\star(s,a))_{i\in[N],s\in\mathcal{S},a\in\mathcal{A}}\) be an optimal solution to this LP, and let \(\rho^{\mathrm{rel}}\) denote the optimal value. [13] show that \(\rho^\star(\boldsymbol{s}_0)\le \rho^{\mathrm{rel}}\) for all \(N\)-armed WCMDPs and all initial state \(\boldsymbol{s}_0\).

2.3 Restless bandits↩︎

An extensively studied subclass of WCMDPs is the restless bandits. The additional structure in RBs has enabled the development of planning policies with smaller optimality gap. We are interested in whether the similar refinement is possible for learning.

We use the same notation for RBs as that for WCMDPs unless otherwise specified. It should be clear what we refer to from the context. An RB problem is a WCMDP where each arm has a binary action space \(\mathcal{A} = \{0,1\}\), where \(a=1\) is referred to as the pulling/active action and \(a=0\) the non-pulling/passive action. The cost constraint in an RB has a simple form: \[\sum\nolimits_{i\in[N]} a_i = \alpha N,\] where \(0<\alpha < 1\) and \(\alpha N\) is an integer. Compared to the standard WCMDP form, this constraint is written as an equality rather than an inequality. This discrepancy is largely conventional and does not change the problem in any fundamental way. We focus on the commonly studied homogeneous setting, where each arm’s MDP has the same transition kernel \(P\) and reward function \(r\).

An RB has an LP relaxation similar to that of the WCMDP [14]: \[\tag{7} \begin{align} \max_{(y(s,a))_{s\in\mathcal{S},\,a\in\mathcal{A}}}\mspace{15mu}&\sum\nolimits_{s\in\mathcal{S},a\in\mathcal{A}} y(s, a) r(s, a)\tag{8}\\ \text{subject to}\mspace{21mu} &\mspace{0mu}\sum\nolimits_{s\in\mathcal{S}} \quad y(s, 1) = \alpha, \tag{9}\\ &\sum\nolimits_{s'\in\mathcal{S},\,a'\in\mathcal{A}} P(s \mid s',a') y(s',a') = \sum\nolimits_{a\in\mathcal{A}} y(s,a), \quad \forall s\in\mathcal{S} \tag{10}\\ &\mspace{0mu}\sum\nolimits_{s'\in\mathcal{S}, a'\in\mathcal{A}} y(s',a') = 1, \quad y(s,a) \geq 0, \;\; \forall s\in\mathcal{S}, a\in\mathcal{A}. \tag{11} \end{align}\] Let \((y^\star(s,a))_{s\in\mathcal{S},a\in\mathcal{A}}\) be an optimal solution to this LP, and let \(\rho^{\mathrm{rel}}\) denote the optimal value. It has been shown that \(\rho^\star(\boldsymbol{s}_0)\le \rho^{\mathrm{rel}}\) for all \(N\)-armed RBs and all initial state \(\boldsymbol{s}_0\) [15].

3 Learning via a Plug-in Approach with Reference Policies↩︎

We adopt a plug-in approach for learning. This approach first constructs an empirical transition probability matrix for each arm using data, and then plug the empirical MDP into a planning algorithm. While the exact optimal policy is intractable for WCMDPs/RBs, we make use of existing efficient planning algorithms for computing a near-optimal policy, which we call a reference policy.

3.1 Constructing empirical MDPs↩︎

We assume access to a generative model, also known as a simulator [48], for the transition matrix of each arm’s MDP. As is standard in the generative setting, we assume the reward and cost functions are known.

In an \(N\)-armed WCMDP, for each arm \(i\), we collect \(n\) i.i.d.samples \(S_{s,a}^{i,1}, \dots, S_{s,a}^{i,n}\) from \(P_i(\cdot\mid s,a)\) for each state-action pair \((s,a)\in\mathcal{S}\times\mathcal{A}\). We construct the empirical transition kernel \(\widehat{P}_i\) by \(\widehat{P}_i(s' \mid s, a) \triangleq\frac{1}{n} \sum\nolimits_{j=1}^{n} \mathbb{I}\{S_{s,a}^{i,j} = s'\}, \forall s' \in \mathcal{S}.\) The empirical \(N\)-armed transition kernel is then given by the product \(\widehat{\boldsymbol{P}}(\boldsymbol{s}'\mid \boldsymbol{s},\boldsymbol{a})=\prod\nolimits_{i=1}^N \widehat{P}_i(s'_i \mid s_i, a_i).\)

For an \(N\)-armed RB, since we focus on the homogeneous setting where all the arms share the same transition kernel \(P\), we can pick any arm and construct the empirical transition kernel \(\widehat P\) using \(n\) i.i.d.samples per state-action pair. Then we define the empirical \(N\)-armed transition kernel \(\widehat{\boldsymbol{P}}\) in the same way as WCMDP by setting \(\widehat P_i=\widehat P\) for all \(i\in[N]\).

3.2 Plug-in approach for WCMDPs with ID policy↩︎

For WCMDPs, we consider the ID policy developed in [13] as our reference policy, denoted as \(\pi_{\mathrm{ID}}\). The ID policy is efficiently computable (with \(\text{poly}(N)\) complexity), and (under proper conditions) it achieves an \(O(1/\sqrt{N})\) optimality gap, i.e., \(\rho^\star(\boldsymbol{s}_0)-\rho^{\pi_{\mathrm{ID}}}(\boldsymbol{s}_0)=O(1/\sqrt{N})\).

A key component of the ID policy is the collection of optimal single-armed policies. Specifically, recall that \((y_i^\star(s,a))_{i\in[N],s\in\mathcal{S},a\in\mathcal{A}}\) is an optimal solution to the LP 2 . Then for each arm \(i\), viewed as an MDP on its own, we can define the following policy: \[\begin{align} \label{def-pibst} \bar{\pi}_i^\star(a \mid s) = \begin{cases} \frac{y_i^\star(s,a)}{\sum_{a \in \mathcal{A}} y_i^\star(s,a)}, & \text{if } \sum_{a \in \mathcal{A}} y_i^\star(s,a) > 0, \\ \frac{1}{|\mathcal{A}|}, & \text{if } \sum_{a \in \mathcal{A}} y_i^\star(s,a) = 0. \end{cases} \end{align}\tag{12}\] This policy is called the optimal single-armed policy for arm \(i\). The policies \(\{\bar{\pi}_i^\star\}_{i\in[N]}\) are designed such that if each arm \(i\) follows \(\bar{\pi}_i^\star\) and evolves completely independently, then the arms together satisfy the cost constraint in a time-average fashion and achieve a total reward of \(\rho^{\mathrm{rel}}\), the optimal value of the LP, which is an upper bound on the true optimal value of the \(N\)-armed WCMDP.

We defer a formal description of the ID policy to Algorithm 7 in Appendix 11. The high-level idea of the ID policy is to let most arms follow their optimal single-armed policies, while conforming to the hard cost constraints. An insight behind this approach is that if the arms are given a consistent ordering, e.g., based on the arm IDs, then the set of arms that can consistently follow their optimal single-armed policies expands over time and ultimately covers all but \(O(\sqrt{N})\) arms on average.

With the ID policy as our reference policy, the plug-in approach proceeds as follows. We substitute the empirical transition kernels \(\widehat P_i\)’s into the LP 2 . Solving this “empirical LP” gives an optimal solution \((\widehat{y}^\star_i(s,a))_{i\in[N],s\in\mathcal{S},a\in\mathcal{A}}\) and the resulting optimal single-armed policies \(\{\widehat{\Bar{\pi}}^\star_i\}_{i\in[N]}\). We then use \((\widehat{y}^\star_i(s,a))_{i\in[N],s\in\mathcal{S},a\in\mathcal{A}}\) and \(\{\widehat{\Bar{\pi}}^\star_i\}_{i\in[N]}\) to construct the ID policy, denoted as \(\widehat{\pi}_{\mathrm{ID}}\).

3.3 Plug-in approach for RBs with two-set policy↩︎

For homogeneous RBs, we consider the two-set policy from [14] as our reference policy, denoted as \(\pi_{\mathrm{TS}}\). The two-set policy is also efficiently computable, and (under proper conditions) it achieves an optimality gap \(\rho^\star(\boldsymbol{s}_0)-\rho^{\pi_{\mathrm{TS}}}(\boldsymbol{s}_0)=O(\exp(-cN))\) for a constant \(c>0\). Note that such an exponentially small optimality gap has been known to be achievable only for the RB subclass of WCMDPs, in the homogeneous setting under a set of conditions.

The two-set policy is also built on an optimal single-armed policy. Recall that \((y^\star(s,a))_{s\in\mathcal{S},a\in\mathcal{A}}\) is an optimal solution to the LP 7 . We define the corresponding optimal single-armed policy as: \[\label{eq:single-opt-RB} \bar\pi^\star(a\mid s)= \begin{cases} \frac{y^\star(s,a)}{y^\star(s,0)+y^\star(s,1)}, &\text{if } y^\star(s,0)+y^\star(s,1)>0,\\ \frac{1}{2}, & \text{if }y^\star(s,0)+y^\star(s,1)=0. \end{cases}\tag{13}\] Since the arms are homogeneous, they share the same single-armed policy \(\bar\pi^\star\).

A compact formal sketch of the two-set policy is given in Algorithm 9 in Appendix 14.1. Here we briefly describe its structure to facilitate the discussion of our learning approach. The two-set policy \(\pi_{\mathrm{TS}}\) maintains two disjoint subsets of arms, \(D_t^{\mathrm{OL}}\) and \(D_t^{\Bar{\pi}^\star}\), at each time \(t\). It applies two different decision rules to these two subsets, and both rules are based on the optimal single-armed policy \(\bar\pi^\star\). The subsets \(D_t^{\mathrm{OL}}\) and \(D_t^{\Bar{\pi}^\star}\) are updated using \(D_{t-1}^{\mathrm{OL}}\), \(D_{t-1}^{\Bar{\pi}^\star}\), and the current arm states. As a result, \(\pi_{\mathrm{TS}}\) operates on an augmented state that includes both the arm states and the two subsets.

The plug-in approach with the two-set policy as the reference policy proceeds similarly to the WCMDP case. We first substitute the empirical kernel \(\widehat P\) into the LP in 7 . Solving this LP gives an optimal solution \((\widehat{y}^\star(s,a))_{s\in\mathcal{S},a\in\mathcal{A}}\) and the corresponding optimal single-armed policies \(\widehat{\Bar{\pi}}^\star\). We then use \((\widehat{y}^\star(s,a))_{s\in\mathcal{S},a\in\mathcal{A}}\) and \(\widehat{\Bar{\pi}}^\star\) to construct the two-set policy, which is denoted as \(\widehat{\pi}_{\mathrm{TS}}\).

4 Main Results↩︎

We present our main results, which give upper bounds on the optimality gaps of the learned policies: \(\widehat{\pi}_{\mathrm{ID}}\) for WCMDPs and \(\widehat{\pi}_{\mathrm{TS}}\) for RBs. These bounds directly imply sample complexity bounds.

4.1 Main Results for WCMDPs↩︎

We begin by stating our assumptions. In average-reward MDP literature, it is common for sample complexity results to require a uniform mixing time bound under all policies (e.g., [44], [49]–[51]), or alternatively depend on the MDP diameter or bias span of an optimal policy (e.g., [11], [18], [32]). In our setting, the weakly coupled structure allows us to avoid imposing uniform mixing (or other) assumptions on the overall \(N\)-armed MDP, whose state/action spaces grow exponentially with \(N\). Instead, it suffices to make uniform mixing assumption on the individual arm MDPs.

Specifically, for each arm \(i\), we consider the associated single-armed MDP \((\mathcal{S}, \mathcal{A}, P_i, r_i)\), ignoring the cost functions and constraints. Given a policy \(\pi\) for this MDP, let \(P^\pi_i\) denote the transition probability matrix of the Markov chain induced by \(\pi\), i.e., \(P^\pi_i(s,s') \mathrel{\vcenter{:}}= \sum_{a\in\mathcal{A}} P_i(s'\mid s,a)\pi(a\mid s).\) If this Markov chain has a unique stationary distribution \(\mu^\pi_i\), we define its mixing time as \(\tau^\pi_i\mathrel{\vcenter{:}}=\min\left\{ t\in\mathbb{N}\colon \max_{s\in\mathcal{S}}\bigl\| (P^\pi_i)^{t}(s,\cdot)-\mu^\pi_i(\cdot)\bigr\|_1 \le 1/4 \right\},\) where \((P^\pi_i)^{t}\) is the \(t\)-step transition matrix. We assume that each arm has a finite uniform mixing time bound under all policies, and further that these bounds across arms have a finite uniform upper bound, as summarized in Assumption 1 below.

We remark that our learning approach does not use prior knowledge of the mixing time upper bound \(\tau_{\mathrm{unif}}\) in Assumption 1.

We provide a proof of Theorem 1 in Section 6, and give the detailed proofs of the key lemmas in Appendix 12. The optimality gap bound for \(\widehat{\pi}_{\mathrm{ID}}\) in Theorem 1 consists of two terms. The first term is a finite-sample error term that decreases at rate \(1/{\sqrt{n}}\) as the sample size \(n\) increases. The second term, \(C_2/{\sqrt{N}}\), is inherited from the optimality gap of the ID policy itself and is not affected by learning or the sample size \(n\). However, it vanishes at rate \(1/{\sqrt{N}}\) as the system size \(N\) increases. This scaling is the asymptotic regime of interest for WCMDPs, where the primary interest is in large systems.

The bound in Theorem 1 directly yields a sample complexity bound for achieving an optimality gap at most \(\epsilon\). Note that we can only guarantee a gap level \(\epsilon=\Omega(1/\sqrt{N})\) due to the second term in the bound. To achieve any \(\epsilon=\Omega(1/\sqrt{N})\), the sample size needed is \(n=\Omega\left(\frac{(S + \log (SAN/\eta))N^2}{\epsilon^2}\right)\). Notably, the total number of samples needed, \(NSAn\), grows only polynomially in \(N\) rather than exponentially in \(N\), although the state and action space sizes of the overall \(N\)-armed MDP are exponential in \(N\). This contrasts with the sample complexity results for general average-reward MDPs, and formally demonstrates the benefit of exploiting the weakly coupled structure in learning.

4.2 Main Results for RBs↩︎

Recall that for RBs, our plug-in learning approach uses the two-set policy as the reference policy. We first state a set of assumptions slightly adapted from the conditions that guarantee the \(O(\exp(-cN))\) optimality gap for the two-set policy [14].

Recall that \((y^\star(s,a))_{s\in\mathcal{S},a\in\mathcal{A}}\) is an optimal solution to the LP 7 , based on which we defined the optimal single-armed policy \(\bar\pi^\star\) in 13 . Let \(\mu^\star(s) \mathrel{\vcenter{:}}= y^\star(s, 0) + y^\star(s, 1)\) for all \(s\in\mathcal{S}\). It is easy to verify that \(\mu^\star\) is a stationary distribution for the single-armed MDP under policy \(\bar\pi^\star\). With these quantities, we define an \(S\times S\) matrix \(\Phi\) as follows \[\label{def:phi} \Phi \mathrel{\vcenter{:}}= P^{\Bar{\pi}^\star}-\mathbf{1}\mu^\star -\bigl(c^{\Bar{\pi}^\star}-\alpha\mathbf{1}\bigr)\bigl(P_{\tilde{s}1}-P_{\tilde{s}0}\bigr),\tag{14}\] where \(P^{\Bar{\pi}^\star}\) is the transition matrix of the Markov chain induced by \(\bar\pi^\star\), \(\mathbf{1}\) is the all-one column vector, \(c^{\Bar{\pi}^\star}\mathrel{\vcenter{:}}=\bigl(\bar\pi^\star(1\mid s)\bigr)_{s\in\mathcal{S}}\) is a column vector, and \(P_{sa}\mathrel{\vcenter{:}}= \bigl(P(s'\mid s,a)\bigr)_{s'\in\mathcal{S}}\) are row vectors. We will use several matrix norms, including the operator norm \(\left\lVert \cdot\right\rVert _{\mu^\star\to\mu^\star}\) induced by \(\mu^\star\), with detailed definitions in Appendix 14.2. We state the assumptions below, which are all independent of \(N\).

We remark that these assumptions are slightly stronger than those in [14]. In particular, the ergodicity assumption requires irreducibility while that paper requires unichain; the local stability assumption here is also slightly stronger since [14] assumes the moduli of all eigenvalues of \(\Phi\) are strictly less than \(1\).

We make a further assumption on the dual LP of the LP 7 , where the dual LP can be written as \[\label{eq:RB95dual95LP} \begin{align} \min_{\zeta,\lambda,(h(s))_{s\in\mathcal{S}}}\quad & \zeta - \alpha \lambda \\ \text{subject to}\quad & r(s,a)+\lambda\mathbb{I}\{a\!=\!1\} + \sum\nolimits_{s'\in\mathcal{S}} \! P(s'\mid s,a)\, h(s')\le\zeta + h(s),\;\; \forall s\in\mathcal{S},a\in\mathcal{A}. \end{align}\tag{15}\]

Assumption 3 is a dual non-degeneracy condition, which in general is a sufficient condition for a unique primal solution, and in our setting is actually an equivalent condition.

We highlight that we do not require uniform-mixing type assumptions. Instead, we only require ergodicity for the single-armed Markov chain induced by one policy, \(\bar\pi^\star\). Therefore, our analysis of the learned policy differs from established techniques based on uniform mixing. Interestingly, the assumptions that allow for an exponentially small optimality gap, after slightly strengthened into our Assumptions 2 and 3, also enables us to prove a perturbation analysis theorem (Theorem 3). This theorem shows that the single-armed policy \(\widehat{\Bar{\pi}}^\star\) solved from the empirical LP preserves key structural properties, including the identity of the neutral state and the local stability property under small transition-kernel perturbations. This establishes a form of robustness induced by the structural assumptions. We view this perturbation result as potentially of independent interest. The full statement of Theorem 3 is given in Section 4.3, the proof is given in Section 8. Based on Theorem 3, we obtain the main theorem for RBs. The proof is provided in Section 7, and the detailed proofs of the key lemmas are in Appendix 15.

Similarly to WCMDP, the optimality gap bound for \(\widehat{\pi}_{\mathrm{TS}}\) in Theorem 2 also consists of two terms. The first term is the finite-sample error that decreases at a rate \(1/{\sqrt{n}}\) with the sample size \(n\). The second term, \(C_4\exp(-C_5N)\), is inherited from the optimality gap of the two-set policy.

The bound in Theorem 2 also directly yields a sample complexity bound for achieving an optimality gap at most \(\epsilon\). However, since now the reference policy achieves a much smaller optimality gap, we can guarantee a gap level \(\epsilon=\Omega(\exp(-C_5N))\). To achieve any \(\epsilon=\Omega(\exp(-C_5N))\), the sample size needed is \(n=\Omega\left(\frac{(S + \log (SA/\eta))N^2}{\epsilon^2}\right)\). Now as long as we target an \(\epsilon=\Theta(1/\textrm{poly}(N))\), the total number of samples, \(SAn\), grows polynomially in \(N\).

4.2.0.1 Blocking in the fixed-sample regime.

The bound in Theorem 2 also suggests a simple modification when the sample size \(n\) is fixed, as in an offline setting. We partition the \(N\) arms into \(B\) disjoint blocks, each of size \(\bar N=N/B\), and run the plug-in two-set policy independently within each block. Since the RB is homogeneous, every block uses the same normalized budget \(\alpha\), so the block budgets add up to the original budget. The blocked policy, denoted by \(\widehat\pi_{\mathrm{TS}}^{\mathrm{blk}}\), simply combines the actions chosen by the block-level policies.

We only use block sizes for which Theorem 2 can still be applied. Let \(N_{\max}\) be the fixed lower bound on the system size in that theorem. Choose a sequence \(N_{\mathrm{blk}}=\omega(1)\) with \(N_{\mathrm{blk}}\ge N_{\max}\), and restrict to \(\bar N=\frac{N}{B}\ge N_{\mathrm{blk}}.\) The role of \(N_{\mathrm{blk}}\) is just to rule out blocks that are too small. If the blocks are too small, the large-\(N\) guarantee for the two-set policy no longer applies. Equivalently, we require \(B\le B_{\max}:=\left\lfloor\frac{N}{N_{\mathrm{blk}}}\right\rfloor .\)

Applying Theorem 2 to each block with failure probability \(\eta/B\), and then taking a union bound, gives with probability at least \(1-\eta\), \[\rho^\star(\boldsymbol{s}_0)-\rho^{\widehat\pi_{\mathrm{TS}}^{\mathrm{blk}}}(\boldsymbol{s}_0) \le \min\left\{ C_3\frac{N}{B} \frac{\sqrt{S+\log(SAB/\eta)}}{\sqrt n}, r_{\max} \right\} + C_4\exp\left(-C_5\frac{N}{B}\right).\]

This bound shows the tradeoff. The two terms in this bound move in opposite directions as \(B\) changes. Thus \(B\) should be chosen to balance these two terms, while keeping \(N/B\ge N_{\mathrm{blk}}\).

For example, if \(n=\Theta(N^2)\), the unblocked bound is \(\widetilde{O}(1)\). Taking \(B=\sqrt N\) gives blocks of size \(\sqrt N\), and the bound becomes \[\widetilde{O}\left(\frac{1}{\sqrt N}\right) + \exp(-\Theta(\sqrt N)).\] This demonstrates that the blocking scheme is beneficial when the sample size \(n\) is not large enough for the finite-sample error to be dominated by the optimality gap of the reference policy.

4.3 LP perturbation analysis↩︎

We now state the perturbation analysis theorem. We first introduce the vectorized true and perturbed primal-dual LPs used in the statement and proof.

4.3.0.1 Vectorized LP setup.

We first define vectorized versions of the primal and dual LPs corresponding to both the true and perturbed (that is, corresponding to \(P\) and \(\widehat{P}\)) systems.

4.3.0.2 True system LPs.

We define the LPs corresponding to the true system \(P\). We treat \(y\) as a row vector, define \(\tilde{e} \in \mathbb{R}^{SA}\) by \(\tilde{e}(sa) = \mathbb{I}(a = 1)\), and let \(J \in \mathbb{R}^{SA \times S}\) be the matrix such that \(e_{sa}^\top J = e_s^\top\). Here \(e_s \in \mathbb{R}^S\) denotes the vector such that \(e_s(s') = \mathbb{I}(s'=s)\), and likewise \(e_{sa} \in\mathbb{R}^{SA}\) has \(e_{sa}(s',a') = \mathbb{I}(s'=s,a'=a)\). Then we equivalently have the following primal and associated dual LPs.

To assist the reader in interpreting the matrix \(J\), we note that \(Jh \in \mathbb{R}^{SA}\) and \((Jh)(sa) = h(s)\). Also \(yJ = \mu\) where \(\mu(s) = y(s,0) + y(s,1)\). Lastly we present the complementary slackness property of solutions to the above LPs: if \(y\) is primal feasible and \(\zeta, \lambda, h\) are dual feasible, then they are said to satisfy the complementary slackness property if \[\begin{align} y \circ \left( r + \lambda \tilde{e} + Ph - \zeta \mathbf{1}- J h \right) = \mathbf{0}. \label{eq:LP95CS95true} \end{align}\tag{16}\]

4.3.0.3 Perturbed system LPs.

Next we analogously define the LPs corresponding to the perturbed systems (with transition kernel \(\widehat{P}\)). The perturbed primal and dual LPs are given as follows.

Finally, the complementary slackness condition for primal feasible \(y\) and dual feasible \(\zeta, \lambda, h\) is \[\begin{align} y \circ \left( r + \lambda \tilde{e} + \widehat{P}h - \zeta \mathbf{1}- J h \right) = \mathbf{0}. \label{eq:LP95CS95pert} \end{align}\tag{17}\]

The theorem involves the span seminorm \(\left\Vert \cdot\right\Vert _{\textrm{span}}\), defined as \(\left\Vert x\right\Vert _{\textrm{span}} = \max_{i} x_i - \min_i x_i\) for a vector \(x \in \mathbb{R}^S\). It also involves the matrix \(H_U=(I-\Phi)^{-1}-\mathbf{1}\mu^\star.\) The matrix \(H_U\) plays the role of a condition-number-like matrix. A more detailed explanation of \(H_U\) is given in Appendix 13. Now we state the theorem.

4.3.0.4 Interpretation of Theorem 3.

Theorem 3 describes how the LP solution changes when the transition kernel \(P\) is replaced by \(\widehat P\). Under Assumptions 2 and 3, the empirical LP preserves the main structural properties of the true LP.

Parts 1 and 2 show that the support structure of the optimal LP solution is stable. In particular, \(\widehat y^\star(s,a)=0 \Longleftrightarrow y^\star(s,a)=0.\) Therefore, by the construction in 13 , the empirical optimal single-arm policy can differ from the true optimal single-arm policy only at the neutral state. The neutral state is also preserved: \(\tilde{s}\) remains the unique state where both actions have positive mass. This matters because the two-set policy uses the neutral state to adjust the number of active arms and meet the budget constraint. Part 2 further shows that the positive entries of \(y^\star\) stay bounded away from zero after perturbation. Thus the empirical LP keeps a nontrivial amount of mass on the actions used by the true LP.

Parts 3–5 provide the stability bounds used in the Lyapunov analysis. Part 3 shows that local stability is preserved: \(1-\|\widehat\Phi\|_{\mu^\star\to\mu^\star} \ge \frac{1-\|\Phi\|_{\mu^\star\to\mu^\star}}{2}.\)This lets us define the empirical versions of the weighted matrices and the Lyapunov function. Part 4 gives explicit \(O(\delta)\) bounds on the changes in the primal and dual LP solutions, including \(\widehat y^\star\), \(\widehat h^\star\), \(\widehat\lambda^\star\), and \(\widehat\zeta^\star\). These bounds are then used in Part 5 to show that inactive actions still have positive dual slack after perturbation.

Finally, Part 6 shows that the Markov chain induced by the empirical single-arm policy \(\widehat{\bar\pi}^\star\) under the empirical kernel \(\widehat P\) is ergodic, with a controlled mixing time. This makes sure that the empirical stationary distribution and the empirical Lyapunov function are well-defined.

5 A Lyapunov Framework for Sample Complexity Analysis↩︎

In this section, we give an overview of our technical framework, which we believe is broadly applicable beyond WCMDPs and RBs. Our approach can be viewed as generalizing the classical simulation lemma. A key innovation is that we use Lyapunov drift bounds, rather than the Bellman equation, to derive performance difference between the true and empirical systems.

Let \(\pi\) be a reference policy and \(\widehat{\pi}\) be its empirical version computed from the empirical transition kernels. We use \(\,\widehat{\cdot}\,\) to denote the empirical version of a quantity in general, and we ignore the initial state for simplicity. Our goal is to bound the optimality gap of \(\widehat{\pi}\), which can be decomposed as \[\label{eq:decomp} \begin{align} \rho^{\star} - \rho^{\widehat{\pi}} \le \rho^{\mathrm{rel}} - \widehat{\rho}^{\pi} + \widehat{\rho}^{\pi} - \rho^{\widehat{\pi}} \le \bigl(\rho^{\mathrm{rel}} - \widehat{\rho}^{\pi}\bigr) + \bigl(\widehat{\rho}^{\mathrm{rel}} - \rho^{\widehat{\pi}}\bigr). \end{align}\tag{18}\] In the remainder of this section, we demonstrate our framework on deriving an upper bound for \(\rho^{\mathrm{rel}} - \widehat{\rho}^{\pi}\); the term \(\widehat{\rho}^{\mathrm{rel}} - \rho^{\widehat{\pi}}\) can be bounded in a similar manner.

If we were to use the classical simulation lemma, we would note \(\rho^{\mathrm{rel}}-\widehat{\rho}^{\pi} =\bigl(\rho^{\mathrm{rel}}-\rho^{\pi}\bigr) + \bigl(\rho^{\pi} -\widehat{\rho}^{\pi}\bigr)\), and then bound the second term as \(\rho^{\pi} -\widehat{\rho}^{\pi}= \widehat{\mathbb{E}}^{\pi} \big[(\boldsymbol{P}^{\pi}-\widehat{\boldsymbol{P}}^{\pi})h^{\pi}(Z_\infty) \big] \le \left\lVert \boldsymbol{P}^{\pi}-\widehat{\boldsymbol{P}}^{\pi}\right\rVert _{\infty \to \infty} \mathbb{E}\left[\left\Vert h^{\pi}(Z_\infty)\right\Vert _{\infty}\right]\), where \(h^{\pi}\) is the bias function of \(\pi\), and \(Z_{\infty}\) is the system state in steady state. However, a challenge to further proceed is that it is difficult to bound \(\left\Vert h^{\pi}(\cdot)\right\Vert _{\infty}\), as the bias function \(h^{\pi}\) can be complicated.

In our approach, we construct a Lyapunov function \(V\) explicitly, which essentially plays the role of the bias function \(h^{\pi}\). However, because \(V\) is a design choice, we can choose it to ensure \(\left\Vert V(\cdot)\right\Vert _{\infty}\) has a desirable bound. In particular, our framework has two steps, described below.

5.0.0.1 Step 1: Lyapunov analysis

This step follows the classical Lyapunov analysis, which has a long history in the study of stochastic systems. The goal is to construct a Lyapunov function \(V\) that satisfies the following two conditions.

1. Drift bound: For each state \(z\), \[\label{eq:matrix-drift} [(\boldsymbol{P}^{\pi}-I)V](z)\le -C_0 F(z)+G_1(N),\tag{19}\] where \(F\) is a function of the state, \(C_0>0\) is a constant independent of \(N\), and \(G_1(N)\) is a term that may depend on \(N\).

2. Gap dominance: For each state \(z\), \[\label{eq:gap-dominance} \rho^{\mathrm{rel}}-r^\pi(z)\le C_0'F(z)+G_2(N),\tag{20}\] where \(r^{\pi}(z)=\mathbb{E}_{A\sim\pi(\cdot\mid z)}[r(z,A)]\), \(C_0'>0\) is a constant independent of \(N\), and \(G_2(N)\) is a term that may depend on \(N\).

With these conditions, one can bound the optimality gap of the policy \(\pi\). Specifically, we take expectations on both sides of 19 and 20 with respect to \(z\sim Z_{\infty}\), where \(Z_{\infty}\) follows the state stationary distribution of \(\pi\). This makes the left-hand-sides of 19 and 20 equal to \(0\) and \(\rho^{\mathrm{rel}}-\rho^{\pi}\), respectively. Combining the two inequalities then yields \(\rho^{\mathrm{rel}}-\rho^{\pi} \le \frac{C_0'}{C_0}G_1(N)+G_2(N).\) This approach has been used in  [13] and [14] to derive optimality gap bounds for the ID policy and the two-set policy, respectively.

5.0.0.2 Step 2: Drift transfer

We next transfer the drift bound in (C1) from the true system to the empirical system. The key observation is that, for the same Lyapunov function \(V\), \[[(\widehat{\mathbf{P}}^{\pi}-I)V](z) = [(\mathbf{P}^{\pi}-I)V](z) + [(\widehat{\mathbf{P}}^{\pi}-\mathbf{P}^{\pi})V](z).\] Thus the empirical system inherits the true-system drift bound up to the model-error term \([(\widehat{\mathbf{P}}^{\pi}-\mathbf{P}^{\pi})V](z)\). Therefore, we have:

1. Drift bound: For each state \(z\), \[\begin{align} [(\widehat{\boldsymbol{P}}^{\pi}-I)V](z) \leq - C_0 F(z) + G_1(N) + [(\widehat{\boldsymbol{P}}^{\pi}-\boldsymbol{P}^{\pi})V](z). \label{eq:overview95drift95empirical} \end{align}\tag{21}\]

5.0.0.3 Completing the empirical performance bound

With Steps 1 and 2 in place, we are ready to bound the gap, \(\rho^{\mathrm{rel}} - \widehat{\rho}^{\pi}\), using [cond:drift-hat] and [cond:dominance]. This follows the same procedure as in deriving an optimality gap bound using [cond:drift] and [cond:dominance]. We take expectations on both sides of 21 and 20 with respect to \(z\sim Z_{\infty}\), where \(Z_{\infty}\) follows the state stationary distribution of \(\pi\) in the empirical system. Again the left-hand-side of 21 becomes \(0\). This gives \[\begin{align} \rho^{\mathrm{rel}}-\widehat{\rho}^{\pi} &\le \frac{C_0'}{C_0}G_1(N)+G_2(N)+\frac{C_0'}{C_0}\widehat{\mathbb{E}}^{\pi}\left[[(\widehat{\boldsymbol{P}}^{\pi}-\boldsymbol{P}^{\pi})V](Z_{\infty})\right]\\ &\le \frac{C_0'}{C_0}G_1(N)+G_2(N)+\frac{C_0'}{C_0} \left\lVert \boldsymbol{P}^{\pi}-\widehat{\boldsymbol{P}}^{\pi}\right\rVert _{\infty \to \infty} \mathbb{E}\left[\left\Vert V(Z_\infty)\right\Vert _{\infty}\right]. \label{eq:overview95empirical95perf95bound952} \end{align}\tag{22}\] From this bound we can see that it suffices to bound \(\left\Vert V(\cdot)\right\Vert _{\infty}\). This is typically more tractable than bounding \(\left\Vert h^{\pi}(\cdot)\right\Vert _{\infty}\) since our construction of \(V\) is explicit. Lemma formalizes this drift-transfer step in a form that we will repeatedly use in the proofs, whose proof is given in Appendix.

These steps suggest that our framework may be applicable to a much broader set of problems, given that the reference policy admits a Lyapunov analysis with a well-behaved Lyapunov function.

6 Proof of Theorem 1↩︎

We employ the framework in Section 5 to prove Theorem 1. According to the decomposition 18 , it suffices to bound \(\rho^{\mathrm{rel}}-\widehat\rho^{\pi_{\mathrm{ID}}}(\boldsymbol{s}_0)\) and \(\widehat\rho^{\mathrm{rel}}-\rho^{\widehat{\pi}_{\mathrm{ID}}}(\boldsymbol{s}_0)\) separately.

6.0.0.1 Proof roadmap.

The proof has three main parts. First, we bound \(\rho^{\mathrm{rel}}-\widehat\rho^{\pi_{\mathrm{ID}}}(\boldsymbol{s}_0)\), where the ID policy is computed from the true model and evaluated under the empirical model. This step uses the ID policy Lyapunov drift condition from Lemma 5 and the gap dominance bound from Lemma 6, which correspond to Conditions [cond:drift] and [cond:dominance] in our framework. Together with the drift transfer technique, they give Lemma 3.

Second, we bound \(\widehat\rho^{\mathrm{rel}}-\rho^{\widehat{\pi}_{\mathrm{ID}}}(\boldsymbol{s}_0)\), where the ID policy is computed from the empirical model and evaluated under the true model. The argument is parallel, but it first verifies that the empirical single-arm chains are well behaved. The empirical drift and dominance bounds, Lemmas 25 and 26, then give Lemma 4.

Both Lemma 3 and Lemma 4 use model-accuracy lemmas, which we state next. Figure 5 summarizes the main proof steps. We omit the auxiliary model-accuracy lemmas from the figure.

6.0.0.2 Model accuracy.

In order to get the final result, we firstly show the model accuracy lemmas we used, whose proofs are deferred to Appendix 12.1. We begin with a standard concentration bound for the empirical estimate of each single-armed transition kernel. The next lemma gives a uniform \(\ell_1\) bound over all arms \(i\in[N]\) and all state-action pairs \((s,a)\in\mathcal{S}\times\mathcal{A}\).

We next lift the single-armed model accuracy bound to the \(N\)-armed system. The error accumulates across arms, which leads to an additional factor of \(N\). The same bound also holds for the transition matrices induced by any fixed policy.

We now state the two Lemma 3 and Lemma 4.

Here we provide the proof of Lemma 3 to illustrate how our Lyapunov framework is applied; the proof of Lemma 4 is deferred to the Appendix 12.2.

6.0.0.3 Proof of Lemma 3

We leverage the Lyapunov function \(V\) constructed in [13] for analyzing the optimality gap of the ID policy in WCMDP. In particular, the function \(V\) is defined in 33 with respect to the one-hot representation of the system state \(\boldsymbol{S}_t\), denoted as \(\boldsymbol{X}_t.\) Specifically, \(X_{i,t} = (X_{i,t}(s))_{s\in\mathbb{S}} \in \mathbb{R}^{S}\), where \(X_{i,t}(s)=1\) if \(S_{i,t}=s\) and \(0\) otherwise.

6.0.0.4 Step 1: Lyapunov analysis

We show that the Lyapunov function \(V\) satisfies [cond:drift] and [cond:dominance] in our framework, stated formally as Lemma 5 and Lemma 6, respectively.

All constants above depend on the MDP parameters only through the mixing-time upper bound \(\tau_{\mathrm{unif}}\).

The proof of Lemma 6 follows the same argument as [13]; we omit it here.

That is, our Lyapunov function \(V\) satisfies [cond:drift] and [cond:dominance] with \(F(\boldsymbol{x})=V(\boldsymbol{x}),\) \(G_1(N)=K_V/\sqrt{N}\) and \(G_2(N)={2r_{\max}K_{\mathrm{conf}}}/{\sqrt{N}}\).

6.0.0.5 Step 2: Drift transfer.

The following lemma formalizes this drift-transfer step in a reusable form. In the lemma, \(Q\) denotes the transition matrix under which the Lyapunov drift inequality is available, while \(P\) denotes the transition matrix under which the long-run performance is evaluated. The proof is a finite-horizon telescoping argument and is given in Appendix 10.

We now apply Lemma 7 with \(Q=\boldsymbol{P}^{\pi_{\mathrm{ID}}}, P=\widehat{\boldsymbol{P}}^{\pi_{\mathrm{ID}}}, R=\rho^{\mathrm{rel}}, F=V, \bar r=r^{\pi_{\mathrm{ID}}}.\) Lemmas 5 and 6 give the required drift and dominance inequalities with \[C_0=\rho_V, \qquad C_0'=\frac{2r_{\max}+L_h}{L_h}, \qquad G_1(N)=\frac{K_V}{\sqrt N}, \qquad G_2(N)=\frac{2r_{\max}K_{\mathrm{conf}}}{\sqrt N}.\] Hence, \[\begin{align} \rho^{\mathrm{rel}}-\widehat\rho^{\pi_{\mathrm{ID}}}(\boldsymbol{s}_0) \le \frac{2r_{\max}+L_h}{L_h\rho_V} \sup_{\boldsymbol{x}} \left| (\widehat{\boldsymbol{P}}^{\pi_{\mathrm{ID}}}-\boldsymbol{P}^{\pi_{\mathrm{ID}}})V(\boldsymbol{x}) \right| + \left[ \frac{(2r_{\max}+L_h)K_V}{L_h\rho_V} + 2r_{\max}K_{\mathrm{conf}} \right]\frac{1}{\sqrt N}. \end{align}\] By Lemma 2, \(\left\lVert \widehat{\boldsymbol{P}}^{\pi_{\mathrm{ID}}}-\boldsymbol{P}^{\pi_{\mathrm{ID}}}\right\rVert _{\infty \to \infty} \le N\delta .\) Moreover, \(\|V\|_\infty\le L_h\) according to 35 . Therefore, \[\begin{align} \sup_{\boldsymbol{x}} \left| (\widehat{\boldsymbol{P}}^{\pi_{\mathrm{ID}}}-\boldsymbol{P}^{\pi_{\mathrm{ID}}})V(\boldsymbol{x}) \right| \le \left\lVert \widehat{\boldsymbol{P}}^{\pi_{\mathrm{ID}}}-\boldsymbol{P}^{\pi_{\mathrm{ID}}}\right\rVert _{\infty \to \infty}\|V\|_\infty \le L_hN\delta . \end{align}\] Substituting this bound gives the desired result.

6.0.0.6 Completing the proof of Theorem 1

To combine Lemma 3 and Lemma 4 to obtain Theorem 1, what is left to do is to connect the single-armed model accuracy \(\delta\) to the number of samples \(n\). First, we notice that when \(n\le\left(2S\log2+2\log(SAN/\eta)\right)16\tau^2S^2(5+\log_2S)^2,\) we can choose \(C_1=8\tau(5+\log_2S)\) so that \[\rho^\star(\boldsymbol{s}_0)-\rho^{\widehat{\pi}_{\mathrm{ID}}}(\boldsymbol{s}_0)\le 1\le C_1N\sqrt{\frac{S + \log (SAN/\eta)}{n}}+\frac{C_2}{\sqrt{N}} .\] Therefore, we only need to consider the case where \(n\ge\left(2S\log2+2\log(SAN/\eta)\right)16\tau^2S^2(5+\log_2S)^2.\) In this case, according to Lemma 1, we have the single-armed model accuracy: \[\max_{i\in [N]}\max_{s \in \mathcal{S},\;a \in \mathcal{A}} \left\| \widehat{P}_i(\cdot \mid s, a) - P_i(\cdot \mid s, a) \right\|_1 \le \delta\triangleq \sqrt{\frac{2S \log(2) + 2\log (SAN/\eta)}{n}}\le\frac{1}{4\tau S(5+\log_2S)}.\] with probability at least \(1-\eta\). In this case, the conditions of Lemma 3 and Lemma 4 are satisfied. It is straightforward to combine the results of these two lemmas, plus the fact that the reward from each arm is upper bounded by \(r_{\max}\), to get Theorem 1.

7 Proof of Theorem 2↩︎

We use the framework in Section 5 to prove Theorem 2. The proof follows the same decomposition as in 18 . It is sufficient to bound \(\rho^{\mathrm{rel}}-\widehat\rho^{\pi_{\mathrm{TS}}}(\boldsymbol{s}_0)\) and \(\widehat\rho^{\mathrm{rel}}-\rho^{\widehat{\pi}_{\mathrm{TS}}}(\boldsymbol{s}_0)\).

7.0.0.1 Proof roadmap.

The proof has two main intermediate bounds. First, we bound \(\rho^{\mathrm{rel}}-\widehat\rho^{\pi_{\mathrm{TS}}}(\boldsymbol{s}_0)\). Here the two-set policy is computed from the true model but is evaluated under the empirical model. We use the Lyapunov drift bound for the two-set policy (Lemma 31) and the gap-dominance bound (Lemma 32). These two lemmas correspond to Conditions [cond:drift] and [cond:dominance] in our Lyapunov framework. Together with the drift-transfer argument, they imply Lemma 9.

Second, we bound \(\widehat\rho^{\mathrm{rel}}-\rho^{\widehat{\pi}_{\mathrm{TS}}}(\boldsymbol{s}_0)\). Here the two-set policy is computed from the empirical model and evaluated under the true model. This part uses the same Lyapunov argument, but but it also uses Theorem 3 to justify the empirical Lyapunov analysis. Then the empirical drift condition (Lemma [lem:DC-Vhat-homo]) and the empirical gap dominance bound (Lemma 39) imply Lemma 10.

Both intermediate lemmas use model-accuracy lemma, which we state below. Figure 6 summarizes the main steps.

7.0.0.2 Model accuracy.

The model-accuracy lemma used for the homogeneous RB setting is a special case of the corresponding lemmas for the heterogeneous WCMDP setting. We state it below.

We now state Lemma 9 and Lemma 10.

Lemma 9 is proved in Appendix 15.1. Here we provide a proof outline of Lemma 10, which is the part where the perturbation analysis enters the proof of Theorem 2. The complete proof is deferred to Appendix 15.2. Unlike Lemma 9, which analyzes the true two-set policy, Lemma 10 analyzes the learned two-set policy \(\widehat{\pi}_{\mathrm{TS}}\) under the true model. Therefore, before applying the Lyapunov framework, we must first verify that the empirical LP solution preserves the structural properties required by the two-set policy and its Lyapunov analysis. We use Theorem 3 exactly for this purpose.

7.0.0.3 Proof outline of Lemma 10.

7.0.0.4 Step 1: Structural stability from the perturbation theorem.

Since the single-armed model accuracy satisfies the requirements of Theorem 3, the empirical LP preserves the key structure of the true LP. Therefore, the empirical two-set objects used below, including \(\widehat g\) and \(\widehat V\), are well-defined.

7.0.0.5 Step 2: Empirical Lyapunov analysis.

We now apply the two-set Lyapunov analysis to the empirical system. Let \(\Sigma_t = (\boldsymbol{X}_t,D_t^{\mathrm{OL}},D_t^{\widehat{\Bar{\pi}}^\star})\) denote the augmented state of the learned two-set policy, and let \(\widehat V\) be the empirical Lyapunov function constructed from \(\widehat y^\star\), \(\widehat\mu^\star\), and the perturbed local stability matrix \(\widehat{\Phi}\). The empirical two-set policy admits the following drift and gap-dominance bounds, stated formally as Lemmas [lem:DC-Vhat-homo] and 39, respectively. Informally, for every augmented state \(\sigma\), \[(\widehat{\boldsymbol{P}}^{\widehat{\pi}_{\mathrm{TS}}}-I)\widehat V(\sigma) \le -\frac{\widehat\gamma}{4(\widehat\beta+r_{\max})} \widehat g(\sigma) + 6\exp(8)S\widehat{\widetilde{V}}_{\max} \exp(-\widehat C N),\] and \(\widehat\rho^{\mathrm{rel}}-r^{\widehat{\pi}_{\mathrm{TS}}}(\sigma) \le \widehat g(\sigma).\) Thus, in the notation of the Lyapunov framework, the empirical Lyapunov function \(\widehat V\) satisfies Conditions [cond:drift] and [cond:dominance] with \(F(\sigma)=\widehat g(\sigma), C_0=\frac{\widehat\gamma}{4(\widehat\beta+r_{\max})}, G_1(N)=6\exp(8)S\widehat{\widetilde{V}}_{\max}\exp(-\widehat C N), C_0'=1, G_2(N)=0.\) The perturbation theorem is used here to ensure that the hatted objects appearing in these bounds are well-defined and that the empirical constants are uniformly controlled.

7.0.0.6 Step 3: Drift transfer.

The drift bound in Step 2 is for the empirical transition kernel \(\widehat{\boldsymbol{P}}^{\widehat{\pi}_{\mathrm{TS}}}\), while Lemma 10 concerns the performance of \(\widehat{\pi}_{\mathrm{TS}}\) under the true transition kernel \(\boldsymbol{P}^{\widehat{\pi}_{\mathrm{TS}}}\). We therefore apply Lemma 7 with \(Q=\widehat{\boldsymbol{P}}^{\widehat{\pi}_{\mathrm{TS}}}, P=\boldsymbol{P}^{\widehat{\pi}_{\mathrm{TS}}}, R=\widehat\rho^{\mathrm{rel}}, F=\widehat g, V=\widehat V, \bar r=r^{\widehat{\pi}_{\mathrm{TS}}}.\) Using the values of \(C_0,C_0',G_1(N),G_2(N)\) from Step 2, we obtain \[\begin{align} \widehat\rho^{\mathrm{rel}} - \rho^{\widehat{\pi}_{\mathrm{TS}}}(\boldsymbol{s}_0) \le& \frac{4(\widehat\beta+r_{\max})}{\widehat\gamma} \sup_{\sigma} \left| (\boldsymbol{P}^{\widehat{\pi}_{\mathrm{TS}}}-\widehat{\boldsymbol{P}}^{\widehat{\pi}_{\mathrm{TS}}}) \widehat V(\sigma) \right| + \frac{4(\widehat\beta+r_{\max})}{\widehat\gamma} 6\exp(8)S\widehat{\widetilde{V}}_{\max} \exp(-\widehat C N). \end{align}\] The model-error term is upper bounded by Lemma 45: \(\sup_{\sigma} \left| (\boldsymbol{P}^{\widehat{\pi}_{\mathrm{TS}}}-\widehat{\boldsymbol{P}}^{\widehat{\pi}_{\mathrm{TS}}}) \widehat V(\sigma) \right| \le \widehat V_{\max}N\delta.\) Substituting this bound into the display from Step 3 gives \[\begin{align} \widehat\rho^{\mathrm{rel}} - \rho^{\widehat{\pi}_{\mathrm{TS}}}(\boldsymbol{s}_0) \le& \frac{4\widehat V_{\max}(\widehat\beta+r_{\max})}{\widehat\gamma} N\delta + \frac{4(\widehat\beta+r_{\max})}{\widehat\gamma} 6\exp(8)S\widehat{\widetilde{V}}_{\max} \exp(-\widehat C N). \end{align}\]

7.0.0.7 Step 4: Replacing empirical constants by deterministic bounds.

Finally, Theorem 3 and the auxiliary well-definedness lemmas provide deterministic bounds on the empirical constants: \(\widehat\gamma\ge \widehat\gamma^{\mathrm{low}}, \widehat\beta\le \widehat\beta^{\max}, \|\widehat V\|_\infty\le \widehat V_{\max}, \widehat{\widetilde{V}}_{\max}<\infty.\) These bounds depend only on the original single-armed RB parameters, not on \(N,n,\eta\), or the initial state. Hence the previous display implies \[\widehat\rho^{\mathrm{rel}} - \rho^{\widehat{\pi}_{\mathrm{TS}}}(\boldsymbol{s}_0) \le C_7N\delta + 6\exp(8)S\widehat{\widetilde{V}}_{\max} \exp(-\widehat C N),\] for a constant \(C_7\) independent of \(N,n,\eta\), and \(\boldsymbol{s}_0\). This is Lemma 10.

7.0.0.8 Completing the proof of Theorem 2.

Combining Lemma 9 and Lemma 10 yields Theorem 2 once we relate the single-armed model accuracy parameter \(\delta\) to the sample size \(n\) under the generative model. First, we notice that when \(n\le\left(2S\log2+2\log(SA/\eta)\right)/\delta_{\min}^2,\) where \(\delta_{\min}\) is defined in ?? , we can choose \(C'=2/\delta_{\min}\), then \[\rho^\star(\boldsymbol{s}_0)-\rho^{\widehat{\pi}_{\mathrm{TS}}}(\boldsymbol{s}_0)\le 1\le C'N\sqrt{\frac{S + \log (SA/\eta)}{n}}+C''\exp(-C_5N).\] Therefore, we only need to consider the case when \(n\ge\left(2S\log2+2\log(SA/\eta)\right)/\delta_{\min}^2,\) In this case, according to Lemma 1, we have the single-armed model accuracy: \[\max_{s \in \mathcal{S},\;a \in \mathcal{A}} \left\| \widehat{P}(\cdot \mid s, a) - P(\cdot \mid s, a) \right\|_1 \le \delta\triangleq \sqrt{\frac{2S \log(2) + 2\log (SA/\eta)}{n}}\le\delta_{\min},\] with probability at least \(1-\eta\). We consider the case when \[\label{eq:def-Nmax} N\ge N_{\max}\triangleq\max\left\{\frac{4}{\min\{y^\star(\tilde{s},0),y^\star(\tilde{s},1)\}},\left(\frac{4M}{\gamma}\right)^2,\left(\frac{4\widehat{M}^{\mathrm{up}}}{\widehat{\gamma}^{\mathrm{low}}}\right)^2\right\},\tag{23}\] where \(M\) is defined in ?? , \(\gamma\) in 53 , \(\widehat{M}^{\mathrm{up}}\) in ?? and \(\widehat{\gamma}^{\mathrm{low}}\) in ?? . Based on these conditions, both the conditions of \(N\) and \(\delta\) in Lemmas 9 and 10 hold. Therefore, we can combine the results of these two lemmas by choosing \(C_3=C_6+C_7, C_4=6\exp(8)S(\tilde{V}_{\max}+\widehat{\tilde{V}}_{\max}) \text{ and } C_5=\min\{C,\widehat C\},\) which completes the proof.

8 Proof of Theorem 3↩︎

In this section we provide the proof of Theorem 3, which will be preceded by many intermediate lemmas, organized into three subsections 8.2, 8.3, 8.4 and 8.5. We firstly give a proof outline in 8.1 to show the high-level ideas.

8.1 Proof outline↩︎

The proof uses a primal-dual perturbation argument. Under the nondegeneracy and strict-gap assumptions, a small perturbation of the transition kernel should not change which LP constraints are active. We therefore build candidate primal and dual solutions for the perturbed LP using the same active structure as in the true LP. We then check primal feasibility, dual feasibility, complementary slackness, and uniqueness.

One complication is that the RB LP has a redundant flow-balance constraint, and the dual bias vector is only unique up to an additive constant. For this reason, we first perturb the state occupancy instead of perturbing the primal and dual variables directly. Around the optimal state occupancy \(\mu^\star\), the locally linear policy follows \(\Bar{\pi}^\star\) at all non-neutral states and uses the neutral state \(\tilde{s}\) to satisfy the budget. This gives the local linearization matrix \(U=P^{\Bar{\pi}^\star}-(c^{\Bar{\pi}^\star}-\alpha\mathbf{1})\xi\), where \(\xi=P_{\tilde{s}1}-P_{\tilde{s}0}\). Replacing \(P\) by \(\widehat{P}\) gives the perturbed matrix \(\widehat{U}\).

We define \(H_U=(I-\Phi)^{-1}-\mathbf{1}\mu^\star\) and \(\widehat{\mu} = \mu^\star\bigl(I-(\widehat{U}-U)H_U\bigr)^{-1}.\) The matrix \(H_U\) measures how sensitive the state occupancy is to the model perturbation. The key identity is \(\widehat{\mu}-\mu^\star=\widehat{\mu}(\widehat{U}-U)H_U.\) This is similar to the usual perturbation formula for stationary distributions of Markov chains, although \(U\) and \(\widehat{U}\) are not transition matrices.

After constructing \(\widehat{\mu}\), we use a linear map \(W\) to define the primal candidate \(\widehat{y}=\widehat{\mu}W\). The construction of \(W\) ensures that \(\widehat{y}\) satisfies the perturbed budget, flow-balance, and normalization constraints. It also preserves the support pattern: active entries of \(y^\star\) remain positive, while inactive entries remain zero. For the dual side, we construct \((\widehat{\zeta},\widehat{\lambda},\widehat{h})\) so that the perturbed dual constraints are tight on the active state-action pairs. The dual perturbation bounds then show that inactive constraints still have positive slack. Thus the constructed primal and dual candidates are feasible and satisfy complementary slackness, so they are optimal. The strict slack on inactive actions also gives uniqueness and support preservation.

Finally, support preservation implies that the empirical optimal single-arm policy can differ from the true one only at the neutral state. Together with a Markov-chain perturbation bound, this gives the aperiodicity, irreducibility, and mixing-time conclusion in the theorem.

8.2 Candidate state occupancy construction↩︎

Throughout the proof, fix an arbitrary policy \(\pi^\star\) which satisfies that \(\pi^\star(s)=\Bar{\pi}^\star(s)\) for all \(s \neq \tilde{s}\). It is straightforward to check that \(P^{\Bar{\pi}^\star} - (c^{\Bar{\pi}^\star} -\alpha \mathbf{1})\xi = P^{\pi^\star} - (c^{\pi^\star} -\alpha \mathbf{1})\xi\) where for any policy \(\pi\), \(c^{\pi}(s) = \pi(1 \mid s)\), and \(\xi\) is the row vector \(P_{\tilde{s}1}-P_{\tilde{s}0}\). We then define the local linearization matrix \(U\) and its perturbed analogue \[\begin{align} U = P^{\pi^\star} - (c^{\pi^\star} -\alpha \mathbf{1})\xi, \qquad \widehat{U}= \widehat{P}^{\pi^\star} - (c^{\pi^\star} -\alpha \mathbf{1})\widehat \xi, \end{align}\] where \(\widehat{\xi}\triangleq \widehat{P}_{\tilde{s}1}-\widehat{P}_{\tilde{s}0}\). We also define \(H_U = (I - (U - \mathbf{1}\mu^\star))^{-1} - \mathbf{1}\mu^\star.\) Note that \(U-\mathbf{1}\mu^\star=\Phi\), so the inverse \((I - (U - \mathbf{1}\mu^\star))^{-1}\) exists due to the local stability condition of Assumption 2. Finally we define the candidate state occupancy distribution \[\widehat{\mu}\triangleq \mu^\star (I - (\widehat{U}-U)H_U)^{-1}. \label{eq:muhat-definition}\tag{24}\] Such a definition requires the invertibility of \((I - (\widehat{U}-U)H_U)^{-1}\), so it suffices for now to require that we have \(\left\lVert (\widehat{U}-U)H_U\right\rVert _{\mu^\star\to\mu^\star}< 1\). This definition is motivated by the stationary distribution perturbation identity for Markov chains [52] and we can now verify that an analogous identity holds in our case:

Given this definition of \(\widehat{\mu}\) and Lemma 11, we can now also define the perturbed version of \(H_U\): \(H_{\widehat{U}} = (I - (\widehat{U}- \mathbf{1}\widehat{\mu}))^{-1} - \mathbf{1}\widehat{\mu}.\) This definition requires the invertibility of \((I - (\widehat{U}- \mathbf{1}\widehat{\mu}))\), which is provided by the following lemma.

Lemma 12 is proved in 13.3 and we encourage interested readers to read 13.2 for additional properties of \(U, \widehat{U}, \mu^\star, \widehat{\mu}, H_U\), and \(H_{\widehat{U}}\).

8.3 Perturbed primal LP solution construction↩︎

We next construct candidate solutions for the primal and dual perturbed LPs 3 and 4, and then verify their feasibility and optimality.

We first construct the candidate solution for the perturbed primal LP. By the constraint [eq:true95primal95arm95frac95const] of the true primal LP, we have \(y^\star\tilde{e}=\alpha\). Moreover, by the nondegeneracy assumption, for all \(s\neq\tilde{s}\), \(y^\star(s,a)=\mu^\star(s)\mathbb{I}\{\pi^\star(a\mid s)=1\}\). Therefore, we can reconstruct \(y^\star\) from \(\mu^\star\) by using the form of \(\pi^\star\), and then use \(y^\star\tilde{e}=\alpha\) to determine \(y^\star(\tilde{s},0)\) and \(y^\star(\tilde{s},1)\). Hence \(y^\star\) satisfies \[\begin{align} y^\star(s,a) &= \mu^\star(s) \pi^\star(a \mid s) \quad \forall s \neq \tilde{s}, \\ y^\star(\tilde{s},1) &= \alpha -\sum_{s \neq \tilde{s}} \pi^\star(1 \mid s) \mu^\star(s) =\alpha\left(\mu^\star \mathbf{1}\right) -\sum_{s \neq \tilde{s}} \pi^\star(1 \mid s) \mu^\star(s), \\ y^\star(\tilde{s},0) &= (1 - \alpha) - \sum_{s \neq \tilde{s}} \pi^\star(0 \mid s) \mu^\star(s) = (1 - \alpha)\left(\mu^\star \mathbf{1}\right) - \sum_{s \neq \tilde{s}} \pi^\star(0 \mid s) \mu^\star(s). \end{align}\] We wrote the last two equations using \(1=\mu^\star\mathbf{1}\) so that the above display defines a linear system with matrix \(W\) satisfying \(y^\star=\mu^\star W\). Using the same linear map, we define the candidate solution \(\widehat{y}\) by \(\widehat{y}=\widehat{\mu}W\). This construction also ensures that \(\widehat{y}(s,a)=0\) for all \((s,a)\) such that \(y^\star(s,a)=0\). The matrix \(W\) will play a key role in all of our subsequent analysis. Clearly its definition is closely related to the assumed form of \(\mu^\star\) and \(y^\star\). The following lemma guarantees the feasibility of \(\widehat{y}\) and is proved in 13.3.

8.4 Perturbed dual LP solution construction↩︎

Next we construct the candidate dual solution \((\widehat{\zeta}, \widehat{\lambda}, \widehat{h})\). We note that the complementary slackness property 16 of the true LP, combined with the assumed form of \(y^\star\), implies that for all \(i=(s,a)\) such that \(y_i^\star > 0\) we have \[\begin{align} r(i) + \lambda \tilde{e}_i + P_{i}h = \zeta + h(s), \label{eq:true95CS95equality95consequence} \end{align}\tag{25}\] which will be used to guide the candidate dual construction. The following lemma gives a more explicit form of the solution to the true dual LP which will eventually prove useful, and also motivates the candidate perturbed dual solution which will be constructed below.

Lemma 14 is proved in 13.4. We now construct the candidate dual solution. Motivated by Lemma 14, define \(\widehat{h}= H_{\widehat{U}}Wr.\) It remains to define \(\widehat{\lambda}\) and \(\widehat{\zeta}\). Since 25 holds for both \((\tilde{s}, 0)\) and \((\tilde{s}, 1)\), we have the “equal Q-function” property for the neutral state that \(r(\tilde{s},0) + P_{\tilde{s}0} h^\star = r(\tilde{s},1) + \lambda^\star + P_{\tilde{s}1} h^\star.\) We choose \(\widehat{\lambda}\) so that the same indifference holds for the perturbed dual candidate: \(r(\tilde{s},0)+\widehat{P}_{\tilde{s}0}\widehat{h} = r(\tilde{s},1)+\widehat{\lambda}+\widehat{P}_{\tilde{s}1}\widehat{h}.\) Equivalently, we set \[\begin{align} \widehat{\lambda} = r(\tilde{s},0)-r(\tilde{s},1)-\widehat{\xi}\widehat{h}. \label{eq:lambdahat95defn} \end{align}\tag{26}\] Finally, as noted in the proof of Lemma 14, the equality of the objective values for the optimal solutions to the primal and dual LPs implies that \(\zeta^\star = \mu^\star Wr + \lambda^\star \alpha\), so we define \(\widehat{\zeta}\) as \[\begin{align} \widehat{\zeta}= \widehat{\mu}W r + \widehat{\lambda}\alpha, \label{eq:zetahat95defn} \end{align}\tag{27}\] so that the perturbed dual objective matches the objective value of the candidate primal solution.

Now having defined \((\widehat{\zeta}, \widehat{\lambda}, \widehat{h})\), we find conditions for their dual feasibility. The only constraint which we need to check is [eq:pert95dual95ineq]. We check each row of [eq:pert95dual95ineq], dividing them into two cases based on whether the constraint will hold with equality or inequality. First we handle the equality case.

This lemma shows that the dual constraints are active on the support of \(y^\star\). However, this is not yet enough for dual feasibility. We still need to check that the dual constraints also hold for the inactive pairs \((s,a)\) with \(y^\star(s,a)=0\). The next lemma shows that the dual variables only change by a small amount, so dual constraints still have positive slacks after perturbation.

The first part of the lemma controls how much the dual variables move. The last inequality shows that every inactive pair \((s,a)\) still has positive dual slack after perturbation. Combining this with Lemma 15, the perturbed dual constraints are tight on the support of \(y^\star\) and strictly slack outside the support. Hence the candidate dual solution is feasible, and together with the primal solution from Section 8.3, we obtain these candidates have the same objective value and satisfy complementary slackness. Therefore they are optimal for the perturbed primal and dual LPs. Lemma 15 and Lemma [lem:pert95dual95LP95ineq95consts] are proved in 13.5.

8.5 Completing the proof of Theorem 3↩︎

First we confirm the optimality of the constructed candidate solutions \(\widehat{y}\) and \((\widehat{\zeta}, \widehat{\lambda}, \widehat{h})\) for their respective LPs. Lemma [lem:yhat95pert95and95feasibility] guarantees primal feasibility of \(\widehat{y}\), and Lemmas 15 and [lem:pert95dual95LP95ineq95consts] guarantee dual feasibility of \((\widehat{\zeta}, \widehat{\lambda}, \widehat{h})\). Since by construction these primal and dual solutions have the same objective value of \(\widehat{\mu}W r = \widehat{\zeta}- \alpha \widehat{\lambda}\), they are both optimal. The next lemma shows the uniqueness of both the primal and dual solutions and is proved in 13.6.

The following lemma which is proved in 13.7 checks the perturbation bounds from the statement of the theorem and confirm that all assumptions are satisfied for all the lemmas used in the proof.

Now it remains to prove the Markov-chain conclusion. which is guaranteed by the following lemma and its proof is contained in 13.8.

We now match the numbered conclusions in the theorem. Part 1 follows from the support preservation in Lemma 13. Since the support is unchanged, the neutral state \(\tilde{s}\) is also preserved. Part 2 is the lower bound \(\widehat{y}\ge y^\star/2\) from Lemma 13. Part 3 follows from Lemma 12. After support preservation, the perturbed locally linear policy is the one induced by \(\widehat{\Bar{\pi}}^\star\), so \(\widehat{U}-\mathbf{1}\widehat{\mu}\) is the perturbed local-stability matrix \(\widehat{\Phi}\). Part 4 follows from Lemma 13 and Lemma 16, together with \(\left\lVert \widehat{U}-U\right\rVert _{\infty \to \infty}\le 3\delta, \left\lVert \widehat{\xi}-\xi\right\rVert _{\infty \to \infty}\le 2\delta.\) Part 5 is the strict-gap conclusion in Lemma 16, after using the support preservation from Part 1. Finally, Part 6 is Lemma 19. This proves all parts of Theorem 3.

9 Additional Notation↩︎

9.0.0.1 Basic notation.

Let \(\mathbb{R}\), \(\mathbb{N}\), and \(\mathbb{N}_+\) denote the sets of real numbers, nonnegative integers, and positive integers, respectively. For \(n \leq n'\) with \(n,n' \in \mathbb{N}_+\), define \([n] \triangleq \{1,2,\dots,n\}\) and \([n:n'] \triangleq \{n,n+1,\dots,n'\}\). We also define the grid \([0,1]_n \triangleq \left\{\frac{i}{n}\;\middle|\;i\in\mathbb{N},\;0\le \frac{i}{n}\le 1\right\}\). For vectors \(u,v\in\mathbb{R}^{S}\), we use the inner product \(\langle u,v\rangle \triangleq \sum_{s\in\mathcal{S}} u(s)v(s)\).

9.0.0.2 Asymptotic notation.

We use standard Bachmann–Landau notation \(O(\cdot)\), \(\Omega(\cdot)\), \(\Theta(\cdot)\), \(o(\cdot)\), and \(\omega(\cdot)\). We also use \(\widetilde{O}(\cdot)\), \(\widetilde{\Omega}(\cdot)\), and \(\widetilde{\Theta}(\cdot)\) to hide logarithmic factors in problem parameters such as \(n\), \(N\), \(S\), \(A\), and \(1/\eta\).

Symbol	Meaning
\(\mathcal{S}, \mathcal{A}\)	State and Action space of each arm
\(S,A\)	Cardinality of the state and action space, \(S = |\mathcal{S}|, A=|\mathcal{A}|\)
\(s,a\)	one-dimension state and action
\(\boldsymbol{s},\boldsymbol{a}\)	\(N\)-dimension state and action
\(P(\cdot \mid s,a)\)	True transition probability given \((s,a)\) for single arm
\(\widehat{P}(\cdot \mid s,a)\)	Estimated transition probability given \((s,a)\) for single arm
\(\boldsymbol{P}(\cdot \mid \boldsymbol{s},\boldsymbol{a})\)	True transition probability given \((\boldsymbol{s},\boldsymbol{a})\) for the \(N\)-arm system
\(\widehat{\boldsymbol{P}}(\cdot \mid \boldsymbol{s},\boldsymbol{a})\)	Estimated transition probability given \((\boldsymbol{s},\boldsymbol{a})\) for the \(N\)-armed system
\(\Bar{\pi}^\star\)	Optimal single-armed policy for the true system
\(\widehat{\Bar{\pi}}^\star\)	Optimal single-armed policy for the empirical system
\(\mu^{\star}\)	Stationary distribution obtained by running \(\bar{\pi}^{\star}\) under the true MDP
\(\widehat{\mu}^{\star}\)	Stationary distribution obtained by running \(\widehat{\Bar{\pi}}^\star\) under the empirical MDP
\(P^{\pi}\)	One-step transition matrix induced by a policy \(\pi\)
\(P^{\pi,\infty}\)	Limiting transition matrix of the Markov chain under policy \(\pi\)
\(\|\cdot\|_{1}\)	\(\ell_{1}\) norm of a vector
\(\mathbf{1}\)	All-ones vector
\(\mathbb{I}\)	Indicator function
\(\lambda_{W}\)	Maximal eigenvalue of a matrix \(W\)
\(\mathbb{E}^\pi\)	Expectation under policy \(\pi\) and the true transition kernel \(\boldsymbol{P}\)
\(\widehat{\mathbb{E}}^\pi\)	Expectation under policy \(\pi\) and the empirical transition kernel \(\widehat{\boldsymbol{P}}\)
\(\rho^\pi\)	Average reward of policy \(\pi\) under true model
\(\widehat{\rho}^\pi\)	Average reward of policy \(\pi\) under empirical model

10 Common Technical Lemmas↩︎

This section collects the proof of Lemma 7 together with several finite-state Markov-chain perturbation bounds used later in the proofs.

Proof. Proof of Lemma 7. Fix an arbitrary initial state \(z_0\), and let \(\Delta:=\sup_{z\in\mathcal{Z}}|[(P-Q)V](z)|\). Since \(\mathcal{Z}\) is finite, for every function \(f:\mathcal{Z}\to\mathbb{R}\), the Cesaro average \(T^{-1}\sum_{t=0}^{T-1}\mathbb{E}_P[f(Z_t)\mid Z_0=z_0]\) exists.

For every \(z\in\mathcal{Z}\), we have \((P-I)V(z)=(Q-I)V(z)+(P-Q)V(z)\le -C_0F(z)+G_1(N)+\Delta\). Averaging this inequality along the Markov chain governed by \(P\), we obtain, for every \(T\ge1\), \[\frac{\mathbb{E}_P[V(Z_T)\mid Z_0=z_0]-V(z_0)}{T} \le -C_0 \frac{1}{T} \sum_{t=0}^{T-1} \mathbb{E}_P[F(Z_t)\mid Z_0=z_0] + G_1(N)+\Delta .\] Since \(\mathcal{Z}\) is finite, \(V\) is bounded, so \((\mathbb{E}_P[V(Z_T)\mid Z_0=z_0]-V(z_0))/T\to0\). Rearranging the previous display and taking limits gives \[\label{eq:limF} \lim_{T\to\infty} \frac{1}{T} \sum_{t=0}^{T-1} \mathbb{E}_P[F(Z_t)\mid Z_0=z_0] \le \frac{G_1(N)+\Delta}{C_0}.\tag{28}\] Next, averaging \(R-\bar r(z)\le C_0'F(z)+G_2(N)\) along the same trajectory gives, for every \(T\ge1\), \[R- \frac{1}{T} \sum_{t=0}^{T-1} \mathbb{E}_P[\bar r(Z_t)\mid Z_0=z_0] \le C_0' \frac{1}{T} \sum_{t=0}^{T-1} \mathbb{E}_P[F(Z_t)\mid Z_0=z_0] + G_2(N).\] Taking limits on both sides yields \[R-\rho_P(z_0) \le C_0' \lim_{T\to\infty} \frac{1}{T} \sum_{t=0}^{T-1} \mathbb{E}_P[F(Z_t)\mid Z_0=z_0] + G_2(N).\] Combining this inequality with 28 we can get the desired result. ◻

Lemma 20. Let \(Q, \widetilde{Q}\) be two Markov transition matrices on the same finite state space \(\mathcal{Z}\). Suppose that the chain \(Q\) is unichain, aperiodic, and has mixing time bounded by \(\tau\). Then if \(\left\lVert \widetilde{Q} - Q\right\rVert _{\infty \to \infty} \leq \frac{1}{4|\mathcal{Z}|\tau (5 + \log_2 |\mathcal{Z}|)}\), the Markov chain \(\widetilde{Q}\) is unichain, aperiodic, and has mixing time bounded by \((3 + \log_2 |\mathcal{Z}|) \tau\).

Let \(Q^\infty = \mathbf{1}\mu^\top\) for some \(\mu\), which is a valid expression since \(Q\) is unichain and aperiodic. Suppose \(\left\lVert \widetilde{Q} - Q\right\rVert _{\infty \to \infty} \leq\delta\). Let \(t\ge\tau\) be a positive integer which we will choose later. By triangle inequality \(\left\lVert \widetilde{Q}^t - Q^\infty\right\rVert _{\infty \to \infty} \leq \left\lVert \widetilde{Q}^t - Q^t\right\rVert _{\infty \to \infty} + \left\lVert Q^t - Q^\infty\right\rVert _{\infty \to \infty} .\) Now we bound each of these terms. First, \(\widetilde{Q}^t - Q^t=\sum_{k=0}^{t-1}\widetilde{Q}^{t-1-k}(\widetilde{Q}-Q)Q^k,\) and so \[\begin{align} \left\lVert \widetilde{Q}^t - Q^t\right\rVert _{\infty \to \infty} \le & \sum_{k=0}^{t-1}\left\lVert \widetilde{Q}^{t-1-k}\right\rVert _{\infty \to \infty}\left\lVert \widetilde{Q}-Q\right\rVert _{\infty \to \infty}\left\lVert Q^k\right\rVert _{\infty \to \infty} \leq \sum_{k=0}^{t-1}1\cdot\delta\cdot 1 \leq t \delta \end{align}\] since each \(\widetilde{Q}^{t-k} Q^{k-1}\) (for \(k = 1, \dots, t\)) is a stochastic matrix and thus has \(\left\lVert \cdot\right\rVert _{\infty \to \infty}\) equal to \(1\). By Lemma 21 we have \(\left\lVert Q^t - Q^\infty\right\rVert _{\infty \to \infty}\le2^{-\lfloor t/\tau\rfloor}.\) Combining the above two results, we have \(\left\lVert \widetilde{Q}^t- Q^\infty\right\rVert _{\infty \to \infty}\leq t \delta + 2^{-\lfloor t/\tau\rfloor}< t \delta + 2^{- t/\tau+1}.\) We can choose \(t=(3+\log_2 |\mathcal{Z}|)\tau\), \(\delta=\frac{1}{2|\mathcal{Z}|\tau(3+\log_2|\mathcal{Z}|)}\) so that \(\left\lVert \widetilde{Q}^t - Q^\infty\right\rVert _{\infty \to \infty} < \frac{1}{|\mathcal{Z}|}\). Then, notice \(Q^\infty = \mathbf{1}\mu^\top\), we have \(\max_{z\in\mathcal{Z}} \mu(z) \geq \frac{1}{|\mathcal{Z}|}\) by a standard argument. Let \(z^\star\) have \(\mu(z^\star) \geq \frac{1}{|\mathcal{Z}|}\). Then for all states \(z_0\), we have \[\begin{align} e_{z_0}^\top \widetilde{Q}^{t} e_{z^\star} &\geq e_{z_0} Q^\infty e_{z^\star} - e_{z_0}^\top (Q^\infty - \widetilde{Q}^{t})e_{z^\star} \\ & \geq e_{z_0} \widetilde{Q}^\infty e_{z^\star} - \left\lVert e_{z_0}^\top\right\rVert _{\infty \to \infty} \left\lVert Q^\infty - \widetilde{Q}^{t}\right\rVert _{\infty \to \infty} \left\Vert e_{z^\star}\right\Vert _{\infty} \\ &= \mu(z^\star) - \left\lVert Q^\infty - \widetilde{Q}^{t}\right\rVert _{\infty \to \infty} > \frac{1}{|\mathcal{Z}|} - \frac{1}{|\mathcal{Z}|} = 0. \end{align}\] Therefore we have shown that for any \(z_0\), there is positive probability of reaching \(z^\star\) after \(t\) steps. Therefore if \(z_0\) is recurrent, then \(z^\star\) is also recurrent and they are in the same minimal closed recurrent class. Thus all recurrent classes contain \(z^\star\), so there is only one recurrent class, and thus by definition \(\widetilde{Q}\) is unichain.

Next we bound \(\left\lVert \widetilde{Q}^t - \widetilde{Q}^\infty\right\rVert _{\infty \to \infty}\). By triangle inequality \(\left\lVert \widetilde{Q}^t - \widetilde{Q}^\infty\right\rVert _{\infty \to \infty} \leq \left\lVert \widetilde{Q}^t - Q^t\right\rVert _{\infty \to \infty} + \left\lVert Q^t - Q^\infty\right\rVert _{\infty \to \infty} + \left\lVert Q^\infty - \widetilde{Q}^\infty\right\rVert _{\infty \to \infty}.\) We have already bounded the first two terms. For the third term we have \(\widetilde{Q}^\infty - Q^\infty = \widetilde{Q}^\infty \widetilde{Q} - Q^\infty Q = \widetilde{Q}^\infty (\widetilde{Q} - Q) + (\widetilde{Q}^\infty - Q^\infty)Q,\) which implies \((\widetilde{Q}^\infty - Q^\infty)(I-Q) =\widetilde{Q}^\infty (\widetilde{Q} - Q).\) Right-multiplying by \(H_Q\) we have \(\widetilde{Q}^\infty (\widetilde{Q} - Q)H_Q = (\widetilde{Q}^\infty - Q^\infty)(I-Q)H_Q = (\widetilde{Q}^\infty - Q^\infty)(I-Q^\infty) = \widetilde{Q}^\infty - Q^\infty\) using the fact that \(\widetilde{Q}^\infty Q^\infty = \widetilde{Q}^\infty \mathbf{1}\mu^\top = \mathbf{1}\mu^\top = Q^\infty\). Hence, \[\begin{align} \left\lVert Q^\infty - \widetilde{Q}^\infty\right\rVert _{\infty \to \infty} &= \left\lVert \widetilde{Q}^\infty (\widetilde{Q}- Q) H_{Q}\right\rVert _{\infty \to \infty}\\ &\leq \left\lVert \widetilde{Q}^\infty\right\rVert _{\infty \to \infty} \left\lVert \widetilde{Q}- Q\right\rVert _{\infty \to \infty} \left\lVert H_{Q}\right\rVert _{\infty \to \infty} \leq \left\lVert \widetilde{Q}- Q\right\rVert _{\infty \to \infty} 2\tau \leq 2\delta \tau \end{align}\] using Lemma 22 in the penultimate inequality. Therefore, we have \(\left\lVert \widetilde{Q}^t - \widetilde{Q}^\infty\right\rVert _{\infty \to \infty} \leq t \delta + 2^{-\lfloor\frac{t}{\tau}\rfloor} + 2\delta \tau< (t+2\tau)\delta + 2^{-\frac{t}{\tau}+1} .\) By choosing \(t=(3+\log_2 |\mathcal{Z}|)\tau,\delta=\frac{1}{4(5+\log_2|\mathcal{Z}|)\tau}\) we can make this \(\leq \frac{1}{2}\), which implies that the standard mixing time of \(\widetilde{Q}\) is within \((3+\log_2 |\mathcal{Z}|)\tau\). Then it implies that \(\widetilde{Q}\) is aperiodic. In conclusion, if \(\left\lVert \widetilde{Q} - Q\right\rVert _{\infty \to \infty} \leq \frac{1}{4|\mathcal{Z}|\tau (5 + \log_2 |\mathcal{Z}|)}\), the Markov chain \(\widetilde{Q}\) is unichain and aperiodic and the mixing time of \(\widetilde{Q}\) is bounded by \((3+\log_2|\mathcal{Z}|) \tau\).

Lemma 21. Suppose that the Markov chain \(Q\) is unichain, aperiodic, and has mixing time bounded by \(\tau\). Then for any time \(t\ge \tau\), \(\left\lVert Q^t - Q^\infty\right\rVert _{\infty \to \infty}\le2^{-\lfloor t/\tau\rfloor}.\)

Denote \(\mu\) as the stationary distribution of the Markov chain \(Q\). Hence \(Q^\infty=\mathbf{1}\mu\). By the definition of the uniform mixing time \(\tau\), we have \[\|Q^{\tau} - Q^\infty\|_{\infty\to\infty}=\max_{s}\sum_{j}|Q^{\tau}(s,j)-\mu(j)|=2\max_s\|Q^{\tau}(s,\cdot)-\mu(\cdot)\|_{\text{TV}} \le \frac{1}{2}.\] Let \(t = k\,\tau + r, 0 \le r < \tau.\) Then \(Q^t - Q^\infty = Q^r \bigl(Q^{k\,\tau} - Q^\infty\bigr).\) Hence, \(\forall t\ge\tau\), \[\left\lVert Q^t - Q^\infty\right\rVert _{\infty \to \infty}\le\left\lVert Q^{k\tau} - Q^\infty\right\rVert _{\infty \to \infty}\le\left\lVert Q^{\tau} - Q^\infty\right\rVert _{\infty \to \infty}^k\le\left(\frac{1}{2}\right)^k=2^{-\lfloor t/\tau\rfloor}.\]

Lemma 22. Let \(Q\) be a finite-state Markov transition matrix. If \(Q\) is unichain and aperiodic and has mixing time bounded by \(\tau\), then the deviation matrix of \(Q\), denoted as \(H_Q\), satisfies \(\left\lVert H_Q\right\rVert _{\infty \to \infty} \leq 2\tau.\)

Since \(Q\) is aperiodic (so the Cesaro limit in the expression for \(H_Q\) coincides with the usual limit), we have \[\begin{align} \left\lVert H_Q\right\rVert _{\infty \to \infty} &= \left\lVert \sum_{t=0}^\infty \left( Q^{t} - Q^{\infty}\right)\right\rVert _{\infty \to \infty} \leq \sum_{t=0}^\infty \left\lVert Q^{t} - Q^{\infty}\right\rVert _{\infty \to \infty}\\ & \leq \sum_{t=0}^\infty 2^{-\lfloor\frac{t}{\tau}\rfloor} = \sum_{k=0}^\infty \sum_{j=0}^{\tau - 1} 2^{-\lfloor\frac{\tau k + j}{\tau}\rfloor} \leq \sum_{k=0}^\infty \sum_{j=0}^{\tau - 1} 2^{-\lfloor\frac{\tau k}{\tau}\rfloor} = \tau \sum_{k=0}^\infty 2^{-k} = 2 \tau. \end{align}\]

11 Preliminaries for the proof of Theorem 1↩︎

Theorem 1 is based on the ID policy, proposed by [13]. To facilitate the presentation of the proof of Theorem 1, in this section we provide some preliminaries on the ID policy and its analysis. The content is mostly taken from [13]. We present the description of ID policy in Section 11.1, the analysis of ID policy in Section 11.2, and the empirical ID policy in Section 11.3.

11.1 Description of the ID policy↩︎

In this subsection, we describe the ID policy and the corresponding ID reassignment subroutine.

11.1.0.1 ID policy execution (ID-based prioritization).

Each arm is assigned a unique ID in \(\{1,\dots,N\}\) (after reassignment described below). At each time \(t\), the policy first samples an ideal action \(A^{\mathrm{ideal}}_{i,t}\sim \bar{\pi}_i^\star(\cdot\mid S_{i,t}),\quad \forall i\in[N].\) It then attempts to execute these ideal actions in ascending ID order. Define the conforming number \(N_t^\star\), i.e., the number of arms that actually conform to their ideal actions at time \(t\): \[\label{eq:conforming-number} N_t^\star =\max\left\{n\in[N]: \sum_{i=1}^n c_{k,i}(S_{i,t},A^{\mathrm{ideal}}_{i,t})\le \alpha_kN, \quad \forall k\in[K]\right\}.\tag{29}\] The realized action is \(A_{i,t}=A^{\mathrm{ideal}}_{i,t}\) for \(i\in[N_t^\star]\), and \(A_{i,t}=0\) otherwise. Details of the ID policy is shown in Algorithm 7.

11.1.0.2 ID reassignment.

In the fully heterogeneous setting, arms can have very different cost profiles under \(\bar{\pi}_i^\star\). Define the expected type-\(k\) cost of arm \(i\) under \(\Bar{\pi}^\star_i\) as \(C_{k,i}^\star \triangleq \sum_{s\in\mathcal{S},\,a\in\mathcal{A}} y_i^\star(s,a)\, c_{k,i}(s,a).\) We call constraint \(k\) active if \(\sum_{i=1}^N C_{k,i}^\star \ge \frac{\alpha_k}{2}N.\) Let \(\mathcal{A}\subseteq[K]\) denote the set of active constraints.

For each subset \(D\subseteq[N]\), define the total expected type-\(k\) cost as \(C_k^\star(D)\triangleq \sum_{i\in D} C_{k,i}^\star\), and define the remaining budget as \(\bar{C}_k^\star(D) = \alpha_k N - C_k^\star(D) - \frac{\alpha_k}{3}|D| \cdot \mathbb{I}(k\notin\mathcal{A}).\) The reassignment algorithm is shown in Algorithm 8. Algorithm 8 permutes IDs so that, as we move along IDs, the remaining budgets \(\bar{C}_k^\star([n])\) do not exhibit long “plateaus” (i.e., overly flat cumulative cost), which would otherwise make \(N_t^\star\) overly sensitive to random ideal-action sampling.

11.2 Analysis of the ID policy↩︎

The analysis of the ID policy in [13] relies on a specific Lyapunov function. Before we introduce the Lyapunov function, we firstly introduce the one-hot representation of the state and define a key quantity called the focus set.

11.2.0.1 One-hot representation.

For a system state \(\boldsymbol{s}=(s_i)_{i\in[N]}\), let \(\boldsymbol{x}\in\mathbb{R}^{N\times S}\) be its one-hot representation, where \(x_i(s)=\mathbb{I}\{s_i=s\}\). We use \(\boldsymbol{s}\) and \(\boldsymbol{x}\) interchangeably, and write \(\boldsymbol{X}_t\) for the one-hot representation of the stochastic state \(\boldsymbol{S}_t\).

11.2.0.2 Focus set.

The ID policy executes ideal actions only for a (random) prefix of arms of length \(N_t^\star\). To analyze this, the paper introduces a focus set that tracks a deterministic prefix length selected based on the current system state.

Let \(\boldsymbol{x}\) denote a system state and let \(h(\boldsymbol{x},m)\) be a Lyapunov-type quantity which is parameterized by \(m\in[0,1]_N\triangleq\{0,1/N,\dots,1\}\) and is defined in 32 . Define \[\label{eq:def-m} m(\boldsymbol{x}) = \max\Bigl\{m \in [0,1]_N :h(\boldsymbol{x},m) \le \min_{k\in[K]} \bar{C}_k^{\star}([Nm]) \Bigr\}.\tag{30}\] and the focus set as the prefix \([Nm(x)]\). Intuitively, \(m(x)\) is chosen as the largest fraction such that \(h(\boldsymbol{x},m)\) is covered by the minimum remaining budget across constraints.

The analysis then establishes three key properties: (i) majority conformity—almost all arms in the focus set, except for \(O(\sqrt{N})\) arms, can follow the optimal single-armed policies \(\Bar{\pi}^\star_i\); (ii) almost non-shrinking—the focus set shrinks by at most \(O(\sqrt{N})\) on average over time; (iii) sufficient coverage—the complement size \(1-m(\boldsymbol{X}_t)\) is controlled by \(h(\boldsymbol{X}_t,m(\boldsymbol{X}_t))\).

11.2.0.3 Projection-based Lyapunov function.

We firstly introduce some necessary single-armed quantities. For each cost type \(k\in[K]\), define \(c^\star_{k,i}(s) \triangleq \sum_{a\in\mathcal{A}}\bar{\pi}^\star_i(a\mid s)\,c_{k,i}(s,a)\) and the vector \(c^\star_k \triangleq (c^\star_{k,i})_{i\in[N]}\). Similarly, define \(r^\star_i(s) \triangleq \sum_{a\in\mathcal{A}}\bar{\pi}^\star_i(a\mid s)\,r_i(s,a)\) and \(r^\star \triangleq (r^\star_i)_{i\in[N]}\). We collect these vectors as \(\mathcal{G}\triangleq\{c^\star_1,\dots,c^\star_K,r^\star\}\). With Assumption 1, the Markov chain induced by \(\Bar{\pi}^\star_i\) converges to a unique stationary distribution, denoted by \(\mu_i^\star = (\mu_i^\star(s))_{s \in \mathcal{S}}\). It is straightforward to verify that \(\mu_i^\star(s) = y_i^\star(s, 0) + y_i^\star(s, 1)\). We scale the subset Lyapunov function introduced in [13], for any system state \(\boldsymbol{x}\) and subset \(D\subseteq [N]\), \[h_{P,\tau}(\boldsymbol{x},D) \triangleq \max_{g\in\mathcal{G}} \sup_{\ell\in\mathbb{N}} \left| \frac{1}{N}\sum_{i\in D} \left\langle (\boldsymbol{x}_i - \mu_i^\star)P_i^{\ell}/\gamma^{\ell}, g_i \right\rangle \right|,\] where \[\label{def:gamma-tau-g} \gamma = 4^{-\frac{1}{2\tau}},\quad\tau=(3+\log_2S)\tau_{\mathrm{unif}},\quad g_i\in\mathcal{G}.\tag{31}\] Here \(\tau_{\mathrm{unif}}\) is the uniform mixing time defined in Assumption 1. Then for any \(m\in[0,1]_N\), \[\label{def:h} h(\boldsymbol{x},m)\triangleq\max_{m'\in[0,1]_N: m'\le m}h_{P,\tau}\bigl(\boldsymbol{x},[N m']\bigr),\tag{32}\] Finally the Lyapunov function is defined as \[\label{def:lya-true} V(\boldsymbol{x})=h(\boldsymbol{x},m(\boldsymbol{x}))+L_h(1-m(\boldsymbol{x})),\tag{33}\] where \(m(\boldsymbol{x})\) is defined in 30 and \[\label{eq:def-Lh-Ctau-tau} L_h = 2\max\{c_{\max},r_{\max}\} C_\tau,\quad C_{\tau} = 16\tau,\quad \tau=(3+\log_2S)\tau_{\mathrm{unif}}.\tag{34}\] Moreover, by the \(L_h\)-Lipschitz property of \(h(\cdot,m(\cdot))\) in [13], we have for any system state \(\boldsymbol{x}\), \[\label{eq:bound-V-hete} V(\boldsymbol{x}) = h(\boldsymbol{x},m(\boldsymbol{x}))+L_h(1-m(\boldsymbol{x})) \le h(\boldsymbol{x},0)+L_hm(\boldsymbol{x})+L_h(1-m(\boldsymbol{x})) = L_h .\tag{35}\] Bounding the drift of \(V\) yields control of the long-run average \(V(\boldsymbol{X}_t)\), and together with the focus-set lemmas this leads to an \(O(1/\sqrt{N})\) optimality gap for the ID policy with reassignment.

11.3 Empirical ID policy↩︎

In this subsection, we introduce the ID policy for the empirical system. The empirical LP is obtained from the relaxation 2 by replacing \(P_i\) with \(\widehat{P}_i\) in the flow-balance constraints. Let \(\widehat{\rho}^{\mathrm{rel}}\) be its optimal value, and let \(\bigl(\widehat{y}^\star_i(s,a)\bigr)_{i\in[N],\,s\in\mathcal{S},\,a\in\mathcal{A}}\) be an optimal solution. The empirical optimal single-arm policies \(\{\widehat{\Bar{\pi}}^\star_i\}_{i\in[N]}\) are defined from \(\widehat{y}^\star_i\) in the same way that \(\{\Bar{\pi}^\star_i\}_{i\in[N]}\) are defined from \(y_i^\star\). Plugging \(\widehat{y}^\star_i\) and \(\widehat{\Bar{\pi}}^\star_i\) into the ID-policy construction gives the empirical ID policy \(\widehat{\pi}_{\mathrm{ID}}\). For any policy \(\pi\), we write \(\widehat{\rho}^\pi\in\mathbb{R}^{S^N}\) for its gain under the empirical \(N\)-armed system.

12 Proof details of the lemmas used in Theorem 1↩︎

12.1 Proofs of model accuracy lemmas↩︎

Proof. Proof of Lemma 1

Fix \(i\in[N]\), let \(e_{sa}\in\mathbb{R}^{SA}\) be the row-selector vector whose \((s,a)\)-th entry is \(1\) and others \(0\). Let \(P_i,\widehat P_i\in\mathbb{R}^{SA\times S}\) be matrices with \(P_i(s,a,s')=P(s'\mid s,a)\) and \(\widehat P_i(s,a,s')=\widehat P(s'\mid s,a)\). Then by definition, \(\max_{s \in \mathcal{S}, a \in \mathcal{A}} \left\Vert P_i(\cdot\mid s,a) - \widehat{P}_i(\cdot\mid s,a)\right\Vert _{1} = \max_{s \in \mathcal{S}} \max_{a \in \mathcal{A}} \max_{v \in \{-1,1\}^{\mathcal{S}}}e_{sa}^\top \left( P_i - \widehat{P}_i\right)v .\) Now fixing some \(s \in \mathcal{S}, a \in \mathcal{A}, v \in \{-1,1\}^{\mathcal{S}}\), we have by Hoeffding’s inequality that \(\mathbb{P}\left(e_{sa}^\top \left( P_i - \widehat{P}_i\right)v \geq \sqrt{\frac{2\log (1/\eta')}{n}} \right) \leq \exp \left(-\frac{2n}{4} \sqrt{\frac{2\log (1/\eta')}{n}}^2 \right) = \eta'.\) Setting \(\eta' = \frac{\eta}{NSA 2^S}\) and taking a union bound over all \(s \in \mathcal{S}, a \in \mathcal{A}, v \in \{-1,1\}^{\mathcal{S}}, i\in[N]\), we obtain the bound in the statement of the lemma. ◻

By Lemma 23, for any fixed \((\boldsymbol{s},\boldsymbol{a})\in \mathcal{S}^N\times\mathcal{A}^N\), we have \[\begin{align} & \left\Vert \boldsymbol{P}(\cdot\mid \boldsymbol{s},\boldsymbol{a}) - \widehat{\boldsymbol{P}}(\cdot\mid \boldsymbol{s},\boldsymbol{a})\right\Vert _{1} \\ =& \sum_{s_1',\dots,s_N'}\left|\prod_{i=1}^Np_i(s_i'\mid s_i,a_i)-\prod_{i=1}^N\widehat{P}_i(s_i'\mid s_i,a_i)\right| \\ =& \sum_{s_1',\dots,s_N'}\left|\sum_{j=1}^N\Big(\prod_{i<j}\widehat{P}_i(s_i'\mid s_i,a_i)\Big)\Big(P_j(s_j'\mid s_j,a_j)-\widehat{P}_j(s_j'\mid s_j,a_j)\Big)\Big(\prod_{i>j}P_i(s_i'\mid s_i,a_i)\Big)\right|\\ \le & \sum_{s_1',\dots,s_N'}\sum_{j=1}^N\prod_{i<j}\widehat{P}_i(s_i'\mid s_i,a_i)\left|P_j(s_j'\mid s_j,a_j)-\widehat{P}_j(s_j'\mid s_j,a_j)\right|\prod_{i>j}P_i(s_i'\mid s_i,a_i)\\ =&\sum_{j=1}^N\underbrace{\left(\sum_{s_1',\dots,s_{j-1}'}\prod_{i<j}\widehat{P}_i(s_i'\mid s_i,a_i)\right)}_{=1} \times \left(\sum_{s_j'}\left|P_j(s_j'\mid s_j,a_j)-\widehat{P}_j(s_j'\mid s_j,a_j)\right|\right) \times \underbrace{\left(\sum_{s_{j+1}',\dots,s_{N}'}\prod_{i>j}P_i(s_i'\mid s_i,a_i)\right)}_{=1}\\ =&\sum_{j=1}^N\left\Vert P_j(\cdot\mid s_j,a_j)-\widehat{P}_j(\cdot\mid s_j,a_j)\right\Vert _{1}\le N\delta. \end{align}\] It follows that \(\max_{\boldsymbol{s}\in\mathcal{S}^N,\boldsymbol{a}\in\mathcal{A}^N}\left\Vert \boldsymbol{P}(\cdot\mid \boldsymbol{s},\boldsymbol{a}) - \widehat{\boldsymbol{P}}(\cdot\mid \boldsymbol{s},\boldsymbol{a})\right\Vert _{1} \le N\delta\) as desired. And accordingly, \[\begin{align} \left\lVert \boldsymbol{P}^{\pi}-\widehat{\boldsymbol{P}}^{\pi}\right\rVert _{\infty \to \infty} =& \max_{\boldsymbol{s}}\left\Vert \boldsymbol{P}^{\pi}(\boldsymbol{s},\cdot)-\widehat{\boldsymbol{P}}^{\pi}(\boldsymbol{s},\cdot)\right\Vert _{1} \le \max_{\boldsymbol{s}}\sum_{\boldsymbol{a}}\pi(\boldsymbol{a}\mid\boldsymbol{s})\left\Vert \boldsymbol{P}(\cdot\mid\boldsymbol{s},\boldsymbol{a})-\widehat{\boldsymbol{P}}(\cdot\mid\boldsymbol{s},\boldsymbol{a})\right\Vert _{1} \le N\delta. \end{align}\] Finally, we record the following standard identity, which is used in the proof of Lemma 2.

Lemma 23. For any real numbers \(a_i, b_i \in \mathbb{R}\) for \(i = 1, \dots, N\), the following identity holds: \(\prod_{i=1}^N a_i - \prod_{i=1}^N b_i = \sum_{j=1}^N \left( \prod_{i<j} b_i \right)(a_j - b_j)\left( \prod_{i>j} a_i \right).\)

Proof. Proof We proceed by induction on \(N\). The base case \(N = 2\) follows from: \(a_1 a_2 - b_1 b_2 = (a_1 - b_1)a_2 + b_1(a_2 - b_2).\) Assume the identity holds for \(N - 1\) terms. Then, \[\prod_{i=1}^N a_i - \prod_{i=1}^N b_i = \left( \prod_{i=1}^{N-1} a_i \right) a_N - \left( \prod_{i=1}^{N-1} b_i \right) b_N = \left( \prod_{i=1}^{N-1} a_i - \prod_{i=1}^{N-1} b_i \right) a_N + \left( \prod_{i=1}^{N-1} b_i \right)(a_N - b_N).\] Applying the inductive hypothesis to the first RHS term completes the proof. ◻

12.2 Proof of Lemma 4↩︎

We prove Lemma 4. The goal of Lemma 4 is to bound \(\widehat{\rho}^{\mathrm{rel}}-\rho^{\widehat{\pi}_{\mathrm{ID}}}(\boldsymbol{s}_0)\), which is the second term in the decomposition 18 , so we need to work with the empirical system. The proof mirrors that of Lemma 3, but with the empirical LP solution and the empirical kernel. We first verify that the empirical single-arm chains needed to define the empirical Lyapunov function are well behaved.

12.2.1 Markov chain under empirical model↩︎

Lemma 24. Under the conditions of Lemma 4, for every \(i\in[N]\), the Markov chain induced by \(\widehat{\Bar{\pi}}^\star_i\) under \(\widehat{P}_i\) is unichain and aperiodic, with mixing time at most \(\tau\), where \(\tau\) is defined in 31 .

Proof. Proof. Fix \(i\in[N]\). Let \(Q_i(s,s') = \sum_{a\in\mathcal{A}}\widehat{\Bar{\pi}}^\star_i(a\mid s)P_i(s'\mid s,a), \widehat Q_i(s,s') = \sum_{a\in\mathcal{A}}\widehat{\Bar{\pi}}^\star_i(a\mid s)\widehat{P}_i(s'\mid s,a).\) Although \(\widehat{\Bar{\pi}}^\star_i\) is computed from the empirical model, it is still a stationary policy for the true single-arm MDP. Hence Assumption 1 implies that \(Q_i\) is unichain, aperiodic, and has mixing time at most \(\tau_{\mathrm{unif}}\). Moreover, by convexity of the \(\ell_1\) norm, \[\left\lVert \widehat Q_i-Q_i\right\rVert _{\infty \to \infty} \le \max_{s\in\mathcal{S},a\in\mathcal{A}} \left\Vert \widehat{P}_i(\cdot\mid s,a)-P_i(\cdot\mid s,a)\right\Vert _{1} \le \delta\le \frac{1}{4S\tau_{\mathrm{unif}}(5+\log_2 S)} .\] Lemma 20, applied with \(\mathcal{Z}=\mathcal{S}\), \(Q=Q_i\), and \(\widetilde{Q}=\widehat Q_i\), gives the desired conclusion. ◻

Let \(\widehat{\mu}^\star_i\) denote the stationary distribution of the Markov chain induced by \(\widehat{\Bar{\pi}}^\star_i\) under \(\widehat{P}_i\), whose existence and uniqueness are guaranteed by Lemma 24.

12.2.2 Lyapunov function for the empirical system↩︎

In this subsection we introduce the Lyapunov function for the empirical system. We firstly introduce the following subset Lyapunov function: \(h_{\widehat{P},\tau}(\boldsymbol{x},D) = \max_{g\in\mathcal{G}} \sup_{\ell\in\mathbb{N}} \left|\frac{1}{N}\sum_{i\in D}\left\langle(\boldsymbol{x}_i - \widehat\mu_i^\star)\widehat{P}_i^{\ell}/\gamma^{\ell},g_i\right\rangle\right|,\) where \(\gamma, g_i\in\mathcal{G}\) are the same as 31 . Then we define \(\widehat{h}(\boldsymbol{x},m)\triangleq\max_{m'\in[0,1]_N: m'\le m}h_{\widehat{P},\tau}\bigl(\boldsymbol{x},[N m']\bigr),\) Finally, we define the Lyapunov function \(\widehat{V}\) for the empirical system as \[\label{def:vhat-hete} \widehat{V}(\boldsymbol{x})=\widehat{h}(\boldsymbol{x},\widehat m(\boldsymbol{x}))+L_h(1-\widehat m(\boldsymbol{x})),\tag{36}\] where \(L_h\) is the same as 34 and \(\widehat m(\boldsymbol{x})\) is defined as \(\widehat m(\boldsymbol{x}) = \max\Bigl\{m \in [0,1]_N :\widehat{h}(\boldsymbol{x},m) \le \min_{k\in[K]} \widehat{\overline{C}}_k^{\star}([Nm]) \Bigr\},\) where \(\widehat{\overline{C}}_k^\star(D) = \alpha_k N - \widehat{C}_k^\star(D) - \dfrac{\alpha_k}{3}\,|D| \cdot \mathbb{I}(k\not\in\mathcal{B}),\) \(\widehat C_k^\star(D)\triangleq \sum_{i\in D} \widehat C_{k,i}^\star\) and \(\widehat C_{k,i}^\star\triangleq \sum_{s\in\mathcal{S}}\sum_{a\in\mathcal{A}} \widehat{y}_i^\star(s,a)\, c_{k,i}(s,a).\) The focus set of \(\widehat{\pi}_{\mathrm{ID}}\) is \([N\widehat{m}(\boldsymbol{x})]\).

12.2.3 Completing the proof of Lemma 4↩︎

Proof. Proof The next two lemmas implement the two key parts for the Lyapunov framework: Lemma 25 provides the drift bound (Condition [cond:drift]) and Lemma 26 provides the gap-dominance bound (Condition [cond:dominance]), both for the empirical quantities and the policy \(\widehat{\pi}_{\mathrm{ID}}\). Their proofs are identical to those for Lemmas 5 and 6 after replacing the true model by the empirical model; we omit the details.

Lemma 25. Under the assumptions of Lemma 4, the Lyapunov function \(\widehat{V}(\cdot)\) defined in 36 satisfies \[\label{drift95cond95hat95hetero} \widehat{\mathbb{E}}^{\widehat{\pi}_{\mathrm{ID}}}\!\left[\widehat{V}(\boldsymbol{X}_{t+1})-\widehat{V}(\boldsymbol{X}_t)\mid \boldsymbol{X}_t=\boldsymbol{x}\right] \le -\rho_V\,\widehat{V}(\boldsymbol{x})+K_V/\sqrt{N},\qquad{(7)}\] where the constants \(\rho_V\) and \(K_V\) are the same as in ?? .

Remark. The constants in ?? are the same as those in the true system drift bound (Lemma 5), because their definitions do not depend on the transition kernel, which is the only difference between the true and empirical systems.

Lemma 26. Suppose the assumptions of Lemma 4 hold. Fix a system state \(\boldsymbol{s}\), and let \(A_i^{\widehat{\pi}_{\mathrm{ID}}}\) be the action applied to arm \(i\) under \(\widehat{\pi}_{\mathrm{ID}}\). Define \(r^{\widehat{\pi}_{\mathrm{ID}}}(\boldsymbol{s})=\frac{1}{N}\sum_{i=1}^N\mathbb{E}\!\left[r_i(s_i,A_i^{\widehat{\pi}_{\mathrm{ID}}})\right].\) Then \(\widehat{\rho}^{\mathrm{rel}}-r^{\widehat{\pi}_{\mathrm{ID}}}(\boldsymbol{s}) \le \frac{2r_{\max}+L_h}{L_h}\,\widehat{V}(\boldsymbol{x})+\frac{2r_{\max}K_{\mathrm{conf}}}{\sqrt{N}}.\)

12.2.3.1 Back to the proof of Lemma 4.

We apply Lemma 7 with \(Q=\widehat{\boldsymbol{P}}^{\widehat{\pi}_{\mathrm{ID}}}\), \(P=\boldsymbol{P}^{\widehat{\pi}_{\mathrm{ID}}}\), \(R=\widehat{\rho}^{\mathrm{rel}}\), \(F=\widehat{V}\), and \(\bar r=r^{\widehat{\pi}_{\mathrm{ID}}}\). Lemmas 25 and 26 give the same constants as in Lemma 3: \(a=\rho_V, b=K_V/\sqrt N, c=\frac{2r_{\max}+L_h}{L_h}, d=\frac{2r_{\max}K_{\mathrm{conf}}}{\sqrt N}.\) Therefore, \[\widehat{\rho}^{\mathrm{rel}}-\rho^{\widehat{\pi}_{\mathrm{ID}}}(\boldsymbol{s}_0) \le \frac{2r_{\max}+L_h}{L_h\rho_V}\sup_{\boldsymbol{x}}|(\boldsymbol{P}^{\widehat{\pi}_{\mathrm{ID}}}-\widehat{\boldsymbol{P}}^{\widehat{\pi}_{\mathrm{ID}}})\widehat{V}(\boldsymbol{x})| +\left[\frac{(2r_{\max}+L_h)K_V}{L_h\rho_V}+2r_{\max}K_{\mathrm{conf}}\right]\frac{1}{\sqrt N}.\] By Lemma 2, \(\left\lVert \boldsymbol{P}^{\widehat{\pi}_{\mathrm{ID}}}-\widehat{\boldsymbol{P}}^{\widehat{\pi}_{\mathrm{ID}}}\right\rVert _{\infty \to \infty}\le N\delta\). The empirical Lyapunov function satisfies \(\|\widehat{V}\|_\infty\le L_h\) by the same Lipschitz argument used for \(V\). Thus \(\sup_{\boldsymbol{x}}|(\boldsymbol{P}^{\widehat{\pi}_{\mathrm{ID}}}-\widehat{\boldsymbol{P}}^{\widehat{\pi}_{\mathrm{ID}}})\widehat{V}(\boldsymbol{x})| \le L_hN\delta,\) which gives the desired bound. ◻

13 Proof of lemmas used in Theorem 3↩︎

13.1 Proof of Lemma 12↩︎

Proof. Proof of Lemma 12. It suffices to bound \(\left\lVert \widehat{U}-\mathbf{1}\widehat{\mu}\right\rVert _{\mu^\star\to\mu^\star}\). We calculate \(\widehat{U}- \mathbf{1}\widehat{\mu} = U - \mathbf{1}\mu^\star + (\widehat{U}-U) - \mathbf{1}(\widehat{\mu}- \mu^\star) = U - \mathbf{1}\mu^\star + (\widehat{U}-U) - \mathbf{1}\widehat{\mu}(\widehat{U}-U)H_{U},\) using Lemma 11 in the second equality. Then by triangle inequality we have that \(\left\lVert \widehat{U}- \mathbf{1}\widehat{\mu}\right\rVert _{\mu^\star\to\mu^\star} \leq \left\lVert U - \mathbf{1}\mu^\star\right\rVert _{\mu^\star\to\mu^\star} + \left\lVert \widehat{U}-U\right\rVert _{\mu^\star\to\mu^\star} + \left\lVert \mathbf{1}\widehat{\mu}(\widehat{U}-U)H_{U}\right\rVert _{\mu^\star\to\mu^\star}.\) Now subtracting both sides of the above inequality from \(1\), we have \[\begin{align} 1 - \left\lVert \widehat{U}- \mathbf{1}\widehat{\mu}\right\rVert _{\mu^\star\to\mu^\star} &\geq 1 - \left\lVert U - \mathbf{1}\mu^\star\right\rVert _{\mu^\star\to\mu^\star}-\left\lVert \widehat{U}-U\right\rVert _{\mu^\star\to\mu^\star}-\left\lVert \mathbf{1}\widehat{\mu}(\widehat{U}-U)H_{U}\right\rVert _{\mu^\star\to\mu^\star} \\ & \geq 1 - \left\lVert U - \mathbf{1}\mu^\star\right\rVert _{\mu^\star\to\mu^\star}-\left\lVert \widehat{U}-U\right\rVert _{\mu^\star\to\mu^\star} -\left\lVert \mathbf{1}\widehat{\mu}\right\rVert _{\mu^\star\to\mu^\star} \left\lVert \widehat{U}-U\right\rVert _{\mu^\star\to\mu^\star} \left\lVert H_{U}\right\rVert _{\mu^\star\to\mu^\star} \\ & \stackrel{(*)}{\geq} 1 - \left\lVert U - \mathbf{1}\mu^\star\right\rVert _{\mu^\star\to\mu^\star}-\left\lVert \widehat{U}-U\right\rVert _{\mu^\star\to\mu^\star} -\frac{1}{\sqrt{\mu^\star_{\min}}}\left\lVert \widehat{U}-U\right\rVert _{\mu^\star\to\mu^\star} \left\lVert H_{U}\right\rVert _{\mu^\star\to\mu^\star} \end{align}\] where in the final inequality \((*)\) we used that \[\begin{align} \left\lVert \mathbf{1}\widehat{\mu}\right\rVert _{\mu^\star\to\mu^\star} &= \left\lVert \mathbf{1}\mu^\star (I - (\widehat{U}-U)H_U)^{-1}\right\rVert _{\mu^\star\to\mu^\star} \\ &\leq \left\lVert \mathbf{1}\mu^\star \right\rVert _{\mu^\star\to\mu^\star} \left\lVert (I - (\widehat{U}-U)H_U)^{-1}\right\rVert _{\mu^\star\to\mu^\star} \leq \frac{1}{\sqrt{\mu^\star_{\min}}} \frac{1}{1- \left\lVert (\widehat{U}-U)\right\rVert _{\mu^\star\to\mu^\star} \left\lVert H_U\right\rVert _{\mu^\star\to\mu^\star} }, \end{align}\] noting that \(\left\lVert \mathbf{1}\mu^\star \right\rVert _{\mu^\star\to\mu^\star} \leq \frac{1}{\sqrt{\mu^\star_{\min}}} \left\lVert \mathbf{1}\mu^\star\right\rVert _{\infty \to \infty} = \frac{1}{\sqrt{\mu^\star_{\min}}}\).

To ensure \(1-\left\lVert \widehat{U}- \mathbf{1}\widehat{\mu}\right\rVert _{\mu^\star\to\mu^\star} \geq \frac{1-\left\lVert U - \mathbf{1}\mu^\star\right\rVert _{\mu^\star\to\mu^\star}}{2}\), it is sufficient to guarantee that \[\begin{align} 1 - \left\lVert U - \mathbf{1}\mu^\star\right\rVert _{\mu^\star\to\mu^\star} -\left\lVert \widehat{U}-U\right\rVert _{\mu^\star\to\mu^\star} -\frac{1}{\sqrt{\mu^\star_{\min}}}\left\lVert \widehat{U}-U\right\rVert _{\mu^\star\to\mu^\star} \left\lVert H_{U}\right\rVert _{\mu^\star\to\mu^\star} \geq& \frac{1-\left\lVert U - \mathbf{1}\mu^\star\right\rVert _{\mu^\star\to\mu^\star}}{2}. \end{align}\] Simplifying the expression, this is equivalent to \(\left\lVert \widehat{U}-U\right\rVert _{\mu^\star\to\mu^\star}\left(1 + \frac{\left\lVert H_{U}\right\rVert _{\mu^\star\to\mu^\star}}{\sqrt{\mu^\star_{\min}}} \right) \leq \frac{1-\left\lVert U - \mathbf{1}\mu^\star\right\rVert _{\mu^\star\to\mu^\star}}{2},\) which is in turn equivalent to ?? . ◻

We note that ?? implies the previously used condition that \(\left\lVert (\widehat{U}-U)H_U\right\rVert _{\mu^\star\to\mu^\star}< 1\), since \(\left\lVert (\widehat{U}-U)H_U\right\rVert _{\mu^\star\to\mu^\star} \leq \left\lVert \widehat{U}-U\right\rVert _{\mu^\star\to\mu^\star}\left\lVert H_U\right\rVert _{\mu^\star\to\mu^\star}\) and ?? implies that \(\left\lVert \widehat{U}-U\right\rVert _{\mu^\star\to\mu^\star}\left\lVert H_U\right\rVert _{\mu^\star\to\mu^\star} \leq 1/2 < 1.\) Hence, \((I - (\widehat{U}-U)H_U)^{-1}\) is invertible.

13.2 Algebraic properties of \(U, \widehat{U}, \mu^\star, \widehat{\mu}, H_U\) and \(H_{\widehat{U}}\)↩︎

The following two lemmas that check various algebraic properties of \(U, \widehat{U}, \mu^\star, \widehat{\mu}, H_U\), and \(H_{\widehat{U}}\), which will be used in the sequel.

Lemma 27. We have \(U\mathbf{1}=\mathbf{1}\) and \(\widehat{U}\mathbf{1}=\mathbf{1}\). Moreover, if \(I-(U-\mathbf{1}\mu^\star)\) is invertible, then \(H_U\mathbf{1}=\mathbf{0}\).

Proof. Proof. We firstly prove \(U\mathbf{1}=\mathbf{1}\); the proof of \(\widehat{U}\mathbf{1}=\mathbf{1}\) is identical. Since \(P^{\pi^\star}\) is row-stochastic and \(\xi\mathbf{1} = (P_{\tilde{s}1}-P_{\tilde{s}0})\mathbf{1} = 1-1 = 0,\) we have \(U\mathbf{1} = \bigl(P^{\pi^\star}-(c^{\pi^\star}-\alpha\mathbf{1})\xi\bigr)\mathbf{1} = P^{\pi^\star}\mathbf{1} - (c^{\pi^\star}-\alpha\mathbf{1})(\xi\mathbf{1}) = \mathbf{1}.\) Let \(x = H_U \mathbf{1}= (I - (U - \mathbf{1}\mu^\star))^{-1} \mathbf{1}- \mathbf{1}\mu^\star \mathbf{1}= (I - (U - \mathbf{1}\mu^\star))^{-1} \mathbf{1}- \mathbf{1}\) (using that \(\mu^\star \mathbf{1}= \mathbf{1}\)). Then left-multiplying by \((I - (U - \mathbf{1}\mu^\star))\), we have \[\begin{align} (I - (U - \mathbf{1}\mu^\star)) x &= (I - (U - \mathbf{1}\mu^\star))(I - (U - \mathbf{1}\mu^\star))^{-1} \mathbf{1}- (I - (U - \mathbf{1}\mu^\star)) \mathbf{1} = \mathbf{1}- \mathbf{1}+ U \mathbf{1}- \mathbf{1}\mu^\star \mathbf{1} = \mathbf{0} \end{align}\] using that \(\mu^\star \mathbf{1}= \mathbf{1}\) and that \(U \mathbf{1}= \mathbf{1}\) in the final equality. But since \((I - (U - \mathbf{1}\mu^\star))\) is invertible, the equality \((I - (U - \mathbf{1}\mu^\star)) x = \mathbf{0}\) implies that \(x = \mathbf{0}\). ◻

Lemma 28. Suppose that \(\left\lVert U-\mathbf{1}\mu^\star\right\rVert _{\mu^\star\to\mu^\star}<1\) and ?? holds. Then \(\widehat{\mu}\widehat{U}=\widehat{\mu}, \widehat{\mu}\mathbf{1}=1,\) and \(H_{\widehat{U}}\mathbf{1}=\mathbf{0}, \widehat{\mu}H_{\widehat{U}}=\mathbf{0}, (I-\widehat{U})H_{\widehat{U}}=I-\mathbf{1}\widehat{\mu}.\) Moreover, there exists a row vector \(x\) such that \(H_{\widehat{U}}-H_U = H_U(\widehat{U}-U)H_{\widehat{U}}+\mathbf{1}x.\)

Proof. Proof. Abbreviate \(X = (I - (\widehat{U}- U)H_U)^{-1}\). By the definition 24 of \(\widehat{\mu}\), to show \(\widehat{\mu}\widehat{U}= \widehat{\mu}\) it suffices to show that \(\mu^\star X \widehat{U}= \mu^\star X.\) From the definition of \(X\) we have that \[\begin{align} X (I - (\widehat{U}- U)H_U) = I \implies & X + XUH_U - I = X \widehat{U}H_U \\ \implies & (X + XUH_U - I)(I-U) = X \widehat{U}H_U(I-U) = X\widehat{U}(I - \mathbf{1}\mu^\star) \\ \implies & X\widehat{U}= (X + XUH_U - I)(I-U) + X\widehat{U}\mathbf{1}\mu^\star \\ & \quad\;\;\, = X - XU+XUH_U - XUH_U U - I + U + X\widehat{U}\mathbf{1}\mu^\star, \end{align}\] where we used the property that \(H_U(I-U) = I - \mathbf{1}\mu^\star\). Now left-multiplying by \(\mu^\star\), and also using the facts that \(\widehat{U}\mathbf{1}= \mathbf{1}\) and \(\widehat{U}\mathbf{1}= U\mathbf{1}= \mathbf{1}\) from Lemma 27, we have that \[\begin{align} \mu^\star X \widehat{U} &= \mu^\star \left( X - XU+XUH_U - XUH_U U - I + U + X\widehat{U}\mathbf{1}\mu^\star\right) \\ &= \mu^\star X + \mu^\star XU (-I + H_U - H_UU + \mathbf{1}\mu^\star) = \mu^\star X, \end{align}\] where in the final equality we used that \(-I + H_U - H_UU + \mathbf{1}\mu^\star = 0\), which is equivalent to the fact that \(H_U(I - U) = I - \mathbf{1}\mu^\star\). Hence we have that \(\widehat{\mu}\widehat{U}= \widehat{\mu}\) as desired.

Now we check that \(\widehat{\mu}\mathbf{1}= \mathbf{1}\). The condition \(\left\lVert (\widehat{U}-U)H_U\right\rVert _{\mu^\star\to\mu^\star}< 1\) (which is implied by ?? as mentioned above) implies the Neumann series expansion \((I - (\widehat{U}-U)H_U)^{-1} = \sum_{t \geq 0} ((\widehat{U}-U)H_U)^t\). Hence by the definition 24 of \(\widehat{\mu}\) we have \[\begin{align} \widehat{\mu}\mathbf{1} = \mu^\star (I - (\widehat{U}-U)H_U)^{-1} \mathbf{1} &= \sum_{t \geq 0} \mu^\star ((\widehat{U}-U)H_U)^t \mathbf{1}= \mu^\star \mathbf{1}+ \sum_{t \geq 0} \mu^\star ((\widehat{U}-U)H_U)^t (\widehat{U}-U)H_U \mathbf{1} = \mathbf{1}, \end{align}\] where in the final equality we used that \(\mu^\star \mathbf{1}= \mathbf{1}\) and that \(H_U \mathbf{1}= \mathbf{0}\) (from Lemma 27).

Having checked \(\widehat{\mu}\mathbf{1}= 1\), we can use an analogous proof as for Lemma 27 to show \(H_{\widehat{U}} \mathbf{1}= \mathbf{0}\).

Next we check that \(\widehat{\mu}H_{\widehat{U}} = \mathbf{0}\). From the Neumann series for \((I - (\widehat{U}- \mathbf{1}\widehat{\mu}))^{-1}\) (since \(\left\lVert \widehat{U}- \mathbf{1}\widehat{\mu}\right\rVert _{\mu^\star\to\mu^\star}<1\) by Lemma 12) we have \[\begin{align} \widehat{\mu}H_{\widehat{U}} = \widehat{\mu}(I - (\widehat{U}- \mathbf{1}\widehat{\mu}))^{-1} - \widehat{\mu}\mathbf{1}\widehat{\mu} &= \sum_{t \geq 0} \widehat{\mu}(\widehat{U}- \mathbf{1}\widehat{\mu})^t - \widehat{\mu} = \widehat{\mu}I + \sum_{t \geq 0 }\widehat{\mu}(\widehat{U}- \mathbf{1}\widehat{\mu}) (\widehat{U}- \mathbf{1}\widehat{\mu})^t - \widehat{\mu} = \mathbf{0}, \end{align}\] where we used that \(\widehat{\mu}(\widehat{U}- \mathbf{1}\widehat{\mu}) = \mathbf{0}\), which follows from combining the facts \(\widehat{\mu}\widehat{U}= \widehat{\mu}\) and \(\widehat{\mu}\mathbf{1}=1\).

Finally we show that \((I - \widehat{U})H_{\widehat{U}} = I - \mathbf{1}\widehat{\mu}\). We have \[\begin{align} (I - \widehat{U})H_{\widehat{U}} = (I - \widehat{U}+ \mathbf{1}\widehat{\mu})H_{\widehat{U}} - \mathbf{1}\widehat{\mu}H_{\widehat{U}} &= (I - \widehat{U}+ \mathbf{1}\widehat{\mu}) \left((I - (\widehat{U}- \mathbf{1}\widehat{\mu}))^{-1} - \mathbf{1}\widehat{\mu}\right) - \mathbf{1}\widehat{\mu}H_{\widehat{U}} \\ &= I - (I - \widehat{U}+ \mathbf{1}\widehat{\mu})\mathbf{1}\widehat{\mu}- \mathbf{1}\widehat{\mu}H_{\widehat{U}} = I - \mathbf{1}\widehat{\mu}+ \mathbf{1}\widehat{\mu}- \mathbf{1}\widehat{\mu}, \end{align}\] where the final equality used \(\widehat{U}\mathbf{1}= \mathbf{1}\), \(\widehat{\mu}\mathbf{1}= \mathbf{1}\) and \(\widehat{\mu}H_{\widehat{U}} =\mathbf{0}\).

Note the resolvent identity \(A^{-1} - B^{-1} = A^{-1}(B-A)B^{-1} = B^{-1} (B-A)A^{-1}\) and the fact that \(I - (\widehat{U}- \mathbf{1}\widehat{\mu})\) and \(I - (U - \mathbf{1}\mu^\star)\) are invertible due to the assumptions and Lemma 12. We have \[\begin{align} & (I - (\widehat{U}- \mathbf{1}\widehat{\mu}))^{-1} - (I - (U - \mathbf{1}\mu^\star))^{-1} \nonumber \\ &= (I - (U - \mathbf{1}\mu^\star))^{-1} \left( (I - (U - \mathbf{1}\mu^\star)) - (I - (\widehat{U}- \mathbf{1}\widehat{\mu})) \right) (I - (\widehat{U}- \mathbf{1}\widehat{\mu}))^{-1}\nonumber \\ &= (I - (U - \mathbf{1}\mu^\star))^{-1} \left( \widehat{U}- U - \mathbf{1}\widehat{\mu}+ \mathbf{1}\mu^\star \right) (I - (\widehat{U}- \mathbf{1}\widehat{\mu}))^{-1} \nonumber\\ &= (I - (U - \mathbf{1}\mu^\star))^{-1} \left( \widehat{U}- U \right) (I - (\widehat{U}- \mathbf{1}\widehat{\mu}))^{-1} - \mathbf{1}(\widehat{\mu}- \mu^\star) (I - (\widehat{U}- \mathbf{1}\widehat{\mu}))^{-1} \label{eq:HU-Huhat95step1} \end{align}\tag{37}\] using that \((I - (U - \mathbf{1}\mu^\star))^{-1} \mathbf{1}= \mathbf{1}\) in the final equality, which follows from Lemma 27. Next we have \[\begin{gather} (I - (U - \mathbf{1}\mu^\star))^{-1} \left( \widehat{U}- U \right) (I - (\widehat{U}- \mathbf{1}\widehat{\mu}))^{-1} \\ = H_U \left( \widehat{U}- U \right) (I - (\widehat{U}- \mathbf{1}\widehat{\mu}))^{-1} + \mathbf{1}\mu^\star \left( \widehat{U}- U \right) (I - (\widehat{U}- \mathbf{1}\widehat{\mu}))^{-1} \label{eq:HU-Huhat95step2} \end{gather}\tag{38}\] and \[\begin{align} H_U \left( \widehat{U}- U \right) (I - (\widehat{U}- \mathbf{1}\widehat{\mu}))^{-1} &= H_U \left( \widehat{U}- U \right) H_{\widehat{U}} + H_U \left( \widehat{U}- U \right) \mathbf{1}\widehat{\mu}\nonumber\\ &= H_U \left( \widehat{U}- U \right) H_{\widehat{U}} + H_U \mathbf{0} = H_U \left( \widehat{U}- U \right) H_{\widehat{U}}, \label{eq:HU-Huhat95step3} \end{align}\tag{39}\] where we used \(U \mathbf{1}= \mathbf{1}\) and \(\widehat{U}\mathbf{1}= \mathbf{1}\) from Lemma 27. Combining these calculations, we have that \[\begin{align} H_{\widehat{U}} - H_U =& (I - (\widehat{U}- \mathbf{1}\widehat{\mu}))^{-1} - \mathbf{1}\widehat{\mu}- (I - (U - \mathbf{1}\mu^\star))^{-1} + \mathbf{1}\mu^\star \\ \stackrel{(i)}{=}& (I - (U - \mathbf{1}\mu^\star))^{-1} \left( \widehat{U}- U \right) (I - (\widehat{U}- \mathbf{1}\widehat{\mu}))^{-1} - \mathbf{1}(\widehat{\mu}- \mu^\star) (I - (\widehat{U}- \mathbf{1}\widehat{\mu}))^{-1} - \mathbf{1}\widehat{\mu}+ \mathbf{1}\mu^\star \\ \stackrel{(ii)}{=}& H_U \left( \widehat{U}- U \right) (I - (\widehat{U}- \mathbf{1}\widehat{\mu}))^{-1} + \mathbf{1}\mu^\star \left( \widehat{U}- U \right) (I - (\widehat{U}- \mathbf{1}\widehat{\mu}))^{-1} \\ &- \mathbf{1}(\widehat{\mu}- \mu^\star) (I - (\widehat{U}- \mathbf{1}\widehat{\mu}))^{-1} - \mathbf{1}\widehat{\mu}+ \mathbf{1}\mu^\star \\ \stackrel{(iii)}{=}& H_U \left( \widehat{U}- U \right) H_{\widehat{U}} + \mathbf{1}\mu^\star \left( \widehat{U}- U \right) (I - (\widehat{U}- \mathbf{1}\widehat{\mu}))^{-1} - \mathbf{1}(\widehat{\mu}- \mu^\star) (I - (\widehat{U}- \mathbf{1}\widehat{\mu}))^{-1} - \mathbf{1}\widehat{\mu}+ \mathbf{1}\mu^\star \end{align}\] where in steps \((i), (ii),\) and \((iii)\) we used equations 37 , 38 , and 39 , respectively. Hence the desired equality is true for \(x = \mu^\star \left( \widehat{U}- U \right) (I - (\widehat{U}- \mathbf{1}\widehat{\mu}))^{-1} - (\widehat{\mu}- \mu^\star) (I - (\widehat{U}- \mathbf{1}\widehat{\mu}))^{-1} - \widehat{\mu}+ \mu^\star.\) ◻

13.3 Proof of Lemma [lem:yhat95pert95and95feasibility]↩︎

Before checking the feasibility of \(\widehat{y}\), we first show some useful facts about \(W\). Firstly we write the entries of \(W\) more explicitly. For \(s\neq\tilde{s}\), \[\begin{align} W_{s, s0} = \pi^\star(0 \mid s), \;W_{s, s1} = \pi^\star(1 \mid s), \;W_{s, \tilde{s}0} = (1-\alpha) - \pi^\star(0\mid s), \;W_{s, \tilde{s}1} = \alpha - \pi^\star(1\mid s), \label{eq:W95entries951} \end{align}\tag{40}\] and all other entries of the row \(W_{s,\cdot}\) are zero. For \(s=\tilde{s}\), \[\begin{align} W_{\tilde{s}, \tilde{s}0} = 1-\alpha, \quad W_{\tilde{s}, \tilde{s}1} = \alpha, \label{eq:W95entries952} \end{align}\tag{41}\] and all other entries of the row \(W_{\tilde{s},\cdot}\) are zero. Then we have the following lemma.

Lemma 29. \(W\) satisfies the following properties: \(WJ = I\); \(W \tilde{e} = \alpha \mathbf{1}\); \(W \mathbf{1}= \mathbf{1}\); \(W P = U\); \(W \widehat{P}= \widehat{U}\).

Proof. Proof 1. (Proof of \(WJ=I\).) Let \(\mu\) be an arbitrary row vector of size \(S\) and let \(y=\mu W\). For any non-neutral state \(s\neq \tilde{s}\), we have \((yJ)(s)=\sum_{a\in\{0,1\}}y(s,a)=\mu(s)\sum_{a}\pi^\star(a\mid s)=\mu(s).\) For the neutral state \(\tilde{s}\), using \(\pi^\star(0\mid s)+\pi^\star(1\mid s)=1\) for any \(s \in \mathcal{S}\), we have \[\begin{align} (yJ)(\tilde{s}) =y(\tilde{s},0)+y(\tilde{s},1) &=(1-\alpha)(\mu\mathbf{1})+\alpha(\mu\mathbf{1}) -\sum_{s\neq \tilde{s}}\big(\pi^\star(0\mid s)+\pi^\star(1\mid s)\big)\mu(s)\\ &=(\mu\mathbf{1})-\sum_{s\neq \tilde{s}}\mu(s)=\mu(\tilde{s}). \end{align}\] Hence \(yJ=\mu\) holds for every \(\mu\), that is \(\mu(WJ)=\mu\) for all \(\mu\), so \(WJ=I\).

2. (Proof of \(W\tilde{e}=\alpha\mathbf{1}\).) Recall \(\tilde{e}\in\mathbb{R}^{SA}\) is defined by \(\tilde{e}(s,a)=\mathbb{I} (a=1)\). Again let \(\mu\) be an arbitrary row vector of size \(S\) and let \(y=\mu W\). Then \[\begin{align} y\tilde{e} =\sum_{s\in S} y(s,1) &=\sum_{s\neq \tilde{s}}\mu(s)\pi^\star(1\mid s)+y(\tilde{s},1) =\sum_{s\neq \tilde{s}}\mu(s)\pi^\star(1\mid s) +\alpha(\mu\mathbf{1})-\sum_{s\neq \tilde{s}}\mu(s)\pi^\star(1\mid s) =\alpha(\mu\mathbf{1}). \end{align}\] Equivalently, \(\mu(W\tilde{e})=\alpha(\mu\mathbf{1})=\mu(\alpha\mathbf{1})\) for all \(\mu\), so \(W\tilde{e}=\alpha\mathbf{1}\).

3. (Proof of \(W\mathbf{1}=\mathbf{1}\).) Let \(\mathbf{1}_S\) denote the all-ones vector in \(\mathbb{R}^{S}\) and \(\mathbf{1}_{SA}\) the all-ones vector in \(\mathbb{R}^{SA}\). By definition of \(J\), we have \(J \mathbf{1}_S=\mathbf{1}_{SA}\). Therefore, using \(WJ=I\) from the previous part, we have \(W\mathbf{1}_{SA}=WJ\mathbf{1}_S=I\mathbf{1}_S=\mathbf{1}_S.\)

4. (Proof of \(W \widehat{P}= \widehat{U}\).) Take an arbitrary \(\mu\) and set \(y=\mu W\). Then \(y \widehat{P}=\sum_{s\in \mathcal{S}}\sum_{a\in\{0,1\}} y(s,a)\widehat{P}_{sa}.\) For \(s\neq \tilde{s}\), we have \(y(s,a)=\mu(s)\pi^\star(a\mid s)\), so \(\sum_{a\in\{0,1\}} y(s,a)\widehat{P}_{sa} = \mu(s)e_s^\top \widehat{P}^{\pi^\star}.\) For the neutral state, \[\begin{align} y(\tilde{s},0) \widehat{P}_{\tilde{s}0} + y(\tilde{s},1) \widehat{P}_{\tilde{s}1} &=\Big((1-\alpha)(\mu\mathbf{1})-\sum_{s\neq \tilde{s}}\pi^\star(0\mid s)\mu(s)\Big)\widehat{P}_{\tilde{s}0} +\Big(\alpha(\mu\mathbf{1})-\sum_{s\neq \tilde{s}}\pi^\star(1\mid s)\mu(s)\Big)\widehat{P}_{\tilde{s}1} \\ &= \mu(\tilde{s}) e_s^\top \widehat{P}^{\pi^\star} + \left(\alpha (\mu \mathbf{1}) - \sum_{s \in \mathcal{S}} c^{\pi^\star}(s)\mu(s)\right) \widehat{\xi} \end{align}\] since \(\widehat{P}_{\tilde{s}1} = \widehat{P}_{\tilde{s}0} + \widehat{\xi}\) and \(\pi^\star(0 \mid s) = 1 - c^{\pi^\star}(s)\) for all \(s \in \mathcal{S}\). Summing over all states we have \[\begin{align} y \widehat{P}&= \left(\alpha (\mu \mathbf{1}) - \sum_{s \in \mathcal{S}} c^{\pi^\star}(s)\mu(s)\right) \widehat{\xi}+ \sum_{s \in \mathcal{S}} \mu(s) e_s^\top \widehat{P}^{\pi^\star} = \mu \left( \left( \alpha \mathbf{1}- c^{\pi^\star} \right) \widehat{\xi}+ \widehat{P}^{\pi^\star}\right) = \mu \widehat{U}. \end{align}\] We have thus shown that \(\mu W \widehat{P}= y \widehat{P}= \mu \widehat{U}\), so we have \(W \widehat{P}= \widehat{U}\).

5. (Proof of \(W P=U\).) The proof of this fact is analogous to the previous part after replacing \(\widehat{P}, \widehat{U}, \widehat{\xi}\) by \(P, U, \xi\), respectively. ◻

We now prove Lemma [lem:yhat95pert95and95feasibility].

Proof. Proof of Lemma [lem:yhat95pert95and95feasibility]. First we check the bound ?? . Since \(\widehat{y}=\widehat{\mu}W\) and \(y^\star=\mu^\star W\), using Lemma 11, we have \[\begin{align} & \widehat{y}- y^\star = (\widehat{\mu}- \mu^\star)W = \widehat{\mu}\left(\widehat{U}- U \right) H_{U} W \nonumber\\ \implies & \widehat{y}_i - y_i^\star = (\widehat{\mu}- \mu^\star)We_i = \widehat{\mu}\left(\widehat{U}- U \right) H_{U} We_i \nonumber\\ \implies & \left| \widehat{y}_i - y_i^\star \right| \leq \left\lVert \widehat{\mu}\right\rVert _{\infty \to \infty} \left\lVert \widehat{U}- U\right\rVert _{\infty \to \infty} \left\lVert H_{U}\right\rVert _{\infty \to \infty} \left\Vert We_i\right\Vert _{\infty} .\label{eq:yhat95pert95bound95int} \end{align}\tag{42}\] We have \(\left\Vert We_i\right\Vert _{\infty} \leq \max\{\alpha, 1-\alpha\} \leq 1\) for \(i = (\tilde{s}, 0), (\tilde{s}, 1)\), and \(\left\Vert We_i\right\Vert _{\infty} = 1\) for the remaining \(i=(s,a)\) which have \(\pi^\star(a \mid s) = 1\). Also \(We_i = \mathbf{0}\) if \(i = (s,a)\) where \(s \neq \tilde{s}\) and \(\pi^\star(a \mid s) = 0\). In all cases we have \(\left\Vert W e_i\right\Vert _{\infty} \leq 1\). Combining the above bound with the fact that \(\left\lVert \widehat{\mu}\right\rVert _{\infty \to \infty} = 1\), we obtain the desired bound.

We now verify feasibility of \(\widehat{y}\) for the perturbed primal LP 3. Using Lemma 29 and Lemma 28, we have \(\widehat{y}\tilde{e}=\widehat{\mu}W\tilde{e}=\widehat{\mu}(\alpha\mathbf{1})=\alpha, \widehat{y}\mathbf{1}=\widehat{\mu}W\mathbf{1}=\widehat{\mu}\mathbf{1}=1, \widehat{y}\widehat{P}=\widehat{\mu}W\widehat{P}=\widehat{\mu}\widehat{U}=\widehat{\mu}=\widehat{\mu}WJ=\widehat{y}J..\) Thus it remains to check nonnegativity. If \(i=(s,a)\), \(s\neq\tilde{s}\), and \(\pi^\star(a\mid s)=0\), then \(y^\star_i=0\) and \(We_i=\mathbf{0}\), so 42 gives \(\widehat{y}_i=0\). For indices \(i\) with \(y^\star_i>0\), using \(\left\lVert We_i\right\rVert _{\infty \to \infty}\le1\) and 42 , \[\begin{align} |\widehat{y}_i - y^\star_i| &\leq \left\lVert \widehat{\mu}\right\rVert _{\infty \to \infty} \left\lVert \widehat{U}- U\right\rVert _{\infty \to \infty} \left\lVert H_{U}\right\rVert _{\infty \to \infty} \left\Vert We_i\right\Vert _{\infty} \leq \left\lVert \widehat{U}- U\right\rVert _{\infty \to \infty} \left\lVert H_{U}\right\rVert _{\infty \to \infty} \stackrel{(*)}{\leq} \frac{1}{2}\min_{j : y^\star_j > 0} y^\star_j \leq \frac{1}{2} y^\star_i \end{align}\] where \((*)\) follows from the assumption ?? . Hence \(\widehat{y}_i\ge y^\star_i/2>0\) for all \(i\) with \(y^\star_i>0\). Therefore \(\widehat{y}\ge0\), and all constraints of 3 are satisfied. ◻

13.4 Proof of Lemma 14↩︎

Proof. Proof. Each row of \(W\) is only supported on indices \(i\) such that \(y^\star_i > 0\), and hence where 25 holds. Therefore we have \(W (r + \lambda^\star \tilde{e} + Ph^\star) = W(\zeta^\star \mathbf{1}+ Jh^\star).\) Using the properties of \(W\) from Lemma 29 that \(WP = U, W \mathbf{1}= \mathbf{1}, W J = I\), and \(W \tilde{e} = \alpha \mathbf{1}\), the above can be simplified to \(Wr + \lambda^\star \alpha \mathbf{1}+ U h^\star = \zeta^\star \mathbf{1}+ h^\star.\) Eliminating \(\zeta^\star\) using that \(\zeta^\star = \mu^\star W r + \lambda^\star \alpha\) (since the primal value \(y^\star r = \mu^\star W r\) must be equal to the dual value \(\xi^\star - \alpha \lambda^\star\)), we obtain \(Wr + \lambda^\star \alpha \mathbf{1}+ U h^\star = (\mu^\star W r + \lambda^\star \alpha) \mathbf{1}+ h^\star\) which simplifies further to \((I - U)h^\star = Wr - \mu^\star W r \mathbf{1}.\) The solutions to this Poisson-like equation can be characterized using the assumed invertibility of \((I - (U-\mathbf{1}\mu^\star))\). Rewriting the equation as \(\left(I - (U-\mathbf{1}\mu^\star)\right)h^\star = (I - \mathbf{1}\mu^\star)Wr + \mathbf{1}\mu^\star h,\) we obtain \[\begin{align} h^\star &= \left(I - (U-\mathbf{1}\mu^\star)\right)^{-1}\left( (I - \mathbf{1}\mu^\star)Wr + \mathbf{1}\mu^\star h^\star\right)\\ &=\left(I - (U-\mathbf{1}\mu^\star)\right)^{-1} Wr - \mathbf{1}\mu^\star Wr + \mathbf{1}\mu^\star h^\star = H_U Wr + \mathbf{1}\mu^\star h^\star \end{align}\] using that \(\left(I - (U-\mathbf{1}\mu^\star)\right)^{-1} \mathbf{1}= \mathbf{1}\), which follows from the fact that \(H_U \mathbf{1}= \mathbf{0}\) (Lemma 27). ◻

13.5 Proof of Lemma 15 and Lemma [lem:pert95dual95LP95ineq95consts]↩︎

Before checking the feasibility of \((\widehat{\zeta}, \widehat{\lambda}, \widehat{h})\), we compute one more useful fact about \(Wr\).

Lemma 30. We have \(Wr = r^{\pi^\star} + (c^{\pi^\star} - \alpha \mathbf{1})(r(\tilde{s},0) - r(\tilde{s},1)).\)

Proof. Proof. For \(s \neq \tilde{s}\), using 40 we have \[\begin{align} (Wr)(s) &= \sum_{s'a'} W_{s, s'a'} r(s',a') \\ &= \pi^\star(0 \mid s) r(s,0) + \pi^\star(1 \mid s) r(s,1) + \left((1-\alpha) - \pi^\star(0\mid s) \right) r(\tilde{s},0) + \left( \alpha - \pi^\star(1\mid s)\right) r(\tilde{s},1) \\ &= r^{\pi^\star}(s) - \alpha r(\tilde{s},0) + \alpha r(\tilde{s},1) + c^{\pi^\star}(s)r(\tilde{s},0) - c^{\pi^\star}(s)r(\tilde{s},1) \\ &=r^{\pi^\star}(s) + (c^{\pi^\star}(s) - \alpha)(r(\tilde{s},0) - r(\tilde{s},1)). \end{align}\] For \(s = \tilde{s}\), using 41 we have \[\begin{align} (Wr)(\tilde{s}) &= \sum_{s'a'} W_{\tilde{s}, s'a'} r(s',a') = (1-\alpha )r(\tilde{s},0) + \alpha r(\tilde{s},1) \\ &= (1-\alpha )r(\tilde{s},0) + \alpha r(\tilde{s},1) + r^{\pi^\star}(\tilde{s}) - \pi^\star(1 \mid \tilde{s})r(\tilde{s},1) - \pi^\star(0 \mid \tilde{s})r(\tilde{s},0) \\ &= r^{\pi^\star}(\tilde{s}) + (c^{\pi^\star}(\tilde{s}) - \alpha)(r(\tilde{s},0) - r(\tilde{s},1)). \end{align}\] Therefore we have that \(Wr = r^{\pi^\star} + (c^{\pi^\star} - \alpha \mathbf{1})(r(\tilde{s},0) - r(\tilde{s},1))\) as desired. ◻

Proof. Proof of Lemma 15. From the fact that \((I - \widehat{U})H_{\widehat{U}} = I - \mathbf{1}\widehat{\mu}\) from Lemma 28, we have that \(\widehat{h}- \widehat{U}\widehat{h}= Wr - \mathbf{1}\widehat{\mu}Wr \nonumber\) which implies, after rearranging and using \(\widehat{\mu}W r = \widehat{\zeta}- \widehat{\lambda}\alpha\) from the definition 27 of \(\widehat{\zeta}\), that \[\begin{align} \widehat{h}+ \widehat{\zeta}\mathbf{1}= Wr + \widehat{U}\widehat{h}+ \widehat{\lambda}\alpha \mathbf{1}= Wr + \widehat{P}^{\pi^\star} \widehat{h}- \left(c^{\pi^\star} - \alpha \mathbf{1}\right)\widehat{\xi}\widehat{h}+ \widehat{\lambda}\alpha \mathbf{1}. \label{eq:h3943rho39161Wr43U39h39} \end{align}\tag{43}\] Using Lemma 30 as well as the definition 26 of \(\widehat{\lambda}=r(\tilde{s},0) - r(\tilde{s},1) - \widehat{\xi}\widehat{h}\), we can compute that \[\begin{align} &Wr + \widehat{P}^{\pi^\star} \widehat{h}- \left(c^{\pi^\star} - \alpha \mathbf{1}\right)\widehat{\xi}\widehat{h}+ \widehat{\lambda}\alpha \mathbf{1}\\ &= \left(r^{\pi^\star} + (c^{\pi^\star} - \alpha \mathbf{1})(r(\tilde{s},0) - r(\tilde{s},1)) \right) + \widehat{P}^{\pi^\star} \widehat{h}- \left(c^{\pi^\star} - \alpha \mathbf{1}\right)\left( r(\tilde{s},0) - r(\tilde{s},1) - \widehat{\lambda}\right) + \widehat{\lambda}\alpha \mathbf{1}\\ &= r^{\pi^\star} + \widehat{P}^{\pi^\star} \widehat{h}+ \widehat{\lambda}c^{\pi^\star} \end{align}\] Combining this with 43 , we obtain that \[\begin{align} r^{\pi^\star} + \widehat{P}^{\pi^\star} \widehat{h}+ \widehat{\lambda}c^{\pi^\star}=\widehat{h}+\widehat{\zeta}\mathbf{1}. \label{eq:pert95LP95bellman95eqn} \end{align}\tag{44}\]

Finally we check the equality of the rows involving the neutral state. As discussed above, the definition 26 of \(\widehat{\lambda}\) is \(\widehat{\lambda} = r(\tilde{s},0) - r(\tilde{s},1) - \widehat{\xi}\widehat{h}= r(\tilde{s},0) - r(\tilde{s},1) - \widehat{\xi}\widehat{h}= r(\tilde{s},0) - r(\tilde{s},1) -(\widehat{P}_{\tilde{s}1} - \widehat{P}_{\tilde{s}0})\widehat{h}\) which directly rearranges to \[\begin{align} r(\tilde{s},0) + \widehat{P}_{\tilde{s}0} \widehat{h}= r(\tilde{s},1) + \widehat{\lambda}+ \widehat{P}_{\tilde{s}1} \widehat{h}. \label{eq:pert95equal95Q95cond} \end{align}\tag{45}\] Therefore, 45 implies \[\begin{align} r^{\pi^\star}(\tilde{s}) + e_{\tilde{s}}^\top\widehat{P}^{ \pi^\star} \widehat{h}+ \widehat{\lambda}c^{\pi^\star}(\tilde{s}) &= \pi^\star(0 \mid \tilde{s})\left(r(\tilde{s},0) + \widehat{P}_{\tilde{s}0} \widehat{h}\right) + \pi^\star(1 \mid \tilde{s})\left(r(\tilde{s},1) + \widehat{\lambda}+ \widehat{P}_{\tilde{s}1} \widehat{h}\right)\\ &= r(\tilde{s},0) + \widehat{P}_{\tilde{s}0} \widehat{h}= r(\tilde{s},1) + \widehat{\lambda}+ \widehat{P}_{\tilde{s}1} \widehat{h}. \end{align}\] Combining with 44 (specialized to just row \(\tilde{s}\)) we obtain \(r(\tilde{s},0) + \widehat{P}_{\tilde{s}0} \widehat{h}= r(\tilde{s},1) + \widehat{\lambda}+ \widehat{P}_{\tilde{s}1} \widehat{h}= \widehat{h}(\tilde{s})+\widehat{\zeta}.\) ◻

Proof. Proof of Lemma [lem:pert95dual95LP95ineq95consts]. We start by showing the first three perturbation bounds between the true dual solution and the perturbed dual candidate solution. Using Lemma 14 (and that \(\left\Vert \cdot\right\Vert _{\textrm{span}}\) is invariant to shifts by \(\mathbf{1}\)), we have that \[\begin{align} \left\Vert \widehat{h}- h^\star\right\Vert _{\textrm{span}} & =\left\Vert H_UWr-H_{\widehat{U}}Wr\right\Vert _{\textrm{span}}\\ &= \left\Vert H_U(\widehat{U}-U)H_{\widehat{U}}Wr + \mathbf{1}x Wr\right\Vert _{\textrm{span}} }\\ &= \left\Vert H_U (\widehat{U}-U) h^\star + H_U (\widehat{U}-U) (\widehat{h}-h^\star)\right\Vert _{\textrm{span}} \\ & \le \left\Vert H_U (\widehat{U}-U) h^\star\right\Vert _{\textrm{span}} + \left\lVert H_U\right\rVert _{\infty \to \infty} \left\lVert \widehat{U}-U\right\rVert _{\infty \to \infty} \left\Vert \widehat{h}-h^\star\right\Vert _{\textrm{span}} . \end{align}\] After rearranging, we obtain the bound \[\begin{align} \left\Vert \widehat{h}- h^\star\right\Vert _{\textrm{span}} \leq \frac{\left\Vert H_U (\widehat{U}-U) h^\star\right\Vert _{\textrm{span}}}{1-\left\lVert H_U\right\rVert _{\infty \to \infty} \left\lVert \widehat{U}-U\right\rVert _{\infty \to \infty}} \leq \frac{\left\lVert H_U\right\rVert _{\infty \to \infty} \left\lVert \widehat{U}- U\right\rVert _{\infty \to \infty} \left\Vert h^\star\right\Vert _{\textrm{span}}}{1-\left\lVert H_U\right\rVert _{\infty \to \infty} \left\lVert \widehat{U}-U\right\rVert _{\infty \to \infty}} \end{align}\] since \[\begin{align} \left\Vert H_U (\widehat{U}-U) h^\star\right\Vert _{\textrm{span}} &= \inf_{\kappa \in \mathbb{R}} \left\Vert H_U (\widehat{U}-U) (h^\star- \kappa \mathbf{1})\right\Vert _{\textrm{span}}\\ &\leq 2 \inf_{\kappa \in \mathbb{R}}\left\Vert H_U (\widehat{U}-U) (h^\star- \kappa \mathbf{1})\right\Vert _{\infty} \\ &\leq 2 \left\lVert H_U\right\rVert _{\infty \to \infty} \left\lVert \widehat{U}- U\right\rVert _{\infty \to \infty} \inf_{\kappa \in \mathbb{R}}\left\Vert h^\star - \kappa \mathbf{1}\right\Vert _{\infty} = \left\lVert H_U\right\rVert _{\infty \to \infty} \left\lVert \widehat{U}- U\right\rVert _{\infty \to \infty} \left\Vert h^\star\right\Vert _{\textrm{span}}. \end{align}\] Next, for \(\widehat{\lambda}-\lambda\), we have \[\begin{align} \widehat{\lambda}- \lambda &= \xi h^\star - \widehat{\xi}\widehat{h} = (\xi - \widehat{\xi}) h^\star + \widehat{\xi}(h^\star - \widehat{h}) = (\xi - \widehat{\xi}) (h^\star - \kappa \mathbf{1}) + \widehat{\xi}(h^\star - \widehat{h}- \kappa' \mathbf{1}) \end{align}\] for any \(\kappa, \kappa' \in \mathbb{R}\), since as checked previously \(\xi \mathbf{1}= \widehat{\xi}\mathbf{1}= 0\). Hence \[\begin{align} \left| \widehat{\lambda}- \lambda \right| & \leq \left\lVert \xi - \widehat{\xi}\right\rVert _{\infty \to \infty} \inf_{\kappa \in \mathbb{R}}\left\Vert h^\star - \kappa \mathbf{1}\right\Vert _{\infty} + \inf_{\kappa' \in \mathbb{R}}\left\lVert \widehat{\xi}\right\rVert _{\infty \to \infty} \left\Vert h^\star - \widehat{h}- \kappa' \mathbf{1}\right\Vert _{\infty} \\ &= \frac{1}{2}\left\lVert \xi - \widehat{\xi}\right\rVert _{\infty \to \infty} \left\Vert h^\star\right\Vert _{\textrm{span}} + \frac{1}{2}\left\lVert \widehat{\xi}\right\rVert _{\infty \to \infty} \left\Vert \widehat{h}- h^\star\right\Vert _{\textrm{span}} \leq \frac{1}{2}\left\lVert \xi - \widehat{\xi}\right\rVert _{\infty \to \infty} \left\Vert h^\star\right\Vert _{\textrm{span}} + \left\Vert \widehat{h}- h^\star\right\Vert _{\textrm{span}} \end{align}\] using that \(\left\lVert \widehat{\xi}\right\rVert _{\infty \to \infty} = \left\lVert \widehat{P}_{\tilde{s} 1} - \widehat{P}_{\tilde{s} 0}\right\rVert _{\infty \to \infty} \leq \left\lVert \widehat{P}_{\tilde{s} 1}\right\rVert _{\infty \to \infty} + \left\lVert \widehat{P}_{\tilde{s} 0}\right\rVert _{\infty \to \infty} = 2\). Next we bound \(|\widehat{\zeta}- \zeta|\). We have, for an arbitrary \(\kappa \in \mathbb{R}\), that \[\begin{align} \widehat{\zeta}- \zeta = \widehat{\mu}Wr + \widehat{\lambda}\alpha - \mu^\star Wr + \lambda \alpha &= (\widehat{\mu}- \mu) Wr + (\widehat{\lambda}- \lambda) \alpha \\ & = \widehat{\mu}(\widehat{U}- U) H_U Wr + (\widehat{\lambda}- \lambda) \alpha = \widehat{\mu}(\widehat{U}- U ) (h^\star +\kappa \mathbf{1}) + (\widehat{\lambda}- \lambda) \alpha \end{align}\] using the identity for \(\widehat{\mu}- \mu^\star\) shown in Lemma 11 as well as that \(h^\star\) is equal to \(H_U W r\) plus a shift by a multiple of \(\mathbf{1}\) (by Lemma 14) and \((\widehat{U}- U ) \mathbf{1}= \mathbf{0}\) (by Lemma 27). Now by triangle inequality we can bound \[\begin{align} \left| \widehat{\zeta}- \zeta \right| & \leq \left\lVert \widehat{\mu}\right\rVert _{\infty \to \infty} \left\lVert \widehat{U}- U\right\rVert _{\infty \to \infty} \inf_{\kappa \in \mathbb{R}} \left\Vert h^\star + \kappa \mathbf{1}\right\Vert _{\infty} + \left|\widehat{\lambda}- \lambda \right||\alpha| \leq \left\lVert \widehat{U}- U\right\rVert _{\infty \to \infty} \frac{1}{2}\left\Vert h^\star\right\Vert _{\textrm{span}} + \left|\widehat{\lambda}- \lambda \right| \end{align}\] since \(\left\lVert \widehat{\mu}\right\rVert _{\infty \to \infty} = 1\) (because Lemma [lem:yhat95pert95and95feasibility] implies that it is a probability distribution) and \(|\alpha| \leq 1\).

Now we show the final part of the lemma statement. Our goal is equivalently to show that elementwise \(M \left( r + \widehat{\lambda}\tilde{e} + \widehat{P}\widehat{h}- \widehat{\zeta}- J \widehat{h}\right) < \mathbf{0},\) where \(M\) is the matrix which selects only the rows in the conclusion of the lemma, that is, \(M \in \mathbb{R}^{(S-1) \times (SA)}\), each row of \(M\) is only supported on the entries \((s,a)\) such that \(s \neq \tilde{s}\) and \(\pi^\star(a \mid s) = 1\), and each row of \(M\) is distinct and has only one nonzero entry. We start from the identity \(r + \widehat{\lambda}\tilde{e} + \widehat{P}\widehat{h}- \widehat{\zeta}- J \widehat{h} = (\widehat{P}- P)h^\star + (\widehat{P}- J)(\widehat{h}-h^\star) + (\widehat{\lambda}- \lambda)\tilde{e} - (\widehat{\zeta}-\zeta)\mathbf{1}+ \left(r + \lambda \tilde{e} + Ph^\star - \zeta - J h^\star \right),\) and now we will apply the projection matrix \(M\) and attempt to upper-bound the result. We calculate \[\begin{align} M \left( r + \widehat{\lambda}\tilde{e} + \widehat{P}\widehat{h}- \widehat{\zeta}- J \widehat{h}\right) \\&= M \left( (\widehat{P}- P)h^\star + (\widehat{P}- J)(\widehat{h}-h^\star) + (\widehat{\lambda}- \lambda)\tilde{e} - (\widehat{\zeta}-\zeta)\mathbf{1}+ \left(r + \lambda \tilde{e} + Ph^\star - \zeta - J h^\star \right)\right) \\ &= M \Big( (\widehat{P}- P)(h^\star - \kappa \mathbf{1}) + (\widehat{P}- J)(\widehat{h}-h^\star - \kappa' \mathbf{1}) + (\widehat{\lambda}- \lambda)\tilde{e} - (\widehat{\zeta}-\zeta)\mathbf{1} + \left(r + \lambda \tilde{e} + Ph^\star - \zeta - J h^\star \right)\Big) \\ & \leq M \left(r + \lambda \tilde{e} + Ph^\star - \zeta - J h^\star \right) + \left\lVert \widehat{P}- P \right\rVert _{\infty \to \infty}\left\Vert h^\star - \kappa \mathbf{1}\right\Vert _{\infty}\mathbf{1}\\ & \qquad + \left\lVert \widehat{P}- J\right\rVert _{\infty \to \infty} \left\Vert \widehat{h}-h^\star - \kappa' \mathbf{1}\right\Vert _{\infty}\mathbf{1}+ \left|\widehat{\lambda}- \lambda \right| \left\Vert \tilde{e}\right\Vert _{\infty} \mathbf{1}+ \left|\widehat{\zeta}-\zeta\right|\mathbf{1}\\ & \leq M \left(r + \lambda \tilde{e} + Ph^\star - \zeta - J h^\star \right) + \left\lVert \widehat{P}- P \right\rVert _{\infty \to \infty} \frac{1}{2}\left\Vert h^\star\right\Vert _{\textrm{span}}\mathbf{1} + \left\Vert \widehat{h}- h^\star\right\Vert _{\textrm{span}}\mathbf{1}+ \left|\widehat{\lambda}- \lambda \right|\mathbf{1}+ \left|\widehat{\zeta}-\zeta\right|\mathbf{1}\end{align}\] using that \((\widehat{P}-P) \mathbf{1}= \mathbf{0}\) and \((\widehat{P}- J) \mathbf{1}= \mathbf{0}\) for the second equality, and then that \(\left\lVert J\right\rVert _{\infty \to \infty} = \max_{s a} \left\Vert e_s\right\Vert _{1} = 1\), \(\left\Vert \tilde{e}\right\Vert _{\infty} = 1\), \(\left\lVert M\right\rVert _{\infty \to \infty}= 1\), and choosing \(\kappa \in \mathbb{R}\) so that \(\left\Vert h^\star - \kappa \mathbf{1}\right\Vert _{\infty}= \left\Vert h^\star\right\Vert _{\textrm{span}}/2\) for the inequality steps.

Using the first three bounds shown in this lemma, we have that \[\begin{align} &\left\lVert \widehat{P}- P \right\rVert _{\infty \to \infty} \frac{1}{2}\left\Vert h^\star\right\Vert _{\textrm{span}} + \left\Vert \widehat{h}- h^\star\right\Vert _{\textrm{span}} + \left|\widehat{\lambda}- \lambda \right| + \left|\widehat{\zeta}-\zeta\right| \nonumber\\ & \leq \frac{\delta }{2}\left\Vert h^\star\right\Vert _{\textrm{span}} + \left\Vert \widehat{h}- h^\star\right\Vert _{\textrm{span}} + \left|\widehat{\lambda}- \lambda \right|+ \left\lVert \widehat{U}- U\right\rVert _{\infty \to \infty} \frac{1}{2}\left\Vert h^\star\right\Vert _{\textrm{span}} + \left|\widehat{\lambda}- \lambda \right| \nonumber\\ & \leq \frac{\delta }{2}\left\Vert h^\star\right\Vert _{\textrm{span}} + \left\Vert \widehat{h}- h^\star\right\Vert _{\textrm{span}} + 2\left|\widehat{\lambda}- \lambda \right|+ \frac{3\delta }{2}\left\Vert h^\star\right\Vert _{\textrm{span}}\nonumber\\ & \leq 2 \delta \left\Vert h^\star\right\Vert _{\textrm{span}} + \left\Vert \widehat{h}- h^\star\right\Vert _{\textrm{span}} + 2\left( \frac{1}{2}\left\lVert \xi - \widehat{\xi}\right\rVert _{\infty \to \infty} \left\Vert h^\star\right\Vert _{\textrm{span}} + \left\Vert \widehat{h}- h^\star\right\Vert _{\textrm{span}}\right) \nonumber\\ & \leq 4 \delta \left\Vert h^\star\right\Vert _{\textrm{span}} + 3\left\Vert \widehat{h}- h^\star\right\Vert _{\textrm{span}} \nonumber\\ & \leq 4 \delta \left\Vert h^\star\right\Vert _{\textrm{span}} + 3 \frac{\left\lVert H_U\right\rVert _{\infty \to \infty} \left\lVert \widehat{U}- U\right\rVert _{\infty \to \infty} \left\Vert h^\star\right\Vert _{\textrm{span}}}{1-\left\lVert H_U\right\rVert _{\infty \to \infty} \left\lVert \widehat{U}-U\right\rVert _{\infty \to \infty}}\nonumber\\ & \leq 4 \delta \left\Vert h^\star\right\Vert _{\textrm{span}} + 3 \frac{\left\lVert H_U\right\rVert _{\infty \to \infty} 3\delta \left\Vert h^\star\right\Vert _{\textrm{span}}}{1-\left\lVert H_U\right\rVert _{\infty \to \infty} \left\lVert \widehat{U}- U\right\rVert _{\infty \to \infty}} \label{eq:pert95dual95ineq95const95terms95bd951} \end{align}\tag{46}\] where also we simplified by using that \(\left\lVert \widehat{P}- P \right\rVert _{\infty \to \infty} \leq \delta\) by assumption, that \(\left\lVert \widehat{\xi}- \xi\right\rVert _{\infty \to \infty} \leq 2 \left\lVert \widehat{P}- P\right\rVert _{\infty \to \infty} \leq 2 \delta\), and \[\begin{align} \left\lVert \widehat{U}- U\right\rVert _{\infty \to \infty} &= \left\lVert P^{\pi^\star} - (c^{\pi^\star} -\alpha \mathbf{1})\xi- \widehat{P}^{\pi^\star} + (c^{\pi^\star} -\alpha \mathbf{1})\widehat \xi\right\rVert _{\infty \to \infty} \\ & \leq \left\lVert P^{\pi^\star} - \widehat{P}^{\pi^\star}\right\rVert _{\infty \to \infty} + \left\Vert c^{\pi^\star} -\alpha \mathbf{1}\right\Vert _{\infty} \left\lVert \xi - \widehat \xi\right\rVert _{\infty \to \infty} \leq \delta + 1\cdot 2 \delta = 3\delta. \end{align}\] Note that ?? implies that \(\left\lVert \widehat{U}- U\right\rVert _{\infty \to \infty} \leq \frac{1}{2}\frac{\sqrt{\mu_{\min}^\star}}{\left\lVert H_U\right\rVert _{\mu^\star\to\mu^\star}} \leq \frac{1}{2} \frac{1}{\left\lVert H_U\right\rVert _{\infty \to \infty}},\) where the second inequality is because \(\left\lVert H_U\right\rVert _{\infty \to \infty} \leq \frac{1}{\sqrt{\mu^\star_{\min}}}\left\lVert H_U\right\rVert _{\mu^\star\to\mu^\star}\). Hence we can further simplify 46 and bound \[\begin{align} 4 \delta \left\Vert h^\star\right\Vert _{\textrm{span}} + 3 \frac{\left\lVert H_U\right\rVert _{\infty \to \infty} 3\delta \left\Vert h^\star\right\Vert _{\textrm{span}}}{1-\left\lVert H_U\right\rVert _{\infty \to \infty} \left\lVert \widehat{U}- U\right\rVert _{\infty \to \infty}} &\leq 4 \delta \left\Vert h^\star\right\Vert _{\textrm{span}} + 3 \frac{\left\lVert H_U\right\rVert _{\infty \to \infty} 3\delta \left\Vert h^\star\right\Vert _{\textrm{span}}}{1/2} \\ &= 4 \delta \left\Vert h^\star\right\Vert _{\textrm{span}} + 18\left\lVert H_U\right\rVert _{\infty \to \infty} \delta \left\Vert h^\star\right\Vert _{\textrm{span}}. \end{align}\]

Finally, letting \(G = \min_{sa:y^\star(s,a)=0} \zeta^\star(s) + h^\star(s) -r(s, a) - \lambda^\star \mathbb{I}(a=1) - P_{s a}h^\star > 0,\) we can combine all of our previous calculations to obtain that \[\begin{align} M \left( r + \widehat{\lambda}\tilde{e} + \widehat{P}\widehat{h}- \widehat{\zeta}- J \widehat{h}\right) & \leq M \left(r + \lambda \tilde{e} + Ph^\star - \zeta - J h^\star \right) + (4 \delta \left\Vert h^\star\right\Vert _{\textrm{span}} + 18\left\lVert H_U\right\rVert _{\infty \to \infty} \delta \left\Vert h^\star\right\Vert _{\textrm{span}})\mathbf{1}\\ & \leq -G \mathbf{1}+ (4 \delta \left\Vert h^\star\right\Vert _{\textrm{span}} + 18\left\lVert H_U\right\rVert _{\infty \to \infty} \delta \left\Vert h^\star\right\Vert _{\textrm{span}})\mathbf{1} \end{align}\] which is elementwise strictly less than \(\mathbf{0}\) when \(\delta \leq \frac{G/2}{4 \left\Vert h^\star\right\Vert _{\textrm{span}} + 18\left\lVert H_U\right\rVert _{\infty \to \infty} \left\Vert h^\star\right\Vert _{\textrm{span}}},\) as desired. ◻

13.6 Proof of Lemma 17↩︎

Now we show uniqueness of the primal and dual optimal solutions. First, letting \(\tilde{y}\) be another optimal solution to the perturbed primal LP, then \(\tilde{y}\) and \((\widehat{\zeta}, \widehat{\lambda}, \widehat{h})\) must satisfy the complementary slackness property 17 (as optimal solutions). Since we have checked in Lemma [lem:pert95dual95LP95ineq95consts] that the dual constraints are strict for all \(s,a\) such that \(y^\star(s,a) = 0\), this implies that we must have that \(\tilde{y}(s,a)=0\) for all \(s,a\) such that \(y^\star(s,a)=0\). This implies that, letting \(\tilde{\mu}(s)= \tilde{y}(s,0)+\tilde{y}(s,1)\), we have that \(\tilde{y} = \tilde{\mu} W\), since \(\tilde{y}\) is supported on a (possibly non-proper) subset of the support of \(y^\star\), and also \(\tilde{y} \tilde{e} = \alpha\) by its feasibility for the primal perturbed LP. Then since primal feasibility also guarantees \(\tilde{y}P = \tilde{y}J\), we have \(\tilde{\mu} \widehat{U}= \tilde{\mu} W \widehat{P}= \tilde{y} \widehat{P}= \tilde{y} J = \tilde{\mu} W J = \tilde{\mu} I = \tilde{\mu}.\) From the fact that \(\tilde{\mu} \widehat{U}= \tilde{\mu}\), we can derive that \[\begin{align} \tilde{\mu} (\widehat{U}- \mathbf{1}\widehat{\mu}) = \tilde{\mu}\widehat{U}- \tilde{\mu}\mathbf{1}\widehat{\mu}= \tilde{\mu} - \widehat{\mu} \quad\implies\quad &\widehat{\mu}= \tilde{\mu}\left(I - (\widehat{U}- \mathbf{1}\widehat{\mu}) \right) \\ \quad\implies\quad & \tilde{\mu} = \widehat{\mu}\left(I - (\widehat{U}- \mathbf{1}\widehat{\mu}) \right)^{-1} = \widehat{\mu}H_{\widehat{U}} + \widehat{\mu}\mathbf{1}\widehat{\mu}= \widehat{\mu} \end{align}\] using that \(\tilde{\mu} \mathbf{1}= \tilde{\mu} W \mathbf{1}= \tilde{y} \mathbf{1}= 1\) by primal feasibility of \(\tilde{y}\) in the first line, and then invertibility of \(I - (\widehat{U}- \mathbf{1}\widehat{\mu})\) (by Lemma 12) and then the facts that \(\widehat{\mu}H_{\widehat{U}} = \mathbf{0}\) and \(\widehat{\mu}\mathbf{1}= 1\) (both from Lemma 28) in the final line. Finally, \(\widehat{\mu}= \tilde{\mu}\) implies that \(\tilde{y} = \tilde{\mu} W = \widehat{\mu}W = \widehat{y}\), so we have shown uniqueness of \(\widehat{y}\).

Now we show the uniqueness properties of the dual solution. These steps are analogous to those of Lemma 14. Let \((\tilde{\zeta}, \tilde{\lambda}, \tilde{h})\) be some dual optimal solution. By complementary slackness between \((\tilde{\zeta}, \tilde{\lambda}, \tilde{h})\) and \(\widehat{y}\), for all \(s,a\) such that \(\widehat{y}(s,a)>0\) we have \(r(s,a)+\tilde{\lambda} \mathbb{I}(a=1) + \widehat{P}_{sa}\tilde{h} = \tilde{\zeta} + \tilde{h}(s)\). By the construction of \(\widehat{y}\) and Lemma [lem:yhat95pert95and95feasibility], these are exactly the \(s,a\) such that \(y^\star(s,a)>0\). Each row of \(W\) is only supported on such such \((s,a)\), so we have that \(W(r + \tilde{\lambda} + \widehat{P}\tilde{h}) = W(\tilde{\zeta} \mathbf{1}+ J \tilde{h}).\) Using the properties of \(W\) from Lemma 29 that \(W\widehat{P}= \widehat{U}\), \(W \mathbf{1}= \mathbf{1}\), \(WJ = I\), and \(W \tilde{e} = \alpha \mathbf{1}\), the above simplifies to \(Wr + \tilde{\lambda} \alpha \mathbf{1}+ \widehat{U}\tilde{h} = \tilde{\zeta} \mathbf{1}+ \tilde{h}.\) Since \((\tilde{\zeta}, \tilde{\lambda}, \tilde{h})\) is dual optimal and has the same objective value as \(\widehat{y}\) for the perturbed primal LP, we have that \(\tilde{\zeta} = \widehat{\mu}W r + \tilde{\lambda} \alpha\). Combining this with the previous display equation, we obtain that \((I - \widehat{U})\tilde{h} = Wr - \widehat{\mu}W r \mathbf{1}.\) After rewriting this as \((I - (\widehat{U}- \mathbf{1}\widehat{\mu})) \tilde{h} = (I - \mathbf{1}\widehat{\mu}) Wr + \mathbf{1}\widehat{\mu}\tilde{h}\) and then multiplying by \((I - (\widehat{U}- \mathbf{1}\widehat{\mu}))^{-1}\), we obtain that \[\begin{align} \tilde{h} &= (I - (\widehat{U}- \mathbf{1}\widehat{\mu}))^{-1} \left( (I - \mathbf{1}\widehat{\mu}) Wr + \mathbf{1}\widehat{\mu}\tilde{h} \right) \\ &= (I - (\widehat{U}- \mathbf{1}\widehat{\mu}))^{-1}Wr - \mathbf{1}\widehat{\mu}Wr + \mathbf{1}\widehat{\mu}\tilde{h} = H_{\widehat{U}} Wr + \mathbf{1}\widehat{\mu}\tilde{h} = \widehat{h}+ \mathbf{1}\widehat{\mu}\tilde{h} \end{align}\] using that \((I - (\widehat{U}- \mathbf{1}\widehat{\mu}))^{-1} \mathbf{1}= \mathbf{1}\), which follows from \(H_{\widehat{U}} \mathbf{1}= \mathbf{0}\) (Lemma 28). The equalities implied by the aforementioned complementary slackness between between \((\tilde{\zeta}, \tilde{\lambda}, \tilde{h})\) and \(\widehat{y}\) also ensure that \(r(\tilde{s},0) + \widehat{P}_{\tilde{s}0}\tilde{h} = \tilde{\zeta} + \tilde{h}(\tilde{s}) = r(\tilde{s},1)+\tilde{\lambda} + \widehat{P}_{\tilde{s}1}\tilde{h}\) (by considering \((s,a)= (\tilde{s}, 0)\) and \((\tilde{s},1)\)). Hence by rearranging we have \[\begin{align} \tilde{\lambda} = r(\tilde{s},0)-r(\tilde{s},1) - \widehat{P}_{\tilde{s}1}\tilde{h} +\widehat{P}_{\tilde{s}0}\tilde{h} &= r(\tilde{s},0)-r(\tilde{s},1) - \widehat{\xi}\tilde{h} \\ &= r(\tilde{s},0)-r(\tilde{s},1) - \widehat{\xi}(\widehat{h}+ \mathbf{1}\widehat{\mu}\tilde{h}) = r(\tilde{s},0)-r(\tilde{s},1) - \widehat{\xi}\widehat{h} = \widehat{\lambda} \end{align}\] using the fact that \(\widehat{\xi}\mathbf{1}= \mathbf{0}\) and the definition 26 of \(\widehat{\lambda}\). Finally, we have already shown that \(\tilde{\zeta} = \widehat{\mu}W r + \tilde{\lambda} \alpha\), but now since we have also shown that \(\tilde{\lambda} = \widehat{\lambda}\), by combining with the definition 27 of \(\widehat{\zeta}\), we furthermore can conclude that \(\tilde{\zeta} = \widehat{\zeta}\).

13.7 Proof of Lemma 18↩︎

As shown in the proof of Lemma [lem:pert95dual95LP95ineq95consts], we have \(\left\lVert \widehat{\xi}- \xi\right\rVert _{\infty \to \infty} \leq 2\delta\) and \(\left\lVert \widehat{U}- U\right\rVert _{\infty \to \infty} \leq 3 \delta\). We will now use these to simplify the various perturbation bounds. From Lemma [lem:yhat95pert95and95feasibility], we have \(\left\Vert \widehat{y}- y^\star\right\Vert _{\infty} \leq \left\lVert \widehat{U}- U\right\rVert _{\infty \to \infty} \left\lVert H_U\right\rVert _{\infty \to \infty} \leq 3 \left\lVert H_U\right\rVert _{\infty \to \infty}\delta .\) As shown in the proof of Lemma [lem:pert95dual95LP95ineq95consts], under the condition ?? we have \[\begin{align} \left\Vert \widehat{h}- h^\star\right\Vert _{\textrm{span}} &\leq \frac{\left\lVert H_U\right\rVert _{\infty \to \infty} \left\lVert \widehat{U}- U\right\rVert _{\infty \to \infty} \left\Vert h^\star\right\Vert _{\textrm{span}}}{1-\left\lVert H_U\right\rVert _{\infty \to \infty} \left\lVert \widehat{U}-U\right\rVert _{\infty \to \infty}} \leq 2 \left\lVert H_U\right\rVert _{\infty \to \infty} \left\lVert \widehat{U}- U\right\rVert _{\infty \to \infty} \left\Vert h^\star\right\Vert _{\textrm{span}}. \end{align}\] Hence \(\left\Vert \widehat{h}- h^\star\right\Vert _{\textrm{span}} \leq 6 \delta \left\lVert H_U\right\rVert _{\infty \to \infty} \left\Vert h^\star\right\Vert _{\textrm{span}}.\) Now for the other perturbation bounds from Lemma [lem:pert95dual95LP95ineq95consts], we can simplify them as \[\begin{align} \left| \widehat{\lambda}- \lambda \right| & \leq \frac{1}{2}\left\lVert \xi - \widehat{\xi}\right\rVert _{\infty \to \infty} \left\Vert h^\star\right\Vert _{\textrm{span}} + \left\Vert \widehat{h}- h^\star\right\Vert _{\textrm{span}} \leq \delta \left\Vert h^\star\right\Vert _{\textrm{span}} + 6 \delta \left\lVert H_U\right\rVert _{\infty \to \infty} \left\Vert h^\star\right\Vert _{\textrm{span}} \end{align}\] and \[\begin{align} \left| \widehat{\zeta}- \zeta \right| & \leq \left\lVert \widehat{U}- U\right\rVert _{\infty \to \infty} \frac{1}{2}\left\Vert h^\star\right\Vert _{\textrm{span}} + \left|\widehat{\lambda}- \lambda \right| \leq \frac{3}{2}\delta \left\Vert h^\star\right\Vert _{\textrm{span}} + \delta \left\Vert h^\star\right\Vert _{\textrm{span}} + 6 \delta \left\lVert H_U\right\rVert _{\infty \to \infty} \left\Vert h^\star\right\Vert _{\textrm{span}}. \end{align}\]

Finally, we confirm that all assumptions are satisfied for all the lemmas used in this proof. To ensure ?? , if we require \(\delta \leq \frac{\sqrt{\mu^\star_{\min}}}{6}\frac{1 - \left\lVert \Phi\right\rVert _{\mu^\star\to\mu^\star}}{1 + {\left\lVert H_{U}\right\rVert _{\mu^\star\to\mu^\star}}/{\sqrt{\mu^\star_{\min}}} }\) then we will have \(\left\lVert \widehat{U}-U\right\rVert _{\mu^\star\to\mu^\star} \leq 3\delta \leq \frac{1}{2}\frac{1 - \left\lVert U - \mathbf{1}\mu^\star\right\rVert _{\mu^\star\to\mu^\star}}{1 + {\left\lVert H_{U}\right\rVert _{\mu^\star\to\mu^\star}}/{\sqrt{\mu^\star_{\min}}} }\) as needed. To ensure ?? , if we require \(\delta \leq \min_{sa : y^\star(s,a)> 0} \frac{ y^\star(s,a)}{6\left\lVert H_{U}\right\rVert _{\infty \to \infty} }\) then we will have \(\left\lVert \widehat{U}-U\right\rVert _{\mu^\star\to\mu^\star} \leq 3\delta \leq \min_{sa : y^\star(s,a)> 0} \frac{ y^\star(s,a)}{2\left\lVert H_{U}\right\rVert _{\infty \to \infty} }\) as needed.

13.8 Proof of Lemma 19↩︎

By support preservation, \(\widehat{\Bar{\pi}}^\star(s)=\Bar{\pi}^\star(s)\) for all \(s\neq\tilde{s}\). Hence the two policies can differ only at the neutral state \(\tilde{s}\). By the perturbation bound for \(\widehat{y}^\star\), and by the definition of \(\delta_{\min}\), for each \(a\in\{0,1\}\), \[|y^\star(\tilde{s},a)-\widehat{y}^\star(\tilde{s},a)| \le 3\delta\left\lVert H_U\right\rVert _{\infty \to \infty} \le \frac{\mu^\star_{\min}}{48S\tau(5+\log_2S)}.\] Since \(\Bar{\pi}^\star(a\mid\tilde{s}) = \frac{y^\star(\tilde{s},a)}{\mu^\star(\tilde{s})}, \widehat{\Bar{\pi}}^\star(a\mid\tilde{s}) = \frac{\widehat{y}^\star(\tilde{s},a)}{\widehat{\mu}^\star(\tilde{s})},\) and \(|\widehat{\mu}^\star(\tilde{s})-\mu^\star(\tilde{s})| \le \sum_{a\in\{0,1\}} |y^\star(\tilde{s},a)-\widehat{y}^\star(\tilde{s},a)|,\) we obtain \[|\Bar{\pi}^\star(a\mid\tilde{s})-\widehat{\Bar{\pi}}^\star(a\mid\tilde{s})| \le \frac{1}{16S\tau(5+\log_2S)}, \qquad a\in\{0,1\}.\] Therefore, \[\left\lVert P^{\Bar{\pi}^\star}-P^{\widehat{\Bar{\pi}}^\star}\right\rVert _{\infty \to \infty} \le \sum_{a\in\{0,1\}} |\Bar{\pi}^\star(a\mid\tilde{s})-\widehat{\Bar{\pi}}^\star(a\mid\tilde{s})| \le \frac{1}{8S\tau(5+\log_2S)}.\] On the other hand, by convexity of the \(\ell_1\) norm and the fifth term in the definition of \(\delta_{\min}\), \[\left\lVert P^{\widehat{\Bar{\pi}}^\star}-\widehat{P}^{\widehat{\Bar{\pi}}^\star}\right\rVert _{\infty \to \infty} \le \max_{s,a}\|P(\cdot\mid s,a)-\widehat{P}(\cdot\mid s,a)\|_1 \le \delta \le \frac{1}{8S\tau(5+\log_2S)}.\] Combining the last two displays gives \(\left\lVert P^{\Bar{\pi}^\star}-\widehat{P}^{\widehat{\Bar{\pi}}^\star}\right\rVert _{\infty \to \infty} \le \frac{1}{4S\tau(5+\log_2S)}.\) Lemma 20, applied with \(\mathcal{Z}=\mathcal{S}\), \(Q=P^{\Bar{\pi}^\star}\), and \(\widetilde{Q}=\widehat{P}^{\widehat{\Bar{\pi}}^\star}\), implies that the Markov chain induced by \(\widehat{\Bar{\pi}}^\star\) under \(\widehat{P}\) is aperiodic and unichain, with mixing time at most \((3+\log_2S)\tau\).

It remains to identify its stationary distribution. By feasibility of the perturbed primal solution, \[\sum_{s\in\mathcal{S}}\widehat{\mu}^\star(s)\widehat{\Bar{\pi}}^\star(1\mid s) = \sum_{s\in\mathcal{S}}\widehat{y}^\star(s,1) = \alpha.\] Recall that \(\widehat{U} = \widehat{P}^{\widehat{\Bar{\pi}}^\star} - (c^{\widehat{\Bar{\pi}}^\star}-\alpha\mathbf{1})\widehat{\xi}.\) Therefore, \[\begin{align} \widehat{\mu}^\star=\widehat{\mu}^\star\widehat{U}= \widehat{\mu}^\star\widehat{P}^{\widehat{\Bar{\pi}}^\star} - \widehat{\mu}^\star(c^{\widehat{\Bar{\pi}}^\star}-\alpha\mathbf{1})\widehat{\xi}= \widehat{\mu}^\star\widehat{P}^{\widehat{\Bar{\pi}}^\star} - \left( \sum_{s\in\mathcal{S}}\widehat{\mu}^\star(s)\widehat{\Bar{\pi}}^\star(1\mid s)-\alpha \right)\widehat{\xi}= \widehat{\mu}^\star\widehat{P}^{\widehat{\Bar{\pi}}^\star}. \end{align}\] So \(\widehat{\mu}^\star\) is stationary for \(\widehat{P}^{\widehat{\Bar{\pi}}^\star}\). Part 1 shows \(\widehat{\mu}^\star(s)>0\) for all \(s\in\mathcal{S}\). Since the chain has a single recurrent class and its stationary distribution puts positive mass on every state, no state can be transient. Hence the chain is irreducible. This proves part 6 and completes the proof of Theorem 3.

14 Preliminaries for the proof of Theorem 2↩︎

14.1 Two-set Policy↩︎

14.1.0.1 Two dynamic sets.

At each time \(t\), the two-set policy maintains disjoint subsets: (i) Set \(D_t^{\mathrm{OL}}\) on which we run Optimal Local Control to harvest near-optimal reward; (ii) Set \(D_t^{\bar\pi^\star}\) on which we run Unconstrained Optimal Control to steer arms toward \(\mu^\star\) and eventually merge them into \(D_t^{\mathrm{OL}}\). The remaining arms act as a buffer to satisfy the global constraint \(\sum_i A_t(i)=\alpha N\) exactly.

14.1.0.2 Subroutines.

For a subset \(D\) with state counts \(z(s)=|\{i\in D:S_t(i)=s\}|\): (i) Unconstrained Optimal Control activates an expected \(\bar\pi^\star(1\mid s)\,z(s)\) arms in each state \(s\) (using randomized rounding to handle integrality); (ii) Optimal Local Control draws a target budget \(B\in\{\lfloor \alpha|D|\rfloor,\lceil \alpha|D|\rceil\}\) with \(\mathbb{E}[B]=\alpha|D|\), and then allocates actions in \(D\) following a priority rule and using the neutral state \(\tilde{s}\) to meet the budget constraint.

14.1.0.3 Augmented state space.

Note that the Two-set policy induces a finite-state Markov chain whose state at time \(t\) is \((\boldsymbol{X}_t,D_t^{\mathrm{OL}},D_t^{\Bar{\pi}^\star})\). For a short notation, we write \(\Sigma_t=(\boldsymbol{X}_t,D_t^{\mathrm{OL}},D_t^{\Bar{\pi}^\star})\).

14.2 \(\mu^\star\)-weighted norms and operator norms↩︎

With Assumption 2, the Markov chain induced by \(\Bar{\pi}^\star\) converges to a unique stationary distribution, denoted by \(\mu^\star = (\mu^\star(s))_{s \in \mathbb{S}}\), and this Markov chain has no transient state, which means \(\mu^\star_{\min}\triangleq\min_{s}\mu^{\star}(s)>0\). Let \(\tau\) be its mixing time. From the definition of \(\Bar{\pi}^\star\), it is straightforward to verify that \(\mu^\star(s) = y^\star(s, 0) + y^\star(s, 1)\). Consequently, the long-run average reward of \(\Bar{\pi}^\star\) equals \(\rho^{\mathrm{rel}}\), and the long-run average budget usage under \(\Bar{\pi}^\star\) equals \(\alpha\). Define \(D_{\mu^{\star}}\triangleq\mathrm{diag}(\mu^{\star})\). For any vector \(f\in\mathbb{R}^{S}\) we define the weighted inner product \(\langle f,g\rangle_{\mu^{\star}} \triangleq \sum_{s\in S}\mu^{\star}(s)\,f(s)g(s)\) and weighted norm \(\left\lVert f\right\rVert _{\mu^\star} \triangleq \big(\langle f,f\rangle_{\mu^{\star}}\big)^{1/2} = \big\|D_{\mu^{\star}}^{1/2} f\big\|_{2}.\) They correspond to the Euclidean space \(L_{2}(\mu^{\star})\) equipped with the RMS weight \(\mu^{\star}\). We also use the induced norm \(\left\lVert A\right\rVert _{\mu^\star\to\mu^\star} \triangleq \sup_{f\neq 0}\frac{\left\lVert Af\right\rVert _{\mu^\star}}{\left\lVert f\right\rVert _{\mu^\star}} = \big\|D_{\mu^{\star}}^{1/2}\,A\,D_{\mu^{\star}}^{-1/2}\big\|_{2}.\) The last equality shows that the \(L_{2}(\mu^{\star})\)–operator norm is the spectral norm of the similarity transform \(D_{\mu^{\star}}^{1/2} A D_{\mu^{\star}}^{-1/2}\). For comparison, we recall the induced \(\ell_\infty\) operator norm for a matrix \(A \in \mathbb{R}^{S \times S}\): \(\left\lVert A\right\rVert _{\infty \to \infty} \triangleq \sup_{f \neq 0} \frac{\|Af\|_\infty}{\|f\|_\infty} = \max_{s \in \mathcal{S}} \sum_{s' \in \mathcal{S}} |A(s,s')|,\) which coincides with the maximum absolute row sum of \(A\). It is easy to check that \((\mu^\star_{\min})^{1/2}\; \left\lVert A\right\rVert _{\infty \to \infty} \le \left\lVert A\right\rVert _{\mu^\star\to\mu^\star} \le (\mu^\star_{\min})^{-1/2} \; \left\lVert A\right\rVert _{\infty \to \infty}.\) These inequalities follow from the vector–norm equivalences \((\mu^\star_{\min})^{1/2} \|f\|_{\infty} \le \left\lVert f\right\rVert _{\mu^\star} \le \|f\|_{\infty}\).

14.3 Weighted \(\ell_2\) norms for quantifying distributional convergence↩︎

A recurring theme in our analysis is to control how fast the empirical state distribution of a collection of arms approaches a target stationary distribution. To this end, we follow the weighted-\(\ell_2\) approach and introduce two matrices, \(W\) and \(U\), which is used in [14] and induce two weighted norms on \(\mathbb{R}^{S}\). Recall that \(\mu^\star\) is the stationary distribution of the Markov chain induced by \(\Bar{\pi}^\star\) under \(P\), and the matrix \(\Phi\) is defined in 14 .

Definition 1. Define \(W,U\in\mathbb{R}^{S\times S}\) by \(W \;\triangleq\; \sum_{k=0}^{\infty} (P^{\bar\pi^\star}-\mathbf{1}\mu^\star)^k\bigl((P^{\bar\pi^\star}-\mathbf{1}\mu^\star)^{\top}\bigr)^k \text{ and } U \;\triangleq\; \sum_{k=0}^{\infty} \Phi^k(\Phi^{\top})^k.\)

The matrices \(W\) and \(U\) satisfy the identities \(W \;=\; I + (P^{\bar\pi^\star}-\mathbf{1}\mu^\star)W(P^{\bar\pi^\star}-\mathbf{1}\mu^\star)^{\top}\) and \(U \;=\; I + \Phi\,U\,\Phi^{\top}.\) They induce the weighted \(\ell_2\) norms \(\|v\|_{W} \;\triangleq\; \sqrt{v^{\top}Wv}\) and \(\|v\|_{U} \;\triangleq\; \sqrt{v^{\top}Uv}\) for \(v\in\mathbb{R}^{S}.\) The local stability condition in Assumption 2 implies that all eigenvalues of \(\Phi\) are less than 1. Hence Lemma 4 from [14] guarantees that \(W\) and \(U\) are symmetric positive definite and the eigenvalues of \(W, U\) are in the range \([1,\lambda_W]\) and \([1,\lambda_U]\), respectively, where \(\lambda_W\) and \(\lambda_U\) are the largest eigenvalues of \(W\) and \(U\). In particular, for all \(v\in\mathbb{R}^{S}\), it holds that \(\|v\|_2 \;\le\; \|v\|_W \;\le\; \sqrt{\lambda_W}\,\|v\|_2\) and \(\|v\|_2 \;\le\; \|v\|_U \;\le\; \sqrt{\lambda_U}\,\|v\|_2,\) which will be repeatedly used to translate between Euclidean and weighted metrics.

14.4 Subset Lyapunov functions↩︎

We used the following two subset Lyapunov functions which are introduced in [14] as building blocks in our Lyapunov analysis. These two classes of functions quantify the convergence of state distributions for subsets of arms that follow the Unconstrained Optimal Control or the Optimal Local Control. For any system state \(\boldsymbol{x}\) and subset \(D\subseteq[N]\), let \(z(s)\) be the number of arms in \(D\) currently in state \(s\in\mathcal{S}\). Define the normalized state-count vector \(\boldsymbol{x}(D)\in\mathbb{R}^{S}\) by \(\boldsymbol{x}(D,s)=\frac{z(s)}{N}\), and \(m(D)=\sum_{s\in\mathcal{S}}\boldsymbol{x}(D,s)=\frac{|D|}{N}\). Then define \[\label{def:hu-hw} \begin{align} h_W(\boldsymbol{x},D)=\|\boldsymbol{x}(D)-m(D)\mu^\star\|_W, \qquad h_U(\boldsymbol{x},D)=\|\boldsymbol{x}(D)-m(D)\mu^\star\|_U. \end{align}\tag{47}\]

14.5 Feasibility-ensuring pair↩︎

Here we briefly introduce the feasibility-ensuring pair showed in [14]. Define the set of transient states as \(\mathcal{S}^{\emptyset}:=\{s\in\mathcal{S}:\; y^\star(s,0)=y^\star(s,1)=0\}.\)

A sufficient condition ensuring that the Optimal Local Control routine can always realize exactly \(B\) activations is \[\label{eq:integer-feasibility} \sum_{s\neq \tilde{s}}\bar\pi^\star(1\mid s)\,z(s)\le \alpha n-|\mathcal{S}^{\emptyset}|-1, \qquad \sum_{s\neq \tilde{s}}\bar\pi^\star(0\mid s)\,z(s)\le (1-\alpha)n-|\mathcal{S}^{\emptyset}|-1.\tag{48}\] Intuitively, 48 guarantees that after rounding decisions for states \(s\neq \tilde{s}\), the remaining budget is nonnegative and does not exceed the available number of arms in the neutral state, so \(\tilde{s}\) can “close the budget”.

For parameters \((\eta,\epsilon_N^{\mathrm{fe}})\), define the feasibility slack \(\delta(\boldsymbol{x},D):=\eta\,m(D)-\|\boldsymbol{x}(D)-m(D)\mu^\star\|_U-\epsilon_N^{\mathrm{fe}}.\)

Definition 2 (Feasibility-ensuring pair). A pair \((\eta,\epsilon_N^{\mathrm{fe}})\) is called feasibility-ensuring* if \[\delta(\boldsymbol{x},D)\ge 0 \quad\Longrightarrow\quad \text{D satisfies the integer feasibility condition \eqref{eq:integer-feasibility}.}\] Equivalently, whenever the subset-level state composition \(\boldsymbol{x}(D)\) is sufficiently close (in \(\|\cdot\|_U\)) to the target profile \(m(D)\mu^\star\) with margin \(\eta m(D)-\epsilon_N^{\mathrm{fe}}\), Subroutine 2 is guaranteed to be feasible on \(D\).*

In our case, \(\mathcal{S}^{\emptyset}=\emptyset\). We use the following convenient explicit choice \[\label{eq:explicit-fe-pair} \eta = S^{-1/2}\min\{y^\star(\tilde{s},0),\,y^\star(\tilde{s},1)\}, \qquad \epsilon_N^{\mathrm{fe}}= S^{-1/2}\frac{|\mathcal{S}^{\emptyset}|+1}{N}=S^{-1/2}\frac{1}{N}.\tag{49}\] Lemma 2 in [14] shows that this choice of \((\eta,\epsilon_N^{\mathrm{fe}})\) is a feasibility-ensuring pair.

14.6 Maximal Feasible Set↩︎

In our algorithm, at each time step we select a subset of arms on which a local control routine is executed. Rather than requiring an exact maximal feasible set, we work with an approximate notion of maximality, parameterized by a small tolerance \(\epsilon_N^{\mathrm{rd}}\ge 0\). This tolerance allows mild slack in the maximality requirement while still ensuring that the chosen set is nearly as large as any sufficiently feasible superset.

Definition 3 (\(\epsilon_N^{\mathrm{rd}}\)-maximal feasible set). Fix a system state \(\boldsymbol{x}\) and a tolerance parameter \(\epsilon_N^{\mathrm{rd}}\ge 0\). A set \(D\subseteq[N]\) is called \(\epsilon_N^{\mathrm{rd}}\)-maximal feasible at state \(\boldsymbol{x}\) if the following hold: 1. Feasibility: \(\delta(\boldsymbol{x},D)\ge 0\), or \(D=\emptyset\); 2. Approximate maximality: for any \(D'\) such that \(D\subseteq D'\subseteq[N]\) and \(\delta(\boldsymbol{x},D')\ge \epsilon_N^{\mathrm{rd}}\), we have \(m(D') \le m(D)+\epsilon_N^{\mathrm{rd}}.\)

When \(\epsilon_N^{\mathrm{rd}}=0\), Definition 3 reduces to the usual notion of a maximal element (under set inclusion) in the family \(\{D'\subseteq[N]:\delta(\boldsymbol{x},D')\ge 0\}\cup\{\emptyset\}\). In our theoretical development we typically take \(\epsilon_N^{\mathrm{rd}}=\Theta(1/N)\), matching the granularity of the mass \(m(D)\), since \(m(D)\) changes in increments of \(1/N\) when adding or removing a single arm.

14.7 Lyapunov functions↩︎

In this subsection we introduce the Lyapunov function we use. We constructed our Lyapunov function based on the Lyapunov function \(\tilde{V}\) introduced in [14]. For any system state \(\sigma=(\boldsymbol{x},d^{\mathrm{OL}},d^{\Bar{\pi}^\star})\), \[\label{eq:def-Vtilde} \tilde{V}(\sigma)=\tilde{V}(\boldsymbol{x},d^{\mathrm{OL}},d^{\Bar{\pi}^\star})=h_U(\boldsymbol{x},d^{\mathrm{OL}})+h_W(\boldsymbol{x},d^{\Bar{\pi}^\star})+L(1-m(d^{\mathrm{OL}})),\tag{50}\] where \(h_U, h_W\) are defined in 47 , \(L = 2\lambda_U^{1/2}+2\lambda_{W}^{1/2}-2\lambda_{W}^{1/2}\min(\alpha,1-\alpha)\). It is shown in [14] that \[\label{eq:def-Vtilde95max} \forall \sigma, 0\le \tilde{V}(\sigma)\le \tilde{V}_{\max}\triangleq\lambda_U^{1/2}+\lambda_{W}^{1/2}+L\tag{51}\] Define our Lyapunov function \(V\) as \[\label{equ:defi-V} V(\sigma)=V(\boldsymbol{x},d^{\mathrm{OL}},d^{\Bar{\pi}^\star})=(\tilde{V}-\frac{\bar\eta}{2})^++\frac{\gamma}{4(\beta+r_{\max})}(\mu^\star-\boldsymbol{x}([N]))Qb,\tag{52}\] where \[\label{eq:def-beta-Q-b-bareta-gamma} \begin{gather} \beta=\sup_\sigma\left|(\mu^\star-\boldsymbol{x}([N]))Qb-\mathbb{E}\left[(\mu^\star-\boldsymbol{X}_t([N]))Qb\mid \Sigma_t=\sigma\right]\right|, \quad Q=(I-\Phi)^{-1}, \\ b=\left(\sum_{a\in\mathcal{A}}(r(s,a)-r(\tilde{s},a))\Bar{\pi}^\star(a\mid s)\right)_{s\in\mathcal{S}}\in\mathbb{R}^S, \quad \bar\eta=\eta-\epsilon_N^{\mathrm{fe}}, \\ \gamma=\frac{\bar\eta}{K_{Vh}},K_{Vh}=2\max\{\lambda_W,\lambda_U\}\left(1+\frac{L\lambda_U^{1/2}}{\eta\omega}\right), \quad \omega=\min\{\alpha,1-\alpha\}. \end{gather}\tag{53}\] \(\Phi\) is defined in 14 and \(\eta,\epsilon_N^{\mathrm{fe}}\) are defined in 49 . It is obvious that \(\beta\) is a finite number since it is the maximum over a finite set. And notice that in order to make sure \(\bar\eta>0\), we need \(N>\frac{1}{\min\{y^\star(\tilde{s},0), y^\star(\tilde{s},1)\}}.\)

15 Proof details of the lemmas used in Theorem 2↩︎

15.1 Proof of Lemma 9↩︎

Proof. Proof We use the Lyapunov function \(V\) defined in 52 (see Appendix 14.7). The following two lemmas provide the backbone of the Lyapunov analysis, which are corresponding to [cond:drift] and [cond:dominance] in the Lyapunov framework respectively.

Lemma 31. When \(N\ge\left(\frac{4M}{\gamma}\right)^2\), the Lyapunov function \(V\) defined in 52 satisfies \[\mathbb{E}^{\pi_{\mathrm{TS}}}[V(\Sigma_{t+1})\mid \Sigma_t=\sigma]-V(\sigma)\le -\frac{\gamma}{4(\beta+r_{\max})}g(\sigma)+6\exp(8)S\tilde{V}_{\max}\exp\left(-CN\right),\] where \(\gamma,\beta\) are defined in 53 , \(\tilde{V}_{\max}\) is defined in 51 , and \[\label{def:g-sigma} g(\sigma)=r_{\max}\mathbb{I}[d^{\mathrm{OL}}\neq [N]] + (\mu^\star-\boldsymbol{x}([N]))b\cdot\mathbb{I}[d^{\mathrm{OL}}= [N]],\qquad{(8)}\] \[\label{def:g-C-M} \begin{align} M&=\frac{L}{2K_{Vh}\omega}\left(1+ \frac{2S^{-\frac{1}{2}}}{\eta}\right)+5\lambda_{U}^{1/2}S+3\lambda_{W}^{1/2}S +(\lambda_{W}^{1/2}+\lambda_{U}^{1/2})\exp\left(\frac{1}{2\lambda_U^3S^3}+32\right)\frac{16\lambda_U^{3/2}S^{2}}{\eta} +2\lambda_{W}^{1/2},\\ C&=\frac{\min\{\gamma^2/4,1\}}{4\max\{\lambda_W,\lambda_U\}S^2}. \end{align}\qquad{(9)}\]

Proof. Proof We have \[\begin{align} & \mathbb{E}^{\pi_{\mathrm{TS}}}[V(\Sigma_{t+1})\mid \Sigma_t=\sigma]-V(\sigma)\\ = & \mathbb{E}^{\pi_{\mathrm{TS}}}\left[\left(\tilde{V}(\Sigma_{t+1})-\frac{\bar\eta}{2}\right)^+\mid \Sigma_t = \sigma\right]-\left(\tilde{V}(\sigma)-\frac{\bar\eta}{2}\right)^+ \\ &+\frac{\gamma}{4(\beta+r_{\max})}\left(\mathbb{E}^{\pi_{\mathrm{TS}}}\left[(\mu^\star-\boldsymbol{X}_t([N]))Qb\mid \Sigma_t=\sigma\right]-(\mu^\star-\boldsymbol{x}([N]))Qb\right) \\ \le & -\frac{\gamma}{4}\mathbb{I}[d^{\mathrm{OL}}\neq [N]]+6\exp(8)S\tilde{V}_{\max}\exp\left(-CN\right) \\ &+\frac{\gamma}{4(\beta+r_{\max})}\left(\mathbb{E}^{\pi_{\mathrm{TS}}}\left[(\mu^\star-\boldsymbol{X}_t([N]))Qb\mid \Sigma_t=\sigma\right]-(\mu^\star-\boldsymbol{x}([N]))Qb\right) \\ = & -\frac{\gamma}{4}\mathbb{I}[d^{\mathrm{OL}}\neq [N]] +6\exp(8)S\tilde{V}_{\max}\exp\left(-CN\right) \\ & -\frac{\gamma}{4(\beta+r_{\max})}\left((\mu^\star-\boldsymbol{x}([N]))Qb-\mathbb{E}^{\pi_{\mathrm{TS}}}\left[(\mu^\star-\boldsymbol{X}_t([N]))Qb\mid \Sigma_t=\sigma\right]\right)\mathbb{I}[d^{\mathrm{OL}}\neq [N]] \\ & -\frac{\gamma}{4(\beta+r_{\max})}\left((\mu^\star-\boldsymbol{x}([N]))Qb-\mathbb{E}^{\pi_{\mathrm{TS}}}\left[(\mu^\star-\boldsymbol{X}_t([N]))Qb\mid \Sigma_t=\sigma\right]\right)\mathbb{I}[d^{\mathrm{OL}}=[N]] \\ \le & 6\exp(8)S\tilde{V}_{\max}\exp\left(-CN\right) -\frac{\gamma}{4(\beta+r_{\max})}\biggl(r_{\max}\mathbb{I}[d^{\mathrm{OL}}\neq[N]]\\ &\qquad +\left((\mu^\star-\boldsymbol{x}([N]))Qb -\mathbb{E}^{\pi_{\mathrm{TS}}}\left[(\mu^\star-\boldsymbol{X}_t([N]))Qb\mid \Sigma_t=\sigma\right]\right)\mathbb{I}[d^{\mathrm{OL}}=[N]]\biggr), \end{align}\] where the first inequality follows from Lemma 40 and the second inequality from the definition of \(\beta\) in 53 . Note that \(Q=(I-\Phi)^{-1}\), thus \(\mu^\star-\boldsymbol{x}([N])=(\mu^\star-\boldsymbol{x}([N]))Q-(\mu^\star-\boldsymbol{x}([N]))\Phi Q.\) Hence, \[\begin{align} &\left((\mu^\star-\boldsymbol{x}([N]))Qb\cdot-\mathbb{E}^{\pi_{\mathrm{TS}}}[(\mu^\star-\boldsymbol{X}_t([N]))Qb\mid \Sigma_t=\sigma]\right)\cdot\mathbb{I}[d^{\mathrm{OL}}= [N]] \\ =& (\mu^\star-\boldsymbol{x}([N]))Qb\cdot\mathbb{I}[d^{\mathrm{OL}}= [N]]-(\mu^\star-\boldsymbol{x}([N]))\Phi Q b\cdot\mathbb{I}[d^{\mathrm{OL}}= [N]] \\ =& (\mu^\star-\boldsymbol{x}([N]))b\cdot\mathbb{I}[d^{\mathrm{OL}}= [N]], \end{align}\] where the first equality follows from Lemma 46. Therefore, we have the desired bound \(\mathbb{E}^{\pi_{\mathrm{TS}}}[V(\Sigma_{t+1})\mid \Sigma_t=\sigma]-V(\sigma) \le -\frac{\gamma}{4(\beta+r_{\max})}g(\sigma)+6\exp(8)S\tilde{V}_{\max}\exp\left(-CN\right).\) ◻

Lemma 32. Consider a \(N\)-armed RB problem. For each \(\sigma=(\boldsymbol{x},d^{\mathrm{OL}},d^{\Bar{\pi}^\star})\), define \(r^{\pi_{\mathrm{TS}}}(\sigma)=\mathbb{E}_{A\sim \pi_{\mathrm{TS}}(\cdot\mid\sigma)}[r(\sigma,A)].\) Then \(\rho^{\mathrm{rel}}-r^{\pi_{\mathrm{TS}}}(\sigma)\le g(\sigma),\) where \(g(\sigma)\) is defined in ?? .

Proof. Proof. Consider the affine function introduced in [14]: \[\begin{align} \bar r^{\pi_{\mathrm{TS}}}(\boldsymbol{x})=r^{\pi_{\mathrm{TS}}}(\boldsymbol{x},[N],\emptyset) & = \sum_{a\in\mathcal{A}}(r(\cdot,a)-r(\tilde{s},a))\Bar{\pi}^\star(a\mid \cdot)\cdot \boldsymbol{x}([N])+\alpha r(\tilde{s},1)+(1-\alpha)r(\tilde{s},0)\\ &=\boldsymbol{x}([N])\cdot b+\alpha r(\tilde{s},1)+(1-\alpha)r(\tilde{s},0). \end{align}\] Notice that \(\rho^{\mathrm{rel}}=\bar r^{\pi_{\mathrm{TS}}}(\mu^\star)\), hence \[\begin{align} \rho^{\mathrm{rel}}-r^{\pi}(\sigma) & =\bar r^{\pi_{\mathrm{TS}}}(\mu^\star)-r^{\pi_{\mathrm{TS}}}(\sigma) \\ & =(\bar r^{\pi_{\mathrm{TS}}}(\mu^\star)-r^{\pi_{\mathrm{TS}}}(\sigma))\mathbb{I}\big[d^{\mathrm{OL}}\ne [N]\big] + (\bar r^{\pi_{\mathrm{TS}}}(\mu^\star)-r^{\pi_{\mathrm{TS}}}(\sigma))\mathbb{I}\big[d^{\mathrm{OL}}= [N]\big] \\ & = (\bar r^{\pi_{\mathrm{TS}}}(\mu^\star)-r^{\pi_{\mathrm{TS}}}(\sigma))\mathbb{I}\big[d^{\mathrm{OL}}\ne [N]\big] + (\bar r^{\pi_{\mathrm{TS}}}(\mu^\star)-\bar r^{\pi_{\mathrm{TS}}}(\boldsymbol{x}))\mathbb{I}\big[d^{\mathrm{OL}}= [N]\big] \\ & \le r_{\max}\cdot \mathbb{I}\big[d^{\mathrm{OL}}\ne [N]\big]+ (\mu^\star-\boldsymbol{x}([N]))b\cdot\mathbb{I}\big[d^{\mathrm{OL}}= [N]\big] \;=\; g(\sigma). \end{align}\] ◻

Lemma 36 guarantees that \(\bar\eta\) and \(\gamma\) are well-defined. We now apply Lemma 7 with source kernel \(Q=\boldsymbol{P}^{\pi_{\mathrm{TS}}}\) and target kernel \(P=\widehat{\boldsymbol{P}}^{\pi_{\mathrm{TS}}}\), benchmark \(R=\rho^{\mathrm{rel}}\), function \(F=g\), one-period reward \(\bar r=r^{\pi_{\mathrm{TS}}}\), and \(a=\frac{\gamma}{4(\beta+r_{\max})}, b=6\exp(8)S\tilde{V}_{\max}\exp(-CN), c=1, d=0.\) Lemmas 31 and 32 provide the required drift and dominance inequalities. Therefore, \[\rho^{\mathrm{rel}}-\widehat\rho^{\pi_{\mathrm{TS}}}(\boldsymbol{s}_0) \le \frac{4(\beta+r_{\max})}{\gamma}\sup_\sigma |(\widehat{\boldsymbol{P}}^{\pi_{\mathrm{TS}}}-\boldsymbol{P}^{\pi_{\mathrm{TS}}})V(\sigma)| +\frac{4(\beta+r_{\max})}{\gamma}\,6\exp(8)S\tilde{V}_{\max}\exp(-CN).\] By Lemma 44, the model-error term is at most \(V_{\max}N\delta\), where \(V_{\max}\) is defined in Lemma 41. Hence \[\rho^{\mathrm{rel}}-\widehat\rho^{\pi_{\mathrm{TS}}}(\boldsymbol{s}_0) \le \frac{4V_{\max}(\beta+r_{\max})}{\gamma}N\delta +\frac{4(\beta+r_{\max})}{\gamma}\,6\exp(8)S\tilde{V}_{\max}\exp(-CN).\] Defining \(C_6=4V_{\max}(\beta+r_{\max})/\gamma\) completes the proof. ◻

15.2 Proof of Lemma 10↩︎

Lemma 10 bounds \(\widehat{\rho}^{\mathrm{rel}}-\rho^{\widehat{\pi}_{\mathrm{TS}}}(\boldsymbol{s}_0)\), which is the second component in the decomposition 18 . As a result, the analysis in this part is carried out under the empirical model. To streamline the discussion, we first introduce the key objects and notation for the empirical system in Appendix 15.2.1; their well-definedness and basic properties are established in Appendix 15.2.2.

15.2.1 Definitions↩︎

As in the proof of Lemma 4, to apply our Lyapunov framework we first need to ensure that the Markov chain induced by the policy \(\widehat{\Bar{\pi}}^\star\) under the empirical kernel \(\widehat{P}\) remains ergodic, which is showed in Theorem 3.

15.2.1.1 Weighted \(\ell_2\) norms

Similarly to Definition 1, we define following for the empirical system:

Definition 4. Define \(\widehat W,\widehat U\in\mathbb{R}^{S\times S}\) by \(\widehat W \;\triangleq\; \sum_{k=0}^{\infty} (\widehat P_{\widehat{\Bar{\pi}}^\star}-\mathbf{1}\widehat{\mu}^\star)^k\bigl((\widehat P_{\widehat{\Bar{\pi}}^\star}-\mathbf{1}\widehat{\mu}^\star)^{\top}\bigr)^k,\) and \(\widehat U \;\triangleq\; \sum_{k=0}^{\infty} \widehat \Phi^k(\widehat{\Phi}^{\top})^k.\)

15.2.1.2 Subset Lyapunov functions

For the empirical system, we can naturally define \[\label{def:huh-hwh} \begin{align} h_{\widehat W}(\boldsymbol{x},D) =\|\boldsymbol{x}(D)-m(D)\widehat{\mu}^\star\|_{\widehat{W}}, \qquad h_{\widehat{U}}(\boldsymbol{x},D) =\|\boldsymbol{x}(D)-m(D)\widehat{\mu}^\star\|_{\widehat{U}} \end{align}\qquad{(10)}\] Furthermore, denote \(\lambda_{\widehat{W}}\) and \(\lambda_{\widehat{U}}\) as the largest eigenvalues of \(\widehat W, \widehat{U}\).

15.2.1.3 Feasibility-ensuring pair

Under the condition of Theorem 3 and according to the construction of the empirical primal optimal solution, we know \(\{s\in\mathcal{S}:\; y^\star(s,0)=y^\star(s,1)=0\}=\{s\in\mathcal{S}:\widehat y^\star(s,0)=\widehat y^\star(s,1)=0\}.\) So in terms of the empirical model, we can choose the feasibility-ensuring pair \((\widehat\eta,\widehat\epsilon_N^{\mathrm{fe}})\) as: \(\widehat\eta = S^{-1/2}\min\{\widehat y^\star(\tilde{s},0),\widehat y^\star(\tilde{s},1)\}\) and \(\widehat \epsilon_N^{\mathrm{fe}}=\epsilon_N^{\mathrm{fe}}= S^{-1/2}\frac{|\mathcal{S}^{\emptyset}|+1}{N}=S^{-1/2}\frac{1}{N}.\)

15.2.1.4 Lyapunov functions

In terms of the empirical model, we can define the matrix \(\widehat{\Phi}\) as \(\widehat{\Phi}\triangleq \widehat{P}_{\widehat{\Bar{\pi}}^\star}-\mathbf{1}^{\top}\widehat{\mu}^\star -\bigl(c_{\widehat{\Bar{\pi}}^\star}-\alpha\mathbf{1}\bigr)^{\top}\bigl(\widehat{P}_1(\tilde{s})-\widehat{P}_0(\tilde{s})\bigr).\) In the same way, for any system state \(\sigma=(\boldsymbol{x},d^{\mathrm{OL}},d^{\Bar{\pi}^\star})\), we make use of the following empirical version of the Lyapunov function introduced in [14]: \[\widehat{\tilde{V}}(\sigma)=\widehat{\tilde{V}}(\boldsymbol{x},d^{\mathrm{OL}},d^{\Bar{\pi}^\star})=h_{\widehat{U}}(\boldsymbol{x},d^{\mathrm{OL}})+h_{\widehat{W}}(\boldsymbol{x},d^{\Bar{\pi}^\star})+\widehat L(1-m(d^{\mathrm{OL}})),\] where \(h_{\widehat{U}}, h_{\widehat W}\) are defined in ?? , \(\widehat L = 2\lambda_{\widehat{U}}^{1/2}+2\lambda_{\widehat{W}}^{1/2}-2\lambda_{\widehat{W}}^{1/2}\min(\alpha,1-\alpha)\le2\lambda_{\widehat{U}}^{1/2}+2\lambda_{\widehat{W}}^{1/2}\). Now we can define the empirical Lyapunov function \(\widehat{V}\) as: \[\label{equ:defi-Vhat} \widehat{V}(\sigma)=\widehat{V}(\boldsymbol{x},d^{\mathrm{OL}},d^{\Bar{\pi}^\star})=\left(\widehat {\tilde{V}}(\sigma)-\frac{\bar\eta}{2}\right)^++\frac{\widehat\gamma}{4(\widehat \beta+r_{\max})}(\widehat{\mu}^\star-\boldsymbol{x}([N]))\widehat{Q}\widehat b\tag{54}\] where \[\label{eq:def-hat-beta-Q-b-bareta-gamma} \begin{gather} \widehat \beta=\sup_\sigma\left|(\widehat{\mu}^\star-\boldsymbol{x}([N]))\widehat{Q}\widehat b-\mathbb{E}\left[(\widehat{\mu}^\star-\boldsymbol{X}_t([N]))\widehat{Q}\widehat b\mid \Sigma_t=\sigma\right]\right|, \widehat{Q}=(I-\widehat{\Phi})^{-1},\\ \widehat b=\left(\sum_{a\in\mathcal{A}}(r(s,a)-r(\tilde{s},a))\widehat{\Bar{\pi}}^\star(a\mid s)\right)_{s\in\mathcal{S}}, \quad \widehat{\bar\eta}=\widehat \eta-\epsilon_N^{\mathrm{fe}},\\ \widehat\gamma=\frac{\widehat{\bar\eta}}{\widehat K_{Vh}}, \quad \widehat K_{Vh}=2\max\{\lambda_{\widehat{W}},\lambda_{\widehat{U}}\}\left(1+\frac{\widehat L\lambda_{\widehat{U}}^{1/2}}{\widehat\eta\omega}\right), \quad \omega=\min\{\alpha,1-\alpha\}. \end{gather}\tag{55}\]

15.2.2 Well-definedness and properties↩︎

Lemma 33 guarantees that \(\widehat W, \widehat{U}\) are well-defined and their eigenvalues are in the range of \([1,\lambda_{\widehat{W}}]\) and \([1,\lambda_{\widehat{U}}]\).

Lemma 33. Under the conditions in Lemma 10, the matrices \(\widehat W, \widehat{U}\) given in Definition 4 are well-defined. Moreover, their eigenvalues are lower bounded by \(1\).

Proof. Proof We first establish the well-definedness of \(\widehat{W}\) and lower bound its eigenvalues, following the same argument as Lemma 4 of [14]. The key is that by Theorem 3, all eigenvalues of \(\widehat{P}_{\widehat{\Bar{\pi}}^\star}-\mathbf{1}\widehat{\mu}^\star\) have modulus strictly smaller than \(1\), and the same property also holds for \(\widehat{\Phi}\). Therefore, the proof for \(\widehat{U}\) proceeds analogously, with \(\widehat{P}_{\widehat{\Bar{\pi}}^\star}-\mathbf{1}\widehat{\mu}^\star\) replaced by \(\widehat{U}\). ◻

Under appropriate conditions, the following two lemmas provide upper bounds, denoted as \(\lambda^{\mathrm{ub}}_{\widehat{W}}\) and \(\lambda^{\mathrm{ub}}_{\widehat{U}}\), for \(\lambda_{\widehat{W}}\) and \(\lambda_{\widehat{U}}\).

Lemma 34. Under the conditions in Lemma 10, \(\widehat{W}\) satisfies \[\label{def:ublwhat} \lambda_{\widehat{W}}\leq \lambda^{\mathrm{ub}}_{\widehat{W}}\triangleq 4S(3+\log_2S)\tau,\qquad{(11)}\] where \(\tau\) is the mixing time of the single-armed MDP under the optimal single-armed policy \(\bar\pi^\star\).

Proof. Proof Note that \(\widehat{W} = I + \sum_{t=1}^\infty (\widehat{P}^{\widehat{\Bar{\pi}}^\star,t} - \mathbf{1}\widehat{\mu}^\star) (\widehat{P}^{\widehat{\Bar{\pi}}^\star,t} - \mathbf{1}\widehat{\mu}^\star)^\top\) since \((\widehat{P}_{\widehat{\Bar{\pi}}^\star} - \mathbf{1}\widehat{\mu}^\star)^t = \widehat{P}^{\widehat{\Bar{\pi}}^\star,t} - \mathbf{1}\widehat{\mu}^\star\) if \(t \geq 1\), and otherwise if \(t = 0\) then \((\widehat{P}_{\widehat{\Bar{\pi}}^\star} - \mathbf{1}\widehat{\mu}^\star)^t = I\). Therefore for any \(v\) such that \(\left\lVert v\right\rVert _{2} = 1\), we have \[\begin{align} v^\top \widehat{W} v &= 1 + \sum_{t=1}^\infty v^\top(\widehat{P}^{\widehat{\Bar{\pi}}^\star,t} - \mathbf{1}\widehat{\mu}^\star) (\widehat{P}^{\widehat{\Bar{\pi}}^\star,t} - \mathbf{1}\widehat{\mu}^\star)^\top v \leq 1 + \sum_{t=1}^\infty \left\lVert (\widehat{P}^{\widehat{\Bar{\pi}}^\star,t} - \mathbf{1}\widehat{\mu}^\star)^\top v\right\rVert _{2}^2. \label{eq:W95eval95bd951} \end{align}\tag{56}\] Next we can bound \[\begin{align} \left\lVert (\widehat{P}^{\widehat{\Bar{\pi}}^\star,t} - \mathbf{1}\widehat{\mu}^\star)^\top v\right\rVert _{2} &= \sup_{w:\left\lVert w\right\rVert _{2}\leq 1} v^\top (\widehat{P}^{\widehat{\Bar{\pi}}^\star,t} - \mathbf{1}\widehat{\mu}^\star) w \\ & \leq \left\lVert v^\top\right\rVert _{\infty \to \infty} \left\lVert \widehat{P}^{\widehat{\Bar{\pi}}^\star,t} - \mathbf{1}\widehat{\mu}^\star\right\rVert _{\infty \to \infty} \left\Vert w\right\Vert _{\infty} \leq \sqrt{S} \left\lVert \widehat{P}^{\widehat{\Bar{\pi}}^\star,t} - \mathbf{1}\widehat{\mu}^\star\right\rVert _{\infty \to \infty}, \end{align}\] where we used that \(\left\Vert w\right\Vert _{\infty} \leq \left\lVert w\right\rVert _{2}\leq 1\) and that \(\left\lVert v^\top\right\rVert _{\infty \to \infty} = \left\Vert v\right\Vert _{1} \leq \sqrt{S} \left\lVert v\right\rVert _{2}\). Plugging this back into 56 and according to Lemma 21 we have \(\left\lVert \widehat{P}^{\widehat{\Bar{\pi}}^\star,t} - \mathbf{1}\widehat{\mu}^\star\right\rVert _{\infty \to \infty} \leq 2^{-\lfloor t/(3+\log_2S)\tau\rfloor}.\) Hence, \(v^\top \widehat{W} v \leq 1 + \sum_{t=1}^\infty S 2^{-2\lfloor t/(3+\log_2S)\tau\rfloor} \le 4S(3+\log_2S)\tau.\) Thus \(\lambda_{\widehat{W}}\leq 4S(3+\log_2S)\tau\). ◻

Lemma 35. Under the conditions in Lemma 10, \(\lambda_{\widehat U}\) satisfies \[\label{def:ubluhat} \lambda_{\widehat U}\le \lambda^{\mathrm{ub}}_{\widehat{U}}\triangleq\frac{1}{\mu^\star_{\min}}\frac{2}{1-\left\lVert \Phi\right\rVert _{\mu^\star\to\mu^\star}}.\qquad{(12)}\]

Proof. Proof Let \(v\) be an arbitrary vector satisfying \(\left\lVert v\right\rVert _{2} \leq 1\). Then we have \[\begin{align} v^\top \widehat{U}v &= v^\top \left(\sum_t D_{\mu^\star}^{-1/2} (D_{\mu^\star}^{1/2} \widehat{\Phi}D_{\mu^\star}^{-1/2} )^t D_{\mu^\star}^{1/2} D_{\mu^\star}^{1/2} ( D_{\mu^\star}^{-1/2} \widehat{\Phi}^\top D_{\mu^\star}^{1/2})^t D_{\mu^\star}^{-1/2} \right) v \\ &= \sum_t (D_{\mu^\star}^{-1/2}v)^\top (D_{\mu^\star}^{1/2} \widehat{\Phi}D_{\mu^\star}^{-1/2} )^t D_{\mu^\star} ( D_{\mu^\star}^{-1/2} \widehat{\Phi}^\top D_{\mu^\star}^{1/2})^t (D_{\mu^\star}^{-1/2}v) \\ & = \sum_t \left\lVert ( D_{\mu^\star}^{-1/2} \widehat{\Phi}^\top D_{\mu^\star}^{1/2})^t (D_{\mu^\star}^{-1/2}v)\right\rVert _{\mu^\star\to\mu^\star}^2\\ & \leq \left(\max_s \mu(s)\right)\sum_t \left\lVert ( D_{\mu^\star}^{-1/2} \widehat{\Phi}^\top D_{\mu^\star}^{1/2})^t (D_{\mu^\star}^{-1/2}v)\right\rVert_{2}^2\\ & \leq \sum_t \left\lVert ( D_{\mu^\star}^{-1/2} \widehat{\Phi}^\top D_{\mu^\star}^{1/2})\right\rVert_{2 \to 2}^{2t} \left\lVert D_{\mu^\star}^{-1/2}v\right\rVert_{2}^2\\ & =\sum_t \left\lVert \widehat{\Phi}\right\rVert _{\mu^\star\to\mu^\star}^{2t} v^\top D_{\mu^\star}^{-1} v\\ & \leq \sum_t \left\lVert \widehat{\Phi}\right\rVert _{\mu^\star\to\mu^\star}^{2t} \frac{1}{\mu^\star_{\min}} \left\lVert v\right\rVert _{2}^2 \le \frac{1}{\mu^\star_{\min}(1-\left\lVert \widehat{\Phi}\right\rVert _{\mu^\star\to\mu^\star})}. \end{align}\] Hence, according to Theorem 3, given \(\delta\le\delta_{\min}\), we have the desired bound \(\lambda_{\widehat U}\le \frac{1}{\mu^\star_{\min}}\frac{1}{1-\left\lVert \widehat{\Phi}\right\rVert _{\mu^\star\to\mu^\star}}\le\frac{1}{\mu^\star_{\min}}\frac{2}{1-\left\lVert \Phi\right\rVert _{\mu^\star\to\mu^\star}}.\) ◻

The well-definedness of \(\widehat{\bar\eta}=\widehat \eta-\epsilon_N^{\mathrm{fe}}\) requires it to be positive, which is guaranteed by the following lemma. In fact, the lemma provides a strictly positive lower bound for \(\widehat{\bar\eta}\) under certain conditions.

Lemma 36. When \(N\ge\frac{4}{\min\{y^\star(\tilde{s},0),y^\star(\tilde{s},1)\}}\), we have \(\bar\eta\ge\frac{3}{4}S^{-1/2}\min\{y^\star(\tilde{s},0),y^\star(\tilde{s},1)\}>0.\) When \(N\ge\frac{4}{\min\{y^\star(\tilde{s},0),y^\star(\tilde{s},1)\}}, \delta\le\delta_{\min}\), we have \(\widehat{\bar\eta}\ge\frac{1}{4}S^{-1/2}\min\{y^\star(\tilde{s},0),y^\star(\tilde{s},1)\}>0.\)

Proof. Proof By definition, when \(N\ge\frac{4}{\min\{y^\star(\tilde{s},0),y^\star(\tilde{s},1)\}}\), \[\begin{align} \bar\eta=\eta-\epsilon_N^{\mathrm{fe}}& =S^{-1/2}\min\{y^\star(\tilde{s},0),y^\star(\tilde{s},1)\}-S^{-1/2}\frac{1}{N} \\ & \ge S^{-1/2}\min\{y^\star(\tilde{s},0),y^\star(\tilde{s},1)\}-\frac{1}{4}S^{-1/2}\min\{y^\star(\tilde{s},0),y^\star(\tilde{s},1)\}\\ & = \frac{3}{4}S^{-1/2}\min\{y^\star(\tilde{s},0),y^\star(\tilde{s},1)\}>0. \end{align}\] When \(N\ge\frac{4}{\min\{y^\star(\tilde{s},0),y^\star(\tilde{s},1)\}}, \delta\le\delta_{\min}\), Lemma [lem:yhat95pert95and95feasibility] ensures that \(|\widehat{y}^\star(\tilde{s},0)-y^\star(\tilde{s},0)|\le \frac{1}{2}y^\star(\tilde{s},0)\) and \(|\widehat{y}^\star(\tilde{s},1)-y^\star(\tilde{s},1)|\le \frac{1}{2}y^\star(\tilde{s},1).\) Hence, \[\begin{align} \widehat{\bar\eta}=\widehat \eta-\epsilon_N^{\mathrm{fe}}& =S^{-1/2}\min\{\widehat{y}^\star(\tilde{s},0),\widehat{y}^\star(\tilde{s},1)\}-S^{-1/2}\frac{1}{N} \\ & \ge \frac{1}{2}S^{-1/2}\min\{y^\star(\tilde{s},0),y^\star(\tilde{s},1)\}-\frac{1}{4}S^{-1/2}\min\{y^\star(\tilde{s},0),y^\star(\tilde{s},1)\}\\ & = \frac{1}{4}S^{-1/2}\min\{y^\star(\tilde{s},0),y^\star(\tilde{s},1)\}>0. \end{align}\] ◻

The following lemma offers a strictly positive upper and lower bound for \(\widehat \gamma\), which guarantees the well-definedness of \(\widehat \gamma\).

Lemma 37. We have \(\widehat{\gamma}\le\widehat{\gamma}^{\mathrm{up}}\) when \(\delta\le\delta_{\min}\), and \(0<\widehat{\gamma}^{\mathrm{low}}\le\widehat{\gamma}\le\widehat{\gamma}^{\mathrm{up}}\) when \(\delta\le\delta_{\min}\) and \(N\ge \frac{4}{\min\{y^\star(\tilde{s},0),y^\star(\tilde{s},1)\}}\), where \[\label{eq:def-lbg-upg-ubKvh} \begin{align} \widehat{\gamma}^{\mathrm{low}}&\triangleq \frac{S^{-1/2}\min\{y^\star(\tilde{s},0),y^\star(\tilde{s},1)\}}{4\widehat{K}_{Vh}^{\mathrm{up}}}, \qquad \widehat{\gamma}^{\mathrm{up}}\triangleq \frac{3}{4}S^{-1/2}\min\{y^\star(\tilde{s},0),y^\star(\tilde{s},1)\},\\ \widehat{K}_{Vh}^{\mathrm{up}}&\triangleq 2\max\{\lambda^{\mathrm{ub}}_{\widehat{W}},\lambda^{\mathrm{ub}}_{\widehat{U}}\}\left(1+\frac{4(\lambda^{\mathrm{ub}}_{\widehat{W}}+\lambda^{\mathrm{ub}}_{\widehat{U}})\lambda^{\mathrm{ub}}_{\widehat{U}}}{S^{-1/2}\min\{y^\star(\tilde{s},0),y^\star(\tilde{s},1)\}\omega}\right), \end{align}\qquad{(13)}\] and \(\lambda^{\mathrm{ub}}_{\widehat{W}},\lambda^{\mathrm{ub}}_{\widehat{U}}\) are defined in ?? and ?? .

Proof. Proof According to Theorem 3, when \(\delta\le\delta_{\min}\), we have \[\frac{3}{2}S^{-1/2}\min\{y^\star(\tilde{s},0),y^\star(\tilde{s},1)\}\ge\widehat \eta=S^{-1/2}\min\{\widehat{y}^\star(\tilde{s},0),\widehat{y}^\star(\tilde{s},1)\ge\frac{1}{2}S^{-1/2}\min\{y^\star(\tilde{s},0),y^\star(\tilde{s},1)\}\] It is easy to check that when \(N\ge \frac{4}{\min\{y^\star(\tilde{s},0),y^\star(\tilde{s},1)\}}\), it holds that \[\begin{align} \widehat{\bar{\eta}}=\widehat \eta-\epsilon_N^{\mathrm{fe}}&=S^{-1/2}\min\{\widehat{y}^\star(\tilde{s},0),\widehat{y}^\star(\tilde{s},1)\}-S^{-1/2}\frac{1}{N}\\ & \ge \frac{1}{2}S^{-1/2}\min\{y^\star(\tilde{s},0),y^\star(\tilde{s},1)\}-S^{-1/2}\frac{1}{N} \ge \frac{1}{4}S^{-1/2}\min\{y^\star(\tilde{s},0),y^\star(\tilde{s},1)\}. \end{align}\] Also, we have \[\begin{align} \widehat K_{Vh}&=2\max\{\lambda_{\widehat{W}},\lambda_{\widehat{U}}\}\left(1+\frac{\widehat L\lambda_{\widehat{U}}^{1/2}}{\widehat\eta\omega}\right) \le 2\max\{\lambda^{\mathrm{ub}}_{\widehat{W}},\lambda^{\mathrm{ub}}_{\widehat{U}}\}\left(1+\frac{4(\lambda^{\mathrm{ub}}_{\widehat{W}}+\lambda^{\mathrm{ub}}_{\widehat{U}})\lambda^{\mathrm{ub}}_{\widehat{U}}}{S^{-1/2}\min\{y^\star(\tilde{s},0),y^\star(\tilde{s},1)\}\omega}\right)\triangleq \widehat{K}_{Vh}^{\mathrm{up}}, \end{align}\] where \(\lambda^{\mathrm{ub}}_{\widehat{W}},\lambda^{\mathrm{ub}}_{\widehat{U}}\) are defined in ?? and ?? , which are depend on the parameters of the original system. Hence, \(\widehat \gamma=\frac{\widehat{\bar{\eta}}}{\widehat{K}_{Vh}}\ge \frac{\frac{1}{4}S^{-1/2}\min\{y^\star(\tilde{s},0),y^\star(\tilde{s},1)\}}{\widehat{K}_{Vh}^{\mathrm{up}}}.\) It is clear that \(\widehat K_{Vh}\ge 2\), so when \(\delta\le\delta_{\min}\), we have \(\widehat \gamma=\frac{\widehat{\bar{\eta}}}{\widehat{K}_{Vh}}\le\frac{3}{4}S^{-1/2}\min\{y^\star(\tilde{s},0),y^\star(\tilde{s},1)\}.\) ◻

The following lemma gives an upper bound of \(\widehat\beta\), which guarantees \(\widehat\beta\) will not go to infinity.

Lemma 38. Under the conditions in Lemma 10, \(\widehat \beta\) satisfies \(\widehat{\beta}\le \widehat{\beta}_{\max}\triangleq \frac{8r_{\max}}{\sqrt{\mu^\star_{\min}}}\frac{1}{1-\left\lVert \Phi\right\rVert _{\mu^\star\to\mu^\star}}.\)

Proof. Proof According to Theorem 3, we know \(\left\lVert \widehat{\Phi}\right\rVert _{\mu^\star\to\mu^\star}<1\). Hence, \(\widehat Q = (I-\widehat{\Phi})^{-1}=\sum_{t=0}^\infty\widehat{\Phi}^t,\) which implies that \(\left\lVert \widehat Q\right\rVert _{\mu^\star\to\mu^\star}\le \sum_{t=0}^\infty\left\lVert \widehat{\Phi}\right\rVert _{\mu^\star\to\mu^\star}\le\frac{1}{1-\left\lVert \widehat{\Phi}\right\rVert _{\mu^\star\to\mu^\star}}.\) It follows that \[\begin{align} \widehat \beta&\le \sup_x 2\left\Vert \widehat{\mu}^\star-\boldsymbol{x}([N])\right\Vert _{1}\left\lVert \widehat Q\right\rVert _{\infty \to \infty}\left\Vert \widehat b\right\Vert _{\infty}\\ & \le 2\cdot 2\frac{\left\lVert \widehat Q\right\rVert _{\mu^\star\to\mu^\star}}{\sqrt{\mu^\star_{\min}}}r_{\max} ^\star-\boldsymbol{x}([N])\right\Vert _{1}\le 2, \left\Vert \widehat{b}\right\Vert _{\infty}\le r_{\max}} \\ &\le \frac{4r_{\max}}{\sqrt{\mu^\star_{\min}}}\frac{1}{1-\left\lVert \widehat{\Phi}\right\rVert _{\mu^\star\to\mu^\star}} \le \frac{8r_{\max}}{\sqrt{\mu^\star_{\min}}}\frac{1}{1-\left\lVert \Phi\right\rVert _{\mu^\star\to\mu^\star}}. \end{align}\] where the last inequality follows from Theorem 3. ◻

In terms of the properties of the Lyapunov function we use, Lemma 34 and Lemma 35 guarantee that under a sufficiently small single-arm estimation error, \[\label{def:hat-tilde-V-max} \forall \sigma, 0\le \widehat{\tilde{V}}(\sigma)\le \lambda_{\widehat U}^{1/2}+\lambda_{\widehat{W}}^{1/2}+\widehat L\le3\lambda_{\widehat U}^{1/2}+3\lambda_{\widehat{W}}^{1/2}\le3\sqrt{\lambda^{\mathrm{ub}}_{\widehat{U}}}+3\sqrt{\lambda^{\mathrm{ub}}_{\widehat{W}}}\triangleq \widehat{\tilde{V}}_{\max},\tag{57}\] where \(\lambda^{\mathrm{ub}}_{\widehat{U}}\) is defined in ?? and \(\lambda^{\mathrm{ub}}_{\widehat{W}}\) is defined in ?? . Notice that a sufficient condition to make sure \(\widehat Q\) is well-defined is \(\left\lVert \widehat{\Phi}\right\rVert _{\mu^\star\to\mu^\star}<1\), which holds under the condition of Theorem 3.

15.2.3 Final proof of Lemma 10↩︎

Proof. Proof We work with the empirical Lyapunov function \(\widehat{V}\) defined in 54 (see Appendix 14.7). The next two lemmas play the roles of the drift bound and the gap-dominance bound in our Lyapunov framework (Conditions [cond:drift] and [cond:dominance]), both stated for the empirical system under the policy \(\widehat{\pi}_{\mathrm{TS}}\). Their proofs follow the same steps as those for Lemma 31 and Lemma 32 after replacing all quantities by their hatted versions, so we omit the details.

lemmadriftconditionhat Suppose the conditions of Lemma 10 hold. When \(N\ge\left(\frac{4\widehat M}{\widehat \gamma}\right)^2\), the Lyapunov function defined in 54 satisfies \[\widehat \mathbb{E}^{\widehat{\pi}_{\mathrm{TS}}}[\widehat{V}(\Sigma_{t+1})\mid \Sigma_t=\sigma]-\widehat{V}(\sigma)\le -\frac{\widehat\gamma}{4(\widehat\beta+r_{\max})} \widehat g(\sigma)+6\exp(8)S\widehat{\tilde{V}}_{\max}\exp\left(-\widehat C N\right),\] where \(\widehat\gamma, \widehat\beta\) are defined in 55 , \(\widehat{\tilde{V}}_{\max}\) is defined in 57 , and \[\label{def:hat-g-gamma-C-K-M} \begin{align} \widehat g(\sigma) &=r_{\max}\mathbb{I}[d^{\mathrm{OL}}\neq [N]] +(\widehat{\mu}^\star-\boldsymbol{x}([N]))\widehat b\cdot\mathbb{I}[d^{\mathrm{OL}}= [N]], \qquad \widehat C =\frac{\min\{\widehat \gamma^2/4,1\}}{4\max\{\lambda_{\widehat{W}},\lambda_{\widehat{U}}\}S^2}.\\ \widehat M & =\frac{\widehat L}{2\widehat K_{Vh}\omega}\left(1+ \frac{2S^{-\frac{1}{2}}}{\widehat \eta}\right)+5\lambda_{\widehat{U}}^{1/2}S+3\lambda_{\widehat{W}}^{1/2}S +(\lambda_{\widehat{W}}^{1/2}+\lambda_{\widehat{U}}^{1/2})\exp\left(\frac{1}{2\lambda_{\widehat{U}}^3S^3}+32\right)\frac{16\lambda_{\widehat{U}}^{3/2}S^{2}}{\widehat \eta} +2\lambda_{\widehat{W}}^{1/2}. \end{align}\tag{58}\]

Lemma 39. Suppose the conditions of Lemma 10 hold. \(\forall \sigma=(\boldsymbol{x},d^{\mathrm{OL}},d^{\Bar{\pi}^\star})\). Define \(r^{\widehat{\pi}_{\mathrm{TS}}}(\sigma)=\mathbb{E}_{A\sim \widehat{\pi}_{\mathrm{TS}}(\cdot\mid\sigma)}[r(\sigma,A)].\) Then we have \(\widehat \rho^{\mathrm{rel}}-r^{\widehat{\pi}_{\mathrm{TS}}}(\sigma)\le \widehat g(\sigma),\) where \(\widehat{g}(\sigma)\) is defined in 58 .

Lemma 36 guarantees that \(\widehat{\bar\eta}\) and \(\widehat \gamma\) are well-defined. Moreover, by Lemma 37 and Lemma 42, \[N\ge\max\left\{\frac{4}{\min\{y^\star(\tilde{s},0),y^\star(\tilde{s},1)\}},\left(\frac{4\widehat{M}^{\mathrm{up}}}{\widehat{\gamma}^{\mathrm{low}}}\right)^2\right\},\delta\le\delta_{\min} \quad \Longrightarrow \quad N\ge\left(\frac{4\widehat M}{\widehat \gamma}\right)^2,\] so the condition required by Lemma [lem:DC-Vhat-homo] holds.

15.2.3.1 From the empirical drift bound to a true-system bound.

We apply Lemma 7 with source kernel \(Q=\widehat{\boldsymbol{P}}^{\widehat{\pi}_{\mathrm{TS}}}\) and target kernel \(P=\boldsymbol{P}^{\widehat{\pi}_{\mathrm{TS}}}\), benchmark \(R=\widehat{\rho}^{\mathrm{rel}}\), function \(F=\widehat g\), one-period reward \(\bar r=r^{\widehat{\pi}_{\mathrm{TS}}}\), and \(a=\frac{\widehat\gamma}{4(\widehat\beta+r_{\max})}, b=6\exp(8)S\widehat{\tilde{V}}_{\max}\exp(-\widehat C N), c=1, d=0.\) The drift and gap-dominance conditions are Lemmas [lem:DC-Vhat-homo] and 39; the preceding bounds ensure that their assumptions hold. Lemma 7 gives \[\widehat{\rho}^{\mathrm{rel}}-\rho^{\widehat{\pi}_{\mathrm{TS}}}(\boldsymbol{s}_0) \le \frac{4(\widehat\beta+r_{\max})}{\widehat\gamma}\sup_\sigma |(\boldsymbol{P}^{\widehat{\pi}_{\mathrm{TS}}}-\widehat{\boldsymbol{P}}^{\widehat{\pi}_{\mathrm{TS}}})\widehat{V}(\sigma)| +\frac{4(\widehat\beta+r_{\max})}{\widehat\gamma}\,6\exp(8)S\widehat{\tilde{V}}_{\max}\exp(-\widehat C N).\] Using Lemma 45, Lemma 37, and Lemma 38, we obtain \[\widehat{\rho}^{\mathrm{rel}}-\rho^{\widehat{\pi}_{\mathrm{TS}}}(\boldsymbol{s}_0) \le \frac{4\widehat{V}_{\max}(\widehat\beta_{\max}+r_{\max})}{\widehat{\gamma}^{\mathrm{low}}}N\delta +\frac{4(\widehat\beta_{\max}+r_{\max})}{\widehat{\gamma}^{\mathrm{low}}}\,6\exp(8)S\widehat{\tilde{V}}_{\max}\exp(-\widehat C N).\] Defining the constants accordingly completes the proof. ◻

15.3 Other Lemmas and Proofs↩︎

Lemma 40. When \(N\ge\left(\frac{4M}{\gamma}\right)^2\), the Lyapunov function \(\tilde{V}\) defined in 50 satisfies: \[\mathbb{E}^{\pi_{\mathrm{TS}}}\left[\left(\tilde{V}(\Sigma_{t+1})-\frac{\bar\eta}{2}\right)^+\mid \Sigma_t \right]-\left(\tilde{V}(\Sigma_t)-\frac{\bar\eta}{2}\right)^+\le-\frac{\gamma}{4}\mathbb{I}[D_t^{\mathrm{OL}}\neq [N]]+6\exp(8)S\tilde{V}_{\max}\exp(-CN),\] where \(\gamma\) is defined in 53 and \(M,C\) are defined in ?? .

Proof. Proof We can directly follow the proof of Lemma 8 in [14]. Showing all the constants explicitly gives us the result; we omit the details here. ◻

The following lemma gives an upper bound of \(\left\Vert V\right\Vert _{\infty}\).

Lemma 41. Under Assumption 2, the Lyapunov function \(V\) defined in 52 satisfies \[\left\Vert V\right\Vert _{\infty}\le V_{\max}\triangleq\tilde{V}_{\max}+\frac{\gamma}{\sqrt{\mu^\star_{\min}}}\frac{1}{1-\left\lVert \Phi\right\rVert _{\mu^\star\to\mu^\star}}.\]

Proof. Proof We first notice that: \((\tilde{V}-\frac{\bar\eta}{2})^+\le \left\Vert \tilde{V}\right\Vert _{\infty}\le \tilde{V}_{\max}.\) Also, we have \[\begin{align} \beta&=\sup_\sigma\left|(\mu^\star-\boldsymbol{x}([N]))Qb-\mathbb{E}\left[(\mu^\star-\boldsymbol{X}_t)Qb\mid \Sigma_t=\sigma\right]\right| \\ & \ge \sup_{\sigma:d^{\mathrm{OL}}=[N]}\left|(\mu^\star-\boldsymbol{x}([N]))Qb-(\mu^\star-\boldsymbol{x}([N]))\Phi Qb\right| \\ & = \sup_{\sigma:d^{\mathrm{OL}}=[N]}\left|(\mu^\star-\boldsymbol{x}([N]))(I-\Phi) Qb\right| \\ & = \sup_x\left|(\mu^\star-\boldsymbol{x}([N]))b\right| \ge \left\Vert b-(\mu^\star b)\mathbf{1}\right\Vert _{\infty} \ge \frac{\left\Vert b\right\Vert _{\infty}}{2}. \end{align}\] where the first inequality follows from Lemma 46, and in the last inequality we use Lemma 47 by noticing \(b(\tilde{s})=0\) and letting \(c=\mu^\star b\). Hence, \[\begin{align} \frac{\gamma}{4(\beta+r_{\max})}(\mu^\star-\boldsymbol{x}([N]))Qb \le &\frac{\gamma}{2\left\Vert b\right\Vert _{\infty}+4r_{\max}}\left\Vert (\mu^\star-\boldsymbol{x}([N]))Qb\right\Vert _{\infty}\\ \le&\frac{\gamma}{2\left\Vert b\right\Vert _{\infty}+4r_{\max}}\left\Vert \mu^\star-\boldsymbol{x}([N])\right\Vert _{1}\left\lVert Q\right\rVert _{\infty \to \infty}\left\Vert b\right\Vert _{\infty}\le\gamma\left\lVert Q\right\rVert _{\infty \to \infty}, \end{align}\] where the last inequality we use the fact that \(\left\Vert \mu^\star-\boldsymbol{x}([N])\right\Vert _{1}\le 2\). Since \(\left\lVert \Phi\right\rVert _{\mu^\star\to\mu^\star}<1\), so we can write \(Q\) as: \(Q=(I-\Phi)^{-1}=\sum_{t=0}^\infty\Phi^t.\) Then \[\begin{align} \left\lVert Q\right\rVert _{\infty \to \infty} \le \frac{\left\lVert Q\right\rVert _{\mu^\star\to\mu^\star}}{\sqrt{\mu^\star_{\min}}} &\le \frac{1}{\sqrt{\mu^\star_{\min}}}\sum_{t=0}^\infty \left\lVert \Phi\right\rVert _{\mu^\star\to\mu^\star} = \frac{1}{\sqrt{\mu^\star_{\min}}(1-\left\lVert \Phi\right\rVert _{\mu^\star\to\mu^\star})}. \end{align}\] Combining the above results, we obtain \(\left\Vert V\right\Vert _{\infty}\le \tilde{V}_{\max}+\frac{\gamma}{\sqrt{\mu^\star_{\min}}}\frac{1}{1-\left\lVert \Phi\right\rVert _{\mu^\star\to\mu^\star}}.\) ◻

Lemma 42. When \(\delta\le\delta_{\min}\), we have the bound \(\widehat{M}\le\widehat{M}^{\mathrm{up}}\), where \[\label{def:ubmhat} \begin{align} \widehat{M}^{\mathrm{up}}\triangleq&\frac{2\lambda^{\mathrm{ub}}_{\widehat{W}}+2\lambda^{\mathrm{ub}}_{\widehat{U}}}{4\omega}\left(1+\frac{4}{\min\{y^\star(\tilde{s},0),y^\star(\tilde{s},1)\}}\right)+5\sqrt{\lambda^{\mathrm{ub}}_{\widehat{U}}}S+3\sqrt{\lambda^{\mathrm{ub}}_{\widehat{W}}}S\\ & +\exp(33)\left(\sqrt{\lambda^{\mathrm{ub}}_{\widehat{W}}}+\sqrt{\lambda^{\mathrm{ub}}_{\widehat{U}}}\right)\frac{32(\lambda^{\mathrm{ub}}_{\widehat{U}})^{\frac{3}{2}}S^{\frac{5}{2}}}{\min\{y^\star(\tilde{s},0),y^\star(\tilde{s},1)\}}+2\sqrt{\lambda^{\mathrm{ub}}_{\widehat{W}}}. \end{align}\qquad{(14)}\]

Proof. Proof According to Theorem 3, when \(\delta\le\delta_{\min}\), we have \[\begin{align} \frac{3}{2}S^{-1/2}\min\{y^\star(\tilde{s},0),y^\star(\tilde{s},1)\} \ge\widehat \eta &=S^{-1/2}\min\{\widehat{y}^\star(\tilde{s},0),\widehat{y}^\star(\tilde{s},1) \ge \frac{1}{2}S^{-1/2}\min\{y^\star(\tilde{s},0),y^\star(\tilde{s},1)\}. \end{align}\] It is clear that \(\widehat K_{Vh}\ge 2\), so \[\begin{align} \widehat M=&\frac{\widehat L}{2\widehat K_{Vh}\omega}\left(1 + \frac{2S^{-\frac{1}{2}}}{\widehat \eta}\right)+5\lambda_{\widehat{U}}^{1/2}S+3\lambda_{\widehat{W}}^{1/2}S +(\lambda_{\widehat{W}}^{1/2}+\lambda_{\widehat{U}}^{1/2})\exp\left(\frac{1}{2\lambda_{\widehat{U}}^3S^3}+32\right)\frac{16\lambda_{\widehat{U}}^{3/2}S^{2}}{\widehat \eta} +2\lambda_{\widehat{W}}^{1/2}\\ \le &\frac{2\lambda^{\mathrm{ub}}_{\widehat{W}}+2\lambda^{\mathrm{ub}}_{\widehat{U}}}{4\omega}\left(1+\frac{4}{\min\{y^\star(\tilde{s},0),y^\star(\tilde{s},1)\}}\right)+5\sqrt{\lambda^{\mathrm{ub}}_{\widehat{U}}}S+3\sqrt{\lambda^{\mathrm{ub}}_{\widehat{W}}}S\\ & +\exp(33)\left(\sqrt{\lambda^{\mathrm{ub}}_{\widehat{W}}}+\sqrt{\lambda^{\mathrm{ub}}_{\widehat{U}}}\right)\frac{32(\lambda^{\mathrm{ub}}_{\widehat{U}})^{\frac{3}{2}}S^{\frac{5}{2}}}{\min\{y^\star(\tilde{s},0),y^\star(\tilde{s},1)\}}+2\sqrt{\lambda^{\mathrm{ub}}_{\widehat{W}}}\triangleq\widehat{M}^{\mathrm{up}} \end{align}\] where \(\lambda^{\mathrm{ub}}_{\widehat{W}},\lambda^{\mathrm{ub}}_{\widehat{U}}\) are defined in ?? and ?? , which only depend on the parameters of the original system. ◻

The following lemma bounds \(\left\Vert \widehat{V}\right\Vert _{\infty}\) under a sufficiently small single-arm estimation error.

Lemma 43. Consider a \(N\)-armed RB problem with an initial state \(\boldsymbol{s}_0\) satisfying Assumptions 2, 3. Suppose we have the single-armed model accuracy bound: \(\max_{s \in \mathcal{S},\;a \in \mathcal{A}} \left\| \widehat{P}(\cdot \mid s, a) - P(\cdot \mid s, a) \right\|_1 \le \delta\le\delta_{\min}.\) Then the Lyapunov function defined in 54 satisfies: \[\begin{align} \left\Vert \widehat V\right\Vert _{\infty} \le& \widehat{ V}_{\max}\triangleq\frac{3}{\sqrt{\mu^\star_{\min}}}\sqrt{\frac{2}{1-\left\lVert \Phi\right\rVert _{\mu^\star\to\mu^\star}}}+6\sqrt{S(3+\log_2S)\tau} +\frac{\widehat{\gamma}^{\mathrm{up}}}{\sqrt{\mu^\star_{\min}}}\frac{2}{1-\left\lVert \Phi\right\rVert _{\mu^\star\to\mu^\star}}. \end{align}\]

Proof. Proof We first notice that: \[\begin{align} (\widehat{\tilde{V}}-\frac{\bar\eta}{2})^+& \le \left\Vert \widehat{\tilde{V}}\right\Vert _{\infty}\le \widehat{\tilde{V}}_{\max}\le 3\lambda_{\widehat{U}}^{1/2}+3\lambda_{\widehat{W}}^{1/2} \le\frac{3}{\sqrt{\mu^\star_{\min}}}\sqrt{\frac{2}{1-\left\lVert \Phi\right\rVert _{\mu^\star\to\mu^\star}}}+6\sqrt{S(3+\log_2S)\tau}, \end{align}\] where the last inequality uses Lemma 34 and Lemma 35. Then following the same argument as Lemma 41, we have \[\begin{align} \frac{\widehat\gamma}{4(\widehat \beta+r_{\max})}(\widehat{\mu}^\star-\boldsymbol{x}([N]))\widehat{Q}\widehat b \le \widehat\gamma\left\lVert \widehat Q\right\rVert _{\infty \to \infty} & \le\frac{\widehat\gamma}{\sqrt{\mu^\star_{\min}}\big(1-\left\lVert \widehat{\Phi}\right\rVert _{\mu^\star\to\mu^\star}\big)}\\ & \le\frac{\widehat\gamma}{\sqrt{\mu^\star_{\min}}}\frac{2}{1-\left\lVert \Phi\right\rVert _{\mu^\star\to\mu^\star}} \le \frac{\widehat{\gamma}^{\mathrm{up}}}{\sqrt{\mu^\star_{\min}}}\frac{2}{1-\left\lVert \Phi\right\rVert _{\mu^\star\to\mu^\star}}, \end{align}\] where the last inequality we use Lemma 37. Combining the above results we get the final bound. ◻

Lemma 44. Consider a \(N\)-armed RB problem with an initial state \(\boldsymbol{s}_0\) satisfying Assumptions 2, 3. Suppose we have the single-armed model accuracy bound: \(\max_{s \in \mathcal{S},\;a \in \mathcal{A}} \left\| \widehat{P}(\cdot \mid s, a) - P(\cdot \mid s, a) \right\|_1 \le \delta.\) Then for all \(\sigma=(\boldsymbol{x},d^{\mathrm{OL}},d^{\Bar{\pi}^\star})\), we have \(|(\widehat \boldsymbol{P}^{\pi_{\mathrm{TS}}}-\boldsymbol{P}^{\pi_{\mathrm{TS}}} )V(\sigma)| \le V_{\max}N\delta.\)

Proof. Proof Note that for all \(t,\) we have \[\begin{align} \boldsymbol{P}^{\pi_{\mathrm{TS}}}V(\sigma) =\mathbb{E}^{\pi_{\mathrm{TS}}}\left[V(\Sigma_{t+1})\mid \Sigma_t=\sigma\right] &=\mathbb{E}^{\pi_{\mathrm{TS}}}\left[V(\boldsymbol{X}_{t+1},D_{t+1}^{\mathrm{OL}},D_{t+1}^{\Bar{\pi}^\star})\mid \Sigma_t=\sigma\right] \\ & = \mathbb{E}^{\pi_{\mathrm{TS}}}\left[\mathbb{E}^{\pi_{\mathrm{TS}}}\left[V(\boldsymbol{X}_{t+1},D_{t+1}^{\mathrm{OL}},D_{t+1}^{\Bar{\pi}^\star})\mid \boldsymbol{X}_{t+1}, \Sigma_t=\sigma\right]\mid \Sigma_t=\sigma \right] \end{align}\] Introduce the shorthand \(f(\boldsymbol{X}_{t+1},\sigma) = \mathbb{E}^{\pi_{\mathrm{TS}}}\left[V(\boldsymbol{X}_{t+1},D_{t+1}^{\mathrm{OL}},D_{t+1}^{\Bar{\pi}^\star})\mid \boldsymbol{X}_{t+1}, \Sigma_t=\sigma\right]\) It is clear that \(0\le f(\boldsymbol{X}_{t+1},\sigma)\le V_{\max}, \forall t\). Then: \[\begin{align} \boldsymbol{P}^{\pi_{\mathrm{TS}}}V(\sigma)& =\mathbb{E}^{\pi_{\mathrm{TS}}}\left[f(\boldsymbol{X}_{t+1},\sigma)\mid \Sigma_t=\sigma\right] \\ & = \mathbb{E}^{\pi_{\mathrm{TS}}}\left[\mathbb{E}^{\pi_{\mathrm{TS}}}[f(\boldsymbol{X}_{t+1},\sigma)\mid \Sigma_t=\sigma, \boldsymbol{A}_t\sim \pi_{\mathrm{TS}}(\sigma)]\mid \Sigma_t=\sigma\right] \\ & = \mathbb{E}^{\pi_{\mathrm{TS}}}\left[\sum_{\boldsymbol{x}_{t+1}}f(\boldsymbol{x}_{t+1},\sigma)\cdot \boldsymbol{P}(\boldsymbol{x}_{t+1}\mid \boldsymbol{x}, \boldsymbol{A}_t)\mid \Sigma_t=\sigma\right] \\ & =\sum_{\boldsymbol{a}_t}\sum_{\boldsymbol{x}_{t+1}}f(\boldsymbol{x}_{t+1},\sigma)\cdot \boldsymbol{P}(\boldsymbol{x}_{t+1}\mid \boldsymbol{x}, \boldsymbol{a}_t)\cdot\pi_{\mathrm{TS}}(\boldsymbol{a}_t\mid \sigma) . \end{align}\] Following the same argument, we have: \[\begin{align} \widehat \boldsymbol{P}^{\pi_{\mathrm{TS}}}V(\sigma) =\widehat \mathbb{E}^{\pi_{\mathrm{TS}}}\left[V(\Sigma_{t+1})\mid \Sigma_t=\sigma\right] &=\widehat \mathbb{E}^{\pi_{\mathrm{TS}}}\left[V(\boldsymbol{X}_{t+1},D_{t+1}^{\mathrm{OL}},D_{t+1}^{\Bar{\pi}^\star})\mid \Sigma_t=\sigma\right] \\ & = \widehat \mathbb{E}^{\pi_{\mathrm{TS}}}\left[\widehat \mathbb{E}^{\pi_{\mathrm{TS}}}\left[V(\boldsymbol{X}_{t+1},D_{t+1}^{\mathrm{OL}},D_{t+1}^{\Bar{\pi}^\star})\mid \boldsymbol{X}_{t+1}, \Sigma_t=\sigma\right]\mid \Sigma_t=\sigma \right] \\ & = \widehat \mathbb{E}^{\pi_{\mathrm{TS}}}\left[\mathbb{E}^{\pi_{\mathrm{TS}}}\left[V(\boldsymbol{X}_{t+1},D_{t+1}^{\mathrm{OL}},D_{t+1}^{\Bar{\pi}^\star})\mid \boldsymbol{X}_{t+1}, \Sigma_t=\sigma\right]\mid \Sigma_t=\sigma \right], \end{align}\] where the last equality is owing to the following key observation: given \(\boldsymbol{X}_{t+1}\), the choice of the two sets \(D_{t+1}^{\mathrm{OL}}, D_{t+1}^{\Bar{\pi}^\star}\) has no relationship with the transition kernel \(P\) and \(\widehat P\). Hence, \(\widehat{\boldsymbol{P}}^{\pi_{\mathrm{TS}}}V(\sigma) = \sum_{\boldsymbol{a}_t}\sum_{\boldsymbol{x}_{t+1}}f(\boldsymbol{x}_{t+1},\sigma)\cdot \widehat{\boldsymbol{P}}(\boldsymbol{x}_{t+1}\mid \boldsymbol{x}, \boldsymbol{a}_t)\cdot\pi_{\mathrm{TS}}(\boldsymbol{a}_t\mid \sigma)\) Then \[\begin{align} |(\widehat{\boldsymbol{P}}^{\pi_{\mathrm{TS}}}-\boldsymbol{P}^{\pi_{\mathrm{TS}}})V(\sigma)| & =\sum_{\boldsymbol{a}_t}\sum_{\boldsymbol{x}_{t+1}}f(\boldsymbol{x}_{t+1},\sigma)\left(\widehat{\boldsymbol{P}}(\boldsymbol{x}_{t+1}\mid \boldsymbol{x},\boldsymbol{a}_t)-\boldsymbol{P}(\boldsymbol{x}_{t+1}\mid \boldsymbol{x},\boldsymbol{a}_t)\right)\pi_{\mathrm{TS}}(\boldsymbol{a}_t\mid \sigma)\\ & \le V_{\max}\sum_{\boldsymbol{a}_t}\pi_{\mathrm{TS}}(\boldsymbol{a}_t\mid \sigma)\sum_{\boldsymbol{x}_{t+1}}\left|\widehat{\boldsymbol{P}}(\boldsymbol{x}_{t+1}\mid \boldsymbol{x},\boldsymbol{a}_t)-\boldsymbol{P}(\boldsymbol{x}_{t+1}\mid \boldsymbol{x},\boldsymbol{a}_t)\right|\\ & \le V_{\max}\sum_{\boldsymbol{a}_t}\pi_{\mathrm{TS}}(\boldsymbol{a}_t\mid \sigma)\left\Vert \widehat{\boldsymbol{P}}(\cdot\mid \boldsymbol{x},\boldsymbol{a}_t)-\boldsymbol{P}(\cdot\mid \boldsymbol{x},\boldsymbol{a}_t)\right\Vert _{1} \\ & \le V_{\max}N\delta \sum_{\boldsymbol{a}_t}\pi_{\mathrm{TS}}(\boldsymbol{a}_t\mid \sigma) = V_{\max}N\delta, \end{align}\] where in the last inequality we use Lemma [single-to-Narm-accu]. ◻

Applying the same argument to the empirical system, we obtain the following lemma:

Lemma 45. Consider a \(N\)-armed RB problem with an initial state \(\boldsymbol{s}_0\) satisfying Assumptions 2 and 3. Suppose we have the single-armed model accuracy bound: \(\max_{s \in \mathcal{S},\;a \in \mathcal{A}} \left\| \widehat{P}(\cdot \mid s, a) - P(\cdot \mid s, a) \right\|_1 \le \delta\le\delta_{\min},\) where \(\delta_{\min}\) is defined in ?? . Then for all \(\sigma=(\boldsymbol{x},d^{\mathrm{OL}},d^{\widehat{\Bar{\pi}}^\star})\), we have \(|(\boldsymbol{P}^{\widehat{\pi}_{\mathrm{TS}}}-\widehat \boldsymbol{P}^{\widehat{\pi}_{\mathrm{TS}}} )\widehat{V}(\sigma)| \le \widehat{V}_{\max}N\delta.\)

The following lemma shows that if all arms follow the Optimal Local Control subroutine, the expected scaled state-count vector \(\mathbb{E}^{\pi_{\mathrm{TS}}}[\boldsymbol{X}_t([N])]\) has a linear dynamics.

Lemma 46 ([14], Lemma 1). Under Assumption 2, suppose 48 holds for the \(N\)-armed system at time step \(t\). We have \[\label{eq:8} \mathbb{E}^{\pi_{\mathrm{TS}}}\left[\, \boldsymbol{X}_{t+1}\bigl([N]\bigr)-\mu^{\star} \mid \boldsymbol{X}_t,\;\text{all arms follow Optimal Local Control\;} \right] = \bigl( \boldsymbol{X}_t\bigl([N]\bigr)-\mu^{\star} \bigr)\Phi .\qquad{(15)}\] where \(\Phi\) is the \(S\times S\) matrix defined in 14 .

Lemma 47. Let \(b\in\mathbb{R}^n\). Suppose there exists an index \(i_0\in\{1,\dots,n\}\) such that \(b_{i_0}=0\). Then for every scalar \(c\in\mathbb{R}\), it holds that \(\|\,b-c\mathbf{1}\,\|_\infty \;\ge\; \frac{1}{2}\|b\|_\infty,\) where \(\mathbf{1}\in\mathbb{R}^n\) denotes the all-ones vector.

Proof. Proof Let \(M\triangleq \|b\|_\infty = \max_{1\le i\le n}|b_i|\). Choose an index \(i_{\max}\) such that \(|b_{i_{\max}}|=M\). By assumption, pick \(i_0\) with \(b_{i_0}=0\). For any \(c\in\mathbb{R}\), we have \(\|b-c\mathbf{1}\|_\infty = \max_{1\le i\le n}|b_i-c| \;\ge\; \max\bigl(|b_{i_{\max}}-c|,\;|b_{i_0}-c|\bigr) = \max\bigl(|b_{i_{\max}}-c|,\;|c|\bigr).\) Now consider two cases. If \(|c|\ge M/2\), then \(\|b-c\mathbf{1}\|_\infty \ge |c|\ge M/2\). If \(|c|< M/2\), then by the reverse triangle inequality, \(|b_{i_{\max}}-c| \;\ge\; \bigl||b_{i_{\max}}|-|c|\bigr| = M-|c| > M-\frac{M}{2}=\frac{M}{2}.\) Hence \(\|b-c\mathbf{1}\|_\infty \ge |b_{i_{\max}}-c|\ge M/2\).

Combining the two cases gives \(\|b-c\mathbf{1}\|_\infty \ge M/2 = \|b\|_\infty/2\) for all \(c\). Besides, the constant \(1/2\) is tight: for example, \(b=(0,M)\) and \(c=M/2\) give \(\|b-c\mathbf{1}\|_\infty = M/2 = \|b\|_\infty/2\). ◻

References↩︎