Projection-based Lyapunov method for fully heterogeneous weakly-coupled MDPs
Authors: XiangCheng Zhang
Yige Hong
Weina Wang
Venue: NeurIPS 2025 spotlight ()
Keywords: weakly-coupled Markov decision processes
fully heterogeneous systems
asymptotic optimality
planning
average-reward Markov decision processes
Lyapunov analysis
Primary area: reinforcement_learning
TL;DR: We use a novel projection-based Lyapunov function to prove the first asymptotic optimality theorem for fully heterogeneous weakly-coupled Markov Decision Processes.

Abstract: Heterogeneity poses a fundamental challenge for many real-world large-scale decision-making problems but remains largely understudied.
In this paper, we study the _fully heterogeneous_ setting of a prominent class of such problems, known as weakly-coupled Markov decision processes (WCMDPs).
Each WCMDP consists of $N$ arms (or subproblems), which have distinct model parameters in the fully heterogeneous setting, leading to the curse of dimensionality when $N$ is large.
We show that, under mild assumptions, an efficiently computable policy achieves an $O(1/\sqrt{N})$ optimality gap in the long-run average reward per arm for fully heterogeneous WCMDPs as $N$ becomes large.
This is the _first asymptotic optimality result_ for fully heterogeneous average-reward WCMDPs.
Our main technical innovation is the construction of projection-based Lyapunov functions that certify the convergence of rewards and costs to an optimal region, even under full heterogeneity.

Projection-based Lyapunov method for fully heterogeneous weakly-coupled MDPs
Xiangcheng Zhang!*
Yige Hong2*
Weina Wang?
Weiyang College, Tsinghua University
2 Computer Science Department, Carnegie Mellon University
xc-zhang21 @mai 1 t.s nggua edu.cn (y Lyiggn geh, weinaw lcs. cmu.edii edu
Abstract
Heterogeneity poses fundamental challenge for many real-world large-scale decision- maasiinnmmainnggg problems but remains largely understudied. In this paper, we study the fully heterogeneous setting of a prominent class of such problems, known as weakly-coupled Markov decision processes (WCMDPs). Each WCMDP con- sists of N arms (or subproblems), which have distinct model parameters in the fully heterogeneous setting, leading to the curse of dimensionality when N is large. We show that, under mild assumptions, achieves ((1/VN) N) optimality gap in the long-run average reward per for fully heterogeneous WCMDPs as N becomes large. This is the first asymptotic optimality result for fully heterogeneous average-reward WCMDPs. Our main technical innovation the construction of projection-based Lyapunov functions that certify the convergence of rewards and costs an optimal region, even under full heterogeneity
efficiently computable policy
Introduction
Heterogeneity poses fundamental challenge for many real-world decision- makinn problems, where each problem consists of a large number of interacting components. However, despite its practical significance, heterogeneity remains largely understudied in the literature. In this paper, we study heterogeneous settings of prominent class of such problems, known as weakly-coupled Markov decision processes (WCMDPs) arm itself is Markov decision process (MDP). In a heterogeneous setting. the MDPs could be distinct. At each time step, the
2 A WCMDP consists of N arms (or subproblems), where each
maker selects an action for each arm, which affects the arm's transition probabiltities and reward, and then the arms make state transitions independently. However, these actions are subject to set of global budger constraints, where each constraint limits one type of total cost across all arms at each time step. The objective is to find a policy that maximizes the long-run average reward over an infinite time horizon. We focus on the planning setting, where all the model parameters (reward function, cost functions, budget, and transition kernel) are known.
WCMDPs have been used model a wide range of applications, including online advertising 7 job scheduling [X]. healthcare 5l. surveillance 40), and machine maintenance 21 A faithful modeling of these applications calls for heterogeneity. For instance, in [5], arms are beneficiaries of a health program and they could react to interventions differently: in 40 arms are targets of
'These authors contributed equally to this work.
WWrk done during visit at Carnegie Mellon University.
A full version of this paper [54] can be found at attptttts//// /tt::////www... www.warxiv.or.goooooo wttp:/ggggbbb///////e 2502. 6266
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

surveillance who have different locations and probabilities to be exposed: in 221 arms are machines that could require distinct repair schedules.
Although heterogeneity is crucial in the modeling of these applications, most existing work on average- reward WCMDPs establishes asymptotic optimality only for the homogeneous setting where all arms share the same set of model parameters [4 15
Only a few exceptions address heterogeneity, but in highly specialized settings. Among these, a common approach to handle heterogeneity is to consider the typed heterogeneous setting, where the N arms are divided into a constant number of types as N scales up, with each type having distinct model parameters. While heterogeneous WCMDPs have been studied under the finite-horizon total-reward and discounted-rewail criteria, these results do not extend the werage-reward setting we consider. We review related work in more detail at the end of this section and also in Appendix A
22 24
42 47
25
59 46
The key distinction between the homogeneous (or typed heterogeneous) setting and the fully het- erogeneous setting is whether the arms can be divided into a constant number of homogeneous groups. In the former, the system dynamics depends only on the fraction of arms in each state each homogeneous group. Thus, the effective dimension of the state space is polynomial in N. In contrast, in the fully heterogeneous setting, the state space grows exponentially in N, making the problem truly high-dimensional.
Our contribution. In this paper, we study fully heterogeneous WCMDPs. We propose a policy we call the ID policy with reassigument, which generalizes the ID policy in the literature 227. In our policy, we first perform an ID reassignment algorithm reorder the arms, which ensures proper arm prioritization during policy execution. We then run variant of the ID policy adapted to handle heterogeneity, which consists of two phases. The first phase is pre-processing phase, where we compute an optimal single-armed policy for each arm (denoted as के for the i-th arm) that prescribes the ideal action the arm would take at each state. The second phase is the real-time phase. At each time step, the policy iterates over the arms according to their reassigned IDs, and it lets as many arms as possible follow their respective ideal actions while satisfying the budget constraints. Unlike the original ID policy, which has only one optimal single-armn aamee policy due to homogeneous arms, our policy computes N optimal single-armed policies, one for each arm. Our proposed policy is efficiently computable, with computational complexity polynomial in N.
We prove that the proposed ID policy with reassignment achieves an O(1//N) optimality gap under mild assumptions as the number of arms N becomes large. Here, the optimality gap refers to the difference between the long-run average reward per arm under our policy and that under the optimal policy. This is the first result establishing asymptotic optimality for fully heterogeneous averuge-reward WCMDPs.
We remark that the original ID policy was designed for special case of WCMDPs known as restless bandits, and it is for the homogeneous setting. While the generalization in our proposed policy is natural, identifying the appropriate generalization and establishing its optimality gap in the fully heterogeneous setting are technically challenging and require new thcoretical approaches.
Technical novelty. The main technical innovation of the paper is the introduction of novel Lyapunov function for fully heterogeneous WCMDPs. Specifically, to prove the asymptotic optimality of a policy, a key step is to show that the system state is globally attracted an optimal region where most arms can follow the ideal actions generated by their respective optimal single-armed policies 7t's. In the homogeneous setting, we can prove such convergence using state aggregation techniques that rely on the symmetry of arms. However, in the heterogeneous setting, states of different arms cannot be aggregated since arms are no longer symmetric. Our technique is to project arm states onto set of carefully selected feature vectors, and define the Lyapunov function based on these projections. These feature vectors encode the minimal amount of information needed to evaluate the relevant functions of the system state (e.g., instantaneous reward or cost) and predict Lyapunov function provides a principled way to
their future expectations. This projection-basee measure deviations of the system state from the optimal region in fully heterogeneous setting. A more detailed discussion of this approach can be found in Section
Beyond WCMDPs, our techniques have the potential to be applied to more general heterogeneous large stochastic systems. Heterogeneity has been a topic of strong interest these systems, but is known to be a challenging problem with limited theoretical results. Only recently have there been

---

notable breakthroughs. 11 2 extended the popular mean-field analysis to class of heterogeneous large stochastic systems for the first time, but the results are only for transient distributions. Another line of work [55 566 studied heterogeneous load-balancing systems. They first analyzed the transient distributions and then used interchange-of-line
arguments extend the results to steady state. Our method provides a more direct framework for steady-state analysis and has the potential to generalize to a broader range of heterogeneous stochastic systems.
Related work. WCMDPs have been extensively studied with a rich body of literature. Here we briefly overview the most relevant work and refer the reader Appendix A for a detailed survey.
We first focus on the average-reward criterion. As mentioned earlier, most existing work considers the homogeneous sefting. Early work on WCMDPs primarily focuses a special case known as the restless bandit (RB) problem, where each arm's 's MDP has a binary action space (active and passive actions) and there is only one budget constraint that limits the total number of active actions across all arms at each time step. The seminal work by Whittle [4]] introduced the RB problem and the celebrated Whittle index policy, which was later shown to achieve an o(1) optimality gap
as N + oc under a set of conditions [2]. Subsequent work on RBs has focused on designing
policies that achieve asymptotic optimality under more relaxed conditions [25 27 39
well 27 or ((exp(-cx)) 14 15 26 Among these
as improving the optimality gap to O(L/vN)
papers, [25] 39 address heterogeneous RBs. However, 39 focuses on the typed heterogeneous
setting, where the N arms are divided into a constant number of types as N - c0. The paper (25 includes an extension to the fully heterogeneous setting. However, for their result to yield asymptotic optimality, there need to be further assumptions on the orders of the so-called synchronization times in the paper. The policies in both papers cannot be straightforwardly extended to general WCMDPs, which have multiple actions, multiple budget constraints, and state-dependent cost functions.
Beyond RBs, work on general average-reward WCMDPs is scarce. The closest to ours are 24 39 46 which studied WCMDPs with single budget constraint and established o optimality gaps, but again in the homogeneous setting [24] or the typed heterogeneous setting 39 46.. More recently, [22] proved the first o(1) optimality gap result for WCMDPs with general budget constraints, but in the homogeneous setting.
Under the finite-horizz rotal-reward discounted reward criteria, there has been more work on heterogeneous settings, including both the typed heterogeneous setting [12) and, more recently, the fully heterogeneous setting 10 50) However, the optimality gap these papers generally grows super-lineurly with the (effective) time horizon, except under restrictive conditions. Consequently, it difficult to extend these results to the average-reward setting and still achieve asymptotic optimality,
Although our work focuses on the planning setting where all model parameters are known, there has been growing interest in developing reinforcement learning algorithms for the learning setting with unknown parameters 3 13
Many of these approaches rely on well-designed planning policies foundation to achieve learning efficiency. In this context, our results can serve as an important building block for developing model- based learning algorithms for fully heterogeneous WCMDPs.
30
32
33
36
45
46
General notation. Let R. N. and N4 denote the sets of real numbers, nonnegative integers, and positive integers, respectively. Let [N] & 21,2.... .... N} for any N E N. and [n nz] & {ni,n1 n1 + 1,....,,... n2) for n1, n2 E N4 with n1 S n2. Let [0, 1]x = (i/N: i N,O < i/N < 1}. the set of integer multiples of 1 1/N in j0, 1]. For a matrix A E RRdxd, we denote its operator norm as ||A|I, = sup ||Ax|l, ||=||, We use boldface letters to denote matrices, and regular letters to denote vectors and scalars. We write R$ for the set of real-valued vectors indexed by elements of S, or equivalently, the set of real-valued functions on S; for each u E R. let us)) to denote its element corresponding to E S.
2 Problem setup
We consider a weakly-coupled Markov decision process (WCMDP) that consists of N arms. Each arm has an ID i E [N] and is associated with a smaller MDP denoted as M, (S, A, Pi, (CIg))e((g)) Here S and A are the state space and the action space, respectively, both assumed be finite; IP, describes the transition probabilities with (s(s' ss s,a) being the transition probability from state
3

---

to state s' when action is taken. The state transitions of different arms are independent given the actions. When arm is in state s and we take action a, a reward ry ri a) generated, as well as K types of costs (8.x(s,a) k E [K]. We assume that the costs are nonnegative, i.e., CH,((8,) 2 0 for all i E N,,k E [ 8 E S, and a E A. Note that we allow the arms to be fully heterogeneous, i.e., the M,'s can be all distinct.
When taking an action for each arm in this N-armed system, we are subject to budget constraints. Specifically, suppose each arm i is in state 8s. Then the actions, as 's should satisfy the constraints;
(8,, 0z) S Ng,, vk E [K], M
Σ
where each 0g > is a constant independent of N, and og N is referred to as the budger for type-k cost. We assume that there exists an action 0 A that does not incur any type of cost for any arm at any state, i.e., (s. 0)- = 0 for all k E [K] i E [M], E S. This assumption guarantees that there always exist valid actions (e.g., taking action 0 for every arm) regardless of the states of the arms.
Policy and system state. A policy π for the N-armed problem specifies the action for cach of the N arms, in possibly distory-dependee ith arm at time I, and we refer to ST _ (ST,))E(N) as the system state. Similarly, let A7, denote the action applied to arm i at time I, and we refer AF a (AN as the system action. In this paper, we also use an alternative representation of the system state, denoted as X; and defined as follows. Let X =
way. Under policy л. let ST,, denote the state of the
E TR [S] be a row vector where the entry corresponding to state s is given by (s) S[ = s): i.e., X is a one-hot row vector whose s's entry is 1 if ST, and is 0 otherwise. Then let X be an N x [S] matrix whose ith row is X It is easy to see that X contains the same information as S and
refer both of them the system state. In this paper, we often encounter vectors like X = (X,,, (5)),ES) whose entries correspond to different states in S. For such vectors, say u and v, we use the inner product write a sum for convenience (u, v) _ EEes us))r(s). We sometimes omit the superscript x when it is clear from context.
Maximizing average reward. Our objective is to maximize the long-run time-average reward subject to the budget constraints. To be more precise, we follow the treatment for maximiz- ing average reward in [35). For any policy æ and an initial state Sn of the N-armed sys- tem, consider the limsup average reward R+ t Sp) and the liminf average R (m,, So), de- fined as R* Sn) = limsupr=40 + - N EiENy E [r:( A5,)] and RT(m, Sn) = lim in T ET-1 1
N EieiN E [r:(ST, A7,)). If (T, Sn) = R_(r,, So), then the average reward of policy π under the initial condition So exists and is defined as
R(T, So) = R (x,So) R (~= So) = lim
Σ t=0
Σ NE[N]
BI.(ST 4,)]
(2)
T T
N
Note that these reward notions divide the total reward from all arms by the number of arms, N, measuring the reward per arm. The WCMDP problem is to solve the following optimization problem:
maximize policy x
R So)
(3a)
subject to
Σ CR. AT,) S NNN, Vk E [K], 0. KE[N]
(3b)
Let the optimal value of this problem be denoted as RN (N))). Note that since the WCMDP is an MDP with finite state and action space, if we replace the R (T, So) in the objective Ba) with R+ (H,, So), the optimal value stays the same 35 Proposition 9.1.6).
Asymptotic optimality. Recall that exactly solving the WCMDP problem is PSPACE-hard this paper, our goal is to design a policy π that is efficiently computable and asymptotically optimal as N + oc, with the following notion for asymptotic optimality. For any policy n, define its optimality gap as R (N, So) - R (T, So). We say the policy π is asymptotically optimal if
M4 In
RN So) R (T, So) o(1)
N 00.
(4)

---

When we take this asymptotic regime as N - oc, we keep the number of constraints, K, as well as the budget coefficients, 01, ......... ... ag. fixed. We assume that the reward functions and cost functions are uniformly bounded, i.e., SupseN, max [ri(s, a)
Tiax < oo and
s [K] (s, a) _ Cmax 0c. This notion for asymptotic optimality is con- sistent with that in the existing literature (e.g., 139 Definition 4.11J). We are interested in not only achieving asymptotic optimality but also characterizing the order of the optimality gap.
In the remainder of this paper, we focus on stationary Markov policies, which are sufficient for achieving the optimal value because the WCMDP problem is an MDP with finite state and action spaces 35 Theorem 9. 1.8). Under any stationary Markovian policy, the long-run reward R(T, So) = Rt
So) R (T,, So) is always well-defined
B5 Theorem 8.1.1].
LP relaxation and an upper bound on optimality gap. We consider the linear program (LP) below, which will play a critical role in performance analysis and policy design:
RN
maximize (eN)
Σ
Σ
31(s,a))((s,a)
(5a)
(2:(e.0))kEtn
N
KE[N]
SEB,
subject to
Σ
Σ
(($ ok Ak [K],
(5b)
N
KE(N. NER,
Σ
Pi(s s' d')')a(sss, a)) Σ Ev((s,)) (s) e S, [N], (5c)
s' ''EE,'EA
aEA
Σ
va(s', d') = (3. 2 0, Vs E (,EE
(5d)
e'E
Lemma 1 below establishes connection between this LP and the WCMDP. Lemma 1. The optimal value of any N-armed WCMDP problem upper bounded by the optimal value of the corresponding linear program in 5 i.e.,
(N, S RN, VN, VS.
An immediate implication of Lemma is that for any policy its optimality gap is upper bounded as
R2 (N, So) R (T,, So) Ry R (T,, So).
(6)
Therefore, to derive upper bound for the optimality gap, it suffices to control Hy R (TT, So). which we will show is O(Iv/N) in Theorem 1
To see the intuition of Lemma i we interpret the optimization variable yi a) as the long-run fraction of time arm spends in state and takes action We refer to y (s, a) arm i's state-action
frequency for the state-action pair (s, a). Then the constraints in (5b) of the LP can be viewed as
relaxations of the budget constraints in (3b) for the WCMDP. The constraints in (5c) 55 guarantee that (s, a)'s are proper stationary time fractions. Therefore, the L. is a relaxation of the WCMDP and thus achieves higher optimal value. The proof of Lemma D provided in Appendix Cf (54)
Our LP 5 serves a similar role the LP used in previous work on restless bandits and WCMDPs (see, e.g., 15 22 RZ!
42 46)), but with different forms and dependencies our LP and the L. in previous work relax the hard budget constraints to time-average constraints. However, in the homogeneous arm setting [15] 22 24 42), the IP has only one set of state-action frequencies yss, a). and the LP is independent of N. As a result, both the optimal value of the LP and the complexity of solving it are independent of N. Prior work for the typed- gpeddhhetroogeeouu setting 25 39 46 divides the arms into a constant number of types and defines a set of state-action frequency yı (s. a) for each type k. The optimal value of the resulting LP and the complexity of solving it depend on the number of types K. Hong et al. (25) includes a generalization to the fully heterogeneous setting, resulting in an LP similar to ours, although restricted to restless bandits.
25
39
N. Both
In our LP, we define a separate set state-action frequencies (), a) for each arm i [N], making the I.P explicitly depend on N. Therefore, the optimal value Rd depends on N, and the complexity of solving the I.P grows with N. Nevertheless, because the number of variables and constraints scales linearly with N, our LP can still be solved in polynomial time.
5

---

Algorithm 1 ID reassignment
1: Input: optimal state-action frequencies (vy (x, (.eS,,, budgets (o<))&E(K)
2: Output: new arm ID, recorded in newlD(i), for each arm with old ID DiEE [N]
3: Compute (C', (MM,))) and the set of active constraints A using
4: if A then
5: newlD(i) + i for all i E [N]
No need for ID reassignment
6: else
7: Initialize F 6-2 1
> Set of arms that have been assigned new IDs
8:
Initialize xx -- fi E [M] C2 2 6} for all E A
9:
5 a min 02/4; d t
(Amax 5)K awin 12-
10:
for fore=00 1,1...., N/dd - 1 do
I(t) [ld + (e 1)d; Id+11
12:
for k E A do
if EiEr C (newID)) I(0)} < ô then
14:
Pick any from Dx and set new)D(i) < remove i from DE for all k'; add i JF j j j+1 For all E F, assign values to their newlD(i)'s randomly from (nwwlD))))))
15:
16:
3 ID policy with reassignment
In this section, we introduce the ID policy with reassignment, generalized from the ID policy designed for homogeneous restless bandits in the literature [27]. Our policy first performs an II) reassignment procedure, and then proceeds to run variant of the ID policy adapted to handle heterogeneity. We begin by introducing building block of our policy, referred to as optimal single-armed policies, followed by the ID reassignment algorithm and the execution of the adapted ID policy.
Optimal single-armed policies. Once obtain solution to the LP in (), we can construct policy for each arm i, which we refer to as an optimal single-armed policy for arm i. In particular, let (uf (s, a... be an arbitrary optimal solution to the LP in (5). Then for arm i, the optimal single-armed policy, के. is defined as
(..a) Eeer (s.a))
if E.EA (s) 0,
कं (a 8)
if E.EA V/ (s, -0
where 7 8) is the probability of taking action a given that the arm's current state is 8. Note that due to heterogeneity, this optimal single-armed policy मे can be different for different arms.
The rationale behind these policies is as follows. If each arm i individually follows its optimal single-armed policy मद. then the average reward per arm (total reward divided by N) achieves the upper bound RN given by the LP. However, this strategy only guarantees that the budget constraints are satisfied in a time-average sense, rather than conforming to the hard constraints in the original N-armed WCMDP. Thus, having each arm follow its optimal single-armed policy is not valid policy for the original N-armed problem. Nevertheless, these optimal single-armed policies n. serve as a guide for how the arms should ideally behave to maximize rewards. The ID policy uses the #द as reference. It is then designed to ensure that even under the hard budget constraints, most arms follow their optimal single-armed policies most of the time, yielding a diminishing gap Hdd in reward.
ID reassignment. We first define a few quantities that will be used in the ID reassignment algorithm. For each arm i E [N] and each cost type k E [K], the expected cost under the optimal single-arme policy is defined as Cj Eves.aER. V. (s, ()C,,(s, a). Based on C 's, we divide the budget constraints into active constraints and inactive constraints as follows. For each cost type E [K]. we say the type-k budget constraint is active if
E KE[N]
ak N, 2
(8)
and inactive otherwise. Let A C [K]
denote the set of cost types corresponding to active constraints. Note that replacing N/ with any constant and strict fraction of a will not change the results.

---

Algorithm 2 ID policy with reassignment
1: Input: N-armed WCMDP instance (M))
2: Preprocessing:
3: Solve the L.P in 5 and obtain the optimal state-action frequencies (x, (N)
4: Calculate the optimal single-armed policies (#² [e]) using
5: Perform ID reassignment using Algorithm
6: Real-time:
7: for = 0, do
8: Sample ideal actions A.. ~ .t(: (tt)) for all i [N]
9:
1+1
10: while Σien (S,, A,,)) & a Vk E [K] do
11: For arm I, take action Ar, = Ar.i + + 1
12: For each arm E [I, 1,..., N), take action As,
Based on the costs C2 's and the active constraints, the ID reassignment algorithm rearranges arms so that the cost incurred by each contiguous segment of arms is approximately proportional to the length of the segment. We give brief explanation of how the reassigned IDs affect the execution of the policy at the end of this section. The algorithm formally described in Algorithm J] with more details and properties provided in Appendix D of 54 In the rest of the paper, we use the reassigned IDs to refer to arms, i.e., arm i refers to the arm whose new ID assigned by Algorithm
Constructing ID policy. We are now ready to describe our generalized ID policy, formally described in Algorithm 2 The policy begins with one-time preprocessing phase: solve the associated LP, construct the optimal single-armed policies, and reassign arm IDs using the ID reassignment algorithm (Algorithm Dp. After the preprocessing, the policy proceeds at each time step / follows. For each arm i (where i is the reassigned ID), we first sample an action A referred as ideal action, from the optimal single- armed policy म. St,r). We then attempt to execute these ideal actions, i.e., set the real actions equal to the ideal actions, ascending order of arm IDs, starting from i = 1, then i 2, and so on. We continue the attempt until we have used up at least one type of cost budget, at which point we let the remaining arms take action 0 (the no-cost action).
This ID policy is a natural generalization of the ID policy designed for homogeneous restless bandits IDs decide the priority order for executing ideal actions guarantees that a subset of arms (those with smaller IDs) can persistently follow their ideal actions. This persistency gives these arms time to converge their optimal state-action frequencies, which in turn allows their instantaneous costs to converge to steady-state values. This convergence creates slack in the budget constraints, thereby allowing more arms follow their ideal actions. In contrast, if do not use IDs but instead randomly select subset of arms to follow their ideal actions, the convergence may be disrupted. Indeed, (25) provides an example where this randomized strategy fails achieve asymptotic optimality in restless bandits.
27. At a high level, using
When there is ambiguity, refer to the ID policy with reassignment simply as the ID policy.
How the reassigned IDs affect the policy execution. In the heterogeneous setting, arms differ in their cost consumptions under their optimal single-armed policies. The ID reassignment algorithm designed to prevent "plateaus" in cumulative cost as we progress from smaller to larger IDs. If such a plateau exists, the subset of arms allowed to follow their ideal actions (determined by the budget constraints) can become sensitive the randomness in action sampling, potentially leading to performance instability. The ID reassignment algorithm ensures regularity property of the cost consumptions, stated in Lemma 2 in Appendix of [54], which eliminates such plateaus.
4 Main results and technical overview
Before we present the main results, we first state our main assumption. This assumption is for the optimal single-armed policies 7द's. Note that each मं is stationary Markov policy. Therefore, under this policy, the state of arm forms a Markov chain. Let the transition probability matrix of this
7

---

Markov chain be denoted as P. = (P.(s, s') s')ss,, where the row index is the current state and the column index the next state s'. Then Pi s') can be written as
&( = Pi(s' 88 (, 8).
(9)
aEA
One can verify that the stationary distribution of this Markov chain is μn = (4) (s)) with NG (s) = Daea y a), which we refer to as the optimal state distribution for arm i. Let be the mixing time of this Markov chain, defined as
max min { E N: - 1/ce],
(10)
where Pf is the 1-step transition probability matrix. The mixing time T; is finite if the Markov chain P; is unichain (one recurrent class, possibly with transient states) and aperiodic.
Assumption 1. For each arm i N4, the induced Markov chain under the optimal single-armed policy &; is an aperiodic unichain. Furthermore, the mixing times of these Markov chains have uniform upper bound; i.e., there exists a positive such that for all i N_
Ti ST.
(11)
We remark that in the homogeneous or typed heterogeneous settings, once we make the aperiodic unichain assumption Assumption [
the uniform upper bound on mixing times automatically exists.
Next, we state our main theorem, Theorem whose proof is provided in Appendix of [54].
Theorem 1. Consider N-armed WCMDP problem satisfying Assumption ! with initial system state So. Let policy πt be the ID policy with reassignment (Algorithm 2 Then the optimality gap of π bounded as
CID
R (N, So) - R((,, Sb) S
VN
where Cin is positive constant independent of N.
We re-emphasize that our proposed ID policy with reassignment the first efficiently computable policy that achieves an O(I/VN) optimality gap for fully heterogeneous average-reward WCMDPs. In contrast, the best-known optimality gap for efficiently computable policies for average-reward WCMDPs o(1,, achieved only under restrictive budget constraints and typed-hetcrogennetty
We comment that the primary goal of this paper is to characterize the optimality gap in terms of its order in N. which is in line with the main focus of the large body of prior work on restless bandits and WCMDPs. While our analysis also gives an explicit expression for the constant CID. which shows that CDD OKK max(r Cmax 75 (a we have not attempted optimize dependence on other problem parameters, either through refined analysis alternative policy design.
Remark (Generalization of result). Our result can be generalized to the setting where g fraction of arms have unbounded mixing times, and the mixing times of the remaining arms seale with N with an upper bound r. In this case, we can modify the ID policy by reassigning this (NN fraction of arms the largest IDs, effectively ignoring these arms. Applying Theorem to the remaining arms then implics R (N, So) - H(T, So) S O(K* max Cmax } /(a VN) + + Consequently, this modified policy is asymptotically optimal when g(N) o(1) and //81/8).
Adapting the proof of Theorem M also gives the following finite-time bound (see Appendix I of 544
Proposition (Finite-tima time bound). Under the same conditions as Theorem 7
we have for any T
RN, So)
E E
[ri(ST
AT,) S
CiD VN
Cunite T
(12)
TN 1= NE[N]
where Crinie is another positive constant independent of N.
Technical overview
Our technical approach uses the Lyapunov drift method, which has found widespread applications in queueing systems, Markov decision processes, reinforcement learning, and so on. While the basic
8

---

framework of the drift method is standard, the key challenge lies in constructing the right Lyapunov function with the desired properties, where the difficulty exacerbated by the full heterogeneity of the problem under study. Our construction of such yyapunov function is highly novel, yet still natural. We reiterate that fully heterogeneous, high-dimensional stochastic systems are poorly understood in the existing literature. Our approach opens up the possibility of analyzing the steady-state behavior of such systems through the Lyapunov drift method.
In the remainder of this section, we consider the ID policy, also referred to as the policy Let X denote the system state under it, with the superseript π omitted for brevity. To make this overview more intuitive, here let us assume that X; converges to its steady state Xx in proper sense such that taking expectations in steady state the same as taking time averages. However, note that our formal results do not need this assumption and directly work with time averages. We call a function V Lyapunov/potential function it maps each possible system state to a nonnegative real number.
General framework of the drift method. Here briefly describe the general framework of the drift method when applied to our problem. The goal is to construct a Lyapunov function V such that
(C1) - - R(T, So) S (LE[V(X)) + O(L/ for some constant C1;
(C2) (Drift condition) B [V (X++1) X.] - V(X)) <
for a constant C2.
The drift condition requires that average, the value of V approximately decreases (ignoring the additive O ()) after time step. The drift condition implies a bound on EE [V((Xx ) To this, let X, follow the steady-state distribution, which means X,+1 also follows the steady-state distribution, and take expectations on both sides of the inequality. Then we get 0 R [V(x++)))
[V))))) S
-C5E [V (V,))) + O(VN), which implies E [] E [V(X)) = O(VN). Combining this
with C1) proves the desired O(1/VN) upper bound on the optimality gap.
constructing Lyapunov function. We highlight this challenge by contrasting the homogeneous setting and the heterogeneous setting. In the homogeneous setting, there is only one optimal state distribution, n²" The Lyapunov function in p is defined based the distance between the empirical state distribution across arms and μ². Specifically, it is based on a set of functions (h(X,, D))DE(N) defined
Key challenge:
- m(D)
(13)
where XD(D)= (X)(D)))) denotes within D, the number of arms in each state 8, divided by N: m(mm (D) = |D|/;; and the norm ||-|| is a properly defined norm. The idea is that if all arms in D follow the optimal single-armed policy, the state distribution of each arm in D gets closer to μ², and thus (D) gets closer to m (()) over time.
In the heterogeneous setting, we also want to construct a Lyapunov function (X,, D) to witness the convergence of any set of arms D if they follow the optimal single-armed policies. However, unlike the homogeneous setting, now no longer makes sense to aggregate arm states into an empirical state distribution, since each arm's 's dynamics is distinct. Instead, our Lyapunov function considers 15.e-145 where recall (s, (s) is the indicator that arm i's state is s at time t. A naive first attempt is to construct the Lyapunov function from the pointwise distances, || - #4 || for each arm i, with properly defined norm I--I|- However, the pointwise distances are very noisy: ||X,, ue] could be large even when the state of arm i independently follows the distribution μ for each i, situation when we should view the set of arms as already converged.
Intuitively, to make the Lyapunov function properly reflect the convergence of the set of arms (referred to as "the system" in the rest of the section) following the optimal single-armed policies, we would like it to depend less strongly on the state of each individual arm and focus more on the collective properties of the whole system. Our idea is to project the system state onto a properly selected set of feature vectors, and construct the Lyapunov function based on how far these projections are from the projections of the optimal state distributions (μς )eE Then what features of the system state do we need to determine whether it has converged in proper sense? The first feature we consider is the instantancous reward of the system, EEED (X,..r;), where r E R is the reward function of arm i under म; and recall that the inner product is defined between two vectors whose entries correspond to states in S. We also want to keep track of the l-step ahead expected reward, ΣieD (..Pfrr))

---

is small for each E N. the reward of the system should remain close to that under the optimal state distributions (nz) [[]))[[]]] for long time; conversely, if the state of each arm independently follows pú. each of these features should be small as well. We also consider the E-step ahead expected type-k cost for each & E N and k E [K] as features, defined analogously.
for each E E N.. Intuitively, if DiED ((x)
Combining the above ideas, for any set of arms D, we let the Lyapunov function h(X, D) be the supremum of the differences between X₁ and μ= in all the features directions defined above, under proper weightings:
h(X, D)
max sup SES EEN
Σ (()x,--3))
(14)
iED
where y exp(-1/(22) for r defined in Assumption or corresponds to the type-k cost for some k E [K]] (See Appendix E of [54] for the definition of G).
D each element g G is either g = (r) [e(]
Note that dividing each term by powers of 7y another interesting trick, which induces a negative drift in h( (,, D) under the optimal single-armed policies (See the proof of Lemma in [54
Now with the set of functions (h(X,, D)) DC[N] defined, we generalize the idea of focus sets in
27
to convert (h( x ;, D)) DCIN) into a Lyapunov function V(X.). We prove that V satisfies (CI) and
(C2) using the structure of (h(X,, DC)
Remark 2. The idea for constructing h(X, D) is potentially useful for analyzing other heterogeneous stochastic systems. At a high level. projecting the system state onto set of feature vectors (and their future expectations) can be roughly viewed aggregating system states whose relevant performance metrics remain close for a sufficiently long time. This idea provides a new way to measure the distance between system states in heterogeneous system, and this distance notation enjoys similar properties as that in a homogeneous system, without resorting to symmetry.
Experiments
In this section, we perform two sets of experiments to illustrate the numerical performance of the proposed ID policy for fully heterogeneous WCMDPs.
1.00
Optimality ratio
0.98
0.96
In the first set of experiments, demonstrate the asymptotic optimality the ID policy. We increase the number of arms as N {100, 200, 400, 800, 1600, 3200). Each arm's MDP has
0.94
0.92
Upper bound policy
10 states and 4 actions, with parameters generated uniformly random in a proper sense. The N-armed problem has 4 bud- get constraints, with cost functions also generated randomly. More details are provided in Appendix [..]] We simulate the policy for 2 x 10 time steps over 4 replications for each N. To illustrate the performance more clearly, we measure the optimality ratio, defined as the ratio between the long-run average reward achieved by policy and the LP relaxation upper bound Rtcl Confidence intervals are calculated using the batch means method with batch size of 4000, but they are typically too small to be visible on figures. Figure I shows that the optimality ratio of the policy becomes increasingly close to 1 as N increases.
0.90
1000
2000
3000
Figure 1: Asymptotic optimality of ID) policy.
In the second set of experiments, we compare the ID pol- icy with the ERC policy proposed in 46) As diseussed in Section M only a few prior papers address heterogeneous WCMDPs. Among them, [46] considers the most general setting, but is still limited to a single-budget constraint, state- independent costs, and typed heterogeneity. To make a fair comparison, we evaluate both policies under this special case, while keeping all other settings the same as in the first set of experiments. ID policy turns out to have a slight improvement over ERC policy in some instances, one of which shown in 2 and has comparable performance in others. Impor- tantly, unlike FRC, the ID policy applies far more general classes of WCMDPs.
1.00
Optimality ratio
0.98
0.96
Upper bound
0.94
ERC po
ID policy (this work)
0.92
1000
2000
3000
N
Figure
Figure 2: ID policy vs ERC policy.
10

---

References
[1] S. Allmeier and N. Gast. Mean field and refined mean field approximations for heterogeneous systems: It works! Proc. ACM Meas. Anal. Comput. Syst. 6(1), Feb. 2022.
[2] S. Allmeier and N. Gast. Accuracy of the graphon mean field approximation for interacting particle systems. Stoch. Syst. 15(4):273-29) -90, 2025.
[3] K. E. Avrachenkov and V. S. Borkar. Whittle index based Q-learning for restless bandits with average reward. Automatica, 139:1 10186, 2022.
[4] D. Bertsimas and J. Niño Mora. Conservation laws, extended polymatroids and multiarmed bandit problems; polyhedral approach to indexable systems. Math. Oper. Res., 21(2):557-366 1996.
[5] A. Biswas, G. Aggarwal, P. Varakantham, and M. Tambe. Learning index policies for restless bandits with application to maternal healthcare. In Proc. Int. Jt. Conf. Artificial Intelligence (IJCAI), pages 1467-1468, 2021.
[6] A. Biswas, G. Aggarwal, P. Varakantham, and M. Tambe. Learning index policies for restless bandits with application to maternal healthcare. In Proc. Int. Conf. Autonomous Agents and Multiagent Systems (AAMAS), page 1467-1468, 2021.
[7] C. Boutilier and T. Lu. Budget allocation using weakly coupled, constrained Markov decision processes. In Conf. Uncertainty Artificial Intelligence (UAI), pages 52-61, 2016.
[8] D. B. Brown and J. E. Smith. Index policies and performance bounds for dynamic selection problems. Manage. Sci., 66(7):3029-300 -0500 2020.
[9] D. B. Brown and J. Zhang. Dynamic programs with shared resources and signals: Dynamic fluid policies and asymptotic optimality. Oper. Res., 70(5):3015-30333 2022.
[10] D. B. Brown and J. Zhang. Fluid policies, reoptimization, and performance guarantees in dynamic resource allocation. Oper. Res., 73(2):1029-1044 2025.
[11] R. Durrett. Probability: Theory and Examples. Cambridge University Press, 5 edition, 2019.
[12] J. C. D' Aeth,, S. Ghosal, F. Grimm, D. Haw, F. Koca, K. Lau, H. Liu, S. Moret, D. Rizmie, P. C. Smith, G. Forchini, M. Miraldo, and W. Wiesemann. Optimal hospital care scheduling during the SARS-CoV-2 pandemic. Manage. Sci., 69(10))5923-5547, 2023.
[13] I. El Shar and D. Jiang. Weakly coupled deep Q-networks. Conf. Newral Information Processing Systems (NeurIPS), 36, 2023.
[14] N. Gast, B. Gaujal, and C. Yan. Exponential asymptotic optimality of Whittle index policy. Queueing Syst., 104:107-150, 2023.
[15] N. Gast, B. Gaujal, and C. Yan. Linear program-bused policies for restless bandits: Necessary and sufficient conditions for (exponentially fast) asymptotic optimality. Math. Oper. Res., 49(4): 2468-2491 2024.
[16] N. Gast, B. Gaujal, and C. Yan. Reoptimization nearly solves weakly coupled Markov decision processes. arXiv:2211.01961 [math. OCJ, 2024.
[17] A. Ghosh, D. Nagaraj. M. Jain, and M. Tambe. Indexability is not enough for Whittle: Improved, near-optimal algorithms for restless bandits. In Proc. Int. Conf. Autonomous Agents and Multiagent Systems (AAMAS), pages 1294-1302, 2023.
[18] J. Gittins, K. Glazebrook, and R. Weber. Multi-armed bandit allocation indices. John Wiley & Sons, 2011.
[19] C. Gittins. Bandit processes and dynamic allocation indices. Roy. Stat. Soc. B Met. 41(2): 148-164, 1979.

---

[20] J. C. Gittins and D. M. Jones. A dynamic allocation index for the sequential design of experi- ments. J. Gani, editor, Progress in Statistics, pages 241-266. North-Hollane Amsterdam, 1974.
[21] K. D. Glazebrook, H. M. Mitchell, and P. S. Ansell. Index policies for the maintenance of collection of machines by a set of repairmen. Eur. Oper. Res., 165(():267-284, 2005,
[22] D. Goldsztajn and K. Avrachenkov. Asymptotically optimal policies for weakly coupled Markov decision processes. arXiv:2406.04775 04751 [math. OCJ, 2024.
[23] J. T. Hawkins. A Langrangian decomposition approach to weakly coupled dynamic optimization problems and its applications. PhD thesis, Operations Research Center, Massachusetts Institute of Technology, 2003.
[24] D. J. Hodge and K. D. Glazebrook. On the asymptotic optimality of greedy index heuristics for multi-action restless bandits. Adv. Appl. Probab., 47(3):652-66) 667,, 2015.
[25] Y. Hong, Q. Xie, Y. Chen, and W. Wang. Restless bandits with average reward: Breaking the uniform global attractor assumption. In Conf. Neural Information Processing Systems (NeurIPS), 2023.
[26] Y. Hong, Q. Xie, Y. Chen, and W. Wang. Achieving exponential asymptotic optimality in average-reward restless bandits without global attractor assumption. arXiv:2405.17883 [cs.LG], 2024.
[27] Y. Hong, Q. Xie, Y. Chen, and W. Wang. Unichain and aperiodicity are sufficient for asymptotic optimality of average-reward restless bandits. Math. Oper. Res., 2025. Articles in Advance.
[28] W. Hu and P. Frazier. An asymptotically optimal index policy for finite-horizon restless bandits. arXiv: 1707.00205 [math. OC), 2017.
[29] J. A. Killian, A. Biswas, S. Shah, and M. Tambe. Q-learning Lagrange policies for multi-action restless bandits. In Proc. Ann. ACM SIGKDD Conf. Knowledge Discovery and Data Mining (KDD), pages 871 371-881,2 2021.
[30] J. A. Killian, L. Xu, A. Biswas, and M. Tambe. Restless and uncertain: Robust policies for restless bandits via deep multi-agent reinforcement learning. Conf. Uncertainty in Artificial Intelligence (UAI), pages 990-1000, 2022.
[31] T. Lattimore and C. Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
[32] K. Nakhleh and L.-H. Hou. DeepTOP: Deep threshold-optimal policy for MDPs and RMABs. In Conf. Neural Information Processing Systems (NeurIPS), pages 28734-28777 22746, 2022.
[33] K. Nakhleh, S. Ganji, P.-C. Hsich, I.-H. Hou, and S. Shakkottai. NeurWIN: Neural Whittle index network for restless bandits via deep RL. In Conf. Neural Information Processing Systems (NeurlPS), pages 828-839, 2021.
[34] C. H. Papadimitriou and J. N. Tsitsiklis. The complexity of optimal queuing network control. Math. Oper. Res., 24(2):293-305, 1999.
[35] M. L. Puterman. Markov decision processes: Discrete stochastic dynamic programming. John Wiley & Sons, 2005.
[36] F. Robledo, V. Borkar, U. Ayesta. and K. Avrachenkov. QWI: Q-learning with Whittle index. ACM SIGMETRICS Perform. Evaluation Rev., 450,):47-50, 2022.
[37] N. Tsitsiklis, A short proof of the Gittins index theorem. Ann. Appl. Probab., 4(1):194 199, 1994.
[38] P. Varaiya, J. Walrand, and C. Buyukkoc. Extensions of the multiarmed bandit problem: The discounted case. IEEE Trans. Autom. Control, 30(5):426 439, 1985.
[39] I. M. Verloop. Asymptotically optimal priority policies for indexable and nonindexable restless bandits. Ann. Appl. Probab., -944)99977 2016.
12

---

[40] S. S. Villar. Indexability and optimal index policies for class of reinitialising restless bandits. Probab. Eng. Inf. Sci., 30(1):1-23, 2016.
[41] R. Weber. On the Gittins index for multiarmed bandits. Ann. Appl. Probab. 2(4):1024 1033, 1992.
[42] R. R. Weber and G. Weiss. On an index policy for restless bandits. J. Appl. Probab., 27(3): 637-648, 1990.
[43] Whittle. Multi-armed bandits and the Gittins index. J. Roy. Stat. Soc. B Met., 42(2):143-149, 12 1980.
[44] Whittle. Restless bandits: activity allocation in a changing world. J. Appl. Probab., 25:287 298, 1988.
[45] G. Xiong and J. Li. Finite-time analysis of Whittle index based Q-learning for restless multi- armed bandits with neural network function approximation. Conf. Neural Information Processing Systems (NeurIPS), pages
2023.
[46] G. Xiong, S. Wang, and J. Li. Learning infinite-horizon average- reward restless multi-action bandits via index awareness. In Conf. Neural Information Processing Systems (NeurIPS), pages 17911-17925, 2022.
[47] C. Yan. An optimal-contro approach to aefinite-horizon restless bandits: Achieving asymptotic optimality with minimal assumptions. In Proc. IEEE Conf. Decision and Control (CDC), pages 6665 (675,,667,,00 2024.
[48] Yu, Y. Xu, and L.. Tong. Deadline scheduling as restless bandits. IEEE Trans. Autom, Control, 2363):2333-3388 2018.
[49] G. Zayas-Cabán, S. Jasin, and G. Wang. An asymptotically optimal heuristic for general nonstationary finite-horizon restless multi-armed, multi-action bandits. Adv. Appl. Probab., 51 (3):745-772, 2019.
[50] Zhang. Leveraging nondegeneracy in dynamic resource allocation. Available at SSRN, 2024.
[51] X. Zhang and P. Frazier. Restless bandits with many arms: Beating the central limit theorem. arXiv:2107.1 1191 [math. OC), July 2021.
[52] X. Zhang and P. I. Frazier. Near-optimality for infinite-horizon restless bandits with many arms. arXiv:2203. 15853 [cs.LG), 2022.
[53] X. Zhang, Y. Hong, and W. Wang. Projection- Lyapunov method for fully heteroge- ncous ccakly-coupled MDPs. GitHub repository, wcmdp- fully- 2025.
[54] X. Zhang, Y. Hong, and W. Wang. Projection-based Lyapunov method for fully heterogeneous weakly-coupled MDPs. arXiv:2502.0607226 [cs. 2025.
[55] Z. Zhao and D. Mukherjee. Optimal rate-matrix pruning for heterogeneous systems. ACM SICMETRICS Perform. Evaluation Rev., 51(4):26-27, 2024.
[56] Z. Zhao, D. Mukherjee, and R. Wu. Exploiting data locality to improve performance of heterogeneous server clusters. Stoch. Syst., 14(3):229-77,, 2024.
[57] J. Zhou, S. Mao, G. Yang, B. Tang, Q. Xic, L. Lin, X. Wang, and D. Wang. RL-MPCA: A reinforcement learning based multi-phase computation allocation approach for recommender systems. In Proc. ACM Web Conf., pages 3214-3224, 2023.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The main contribution claimed the abstract and the introduction is an
asymptotic optimality theorem; it corresponds Theorem in the main results section (Section 4).
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: In Section after stating Theorem we pointed out that we did not attempt optimize the optimality gap bound's dependence any parameters other than N.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
14

---

Answer: [Yes]
Justification: We have stated our assumption (Assumption 1) Section right before the main theorem (Theorem 1); we have added cross-reference to the assumption in the theorem's 's statement. The proofs are given in the appendix the arXiv version, and we have referred to the corresponding sections in the arXiv version in the paper.
Guidelines:
The answer NA means that the paper does not include theoretical results. the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: In Section 5 and Appendix B, we have discussed in detail the method of generating random instances, the simulation setting, and the baseline policy.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
15

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [Yes]
Justification:
We have cited the link to our GitHub where the simulation code available.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips) cc/
public http:l//gguueee//eeeeeeeeeeeeeee htte:/CoeSSSuona ssissssiisss olliyl for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (ht
//nips httccc//puuct pttp/public/// hwcpc//uiiiesseeeeee CodeSubma as ciooooooiiiy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: In Section 5 and Appendix B, have diseussed in detail the method of generating random instances, the simulation setting, and the baseline policy. We have also cited the link to the GitHub where the code is available.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification: We have plotted the confidence intervals in the figures, which turn out to be negligibly small.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoo bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
16

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: Our experiments are small-scaled and can be completed on standard PC (6-Core Intel Core i7) within one day.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics pettts://neeriiiii http://ss....obblootttttt/teeeee
Answer: [Yes]
Justification: Since this is theoretical paper, we believe that there is potential harms caused by our research process, and our result does not have negative social impact and harmful consequences.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our result theoretical and we see no direct way that it can be linked to technology with negative social impacts.
17

---

Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considcrations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning conrectly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper does not pose such risks, since it is mainly theoretical and only has small-scale simulation experiments.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: Our paper is mainly mathematical with only small-scale experiments. It does not use existing assets.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
18

---

The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithhee com/ çat aseas has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We have uploaded our simulation code to GitHub.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This is theory paper and does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for rescarch with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: This is theory paper and does not involve crowdsourcing or research with human subjects.
Guidelines:
19

---

The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
The core method development of the paper does not involve LLM.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy
2025/
LLM for what should should not be described.
20

---

A Detailed review on related work
In this section, we provide a more detailed, though still non-exhaustive, review of the literature. We mainly focus on theoretical work with formal performance guarantees, leaving out the extensive body of work with empirical results. We begin by surveying papers with the same reward criterion as ours, i.e., infinite-horizon average-reward criterion. In this setting, we first review existing work on restless bandits (RBs), which is an extensively studied special case of WCMDPs. We then give a more detailed review of existing results on WCMDPs. Next, we turn to work that considers other reward criteria: the finite-horizon total-rewar criterion and the infinite-horizon discounted- criterion. Finally, we briefly mention other problems that are related to WCMDPs.
Infinite-horizon average-reward RBs. For the homogeneous arm setting, the first asymptotic optimality result for average-reward homogeneous RBs is established by Weber and Weiss :2:: they show that the Whittle index policy E4] achieves an o(1) optimality gap as the number of arms N goes to infinity. There are three key assumptions in 42]; indexability, the global attractor property. and the aperiodic-unichain condition. These assumptions have been gradually relaxed in the subsequent papers. In particular, [39 proposes a class of priority policies based on an LP relaxation. This class of policies, later referred to as the LP- Prrriiity policies. generalizes the Whittle index policy. Each LP- LP-Priority policy achieves an o(1) optimality gap without requiring indexability. The work [25] is the first one that breaks the global attractor property assumption. The authors propose a policy name Follow-the Dollow-the-Virtul-AAdee Virtual-Advice (FTVA), which achieves an O(1/ ((1/VN) optimality gap under an assumption named the Synchronization Assumption; there exist problem instances that satisfy the Synchronization Assumption but do not satisfy the global attractor property. Later work [27] further relaxes the conditions and only requires the aperiodic-unicle optimality gap. More recently, Yan 47 proposes the align-and-steer policy, which further weakens the aperiodic-umichain condition and achieves an o(1) optimality gap.
condition to achieve an O(1/VN) /N)
Parallel to relaxing the assumptions for asymptotic optimality, another line of work has focused on improving the optimality gap beyond O(I/VN) under slightly stronger assumptions [4]
15
26
Specifically, Gast et al. [4] show that the Whittle index policy has an ((exp(-cVV) optimality gap for some constant e >> O. In addition to indexability and the operiodic-unichate condition, 14 also
requires a stronger version of the global attractor property named Uniform Global Attractor Property (UGAP), and condition called non-singularity. Subsequently, Gast et al. (15] show that LP-Priority policies achieve (ccxp(-ca (ccN) optimality gaps assuming the serriodic-unichale condition, UGAP, and non-degenerate condition that is equivalent to non-singularity. More recently, Hong et al. 26 propose a two-set policy that also achieves an ((exp(-cN) optimality gap while replacing UGAP of [55
with much weaker condition named local stability.
Among the aforementioned work, 39 and 25 have addressed the heterogeneous arm setting. The setting studied in B9 is the typed heterogencous setting, where the N arms are divided into constant number of types as N + co. The paper (25) includes an extension to the fully heterogeneous setting. In particular, the proposed FTVA policy generalizes to the fully heterogencous setting and leads to an optimality gap of 0 (Twwss//N /VN,, where 7aync is the maximum of quantity called the synchronization time across all arms. Therefore, for this result to yield asymptotic optimality, there needs to be a further assumption that min = o(VN). We re-phasasize that the FTVA policy does not generalize to WCMDPs. The main reason is that FTVA heavily relies on the fact that RB only constrains the number of pulls, while a WCMDP has budget constraints on cost functions each depending on both the state and action of an arm.
Infinite-horizon average-reward WCMDPs. Work on average-reward WCMDPs remains rel- atively scarce, and to our knowledge, fully heterogeneous WCMDPs have yet to be addressed. Compared to RBs, WCMDP allows multiple actions for each arm and multiple cost constraints, where each cost function is function of both the state and the action of an arm. The line of research (2 24 Ky 46 has generalized the action space and cost model of RBs to WCMDPs, and some of them allow for typed heterogeneity. In particular, Hodge and Glazebrook [4! generalize the Whittle index policy to homogeneous WCMDPs with a single constraint and multiple actions, where each action represents different activation level and has a different cost. Verloop (39 extends the I.P-Priority policies to typed heterogeneous WCMDPs with single constraint and multiple actions, but requires each action to have the same cost. Then Xiong et al. 46 propose another index policy
21

---

for typed heterogeneous WCMDPs with a single constraint, and allow each action to have a different o(1) optimality gaps have been proved under a similar set of assumptions as in most restless bandit papers, i.e., aperiodic-unichan
cost. In the three papers above 24 39 46
(or imrducibility) condition, global attractor property, and a generalized indexability condition if the policy is Whittle index. Finally, Goldsztajn and Avrachenkov 22
consider homogeneous WCMDPs with multiple actions and multiple cost constraints with general cost functions, and propose a class of policies with ((1) optimality gaps under a weaker-than-standee aperiodic-unichain condition.
Finite-horizon total-reward RBs and WCMDPs. Next, we review the asymptotic optimality results for mnite-horizon total-reward RBs and WCMDPs. The finite-horizon setting better under- stood than the average-reward setting, partly because the analysis in the finite horizon is not hindered by the technical conditions arising in average-reward MDPs, such as the unichain condition and the global attractor property. On the other hand, computing asymptotically optimal policies for the finite-horizon setting is more complicated, requiring a careful optimization of the transient sample paths.
Hu and Frazier propose the first usymptotically optimal policy for finite-horizon homogeneous RBs, which achieves an o(1) optimality gap without any assumptions Since then, researchers have established asymptotic optimality in more general settings [8 TO
10 Among these papers, the most general setting is addressed by Brown and Zhang [10. where the authors consider
fully heterogeneous WCMDPs; they obtain O(1/ (N) optimality gaps for a naive fluid policy and a reoptimization- based fluid policy, among few other results to be reviewed in the next paragraphs. Notably, there is also further generalization of fully heterogeneous WCMDPs, which involves an exogenous state that affects all arms' transitions, rewards, and constraints; Brown and Zhang O propose this setting, where they achieve an O(1/vN) optimality gap using a dynamic fluid policy.
Another line of work has improved the optimality gap beyond the order O(1/VN) by making an additional assumption called non-degeneracy. Specifically, Zhang and Frazier [5]] establish an (11/N) optimality gap non-degenerate homogeneous RBs. Gast et al. [IS then propose a different policy for the same setting that improves the optimality gap to ((exp(-cN)
Later, Gast et al. [16] and Brown and Zhang [TO] establish (11/N) optimality gaps for homogeneous and typed heterogeneous WCMDPs, respectively. assuming non-degeneracy. More recently, Zhang 50 proposes a policy for fully heterogeneous WCMDPs; the optimality gap bound of the policy interpolates between O11/ /N) and O(1/N) as the degree of non-degeneracy varies, unifying the performance bounds in the degenerate and non-degenerate cases.
Despite the generality of the settings and the fast diminishing rate of the optimality gaps as N + oc, most of the optimality gaps in the finite-horizon setting depend super-linearly on the time horizon, average-reward setting. There are two exceptions. [10 16), which achieve optimality gaps that depend linearly on the time horizon under some special conditions: [10] requires all entries of the transition kernels to be bounded away from zero; [[6] assumes an ergodicity property, which requires two arms in any different states to synchronize in a fixed number of steps under any sequence of actions with a positive probability. However, without these conditions, the optimality gaps in [10, [6] depend quadratically on the time horizon. Apart from having distinct optimality gap bounds, all existing algorithms in the finite-horizon setting need to (sometimes repeatedly) solve LPs whose number of variables scales with the time horizon, so they cannot be directly adapted to the
so they do not earry over to the
average-reward setting.
Infinite-horizon discounted-reward RBs and WCMDPs. Asymptotic optimality has also been es- tablished for RBs and WCMDPs under the fhiiite-horizon discounted-rewart criterion. In particular, Brown and Smith M establish an O ((Xloga(y)) optimality gap for fully heterogeneous WCMDPs when E (1/2, 1). Subsequently, Ghosh et al. [17. Zhang and Frazier (52) obtain 0(1/ (N) optimality gaps for homogeneous and typed heterogeneous RBs, and Brown and Zhang II establish the same order of optimality gap for fully heterogeneous WCMDPs. Similar to the finite-horizon setting, most of these optimality gaps depend siper-linearly on the effective time horizon 1/(1 7)
2 'Here, we measure the optimality gap terms of the reward per arm, to consistent with our convention.
However, in the papers on the finite-horizon total-reward setting. it is also common to measure the optimality gap in terms of the total reward of all arms, which differs from ours by factor of N. We also adopt the same convention when reviewing the papers on the infinite-horizon discounted- reward setting.
22

---

unless special conditions hold [TO so they do not carry over to the infinite-horizon horizon average- reward setting. The policies here also require solving LPs whose complexities scale with the effective time horizon.
Restful bandits, stochastic multi-armed bandits. A special case RB is the restful bandit (also referred to nonrestless bandits, rested bandits, or Markovian bandits), where an arm't 's state does not change it is not pulled. The restful bandit problem has been widely studied, where the celebrated Gittins index policy is proven to be optimal 4 [9 20 37 38
41 33 We refer the readers to [8] for a comprehensive review of Gittins index and restful bandits. Another related topic is the stochastic multi-armed bandit (MAB) problem, which has been extensively studied;
the book [3] for comprehensive overview. The key distinction between MABs and RBs that arms are stateless in MABs, but stateful in RBs. Consequently, MAB becomes trivial with known model parameters, whereas RB is still non-trivial.
B Experimental details
In this appendix, we provide details of the two WCMDP instances considered in Section 5 and the definition of the baseline policy, the ERC policy from Hd. The complete code for these experiments available on GitHub [53), and all results can be reproduced within 24 hours standard PC (e.g.. 6-Core Intel Core 17).
B.1 WCMDP instance generation
S 10, |A] 4, K 4. For each [N], 8 E 8, and a E A, 0) = O, and r; (s, a) is independently sampled from the uniform distribution over [0, 1] for each + O; P, (s,, a, (. independently sampled from the uniform distribution over the probability simplex. As for the cost function, for each i E [N]. E S, E A, and & E [K], we have (s,i(s, 0) and (s, a) is independently sampled from the uniform distribution over [0, for each a 7 O. For each k E [K], og is uniformly sampled from (0.05, 0.1, 0.., 0.45). i.e., the uniform distribution over integer multiples of 0.05 in the interval (0, 0.5).
Details of the WCMDP instance 1 (In Figure 1.
This instance is typed heterogencous with 10 types, with equal fraction of arms each type. Each has [3] 10 states, A actions. For each type, the reward function and transition kernel are generated in the same way as each arm in ithe first instance. The budget is also sampled from the same distribution the first instance. There is single budget constraint. The cost function depends only on the action, consistent with the setting in 46 the cost of each of action
Details of the WCMDP instance (In Figure 2).
sampled from the uniform distribution over [0, 1].
B.2 Definition of ERC policy
The ERC policy 46 solves the same LP in ( to define the single-armed policies #ं (a]s) as in 7 At each time step, the policy computes index for each arm-state pair (i, E [N] x S:
Z(i,s) Σ (cls))r((s..) GE
It then iterates through the arms in descending order of these indices. For each arm, it samples action a ~ (- |)) and applies it only the budget sufficient. If not, defaults to action
23


Reviews:
[{"review_id": "lJaZEiB0Kk", "reviewer": "Reviewer_aSGL", "summary": "The paper considers a class of problems known as weakly coupled Markov Decision Processes. In this framework, the linkage between individual components, or arms, is through joint cost constraints, while each arm operates as its own independent MDP. The objective is to solve for the optimal policy for the entire system, keeping these shared constraints in mind. Typically, the state space for the entire system is exponential in the number of arms, making the problem difficult to solve directly. To approach this, the paper considers the Linear Programming relaxation of the original MDP. The best policy obtained from this LP relaxation provides an upper bound on performance, since the cost constraint is relaxed to only require satisfying a time-averaged version of the constraint. The authors then propose an \"ID reassignment\" based policy to determine the optimal arm-pulling strategy, such that the optimal stationary distribution obtained from the LP optimization problem is eventually tracked. They analyze the regret associated with the LP optimal solution, which serves as an upper bound on the actual regret with respect to the original MDP. The rest of the paper is dedicated to proving that the ID assignment indeed tracks the LP optimal policy in an asymptotic sense. The technical novelty lies in the proof technique, where the a unique Lyapunov function is synthesized for this fully heterogenous setting.", "questions": "1. In equation 8, is there a reason for choosing half the budget per cost constraint as the limit to determine the active constraints? Or is it an arbitrary choice?\n2. In equation 7, is there any intuition beyond setting the policy to be uniform in transient states?\n3. Does line 259 imply that as the arms with lower indices approach their stationary values, the cost constraints are satisfied in a sense that lets more arms follow their LP-optimal policies?\n4. It will help to include the intuition behind Algorithm 1 in the main body of the paper since this is the main algorithmic contribution of the paper. \n5. Is there any intuition behind choosing the cost and reward vectors as the feature vectors?\n6. Is the regret quantified with respect to the best stationary optimal policies or best optimal policies in a wider class of policies (as initially pointed at)?\n\nMinor comment: In the beginning the authors mention that lim inf and lim sup of the average cost are the same in the finite state action setting. However, this is true subject to certain constraints on the Markov chain induced by the policy. Unichain and aperiodicity are sufficient (as assumed later) but this assumption needs to be made clearer earlier on.", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1.  The paper's primary claim is that it provides the first asymptotic optimality result for fully heterogeneous average-reward WCMDPs. This is a significant step beyond existing work, which has focused on homogeneous or simpler typed heterogeneous settings.\n2. The design of a novel Lyapunov function is a theoretical contribution which can be leveraged as a tool to analyze other heterogeneous systems. \n\nWeaknesses:\n\n1. A more complete work would characterize the performance of the ID-reassignment policy in a finite time sense. The paper presents the asymptotic performance where the performance is characterized over the infinite time horizon. \n2. As the number of arms $N$ tends to infinity, the assumption on the finiteness of mixing time may fall through.\n3. It is unclear as to what the approach should be if the LP relaxation has multiple optimal solutions. \n4. $C_{ID}$ seems to scale really badly with the problem parameters, making the result vacuous in large complex settings.", "was_revised": true, "final_justification": "The authors have addressed most of my concerns satisfactorily and hence, I am increasing my score.", "rebuttal": "> Weakness 1: did not characterize the finite-time performance\n> \n\nThanks for bringing up this point. In fact, our proofs of Theorem 1 can be easily adapted to give the following finite-time performance bound: \n\n$$\nR^*(N, \\mathbf{S}\\_0) - \\frac{1}{T} \\sum\\_{t=0}^{T-1} (\\text{expected reward per arm at time $t$}) \\leq \\frac{C\\_{\\text{ID}}}{\\sqrt{N}} + \\frac{2r\\_{\\max} + L\\_h}{\\rho\\_V T}\n$$\n\nTo prove this, we will only need to slightly modify Lemma 4 and 5. Note that the Lemma 5 actually gives a finite-time bound on the expectation of the Lyapunov function $V(\\mathbf{X}\\_t)$ (The equation above (82)), and Lemma 4 can be modified to show that:\n\n$$\nR^*(N, \\mathbf{S}\\_0) - \\frac{1}{T} \\sum\\_{t=0}^{T-1} (\\text{expected reward per arm at time $t$}) \\leq \\left(1 + \\frac{2r\\_{\\max}}{L\\_h}\\right) \\frac{1}{T N}\\sum\\_{t=0}^{T-1} \\mathbb{E}[V(\\mathbf{X}\\_t)] + \\frac{2r\\_{\\max}K\\_{\\text{conf}}}{\\sqrt{N}}\n$$\n\nCombining these two inequalities would give the finite-time performance bound that we claimed at the beginning. \n\nWe will add this result and its derivation to the paper. \n\n> Weakness 2: as $N\\to\\infty$, the assumption on the finiteness of mixing time may fall through.\n> \n\nOur theorem 1 currently assumes the existence of a constant-order upper bound $\\tau$ on the mixing times of all arms (Assumption 1). While this assumption might sound strong, there are some straightforward ways to relax this assumption:\n\n- First, if an $O(1/\\sqrt{N})$ fraction of arms have unbounded mixing times, we can modify the algorithm to ignore these arms, which only causes $O(1/\\sqrt{N})$ degradations in the optimality gap and does not affect the order of our bounds. Moreover, if we only aim for asymptotic optimality, i.e. $o(1)$ optimality gap, we can have at most $o(1)$ fraction of arms with unbounded mixing times.\n- Second, while we mainly focus on the scaling of $N$, Theorem 1 remains true even if the mixing time $\\tau$ scales up with $N$. In that case, Theorem 1 implies that the optimality gap of our policy is at most $O(\\tau^4 / \\sqrt{N})$  (see the second paragraph below Theorem 1), so asymptotically optimality is still achieved when $\\tau = o(N^{1/8})$.\n\nWe could comment on these two relaxations of Assumption 1 in the paper. \n\n> Weakness 3: It is unclear as to what the approach should be if the LP relaxation has multiple optimal solutions.\n> \n\nWe would like to point out that our policy and proofs do not rely on the uniqueness of the optimal solution to the LP relaxation. In the presence of multiple optimal solutions, any of them satisfying Assumption 1 can be used to define an instance of the ID policy, and Theorem 1 applies to all such instances. We can clarify this point in Section 3. \n\n> Weakness 4: $C\\_{\\text{ID}}$ seems to scale badly, making the result vacuous in large complex settings\n> \n\nWe acknowledge that our analysis focuses on the scaling with $N$ and does not aim to optimize the dependence of the optimality gap bound on other parameters. \n\nThat said, we would like to highlight an interesting fact: $C\\_{\\text{ID}}$ does not explicitly depend on the sizes of the state or action spaces. This implies that our bound in Theorem 1 could still be informative for some WCMDP instances with large state-action spaces and many arms, provided that the relevant quantities (such as the mixing time bound $\\tau$) remain moderate. \n\n> Question 1: In equation 8, is there a reason for choosing half the budget per cost constraint as the limit to determine the active constraints? Or is it an arbitrary choice?\n> \n\nThanks for the question. This choice is arbitrary; any constant fraction strictly between $0$ and $1$ would yield the same $O(1/\\sqrt{N})$ optimality gap. We will clarify this point in our revision. \n\n> Question 2: In equation 7, is there any intuition beyond setting the policy to be uniform in transient states?\n> \n\nThanks for the question. To clarify, there is no unique “correct” way to define the single‑armed policy $\\bar{\\pi}\\_{i}^{\\ast}$ in transient states. For the purpose of proving Theorem 1, any definition of the transient behavior of $\\bar{\\pi}\\_{i}^{\\ast}$ suffices, provided it ensures the induced Markov chain is an aperiodic unichain with mixing time bounded by $\\tau$ (Assumption 1). However, the specific choice may affect the required strength of Assumption 1.\n\nThe rationale behind our definition of $\\bar{\\pi}\\_{i}^{\\ast}$ is that it maximizes the \"connectivity\" of the induced chain. Specifically, if any definition of $\\bar{\\pi}\\_{i}^{\\ast}$ in transient states induces a unichain for arm $i$, then this uniform‑action definition also induces a unichain, since it assigns positive probability to every action.\n\n\n\n> Question 3: Does line 259 imply that as the arms with lower indices approach their stationary values, the cost constraints are satisfied in a sense that lets more arms follow their LP-optimal policies?\n> \n\nYour understanding is accurate. We will make this point more explicitly in our revision. \n\n> Question 4: It will help to include the intuition behind Algorithm 1 in the main body of the paper.\n> \n\nWe thank the reviewer for the suggestions. We have provided some intuitions on Lines 263—269, but we could also move up some content in Appendix C to the main body. \n\n> Question 5: Is there any intuition behind choosing the cost and reward vectors as the feature vectors?\n> \n\nWe design the feature vectors to preserve sufficient information of the system state $\\mathbf{X}\\_t$ so that, after projection, we can still determine (i) whether a subset of arms can follow the optimal single-armed policies, and (ii) the instantaneous reward of the subset of arms if they follow the optimal single-armed policies. The first goal requires us to include the cost vector so that we can check if the constraints are satisfied; the latter requires us to include the reward vector. \n\n> Question 6: Is the regret quantified with respect to the best stationary optimal policies or best optimal policies in a wider class of policies (as initially pointed at)?\n> \n\nThanks for pointing out this confusion. We would like to clarify that these two ways of quantifying the regret are equivalent in our setting. Note that the WCMDP problem is an MDP with finite state and action spaces, so, by Theorem 9.1.8 of [35], there exists a stationary Markov policy that is optimal within the class of history-dependent randomized policies (the widest possible class). We will revise Lines 183-185 to clarify this. \n\n> Minor comment: In the beginning the authors mention that lim inf and lim sup of the average cost are the same in the finite state action setting. However, this is true subject to certain constraints on the Markov chain induced by the policy. Unichain and aperiodicity are sufficient (as assumed later) but this assumption needs to be made clearer earlier on.\n> \n\nWe would like to clarify that we do not need the additional assumptions that the reviewer mentions. There are about two places where we mention that lim inf equals lim sup, which we clarify one-by-one:\n\n- In the paragraph below (3), we are only arguing that the *optimal* limsup average reward equals the *optimal* liminf average reward, which always hold in the finite state-action setting, by Proposition 9.1.6 of [35] cited in this paragraph.\n- At the top of Page 5, we argue that the limsup average reward equals the liminf average reward for a finite-state Markov chain. Note that we fix the initial state $\\mathbf{S}\\_0$ and consider the long-run average of the expectation, so we do not really need unichain or aperiodicity."}, {"review_id": "pTYuiDNX9w", "reviewer": "Reviewer_NG7h", "summary": "This paper studies the problem of fully heterogeneous, average-reward, budget-constrained weakly-coupled MDP (WCMDP) under the setting of planning (transition kernels and reward functions are known). For the first time, they design the algorithm of $\\textit{ID policy with reassignment}$ and prove it achieves an $O(\\sqrt{N})$ optimality gap as the number of arms $N$ grows to infinity. The authors novelly design a clean projection-based Lyapunov function analysis that bypasses the need for symmetry or state aggregation. But this paper comes without any experiments.", "questions": "please refer to weakness", "limitations": "I didn't find the discussion about the limitations and societal impact. Since this work is theoretical in nature, it is acceptable for that.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strength:\n1. The presentation is good. Writing is easy to follow. \n2. For the first time, this paper closes the gap and provides the first asymptotic optimality result for average-reward, hard-constrained WCMDP. Also this paper is technically solid.\n3. Technically, they provide a novel construction of a Lyapunov function based on projected features across heterogeneous arms.\n\nWeakness:\n1. I am not convinced by the problem setting's practicality. The average reward setting is not widely used since it is not easy to learn, and not as stable as the discounted reward setting. In this case, the authors should provide at least a synthetic toy case. Second, the hard instantaneous cost constraint is fixed for each time. It might be more practical to consider the cumulated cost for a period of time? \n2. It will be better to provide more comparisons on the techniques with the discounted WCMDP literature, since the authors mentioned the optimality result is provided in that case.", "was_revised": true, "final_justification": "I think this work is strong in its theoretical contribution, providing a novel technique. So I will keep my positive rating.", "rebuttal": "> Weakness 1.1: I am not convinced by the problem setting's practicality. The average reward setting is not widely used since it is not easy to learn, and not as stable as the discounted reward setting.  In this case, the authors should provide at least a synthetic toy case.\n> \n\nThanks for bringing up this point. While learning in average-reward MDPs is harder than in discounted-reward MDPs, it is an active research area and increasingly efficient learning algorithms have been proposed. See, for example, the following paper for a review of the recent developments in learning average-reward MDPs: \n\n    Lee, Jongmin, Mario Bravo, and Roberto Cominetti. \"Near-optimal sample complexity for MDPs via anchoring.\" *arXiv preprint arXiv:2502.04477* (2025).\n\nFor weakly-coupled MDPs, the policy that we propose can serve as a good baseline policy.  We are currently working on leveraging such a near-optimal planning policy to develop learning algorithms with a lower sample complexity.\n\nAs for the experiments, we have performed simulations on some randomly-generated WCMDP instances, whose setup and data can be found in our reply to the Reviewer oixq. Due to the limited time of the rebuttal period, we have only performed simulations on a small number of instances. We could add a few more simulations and include the results in the final version if our paper gets accepted. \n\n> Weakness 1.2: Second, the hard instantaneous cost constraint is fixed for each time. It might be more practical to consider the cumulated cost for a period of time?\n> \n\nWe agree that the cumulated cost is an interesting setting.  That said, the hard instantaneous cost constraint is a natural model for allocating perishable resources, such the computing time of the servers, the availability of nursing personnels, the network bandwidth, etc. \n\n> Weakness 2: It will be better to provide more comparisons on the techniques with the discounted WCMDP literature, since the authors mentioned the optimality result is provided in that case.\n> \n\nThanks for the suggestion. We have briefly discussed the difference between the existing results for discounted-reward WCMDPs and average-reward WCMDPs at the end of Appendix B. We could expand on that to comment more on the techniques. \n\nAt a high-level, the main challenge in the discounted setting is achieving *transient* optimality. To show that a certain policy achieves asymptotic optimality, one needs to show that the stochastic sample paths under the policy concentrate around an “optimal” deterministic path [See, e.g., 17, 52]. The concentration of sample paths usually follow from the concentration of *per-step* transitions, when the number of arms is large. \n\nIn contrast, in the averge-reward setting, the challenge mainly lies in understanding the long-term behavior of the system, and one needs to show that the steady-state distribution of the system state has some concentration properties. Such concentration properties do directly follow from the concentration of per-step transitions; intuitively, some global stability is needed to prevent the stochastic noise from accumulating over the infinite time. Establishing such global stability was a long-standing challenge resolved only recently [22,25,26,47], and a natural technique is to use Lyapunov functions."}, {"review_id": "BHmL2HszCA", "reviewer": "Reviewer_oixq", "summary": "This paper considers the setting of weakly coupled MDPs (WCMDPs), which consist of $N$ arms, each representing a distinct individual MDP. The authors focus on the fully heterogeneous case, where each underlying MDP is governed by a different model. Considering all the models of the individual arms to be fully known, the objective is to maximize the overall reward while satisfying global constraints related to $K$ different cost functions. To this end, the authors propose a policy named \"ID policy with reassignment\", which operates in two phases. The first is the pre-processing phase: for each arm, compute the optimal single-arm policy that prescribes the ideal action the agent should take in each individual MDP. The second is the real-time phase: each MDP is assigned actions from its ideal policy as much as possible without violating the cost constraints, otherwise a neutral policy is applied. By leveraging a Lyapunov function specifically designed for this setting, the authors prove that the proposed policy achieves an asymptotic sub-optimality gap of order $\\mathcal{O}(1/\\sqrt{N})$, where $N$ is the number of arms.", "questions": "1. Do you have any insights on how results extend to the case in which we consider continuous sub-MDPs?\n2. What are the main technical challenges in considering learning policies in unknown sub-MDPs? For instance, is would be possible to apply concepts by constrained reinforcement learning?\n3. In the paragraph at lines 147--158, is it really necessary to indicate the policy $\\pi$ when considering the vectors of MDPs states and actions?\n4. Concerning the definition of $R^*(N,\\boldsymbol{S}_{0})$, is it the optimal reward only or is it accounting for constraint satisfaction too?\n5. In Lemma 1, what happens to constraint violation when employing the solution of the relaxed problem?", "limitations": "The authors discuss widely the limitations of their work throughout the whole manuscript.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths**  \nThe main strength of the paper lies in the quality of the manuscript. The paper is very well written; the authors take the time to discuss every introduced concept, the manuscript is self-contained, the related work is thoroughly reviewed, the notation is clear, and every symbol used is formally defined. Moreover, the authors consider a setting that reflects real-world scenarios, and the proposed ideas are intuitive and well presented. The paper appears to be theoretically sound, and the methodological analysis seems novel (at least to the best of my knowledge, although this is not precisely my area of expertise).\n\n**Weaknesses**  \nThe main weakness I found in the paper is that the authors assume full knowledge of all the tabular MDPs. This assumption makes the problem significantly easier, as it allows the proposed policy to solve each MDP exactly. Additionally, I believe the setting would benefit (and become more challenging) by introducing a finite budget for acting in the MDPs. The paper would also gain from a more detailed discussion of the motivational examples, which are just listed; elaborating on them could help the reader better appreciate the relevance of the proposed setting. That being said, I do not believe this is strictly a reinforcement learning paper, as it does not involve learning a policy through interaction with the environment(s). Furthermore, I would have appreciated at least a toy simulation, to provide a practical illustration of the theoretical results.", "was_revised": true, "final_justification": "I believe this paper provides valuable contributions to the field. \nAfter the rebuttal, all my concerns and doubts on some aspects of the work were resolved, for instance the ones regarding extension to learning and continuous settings, the ones related to the concept of optimality, and the ones related to the motivations for employing a tabular planning scenario. Finally, the authors conducted a toy simulation, which is in line with the theoretical nature of the proposed work, that I think to enforce the presented results.", "rebuttal": "> Weakness: The main weakness I found in the paper is that the authors assume full knowledge of all the tabular MDPs. This assumption makes the problem significantly easier, as it allows the proposed policy to solve each MDP exactly ...  I do not believe this is strictly a reinforcement learning paper, as it does not involve learning a policy through interaction with the environment(s).\n> \n\nWe thank the reviewer for bringing up this point, as we also found the learning aspect of this problem interesting.  That said, we would like to argue that the planning setting itself with known parameters is an interesting setting for the two reasons below, and it needs to be better understood before we move onto the learning setting.  \n\nFirst, the planning setting of WCMDPs and restless bandits has broad applications, especially in operations research, and there has been strong interest in developing better planning algorithms for more general settings.  We’d like to refer to the following survey for a comprehensive overview, and the references in our paper for this continued effort.\n\n    José Niño-Mora. Markovian restless bandits and index policies: A review. *Mathematics*, 11(7), 2023. \n\nFurthermore, planning algorithms can play an instrumental role for learning a policy.  For WCMDPs, if it is treated as a generic tabular MDP, then the sample complexity will be at least the state space size, which is exponential in N.  A more tractable approach could be estimate model parameters first, and then apply a good planning algorithm with the estimated parameters.  Such a model-based approach has been studied before for other RL problems.  This approach is promising for WCMDPs with the ID policy and our results in this paper, but it is non-trivial to establish rigorous guarantees and sample complexity bounds.  We will discuss the challenges in our response to Question 2.\n\n> Weakness (continued): Furthermore, I would have appreciated at least a toy simulation, to provide a practical illustration of the theoretical results.\n> \n> \n> \n\nWe have performed simulation experiments on some random WCMDP instances. Below we display the simulation results on two representative instances. Each WCMDP instance is fully heterogeneous, whose arms are MDPs with independently generated parameters. For each arm, each row of the transition kernel is uniformly sampled from the probability simplex, each entry of the reward function and cost function is uniformly sampled from $[0, 1]$, and each budget parameter $\\alpha_k$ is also uniformly sampled from $[0,1]$. \n\nThe first instance has a single cost constraint, with $|\\mathbb{S}| = 10$, $|\\mathbb{A}| = 4$,. We compare the performance of our policy with the performance of a policy name ERC (“Expected Reward and pull arms constrained by activation Cost” ) [46]. The ERC policy is designed for the typed heterogeneous WCMDPs with a single cost constraint, but we can apply it to fully heterogeneous WCMDPs by regarding each arm as having a different type. We evaluate the “optimality ratio” of the policies, which is defined as the ratio between the long-run average reward $R(\\pi, \\mathbf{S}_0)$ and the optimal value of the LP relaxation $R^{\\text{rel}}_N$. \n\nWe simulate each of the two policies for $10^4$ time steps and $4$ replications for each $N\\in \\\\{100,200,...1000\\\\}$. The result is displayed in the next table, where the confidence interval is calculated using the batch means method. We can see that the performance of these two policies are comparable, with the ID policy being slightly better.  \n\n| N | 100 | 200 | 300 | 400 | 500 | 600 | 700 | 800 | 900 | 1000 |\n| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |\n| ID policy (our work) | 0.9600 | 0.9732 | 0.9788 | 0.9814 | 0.9839 | 0.9855 | 0.9865 | 0.9874 | 0.9881 | 0.9887 |\n| Confidence interval width | 0.0011 | 0.0006 | 0.0005 | 0.0005 | 0.0003 | 0.0004 | 0.0003 | 0.0002 | 0.0003 | 0.0003 |\n| ERC policy | 0.9470 | 0.9643 | 0.9716 | 0.9760 | 0.9787 | 0.9808 | 0.9826 | 0.9836 | 0.9844 | 0.9851 |\n| Confidence interval width | 0.0013 | 0.0006 | 0.0003 | 0.0003 | 0.0003 | 0.0003 | 0.0003 | 0.0004 | 0.0003 | 0.0002 |\n\nThe second instance has three cost constraints, with $|\\mathbb{S}| = 10$, $|\\mathbb{A}| = 2$,. We are not aware of any existing policies for the average-reward heterogeneous WCMDPs with multiple constraints, so we only evaluate the performance of our policy here.  We simulate $10^4$ time steps and $4$ replications for each $N\\in \\\\{100, 200, 300, ... 1000, 2000, 3000, ... 5000\\\\}$. Here, we consider a larger range of $N$ to more clearly demonstrate the asymptotic optimality of our policy. As we can see from the following table, as the number of arms $N$ gets large, the optimality ratio of our policy approaches $1$. \n\n| Variable | 100 | 200 | 300 | 400 | 500 | 600 | 700 | 800 | 900 | 1000 | 2000 | 3000 | 4000 | 5000 |\n| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |\n| ID policy (our work) | 0.9261 | 0.9501 | 0.9617 | 0.9666 | 0.9706 | 0.9734 | 0.9745 | 0.9763 | 0.9776 | 0.9787 | 0.9856 | 0.9881 | 0.9898 | 0.9910 |\n| Confidence interval width | 0.0005 | 0.0003 | 0.0004 | 0.0002 | 0.0002 | 0.0002 | 0.0002 | 0.0002 | 0.0002 | 0.0001 | 0.0002 | 0.0001 | 0.0001 | 0.0001 |\n\nDue to the limited time of the rebuttal period, we have only performed simulations on a small number of instances. We could add a few more simulations and include the results in our final version if our paper gets accepted.\n\n> Question 1: Do you have any insights on how results extend to the case in which we consider continuous sub-MDPs?\n> \n\nWe assume that the reviewer is referring to the continuous-space sub-MDPs. This is an interesting point, and we do think that our algorithm and analysis can possibly be extended to continuous spaces. To see this, observe that the real-time phase of the ID policy only needs to sample from the optimal single-armed policies $\\bar{\\pi}\\_{i}^{\\ast}$’s, which is possible even when the space is continuous.  Moreover, our optimality gap does not explicitly depend on the sizes of state and action spaces, as can be seen from the expression of $C\\_{\\text{ID}}$ in second paragraph below Theorem 1.  Therefore, if we can learn the optimal single-armed policies $\\bar{\\pi}\\_{i}^{\\ast}$ in the continuous sub-MDPs, our results can possibly carry through to continuous spaces. \n\n> Question 2: What are the main technical challenges in considering learning policies in unknown sub-MDPs? For instance, is would be possible to apply concepts by constrained reinforcement learning?\n> \n\nAs mentioned at the beginning of this rebuttal, a reasonable approach for learning a policy for the N-armed WCMDP could be learning the model parameters and then applying the ID policy based on the learned parameters.  To do this, we first learn the model parameters and construct the optimal single-armed policies for each sub-MDP.  As the reviewer pointed out, this can be done through approaches for constrained RL.  The main challenge in this approach is to handle how the errors in each sub-MDP affect the N-armed systems.  Note that actions generated by single-armed policies may not be feasible in the N-armed system since they may not satisfy the hard constraints (this is where the ID policy steps in).  Therefore, errors in each sub-MDP may have a non-linear effect and characterizing this effect is highly non-trivial.\n\n> Question 3: In the paragraph at lines 147--158, is it really necessary to indicate the policy when considering the vectors of MDPs states and actions?\n> \n\nWe thank the reviewer for the pointing out this issue. We indicate the policy $\\pi$ in superscripts mainly because $\\pi$ is the decision variable of the optimization problem formulated in (3), and we want to emphasize the dependency on the decision variable. We can also omit $\\pi$ in the paragraph at lines 147--158 if that is more natural. \n\n> Question 4: Is $R^*(N, \\mathbf{S}\\_0)$ only the optimal reward, or is it accounting for constraint satisfaction too?\n> \n\nIt is the optimal reward; we consider the hard constraints and do not allow constraint violations. \n\n> Question 5: “In Lemma 1, what happens to constraint violation when employing the solution of the relaxed problem?”\n> \n\nEmploying solutions of the relaxed problem would cause the constraint to be only satisfied in the long-run average sense, since the relaxed constraint (5b) is in terms of the long-run average state-action frequency $y(s,a)$. This is why we need Algorithms 1 and 2: we want to turn the solution of the relaxed problem into a policy that satisfies the hard constraint in (3b)."}, {"review_id": "p9J2fR9tAj", "reviewer": "Reviewer_9BWY", "summary": "This paper analyzes weakly-coupled Markov decision processes (WCMDPs), a classical framework for solving large decision-making problems, under the mean-payoff criteria. An algorithm is given with suboptimality guarantees of $O(1/\\sqrt{N})$, where $N$ is the number of components of the weakly-coupled model.", "questions": "**Questions**\n\n- What is the relation between WCMDPs and factored MDP or constrained MDP?\n- How to go beyond unichain? Did the authors consider weakly-communicating models?\n- l310: “let us assume …”: isn’t this implied by Assumption 1 ?\n- l363, quote: “Note that dividing each term by powers of $\\phi$ is another interesting trick, which makes the Lyapunov function strictly contractive under the optimal single-armed policies, as demonstrated in the proof of Lemma 3.” What do you mean by “strictly contractive”? Do you just mean contractive (Lipschitz-continuity with constant strictly smaller than 1)? Also in the proof of Lemma 3 (app E.2) I only found the proof of the Lipschitzness, not of the contraction property. Please clarify.\n\n**Suggestions**\n\n- Maintaining feasibility in the hard-constraint sense is crucial. The fact that the authors manage to do it is pretty strong and perhaps should be emphasized earlier in the paper / in the exposition of the results; I was wondering about this until the middle of page 6 (paragraph line 225 - 232).\n- What does “ID” mean (line 49 and onward)? Perhaps introduce the full term the first time.\n- Unichain assumption should be stated in the abstract and intro. It is crucial, but it only appears on the last-but-one page (page 8).", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n- The paper is very well-written, much better than most submissions I've reviewed this year.\n- The results are strong and the technics are new. This is a good paper.\n\n**Weaknesses** I don't see significant weaknesses. I only have a few questions/comments that could improve the presentation of the results and the positioning of the paper with respect to the rest of the literature on MDPs.", "was_revised": true, "final_justification": "I want to thank the reviewers for taking the time to address my comments. My assessment of the paper remains very positive, and I will keep my score. I encourage the authors to enforce the minor (in my opinion) stylistic improvements that I suggested.", "rebuttal": "> Question 1: What is the relation between WCMDPs and factored MDP or constrained MDP?\n> \n\nThanks for raising this interesting question. For the factored MDP and WCMDPs, while they both consist of some “loosely-coupled” components, their components are coupled in different ways: In the factored MDP, the components lie in a network, and the state transitions of nearby components are correlated. In contrast, the arms in WCMDPs have *independent* state transitions conditioned on the previous states and actions, but the joint actions of the arms are subject to a global constraint. It is unclear to us whether one problem class contains the other, or if there are any formal connections between these two classes. \n\nWCMDPs is also different from the constrainted MDP: in the WCMDPs, the instantaneous costs in every time step are subject to constraints, whereas in the constrained MDP, the long-run average costs are subject to constraints. Nevertheless, the LP relaxation of the WCMDPs is equivalent to a constrained MDP, with (5b) being the long-run average constraints on each type of cost. \n\n> Question 2: How to go beyond unichain? Did the authors consider weakly-communicating models?\n> \n\nGoing from unichain to weakly-communicating models (or more general) is non-trivial; even for the homogeneous case, asymptotically optimal policies are found only very recently by [22, 47]. On a high-level, their policies maintain the distribution of a subset of arms whose empirical state distribution is close to the optimal stationary distribution $\\mu^*$, while trying to control the rest of the arms so that they can be gradually merged into the first subset. This idea might be useful for the fully heterogeneous setting, although an obvious obstacle is to remove the dependency on the empirical state distribution, and it will be an interesting future work to see if our projection idea can work here. \n\n> Question 3: l310: “let us assume …”: isn’t this implied by Assumption 1 ?\n> \n\nThanks for bringing up this point. We would like to clarify that Assumption 1 only implies that each single-armed MDP mix to the steady state under the policy $\\bar{\\pi}_i^*$, whereas on Line 310 we assume that the joint state of all arms has a limiting distribution. \n\n> Question 4: l363, What do you mean by “strictly contractive”? Do you just mean contractive (Lipschitz-continuity with constant strictly smaller than 1)? Also in the proof of Lemma 3 (app E.2) I only found the proof of the Lipschitzness, not of the contraction property. Please clarify.\n> \n\nThanks for pointing out this confusion. By “strictly contractive”, we are referring to the drift condition (C2) on page 8, i.e., $h(\\mathbf{X}\\_t P) \\leq (1-C\\_2) h(\\mathbf{X}\\_t) + O(\\sqrt{N})$, and it is formally stated in the second bullet point of Lemma 3. We used the term “contractive” because $1-C\\_2 < 1$, but we will change the wording to avoid this confusion. \n\n> Suggestion 2: What does “ID” mean (line 49 and onward)?\n> \n\nHere ID is a short hand for identity, which are simply the integer numbers 1, 2, 3, … N assigned to the arms. We will clarify this name in the revision. \n\nWe thank the reviewer for all the constructive suggestions."}]

Author rebuttal:

Meta-review: Reviewers agree on the significance of the theoretical results, the methodological novelty, and the remarkable quality of the writing.
I encourage the authors to implement the proposed improvements in the final version and to include a polished version of the experiments that were presented in the rebuttal. The new finite-time bounds should also be added.
Decision: Accept (spotlight)