Upper Confidence Bound (UCB) method is arguably the most celebrated one used
in online decision making with partial information feedback. Existing
techniques for constructing confidence bounds are typically built upon various
concentration inequalities, which thus lead to over-exploration. In this paper,
we propose a non-parametric and data-dependent UCB algorithm based on the
multiplier bootstrap. To improve its finite sample performance, we further
incorporate second-order correction into the above construction. In theory, we
derive both problem-dependent and problem-independent regret bounds for
multi-armed bandits under a much weaker tail assumption than the standard
sub-Gaussianity. Numerical results demonstrate significant regret reductions by
our method, in comparison with several baselines in a range of multi-armed and
linear bandit problems.

本文提出了一种基于乘数 bootstrap 的非参数和数据相关的 UCB 算法，并进一步将二阶校正融入该算法，在理论上，我们推导出了在比标准次高斯性更弱的尾部假设下的多臂老虎机的问题相关和问题无关的后悔边界，数值结果表明 UCB 算法相比其他基线在一系列多臂和线性老虎机问题中都有显著的降低后悔