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:
- Individual Posterior: Based solely on the player's own interactions.
- 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.
- 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.
- 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