Source-linked AI summary
Delay and Cooperation in Nonstochastic Bandits
Nicolo' Cesa-Bianchi, Claudio Gentile, Yishay Mansour, Alberto Minora
TL;DR
The paper studies cooperative nonstochastic bandits in networks where information arrives with delay. It introduces EXP3-COOP and analyzes how cooperation, delay, and network topology shape regret, also characterizing delayed-feedback regret.
Problem
Delayed feedback arises in sequential decision problems, including recommender systems and communicating learning agents, motivating analysis of cooperative bandits under communication delays.
Method
The paper introduces EXP3-COOP, a distributed cooperative version of EXP3 in which synchronized agents exchange action and loss information through a network with edge-dependent delays.
Results
The analysis establishes average welfare regret bounds governed by a tradeoff between cooperation, delay, and communication-network topology, and provides the first characterization of regret for adversarial bandits with constant delayed feedback.
Takeaways & Limitations
Cooperation can improve bandit performance, but its benefit depends on the delay induced by the underlying communication network.
Takeaways & Limitations
The designed algorithms postpone updates by delay-dependent numbers of time steps rather than using each loss immediately when it becomes available.
Abstract
from arXiv · showhide
We study networks of communicating learning agents that cooperate to solve a common nonstochastic bandit problem. Agents use an underlying communication network to get messages about actions selected by other agents, and drop messages that took more than $d$ hops to arrive, where $d$ is a delay parameter. We introduce \textsc{Exp3-Coop}, a cooperative version of the {\sc Exp3} algorithm and prove that with $K$ actions and $N$ agents the average per-agent regret after $T$ rounds is at most of order $\sqrt{\bigl(d+1 + \tfrac{K}{N}α_{\le d}\bigr)(T\ln K)}$, where $α_{\le d}$ is the independence number of the $d$-th power of the connected communication graph $G$. We then show that for any connected graph, for $d=\sqrt{K}$ the regret bound is $K^{1/4}\sqrt{T}$, strictly better than the minimax regret $\sqrt{KT}$ for noncooperating agents. More informed choices of $d$ lead to bounds which are arbitrarily close to the full information minimax regret $\sqrt{T\ln K}$ when $G$ is dense. When $G$ has sparse components, we show that a variant of \textsc{Exp3-Coop}, allowing agents to choose their parameters according to their centrality in $G$, strictly improves the regret. Finally, as a by-product of our analysis, we provide the first characterization of the minimax regret for bandit learning with delay.
1. Introduction
The paper studies cooperative nonstochastic bandits where network communication creates delayed feedback, and introduces EXP3-COOP to exploit received information. Its regret depends on delay, network structure, and the number of agents, with cooperation improving over noncooperation in key settings.
- Motivation: Delayed feedback arises when recommendations or actions produce information only after variable delays, including communication delays among geographically distributed learning agents.The motivating example is a network of ad servers that shares information through a slower communication network.
- Model and algorithm: EXP3-COOP is a distributed cooperative EXP3 algorithm in which agents receive action information after delays determined by shortest-path distances in the communication graph.Agents start identically, select actions each round, observe selected-action losses, and receive delayed broadcasts from other agents.
- Main result: N agents achieve average welfare regret of order sqrt((d + 1 + (K/N) α≤d)(T ln K)), where α≤d is the independence number of the graph’s d-th power.The d-th power adds edges between nodes whose shortest-path distance is at most d.
- Consequences: The framework recovers prior bounds in special cases and gives the first characterization, up to logarithmic factors, of minimax regret for bandit learning with constant delay.The characterization concerns the delayed-feedback bandit problem and complements the cooperative-network results.
- Analysis: The analysis avoids simple delay reductions by quantifying importance-weighted estimates and controlling how delayed feedback affects the maintained action distributions.In the multi-agent setting, each agent updates actions played d rounds earlier by itself or by agents within distance d.
2. Additional Related Work
The paper situates its contribution among delayed online learning and cooperative bandit work in both nonstochastic and stochastic settings. Prior approaches provide related bounds or network models, but differ in assumptions, feedback, or treatment of delay.
- Delayed online learning: Earlier delayed-online-learning studies developed strategies for controlling delayed-feedback effects and analyzed exponential weights, partial monitoring, and total-delay regret bounds.Related results include bounds involving (D + T) ln K, where D is total delay over T rounds.
- Stochastic bandits: Stochastic cooperative-bandit studies use dynamic peer-to-peer networks, fixed graphs with consensus-based UCB, or indirect feedback from a designated observing agent.These works differ from the present model in stochastic assumptions, communication mechanisms, or which agents observe rewards.
3. Preliminaries
The preliminaries define the exponentially weighted agent and establish probability-drift lemmas that control delayed-feedback regret. The second lemma provides the key multiplicative control used for the paper’s improvements.
- Exponential weighting: An agent selects each action according to normalized exponential weights and updates those weights using nonnegative loss estimates.The action probabilities are determined by weights initialized uniformly, after which observed or additional information produces loss estimates for the update.
- Probability-drift control: Bounding distribution drift over d steps is central to controlling regret when feedback is delayed.The first lemma bounds additive changes in action probabilities regardless of how loss estimates are defined.
- Delayed estimates: Delayed loss estimates use indicators B_t−d(i) and conditional probabilities q_t−d(i) that upper-bound the corresponding action probabilities.These quantities instantiate whether an action was played d rounds earlier and the conditional probability of that event.
- Probability-drift control: Lemma 2 gives a multiplicative probability-change bound for these estimates when η ≤ 1/(K e^(d+1)).This result applies under the specified delayed-estimate form and supplies the key technical control for later regret improvements.
4. The Cooperative Setting on a Communication Network
The cooperative setting places synchronized exponentially weighted agents on a communication graph and uses delayed, importance-weighted information from nearby agents. EXP3-COOP yields regret bounds governed by delay and graph structure, with especially strong guarantees for connected or dense networks.
- Network model: N agents on a connected undirected graph independently draw actions from a common action set while cooperating on one nonstochastic bandit problem.The graph defines communication neighborhoods and the agents’ average welfare regret objective.
- Communication protocol: Messages older than d hops are dropped, while newer messages are forwarded through the network.The protocol sends local messages, receives delayed messages, and forwards only those within the delay threshold.
- EXP3-COOP: EXP3-COOP incorporates delayed losses from agents within distance d using importance-weighted estimates whose denominators are conditional observation probabilities.An agent updates an action when any nearby agent played it at time t−d, using the probability of that event conditioned on history.
- EXP3-COOP: Each agent can tune its learning rate locally through a doubling trick instead of using globally required quantities such as N and α(G≤d).The local rate is increased when the accumulated local quantity exceeds its threshold, and Theorem 4 analyzes the resulting adaptive rates.
- Regret guarantees: Theorem 4 analyzes EXP3-COOP with individually selected learning rates and includes additive terms depending on d and log T.The theorem’s asymptotic statement applies to a network of N agents using delay d.
- Regret guarantees: When d equals the graph diameter, α(G≤d)=1 and the bound approaches the full-information rate when N ≈ K.All agents then receive the same feedback and compute identical updates; sparse graphs may instead favor d=0 and the standard bandit bound.
- Regret guarantees: For every connected graph, choosing d=√K yields an average welfare regret bound of order K^1/4√(T ln K).This choice provides a graph-independent improvement over the noncooperative standard bandit scale described in the section.
5. Extensions: Cooperation with Individual Parameters
EXP3-COOP2 extends cooperative bandit learning to agents with individual delay and time-to-live parameters, inducing a directed information structure and supporting topology-dependent regret analysis.
- Individual parameters: Individual delays and time-to-live values determine which messages each agent forwards and uses for updates.Agent v uses a message from v′ exactly when their graph distance is at most min{d(v), ttl(v′)}.
- Induced communication structure: The induced directed graph G_P contains an arc from v′ to v when their distance is at most min{d(v), ttl(v′)}.Its in-neighborhood records the agents whose information can reach v under the parameter collection.
- Induced communication structure: The parameterization is exogenous and static, so the algorithms cannot trade communication structure against regret.This fixed structure makes regret expressible as a function of available communication.
- EXP3-COOP2: EXP3-COOP2 strictly generalizes EXP3-COOP but must handle directed graphs, which reduce available information and increase estimator variance.The algorithm therefore requires a lower bound on every action probability, with p_t(i,v) bounded below by the exploration parameter expression.
- Regret guarantees: Theorem 9 and Corollary 10 provide regret guarantees for individual parameters, including learning rates selected adaptively through a doubling trick.The stated guarantees use exploration parameter δ = 1/T; Corollary 10 allows each agent to select η(v) adaptively.
- Topology-dependent tuning: Individual parameters help heterogeneous networks: sparse-region agents can use larger delays, while central agents can use small delays and large time-to-live values.Time-to-live parameters also bound message complexity, while topology-dependent parameter selection can be initialized with only a topology-dependent additive regret cost.
6. Delayed Losses (for a Single Agent)
The paper studies nonstochastic bandits with fixed delayed feedback, where the learner observes losses only after d rounds. It combines an improved upper bound with a matching lower bound up to logarithmic factors, characterizing minimax regret.
- Problem: The delayed-loss problem gives the learner access to selected-action losses only after a fixed delay d.At round t, the available losses are those through s = max{1, t − d}.
- Prior bounds: Earlier bandit analyses gave an upper bound of order (d + 1)KT, but no matching lower bound was available.The paper positions its result as closing this gap up to logarithmic factors.
- Baseline: A simple baseline runs d + 1 independent instances of a minimax-optimal no-delay bandit algorithm in parallel.At time t = (d + 1)r + s, instance s + 1 is used for the current play.
- Main result: The paper develops an improved upper bound and a matching lower bound up to logarithmic factors for delayed bandit learning.This establishes the minimax regret order for the fixed-delay setting.
- Main result: The resulting minimax characterization is of order (d + 1)KT up to logarithmic factors.The bound improves the previously available delayed-bandit analysis in the sense stated by the paper’s theorem and contribution passages.
7. Conclusions and Ongoing Research
The paper concludes that cooperation with delayed information yields regret bounds shaped by network topology, while identifying several open questions about optimality, per-agent guarantees, adaptive delays, and communication design.
- Conclusions: The analysis establishes cooperative nonstochastic bandit regret bounds that trade off cooperation against delayed information.This tradeoff is governed by the communication network topology.
- Open questions: Average welfare bounds remain the main scope, with simultaneous individual-agent regret guarantees left as a conjectured extension.The proposed individual bound depends on the size of each agent’s d-neighborhood.
- Open questions: The optimality of the Theorem 4 upper bound in the considered communication model remains unresolved because matching lower bounds are not provided.The paper explicitly asks whether that upper bound is optimal.
- Open questions: The algorithms postpone updates by d or d(v) steps, although generalized versions could use losses as soon as they arrive.Those generalized bounds would combine delays with independence numbers at multiple delay levels.
- Open questions: The paper also leaves open adaptive local tuning of d, removing distribution information from messages, and tighter single-agent delayed-feedback rates.These questions concern algorithmic adaptivity, communication content, and unresolved regret forms.
- Open questions: The discussion notes that bounds based on total time-varying delay, such as (D + T) ln K, would be a worthwhile extension.The paper identifies learning on networks with time-varying delays as an open topic.
Appendix A. Proofs from Section 3
This appendix proves preliminary lemmas for the delayed cooperative update, including weight bounds, uniform initial behavior, and a learning-rate condition.
- Preliminary lemmas: The first lemma proves that updated normalized weights dominate the corresponding unnormalized weights.It uses W_t+1 ≤ 1 to obtain w_t+1(i) ≤ p_t+1(i).
- Preliminary lemmas: For the first d rounds, all delayed feedback terms vanish, so the action distribution remains uniform at 1/K.The lemma then proceeds inductively for later rounds.
- Preliminary lemmas: The appendix records a learning-rate condition ensuring the relevant probability comparison, namely η ≤ 1/(K e^(d+1)).The condition appears in the statement associated with the delayed update analysis.
Appendix B. Proofs from Section 4.1
The appendix derives the Section 4.1 regret bound by combining exponential-weights analysis, delayed importance-weighted estimates, and graph-based variance control.
- Variance control: The variance lemma connects importance-weighted estimate variance to the independence number of the communication graph.Its application uses the graph G^≤d induced by the delay radius.
- Regret decomposition: The proof begins with a deterministic exponential-weights regret inequality for each agent and action.The subsequent analysis separates the resulting sums before averaging across agents.
- Regret decomposition: The three terms in the regret decomposition are bounded separately using iterative applications of the preliminary lemmas.These bounds cover the delayed estimates, their variance, and changes in maintained distributions.
- Final bound: Averaging over agents and applying the graph lemma produces the central network-dependent bound.The proof then overapproximates the resulting expression to obtain the desired theorem.
- Parameter tuning: The theorem proof handles agent-specific learning rates through a doubling trick that restarts an instance when its accumulated estimate quantity exceeds a threshold.Each restart incurs a delay-dependent regret cost.
- Parameter tuning: The resulting analysis bounds regret within each learning-rate phase and controls the total restart contribution.The final expression includes a logarithmic-in-T restart term and a constant depending polynomially on other parameters.
- Final bound: As T grows large, the proof obtains the stated asymptotic regret bound after combining the phase-wise estimates.The residual expression contains T, a 3d log^2 T term, and a T-independent constant before asymptotic simplification.
Appendix C. Proofs from Section 5
This appendix extends the delayed cooperative analysis to modified updates and directed communication, establishing probability bounds, graph inequalities, and the resulting average welfare regret expression.
- Directed extension: The directed-graph analysis first adapts the preliminary lemmas to the EXP3-COOP2 update rule.The proof maintains lower bounds on action probabilities needed for the graph inequality.
- Probability control: The modified update guarantees a deterministic lower bound on every action probability under conditions on δ and η.Lemma 14 assumes δ ≤ 1/d(v) and η ≤ 1/(K e^(d(v)+1)).
- Directed graph inequality: The directed variance lemma uses in-neighborhoods and requires probabilities at least δ/[K(1+δ)].It relates the relevant quantities through a graph independence-number bound.
- Directed graph inequality: The proof derives the directed graph inequality by combining auxiliary bounds and applies it to the communication graph induced by the update parameters.The probability terms need not sum to one across agents for the lemma to apply.
- Final result: Combining the potential inequality with the directed graph lemma yields an average welfare regret bound for individual delays d(v).The proof averages over agents and uses the mean delay parameter before taking the large-T limit.
- Final result: The appendix concludes that the EXP3-COOP2 bound holds asymptotically as T grows large.This follows after combining the preceding estimates and setting δ = 1/T.
Appendix D. Proofs regarding Section 6
The appendix analyzes the single-agent delayed-bandit case, deriving an upper bound via delayed Exp3 updates and a matching lower bound up to logarithmic factors. The lower-bound proof reduces delayed full-information prediction to a no-delay problem and combines this with known bandit lower bounds.
- Upper bound: The single-agent specialization runs standard Exp3 and updates its weights whenever a delayed loss becomes available.It sets B_{t-d}(i)=I{I_{t-d}=i} and q_{d,t-d}(i)=p_{t-d}(i).
- Lower bound: The delayed-bandit lower bound combines the known no-delay bandit lower bound with a full-information lower-bound argument for delayed feedback.The proof uses the latter argument to transfer hardness from the no-delay full-information setting.
- Lower bound: A delayed full-information predictor is transformed into a no-delay predictor by expanding each loss vector into a block of d+1 rounds.The construction sets T=(d+1)B and defines the delayed instance from the no-delay loss sequence.
- Lower bound: The construction remains valid because each transformed prediction uses only losses available at least d steps earlier.The resulting algorithm is a legitimate no-delay full-information online algorithm.
- Lower bound: Delayed bandit regret cannot be smaller than either no-delay bandit regret or delayed full-information regret, yielding a minimax lower bound.This establishes the claimed characterization up to logarithmic factors when paired with the upper bound.