acceptodds
Under review as a conference paper at ICLR 2027

Continuation-Aware Decisions for Matroid-Constrained Restless Bandits

Abstract

Restless multi-armed bandit (RMAB) methods often reduce joint decisions to local scalar priorities. We ask whether this representation remains sufficient when feasible active sets form a matroid. An exact three-arm construction shows that state-local scalar scores can fail to represent the optimal policy under a fixed greedy selector, despite independent transitions and additive rewards. We therefore compare feasible sets using the Whittle continuation value. For binary-state RMABs, a low-order continuation approximation can be learned from known dynamics without joint-state value labels. Under explicit regularity, gap, and transition-row coverage assumptions, we prove a conditional expected finite-horizon regret bound of , where measures the structural error of the true-model frozen policy. Experiments show high decision fidelity under known dynamics and lower frozen-policy Q-loss than plugin and arm-wise optimistic baselines under unknown dynamics. The improvement over the plugin policy is not robust to several distribution shifts, and sparse online fitting can distort early decisions.

Primary area:
reinforcement learning
Keywords:
Restless multi-armed bandits, matroid constraints, reinforcement learning, Whittle index, online learning

Reviews

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

The paper studies whether arm-local scalar scores are sufficient for matroid-constrained restless bandits. An exact three-arm counterexample shows that no such scores, combined with the specified greedy selector, can reproduce the optimal policy. The proposed alternative evaluates feasible sets using the Whittle policy's continuation value, constructs an action sequentially, and applies one local correction. The paper also introduces a sparse second-order continuation approximation and a posterior-guided exploration rule. Its analysis establishes decision stability and a conditional regret bound. Experiments examine representation fidelity, online performance, distribution shifts, and sparse approximation.

Critical strengths
  1. The representational counterexample is clear and technically convincing. It rules out arbitrary arm-specific local scores under the stated selector, rather than merely demonstrating that particular Whittle indices are suboptimal. Independent exact rational computation reproduces the optimal actions and the two stated Bellman gaps. The continuation-based rule also recovers the optimum on this example.

  2. The sparse continuation construction is computationally appealing. Conditional independence makes the expectation of the second-order approximation analytically tractable, and Bellman-residual fitting avoids exact joint-state value labels. The known-model experiments demonstrate high fidelity to the exact continuation-based decisions on the tested instances.

  3. The experimental reporting is careful. The main online study uses 162 independent underlying models and preserves the paired structure in its bootstrap analysis. The paper explicitly distinguishes frozen-policy Q-loss from reward regret and reports unresolved comparisons, distribution-shift failures, and early sparse-fitting errors.

Critical weaknesses

1. The broader benefit of the continuation-based decision rule is not sufficiently established.

The main online comparison keeps the continuation-based architecture fixed and varies exploration. It therefore evaluates the exploration rule, but does not directly establish the value of replacing local index selection with the proposed construction. Likewise, high sparse-versus-exact action agreement measures fidelity to the proposed policy, not its reward quality relative to Whittle or the optimum.

This distinction matters because FP(s,A)=QPπPW(s,A)F_P(s,A)=Q_P^{\pi_P^W}(s,A) is a standard rollout objective, while the proposed sequential construction and single local correction only approximately optimize it. The Whittle action need not belong to the final neighborhood, so the usual policy-improvement guarantee does not follow automatically. The 37 resolved local-score barriers are encouraging, but reward or value comparisons on the already available exact instances would better establish the practical importance of this improvement.

2. The evidence for the specific posterior-guided exploration mechanism is incomplete.

The improvement over plugin is supported by both frozen-policy Q-loss and realized reward. However, the Q-loss difference from random exploration is unresolved: the reported difference is -19.965 with a 95% interval of [-62.509, 26.876]. Performance also deteriorates relative to plugin under several population shifts.

Equation (9) is a signed comparison against the frozen policy on each learner's own trajectory. Consequently, differences can reflect both action quality and the states visited. Reporting reward comparisons against random exploration, alongside the existing plugin comparison, would make the practical conclusion clearer.

The conditional bound RT⋆≤Tϵstruct+O(log⁡T)R_T^\star \leq T\epsilon_{\mathrm{struct}}+\mathcal{O}(\log T) does not resolve this question. It assumes sufficient transition-row coverage, which the proposed policy is not shown to achieve, and does not bound the structural error of the frozen policy. It is useful as a stability result, but provides limited justification for the particular exploration bonus.

3. The computational contribution is not yet demonstrated for a complete scalable online method.

The main online experiments use exact joint-state continuation evaluation with only five or six arms. The sparse replacement fails the prespecified early fidelity criteria. Appendix B.7 states that separate closed-loop trajectories were generated, but the main results emphasize agreement on exact-backend histories rather than the reward consequences when sparse decisions generate their own histories.

The known-model fidelity results are promising, although the primary study has only three underlying models per size. The additive approximation already achieves 99.48% construction-path agreement at both N=6 and N=8, leaving the main demonstrated benefit of pairwise terms concentrated at N=5. The reported larger known-model cases do not establish the accuracy or computational advantage of the complete online algorithm.

Questions for authors
  1. On the existing exact instances, how do Whittle, sequential construction, construction with local correction, and exact maximization of the Whittle continuation score compare in discounted value? Does FP(s,fP(s))≥FP(s,πPW(s))F_P(s,f_P(s)) \geq F_P(s,\pi_P^W(s)) hold at all tested states?

  2. What is the paired realized-reward difference between posterior-guided and random exploration? Does the exploration advantage remain visible in a metric that does not use a different visited-state distribution for each method?

  3. Can the already generated closed-loop sparse-backend trajectories quantify the reward cost of early fitting errors? Please also report fitting and decision costs so that the approximation's computational benefit can be assessed.

  4. How much transition-row coverage is actually achieved in the online experiments, and how does it relate to the assumption in Theorem A.4?

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

This paper studies matroid-constrained restless multi-armed bandits (RMABs) and asks whether policies based on arm-local scalar priorities followed by a fixed greedy matroid selector are sufficiently expressive. Proposition 5.1 provides an exact three-arm counterexample showing that policies of the form π(s)=ΓM(d1(s1),…,dN(sN))\pi(s)=\Gamma_{\mathcal M}(d_1(s_1),\ldots,d_N(s_N)) cannot always represent the optimal policy, even with independent transitions and additive rewards. To address this limitation, the paper proposes a continuation-aware set score FP(s,A)=R(s,A)+γEP[VPW(s′)∣s,A]F_P(s,A)=R(s,A)+\gamma\mathbb{E}_P[V_P^W(s')\mid s,A], which evaluates taking feasible set AA for one step and then following the Whittle policy. The method greedily constructs a feasible set using continuation gains and applies one local add/delete/swap correction. For binary-state RMABs, the paper introduces a sparse second-order continuation approximation fitted using Bellman residuals without exact joint-state value labels. For unknown dynamics, it proposes posterior-guided exploration based on posterior action-margin shifts and variances, together with conditional stability/regret analysis and empirical studies.

Critical strengths
  1. Clear representational impossibility result with a well-motivated alternative.

Proposition 5.1 is a meaningful contribution: it establishes that the limitation is not merely due to imperfect Whittle indices, but can arise for any state-local scalar scoring rule used with the fixed greedy selector. The exact rational three-arm construction is particularly clear. The continuation score FP(s,A)F_P(s,A) is also well motivated as a one-step rollout around the Whittle policy, allowing current decisions to account for future matroid-induced competition.

  1. Decision-focused approximation analysis and commendable empirical transparency.

Proposition 5.2 and Eq. (5) appropriately characterize approximation error through its effect on action comparisons rather than global value MSE alone. The binary sparse approximation also permits efficient evaluation of the approximate continuation expectation. I also appreciate the paper's transparency in reporting negative results: the unresolved comparison to random exploration, reversals under distribution shifts, and the early failures of causal sparse online fitting.

Critical weaknesses
  1. The paper does not yet establish an end-to-end scalable online method.

The main online experiments in Section 7.3 use exact joint-state continuations for both the plugin model and M=8M=8 posterior samples. As the paper notes, this retains exponential dependence on the joint state space, and the online experiments are limited to N∈{5,6}N\in\{5,6\}. The sparse continuation backend intended to address this issue fails the authors' prespecified online fidelity criteria during cold start (Section 7.4 / Appendix B.7), and no larger-scale unknown-dynamics experiment is provided. Thus, the paper currently demonstrates small-scale exact-continuation online learning and known-model sparse approximation, but not scalable online learning under unknown dynamics. The empirical necessity of second-order terms is also somewhat mixed. Pairwise energy is reported to be small, and the first-order model already has high known-model fidelity for N=6,8N=6,8, although sparse second-order terms improve results at N=5N=5. The paper should clarify the regimes in which second-order interactions are essential for decisions rather than merely beneficial in selected instances.

  1. The regret result is conditional on the central exploration challenge.

Theorem A.4 gives a bound of the form Tϵstruct+O(log⁡T)T\epsilon_{\mathrm{struct}}+O(\log T) only under assumptions including sufficiently rapid transition-row coverage. In particular, the paper explicitly states that coverage is assumed rather than established by the proposed policy. Therefore, the theorem is best interpreted as a conditional model-estimation and policy-stability result: once all relevant transition rows are sufficiently covered and estimation errors are below fixed decision margins, the learned policy agrees with the true-model frozen policy. Moreover, the proof uses the posterior bonus in Eq. (4) primarily as a perturbation that must become small enough not to alter the true-model decision. It does not show that this bonus improves transition-row coverage. Under the same externally imposed coverage assumptions, a closely analogous stabilization argument may be possible for a pure plugin rule. Thus, the current theory does not establish a formal exploration advantage for the posterior-guided bonus.

  1. The empirical case for the posterior-guided exploration rule is limited.

The proposed bonus bt(A)=∣mt(A)−m^t(A)∣+βσt(A)b_t(A)=|m_t(A)-\widehat m_t(A)|+\beta\sigma_t(A) is explicitly not calibrated as a confidence bound or derived from an information-seeking objective. Posterior-guided exploration improves over plugin in the main benchmark, but its difference from random exploration is statistically unresolved: the reported 95%95\% CI is [−62.509,26.876][-62.509, 26.876]. It also underperforms plugin under persistence, reward-heterogeneity, and mixed-population shifts. Given the additional cost of posterior sampling and repeated continuation evaluation, stronger evidence is needed that this particular bonus is preferable to simpler exploration rules. A direct Thompson-sampling baseline is notably absent.

  1. The primary online metric is useful diagnostically but insufficient as the main control metric.

The main metric in Eq. (9), frozen-policy Q-loss, measures signed deviation from the frozen continuation policy fPf_P along each learner's own trajectory. It is not regret relative to the true optimal policy and is affected by policy-induced state distributions. Since the experiments are small enough to permit exact dynamic programming, the paper should more prominently report policy-level quantities such as finite-horizon reward regret, discounted value gaps, and optimal-action agreement relative to the true optimal policy. The diagnostic study in Appendix B.2 also indicates that the continuation construction itself is not generally optimal, reinforcing the need for an optimal-policy reference.

Questions for authors
  1. Comparison to the true optimum:

For the N=5,6N=5,6 settings, can the authors report finite-horizon reward regret, discounted value gaps, and optimal-action agreement relative to the true optimal policy? In particular, how large is the structural gap between the frozen continuation policy fPf_P and the true optimal policy?

  1. Coverage diagnostics:

Can the authors report transition-row coverage over time for plugin, random exploration, arm-wise optimism, and posterior-guided exploration? For example, how does min⁡i,s,ani,s,a(t)\min_{i,s,a} n_{i,s,a}(t) evolve, separately for active and passive rows? Does posterior-guided exploration empirically improve the coverage condition required by Theorem A.4?

  1. Posterior-sampling baseline:

Can the authors compare with a direct Thompson-sampling-style baseline that samples a transition model from the posterior at each update and runs the same continuation-aware planner under the sampled model? This would help isolate the contribution of the heuristic margin bonus in Eq. (4).

  1. Cold-start sparse fitting:

Appendix B.7 suggests that substantial early move-margin error is already present in dense second-order fits before sparsification. Have the authors tested a lower-complexity warm-start backend, such as an analytic Bellman-fitted first-order model followed by sparse second-order fitting only after sufficient coverage? The known-model R1 results are encouraging, although they do not directly establish online causal fidelity.

Reviewer_SwvmOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies matroid-constrained restless multi-armed bandits. It first gives a three-arm counterexample showing that arm-local scalar priorities with a fixed greedy selector can fail to represent the optimal policy. The authors then propose a continuation-aware rule that scores feasible activation sets by the future value of a Whittle policy, combined with greedy construction and local correction, plus a sparse second-order continuation approximation and posterior-guided exploration. Under regularity, gap, and coverage assumptions, they prove a conditional regret bound of Tϵstruct+O(log⁡T)T\epsilon_{\mathrm{struct}}+O(\log T). Experiments show high decision fidelity under known dynamics and gains over a plugin baseline in small-scale online settings, while also revealing limitations under distribution shifts and sparse online approximation.

Critical strengths
  1. The paper provides an exact three-arm counterexample showing that arm-local scalar scores with a fixed greedy selector can fail to represent the optimal policy, even under a simple cardinality constraint with independent transitions and additive rewards. I find this a useful theoretical observation that motivates considering joint-state information in RMAB decisions.

  2. Under known dynamics, the sparse second-order continuation approximation can be learned without exact joint-state value labels and achieves high decision fidelity on the tested small-scale instances. The experiments also examine online learning and distribution shifts, explicitly reporting cases where the approach performs poorly. This provides useful evidence about both the potential and the limitations of the method.

Critical weaknesses
  1. The continuation-aware decision rule shares similarities with one-step rollout using the Whittle policy as a baseline, while the sparse value approximation and Bellman residual fitting also build on established techniques. I am not fully convinced what the main methodological novelty is beyond combining these components in the matroid-constrained setting. Separately, the regret bound relies on strong regularity, decision-gap, and transition-coverage assumptions, where coverage is not guaranteed by the proposed policy. The bound also includes a potentially linear structural error term, limiting its implications for regret relative to the optimal policy.

  2. The main online experiments use exact joint-state continuations on small instances (N=5,6N=5,6), rather than the sparse approximation motivated by scalability. Although the sparse approximation achieves high fidelity under known dynamics, its causal online version fails the authors' prespecified fidelity criteria, and no larger-scale unknown-dynamics evaluation is provided. Moreover, the improvement over random exploration is not statistically resolved, and several distribution shifts reverse the advantage over the plugin baseline. These results leave me uncertain about the effectiveness and practical scalability of the complete online approach.

Questions for authors
  1. Regarding Weakness 1, could the authors clarify the main methodological differences between the proposed continuation-aware decision rule and existing RMAB rollout or approximate policy improvement methods?

  2. Regarding Weakness 1, under what conditions can the structural error ϵstruct\epsilon_{\mathrm{struct}} be expected to be small?

  3. Regarding Weakness 1, under what conditions does the proposed exploration policy satisfy the transition-coverage assumption? Is this assumption examined empirically?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.