Robust Multi-Agent Decision-Making with Heavy-Tailed Payoffs
We study the heavy-tailed stochastic bandit problem in the cooperative multiagent setting, where a group of agents interact with a common bandit problem, while communicating on a network with delays. Existing algorithms for the stochastic bandit in this setting utilize confidence intervals arising from an averaging-based communication protocol known as~\textit{running consensus}, that does not lend itself to robust estimation for heavy-tailed settings. We propose \textsc{MP-UCB}, a decentralized multi-agent algorithm for the cooperative stochastic bandit that incorporates robust estimation with a message-passing protocol. We prove optimal regret bounds for \textsc{MP-UCB} for several problem settings, and also demonstrate its superiority to existing methods. Furthermore, we establish the first lower bounds for the cooperative bandit problem, in addition to providing efficient algorithms for robust bandit estimation of location.
Code (0)
등록된 구현이 없습니다.
Tasks
Decision MakingSimilar Papers 제목 키워드 기반
Risk exchange under infinite-mean Pareto models
We study the optimal decisions of agents who aim to minimize their risks by allocating their positions over extremely heavy-tailed (i.e., infinite-mean) and possibly dependent losses. The loss distributions of our focus …
Making Reliable and Flexible Decisions in Long-tailed Classification
Long-tailed classification is challenging due to its heavy imbalance in class probabilities. While existing methods often focus on overall accuracy or accuracy for tail classes, they overlook a critical aspect: certain t…
Decision Makingimage-classificationImage ClassificationUncertainty QuantificationMulti-agent Multi-armed Bandit with Fully Heavy-tailed Dynamics
We study decentralized multi-agent multi-armed bandits in fully heavy-tailed settings, where clients communicate over sparse random graphs with heavy-tailed degree distributions and observe heavy-tailed (homogeneous or h…
Multi-Armed BanditsOn Proximal Policy Optimization's Heavy-tailed Gradients
Modern policy gradient algorithms such as Proximal Policy Optimization (PPO) rely on an arsenal of heuristics, including loss clipping and gradient clipping, to ensure successful learning. These heuristics are reminiscen…
continuous-controlContinuous ControlMuJoCoCooperative Multi-Agent Bandits with Heavy Tails
We study the heavy-tailed stochastic bandit problem in the cooperative multi-agent setting, where a group of agents interact with a common bandit problem, while communicating on a network with delays. Existing algorithms…