Thompson Sampling for Robust Transfer in Multi-Task Bandits

Zhi Wang, Chicheng Zhang, Kamalika Chaudhuri

TL;DR

This paper introduces ROBUSTAGG-TS($\epsilon$), a novel Thompson Sampling-based algorithm for multi-task multi-armed bandits that robustly transfers knowledge between similar tasks. By intelligently switching between shared and individual data, it achieves near-optimal theoretical regret bounds and significantly outperforms existing UCB-based methods in empirical performance.

What Problem Does This Paper Address?

In many real-world scenarios—such as personalized healthcare robotics or recommendation systems—multiple agents (players) face similar but not identical tasks. While data from one agent could theoretically help another learn faster, blindly sharing data can lead to negative transfer, where differences between tasks actually impair performance.

This paper tackles the $\epsilon$-MPMAB (multi-player multi-armed bandit) problem, where the reward distributions for the same arm across different players are similar within a factor of $\epsilon$. The challenge is to design an algorithm that leverages this similarity to speed up learning (reducing "regret") while remaining robust to the slight differences between players. Previous solutions were based on Upper Confidence Bound (UCB) algorithms, which have strong theoretical guarantees but often perform poorly in practice compared to Thompson Sampling (TS).

Methods

The core contribution is the ROBUSTAGG-TS($\epsilon$) algorithm. For every arm and player, it maintains two Gaussian "posterior" distributions:

  1. Individual Posterior: Based solely on the player's own interactions.
  2. Aggregate Posterior: Based on data from all players, offset by a bonus term $\epsilon$ to account for task dissimilarity.

The algorithm uses a bias-variance trade-off to choose between them. Initially, it uses the aggregate posterior because more data means lower variance. However, once a player has collected enough of their own data (surpassing a threshold determined by $\epsilon$ and the time horizon $T$), it switches to the individual posterior to eliminate the bias introduced by other players' data.

Theoretically, analyzing Thompson Sampling in this setting is much harder than UCB. The authors developed a novel concentration inequality for multi-task data aggregation at random stopping times to prove that their algorithm is near-optimal.

Key Insights and Ideas

  • Subpar Arms are the Key: The benefit of transfer learning is most pronounced for "subpar arms"—arms that are clearly not optimal for any player. Data sharing allows players to quickly identify and stop pulling these arms.
  • TS vs. UCB Efficiency: Thompson Sampling is empirically superior because it is more efficient at managing "near-optimal" arms. While UCB might pull these arms many times to reduce uncertainty, TS naturally focuses more on the truly optimal arms.
Percentage of total pulls by arm optimality. ROBUSTAGG-TS efficiently focuses on optimal arms while minimizing pulls on subpar arms.
  • Delayed Updates for Theory: A unique design choice in the algorithm is only updating a player's posterior for an arm when that specific player pulls it. While seemingly counterintuitive for "sharing," this "delayed update" creates an invariant property that makes the complex frequentist analysis possible.

Key Results

The researchers evaluated their algorithm using synthetic data to precisely control the environment (20 players, 10 arms, Bernoulli rewards, 50,000 rounds). The empirical results show that ROBUSTAGG-TS($\epsilon$) is the clear winner across various problem settings.

Cumulative collective regret over 50,000 rounds. ROBUSTAGG-TS(0.15) significantly outperforms baselines.
  • Superior Regret Reduction: In instances with many subpar arms, ROBUSTAGG-TS($\epsilon$) incurs far less regret than both UCB-based transfer methods and standard TS without transfer.
  • Robustness: Even when there are no subpar arms (an "unfavorable" case for transfer), the algorithm remains competitive with standard individual Thompson Sampling, showing it doesn't suffer from significant negative transfer.
  • Theoretical Tightness: The frequentist analysis proves that the algorithm's regret is near-optimal, matching lower bounds modulo logarithmic factors.

Limitations and Future Work

  • Knowledge of $\epsilon$: The current algorithm requires the dissimilarity parameter $\epsilon$ to be known beforehand. The authors note that if $\epsilon$ is completely unknown, achieving sublinear regret through transfer is theoretically impossible in the worst case, but finding ways to estimate it in practice remains an open challenge.
  • Lower-Order Terms: There is an additive $O(M^2K)$ term in the regret bound that does not depend on the time horizon $T$. Future work could aim to reduce this constant overhead.
  • Real-World Application: While synthetic results are promising, testing the algorithm in complex, non-stationary real-world environments is a logical next step.

Summary updated

Abstract

We study the problem of online multi-task learning where the tasks are performed within similar but not necessarily identical multi-armed bandit environments. In particular, we study how a learner can improve its overall performance across multiple related tasks through robust transfer of knowledge. While an upper confidence bound (UCB)-based algorithm has recently been shown to achieve nearly-optimal performance guarantees in a setting where all tasks are solved concurrently, it remains unclear whether Thompson sampling (TS) algorithms, which have superior empirical performance in general, share similar theoretical properties. In this work, we present a TS-type algorithm for a more general online multi-task learning protocol, which extends the concurrent setting. We provide its frequentist analysis and prove that it is also nearly-optimal using a novel concentration inequality for multi-task data aggregation at random stopping times. Finally, we evaluate the algorithm on synthetic data and show that the TS-type algorithm enjoys superior empirical performance in comparison with the UCB-based algorithm and a baseline algorithm that performs TS for each individual task without transfer.
BibTeX
@inproceedings{wang2022thompson,
  author = {Zhi Wang and Chicheng Zhang and Kamalika Chaudhuri},
  title = {{Thompson Sampling for Robust Transfer in Multi-Task Bandits}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
  url = {https://openreview.net/forum?id=fKAC4aBRv2},
}
Figure