Adaptive Algorithm for Multi-Armed Bandit Problem with High-Dimensional Covariates
Adaptive Algorithm for Multi-Armed Bandit Problem with High-Dimensional Covariates
复制标题
高维协变量多臂老虎机问题的自适应算法
DOI：
10.1080/01621459.2022.2152343
复制
发表时间：
2023
影响因子：
3.7
通讯作者：
Liu, Ji
中科院分区：
文献类型：
--
作者：
Qian, Wei;Ing, Ching-Kang;Liu, Ji
本文研究了一个重要的序列决策问题，即带协变量的多臂随机强盗问题。在具有高维协变量的线性强盗框架下，我们提出了一种综合了武器淘汰和随机分配策略的通用多阶段武器分配算法。通过采用一类高维回归方法进行系数估计，本文提出的算法在新的研究范围下具有接近最优的有限时间后悔性能，该研究范围既不需要边际条件，也不需要竞争部门的奖励差距条件。基于协同验证的保证金效益，我们的算法表现出自适应性能，自动适应保证金和缺口条件，并在没有保证金或有保证金的两种研究范围内同时获得最佳后悔率，最高可达对数因子。除了令人满意的遗憾性能外，该算法还可以同时生成有用的竞争臂系数估计输出，并且可以实现估计一致性和变量选择一致性。通过广泛的仿真和两个实际数据评估实例，证明了该方法具有良好的经验性能。本文的补充材料可在网上获得。
This article studies an important sequential decision making problem known as the multi-armed stochastic bandit problem with covariates. Under a linear bandit framework with high-dimensional covariates, we propose a general multi-stage arm allocation algorithm that integrates both arm elimination and randomized assignment strategies. By employing a class of high-dimensional regression methods for coefficient estimation, the proposed algorithm is shown to have near optimal finite-time regret performance under a new study scope that requires neither a margin condition nor a reward gap condition for competitive arms. Based on the synergistically verified benefit of the margin, our algorithm exhibits adaptive performance that automatically adapts to the margin and gap conditions, and attains optimal regret rates simultaneously for both study scopes, without or with the margin, up to a logarithmic factor. Besides the desirable regret performance, the proposed algorithm simultaneously generates useful coefficient estimation output for competitive arms and is shown to achieve both estimation consistency and variable selection consistency. Promising empirical performance is demonstrated through extensive simulation and two real data evaluation examples. Supplementary materials for this article are available online.