Collaborative Min-Max Regret in Grouped Multi-Armed Bandits
We study the impact of sharing exploration in multi-armed bandits in a grouped setting where a set of groups have overlapping feasible action sets [Baek and Farias '24]. In this grouped bandit setting, groups share reward observations, and the objective is to minimize the collaborative regret, defined as the maximum regret across groups. This naturally captures applications in which one aims to balance the exploration burden between groups or populations -- it is known that standard algorithms can lead to significantly imbalanced exploration cost between groups. We address this problem by introducing an algorithm Col-UCB that dynamically coordinates exploration across groups. We show that Col-UCB achieves both optimal minimax and instance-dependent collaborative regret up to logarithmic factors. These bounds are adaptive to the structure of shared action sets between groups, providing insights into when collaboration yields significant benefits over each group learning their best action independently.
Code (0)
등록된 구현이 없습니다.
Tasks
Multi-Armed BanditsMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Communication-Efficient Collaborative Regret Minimization in Multi-Armed Bandits
In this paper, we study the collaborative learning model, which concerns the tradeoff between parallelism and communication overhead in multi-agent multi-armed bandits. For regret minimization in multi-armed bandits, we …
Multi-agent Reinforcement LearningMulti-Armed Banditsreinforcement-learningReinforcement Learning (RL)Collaborative Multi-Agent Heterogeneous Multi-Armed Bandits
The study of collaborative multi-agent bandits has attracted significant attention recently. In light of this, we initiate the study of a new collaborative setting, consisting of $N$ agents such that each agent is learni…
Multi-Armed BanditsBlocked Collaborative Bandits: Online Collaborative Filtering with Per-Item Budget Constraints
We consider the problem of \emph{blocked} collaborative bandits where there are multiple users, each with an associated multi-armed bandit problem. These users are grouped into \emph{latent} clusters such that the mean r…
Collaborative FilteringMatrix CompletionMulti-Armed Bandits with Dependent Arms
We study a variant of the classical multi-armed bandit problem (MABP) which we call as Multi-Armed Bandits with dependent arms. More specifically, multiple arms are grouped together to form a cluster, and the reward dist…
Multi-Armed BanditsBatched Multi-armed Bandits Problem
In this paper, we study the multi-armed bandit problem in the batched setting where the employed policy must split data into a small number of batches. While the minimax regret for the two-armed stochastic bandits has be…
Multi-Armed Bandits