Recently, the research paper "Adversarial Network Optimization under Bandit Feedback: Maximizing Utility in Non-Stationary Multi-Hop Networks" by Professor Longbo Huang's team from the Institute for Interdisciplinary Information Sciences (IIIS) at Tsinghua University was honored with the Best Paper Award. The award was announced at ACM SIGMETRICS 2025, the premier international conference in the field of measurement and analysis of computer systems.
Professor Longbo Huang's research team explores the classic problem of "Stochastic Network Optimization (SNO)" in network systems. This problem considers how to optimally allocate resources in dynamic network systems to maximize various objectives like throughput and system utility, with important applications in areas including network communication, computation scheduling, and operations management. Traditional SNO algorithms typically require network conditions (e.g., channel quality, transmission bandwidth, and job arrival rates) to have stable distributions and be known to the planner before each allocation is made, making them difficult to apply directly in many important dynamic and unknown real-world scenarios.
Addressing these limitations, Professor Longbo Huang's research team proposed a new network system model, "Adversarial Network Optimization (ANO)," and designed a novel optimization algorithm. The algorithm guarantees long-term network stability as well as superior utility maximization performance in arbitrarily complex multi-hop networks, even when network conditions are dynamic and adversarial and feedback is extremely limited. The algorithm first combines ANO performance with adversarial online learning modeling through a global Lyapunov analysis. To tackle the inherent challenges of network optimization, such as unbounded and fluctuating queue lengths, the paper presents novel and customized queue-aware online learning algorithms to achieve adaptivity. Finally, utilizing a self-bounding analysis, the total number of jobs in the network system is controlled by a polynomial of itself, thereby providing throughput guarantees for the network system and concluding that the system utility converges to its optimal value at a polynomial rate.
The first author of the paper is Yan Dai, a 2024 alumni from the IIIS Yao Class, and the corresponding author is Professor Longbo Huang from IIIS.
Paper Link:
Editor: Li Han
