- 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 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
-
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.
-
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.
-
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.
-
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
-
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.
-
The graph-estimation guarantee relies on an insufficiently specified initialization. Assumption 2 requires the burn-in localizer to satisfy . 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 . Since an inaccurate localizer can exclude the true graph from the regression domain, this is consequential for the subsequent guarantees.
-
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 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.
-
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
-
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?
-
How are the burn-in localizers and 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.
-
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?
-
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?
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.