Abstract
We study the problem of online multi-task learning where tasks are performed within similar but not necessarily identical multi-armed bandit environments. Specifically, we investigate how a learner can improve overall performance across multiple related tasks through the robust transfer of knowledge. While upper confidence bound (UCB)-based algorithms have recently achieved nearly-optimal performance guarantees in concurrent settings, the theoretical properties of Thompson sampling (TS) algorithms—which often exhibit superior empirical performance—have remained unclear. In this work, we present ROBUSTAGG-TS($\epsilon$), a TS-type algorithm for a general online multi-task learning protocol. We provide a frequentist analysis proving its near-optimality using a novel concentration inequality for multi-task data aggregation at random stopping times. Finally, we demonstrate that ROBUSTAGG-TS($\epsilon$) enjoys superior empirical performance compared to UCB-based methods and baseline TS algorithms without transfer.
Introduction
In many real-world applications, such as personalized medicine or fleet robotics, a learner must solve multiple "multi-armed bandit" (MAB) problems simultaneously. While each task (e.g., a specific patient or robot) is unique, they often share underlying similarities. Standard single-task learning approaches ignore these commonalities, leading to inefficient exploration. Conversely, naive transfer learning—aggregating all data regardless of task differences—risks "negative transfer," where task-specific nuances are washed out by biased aggregate data, degrading performance.
This paper addresses the challenge of robust aggregation: how to leverage data from related tasks to accelerate learning without being misled by inter-task dissimilarities. While recent UCB-based frameworks have addressed this, Thompson Sampling (TS) has lacked a rigorous frequentist analysis in the multi-task setting despite its practical popularity.
The ROBUSTAGG-TS($\epsilon$) Algorithm
The authors propose ROBUSTAGG-TS($\epsilon$), a Thompson Sampling variant designed for the $\epsilon$-Multi-Player Multi-Armed Bandit ($\epsilon$-MPMAB) problem. The algorithm is built on three core pillars:
1. Dual Posteriors
For every arm, each player (task) maintains two distinct Gaussian distributions:
- Individual Posterior: Constructed using only the player's local data.
- Aggregate Posterior: Constructed using pooled data from all $M$ players.
2. Switching Logic
The algorithm employs a strategic threshold based on a dissimilarity parameter, $\epsilon$. In the early stages of learning, when a player has few samples for a specific arm, they utilize the aggregate posterior to benefit from the "wisdom of the crowd." Once the player has collected enough local data to resolve the fine differences between tasks—specifically when local samples exceed a threshold of approximately $1/\epsilon^2$—the algorithm switches to the individual posterior.
3. Theoretical Innovation
Analyzing TS from a frequentist perspective is notoriously difficult due to the random nature of the sampling. The authors developed a novel concentration inequality for multi-task data aggregation at "random stopping times." This mathematical tool allows them to bound the regret and prove that the algorithm is nearly optimal.
Experimental Evaluation
The algorithm was evaluated using synthetic data to maintain precise control over the $\epsilon$ parameter. The experimental setup included:
- Environment: 30 randomly generated $\epsilon$-MPMAB instances.
- Scale: $M=20$ players, $K=10$ arms, and a time horizon of $T=50,000$ rounds.
- Constraints: Bernoulli rewards where arm means across players were constrained within $\epsilon=0.15$ of each other.
Key Results
- Empirical Superiority: ROBUSTAGG-TS($\epsilon$) consistently outperformed the UCB-based state-of-the-art (ROBUSTAGG) and a baseline that performed TS on each task individually.
- Theoretical Optimality: The regret bound for subpar arms (arms that are clearly suboptimal across tasks) improves by a factor of $M$ compared to non-transfer methods.
- Robustness: In scenarios where no subpar arms existed to exploit, the algorithm's performance remained competitive with standard TS, demonstrating that the transfer mechanism does not penalize the learner in unfavorable environments.
Discussion and Insights
The core contribution of this work is the formalization of the bias-variance tradeoff in transfer learning. Aggregated data reduces variance through a larger sample size but introduces bias due to task differences. ROBUSTAGG-TS($\epsilon$) identifies the "sweet spot" where variance reduction outweighs bias.
Furthermore, the research highlights that transfer learning is most effective for "subpar arms." For arms that are nearly optimal, the risk of negative transfer is higher, and the algorithm correctly prioritizes local data. While the current requirement for a known $\epsilon$ is a limitation, this work provides a robust foundation for future research into online $\epsilon$ estimation and real-world applications in recommendation systems and healthcare robotics.
Summary updated