acceptodds
Under review as a conference paper at ICLR 2027

Graph-Discovering for Networked Restless Multi-Armed Bandits with Nonlinear Delayed Propagation

Abstract

We study nonlinear graph-discovering restless multi-armed bandits, where budgeted interventions propagate through an unknown sparse directed graph and induce delayed, persistent, and nonlinear effects on future arm dynamics. Graph identification is challenging because reward-seeking actions may provide insufficient information, particularly when nonlinear responses are saturated. We propose Nonlinear Graph-Discovery Optimistic Intervention (N-GDOI), which couples derivative-weighted Fisher exploration and localized sparse nonlinear graph estimation with optimistic stochastic rollout planning. Fisher-aware exploration probes uncertain graph directions in informative response regions, while planning over graph confidence sets accounts for both model uncertainty and nonlinear trajectory noise. We establish high-probability graph-recovery guarantees under adaptively collected data and prove stability of stochastic rollout values under graph perturbations. N-GDOI achieves truncated rollout regret over time horizon under scheduled Fisher-informative exploration, improving to when reward-seeking actions provide persistent Fisher excitation. The bounds explicitly separate statistical graph uncertainty from finite graph-candidate, Monte-Carlo rollout, and approximate action-search errors. Experiments show improved graph recovery and long-horizon reward, with the largest gains under partially saturated nonlinear propagation.

Primary area:
reinforcement learning
Keywords:
Restless Multi-Armed Bandits, Online Graph Discovery, Nonlinear Delayed Propagation, Fisher Exploration, Regret Analysis

Reviews

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

This paper studies networked restless multi-armed bandits with an unknown directed graph governing nonlinear and persistent spillover effects. The proposed N-GDOI algorithm combines Fisher-aware exploration, localized sparse nonlinear graph estimation, and optimistic stochastic rollout planning. Under localization, excitation, and planning-accuracy assumptions, the authors establish graph-estimation bounds and O~(T2/3)\widetilde{\mathcal O}(T^{2/3}) regret against a true-graph finite-horizon rollout oracle, with a faster rate under stronger excitation conditions. Synthetic experiments report improvements in both decision performance and graph recovery, particularly under nonlinear propagation.

Critical strengths
  1. Interesting and well-motivated problem. Learning an unknown propagation graph while making sequential interventions is an important problem. Nonlinear responses and persistent spillover effects introduce meaningful challenges beyond independent-arm or known-network formulations.

  2. Statistically motivated exploration objective. The Fisher-aware objective accounts for both input diversity and the sensitivity of the nonlinear response. This addresses the fact that interventions can generate little information about the graph when the response is saturated.

  3. Comprehensive theoretical analysis. The analysis connects graph-estimation accuracy, Fisher excitation, rollout-value stability, and cumulative decision loss. It also explicitly accounts for approximation errors in graph selection, Monte Carlo evaluation, and action search. The distinction between the rollout benchmark and the unrestricted optimal policy is clearly acknowledged.

  4. Promising experimental results. The reported improvements are substantial in the nonlinear settings. For example, under the default sigmoid configuration, N-GDOI achieves support F1 of 0.94 and Frobenius error of 0.58, compared with 0.62 and 2.05 for MH-GRETA. The experiments also include component ablations and variations in graph topology, noise, network size, and intervention budget.

Critical weaknesses
  1. The required exploration guarantee is not established for the proposed rule. Theorem 2 assumes that the exploration policy satisfies the conditional Fisher-excitation condition in Assumption 3. However, the connection between this condition and the approximate information-gain maximization in Eq. (3) remains unresolved. Remark 2 acknowledges that greedy information-gain maximization does not automatically ensure the required excitation. The paper should specify what randomization is used and explain when the implemented exploration policy satisfies the assumption.

  2. The graph-estimation guarantee relies on an insufficiently specified initialization. Assumption 2 requires the burn-in localizer to satisfy ∥P~⋅j−P⋅j⋆∥1≤rloc2.\lVert \tilde P_{\cdot j}-P^\star_{\cdot j}\rVert_1 \leq \frac{r_{\mathrm{loc}}}{2}. . Algorithm 1 states that the localizers are constructed from burn-in data, but the procedure and its accuracy guarantee are unclear. The experiments use 60 burn-in rounds without sufficiently explaining the construction of the localizers or the choice of rlocr_{\mathrm{loc}}. Since an inaccurate localizer can exclude the true graph from the regression domain, this is consequential for the subsequent guarantees.

  3. There is a gap between the practical planner and the conditions of the final regret theorem. Theorem 5 requires increasing rollout counts and appropriately decreasing planning-approximation errors. Appendix D.2 instead reports a fixed rollout count Kt=16K_t=16 and beam width 4. The fixed simulation budget does not satisfy the theorem's growing-budget condition, and the required decay of the action-search error is not established for the reported beam-search implementation. These settings may perform well empirically, but the paper should clarify which guarantees apply to the tested algorithm.

  4. The presentation needs improvement. The formulation introduces many quantities without making their roles sufficiently clear at the point of use. Readers frequently need to determine whether a quantity is known, observed, learned, theoretically calibrated, or chosen as a hyperparameter. Although the appendix contains a notation table, a compact overview in the main text and more explicit descriptions of the initialization and planning subroutines would substantially improve readability and reproducibility.

Questions for authors
  1. What randomization is used by ApproxFisherOracle, and under what conditions does the implemented policy satisfy Assumption 3? How should the one-round conditional excitation requirement be interpreted for greedy or deterministic action selection?

  2. How are the burn-in localizers and rlocr_{\mathrm{loc}} constructed without knowledge of the true graph? Please specify the regression solver and explain whether its output satisfies the optimization condition used in the analysis.

  3. Which version generated the experiments: the scheduled exploration algorithm or the threshold-triggered variant mentioned in Appendix C.14? What guarantee remains for the reported fixed rollout count and beam width?

  4. What graph estimators, model knowledge, and fitting data are used by GRETA and MH-GRETA? Can the Fisher-exploration benefit be evaluated against random feasible exploration with the same estimator, planner, and exploration sample budget?

1 comment
Reviewer_3uXrOpenReview ↗

Response to Authors' Rebuttal

Thank you for the detailed response and additional experiments. The randomized exploration construction, pilot-based localization procedure, and explicit treatment of optimization error substantially improve the theoretical specification. The matched comparison against uniform exploration and unweighted leverage also provides useful evidence for the practical benefit of Fisher weighting.

My main remaining concern is the scope of the guarantees. The experimental implementation retains deterministic Fisher-greedy exploration, warm-start fitting, threshold-triggered exploration, and fixed planning budgets. The new sufficient construction therefore does not establish the stated sublinear regret guarantee for that implementation. I appreciate that the response now makes this distinction explicit.

Please ensure that the revised theorem statements and algorithm descriptions clearly identify which version each guarantee covers. It would also be helpful to clarify which experimental settings satisfy the new local-curvature conditions and what sufficient pilot sample size those conditions imply.

Based on the response, I think the paper is good for me to maintain my weak-accept recommendation, subject to checking the complete revised arguments.

Reviewer_ypHtOpenReview ↗
Rating
4(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies restless multi-armed bandits in which budgeted interventions generate source signals that propagate through an unknown, sparse, nonnegative directed graph. The proposed N-GDOI algorithm combines scheduled, derivative-weighted Fisher exploration, sparse nonlinear graph estimation, and optimistic Monte Carlo rollout planning over columnwise ℓ₁ confidence sets of graphs. The theoretical analysis establishes graph-recovery guarantees under adaptive observations (Theorem 1), restricted Fisher curvature from exploration (Theorem 2), Lipschitz stability of H-step rollout values under graph perturbations (Theorem 3), and a per-round error decomposition (Theorem 4). These results yield Õ(T^{2/3}) truncated rollout regret, improving to Õ(√T) under persistent excitation. Synthetic experiments (N = 30, SBM graphs, identity/sigmoid/softplus links) report the largest improvements in cumulative reward and graph-recovery F1 under sigmoid propagation.

Critical strengths

• Well-motivated problem, with a clear understanding of the state of the art and a well-defined methodological contribution. Treating the interaction graph as an unknown dynamical parameter, rather than a feedback or mobility structure, represents a meaningful extension of networked RMABs.

• Very good integration of graph identification and sequential decision-making, supported by theoretical graph-recovery guarantees under adaptive observations.

• The theoretical analysis explicitly accounts for graph-discretization, Monte Carlo, and approximate action-search errors rather than assuming exact planning.

• Under the identity link, N-GDOI performs comparably to Linear-Graph, providing a useful sanity check.

Critical weaknesses

• One concern is related the strong assumptions that are in the work. The nonlinear link σ, persistence parameter α, source-signal functions gᵢ and Δᵢ, local transition kernels, reward functions, and innovation law are assumed known. Moreover, exposures are directly observed. Under these assumptions, graph identification largely reduces to sparse nonlinear regression on observed covariates. The more realistic latent-exposure setting is left for future work.

• Another (minor) concern is regarding the experiments, which are entirely synthetic, with relatively small networks (N ≤ 60) and 10 random seeds. No real-world or semi-synthetic datasets are considered, despite the public-health motivation. The assumed static, sparse, nonnegative graph structure also limits generality.

• An important missing control is N-GDOI with uniform or random exploration under the same exploration schedule. The current "w/o Fisher exploration" ablation removes exploration entirely, confounding the benefits of exploration itself with those of Fisher-based action selection.

• Computational cost: Runtime results are not reported, despite being mentioned in the introduction to Appendix D. This makes it difficult to assess the practical scalability of the approach.

Questions for authors

• How realistic is the Fisher excitation assumption under practical intervention constraints? Can sufficiently informative exploration be guaranteed when available actions are severely restricted?

• How does optimistic planning scale with network size, intervention budget, and graph-confidence-set complexity? Runtime comparisons would be particularly informative.

• How robust is N-GDOI to model misspecification, particularly incorrect nonlinear links, unknown persistence parameters, and inaccurate local transition kernels?

• Could the authors include a controlled comparison between Fisher-guided and random/uniform exploration using the same exploration budget? This would help isolate the actual contribution of derivative-weighted exploration.

Comments on the paper

1 comment

Summary

This paper studies networked restless multi-armed bandits with unknown sparse directed graphs and nonlinear delayed propagation. The authors propose N-GDOI, which combines Fisher-aware exploration, sparse nonlinear graph estimation, and optimistic stochastic rollout planning. The paper establishes graph recovery guarantees and a truncated rollout regret bound of O~(T2/3)\widetilde O(T^{2/3}), improving to O~(T)\widetilde O(\sqrt T) under persistent Fisher excitation.

Strengths

  1. The paper considers an interesting problem combining unknown network structures, nonlinear propagation, and restless bandits.
  2. Derivative-weighted Fisher exploration is a reasonable approach to addressing information loss caused by nonlinear saturation.
  3. The algorithm integrates graph learning and optimistic multi-step planning in a coherent framework.
  4. Experiments include multiple propagation functiones and useful ablation studies.

Weaknesses

  1. Potential gap in theoretical proofs. In Lemma 2, the proof uses non-negativity of the Bregman divergence to establish the sparse cone condition. However, Assumption 2 only guarantees restricted curvature within the sparse cone. The authors should clarify why the required non-negativity holds over the entire localization region.

  2. Insufficient justification of Fisher excitation. Theorem 2 claims that Fisher excitation leads to the nonlinear restricted curvature required by Theorem 1. However, the effects of second-order nonlinear terms and stochastic residuals are not sufficiently addressed.

  3. Algorithm-theory gap. The proposed plug-in information-gain exploration does not necessarily guarantee the oracle Fisher excitation condition. Similarly, the burn-in localization procedure lacks a concrete sample complexity guarantee.

  4. Computational feasibility. The construction of finite graph candidate sets and the required covering radius are insufficiently explained. Moreover, the theoretical analysis requires increasing Monte Carlo rollout counts, whereas experiments use a fixed count of 16.

  5. Limited experimental validation. Experiments use only 10 seeds, and important implementation details and runtime comparisons are missing. The relationship between the theoretical approximation assumptions and the practical beam-search implementation also remains unclear.

Questions for Authors

  1. Can the authors rigorously justify the cone-condition argument in Lemma 2?
  2. How does Fisher excitation guarantee nonlinear restricted strong convexity?
  3. Can the proposed exploration algorithm guarantee the required Fisher excitation?
  4. How are the burn-in localizer and finite graph candidate sets constructed with theoretical and computational guarantees?

Rating: Weak acceptance

Confidence: 2

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.