Differentially private matroid bandits for online network topology optimization

Efficient and adaptive network topology design is fundamental in communication systems. A key problem is to construct low-cost structures like minimum spanning trees (MSTs) from uncertain and stochastic link measurements. However, topology and link data often reveal sensitive attributes, including location and traffic patterns, posing privacy risks. We propose Differentially Private Matroid Bandits, an online learning framework for consecutive MST construction with formal privacy guarantees. Modeling the problem as stochastic optimization over a matroid, we develop algorithms that balance exploration and exploitation while ensuring differential privacy in both central and local models. We establish regret upper bounds capturing the trade-offs among privacy, accuracy, and structural complexity. Experiments on real network data show our approach achieves near-optimal performance with strong privacy protection.