Multitask Bandit Learning Through Heterogeneous Feedback Aggregation

Abstract

In many real-world applications, multiple agents seek to learn how to perform highly related yet slightly different tasks in an online bandit learning protocol. We formulate this problem as the $\epsilon$-multi-player multi-armed bandit problem, in which a set of players concurrently interact with a set of arms, and for each arm, the reward distributions for all players are similar but not necessarily identical. We develop an upper confidence bound-based algorithm, RobustAgg$(\epsilon )$, that adaptively aggregates rewards collected by different players. In the setting where an upper bound on the pairwise similarities of reward distributions between players is known, we achieve instance-dependent regret guarantees that depend on the amenability of information sharing across players. We complement these upper bounds with nearly matching lower bounds. In the setting where pairwise similarities are unknown, we provide a lower bound, as well as an algorithm that trades off minimax regret guarantees for adaptivity to unknown similarity structure.

References in corpus (19)

• A Contextual-Bandit Approach to Personalized News Article Recommendation
• Distributed Learning in Multi-Armed Bandit with Multiple Players
• Contextual Bandits with Similarity Information
• Distributed Clustering of Linear Bandits in Peer to Peer Networks
• Online Clustering of Bandits
• Sample Complexity of Multi-task Reinforcement Learning
• Online Interactive Collaborative Filtering Using Multi-Armed Bandit with Dependent Arms
• Weighted Linear Bandits for Non-Stationary Environments
• Sequential Transfer in Multi-armed Bandit with Finite Set of Models
• Model Selection in Contextual Stochastic Bandit Problems
• Individual Regret in Cooperative Nonstochastic Multi-Armed Bandits
• Decentralized Multi-player Multi-armed Bandits with No Collision Information
• Warm-starting Contextual Bandits: Robustly Combining Supervised and Bandit Feedback
• Selfish Robustness and Equilibria in Multi-Player Bandits
• Distributed Bandit Learning: Near-Optimal Regret with Efficient Communication
• Taking a hint: How to leverage loss predictors in contextual bandits?
• Polynomial Cost of Adaptation for X -Armed Bandits
• Corralling Stochastic Bandit Algorithms
• Robust Multi-Agent Multi-Armed Bandits