PaperlayerView exact revision on arXiv

Source-linked AI summary

Multi-Agent Multi-Armed Bandits with Limited Communication

Mridul Agarwal, Vaneet Aggarwal, Kamyar Azizzadenesheli

arXiv:2102.08462v1cs.LGcs.AIcs.MA

TL;DR

Servers waste data collected by others when running their own algorithms, while communicating after every recommendation makes communication complexity high. LCC-UCB and LCC-UCB-GRAPH use epoch-based collaboration in fully connected and sparse networks, with agents exchanging arm recommendations and incorporating neighbor information. Empirically, LCC-UCB-GRAPH outperforms every-time communication in which agents share knowledge only with neighbors.

  • Problem

    Servers waste data collected by others when running their own algorithms, while communicating after every recommendation makes communication complexity high.

    Source: §I · p. 1

  • Method

    LCC-UCB and LCC-UCB-GRAPH use epoch-based collaboration in fully connected and sparse networks, with agents exchanging arm recommendations and incorporating neighbor information.

    Source: §IV · p. 5, §VIII · p. 20

  • Results

    Empirically, LCC-UCB-GRAPH outperforms every-time communication in which agents share knowledge only with neighbors.

    Source: §VIII · p. 20

  • Takeaways & Limitations

    The proposed algorithms combine low-bit communication with regret bounds for fully connected and sparse networks.

    Source: §VIII · p. 20

Abstract

from arXiv · show

We consider the problem where $N$ agents collaboratively interact with an instance of a stochastic $K$ arm bandit problem for $K \gg N$. The agents aim to simultaneously minimize the cumulative regret over all the agents for a total of $T$ time steps, the number of communication rounds, and the number of bits in each communication round. We present Limited Communication Collaboration - Upper Confidence Bound (LCC-UCB), a doubling-epoch based algorithm where each agent communicates only after the end of the epoch and shares the index of the best arm it knows. With our algorithm, LCC-UCB, each agent enjoys a regret of $\tilde{O}\left(\sqrt{({K/N}+ N)T}\right)$, communicates for $O(\log T)$ steps and broadcasts $O(\log K)$ bits in each communication step. We extend the work to sparse graphs with maximum degree $K_G$, and diameter $D$ and propose LCC-UCB-GRAPH which enjoys a regret bound of $\tilde{O}\left(D\sqrt{(K/N+ K_G)DT}\right)$. Finally, we empirically show that the LCC-UCB and the LCC-UCB-GRAPH algorithm perform well and outperform strategies that communicate through a central node

I. INTRODUCTION

The paper studies how multiple agents can reduce bandit regret without the cost of communicating after every round. It introduces limited-communication algorithms for fully connected and sparse networks, then compares them empirically with more frequent communication strategies.

I. INTRODUCTION

  • LCC-UCB lets agents collaborate toward lower regret while limiting communication to epoch boundaries.The introduction motivates this trade-off against communication after each recommendation.Source: §I · pp. 1–2
  • Agents run UCB on subsets of arms during doubling-length epochs, then exchange their best-known arm recommendations and restart with updated arm sets.Each agent sends its most-played arm at epoch end.Source: §I · p. 2
  • LCC-UCB-GRAPH divides epochs into equal sub-epochs and incorporates neighbor information, with O(K_G D log T) message exchanges per node.The stated communication bound depends on maximum degree K_G and graph diameter D.Source: §I · p. 2
  • Empirically, LCC-UCB performs close to communication at every step, while LCC-UCB-GRAPH outperforms every-step neighbor sharing; both outperform DEMAB.The introduction also states that DEMAB communicates for O(N log(NK)) rounds.Source: §I · p. 2

II. RELATED WORKS

Prior distributed-bandit work varies in topology, communication frequency, and message content. The paper positions its approach as reducing communication while retaining low regret and avoiding reliance on a central node.

II. RELATED WORKS

  • Some prior methods use a central controller or fully connected communication, unlike this work’s allowance for general network topologies.The cited central-controller setup is distinguished from the paper’s topology-flexible setting.Source: §II · p. 3
  • Fully connected action-elimination work bounds communication rounds by O(log2 T) but sends reward estimates for all K arms, unlike this paper’s O(log2 K)-bit messages.The paper contrasts its compact best-arm messages with transmitting all arm estimates.Source: §II · p. 3
  • Some related works let agents communicate at every time step and send estimates, while epoch-based strategies unicast knowledge of the best arm using O(log K) bits in each epoch.Source: §II · p. 3
  • DEMAB uses a central coordinating node and known horizon for its time-independent message bound; with an unknown horizon, its messages increase to O(log T).The paper compares its proposed regret bounds with DEMAB’s in the surrounding discussion.Source: §II · p. 4

III. PROBLEM FORMULATION

The formulation considers N agents interacting with the same stochastic K-armed bandit over T steps, with each agent’s cumulative regret as the objective. It assumes all-to-all communication initially and later relaxes that assumption.

III. PROBLEM FORMULATION

  • Each agent observes a reward from its chosen arm, with 1-sub-Gaussian noise and arm means assumed to lie between 0 and 1.The ordering of arm means is used in analysis but is unknown to agents.Source: §III · p. 4
  • The setup assumes N is much smaller than K, reflecting settings with many arms relative to agents.An e-commerce site with many products and fewer servers is given as an example.Source: §III · p. 5
  • Initially, every agent can broadcast to all others and communicates only the index of its best-known arm, requiring ceil(log(K)) bits per message.The total per-agent message size per round is (N − 1)ceil(log(K)) bits.Source: §III · p. 5
  • Each agent minimizes its cumulative regret over T steps; minimizing regret for every agent also minimizes total cumulative regret across agents.Source: §III · p. 5

IV. LCC-UCB ALGORITHM

LCC-UCB runs UCB over an evolving set of arms in epochs and uses agents’ recommendations to update that set. It discards old recommendations when new ones arrive, keeping the number of arms per agent bounded.

IV. LCC-UCB ALGORITHM

  • At each epoch’s end, an agent broadcasts its most-played arm, receives recommendations from other agents, and restarts UCB using the updated information.The UCB procedure operates on the augmented arm set for that epoch.Source: §IV · p. 5
  • The augmented set combines an agent’s initial arms with received recommendations and contains at most ceil(K/N) + N − 1 arms.Old recommendations are purged as new recommendations arrive.Source: §IV · p. 5
  • Epoch durations grow geometrically, and if the remaining horizon is too short for a full epoch, the algorithm runs UCB for the remainder.The stated epoch duration is K′(K′ + 1)2^j.Source: §IV · p. 6

V. MAIN RESULT

The main result analyzes LCC-UCB’s regret by bounding the quality of recommended arms and the regret within each epoch. It also bounds communication and contrasts the algorithm’s early-epoch design with prior work.

V. MAIN RESULT

  • For epochs with T_j ≥ K′(K′ + 1), the most-played arm is at most ˜∆_j from the optimal arm.The proof bounds plays of sufficiently suboptimal arms before establishing the guarantee for the most-played arm.Source: §V · pp. 7–8
  • 2K′T_j log T + 16K′^3 bounds an agent’s regret when running UCB for an epoch j ≥ 2.The bound applies to epochs with T_j time steps.Source: §V · pp. 8–9
  • O(N log(K) log(T)) bounds the total bits exchanged by an agent using LCC-UCB.Agents exchange arm indices during each epoch.Source: §V · p. 12
  • Unlike the cited epoch-based approach, LCC-UCB runs UCB from the first epoch and uses a first epoch of length o(1), which the authors say limits regret.The authors attribute an improved regret bound over the state of the art with limited communications to these changes.Source: §V · p. 12

VI. EXTENSION TO GENERAL NETWORK STRUCTURES

The complete-network assumption may not hold in general graphs, and a direct LCC-UCB extension can delay how quickly agents learn about good arms. LCC-UCB-GRAPH uses staged neighbor communication to control regret and communication costs.

Direct extension

  • The direct LCC-UCB extension replaces the arm-pool term ⌈K/N⌉ + N with ⌈K/N⌉ + K_G, but non-neighboring agents may not receive the best-arm information directly.The corollary applies to general graphs; delays in information propagation motivate the modified algorithm.Source: §VI · p. 13

LCC-UCB-GRAPH design

  • LCC-UCB-GRAPH divides each epoch into D equal-length sub-epochs, restarts UCB, and exchanges arm recommendations only between neighbors.Results propagate across the graph by the corresponding sub-epoch in the next epoch.Source: §VI · pp. 14–16

LCC-UCB-GRAPH regret bound

  • Theorem 3 bounds each agent’s regret under LCC-UCB-GRAPH in terms of graph diameter D and maximum degree K_G, with K′ = ⌈K/N⌉ + K_G.The bound applies to a graph G representing the agents’ network.Source: §VI · p. 15

Communication trade-off

  • The staged design avoids exponential regret growth in D, while its D sub-epochs per epoch trade this off for D times more communication rounds.The total exchanged bits per agent are bounded by O(K_G D log(K) log(T)).Source: §VI · p. 16

VII. EVALUATIONS

The evaluations compare regret across communication strategies in complete and sparse networks. LCC-UCB-GRAPH outperforms the cited communication baselines in sparse graphs, while LCC-UCB approaches the optimal-communication case in selected small-agent settings.

LCC-UCB evaluation

  • DEMAB has higher regret than the no-communication strategy in the reported comparison.The authors attribute this to purging observations and not sharing knowledge of the best arm.Source: §VII · pp. 17–18

Sparse-graph evaluation

  • In sparse graphs, LCC-UCB-GRAPH outperforms no communication, per-step communication, and the relay-based LCC-UCB variant.The comparison is shown for per-step cumulative regret of a single agent.Source: Figure 3 · p. 18, §VII · p. 19

LCC-UCB evaluation

  • LCC-UCB regret rises most during early epochs, when agents have not yet found the best arm, and grows slowly later as agents share the optimal-arm index.Source: §VII · p. 18
  • For (N, K) = (10, 100) and (10, 200), LCC-UCB performs closer to the optimal-communication case.The authors attribute this to less overhead from re-sampling arms obtained from other agents.Source: §VII · p. 18

Sparse-graph evaluation

  • For sparse-graph runs, doubling K from 250 to 500 increases regret at a lower rate for LCC-UCB-GRAPH than for the other two strategies.The authors attribute its low regret to at most five allocated arms per agent and low node degree in the tested graphs.Source: §VII · p. 19

VIII. CONCLUSION

The paper addresses regret and communication costs for N agents interacting with a K-arm bandit. It proposes separate algorithms for fully connected and sparse networks, analyzes their regret, and reports empirical performance gains for LCC-UCB-GRAPH over neighbor-only communication strategies.

VIII. CONCLUSION

  • LCC-UCB targets fully connected networks, while LCC-UCB-GRAPH targets sparse networks with maximum degree KG and diameter D.The paper analyzes regret for both algorithms.Source: §VIII · p. 20
  • The algorithms receive regret bounds, with separate expressions stated for LCC-UCB and LCC-UCB-GRAPH.The supplied conclusion passage fragments the expressions, so their exact forms are not reported here.Source: §VIII · p. 20
  • LCC-UCB-GRAPH empirically outperforms every tested strategy in which agents share knowledge only with their neighbors.Source: §VIII · p. 20
  • The authors report low communication bit complexity for both algorithms and identify power-constrained devices as a suitable use case.Source: §VIII · p. 20
Loading 2102.08462v1…