Projection-Free Bandit Online Optimization for Multi-Agent Systems with Dynamic Regret

1

Projection-Free Bandit Online Optimization for Multi-Agent Systems with Dynamic Regret

arXiv:2608.30159v1 [cs.DC] 31 Aug 2026

Xia Jiang, Lu Liu, Senior Member, IEEE, and Gang Feng, Fellow, IEEE

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. Index Terms—bandit feedback, projection-free method, online optimization, distributed optimization, dynamic regret

I. I NTRODUCTION The framework of online convex optimization (OCO) serves as a fundamental tool for modeling sequential decision processes in uncertain environments, offering systematic tools for handling unknown and time-varying cost functions. In the classical OCO setting, a learner makes decisions in a step-bystep manner while facing time-varying and initially unknown cost functions. The quality of these decisions is typically assessed through regret, which measures the performance gap between the learner’s accumulated loss and that of the best fixed decision chosen in hindsight. This paradigm is of significant importance in many practical control applications such as robot formation control [1], target tracking [2] and energy flow management [3]. Moreover, in many large-scale networked systems, such as smart grids [4] and intelligent transport [5], the information of the concerned systems is geographically distributed across separated physical nodes, necessitating scalable distributed online optimization (DOO) algorithms. In such multi-agent networks, each node operates as an autonomous decision-making agent that updates its actions based on local information and communicates with This work was supported by the Research Grants Council of Hong Kong under Grant CityU-11208223. This paper was not presented at any conference. Corresponding author is Lu Liu. X. Jiang is with the School of Electrical and Electronic Engineering, Nanyang Technological University, Singapore 639798, Singapore (email: xia.jiang@ntu.edu.sg). L. Liu and G. Feng are with the Department of Mechanical Engineering, City University of Hong Kong, Hong Kong, China (email: luliu45@cityu.edu.hk, megfeng@cityu.edu.hk).

its neighbors to collectively optimize the global performance under time-varying objectives and environmental disturbances. Motivated by the need for real-time decision-making in networked systems, considerable efforts have been devoted to developing DOO algorithms, leading to the distributed online dual averaging algorithm [6], [7], distributed online primal-dual algorithms [8]–[10], and distributed online gradient tracking algorithms [11] within the OCO framework. Despite this significant progress, most existing DOO methods overlook the dynamical constraints inherent in physical systems. Consequently, a fundamental gap arises when bridging distributed online learning theory with the real-time operation of complex cyber-physical systems. While some studies have successfully incorporated OCO methodologies into the control of linear dynamical systems, addressing challenges such as external disturbance [12], inequality constraints [13], and output feedback [14], [15], these works critically rely on the availability of accurate model knowledge. In practical scenarios, however, obtaining precise models of the concerned systems is often infeasible due to their inherent nonlinearities, unmodeled dynamics, and environmental variations. To reduce the dependence on accurate system models, datadriven control has emerged as a promising model-free alternative. Recent works have proposed resilient data-driven model predictive controllers that are robust to measurement noise [16] and denial-of-service attacks [17], building on behavioral systems theory and historical input–output data. Nevertheless, such approaches typically require persistently exciting input–output data and are restricted to linear time-invariant (LTI) systems. These methods generally assume constant cost functions, treating temporal variations merely as disturbances rather than as part of the optimization objective. In parallel, feedback-based sensitivity learning methods [18]–[20], such as extremum seeking, estimate gradients through perturbations but focus mainly on steady-state optimality. While classical extremum seeking and recent stochastic derivative-free methods [19], [20] have explored stochastic perturbations and averaging to handle time-varying objectives, they primarily offer asymptotic convergence for static problems. Their transient learning performance under non-stationary environments, typically evaluated via dynamic regret, has received very limited attention. Furthermore, extending these methods to general nonlinear systems remains difficult. These observations reveal a remaining gap in the development of effective algorithms capable of achieving online optimization for nonlinear dynamical systems with time-varying cost functions by using only input-output data while with no knowledge of the system model. Recent advancements [21]–

2

[23] in data-driven optimization with bandit feedback provide a useful foundation, showing that zeroth-order gradient-free methods can estimate descent directions from cost evaluations by exploiting system outputs as surrogates for analytical gradients. However, most approaches are tailored for centralized settings and restricted to steady-state optimization with constant cost functions. While some recent efforts have explored bandit feedback for distributed online settings, such as in aggregative games [24] and event-triggered optimization under constraints [25], applying these approaches broadly to DOO still faces theoretical and computational challenges. Theoretically, relying solely on limited local observations induces gradient estimation variance [26], which couples tightly with network consensus drift in time-varying environments. Additionally, standard projection-based methods suffer from computational burdens under complex constraints, making them impractical for real-time systems. To bridge this gap, this paper proposes a novel distributed bandit online learning framework for multi-agent systems with input constraints. Specifically, we develop a projection-free distributed feedback optimization algorithm that integrates a smoothing one-point gradient estimator with a network-level conditional gradient update. This framework addresses the coupled challenges of unknown system dynamics and nonstationary environments. The main contributions of this work are summarized as follows. We establish a model-free distributed online optimization framework for multi-agent systems with unknown nonlinear dynamics. Unlike standard OCO with explicit analytical models, our formulation directly exploits system-induced objective functions via real-time inputoutput measurements, thereby bridging distributed online learning theory with the real-time operation of complex cyber-physical systems without requiring explicit model knowledge. • We develop the distributed projection-free feedback optimization algorithm (DPFOA) that overcomes the coupled challenges of zeroth-order estimation variance and network consensus drift. Rather than a heuristic combination of existing methods, our approach embeds a smoothing one-point gradient estimator into a refined conditional gradient step. This structural design simultaneously bypasses computationally expensive projection operations and effectively suppresses the propagation of gradient approximation errors across the network. • We establish a rigorous sublinear dynamic regret bound that explicitly captures the impact of temporal variation in system non-stationarity. The theoretical breakthrough lies in decoupling and bounding the intertwined effects of bandit estimation errors, gradient tracking consensus mismatch, and dynamic temporal variations. This analysis provides the theoretical performance guarantees for bandit online control and explicitly quantifies how underlying system non-stationarity scales the regret bound in distributed zeroth-order settings.

•

The remainder of the paper is organized as follows. Section II introduces the problem formulation and presents the dis-

tributed online feedback optimization algorithm. Theoretical guarantees on its regret performance are provided in Section III. Numerical experiments demonstrating the effectiveness of the proposed approach are presented in Section IV, followed by concluding remarks in Section V. Mathematical Notations: Throughout this work, let R denote the set of real numbers and Rn the n-dimensional Euclidean space. For a positive integer n, we use [n] := 1, . . . , n. The transpose of a vector v is denoted by v ⊤ , and h·, ·i represents the standard inner product. The symbol ∇f denotes the gradient of a differentiable function f . The communication structure among agents is described by an undirected graph G = (V, E, A), where V = {1, · · · , n} is the node set and E ⊆ V × V is the edge set. Let A = [Aij ] denote the associated adjacent matrix, where Aij > 0 if agents i and j are connected, and Aij = 0 otherwise. For each agent i, its neighbor set is defined as Ni = {j ∈ V : (i, j) ∈ E}. II. P ROBLEM DESCRIPTION AND ALGORITHM DESIGN This paper investigates an online optimization problem for a multi-agent system comprising n heterogeneous agents. Each agent, say agent i, is associated with a stable dynamical sytem that is abstracted by its nonlinear steady-state input-output map hi : Rp × Rr → Rq described as follows: yi = hi (ui , d), p

(1)

q

where ui ∈ R is the input, yi ∈ R is the output, and d ∈ Rr is an unknown but bounded exogenous disturbance. Throughout this work, we do not assume any explicit knowledge of the steady-state map hi . Within the multi-agent network, the agents aim to cooperatively solve a global online optimization problem. Assume that agent i has access to a local, time-varying cost function Ψi,t (ui , yi ), which depends on its input ui and the corresponding output yi . At every time step t, agent i computes its control input ui,t in a decentralized manner and applies it to the underlying dynamical system. Then, the current cost functions Ψi,t is revealed to the agent. Let ut , [u1,t , · · · , un,t ] ∈ Rp×n and yt , [y1,t , · · · , yn,t ] ∈ Rq×n denote the stacked vectors of local inputs and outputs, respectively. The global online optimization problem is formulated as follows: min Ψt (u, y) = u,y

n X

Ψi,t (ui , yi )

i=1

s.t.

y = h(u, d), ui ∈ Ω,

(2)

p

where Ω ⊆ R is the input constraint set and h = [h1 , · · · , hn ] is the aggregate steady-state map. By eliminating y via the steady-state relation, problem (2) can be equivalently reformulated as an unconstrained optimization problem, min Ψ̃t (u) = u

n X i=1

Ψ̃i,t (u),

s.t. u ∈ Ω,

(3)

where Ψ̃i,t (u) = Ψi,t (ui , hi (ui , d)) is the reformulated objective function after substituting the steady-state map. Most existing numerical optimization solvers require an explicit analytical model of the steady-state map h as well

3

as the exact value of the disturbance d. However, such information is often difficult or impossible to obtain in the presence of complex system dynamics and unknown external perturbations. To address these challenges, we develop a feedback-based optimization controller that solely utilizes realtime output measurements to iteratively drive system (1) to an operating point that minimizes the global objective function (2). We make the following assumptions throughout this paper. Assumption II.1. The function Ψi,t is G-Lipschitz over the compact set Ω, i.e. for u1 , u2 ∈ Ω and y1 , y2 ∈ Rq ,

Algorithm 1 Distributed projection-free feedback optimization algorithm (DPFOA) for each agent i ∈ [n] 1: Initialize: stepsizes ρ, η, δ and σt , ui,0 , wi,0 ∈ Ω, di,1 = 0, ai,0 = 0, the number of epochs T . 2: for t = 1, · · · , T do 3: One-point gradient estimator: pvi,t (Ψi,t (ui,t , yi,t ) − Ψi,t−1 (ui,t−1 , yi,t−1 )) (6) gi,t = δ ai,t =(1 − ρ)ai,t−1 + ρgi,t (7) 4:

|Ψi,t (u1 , y1 ) − Ψi,t (u2 , y2 )| ≤ Gku1 − u2 k + Gky1 − y2 k. Assumption II.2. The function Ψ̃i,t is M -Lipschitz continuous and convex.

Global gradient estimator: X di,t+1 = Aij dj,t + ai,t

5:

Projection-free conditional gradient step: Fi,t (w) =ηhdi,t , wi + kwk2

si,t =argmins∈Ω h∇Fi,t (wi,t ), si wi,t+1 =wi,t + σt (si,t − wi,t )

Assumption II.3. The constraint set Ω is convex and compact with diameter D, i.e., ku1 − u2 k ≤ D for any u1 , u2 ∈ Ω. Assumption II.4. The multi-agent network is connected and the associated adjacent matrix A = [Aij ] is symmetric and doubly stochastic with non-negative elements.

6:

Assumption II.5. There exists a constant V > 0 such that for i ∈ V and t ≥ 1, the time-varying cost function Ψi,t satisfies

7: end for

|Ψi,t (u, y) − Ψi,t−1 (u, y)| ≤ V, for any feasible input u ∈ Ω and output y ∈ Rq . Remark II.1. Assumptions II.1–II.4 are standard in distributed online optimization and multi-agent systems [27]– [30]. Assumption II.1 imposes a Lipschitz condition on the stage cost, while Assumption II.2 requires the reduced objective Ψ̃i,t (ui ) to be convex and Lipschitz, which ensures that the cost remains well behaved after eliminating the output through the steady-state map. Assumptions II.3 and II.4 further guarantee that the feasible set is compact and that the network can reach average consensus. Assumption II.5 additionally limits the variation of the cost across consecutive time steps, which is standard in dynamic OCO and prevents abrupt changes in the environment or tracking target. Together, these assumptions provide the regularity and boundedness for the convergence analysis. Remark II.2. To streamline the exposition, this article focuses on nonlinear systems that can be abstracted by steady-state input-output maps. For instance, the dynamical model of agent i can be given as xi,t+1 =fi (xi,t , ui,t , d),

(4)

yi,t =gi (xi,t , d).

(5)

where ui,t , xi,t , and yi,t denote the input, state and output variables of agent i, respectively. The functions fi and gi can be different across agents. If the dynamical system (4) admits a unique, globally exponentially stable steady-state map xi,ss (u, d), then the corresponding steady-state output satisfies yi = gi (xi,ss (ui , d), d) , hi (ui , d), thus recovering the steady-state map representation [23].

(8)

j∈Ni

(9) (10) (11)

Input exploration step: ui,t+1 = wi,t+1 + δvi,t+1

(12)

To solve the online multi-agent optimization problem (2), we design a distributed projection-free feedback optimization algorithm (DPFOA) for each agent i summarized in Algorithm 1. In DPFOA, we adopt a zeroth-order one-point gradient estimator to approximate local gradients, eliminating the need for explicit gradient computations. This gradient estimator relies solely on real-time output measurements and thus does not require explicit knowledge of the underlying system model. Moreover, a smoothing step in (7) is introduced to improve the accuracy of the local gradient estimates. Based on these local gradient approximations, each agent constructs a global gradient estimator by using a weighted combination of its historical local gradients and the information received from its neighbors. To handle the input constraints, we apply a projection-free conditional gradient update with the global gradient estimator di,t . The next control input ui,t+1 is then generated by adding an exploration perturbation δvi,t+1 to the candidate solution wi,t+1 , and the resulting signal is applied to the system (4). The presence of the constraint set Ω makes standard Gaussian random vectors vi,t unsuitable for our setting, as the unbounded support of the Gaussian distribution may drive the perturbed input ui,t = wi,t + δvi,t outside Ω. To avoid this issue, we sample vi,t uniformly from the unit sphere Sp−1 , {vi,t ∈ Rp : kvi,t k = 1}, which has been adopted in zeroth-order optimization methods [23], [31], [32]. In this setting, the smoothed approximation Ψ̃i,t,δ (w) for the objective function Ψ̃i,t (w) is defined as Ψ̃i,t,δ (w) = Ev′ ∼U(Bp ) [Ψ̃i,t (w + δv ′ )]

(13)

where w ∈ Rp , and U (Bp ) is the uniform distribution over the closed unit ball Bp = {v ′ ∈ Rp |kv ′ k ≤ 1} in Rp .

4

The properties of the smoothed approximation Ψ̃δ (w) are summarized as follows. Lemma II.1. [33] Suppose that Ψ̃ : Rp → R is M -Lipschitz continuous. Then, for any w ∈ Rp and δ > 0, the smoothed function Ψ̃δ (w) satisfies hp i Ev∈U(Sp−1 ) Ψ̃(w + δv)v = ∇Ψ̃δ (w), (14) δ Ψ̃δ (w) − Ψ̃(w) ≤ M δ. (15) Remark II.3. The local one-point gradient estimator in Algorithm 1 is inspired by existing works [33]–[36]. However, a key distinction lies in the use of the approximate objective function value Ψt (ut , yt ), which relies on real-time output measurements, rather than the exact steady-state objective function Ψ̃t (ut ) = Ψt (ut , h(ut , d)). This difference arises from the lack of model information and the presence of system dynamics, which prevent direct access to steady-state outputs at each time step. Remark II.4. To ensure feasibility of the perturbed input (12), we can adopt a standard technique in bandit optimization based on a shrunk feasible set. Specifically, define Ωδ := {w ∈ Ω : dist(w, ∂Ω) ≥ δ}. By restricting wi,t to Ωδ and noting that kvi,t k ≤ 1, it follows that ui,t ∈ Ω, ensuring that all function evaluations are welldefined. For clarity of presentation, the algorithm is written over the original set Ω. The above restriction can be equivalently imposed without affecting the algorithmic structure or the theoretical results. This technique is widely used in zerothorder and bandit optimization to handle boundary issues. III. P ERFORMANCE ANALYSIS In this section, we analyze the regret performance of the proposed DPFOA. To this end, we introduce the following dynamic regret metric [11], which measures the accumulated difference between the cost incurred by the proposed algorithm and the optimal cost at each time step:

Lemma III.1. Suppose Assumptions II.1-II.3 hold. The local gradient estimators gi,t and ai,t remain uniformly bounded. In particular, there exists a constant β > 0 such that kgi,t k ≤ β and kai,t k ≤ β for all i ∈ V and t. Proof. By the definition of the estimator gi,t , one has p kgi,t k ≤ kvi,t k · |Ψi,t (ui,t , yi,t ) − Ψi,t−1 (ui,t−1 , yi,t−1 )| δ  p ≤ kvi,t k · |Ψi,t (ui,t , yi,t ) − Ψi,t (ui,t−1 , yi,t−1 )| δ | {z } spatial variation

+ |Ψi,t (ui,t−1 , yi,t−1 ) − Ψi,t−1 (ui,t−1 , yi,t−1 )| {z } | temporal variation



Since vi,t is sampled from the unit sphere, it holds that kvi,t k = 1. We first consider the spatial variation. By Assumptions II.1 and II.3, we have |Ψi,t (ui,t , yi,t )−Ψi,t (ui,t−1 , yi,t−1 )| ≤ GD+ Gkyi,t − yi,t−1 k. For the output yi,t = hi (ui,t , d), note that ui,t ∈ Ω and the disturbance d is bounded. Hence, the pair (ui,t , d) lies in a compact set. Under the standard assumption that the steady-state map hi (ui , d) is continuous, it follows that yi,t is uniformly bounded. Therefore, there exists a constant Cy > 0 such that kyi,t k ≤ Cy for all i, t, which implies kyi,t − yi,t−1 k ≤ 2Cy . We obtain |Ψi,t (ui,t , yi,t )−Ψi,t (ui,t−1 , yi,t−1 )| ≤ G(D + 2Cy ). Then, for the temporal variation term, we know |Ψi,t (ui,t−1 , yi,t−1 ) − Ψi,t−1 (ui,t−1 , yi,t−1 )| ≤ V by Assumption II.5. Combining the above bounds, we obtain p kgi,t k ≤ (G(D + 2Cy ) + V ) =: β. δ Next, we show the boundedness of ai,t . Since ai,0 = 0 and ai,t is a linear combinition of ai,t−1 and gi,t in (7), we can prove the boundness of ai,t by induction, i.e. kai,t k ≤ β. Then for all i ∈ V and all time t, it holds that kgi,t k ≤ β and kai,t k ≤ β. This completes the proof.

(16)

The next two lemmas characterize key properties of the global gradient estimator di,t , whose proofs follow directly from Lemma 3 and Lemma 6 in [28], respectively.

where u∗t = argminu∈Ω Ψ̃t (u) denotes the optimal solution at

Lemma III.2. Suppose Assumption II.4 holds. If kai,t k ≤ β, then for any i ∈ V, we have

Ri,T =

n X T  X j=1 t=1

 E[Ψ̃j,t (ui,t )] − Ψ̃j,t (u∗t ) ,

time t. The regret Ri,T is defined from the perspective of agent i, using its local decisions {ui,t }Tt=1 , whilePperformance n is evaluated with respect to the aggregate cost j=1 Ψ̃j,t (·). Thus, Ri,T measures the gap between the network-wide cost incurred by agent i’s decisions and that of the optimal centralized benchmark. We further define a temporal variation metric capturing non-stationarity as DT =

T X t=1

2

k∇Ψ̃i,t,δ (wi,t ) − ∇Ψ̃i,t−1,δ (wi,t−1 )k ,

which follows the standard formulation adopted in [37]. We first establish several technical lemmas. The first lemma provides uniform bounds on the local gradient estimators.

kdi,t+1 − di,t k ≤ αβ, (17) √ 2 (A) where α = 1+σ 1−σ2 (A) n + 1, and σ2 (A) denotes the second largest eigenvalue of matrix A. Lemma III.3. Suppose Assumption II.4 holds. If kai,t k ≤ β, then for any i ∈ V, we have (18)

√ n ′ i=1 di,t and α = 1−σ2 (A) .

Pn 1

where d¯t = n

kdi,t − d¯t k ≤ α′ β,

The following lemma establishes the Lipschitz-continuity of the projection operator, whose proof can be found in Lemma 5 of [29].

5

Lemma III.4. Let ΠΩ (u, η) = argminw∈Ω ηu⊤ w + kwk2 . Then the operator ΠΩ (·, η) is Lipschitz continuous in its first argument, i.e., kΠΩ (w, η) − ΠΩ (v, η)k ≤ ηku − vk. With the above results, we now discuss the consensus error kwi,t − w̄t k for each agent i, where

2 w̄t = argminw∈Ω F̄t (w) with F̄t (w) = η d¯⊤ t w + kwk . (19)

2 Let ŵi,t = argminw∈Ω ηd⊤ i,t w + kwk . Applying Lemma III.4 yields kŵi,t − w̄t k ≤ ηkdi,t − d¯t k ≤ ηα′ β, which implies that

kwi,t − w̄t k ≤kwi,t − ŵi,t k + kŵi,t − w̄t k q ≤ Fi,t (wi,t ) − Fi,t (ŵi,t ) + ηα′ β,

(20)

where the final inequality follows from the definition of σt . This completes the induction and thus the proof. Remark III.1. To satisfy the condition in Lemma III.5, (1−σ2 (A))D √ one can choose η = 2(√n+1+( . With some n−1)σ2 (A))βT 3/4 straightforward analysis, it can be verified that this choice of η indeed fulfills the condition required in Lemma III.5. A detailed derivation can be found in Appendix E of [28]. Using Lemma III.5, we can further bound the consensus error in (20), as stated in the following proposition. Proposition III.1. Suppose Assumptions II.1, II.3 and II.4 hold. The cumulative deviation between wi,t and w̄t over horizon T satisfies T X

where the second inequality holds since Fi,t is 2-strongly convex1 and ∇Fi,t (ŵi,t ) = 0. Define hi,t = Fi,t (wi,t ) − Fi,t (ŵi,t ).

t=1 √

Lemma III.5. Suppose Assumptions II.1, II.3 and II.4 hold. If the stepsizes η and σt = √1t are chosen such that p ηαβ hi,t+1 ≤ σt2 D2 , then, for any i ∈ V and any t = 1, · · · , T , the following bound holds (21)

Proof. Following a similar analysis to Lemma 2 of [28], we obtain

(22)

In addition, by Lemma III.2, we have known that kdi,t+1 − di,t kp≤ αβ. Under the chosen stepsizes choice ensuring ηαβ hi,t+1 ≤ σt2 D2 , the recursion simplifies to

≤2Dt−1/4 + ηα′ β.

By summing from t = 1 to T , we have that for all i ∈ V, T X t=1

Using this recursion, we can prove the bound (21) by induction. For the base case t = 1, by definition, we have hi,1 = Fi,1 (wi,1 ) − Fi,1 (ŵi,t ) 2

= kwi,1 k − kŵi,t k

Next, assume that the bound holds for t. Using the recursion, we show that it also holds for t + 1 : hi,t+1 ≤ (1 − σt ) hi,t + 2D2 σt2

≤ 4D2 σt (1 − σt ) + 2D2 σt2  σt  = 4D2 σt 1 − σt + 2  σt  2 = 4D σt 1 − 2 ≤ 4D2 σt+1 ,

1 A differentiable function F is 2-strongly convex if for all x, y, F (y) ≥ F (x) + ∇F (x)⊤ (y − x) + ky − xk2 .

8 DT 3/4 + ηα′ βT. 3

Using the consensus error bound in (23), we now analyze the regret of the proposed DPFOA algorithm. Without loss of generality, we let u∗t = wt∗ . For any i, j ∈ V, we have T X t=1

=

T X t=1

≤

2

≤ 4D σ1 .

kwi,t − w̄t k ≤

This completes the proof.

hi,t+1 ≤ (1 − σt ) hi,t + 2D2 σt2 .

2

(23)

Proof. Using (20) and Lemma III.5, we have p kwi,t − w̄t k ≤ hi,t + ηα′ β √ ≤2D σt + ηα′ β

where D is the diameter of the constrained set Ω.

hi,t+1 ≤ (1 − σt ) hi,t + σt2 D2 p + η kdi,t+1 − di,t k hi,t+1 .

8 DT 3/4 + ηα′ βT, 3

where α′ = 1−σ2n(A) .

We establish the upper bound of hi,t in the following lemma.

hi,t ≤ 4D2 σt .

kwi,t − w̄t k ≤

≤ ≤ ≤

Ψ̃j,t (ui,t ) −

t=1

t=1

t=1 T  X

T X

Ψ̃j,t (wt∗ )

t=1



Ψ̃j,t (wi,t ) + M kδvi,t k −

Ψ̃j,t (wi,t ) −

T  X

t=1

Ψ̃j,t (u∗t )

Ψ̃j,t (wi,t + δvi,t ) −

T  X t=1 T X

T X

T X

T X

Ψ̃j,t (wt∗ )

t=1

Ψ̃j,t (wt∗ ) + δM T

t=1

T    X Ψ̃j,t,δ (wt∗ )−δM +δM T Ψ̃j,t,δ (wi,t )+δM − t=1

 Ψ̃j,t,δ (wi,t ) − Ψ̃j,t,δ (wt∗ ) + 3δM T,

(24)

where the first inequality follows from the M -Lipschitz continuity of Ψ̃i,t in Assumption II.2 and the third inequality follows from Lemma II.1. Using Assumption II.2 together with the inequality (23), we now analyze the remaining term Ψ̃j,t,δ (wi,t ) − Ψ̃j,t,δ (wt∗ ),

6

which appears on the right-hand side of (24). Specifically, for any i, j ∈ V, we have T X t=1

≤

T X t=1

+

Ψ̃j,t,δ (wi,t ) − Ψ̃j,t,δ (wt∗ ) Ψ̃j,t,δ (wj,t ) − Ψ̃j,t,δ (wt∗ ) +

T X t=1

≤

T X t=1

M kwj,t − w̄t k

M kwi,t − w̄t k

T X

8 ∇Ψ̃j,t,δ (wj,t )⊤ (wj,t − wt∗ )+2M ( DT 3/4 +ηα′ βT ), 3 t=1 (25)

where the first inequality holds by Assumption II.2 and the second inequality follows from (23). we focus on the upper bound for the term PNext, T ⊤ ∗ ∇ Ψ̃ j,t,δ (wj,t ) (wj,t − wt ) appearing on the right-hand t=1 side of (25). For clarity, we define Pt = (∇Ψ̃j,t,δ (wj,t ) − aj,t )⊤ (wj,t − wt∗ ).

(26)

Using the boundedness of Ω, it follows that T X t=1

Pt ≤

T X

k∇Ψ̃j,t,δ (wj,t ) − aj,t kkwj,t − wt∗ k

t=1 T X

≤D

t=1

k∇Ψ̃j,t,δ (wj,t ) − aj,t k.

The next proposition PT provides an upper bound for the cumulative deviation t=1 k∇Ψ̃i,t,δ (wi,t ) − ai,t k.

Proposition III.2. Suppose Assumptions II.1-II.4 hold. If the stepsizes ρ = T1c with c ∈ (0, 1) and δ = T1b with b ∈ (0, 1), we have T h i X E k∇Ψ̃i,t,δ (wi,t ) − ai,t k t=1

1 c 1 p c = O(T 1+b− 2 ) + O(T 2 +b+ 2 ) + O(T c+ 2 ) DT .

Proof. At first,  we define an auxiliary  gradient estimator pvi,t Ψ̃i,t (ui,t ) − Ψ̃i,t (ui,t−1 ) . By (12) in the prog̃i,t = δ posed algorithm and (14) in Lemma II.1, the estimator g̃i,t satisfies Evi,[t] [g̃i,t ] = ∇Ψ̃i,t,δ (wi,t ). Using the smoothing update (7), the term k∇Ψ̃i,t,δ (wi,t ) − ai,t k admits the following bound: k∇Ψ̃i,t,δ (wi,t ) − ai,t k

≤k∇Ψ̃i,t,δ (wi,t ) − (1 − ρ)ai,t−1 − ρgi,t + ρg̃i,t − ρg̃i,t k

≤k∇Ψ̃i,t,δ (wi,t ) − (1 − ρ)ai,t−1 −ρg̃i,t k +kρ(g̃i,t − gi,t )k.

Squaring both sides of the above inequality yields k∇Ψ̃i,t,δ (wi,t ) − ai,t k2

≤(1 + τ )k∇Ψ̃i,t,δ (wi,t ) − (1 − ρ)ai,t−1 − ρg̃i,t k2 1 + (1 + )ρ2 kg̃i,t − gi,t k2 τ ≤(1 + τ )k∇Ψ̃i,t,δ (wi,t ) − (1 − ρ)ai,t−1 − ρg̃i,t k2

+ (1 +

1 )4ρ2 β 2 , τ

(27)

ρ > 0 is chosen such that where the parameter τ = 2(1−ρ) τ < ρ. 1+τ For the term k∇Ψ̃i,t,δ (wi,t ) − (1 − ρ)ai,t−1 − ρg̃i,t k2 , by adding and subtracting the term (1 − ρ)∇Ψ̃i,t−1,δ (wi,t−1 ) within the norm and rearranging terms, we obtain

k∇Ψ̃i,t,δ (wi,t ) − (1 − ρ)ai,t−1 − ρg̃i,t k2  2  2 + ρ′ D̃i,t = ρ ∇Ψ̃i,t,δ (wi,t ) − g̃i,t  2  + ρ′ ∇Ψ̃i,t−1,δ (wi,t−1 ) − ai,t−1 D E + 2ρρ′ ∇Ψ̃i,t,δ (wi,t ) − g̃i,t , D̃i,t E D 2 + 2 (ρ′ ) D̃i,t , ∇Ψ̃i,t−1,δ (wi,t−1 ) − ai,t−1 E D 2 + 2 (ρ′ ) ∇Ψ̃i,t,δ (wi,t )−g̃i,t , ∇Ψ̃i,t−1,δ (wi,t−1)−ai,t−1 ,

where D̃i,t = ∇Ψ̃i,t,δ (wi,t ) − ∇Ψ̃i,t−1,δ (wi,t−1 ) and ρ′ = 1 − ρ. Taking conditional expectation Evi,[t] [·] and using Evi,[t] [g̃i,t ] = ∇Ψ̃i,t,δ (wi,t ), we obtain i h Evi,[t] k∇Ψ̃i,t,δ (wi,t ) − (1 − ρ)ai,t−1 − ρg̃i,t k2    2 2 + ρ′ D̃i,t =Evi,[t] ρ ∇Ψ̃i,t,δ (wi,t ) − g̃i,t E D 2 + 2 (ρ′ ) D̃i,t , ∇Ψ̃i,t−1,δ (wi,t−1 ) − ai,t−1   2 + ρ′ ∇Ψ̃i,t−1,δ (wi,t−1 ) − ai,t−1 . (28) By Young’s inequality, it holds that E D D̃i,t , ∇Ψ̃i,t−1,δ (wi,t−1 ) − ai,t−1 ≤

2 2 ρ 1 D̃i,t . ∇Ψ̃i,t−1,δ (wi,t−1 ) − ai,t−1 + 2 2ρ

(29)

Substituting (29) into (28) and using (1 + ρ1 )ρ′ ≤ ρ1 , we obtain i h Evi,[t] k∇Ψ̃i,t,δ (wi,t ) − (1 − ρ)ai,t−1 − ρg̃i,t k2   2 ≤ρ2 Evi,[t] ∇Ψ̃i,t,δ (wi,t ) − g̃i,t +

2 ρ′ ∇Ψ̃i,t,δ (wi,t ) − ∇Ψ̃i,t−1,δ (wi,t−1 ) ρ

+ ρ′ ∇Ψ̃i,t−1,δ (wi,t−1 ) − ai,t−1

2

.

(30)

Taking total expectation of (30) yields i h E k∇Ψ̃i,t,δ (wi,t ) − (1 − ρ)ai,t−1 − ρg̃i,t k2 i h ≤ρ2 E k∇Ψ̃i,t,δ (wi,t ) − g̃i,t k2 i 1−ρ h + E k∇Ψ̃i,t,δ (wi,t ) − ∇Ψ̃i,t−1,δ (wi,t−1 )k2 ρ i h (31) + (1 − ρ)E k∇Ψ̃i,t−1,δ (wi,t−1 ) − ai,t−1 k2 .

Furthermore, the variance term satisfies h i E k∇Ψ̃i,t,δ (wi,t ) − g̃i,t k2

7

i  h pv  i,t Ψ̃i,t (ui,t ) − Ψ̃i,t (ui,t−1 ) −∇Ψ̃i,t,δ (wi,t )k2 =E k h pvδ   i i,t ≤E k Ψ̃i,t (ui,t ) − Ψ̃i,t (ui,t−1 ) k2 δ 2M 2 p2 2 2 ≤ (σt D + 4δ 2 ) δ2 2M 2 p2 2 ≤ (D + 4δ 2 ) = O(T 2b ), (32) δ2 where the first inequality holds since the variance is bounded by the second moment, the second inequality follows from Assumptions II.2 and II.3 and we use δ = T −b in the last equality. Taking expectation of (27), summing from t = 1 to T and using (31), (32), we have T X t=1

Finally, by Cauchy–Schwarz, we have T h i X E k∇Ψ̃i,t,δ (wi,t ) − ai,t k

t=1 v u T i u X h ≤tT E k∇Ψ̃i,t,δ (wi,t ) − ai,t k2 .

It then follows from (33) and (34) that

T h i X E k∇Ψ̃i,t,δ (wi,t ) − ai,t k t=1

√ ≤ τ ′ T 1+b

h i E k∇Ψ̃i,t,δ (wi,t ) − ai,t k2

≤(1 + τ )ρ2

T X t=1

√ + τ′

i h E k∇Ψ̃i,t,δ (wi,t ) − g̃i,t k2

√ + τ′

T i (1+τ )(1−ρ) X h E k∇Ψ̃i,t,δ (wi,t )−∇Ψ̃i,t−1,δ (wi,t−1 )k2 + ρ t=1

+ (1 + τ )(1 − ρ) + 8ρβ 2

T i h X E k∇Ψ̃i,t−1,δ (wi,t−1 ) − ai,t−1 k2

(1 + τ )(1 − ρ) DT ρ T −1 h i X E k∇Ψ̃i,t,δ (wi,t ) − ai,t k2 + 8ρβ 2 , + (1+τ )(1−ρ) t=0

PT

where DT = t=1 k∇Ψ̃i,t,δ (wi,t ) − ∇Ψ̃i,t−1,δ (wi,t−1 )k2 . Rearranging terms and using k∇Ψ̃i,T,δ (wi,T ) − ai,T k2 ≥ (ρ(1 + τ ) − τ )k∇Ψ̃i,T,δ (wi,T ) − ai,T k2 since ρ < 1, we get (ρ(τ + 1) − τ )

T X t=1

h i E k∇Ψ̃i,t,δ (wi,t ) − ai,t k2

τ ′ (1 − ρ) τρ 1+2b O(T ) + DT ρτ ′ − τ ρ(ρτ ′ − τ ) 8ρβ 2 τ ′ (1 − ρ) 2 k∇ Ψ̃ (w )k + . + i,0,δ i,t ρτ ′ − τ ρτ ′ − τ

T k∇Ψ̃i,0,δ (wi,t )k ρτ ′ − τ 1 ρ(ρτ ′ − τ )

p T DT .

P Define āt = n1 ni=1 ai,t . Then, using the definition of Pt in (26), we obtain n X T X

∇Ψ̃j,t,δ (wj,t )⊤ (wj,t − wt∗ )

j=1 t=1

n X T X

(∇Ψ̃j,t,δ (wj,t ) − aj,t )⊤ (wj,t − wt∗ )

T n X X j=1 t=1

≤

a⊤ j,t (wj,t − w̄t ) + n 

n X T X

Pt + nβ

+n

∗ ā⊤ t (w̄t − wt ),

j=1 t=1

T X t=1

T X t=1

∗ ā⊤ t (w̄t − wt )

8 DT 3/4 + ηα′ βT 3

 (35)

where the last inequality follows from the consensus error bound in (23) and the boundedness of ai,t . PT ∗ To further bound the term t=1 ā⊤ t (w̄t −w ), we introduce the following lemma.

LemmaP III.6. [38][Lemma 2.3] Let w bt∗ = t−1 argmin i=1 fi (w) + R(w), ∀t ∈ [T ], where R(w) is w∈Ω

(33)

ρ ρτ ′ − τ

This completes the proof.

+

t=1 ′ 2

s

r

t=1 c 1 p 1 c =O(T 1+b− 2 ) + O(T 2 +b+ 2 ) + O(T c+ 2 ) DT .

1+2b

T i h X E k∇Ψ̃i,t,δ (wi,t ) − ai,t k2

s

√ ρ2 + 2 2T β ′ ρτ − τ

h i E k∇Ψ̃i,t,δ (wi,t ) − ai,t k

j=1 t=1

where the last equality is due to ai,0 = 0. Let τ ′ = 1 + τ . Dividing both sides by ρτ ′ − τ > 0 yields

≤

T X

=

(1 + τ )(1 − ρ) ≤(1 + τ )ρ O(T )+ DT ρ + (1 + τ )(1 − ρ)k∇Ψ̃i,0,δ (wi,t ) − ai,0 k2 + 8ρβ 2 (1 + τ )(1 − ρ) =(1 + τ )ρ2 O(T 1+2b ) + DT ρ + (1 + τ )(1 − ρ)k∇Ψ̃i,0,δ (wi,t )k2 + 8ρβ 2 , 2

s

By using ρ = T1c and β = O(1/δ) = O(T b ), it follows that

t=1

≤(1 + τ )ρ2 O(T 1+2b ) +

(34)

t=1

a strongly convex regularization function. Then, ∀w ∈ Ω, it holds that

8

T X t=1

≤ (ft (w bt∗ ) − ft (w))

≤R(w) − R (w b1∗ ) +

T X t=1

∗ bt+1 ft (w bt∗ ) − ft w

≤ .

Applying Lemma III.6, we establish an upper bound on the last term in (35) as follows. Proposition III.3. Suppose Assumption II.3 holds. Then, we have T X t=1

D2 + ηT β 2 . η

∗ ā⊤ t (w̄t − wt ) ≤

proposed algorithm, we have d¯t+1 = d¯t + āt . Note that w̄t+1 2 is given by w̄t+1 = argminw∈Ω η d¯⊤ t+1 w + kwk . Applying ⊤ T Lemma III.6 to the linear loss sequence {āt w}t=1 with the 2 regularizer R(w) = kwk η , we obtain

t=1

kŵk ∗ ā⊤ t (w̄t − wt ) ≤ η 2

2

−0+ T X

T X t=1

⊤ =F̄t (w̄t ) + ηā⊤ t w̄t − F̄t (w̄t+1 ) − ηāt w̄t+1

=F̄t (w̄t ) − F̄t (w̄t+1 ) + ηā⊤ t (w̄t − w̄t+1 ) ≤ηkāt kkw̄t − w̄t+1 k,

which implies kw̄t − w̄t+1 k ≤ ηkāt k. Combining this result with the boundedness condition kāt k ≤ β, we obtain the desired result. Building on the upper bounds established in Propositions III.2 and III.3, we now derive the dynamic regret bound for the proposed DPFOA algorithm. Theorem III.1. Suppose Assumptions II.1-II.4 hold. If the stepsizes are chosen as σt = √1t , ρ = T −2/5 , η = T −3/4 and δ = T −1/10 , then we have n X T   X E[Ψ̃j,t (ui,t )] − Ψ̃j,t (u∗t )

p DT ) + T 7/10 ).

Proof. Combining (24), (25) and (35) yields n X T   X Ψ̃j,t (ui,t ) − Ψ̃j,t (u∗t ) j=1 t=1

∇Ψ̃j,t,δ (wj,t )⊤ (wj,t − wt∗ ) + 3nδM T

8 + 2nM ( DT 3/4 + ηα′ βT ) 3 n X T T X X ∗ ≤ Pt + n ā⊤ t (w̄t − wt ) j=1 t=1

t=1

8 + (nβ + 2nM )( DT 3/4 + ηα′ βT ) + 3nδM T 3 T T n X X X ∗ D k∇Ψ̃j,t,δ (wj,t ) − aj,t k + n ā⊤ ≤ t (w̄t − wt ) t=1

t=1

8 + (nβ + 2nM )( DT 3/4 + ηα′ βT ) + 3nδM T. 3

(37)

Taking expectation of (37) and using Proposition III.2, we have n X T   X E[Ψ̃j,t (ui,t )] − Ψ̃j,t (u∗t ) j=1 t=1

T X t=1

kw̄t − w̄t+1 k2 ≤F̄t+1 (w̄t ) − F̄t+1 (w̄t+1 )

9

j=1 t=1

+n

where the last inequality follows from the boundedness of Ω and the Cauchy-Schwarz inequality. By (19), it is straightforward to verify that F̄t (w) is 2strongly convex and ∇F̄t+1 (w̄t+1 ) = 0, then one has

=O(T 10 (1 +

n X T X

 Ψ̃j,t,δ (wi,t ) − Ψ̃j,t,δ (wt∗ ) + 3nδM T

  c 1 c 1 p ≤nD O(T 1+b− 2 ) + O(T 2 +b+ 2 ) + O(T c+ 2 ) DT

ā⊤ t (w̄t − w̄t+1 )

D ≤ + kāt kkw̄t − w̄t+1 k, η t=1

j=1 t=1

j=1 t=1

j=1

PT

Proof. Define ŵ = arg minw∈Ω t=1 ā⊤ t w. Then, it holds P PT ∗ ⊤ that Tt=1 ā⊤ ( w̄ − w ) ≤ ā ( w̄ − ŵ). By (8) in the t t t t t=1 t

T X

T  n X X

(36)

∗ ā⊤ t (w̄t − wt ) + 3nδM T

8 + (nβ + 2nM )( DT 3/4 + ηα′ βT ). 3

(38)

Then, further using Proposition III.3, η = T −3/4 , δ = T −b , and ρ = T −c , we obtain n X T   X E[Ψ̃j,t (ui,t )] − Ψ̃j,t (u∗t ) j=1 t=1

  1 c 1 p c ≤nD O(T 1+b− 2 ) + O(T 2 +b+ 2 ) + O(T c+ 2 ) DT   2 D +n + ηT β 2 + 3nδM T η 8 + (nβ + 2nM )( DT 3/4 + ηα′ βT ) 3   1 c 1 p 1+b− 2c =nD O(T ) + O(T 2 +b+ 2 ) + O(T c+ 2 ) DT

+ nD2 T 3/4 + nβ 2 T 1/4 + 3nM T 1−b 8 (39) + (nβ + 2nM )( DT 3/4 + α′ βT 1/4 ). 3 To guarantee that the dynamic regret grows sublinearly with respect to the time horizon T (up to the non-stationarity measure DT ), we set b = 1/10 and c = 2/5, n X T   X E[Ψ̃j,t (ui,t )] − Ψ̃j,t (u∗t ) j=1 t=1 9

=O(T 10 (1 +

p DT ) + T 7/10 ).

(40)

This establishes a sublinear dynamic regret bound with explicit dependence on the temporal variation metric DT . This completes the proof.

9

Remark III.2. The stepsizes in Theorem III.1 are chosen in terms of the time horizon T for notational simplicity. In practice, a horizon-free implementation can be obtained using the standard doubling trick technique with periodic restarts [38]. Under these modifications, the same order of regret bounds up to constant factors can be achieved.

0.9

Target DPFOA DESA

0.8 0.7 0.6 0.5 0.4 0.3

IV. N UMERICAL SIMULATION

0.2

In this section, we evaluate the performance of the proposed feedback DPFOA and compare it with existing works. Consider an undirected and connected multi-agent network with ten agents, i.e. n = 10. The dynamics of agent i are described by xi,t+1 =Ai xi,t + Bi ui,t + di,x yi,t =Ci xi,t + di,y .

0.1 0 -0.1 0

100

200

300

400

500

600

700

800

t

Fig. 1. The paths of ct and ȳt generated by DPFOA and DESA.

(41) 9

where the disturbances di,x and di,y are independently generated from standard normal distributions. For simplicity, we consider three type of agents with different Ai , Bi and Ci . Each agent is associated with a time-varying private loss functions fi,t and all agents cooperate to solve the following distributed online optimization problem: min ft (u, y) = u,y

n X

DPFOA DESA

8 7 6 5 4 3

fi,t (ui , yi )

2

i=1

fi,t (ui , yi ) =ai,t kui k2 + bi,t kyi − ct k2 , s.t. y =h(u), ui ∈ U,

1 0 0

where ui and yi are the input and output of the dynamic system of agent i in (41). The coefficients ai,t and bi,t are independently sampled from a standard uniform distribution. The mapping h(u) is the steady-state input-output relationship of the system (41), and the input constraint set is set as U = {u|kuk1 ≤ 2}. The objective of all agents is to cooperatively drive the system output to track a moving target, whose position ct evolves according to t sin 100 , 10t with c0 = 0. At each time step t, every agent i generates an input ui,t and observes its local cost function value fi,t . All agents are initialized with the same feasible input ui,0 ∈ U. For performance comparison, we apply both the proposed DPFOA and a distributed version of the stochastic extremumseeking algorithm (DESA) adapted from [19] to problem (42). Since the ES algorithm in [19] was originally designed for a centralized setting, we extend it to the distributed framework by incorporating an average-consensus step. Both algorithms operate as model-free feedback frameworks. Fig. 1 illustrates the target trajectory P ct along with the trajectories of average output ȳt = n1 ni=1 yi,t for both algorithms. It is observed that both algorithms are capable of tracking the moving target asymptotically. However, the trajectory generated by DPFOA converges faster and remains closer to the true trajectory throughout the tracking process, while DESA exhibits larger transient deviations. To further evaluate the regret performance, we define the worst-case regret across all agents as Rt = maxi∈[10] Ri,t , and

ct+1 = ct +

100

200

300

400

500

600

700

800

(42) Fig. 2. The regret trajectory of DPFOA and DESA.

present its time-averaged value Rt /t in Fig. 2. Both algorithms exhibit decreasing regret curves, confirming their sublinear regret behavior. Nevertheless, DPFOA achieves substantially faster decay and attains a much lower regret level than DESA, demonstrating its superior efficacy and tracking accuracy. V. C ONCLUSION This paper has developed a distributed projection-free bandit online feedback optimization algorithm for multi-agent dynamical systems with constrained inputs and time-varying cost functions. By utilizing a smoothing zeroth-order onepoint estimator, the proposed algorithm constructs local gradient approximations directly from real-time input–output data, eliminating the need for any system model. A projection-free conditional gradient update, integrated with distributed global gradient estimators, is employed to effectively handle input constraints and maintain scalability in large-scale networked systems. The distributed online algorithm is shown to achieve a sublinear dynamic regret. Numerical simulations illustrate its effectiveness. Future work will explore communicationefficient implementations and extensions that incorporate additional safety or state constraints. R EFERENCES [1] R. Dixit, A. S. Bedi, R. Tripathi, and K. Rajawat, “Online learning with inexact proximal online gradient descent algorithms,” IEEE Transactions on Signal Processing, vol. 67, no. 5, pp. 1338–1352, 2019.

10

[2] S. Shahrampour and A. Jadbabaie, “Distributed online optimization in dynamic environments using mirror descent,” IEEE Transactions on Automatic Control, vol. 63, no. 3, pp. 714–725, 2018. [3] D. Yuan, A. Bhardwaj, I. Petersen, E. L. Ratnam, and G. Shi, “Towards online optimization for power grids,” SIGENERGY Energy Inform. Rev., vol. 1, no. 1, p. 51–58, Jan. 2022. [4] P. Yi, Y. Hong, and F. Liu, “Initialization-free distributed algorithms for optimal resource allocation with feasibility constraints and application to economic dispatch of power systems,” Automatica, vol. 74, pp. 259–269, 2016. [5] J. Zhao, X. Chang, Y. Feng, C. H. Liu, and N. Liu, “Participant selection for federated learning with heterogeneous data in intelligent transport system,” IEEE Transactions on Intelligent Transportation Systems, vol. 24, no. 1, pp. 1106–1115, 2023. [6] S. Hosseini, A. Chapman, and M. Mesbahi, “Online distributed convex optimization on dynamic networks,” IEEE Transactions on Automatic Control, vol. 61, no. 11, pp. 3545–3550, 2016. [7] D. Han, K. Liu, Y. Lin, and Y. Xia, “Differentially private distributed online learning over time-varying digraphs via dual averaging,” International Journal of Robust and Nonlinear Control, vol. 32, no. 5, pp. 2485–2499, 2022. [8] X. Yi, X. Li, T. Yang, L. Xie, Y. Hong, T. Chai, and K. H. Johansson, “Distributed online convex optimization with time-varying constraints: Tighter cumulative constraint violation bounds under Slater’s condition,” IEEE Transactions on Automatic Control, pp. 1–16, 2025. [9] K. Lu and H. Xu, “Online distributed optimization with strongly pseudoconvex-sum cost functions and coupled inequality constraints,” Automatica, vol. 156, p. 111203, 2023. [10] X. Li, X. Yi, and L. Xie, “Distributed online optimization for multiagent networks with coupled inequality constraints,” IEEE Transactions on Automatic Control, vol. 66, no. 8, pp. 3575–3591, 2021. [11] ——, “Distributed online convex optimization with an aggregative variable,” IEEE Transactions on Control of Network Systems, vol. 9, no. 1, pp. 438–449, 2022. [12] N. Agarwal, E. Hazan, A. Majumdar, and K. Singh, “A regret minimization approach to iterative learning control,” in Proceedings of the 38th International Conference on Machine Learning, ser. Proceedings of Machine Learning Research, vol. 139. PMLR, 18–24 Jul 2021, pp. 100–109. [13] Y. Yu, X. Li, L. Li, and L. Xie, “Distributed online optimization for heterogeneous linear multi-agent systems with coupled constraints,” Automatica, vol. 159, p. 111407, 2024. [14] A. B. Cassel, A. Peled-Cohen, and T. Koren, “Rate-optimal online convex optimization in adaptive linear control,” in Advances in Neural Information Processing Systems, vol. 35. Curran Associates, Inc., 2022, pp. 7410–7422. [15] G. Carnevale, N. Mimmo, and G. Notarstefano, “Nonconvex distributed feedback optimization for aggregative cooperative robotics,” Automatica, vol. 167, p. 111767, 2024. [16] J. Berberich, J. Köhler, M. A. Müller, and F. Allgöwer, “Data-driven model predictive control with stability and robustness guarantees,” IEEE Transactions on Automatic Control, vol. 66, no. 4, pp. 1702–1717, 2021. [17] W. Liu, J. Sun, G. Wang, F. Bullo, and J. Chen, “Data-driven resilient predictive control under Denial-of-Service,” IEEE Transactions on Automatic Control, vol. 68, no. 8, pp. 4722–4737, Aug. 2023. [18] Z. Qin, T. Liu, T. Liu, Z.-P. Jiang, and T. Chai, “Distributed feedback optimization of nonlinear uncertain systems subject to inequality constraints,” IEEE Transactions on Automatic Control, vol. 69, no. 6, pp. 3989–3996, 2024. [19] S.-J. Liu and M. Krstic, “Stochastic averaging in discrete time and its applications to extremum seeking,” IEEE Transactions on Automatic Control, vol. 61, no. 1, pp. 90–102, 2016. [20] L.-Y. Yang, S.-J. Liu, and P.-P. Zhang, “Stochastic time-varying extremum seeking and its applications,” Automatica, vol. 151, p. 110923, 2023. [21] S. Liu, P.-Y. Chen, B. Kailkhura, G. Zhang, A. O. Hero III, and P. K. Varshney, “A primer on zeroth-order optimization in signal processing and machine learning: Principals, recent advances, and applications,” IEEE Signal Processing Magazine, vol. 37, no. 5, pp. 43–54, 2020. [22] Y. Tang, Z. Ren, and N. Li, “Zeroth-order feedback optimization for cooperative multi-agent systems,” Automatica, vol. 148, p. 110741, 2023. [23] Z. He, S. Bolognani, J. He, F. Dörfler, and X. Guan, “Model-free nonlinear feedback optimization,” IEEE Transactions on Automatic Control, vol. 69, no. 7, pp. 4554–4569, 2024.

[24] W. Liu and P. Yi, “Distributed no-regret learning in aggregative games with residual bandit feedback,” IEEE Transactions on Control of Network Systems, vol. 11, no. 4, pp. 1734–1745, 2024. [25] K. Zhang, X. Yi, G. Wen, M. Cao, K. H. Johansson, T. Chai, and T. Yang, “Distributed event-triggered bandit convex optimization with time-varying constraints,” IEEE Transactions on Control of Network Systems, vol. 12, no. 3, pp. 2242–2253, 2025. [26] X. Jiang, J. Hou, L. Liu, and G. Feng, “Distributed conditional gradient online optimization with recursive variance reduction,” Automatica, vol. 189, p. 112999, 2026. [27] A. Nedic and A. Ozdaglar, “Distributed subgradient methods for multiagent optimization,” IEEE Transactions on Automatic Control, vol. 54, no. 1, pp. 48–61, 2009. [28] W. Zhang, P. Zhao, W. Zhu, S. C. H. Hoi, and T. Zhang, “Projectionfree distributed online learning in networks,” in Proceedings of the 34th International Conference on Machine Learning, ser. Proceedings of Machine Learning Research, vol. 70. PMLR, 06–11 Aug 2017, pp. 4054–4062. [29] J. C. Duchi, A. Agarwal, and M. J. Wainwright, “Dual averaging for distributed optimization: Convergence analysis and network scaling,” IEEE Transactions on Automatic Control, vol. 57, no. 3, pp. 592–606, 2012. [30] W. Shi, Q. Ling, G. Wu, and W. Yin, “Extra: An exact first-order algorithm for decentralized consensus optimization,” SIAM Journal on Optimization, vol. 25, no. 2, pp. 944–966, 2015. [31] O. Shamir, “An optimal algorithm for bandit and zero-order convex optimization with two-point feedback,” J. Mach. Learn. Res., vol. 18, no. 1, p. 1703–1713, Jan. 2017. [32] J. Chen, D. Zhou, J. Yi, and Q. Gu, “A frank-wolfe framework for efficient and effective adversarial attacks,” in Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 2020, pp. 3486–3494. [33] E. Hazan, “Introduction to online convex optimization,” Foundations and Trends in Optimization, vol. 2, no. 3–4, pp. 157–325, 2016. [34] D. Yuan, L. Wang, A. Proutiere, and G. Shi, “Distributed zeroth-order optimization: Convergence rates that match centralized counterpart,” Automatica, vol. 159, p. 111328, 2024. [35] Y. Wan, W.-W. Tu, and L. √ Zhang, “Projection-free distributed online convex optimization with o( T ) communication complexity,” in Proceedings of the 37th International Conference on Machine Learning, ser. Proceedings of Machine Learning Research, vol. 119. PMLR, 13–18 Jul 2020, pp. 9818–9828. [36] Y. Zhang, Y. Zhou, K. Ji, and M. M. Zavlanos, “A new one-point residual-feedback oracle for black-box learning and control,” Automatica, vol. 136, p. 110006, 2022. [37] D. S. Kalhan, A. Singh Bedi, A. Koppel, K. Rajawat, H. Hassani, A. K. Gupta, and A. Banerjee, “Dynamic online learning via frankwolfe algorithm,” IEEE Transactions on Signal Processing, vol. 69, pp. 932–947, 2021. [38] S. Shalev-Shwartz, “Online learning and online convex optimization,” Foundations and Trends in Machine Learning, vol. 4, no. 2, pp. 107– 194, 2011.

Related documents

• A Unified Optimism-Agnostic Framework for Linear Bandits over Spherical Action Sets#1116480
• Sharp Characterization of Bias in Post-Bandit Inference#1052257
• Lower Bounds for Linear-Oracle Online Learning#1142976
• Provable Anytime Ensemble Sampling Algorithms in Nonlinear Contextual Bandits#1052033
• Online Learning with LLM Experts from Limited Feedback#973445