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

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 $\tilde{\mathcal{O}}(T^{2/3})$ truncated rollout regret over time horizon $T$ under scheduled Fisher-informative exploration, improving to $\tilde{\mathcal{O}}(\sqrt{T})$ 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.