The Price of Decentralization in Top-K Arm Identification

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× penalty under full asymmetry. The resulting stopping time scales as O!left(suma fraclog(AM/δ)Deltaa2right) and the fixed-budget error as exp(-Theta(T/H1)), with the dependence on the joint-action count AM shown to be unavoidable.