Variance-Dependent Best Arm Identification
Variance-Dependent Best Arm Identification
复制标题
DOI：
--
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
P. Lu;Chao Tao;Xiaojin Zhang
中科院分区：
文献类型：
--
作者：
P. Lu;Chao Tao;Xiaojin Zhang
研究了随机多臂强盗对策中最佳臂的识别问题。给定一组从$1$到$n$索引的$n$ARM，每个ARM$i$与$[0，1]$上支持的未知报酬分布相关联，平均$\theta_i$和方差$\sigma_i^2$。假设$\theta_1>；\theta_2\geq\cdots\geq\theta_n$。我们提出了一种自适应算法，该算法探索ARM奖励的差距和方差，并基于收集的信息使用一种新的方法来做出未来的决策，该方法被称为分组中值消除}。所提出的算法保证以概率$(1-\Delta)$输出最佳ARM，最多使用$O\Left(\sum_{i=1}^n\Left(\FRAC{\sigma_i^2}{\Delta_i^2}+\FRAC{1}{\Delta_i}\right)(\ln\Delta^{-1}+\ln\ln\Delta_i^^-1})\Right)$个样本，其中$\Delta_i$($i\geq 2$)表示ARM$i$与最佳ARM之间的报酬差距，我们定义$\Delta_1=\Delta_2$。在一些有利的情况下，这实现了相对于方差无关算法的显著优势，并且与最先进的ARM相比，这是第一个消除了最佳ARM上的额外$\ln n$因子的结果。我们进一步证明了一个算法要达到同样的目的，$\Omega\Left(\sum_{i=1}^n\Left(\FRAC{\sigma_i^2}{\Delta_i^2}+\FRAC{1}{\Delta_i}\Right)}$样本是必要的，从而说明我们的算法在双对数项下是最优的。
We study the problem of identifying the best arm in a stochastic multi-armed bandit game. Given a set of $n$ arms indexed from $1$ to $n$, each arm $i$ is associated with an unknown reward distribution supported on $[0,1]$ with mean $\theta_i$ and variance $\sigma_i^2$. Assume $\theta_1>\theta_2 \geq \cdots \geq\theta_n$. We propose an adaptive algorithm which explores the gaps and variances of the rewards of the arms and makes future decisions based on the gathered information using a novel approach called \textit{grouped median elimination}. The proposed algorithm guarantees to output the best arm with probability $(1-\delta)$ and uses at most $O \left(\sum_{i = 1}^n \left(\frac{\sigma_i^2}{\Delta_i^2} + \frac{1}{\Delta_i}\right)(\ln \delta^{-1} + \ln \ln \Delta_i^{-1})\right)$ samples, where $\Delta_i$ ($i \geq 2$) denotes the reward gap between arm $i$ and the best arm and we define $\Delta_1 = \Delta_2$. This achieves a significant advantage over the variance-independent algorithms in some favorable scenarios and is the first result that removes the extra $\ln n$ factor on the best arm compared with the state-of-the-art. We further show that $\Omega \left( \sum_{i = 1}^n \left( \frac{\sigma_i^2}{\Delta_i^2} + \frac{1}{\Delta_i} \right) \ln \delta^{-1} \right)$ samples are necessary for an algorithm to achieve the same goal, thereby illustrating that our algorithm is optimal up to doubly logarithmic terms.