Multi-task Representation Learning for Pure Exploration in Linear Bandits
Multi-task Representation Learning for Pure Exploration in Linear Bandits
复制标题
DOI：
10.48550/arxiv.2302.04441
复制
发表时间：
2023-02
期刊：
影响因子：
--
通讯作者：
Yihan Du;Longbo Huang;Wen Sun
中科院分区：
文献类型：
--
作者：
Yihan Du;Longbo Huang;Wen Sun
尽管最近表征学习在序列决策中取得了成功，但对纯探索情景(即确定最佳选项并使样本复杂性最小化)的研究仍然有限。本文研究了基于多任务表示学习的线性盗贼最佳ARM识别算法(RepBAI-LB)和上下文线性盗贼最佳策略识别算法(RepBPI-CLB)，这两种算法在临床试验和网页内容优化等领域有着广泛的应用。在这两个问题中，所有任务共享一个共同的低维线性表示，我们的目标是利用这一特性来加速所有任务的最佳ARM(策略)识别过程。对于这些问题，我们设计了计算和采样高效的算法DouExpDes和C-DouExpDes，它们执行双重实验设计来规划学习全局表示的最优样本分配。我们表明，通过学习任务之间的共同表示，我们的样本复杂性明显好于独立解决任务的原生方法。据我们所知，这是第一个展示表征学习对于多任务纯探索的好处的工作。
Despite the recent success of representation learning in sequential decision making, the study of the pure exploration scenario (i.e., identify the best option and minimize the sample complexity) is still limited. In this paper, we study multi-task representation learning for best arm identification in linear bandits (RepBAI-LB) and best policy identification in contextual linear bandits (RepBPI-CLB), two popular pure exploration settings with wide applications, e.g., clinical trials and web content optimization. In these two problems, all tasks share a common low-dimensional linear representation, and our goal is to leverage this feature to accelerate the best arm (policy) identification process for all tasks. For these problems, we design computationally and sample efficient algorithms DouExpDes and C-DouExpDes, which perform double experimental designs to plan optimal sample allocations for learning the global representation. We show that by learning the common representation among tasks, our sample complexity is significantly better than that of the native approach which solves tasks independently. To the best of our knowledge, this is the first work to demonstrate the benefits of representation learning for multi-task pure exploration.