Thompson Sampling for Robust Transfer in Multi-Task Bandits
Thompson Sampling for Robust Transfer in Multi-Task Bandits
复制标题
DOI：
10.48550/arxiv.2206.08556
复制
发表时间：
2022-06
期刊：
影响因子：
--
通讯作者：
Zhi Wang;Chicheng Zhang;Kamalika Chaudhuri
中科院分区：
文献类型：
--
作者：
Zhi Wang;Chicheng Zhang;Kamalika Chaudhuri
我们研究了在线多任务学习问题，其中任务是在相似但不一定相同的多臂匪徒环境中执行的。特别是，我们研究了学习者如何通过稳健的知识转移来提高其在多个相关任务中的整体表现。虽然最近基于置信限(UCB)的算法在所有任务同时解决的情况下获得了近乎最优的性能保证，但汤普森采样(TS)算法通常具有更好的经验性能，目前尚不清楚该算法是否具有类似的理论特性。在这项工作中，我们提出了一种更通用的在线多任务学习协议的TS类型算法，它扩展了并发设置。我们给出了它的频域分析，并证明了它也是近最优的，使用了一种新的多任务数据集结的集中度不等式。最后，我们在合成数据上对该算法进行了评估，结果表明，与基于UCB的算法和不需要传输的基线算法相比，TS类型的算法具有更好的经验性能。
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.