Projection-Free Bandit Online Optimization for Multi-Agent Systems with Dynamic Regret
2026-08-31 • Distributed, Parallel, and Cluster Computing
Distributed, Parallel, and Cluster Computing
AI summaryⓘ
The authors study a way for multiple agents to make good decisions over time when the rules and goals keep changing, and when they don't have a perfect model of the system. They create an algorithm that only uses the outcomes of past actions (not the system details) to learn how to improve. Their method cleverly estimates gradients from limited information and respects constraints without costly calculations. They prove their approach performs well theoretically and show it works through simulations.
distributed optimizationonline convex optimizationbandit algorithmszeroth-order estimatorconditional gradient methoddynamic regretmulti-agent systemsinput constraintstime-varying cost functionsprojection-free updates
Authors
Xia Jiang, Lu Liu, Gang Feng
Abstract
This paper investigates distributed online optimization for multi-agent dynamical systems with constrained inputs and time-varying cost functions. While online convex optimization offers a principal framework for sequential decision-making, existing online learning and optimization algorithms typically require accurate system models, limiting their applicability in practical settings. To overcome this challenge, we propose a distributed bandit online feedback optimization algorithm that relies solely on real-time input-output data. The algorithm employs a smoothing zeroth-order one-point estimator to construct local gradient approximations directly from cost evaluations. Additionally, to enforce input constraints effectively, we integrate a projection-free conditional gradient update, making the algorithm well-suited for online and large-scale settings. Furthermore, we establish a sublinear dynamic regret bound that depends on a temporal variation measure of system non-stationarity. Finally, numerical simulations demonstrate the effectiveness of the proposed algorithm.