Exploring Best Arm with Top Reward-Cost Ratio in Stochastic Bandits
Exploring Best Arm with Top Reward-Cost Ratio in Stochastic Bandits
复制标题
DOI：
10.1109/infocom41043.2020.9155362
复制
发表时间：
2020-07
期刊：
影响因子：
--
通讯作者：
Zhida Qin;Xiaoying Gan;Jia Liu;Hongqiu Wu;Haiming Jin;Luoyi Fu
中科院分区：
文献类型：
--
作者：
Zhida Qin;Xiaoying Gan;Jia Liu;Hongqiu Wu;Haiming Jin;Luoyi Fu
多臂强盗模型中的最佳臂识别问题在频谱感知、在线广告、云计算等实际应用中有着广泛的应用。虽然已有大量的研究工作致力于这一领域，但大多数研究都没有考虑拉动行为的成本，即，在此基础上，研究了一个基于比率的最佳手臂识别问题，其中每只手臂都与一个随机奖励和一个随机成本相关联。对于任何δ ∈（0，1），概率至少为1−δ，参与者的目标是使用尽可能少的样本找到期望回报与期望成本之比最大的最佳手臂。为了解决这个问题，我们提出了三种算法：1）基因辅助算法GA; 2）间隙未知的逐次消除算法SEUG; 3）间隙和方差信息未知的逐次消除算法SEUG-V，其中间隙表示最优臂和次优臂之间的差异。我们表明，对于所有三种算法，样本复杂度，即，所有臂的拉动时间随着$\frac{1}{\delta }$的增加而按比例增长。此外，与现有的工作相比，我们的消除型算法的运行是独立的手臂相关的参数，这是更实用。此外，我们还给出了Bernoulli分布下任意算法的样本复杂度的一个基本下界，并证明了所提出的三个算法的样本复杂度在$\log \frac{1}{\delta }$意义下与该下界相匹配.最后，我们通过数值实验验证了我们的理论结果。
The best arm identification problem in multi-armed bandit model has been widely applied into many practical applications, such as spectrum sensing, online advertising, and cloud computing. Although lots of works have been devoted into this area, most of them do not consider the cost of pulling actions, i.e., a player has to pay some cost when she pulls an arm. Motivated by this, we study a ratio-based best arm identification problem, where each arm is associated with a random reward as well as a random cost. For any δ ∈ (0,1), with probability at least 1−δ, the player aims to find the optimal arm with the largest ratio of expected reward to expected cost using as few samplings as possible. To solve this problem, we propose three algorithms: 1) a genie-aided algorithm GA; 2) the successive elimination algorithm with unknown gaps SEUG; 3) the successive elimination algorithm with unknown gaps and variance information SEUG-V, where gaps denote the differences between the optimal arm and the suboptimal arms. We show that for all three algorithms, the sample complexities, i.e., the pulling times for all arms, grow logarithmically as $\frac{1}{\delta }$ increases. Moreover, compared to existing works, the running of our elimination-type algorithms is independent of the arm-related parameters, which is more practical. In addition, we also provide a fundamental lower bound for sample complexities of any algorithms under Bernoulli distributions, and show that the sample complexities of the proposed three algorithms match that of the lower bound in the sense of $\log \frac{1}{\delta }$. Finally, we validate our theoretical results through numerical experiments.