Distributed Online Optimization with Long-Term Constraints and Bandit Feedback: An Event-Triggered Approach

This paper considers the distributed online optimization problem (DOO) with long-term constraints (LTC) and bandit feedback under a time-varying communication network, where the cost function is time-varying and only two specific values are disclosed to agents subsequent to their decision-making process. The primary objective of this paper is to develop a bandit distributed online algorithm that not only ensures sublinear growth of regret and cumulative absolute constraint violation (CACV) with respect to the total time T, but also addresses computation and communication burdens. By considering long-term constraints and introducing an event-triggered (ET) strategy, we design a novel two-point bandit distributed online algorithm. Then, we establish upper bounds for the regret and CACV of the proposed algorithm at \(\mathcal {O}(T^{\max {\{c,1-c\}}})\) and \(\mathcal {O}(T^{1-\frac{c}{2}})\) , respectively. These bounds align with the state-of-the-art results for online algorithms, even under full information feedback without any communication constraint. Finally, the effectiveness of the algorithm and the influence of ET threshold are verified by studying a numerical example of distributed online regularization linear regression.