On the Optimality of Perturbations in Stochastic and Adversarial Multi-armed Bandit Problems
On the Optimality of Perturbations in Stochastic and Adversarial Multi-armed Bandit Problems
复制标题
随机和对抗性多臂老虎机问题中扰动的最优性
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Ambuj Tewari
中科院分区：
文献类型：
--
作者：
Baekjin Kim;Ambuj Tewari
研究了随机对抗性多臂盗贼问题中基于扰动的算法的最优性。对于随机情形，当报酬为亚高斯型时，我们给出了次威布尔扰动和有界扰动的统一后悔分析。对于参数为2的次威布尔扰动也有匹配的尾部下界，以及在支撑的两端有足够的概率质量的所有有界支撑扰动，我们的界限是实例最优的。对于对抗性环境，我们使用离散选择理论和极值理论的工具证明了对两种自然解方法的严格障碍。我们的结果表明，最优扰动，如果存在的话，将是Frechet型的。
We investigate the optimality of perturbation based algorithms in the stochastic and adversarial multi-armed bandit problems. For the stochastic case, we provide a unified regret analysis for both sub-Weibull and bounded perturbations when rewards are sub-Gaussian. Our bounds are instance optimal for sub-Weibull perturbations with parameter 2 that also have a matching lower tail bound, and all bounded support perturbations where there is sufficient probability mass at the extremes of the support. For the adversarial setting, we prove rigorous barriers against two natural solution approaches using tools from discrete choice theory and extreme value theory. Our results suggest that the optimal perturbation, if it exists, will be of Frechet-type.
DOI：
10.2307/2289692
发表时间：
1987-07
期刊：
--
影响因子：
--
作者：
S. Resnick
通讯作者：
S. Resnick