acceptodds
Withdrawn from ICLR 2027

Two-Phase Policy Classes for Multi-Context Restless Bandits

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Restless multi-armed bandits are widely used for sequential resource allocation, yet all existing theory assumes a fixed activation budget. In practice, many applications involve multiple operating contexts with distinct dynamics, and the decision of how to distribute budget across these contexts is as important as which arms to activate within each. We formalize this as the contextual budget bandit (CBB), a two-phase optimization where the upper level allocates per-context budgets under a global capacity constraint and the lower level selects arms under hard per-period limits. We introduce a hierarchy of two-phase policy classes capturing this structure. Our main result shows that, for exchangeable arm types, the optimal policy belongs to a tractable class we call aggregate-state-dependent priority: the type-priority may depend on how many arms of each type are engaged, but not on which specific arms. We prove this via permutation invariance of the value function. Surprisingly, fixed-priority index policies are not always optimal: a portfolio effect causes the priority between types to reverse depending on same-type depth, starting at three arms. A gap bound shows that Lagrangian index policies lose at most a vanishing fraction of the optimum as the number of arms grows. Computational validation across 112,000 randomly generated instances confirms the aggregate-class optimality at 100% and quantifies the portfolio effect at 2–17% of instances. On a food rescue volunteer engagement application, the Mirror Descent Value Iteration (MDVI) algorithm achieves 0.0–3.2% gap from the LP bound, scaling to arms in 10 minutes.

Primary area:
reinforcement learning
Keywords:
Restless multi-armed bandits, sequential resource allocation, value iteration

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_4dejOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper studies a restless-bandit problem in which a context is drawn each period. The policy first chooses integer context budgets satisfying ∑kfkBk≤Btot\sum_k f_k B_k\leq B_{\mathrm{tot}}, then selects arms under the corresponding per-period cap. The paper shows that exchangeable arms admit an optimal policy based on engagement counts within each type, gives an example intended to separate this class from fixed priorities, and claims an O(K/N)O(K/N) approximation bound for Lagrangian policies. MDVI combines single-arm value iteration with price updates. Experiments use small-instance searches and synthetic volunteer-engagement models, including systems with 2,000 arms.

Critical strengths

Theorem 5 identifies a sufficient state description for exact control. Given type tt's engaged count ntn_t, total activation count btb_t, and engaged activation count ℓt\ell_t, both its immediate reward and its next engaged-count distribution are determined. Appendix A.3 spells out the four state/action category counts and the resulting binomial convolution. This makes the reduction concrete: for fixed type count, the state space has ∏t(Nt+1)\prod_t(N_t+1) elements rather than 2N2^N. It also explains why arbitrary choices among identically situated arms do not affect value. I find this result convincing when Fagg\mathcal F_{\mathrm{agg}} is interpreted as the count-allocation class defined in Definition 1.

Critical weaknesses

Theorem 7's stability argument does not describe the policy being bounded. In Appendix B.1, Equation (25) fixes the LP-optimal action in each type/state category and obtains independent linear dynamics. Hard-budget priority selection changes those actions according to the entire count vector. For example, if engaged type-0 arms precede engaged type-1 arms, the latter receive at most min⁡{n1,(B−n0)+}\min\{n_1,(B-n_0)_+\} activations. Their transition law therefore depends on n0n_0. Conditional independence of individual transitions does not remove this dependence. Appendix A.5 also invokes a separate standard-bandit bound for each context, although contexts act successively on the same arms. Neither step establishes the required attraction property for the actual contextual policy. There is a further normalization problem: Section 2 defines gg as total reward per period, while Equation (22) divides the rounding loss by NN and then inserts it into a bound on this unnormalized gg.

MDVI does not yet specify how its prices produce the integer budgets that are central to the problem. Algorithm 1 takes BtotB_{\mathrm{tot}} as input but uses BkB_k in its update without constructing them. It returns independent arm policies; the text refers to complementary slackness for recovering budgets, but does not give a rule that guarantees ∑kfkBk≤Btot\sum_k f_kB_k\leq B_{\mathrm{tot}} together with hard per-period feasibility. This is consequential because solving the relaxed allocation problem does not itself provide that feasible policy. The update also has opposite signs in Algorithm 1 and Appendix C.2. Without a complete budget-recovery procedure, I cannot determine which two-phase policy the reported MDVI results evaluate.

Questions for authors
  1. Proof clarification: What are the population dynamics after hard-budget priority selection and context switching? Can the assumptions needed for Theorem 7 be proved for those dynamics, with a consistent total-reward or per-arm normalization?
  2. Algorithm clarification: How are feasible integer BkB_k recovered from the learned prices, and which update sign was implemented?
  3. Counterexample clarification: What rewards and full-precision parameters were used in Proposition 2? With the printed transitions and unit engaged-pull rewards Ri(s,a)=saR_i(s,a)=sa, an average-reward calculation chooses type 1 at both (n0,n1)=(1,1)(n_0,n_1)=(1,1) and (2,1)(2,1); at the latter state its Bellman advantage over type 0 is approximately 0.06530.0653. This check is conditional on those rewards, which the example does not specify. An average-reward optimality certificate for the complete instance would resolve the discrepancy.
Reviewer_oEtqOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper studies the contextual budget bandit (CBB), a restless bandit in which a context kk is drawn i.i.d. at each period, the arms' dynamics depend on kk, and the per-context budgets BkB_k are decision variables subject to a global constraint ∑kfkBk≤Btot\sum_k f_k B_k \le B_{\text{tot}}. The authors introduce a hierarchy of policy classes FLag⊂Fidx⊂Fagg⊂Fdet⁡\mathcal{F}_{\text{Lag}} \subset \mathcal{F}_{\text{idx}} \subset \mathcal{F}_{\text{agg}} \subset \mathcal{F}_{\det} and claim that: under exchangeable arm types, the optimal policy depends only on the aggregate counts of engaged arms per type; fixed-priority index policies can be suboptimal for N≥3N \ge 3 (a "portfolio effect"); the per-context shadow prices satisfy wk=μ∗fkw_k = \mu^{\ast} f_k; and Lagrangian index policies have an optimality gap of O(K/N)O(K/N). They also propose MDVI, a dual subgradient algorithm, and evaluate it on small exchangeable instances and on synthetic instances calibrated to a food rescue application.

Critical strengths

None

Critical weaknesses

1. Theorem 7, the only non-trivial theoretical result, is not proven; Proposition 6 is both trivially true and incorrectly argued.

(a) Rounding term. The proof (A.5) asserts that the integer-optimal allocation satisfies ∣Bk⋆−DkL∣≤1|B_k^\star - D_k^L| \le 1 "by concavity of gk⋆(Bk)g_k^\star(B_k)". This is unjustified twice over. First, even if the value were separable across contexts (which it is not, see (b)), the upper level would be an integer program with a single weighted constraint ∑kfkBk≤Btot\sum_k f_k B_k \le B_{tot}, i.e. a knapsack; for non-uniform fkf_k the integer optimum need not be within one unit of the continuous optimum in every coordinate. Second, the concavity of the hard-constraint value gk⋆(Bk)g_k^\star(B_k) (Lemma 9) is "proved" by the statement that "the (Bk+2)(B_k+2)-th best arm is worse than the (Bk+1)(B_k+1)-th best", which is a myopic argument with no dynamic content; dropping one activation changes the trajectory of that arm and hence all subsequent decisions, so there is no coupling that keeps the two systems within one arm of each other. The same flaw underlies the claim that each misallocated unit costs at most Rmax⁡R_{\max} per period in the long-run average.

(b) Index term. The proof says "given B⋆B^\star, each context kk faces a standard restless bandit with NN arms and budget Bk⋆B_k^\star" and invokes the exponential bound of Gast et al. per context. But the CBB is a single Markov system whose per-period kernel is drawn i.i.d.; arm states carry over across contexts, so there is no per-context RMAB to which a time-homogeneous asymptotic-optimality theorem applies. Section 7 itself states that no prior index theory addresses this setting. Moreover, Appendix B "verifies" UGAP and GES by analysing a scalar linear ODE with the LP-optimal actions at⋆,at⋆⋆a_t^\star, a_t^{\star\star} held fixed (Eqs. 25–27). Under a priority policy the actions applied to a type-state category depend on how many arms occupy higher-priority categories, so the mean-field dynamics are piecewise-linear and coupled across types through the budget; the constant-action linearisation is precisely the local object that UGAP is not equivalent to. Nothing in Appendix B establishes the hypotheses of the cited theorem.

(c) Units. The left-hand side of Eq. (4) is the total average reward gg (Eq. 2 sums over NN arms), while the right-hand side is derived as a per-arm quantity ("the contribution to the per-arm average gap is KRmax⁡/NK R_{\max}/N"). As written the inequality is dimensionally inconsistent; normalising both sides turns the rounding term into an O(K)O(K) total loss, which is fine but is not what the theorem states.

(d) Proposition 6. The argument "reducing wkw_k to μfk\mu f_k removes this positive term without affecting the per-arm subproblems (which depend on wk/fkw_k/f_k, not BkB_k)" is wrong: the per-arm subproblems depend on wkw_k through the penalty (wk/fk)ai(w_k/f_k) a_i in Eq. (19), so lowering wkw_k changes them. The conclusion wk⋆≤μ⋆fkw_k^\star \le \mu^\star f_k can be rescued (the dual is non-decreasing in wkw_k beyond μfk\mu f_k because ∣∂q/∂wk∣≤N|\partial q/\partial w_k| \le N while the penalty slope is NN), but the "complementary slackness" step then only holds for the convex relaxation, not for the integer, hard-constraint bilevel problem the proposition is stated for. More importantly, the result is immediate: once both constraints are relaxed to expectations, E[∥a∥1∣k]≤BkE[\lVert a\rVert_1 \mid k] \le B_k and ∑kfkBk≤Btot\sum_k f_k B_k \le B_{tot} collapse to the single constraint ∑kfkE[∥a∥1∣k]≤Btot\sum_k f_k E[\lVert a\rVert_1 \mid k] \le B_{tot}, so the per-context variables BkB_k are free and only one multiplier μ\mu survives. The "two-phase" structure disappears entirely in the relaxation, which also means the LP bound used throughout the experiments is just the standard single-budget relaxation. The claim that this "has no analogue in single-budget RMABs" is therefore misleading.

This is consequential because, without Theorem 7, the paper has no guarantee connecting the tractable classes (FLag\mathcal F_{Lag}, MDVI) to the optimum, and the headline "vanishing fraction of the optimum" claim in the abstract is unsupported.

2. The remaining theoretical claims are folklore, and the experiments neither match the theory's assumptions nor test the paper's stated contribution; the reported numbers are internally inconsistent.

(a) Theorem 5 is the standard symmetry reduction. That an MDP invariant under a permutation group admits an optimal policy measurable with respect to the orbits (here, the counts nn) is a textbook lumpability argument; Lemma 4 is exactly the usual proof. Calling the 112,000-instance check a "validation" of this theorem is tautological: the 100% rate is forced by symmetry (any violation would be a tie-breaking artefact), and the statement "we do not require indexability, UGAP, non-degeneracy" compares a symmetry reduction to asymptotic-optimality results that answer a different question. Note also that the restatement of Theorem 5 in A.3 ("the optimal two-phase policy is in Fagg\mathcal F_{agg}") should read "there exists an optimal policy in Fagg\mathcal F_{agg}"; with ties, not every optimal policy is in it.

(b) The portfolio effect is the known finite-NN suboptimality of index policies. That fixed-priority (Whittle/LP-index) policies are not optimal for finite NN and only asymptotically optimal is the starting point of Weber and Weiss (1990) and the entire subsequent literature; Proposition 2 re-establishes it numerically on a 33-arm instance. The Section 3.2 "counterexample" does not even exhibit a reversal: preferring a disengaged organic over an engaged churner is a single fixed ranking (org,0)≻(churn,1)(\mathrm{org},0) \succ (\mathrm{churn},1), so the described optimal policy is in Fidx\mathcal F_{idx}. Remark 3's claim that the effect "requires N≥3N \ge 3" is supported only by a resolution-10 grid; at N=2N=2, T=2T=2 there do exist policies not representable by any fixed ranking. For instance, pulling type 0 when both arms share a state and type 1 otherwise induces, on the (type, state) categories, the cycle (0,0)≻(1,0)≻(0,1)≻(1,1)≻(0,0)(0,0) \succ (1,0) \succ (0,1) \succ (1,1) \succ (0,0), so the claim is non-trivial and remains unproven.

(c) The theory does not apply to the experimental instances. Theorems 5 and 7 assume exchangeable types, but the benchmark arms are heterogeneous: each organic arm has its own distance-dependent pikp_{ik} and idle retention drawn per arm (C.1, C.3). The O(1/N)O(1/N) reference line in Figure 2 has no theoretical basis for these instances, and the MDVI sequence 6.2, 1.2, 3.2, 0.0, 1.1, 0.0 (Table 7) does not "track" it.

(d) The two-phase budget allocation is never exercised. All main experiments use fk=1/Kf_k=1/K, and the paper states (C.1) that the LP-optimal allocation then coincides with the uniform split, so "all performance differences arise from the arm selection policy". The only non-uniform experiment is two sentences in C.3 (3.9% to 2.8%) with no table. The paper's motivating contribution, deciding how to split budget across contexts, is thus untested.

(e) Text and tables contradict each other. "MDVI leads at most configurations" (6.3) and "achieves the lowest gap at every configuration" (Fig. 5 caption) versus Table 2, where NIP is better in six of eleven rows and Mitosis ties at N=500N=500; abstract "0.0–3.2% gap" versus 6.4% at (20,2,4)(20,2,4) and 6.2% at (50,3,5)(50,3,5); "Mitosis ... 1.3% at N=500N=500" (stated twice) versus 0.0% in Tables 2 and 7; "Fdual\mathcal F_{dual} achieves 0.01–0.22% gap" versus 0.3–1.5% in Table 3, with standard errors of 1–3% that swamp every difference the "three clear patterns" are built on; L=500L=500 iterations (6.3) versus 150 (C.2); "N=2,000N=2{,}000 arms in 10 minutes" (abstract) versus 55 minutes (6.5); "four adversarial generators" (Table 6) versus five (Appendix D); "MDVI (Fagg\mathcal F_{agg})" in 6.3 versus FLag\mathcal F_{Lag} everywhere else; Table 3 labels Fdual\mathcal F_{dual} as Fagg\mathcal F_{agg} while the text calls it the smallest class; immediate rewards "R∈[0.8,1.2]R \in [0.8,1.2]" (6.1) versus pik∈[0.1,0.9]p_{ik} \in [0.1,0.9] and churner rewards in [0.05,0.15][0.05,0.15] or [0.80,0.95][0.80,0.95] (C.3). Several of these are not typos but opposite claims about the same table.

This is consequential because, after removing the folklore and the unproven bound, what remains is a Lagrangian LP-index heuristic with subgradient price updates evaluated on instances where the novel part of the problem is switched off, reported with numbers that cannot all be correct.

Questions for authors

Please feel free to address any of the points raised above.

Reviewer_LRXFOpenReview ↗
Rating
2
Confidence
1
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies contextual budget bandits with two-phase resource allocation. It introduces a hierarchy of policy classes and proves that aggregate-state-dependent priority policies are optimal under within-arm-type exchangeability. It also identifies a portfolio effect showing that fixed-index policies can be suboptimal. The paper proposes MDVI, which combines Lagrangian relaxation with per-arm value iteration, and establishes an performance gap of O(K/N)O(K/N) with the theoretical upper bound. Experiments on synthetic food rescue scenarios demonstrate promising performance and scalability with up to 2,000 arms.

Critical strengths
  1. The portfolio effect provides an interesting insight into the limitations of fixed index policies.
  2. The authors analysis the policy-class hierarchy (FLag,Fidx,Fagg,FdetF_{Lag}, F_{idx}, F_{agg}, F_{det}) and provide a structured understanding of the trade-offs between expressiveness and computational cost.
Critical weaknesses
  1. The proposed framework relies on several simplifying assumptions that may limit its applicability to realistic problems. In particular, contexts are assumed to be independently and identically distributed over time. However, real-world contexts often exhibit temporal dependencies, such as seasonal variations. Moreover, actions taken under one context may influence the subsequent contexts. Although the framework captures the temporal evolution of arm states, it does not explicitly model temporal dependencies in context arrivals. Furthermore, the theoretical analysis assumes exchangeability among arms of the same type. In practical scenarios such as food rescue, volunteers may exhibit heterogeneous responses and availability across different contexts due to geographical differences, etc. Although it would be unreasonable to expect the authors to study all these complexities, additional experiments on robustness to temporally correlated contexts and approximately exchangeable arms would help discuss the generalizability of the proposed framework. BTW, the paper's own large-scale experiments introduce arm-specific transition parameters, which do not strictly satisfy the exchangeability assumption underlying Theorem 5.
  2. Although the paper emphasizes joint optimization of context-specific budget allocation and arm selection, the paper lacks ablations of the contribution of budget optimization while keeping the arm-selection policy fixed.
Questions for authors
  1. Appendix C.2 says that Mitosis selects arms greedily based on immediate rewardsn. However, the original Mitosis algorithm evaluates budget allocations using the simulation oracle based on the Contextual Occupancy Index Policy, which incorporates long-term state dynamics.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.