Certifiable action-space compression and surrogate-guided search guarantees for deep reinforcement learning network topology optimization

Deep reinforcement learning (DRL) systems such as DRL-GS/A2C-GS search over hand-compressed action sets, guided by an exact verifier and a graph-neural-network surrogate classifier, to optimize network topology under operator management constraints - but every component is problem-specific and only empirically validated: the compressed action options are designed from prior knowledge, the surrogate's classification threshold and its accuracy-based switching rule are fixed a priori rather than derived from any guarantee, and no theorem relates surrogate accuracy to the quality of the output topology or bounds the search relative to the global optimum. The open problem is to give this methodology certifiable foundations: automatic construction of compressed action sets with a certified bound on the optimality loss, a formal link between surrogate fidelity and the final feasible-objective quality, and an end-to-end performance guarantee for the constrained topology-optimization problem.

Background

Network topology optimization asks how to choose the set of communication links of a transport network (over given node locations and node types) so that an operator objective - for example, balancing bandwidth utilization across links over a daily traffic cycle - is optimized, subject to management constraints imposed by operations, such as limits on the fraction of changed links, modification costs, or per-node utilization rules. Because a topology over $m$ candidate links is a $0/1$ vector, the design space grows as $2^{m}$, and the management constraints are nonlinear and can be nonconvex; classical exact optimization (e.g., mixed-integer programming) and hand-tuned local heuristics from human experts scale poorly and carry no global quality certificate.

Li et al. (IEEE Transactions on Communications, 2023; preprint arXiv:2204.14133) formulated this problem abstractly (referred to as NetTopoOpt: maximize an objective value $f(x) = U(x) + \gamma\,Cost(x,x_0)$, with weight $\gamma<0$, over feasible topology vectors $x$ subject to a feasibility mask $M(x)=True$ and to distance and link-load constraints, so that a larger $f$ is better) and proposed a deep reinforcement learning (DRL) pipeline, DRL-GS (called A2C-GS in the 2022 preprint version), with three components. First, a Verifier - based on breadth-first-search (BFS) enumeration of candidate paths plus a SelectBestPath disambiguation heuristic - checks feasibility of a candidate topology and computes its exact objective value, returning a fixed low value ($-10$ in the implementation) for an infeasible topology. Second, a graph neural network (GNN) surrogate - a message-passing neural network over the topology graph, where each layer aggregates information from neighboring nodes - is trained as a thresholded good/poor classifier (label 1 if the objective value is at least a threshold $q$; the source describes $q$ as a hyperparameter determined by grid search, and uses $q=0.8$ on the 8-node instance and $q=0.6$ on the 23-node instance) and replaces the costly Verifier as the reward signal once its test accuracy reaches 95%. Third, an action-compression scheme replaces the full $2^{m}$ edge-toggle space (for the 23-node, 72-edge real-world instance from a China Mobile dataset, roughly $4.7\times 10^{21}$ topologies) by a small hand-designed set of per-step options, so that a policy-gradient RL agent (advantage actor-critic, A2C, or PPO) can search tractably. Experiments show the method beats one-step expert heuristics and random baselines on average; the reported surrogate accuracy exceeds 99%.

The method, however, is purely empirical. The compressed option sets are constructed from problem-specific prior knowledge, with no argument that good or optimal topologies remain reachable in the compressed space; the threshold $q$ and the 95% switching rule are fixed a priori, with no analysis of when trusting the surrogate is safe; and no theorem relates the surrogate's classification accuracy to the final feasible-objective value of the output topology, nor bounds the DRL search's performance relative to the global optimum. Related DRL network-planning systems (e.g., NeuroPlan of Zhu et al., SIGCOMM 2021) are likewise guarantee-free. Classical approximation algorithms for structured network-design problems exist (e.g., the Williamson-Shmoys design framework), but not for this constrained operator-objective formulation. Existing guarantee frameworks for learned combinatorial optimization - probabilistic unsupervised methods with provable approximation guarantees (Karalias and Loukas), generalization bounds for surrogate policies paired with a combinatorial oracle (Aubin-Frankowski et al.), surrogate models with integer-valued optima (Bliek et al.), and algorithms with predictions for graph problems (Aamand et al.) - address different settings and do not cover a verifier-gated surrogate guiding RL search over compressed action spaces under management constraints.

Problem Statement

The open problem is to put DRL-based network topology optimization under management constraints on a certifiable footing. For the NetTopoOpt problem class - feasibility-masked, management-constrained maximization of an operator objective $f$, as instantiated by the 23-node China Mobile link-load-balancing case, which is the reference instance rather than a restriction of the class - the following three deliverables describe the certification sought, with deliverable 3 as the umbrella objective that deliverables 1 and 2 feed into.

1. Automatic action-space compression with guarantees. Develop a general methodology that, given an arbitrary network instance and constraint family, constructs a compressed action set without problem-specific hand design, together with a certified bound on the optimality loss $\mathrm{OPT} - \max_{x \text{ feasible},\, x \in \mathcal{C}} f(x)$ caused by searching only within the constructed compressed action space $\mathcal{C}$, where $\mathrm{OPT}$ is the maximum of $f$ over feasible topologies (or a proof that no loss occurs under explicitly stated conditions). Here "compressed" is quantitative, as in the source: the constructed option sets must be substantially smaller than the full $2^{m}$ edge-toggle space they replace - for the 23-node instance the source reduces $2^{72}\approx 4.7\times 10^{21}$ toggle options to pre-specified per-step option sets, whose unrestricted step-3 and step-4 choices it already counts in the millions - so a methodology that returns the full edge-toggle space (the source's own $C_a=1$ "full space" choice) does not satisfy this deliverable. Likewise, the "stated conditions" under which no loss occurs must be conditions on the instance and the constraint family that are checkable independently of the answer, and may not themselves presuppose the conclusion, for example by assuming that the compressed set contains a global optimizer.

2. Surrogate-fidelity to solution-quality guarantee. Establish a formal relationship between the fidelity of the learned surrogate (its classification accuracy relative to the threshold $q$, and the verifier-gated switching policy that trusts the surrogate above a fixed accuracy level) and the final feasible-objective value achieved by the RL agent: conditions under which bounded surrogate error implies bounded suboptimality of the output topology, including what such a guarantee implies for the choice of $q$ and of the switching level. The conditions must be non-vacuous for an imperfect surrogate: they must be expressible in terms of quantities measurable for a trained surrogate, such as its classification accuracy relative to $q$, rather than requiring the surrogate to be error-free on the reachable set or to coincide with the Verifier, and they must state the domain over which accuracy and suboptimality are measured (per-instance, distributional, or worst-case) together with what the constants in the resulting bound depend on. Suboptimality is measured against $\mathrm{OPT}$, consistent with the source's maximization convention.

3. End-to-end performance guarantee. Provide a theoretical performance or approximation bound for the overall search method (verifier, surrogate, compressed-space DRL agent) with respect to the global optimum of the constrained topology problem, stated in the source's maximization convention - for example $f(x_{\text{out}}) \geq \rho\,\mathrm{OPT}$ with an explicit $\rho>0$, or an explicit additive loss bound - together with the notion of guarantee being claimed (per-instance, distributional, or competitive). The bound must be non-trivial: $\rho = 0$, or any bound that is also satisfied by the fixed low value the Verifier assigns to infeasible topologies, certifies nothing about output quality.

These deliverables compose into one scientific objective: an automated topology-search methodology whose output quality is certified rather than only empirically observed. All three deliverables are required. Deliverable 3 is the umbrella guarantee, and deliverables 1 and 2 are its component bounds, which must be established as separate results regardless of the form the end-to-end analysis takes, since the loss caused by action compression and the loss caused by surrogate-guided search are both properties of the pipeline being certified. The source's lower-level concerns are scoped as follows: the setting of the gating parameters (the threshold $q$ and the switching accuracy level) belongs to deliverable 2, which asks what a fidelity-to-quality guarantee implies for their choice; the verifier's BFS-enumeration cost on larger networks concerns the running cost of the exact-semantics oracle rather than the certification of output quality, and lies outside the target of this statement.

References

1. Zhuoran Li, Xing Wang, Ling Pan, Lin Zhu, Zhendong Wang, Junlan Feng, Chao Deng, Longbo Huang. Network Topology Optimization via Deep Reinforcement Learning. IEEE Transactions on Communications 71(5):2847-2859, 2023. DOI: 10.1109/TCOMM.2023.3244239 (preprint arXiv:2204.14133). https://doi.org/10.1109/TCOMM.2023.3244239
2. Hang Zhu, Varun Gupta, Satyajeet Singh Ahuja, Yuandong Tian, Ying Zhang, Xin Jin. Network planning with deep reinforcement learning. Proceedings of the ACM SIGCOMM 2021 Conference, pp. 258-271, 2021. DOI: 10.1145/3452296.3472902. https://doi.org/10.1145/3452296.3472902
3. David P. Williamson, David B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011. ISBN 9780521195270, DOI: 10.1017/cbo9780511921735. https://doi.org/10.1017/cbo9780511921735
4. Nikolaos Karalias, Andreas Loukas. Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs. arXiv:2006.10643, 2020. https://arxiv.org/abs/2006.10643
5. Laurens Bliek, Sicco Verwer, Mathijs de Weerdt. Black-box Combinatorial Optimization using Models with Integer-valued Minima. arXiv:1911.08817, 2019. https://arxiv.org/abs/1911.08817
6. Pierre-Cyril Aubin-Frankowski, Yohann De Castro, Axel Parmentier, Alessandro Rudi. Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems. arXiv:2407.17200, 2024. https://arxiv.org/abs/2407.17200
7. Anders Aamand, Justin Y. Chen, Siddharth Gollapudi, Sandeep Silwal, Hao Wu. Improved Approximations for Hard Graph Problems using Predictions. arXiv:2505.23967, 2025. https://arxiv.org/abs/2505.23967
8. Mohammed Ali, Florent Duchesne, Ghassan Dahman, François Gagnon, Diala Naboulsi. New Approaches for Network Topology Optimization Using Deep Reinforcement Learning and Graph Neural Network. IEEE Access 13:85447-85460, 2025. DOI: 10.1109/ACCESS.2025.3569236. https://doi.org/10.1109/ACCESS.2025.3569236
9. Nuowen Kan, Sa Yan, Junni Zou, Wenrui Dai, Xing Gao, Chenglin Li, Hongkai Xiong. GDPlan: Generative Network Planning via Graph Diffusion Model. IEEE Transactions on Networking 33(4):1422-1437, 2025. DOI: 10.1109/TON.2025.3535518. https://doi.org/10.1109/TON.2025.3535518
10. Liang Qin, Xingyu Liu, Wenting Wei, Xiaoshan Yu, Huaxi Gu. TopoCrafter: Toward Highly Reliable Optical-Circuit-Switched HPC/AI Interconnects via Dual-Agent DRL. IEEE Transactions on Cognitive Communications and Networking 12:11277-11292, 2026. DOI: 10.1109/TCCN.2026.3720365. https://doi.org/10.1109/TCCN.2026.3720365
11. Yu Yuan, Foyuan Nie, Zi Chen, Yufan Yuan, Yan Wei, Fengzhong Qu. RLMA-UNTO: Reinforcement Learning and Metaheuristic Algorithms-Based Intelligent Topology Optimization for UASNs. IEEE Internet of Things Journal 13(10):22440-22461, 2026. DOI: 10.1109/JIOT.2026.3670148. https://doi.org/10.1109/JIOT.2026.3670148