CS Paper Radar

Robust Multi-Agent Bandits with Heavy-Tailed Rewards and Information Asymmetry

Daphne Feng, Ricardo Parada, Lily Jiang, Sophia Yi, William Chang

cs.LG cs.AI ·submitted 2026-08-11 06:10 UTC · v1

Abstract

The multi-armed bandit problem is a central framework in sequential decision-making, extensively studied under sub-Gaussian reward assumptions. However, real-world applications often involve heavy-tailed reward distributions and decentralized, information-asymmetric interactions. We study multi-agent multi-armed bandits with heavy-tailed rewards under three information-asymmetry regimes: unobserved actions with common rewards, observed actions with independent rewards, and unobserved actions with independent rewards. We develop robust decentralized algorithms for each setting and derive regret guarantees that nearly match centralized heavy-tailed rates. Experiments on a Pareto-distributed reward environment validate our theoretical findings and illustrate the trade-offs between synchronization, coordination, and exploration across the three regimes.

Closest papers

Nearest neighbours by meaning across the whole index.

DCM Bandits: Multiplayer Information Asymmetric Cascading Bandits for Multiple Clicks

cs.LG ·2026-08-12 ·Andy Wang, Charlton Shih, William Chang
top venue similarity 0.74
Abstract · Accepted to the Asia Conference on Machine Learning and Computing (ACMLC 2026)

In this work, we extend the Dependent Click Model (DCM) Bandits to a multiplayer information-asymmetric setting, where multiple agents interact with a shared ranked list and may observe multiple clicks per session, introducing new challenges for selection strategies. We study asymmetry in (1) actions and (2) rewards, providing sublinear regret guarantees for three settings where at least one asymmetry is present. Establishing matching information-theoretic lower bounds for these settings is left as an open problem. We further show that for small termination probabilities, the termination ranking need not be known, improving on prior single-agent results. Experiments confirm that our algorithms perform well across asymmetric environments and highlight the critical role of feedback structure, specifically the distinction between full versus first-click feedback, in coordinating exploration and minimizing regret.

0.34

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

cs.LG ·2026-08-22 ·Larissa Xu, Jasmine Nguyen, William Chang
similarity 0.73
Abstract

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.

0.04

Coordinating the Unknown Lipschitz Constant in Multiplayer Bandits

cs.LG cs.AI ·2026-08-11 ·Ricardo Parada, Chenzhang Zhao, William Chang
theory similarity 0.73
Abstract

Motivated by decentralized applications, we study cooperative multi-agent bandits in continuous (Lipschitz) action spaces when the Lipschitz constant is unknown. We consider three information structures: (A)~unobserved actions with common rewards, (B)~observed actions with independent rewards, and (C)~unobserved actions with independent rewards. In each case we design and analyze an algorithm that estimates the Lipschitz constant, chooses a discretization of the joint action space, and applies a cooperative bandit method to the induced discrete problem. Players never communicate once learning starts, so the central difficulty is that they must reach the \emph{same} discretization from their own data. We prove regret guarantees showing that common rewards and observable actions each supply this agreement for free, and that in their absence agreement can still be bought, through a dithered quantization of the estimate, at no cost in the leading order of the regret.

0.04

Decentralized Bandit Learning of Markov Perfect Equilibria

cs.LG math.OC ·2026-10-09 ·Felix Höfer, H. Mete Soner
theoryhot direction similarity 0.73
Abstract · 23 pages, 1 figure

We study decentralized bandit learning in discounted infinite-horizon, general-sum Markov games with continuous actions. Agents observe the public state, but only their own realized rewards, and use simultaneous perturbation stochastic approximation to update their actions. Under strong monotonicity of the negative running-reward gradients and sufficiently small time steps, we prove that the fully decentralized procedure converges almost surely to the unique stationary Markov perfect equilibrium. We obtain an $O(n^{-1/2})$ convergence rate and present a natural extension to episodic finite-horizon learning.

0.25

Improved Multiplayer Bandit Algorithm for Bernoulli Rewards

cs.AI stat.ML ·2026-08-11 ·Khang Nguyen, Ricardo Parada, William Chang
theory similarity 0.71
Abstract

We study the multiplayer multi-armed bandit problem with information asymmetry under Bernoulli rewards, for three information structures: asymmetry in actions, in rewards, and in both. Replacing the Hoeffding-style confidence intervals of prior work with Kullback--Leibler (KL) divergence-based bounds gives strictly tighter regret guarantees in each case. We propose \texttt{mKL-UCB}, \texttt{mKL-UCB-Intervals} and \texttt{mKL-DSEE}, and show that the improvement factor is at least two by Pinsker's inequality and far larger when reward means are near zero or one. For asymmetry in rewards we prove that two arms' KL intervals separate after a deterministic number of samples, and that $M$ independent players accelerate elimination further.

0.04

Exact Regret Frontiers and Externality Scheduling in Centralized Serial-Dictatorship Bandits

cs.GT cs.LGstat.ML ·2026-09-17 ·Lishang Xu, Guodong Ma, Pengcheng Weng, Zixuan Xia
similarity 0.71
Abstract · v3: exposition clarified; a sentence in Section 5.3 that was inaccurate for K > N removed, and the K = N condition stated in the introductio…

Exploration in centralized serial-dictatorship matching bandits must use complete matchings, so learning one player-arm pair can impose regret on others. We study this externality under a known common priority order and Gaussian rewards with unit variance. We show that the matching-level Graves-Lai constraints reduce to finitely many pairwise exploration quotas and, at top-choice-separated instances, yield a polynomial-size marginal linear program. At these instances, the exact attainable set of expected logarithmic regret coefficients is $G(θ)\mathcal{X}(θ)$, where $\mathcal{X}$ is the feasible matching-allocation set and $G$ maps allocations to player regret. The usual upper-closed Graves-Lai region can be strictly larger despite having the same Pareto-minimal boundary. We further show that identical exploration quotas can induce very different regret through their scheduling. Finally, we construct estimate-solve-track policies, uniformly good on the full row-strict class, that attain every fixed positively weighted optimum without assuming optimizer uniqueness. Every Pareto-minimal point is pointwise attainable, possibly through an instance-calibrated target.

0.19

Beyond Monotonicity: Stochastic Online Optimization under Semi-Bandit Feedback

cs.LG ·2026-11-02 ·Tsubasa Harada, Yasushi Kawase, Hanna Sumita
theory similarity 0.71
Abstract · 44 pages, 1 figure

We study stochastic online optimization (SOO) under semi-bandit feedback: in each of $T$ rounds, a policy adaptively observes $n$ independent random variables with unknown distributions, learning only from observed values. First-order stochastic dominance (FSD) monotonicity enables general reductions for learning SOO, but can fail when observations change future feasibility, resource use, or reference points. Our algorithm runs the dynamic program for the optimal policy, replacing each expectation by its most optimistic value over a confidence set of distributions. Its regret depends on the level-set complexity $s_i$ of the computed values as functions of the $i$th variable: the number of intervals needed to describe their superlevel sets. For rewards in $[0,1]$, the regret is $\tilde{O}(\sqrt{ST})$ without this monotonicity, where $S=\sum_{i=1}^n\min\{s_i,k_i\}$ and $k_i$ is the support size of the $i$th distribution, which may be infinite when $s_i$ is finite. For constant level-set complexities, regret is $\tilde{O}(\sqrt{nT})$, even for continuous distributions. The algorithm requires no knowledge of $s_i$, $k_i$, or the supports, and it also achieves regret $\tilde{O}(\sqrt{nkT})$ for supports of size at most $k$ without any level-set condition, which improves the previous bound $\tilde{O}(n(\sqrt{kT}+k))$ for FSD-monotone problems. We also prove a lower bound of $Ω(\min\{T,\sqrt{ST}\})$ for all positive integers $s_1,\ldots,s_n$ with $k_i=2s_i+1$, which holds even under full feedback and matches the upper bound up to logarithmic factors. We obtain $\tilde{O}(\sqrt{nT})$ regret for these problems, all nonmonotone under FSD: stochastic Boolean function evaluation, the full-information secretary problem, optimal stopping with loss aversion, scheduling with deadlines and correlated stochastic knapsack with unimodal rewards, and overbooking with group reservations.

0.16

Characterizing Oblivious Common-Reward Multi-Player Bandits: Universal Stationarity, Coordination Traps, and Certified Global Rates

cs.LG ·2026-10-21 ·Mingxiao Li, Wenhai Lai, Hongyu Wang
theory similarity 0.70
Abstract · 20 pages, including 11 pages of supplementary material

This paper presents a theoretical analysis of the oblivious common-reward multi-player multi-armed bandit (OC-MPMAB), a minimal multi-player bandit model in which multiple players select arms simultaneously and observe only a shared reward. Crucially, the players are fully oblivious: they do not observe the actions of other players and do not even know whether any other players exist. The contributions of this work are threefold. First, we prove that the independent gradient-bandit updates applied by the players jointly form an unbiased stochastic gradient estimator of a hidden product-policy objective. This property then yields a universal finite-time first-order stationarity guarantee for every instance. Second, we show that stationarity cannot, in general, be strengthened to global optimality. To illustrate this, we identify a product-policy trap obstruction that rules out the guarantee of global optimality. Third, we show that global optimality can be recovered under structural assumptions on the reward table. To make global optimality achievable, we introduce finite-table certificates that separately characterize product-gradient dominance and self-bounding stochastic noise. We then establish certificate-conditioned bounds on the product-policy gap and pseudo-regret. Consequently, the standard $O(1/t)$ product-policy gap and $O(\log T)$ pseudo-regret rates hold when the certificates are uniform.

0.10