PaperlayerView exact revision on arXiv

Source-linked AI summary

The Price of Decentralization in Top-$K$ Arm Identification

Larissa Xu, Jasmine Nguyen, William Chang

arXiv:2608.22120v1cs.LG

TL;DR

The paper studies how cooperative agents can identify the best K joint actions when each sees only partial information. It develops communication-free UCB-Intervals methods across three observability regimes and shows that shared rewards recover centralized coordination, while full asymmetry incurs a fixed 4× sample-complexity penalty. The joint-action dependence remains unavoidable, and the framework leaves open whether Problem B’s deviation channel can approach pooled-observation rates.

  • Problem

    Cooperative teams must identify top-K joint configurations even when members cannot observe all actions or rewards.

  • Method

    The paper extends elimination-based UCB-Intervals algorithms to three information-asymmetry regimes without communication, exploiting shared rewards, observable deviations, or enlarged confidence radii.

  • Results

    The unified analysis shows that the regimes differ through multiplicity and consensus factors, with matching lower bounds and a 4× penalty under full asymmetry.

  • Takeaways & Limitations

    Dependence on the A^M joint-action count is unavoidable, while Problem B’s deviation channel presents an open route toward pooled-observation rates.

  • Takeaways & Limitations

    Evaluation uses small joint spaces—A^M ≤50 in main panels and up to 243 in scalability—limiting validation when A^M is much larger than T.

Abstract

from arXiv · show

Cooperative teams often need to agree on the best few options rather than simply accumulate reward, and they must do so while each member sees only a fragment of the team's collective experience. We study this as top-$K$ joint-arm identification in multi-agent multi-armed bandits: at every round $M$ agents simultaneously choose individual actions that compose a joint arm, and the team must ultimately return the $K$ joint arms of highest mean reward. The difficulty is that an agent may not observe the actions of others, their rewards, or either. We treat three observability regimes---(A) shared rewards with hidden actions, (B) observed actions with private rewards, and (C) full asymmetry---and design communication-free elimination algorithms (UCB-Intervals) that reconstruct implicit coordination from whatever signal each regime leaves intact: a shared arm ordering in (A), observable deviations in (B), and enlarged confidence radii under (C). We give matching analyses in both the fixed-budget and fixed-confidence objectives, then fold all three regimes into a single meta-guarantee indexed by a multiplicity $c$ and a consensus factor $ρ$. Our central result is quantitative rather than merely algorithmic: change-of-measure lower bounds show that shared-reward identification is optimal up to one universal logarithmic factor, and that the entire statistical price of removing communication is a multiplicative $ρ^2$ in sample complexity---a fixed $4\times$ penalty under full asymmetry. The resulting stopping time scales as $O\!\left(\sum_{\mathbf{a}} \frac{\log(A^M/δ)}{Δ_{\mathbf{a}}^2}\right)$ and the fixed-budget error as $\exp(-Θ(T/H_1))$, with the dependence on the joint-action count $A^M$ shown to be unavoidable.

1 Introduction

The paper studies communication-free top-K identification for cooperative teams whose members observe only partial information. It introduces multi-agent algorithms and theoretical guarantees for action and reward asymmetry in fixed-budget and fixed-confidence settings.

  • Motivation: The framework targets teams identifying a small set of joint configurations when members observe only their own slice of the outcome.Motivating settings include decentralized experimentation, federated experimentation, and privacy-preserving multi-site trials.
  • Modeling scope: The joint action space is treated as unstructured in the baseline, while additive rewards are handled separately because structure can reduce the exponential arm count.The paper notes that structure-free modeling is necessary when joint rewards do not decompose smoothly across components.
  • Contributions: The paper introduces decentralized top-K algorithms for action and reward asymmetry without communication.The algorithms extend elimination-based bandit methods to multiple agents and support implicit coordination.
  • Contributions: The analysis covers both fixed-budget and fixed-confidence objectives and includes empirical validation of the proposed algorithms.These guarantees are part of the paper’s stated contributions.

2 Preliminaries

The paper formalizes cooperative multi-player joint-action bandits with A^M possible arms and defines top-K identification through the ranking of unknown joint-arm means. It establishes that dependence on this joint-action space is information-theoretically unavoidable.

  • Model: M players choose simultaneously from action sets of size A, producing A^M joint arms with unknown 1-subgaussian mean rewards.Players may agree on a strategy and shared arm ordering before learning, but cannot communicate during learning.
  • Top-K objective: The top-K target is the set of the K joint arms ranked highest by their unknown means.The ranking permutation σ orders arms by decreasing mean, and S⋆ contains its first K arms.
  • Information-theoretic cost: 18?

3 Problem Setting

The paper distinguishes three observability regimes and two identification objectives, then compares their statistical costs against a centralized single-agent baseline. Shared rewards preserve centralized rates, while independent reward streams and full asymmetry add coordination costs.

  • Information regimes: The three regimes vary by whether players share rewards and observe the realized joint action.Problem A has shared rewards and hidden actions; Problem B has observed actions and private rewards; Problem C has neither.
  • Information regimes: Problem B is not strictly easier than Problem A because independent reward streams require simultaneous concentration across players.The deviation signal helps coordinate the streams, but does not recover the shared reward stream available in Problem A.
  • Learning objectives: The objectives are to minimize error after horizon T or minimize stopping time while identifying the correct top-K set with probability at least 1−δ.The fixed-budget objective uses R_T, whereas fixed confidence requires unanimous correct output at termination.
  • Baseline comparison: Problem A matches centralized single-agent rates over A^M arms because all players maintain identical sufficient statistics.Shared rewards make empirical means and confidence intervals identical across players.
  • Baseline comparison: Problem B incurs a multiplicative M fixed-budget overhead and an additive log M fixed-confidence overhead from independent concentration events.These are the costs of requiring all player-specific streams to concentrate simultaneously.
  • Baseline comparison: Problem C adds a 4× fixed-confidence penalty and loses the adaptive allocation benefit of UCB-Intervals in fixed budget.Its fixed-budget exponent is weaker under the stated regime, while enlarged consensus radii drive the fixed-confidence penalty.

4 Problem A: Action Asymmetry

In Problem A, shared rewards and a fixed pre-agreed ordering enable synchronous, communication-free elimination despite hidden actions. The resulting fixed-budget and fixed-confidence guarantees have no multi-player overhead relative to centralized identification over A^M arms.

  • Coordination mechanism: Shared rewards make every player maintain identical empirical means and confidence intervals, so eliminations occur synchronously.A fixed ordering supplies the remaining coordination needed when actions are unobservable.
  • Algorithm: UCB-Intervals initializes confidence intervals, selects arms by a fixed ordering, and removes an arm once K candidates dominate it.All players pull the corresponding component and update the shared interval after observing the common reward.
  • Fixed budget: The fixed-budget algorithm completes all eliminations within horizon T when α ≤ T/(16H1).The theorem uses radius α/n_a(t), with a common statistic across players.
  • Fixed confidence: The fixed-confidence variant returns the correct top-K with probability at least 1−δ using a time-uniform confidence radius.Its radius includes log(π^2A^Mt^2/(3δ)) divided by the number of arm samples.
  • Guarantees: Problem A has no multi-player overhead: its fixed-budget and fixed-confidence guarantees are structurally identical to centralized UCB-E bounds over A^M arms.The two objectives differ in whether sampling is allocated through a fixed horizon or adaptively until certification.

5 Problem B: Reward Asymmetry

Problem B combines observable joint actions with private rewards, so players must coordinate despite diverging estimates. Its decentralized method uses deviations as elimination signals, while its guarantees quantify the cost of independent concentration.

  • Information asymmetry: Private rewards make players’ empirical means diverge, so they may become ready to eliminate the same arm at different rounds.Each player estimates every arm from an independent reward stream.
  • Implicit coordination: Observable deviations synchronize asynchronous eliminations without communication: a player pulls an off-schedule component when its intervals certify an arm is dominated.All players observe the realized joint action and remove the arm when a deviation occurs.
  • Guarantees: Theorem 6 and Theorem 7 provide fixed-budget and fixed-confidence guarantees for the decentralized UCB-Intervals algorithm.The fixed-budget and fixed-confidence variants are stated separately for Problem B.
  • Statistical cost: M independent concentration events make Problem B’s fixed-budget bound exactly M times Problem A’s, while fixed-confidence pays only an additive log M term.The fixed-budget factor arises because all players’ confidence conditions must hold simultaneously; the fixed-confidence overhead is logarithmic.
  • Signaling overhead: At most A^M − K off-schedule pulls are wasted for signaling, which is lower-order relative to the required Ω(H_1 log(1/δ)) samples.The signaling cost is absorbed into the constants of the fixed-confidence theorems.
  • Robustness: Under noisy or partial action observation, repeated deviation patterns can tolerate corrupted observations, but adversarial misobservation is left for future work.Repeating a signal for ℓ rounds tolerates floor((ℓ−1)/2) corrupted observations at an ℓ-fold signaling cost.

6 Problem C: Full Asymmetry

Problem C removes both shared rewards and observable actions, eliminating the coordination mechanisms available in the other regimes. The paper therefore uses uniform exploration and enlarged confidence radii, yielding a consensus-driven penalty and limited adaptivity.

  • Full asymmetry: Without shared rewards or observable actions, Problem C cannot use fixed-ordering coordination or deviation signaling.Players instead pre-agree on a deterministic round-robin schedule over all joint arms.
  • Uniform exploration: Uniform exploration visits every joint arm floor(T/A^M) times, and each player independently returns its empirical top-K arms.The procedure requires no online coordination.
  • Consensus: A suitably enlarged confidence radius lets players certify a common top-K set even though their private certification times differ.The round-robin schedule keeps sample counts synchronized, while the enlarged radius supports cross-player consistency.
  • Guarantees: Theorem 10 and Theorem 11 give fixed-budget and fixed-confidence guarantees for uniform exploration under full asymmetry.The fixed-confidence result uses the enlarged per-player radius.
  • Adaptivity: Problem C’s uniform exploration error can be slower than UCB-Intervals on non-uniform instances because it over-explores easy arms.For non-uniform gaps, H_1 can be much smaller than A^M/Δ^2, whereas the uniform schedule continues visiting every arm.
  • Consensus cost: A factor-2 radius enlargement quadruples per-arm sampling, producing a 4× overhead over Problems A and B as the dominant near-unavoidable consensus cost.The enlargement ensures that a separation certified by one player is consistent with every other player’s empirical means.
  • Stopping: Communication-free stopping cannot detect when the slowest teammate finishes; players must either continue the schedule indefinitely or use one end-of-run synchronization bit each.The latter yields simultaneous termination at the maximum private certification time.
  • Scope and open question: Local freezing does not improve the worst case, and whether a teammate-safe non-uniform schedule can beat uniform exploration without communication remains open.When every arm is a boundary arm, no arm is safe to freeze and the schedule still visits all A^M arms.

7 Unified Analysis and Optimality

The paper unifies the three observability regimes through multiplicity c and consensus factor ρ, then establishes fixed-confidence guarantees and matching lower bounds. The statistical cost of decentralization is logarithmic in c but quadratic in ρ, with full asymmetry incurring a 4× penalty.

  • Unified guarantee: The unified meta-theorem represents Problems A, B, and C as (c, ρ) = (1, 1), (M, 1), and (M, 2).Multiplicity counts simultaneous confidence events, while ρ captures the radius inflation required for unanimous output.
  • Unified guarantee: Theorem 14 gives a δ-correct fixed-confidence algorithm whose stopping guarantee specializes to the three regime-specific theorems.Substituting the three parameter pairs recovers Theorems 5, 7, and 11.
  • Price of decentralization: Multiplicity c contributes only an additive logarithmic term, whereas consensus factor ρ enters quadratically and dominates the sample-complexity cost.Moving from ρ = 1 in Problems A and B to ρ = 2 in Problem C multiplies stopping time by 4.
  • Lower bounds: Change-of-measure lower bounds apply to every regime, and fixed-budget error cannot decay faster than exp(-O(T/H1)) on some instance.For Problems B and C, the same per-arm lower bound applies to each player’s private reward stream.
  • Near-optimality: Problem A is asymptotically optimal up to the universal exploration log-factor, Problem B adds only a negligible log M term, and Problem C is optimal up to ρ^2 = 4.The lower-bound comparison establishes near-optimality across all three regimes.
  • Open gap: An oracle pooling the M independent observations could achieve an M-fold round reduction, but communication-free algorithms cannot attain that pooled rate under the established bound.Repurposing Problem B’s deviation channel to approach the pooled rate remains open.

8 Experiments

Experiments compare the three decentralized algorithms across fixed-budget, fixed-confidence, and scalability settings. Problem A benefits from adaptive elimination, Problem B is affected by independent false alarms, and Problem C pays for uniform exploration and enlarged confidence radii.

  • Experimental setup: On a synthetic Gaussian instance, the top-3 arms are {0, 1, 2}, with boundary gap Δ = 0.22 and H1 ≈ 109.The experiment uses M = 2 players, A = 3 actions each, and nine joint arms.
  • Fixed-budget experiment: At small budgets, Problem B has the highest error, while Problem C has the lowest error at small-to-moderate budgets.Problem B’s deviation signal inflates false eliminations; Problem C benefits from every reward stream contributing to each arm estimate.
  • Fixed-confidence experiment: In fixed-confidence trials, Problems A and B stop at τ ≈ 82–88,000, whereas Problem C requires τ ≈ 1.3 × 10^6 rounds, roughly 15× longer.Problem C samples all N arms uniformly and uses an enlarged confidence radius.
  • Scalability: As M grows from 2 to 5 at T = 24,000, Problem A remains strongest with error ≤ 0.07, while Problem C approaches 0.65 and Problem B approaches 0.98.The per-arm budget shrinks as N = A^M grows, and Problem B reflects an M-fold union bound over independent elimination signals.
  • Scope and limitations: The evaluation uses small joint spaces because fixed-confidence runs, especially Problem C, are computationally heavy at these sizes.Large-AM evaluation under additive structure is identified as a next empirical step.

9 Structured Rewards: Additive Decomposition

Additive reward structure lets the paper replace the exponential joint-arm problem with reference-arm estimation, while revealing and removing an unnecessary player-dependent overhead for best-arm identification.

  • Reference design: Reference arms determine every joint mean through contrasts with a fixed profile, allowing confidence intervals for all joint arms to be reconstructed.The construction uses the MA reference arms obtained by changing one coordinate at a time.
  • Reference design: The reference-design algorithm samples only MA reference arms and reconstructs all A^M confidence intervals without sampling the remaining arms.A linear combination of M+1 reference estimators introduces O(M^2) variance inflation, while the union bound ranges over MA reference arms.
  • Structured reward reduction: Additive decomposition collapses the exponential joint-arm count to a polynomial dependence on M and A.The effective arm count changes from Θ(A^M) to polynomial scale under additive rewards.
  • Best-arm specialization: The reference design incurs an O(M^3) overhead for communication-free identification.This overhead arises from estimating joint means one reference arm at a time.
  • Best-arm specialization: For K = 1, the stratified design achieves best-arm complexity independent of M and matches a lower bound based on the smallest per-player gap.The bound is therefore tight in its dependence on the number of players, whereas the reference design is loose by Θ(M^3).

10 Conclusions

The paper shows that communication-free top-K identification can exploit shared rewards, observable deviations, or enlarged confidence radii across three asymmetry regimes, while retaining unavoidable joint-action dependence and identifying open limits.

  • Conclusions: The framework studies top-K joint-arm identification across three information-asymmetry regimes and supplies decentralized, communication-free algorithms with fixed-budget and fixed-confidence guarantees.The algorithms extend elimination methods to enable implicit coordination under limited information.
  • Conclusions: Shared rewards preserve synchronous elimination despite hidden actions, observable deviations synchronize candidate sets, and enlarged confidence radii provide consensus under full asymmetry.Each regime uses the common signal that remains available to its players.
  • Conclusions: A central open problem is whether Problem B's deviation channel can approach the pooled Θ(H1 log(1/δ)/M) rate and close the M-fold gap to oracle algorithms.Other proposed directions include adaptive orderings, nonstationary or adversarial rewards, and structured reward tensors.
  • Conclusions: The study is positioned against collaborative pure exploration and decentralized multi-player bandits, whose typical assumptions include pooled observations, explicit communication, or collision-based coordination.The paper instead targets joint actions with asymmetric local information.
  • Conclusions: All bounds scale with A^M, and this dependence is unavoidable by reduction to single-player top-K identification over A^M arms.The same joint-action scaling is reflected in the lower-bound perspective.

E.7 Proof of Theorem 11

The proof establishes a unified correctness and stopping-time argument for the asymmetry regimes by controlling independent player streams and enlarging confidence radii when consensus is otherwise unavailable.

  • Consensus: Identical schedules and radii make certification imply the true top-K set, so players agree even when their certification times differ.Committed players continue their scheduled component, preserving the coordination argument.
  • Good event: A time-uniform union bound controls c independent player streams across A^M arms, with c = 1 for shared rewards and c = M otherwise.The multiplicity enters through the number of relevant player-arm streams that must be controlled.
  • Correctness: Under the good event, inflated confidence intervals contain the true means, preventing erroneous top-K elimination and ensuring correct certification.For full asymmetry, the enlarged radius also makes one player's certified separation consistent with every other player's estimates.
  • Stopping time: A factor-2 radius enlargement increases required pulls by 4× and yields the stated factor-8 stopping-time term.The proof derives this from the condition needed to separate suboptimal arms from the K-th candidate.
  • Lower bound: The lower bound applies change of measure to alternative instances differing in one arm, and summing over all A^M arms gives Eν[τ] ≥ 2H1 log(1/(2.4δ)).The argument uses the KL divergence of the altered reward distributions and the correctness requirement under both instances.

F Experimental Details

The experiments combine synthetic Gaussian and CTR-style Bernoulli instances with fixed-budget and fixed-confidence protocols, while the PAC extension removes dependence on the smallest gap.

  • Data-generating processes: The experiments use a synthetic Gaussian instance with M = 2, A = 3, K = 3, boundary gap Δ = 0.22, and H1 ≈ 109.The instance has nine joint arms and unit-variance Gaussian noise.
  • Data-generating processes: CTR-style experiments model rewards as Bernoulli click outcomes with arm-specific means in (0, 1).The fixed-budget and fixed-confidence panels use these click-through-rate instances alongside the synthetic setting.
  • Experimental protocol: Each plotted point averages independent trials with fresh reward draws, and error bars report the standard error of the mismatch indicator.The trial counts differ across panels, with fewer Problem C trials because of its long uniform runs.
  • Experimental protocol: Fixed-budget runs use exactly T rounds, whereas fixed-confidence runs stop when certification fires and record the stopping round.An error is recorded when the returned candidate set differs from the true top-K set.
  • PAC extension: The ε-PAC extension replaces each gap by max{Δ⟨K⟩_a, ε}, producing an instance-independent stopping bound O(ρ^2(A^M/ε^2) log(...)).This removes dependence on the smallest gap because arms within ε of the boundary need not be separated.
Loading 2608.22120v1…