A Linear Response Bandit Problem
A Linear Response Bandit Problem
复制标题
线性响应强盗问题
DOI：
10.1214/11-ssy032
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
A. Zeevi
中科院分区：
文献类型：
--
作者：
A. Goldenshluger;A. Zeevi
我们考虑一个双臂老虎机问题，它涉及从两个非齐次总体中进行顺序抽样。每个总体中的响应由一个随机协变量向量和一个参数向量决定，这些参数的值事先未知。目标是使累积期望奖励最大化。我们在极小极大设定下研究这个问题，并开发出速率最优策略，该策略将基于最小二乘估计的短视行为与一种合适的“强制抽样”策略相结合。结果表明，在时间范围\(n\)内，遗憾以对数方式增长，并且在所有可行的问题实例中，没有任何策略能够实现更慢的增长率。在线性响应老虎机的这种设定下，次优行为的标识随协变量向量的值而变化，并且最优策略需要以与\(n\)成比例的速率从较差的总体中进行抽样。
We consider a two–armed bandit problem which involves sequential sampling from two non-homogeneous populations. The response in each is determined by a random covariate vector and a vector of parameters whose values are not known a priori. The goal is to maximize cumulative expected reward. We study this problem in a minimax setting, and develop rate-optimal polices that combine myopic action based on least squares estimates with a suitable “forced sampling” strategy. It is shown that the regret grows logarithmically in the time horizon n and no policy can achieve a slower growth rate over all feasible problem instances. In this setting of linear response bandits, the identity of the sub-optimal action changes with the values of the covariate vector, and the optimal policy is subject to sampling from the inferior population at a rate that grows like n.