Stochastic One-Sided Full-Information Bandit
Stochastic One-Sided Full-Information Bandit
复制标题
随机单边全信息老虎机
DOI：
10.1007/978-3-030-46133-1_10
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Wei Chen
中科院分区：
文献类型：
--
作者：
Haoyu Zhao;Wei Chen
本文研究了单边完全信息盗贼问题的随机形式，其中有$K$ARMS$[K]=1，2，\ldots，K，且玩ARM$I$将从ARM$I$的未知分布中获得报酬，同时获得所有ARM$j\gI$的报酬反馈.单边完全信息盗贼可以模拟在线重复二次价格拍卖，拍卖人可以在每一轮中选择保留价格，只有当竞拍者的出价高于保留价格时，竞拍者才会透露他们的出价。在本文中，我们提出了一种基于消元的算法来解决这个问题。基于消元的算法得到了分布独立的后悔上界$O(T\cdot\log(TK)})$和分布相关的上界$O((\logT+\log K)f(\Delta))$，其中$T$是时间范围，$\Delta$是ARM的平均奖赏与最佳ARM的平均奖赏之间的差距向量，$f(\Delta)$是一个依赖于我们将详细说明的差距向量的公式。我们的算法具有到目前为止最好的理论遗憾上界。我们还对其他可能的选择进行了经验验证。
In this paper, we study the stochastic version of the one-sided full information bandit problem, where we have $K$ arms $[K] = \{1, 2, \ldots, K\}$, and playing arm $i$ would gain reward from an unknown distribution for arm $i$ while obtaining reward feedback for all arms $j \ge i$. One-sided full information bandit can model the online repeated second-price auctions, where the auctioneer could select the reserved price in each round and the bidders only reveal their bids when their bids are higher than the reserved price. In this paper, we present an elimination-based algorithm to solve the problem. Our elimination based algorithm achieves distribution independent regret upper bound $O(\sqrt{T\cdot\log (TK)})$, and distribution dependent bound $O((\log T + \log K)f(\Delta))$, where $T$ is the time horizon, $\Delta$ is a vector of gaps between the mean reward of arms and the mean reward of the best arm, and $f(\Delta)$ is a formula depending on the gap vector that we will specify in detail. Our algorithm has the best theoretical regret upper bound so far. We also validate our algorithm empirically against other possible alternatives.