# Distributed Bandit Online Convex Optimization with Time-Varying Coupled Inequality Constraints

arXiv: https://arxiv.org/abs/1912.03719 · HTML: https://mlsanity.com/paper/1912.03719/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Dec 2019.

## Built on by (most cited first, 11 of 11)

- [Regret and Cumulative Constraint Violation Analysis for Online Convex Optimization with Long Term Constraints](https://mlsanity.com/paper/2106.05135/) (2021)
- [Regret and Cumulative Constraint Violation Analysis for Distributed Online Constrained Convex Optimization](https://mlsanity.com/paper/2105.00321/) (2021)
- [Simultaneously Achieving Sublinear Regret and Constraint Violations for Online Convex Optimization with Time-varying Constraints](https://mlsanity.com/paper/2111.07707/) (2021)
- [Dynamic Regret Analysis of Safe Distributed Online Optimization for Convex and Non-convex Problems](https://mlsanity.com/paper/2302.12320/) (2023)
- [Distributed Stochastic Bandit Learning with Delayed Context Observation](https://mlsanity.com/paper/2207.14391/) (2022)
- [A Survey on Distributed Online Optimization and Game](https://mlsanity.com/paper/2205.00473/) (2022)
- [Distributed Management of Fluctuating Energy Resources in Dynamic Networked Systems](https://mlsanity.com/paper/2405.19015/) (2024)
- [Distributed Online Convex Optimization with Nonseparable Costs and Constraints](https://mlsanity.com/paper/2602.10452/) (2026)
- [No-regret learning for repeated non-cooperative games with lossy bandits](https://mlsanity.com/paper/2205.06968/) (2022)
- [Augmented Lagrangian Methods for Time-varying Constrained Online Convex Optimization](https://mlsanity.com/paper/2205.09571/) (2022)
- [Distributed Online Bandit Nonconvex Optimization with One-Point Residual Feedback via Dynamic Regret](https://mlsanity.com/paper/2409.15680/) (2024)

## Abstract (arXiv)

This paper considers the problem of distributed bandit online convex optimization with time-varying coupled inequality constraints. This problem can be defined as a repeated game between a group of learners and an adversary. The learners attempt to minimize a sequence of global loss functions and at the same time satisfy a sequence of coupled constraint functions. The global loss and the coupled constraint functions are the sum of local convex loss and constraint functions, respectively, which are adaptively generated by the adversary. The local loss and constraint functions are revealed in a bandit manner, i.e., only the values of loss and constraint functions at sampled points are revealed to the learners, and the revealed function values are held privately by each learner. We consider two scenarios, one- and two-point bandit feedback, and propose two corresponding distributed bandit online algorithms used by the learners. We show that sublinear expected regret and constraint violation are achieved by these two algorithms, if the accumulated variation of the comparator sequence also grows sublinearly. In particular, we show that O(Tθ1) expected static regret and O(T7/4-θ1) constraint violation are achieved in the one-point bandit feedback setting, and O(T^maxkappa,1-kappa) expected static regret and O(T1-kappa/2) constraint violation in the two-point bandit feedback setting, where θ1∈(3/4,5/6] and kappa∈(0,1) are user-defined trade-off parameters. Finally, these theoretical results are illustrated by numerical simulations of a simple power grid example.