Pareto Optimal Model Selection in Linear Bandits
Pareto Optimal Model Selection in Linear Bandits
复制标题
DOI：
--
复制
发表时间：
2021-02
期刊：
影响因子：
--
通讯作者：
Yinglun Zhu;R. Nowak
中科院分区：
文献类型：
--
作者：
Yinglun Zhu;R. Nowak
我们研究模型选择的线性土匪，学习者必须适应的维度（表示为$d_\星星$）的最小假设类包含真正的线性模型，同时平衡探索和利用。以前的论文为这个模型选择问题提供了各种保证，但有局限性;即，该分析需要有利的条件，允许进行廉价的统计测试来定位正确的假设类，或者基于“聚集”多个基本算法的想法，而这些算法在实践中通常表现相对较差。这些工作也主要集中在上界。在本文中，我们建立了模型选择问题的第一下界。我们的下限意味着，即使有一个固定的行动集，适应未知的维度$d_\星星$是有代价的：没有算法可以同时达到遗憾界$\widetilde{O}（\sqrt{d_\星星T}）$的所有值$d_\星星$。我们提出了帕累托最优算法，匹配的下限。实验结果表明，我们的算法享有上级性能相比，现有的。
We study model selection in linear bandits, where the learner must adapt to the dimension (denoted by $d_\star$) of the smallest hypothesis class containing the true linear model while balancing exploration and exploitation. Previous papers provide various guarantees for this model selection problem, but have limitations; i.e., the analysis requires favorable conditions that allow for inexpensive statistical testing to locate the right hypothesis class or are based on the idea of"corralling"multiple base algorithms, which often performs relatively poorly in practice. These works also mainly focus on upper bounds. In this paper, we establish the first lower bound for the model selection problem. Our lower bound implies that, even with a fixed action set, adaptation to the unknown dimension $d_\star$ comes at a cost: There is no algorithm that can achieve the regret bound $\widetilde{O}(\sqrt{d_\star T})$ simultaneously for all values of $d_\star$. We propose Pareto optimal algorithms that match the lower bound. Empirical evaluations show that our algorithm enjoys superior performance compared to existing ones.