Source-linked AI summary
Projection-Free Bandit Online Optimization for Multi-Agent Systems with Dynamic Regret
Xia Jiang, Lu Liu, Gang Feng
TL;DR
The paper addresses distributed online optimization for multi-agent dynamical systems whose models are unknown and whose costs vary over time. It proposes a distributed bandit feedback algorithm using real-time input-output data, smoothing one-point estimates, and projection-free updates. The method achieves sublinear dynamic regret with explicit dependence on temporal variation, and simulations demonstrate its effectiveness.
Problem
Existing distributed online optimization methods typically require accurate system models, while model-free approaches remain limited for nonlinear systems with time-varying cost functions.
Method
DPFOA uses real-time input-output measurements for smoothing zeroth-order local gradient estimates, distributed aggregation, and projection-free conditional-gradient updates under input constraints.
Results
The proposed distributed online algorithm achieves a sublinear dynamic regret bound with explicit dependence on temporal variation, and simulations demonstrate its effectiveness.
Takeaways & Limitations
The framework supports model-free distributed online optimization for constrained multi-agent dynamical systems using only real-time feedback.
Abstract
from arXiv · showhide
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.
I. INTRODUCTION
The paper targets distributed online optimization for nonlinear multi-agent systems when dynamics and time-varying objectives are unknown, using only input-output feedback. It proposes DPFOA, combining bandit gradient estimation with projection-free distributed updates and establishes a sublinear dynamic regret guarantee.
- Existing distributed online optimization methods often overlook dynamical constraints, leaving a gap between online learning and real-time cyber-physical systems.
- Model-free approaches remain limited for nonlinear dynamical systems with time-varying costs because many require persistently exciting data, LTI systems, or constant objectives.
- The paper proposes a distributed bandit online learning framework for multi-agent systems with input constraints and unknown system dynamics.
- DPFOA integrates a smoothing one-point gradient estimator with a conditional-gradient update to avoid projections and suppress network propagation of gradient-estimation errors.
- The analysis establishes a sublinear dynamic regret bound that explicitly captures temporal variation in system non-stationarity.
- The paper includes numerical experiments demonstrating the effectiveness of the proposed approach.
II. PROBLEM DESCRIPTION AND ALGORITHM DESIGN
The problem is distributed online optimization for heterogeneous nonlinear agents with constrained inputs, time-varying costs, and unknown disturbances or system maps. DPFOA uses real-time output feedback to estimate gradients, aggregate neighbor information, perform conditional-gradient updates, and apply exploratory inputs without projections.
- Problem formulation: Each heterogeneous agent is modeled by a stable nonlinear steady-state input-output map, with local costs depending on its input and corresponding output.
- Problem formulation: Agents cooperatively optimize a global time-varying objective using decentralized inputs and locally observed system outputs.
- Problem formulation: The reformulated objective substitutes the steady-state map into each local cost, while standard solvers would require explicit knowledge of that map and the disturbance.
- Algorithm design: DPFOA estimates local gradients from real-time output measurements, combines historical local estimates with neighbor information, and applies a projection-free conditional-gradient update.
- Algorithm design: Uniform unit-sphere perturbations address the constraint boundary issue caused by unbounded Gaussian exploration.
- Algorithm design: A shrunk feasible set can ensure perturbed inputs remain feasible without changing the algorithmic structure or theoretical results.
III. PERFORMANCE ANALYSIS
The analysis defines dynamic regret against a time-varying centralized optimum and bounds the estimator, consensus, and update errors underlying the proposed algorithm. With selected stepsizes, the resulting dynamic regret is sublinear and explicitly depends on temporal variation.
- Regret metric: Dynamic regret measures each agent’s accumulated gap from the time-varying optimal centralized benchmark.The benchmark minimizes the aggregate reduced objective at each time step.
- Estimator bounds: The local gradient estimators g_i,t and tracking variables a_i,t remain uniformly bounded by a constant β.The bound holds for every agent and time under the stated assumptions.
- Consensus error: Consensus analysis bounds the cumulative deviation between each agent’s decision variable w_i,t and the network average w̄_t.The projection operator’s Lipschitz continuity is used in deriving this deviation bound.
- Regret decomposition: The proof separates bandit estimation, gradient-tracking consensus mismatch, spatial variation, and temporal variation when bounding regret.The auxiliary estimator is unbiased for the smoothed reduced objective gradient, while temporal variation is controlled through the assumptions on changing costs.
IV. NUMERICAL SIMULATION
Simulations on a connected ten-agent network compare DPFOA with distributed DESA for tracking a moving target and minimizing dynamic regret. Both algorithms track asymptotically and exhibit sublinear regret, while DPFOA converges faster, tracks more closely, and achieves lower regret.
- Setup: The experiment uses an undirected connected network of n = 10 heterogeneous agents with time-varying private loss functions and independently sampled disturbances and coefficients.The input constraint is U = {u|∥u∥1 ≤2}, and agents cooperatively track a moving target.
- Methods: DPFOA and DESA are both model-free distributed feedback methods, with DESA augmented by an average-consensus step.The comparison evaluates both methods on the same distributed online optimization problem.
- Tracking performance: Both algorithms asymptotically track the moving target, but DPFOA converges faster and stays closer to the target while DESA has larger transient deviations.The comparison uses the target trajectory c_t and average output ȳ_t.
- Regret performance: Both algorithms show decreasing time-averaged worst-case regret, confirming sublinear regret behavior.The reported quantity is R̄_t/t, where R_t is the maximum regret across agents.
- Regret performance: DPFOA achieves substantially faster regret decay and a much lower regret level than DESA.The paper presents this result as evidence of superior efficacy and tracking accuracy.
V. CONCLUSION
The paper develops a distributed projection-free bandit online feedback optimization algorithm for constrained multi-agent dynamical systems with time-varying costs. It uses real-time input-output data without a system model, establishes sublinear dynamic regret, and demonstrates effectiveness numerically.
- Conclusion: The proposed algorithm addresses distributed online optimization for multi-agent dynamical systems with constrained inputs and time-varying cost functions.It is a projection-free bandit online feedback optimization method.
- Conclusion: A smoothing zeroth-order one-point estimator constructs local gradient approximations from real-time input-output data without requiring a system model.Distributed global gradient estimators are integrated into the approach.
- Conclusion: A projection-free conditional gradient update handles input constraints and supports scalability in large-scale networked systems.The update is combined with distributed global gradient estimators.
- Conclusion: The distributed online algorithm achieves a sublinear dynamic regret, and numerical simulations illustrate its effectiveness.Future work includes communication-efficient implementations and additional safety or state constraints.