This work is motivated by the growing demand for reproducible machine
learning. We study the stochastic multi-armed bandit problem. In particular, we
consider a replicable algorithm that ensures, with high probability, that the
algorithm's sequence of actions is not affected by the randomness inherent in
the dataset. We observe that existing algorithms require $O(1/\rho^2)$ times
more regret than nonreplicable algorithms, where $\rho$ is the level of
nonreplication. However, we demonstrate that this additional cost is
unnecessary when the time horizon $T$ is sufficiently large for a given $\rho$,
provided that the magnitude of the confidence bounds is chosen carefully. We
introduce an explore-then-commit algorithm that draws arms uniformly before
committing to a single arm. Additionally, we examine a successive elimination
algorithm that eliminates suboptimal arms at the end of each phase. To ensure
the replicability of these algorithms, we incorporate randomness into their
decision-making processes. We extend the use of successive elimination to the
linear bandit problem as well. For the analysis of these algorithms, we propose
a principled approach to limiting the probability of nonreplication. This
approach elucidates the steps that existing research has implicitly followed.
Furthermore, we derive the first lower bound for the two-armed replicable
bandit problem, which implies the optimality of the proposed algorithms up to a
$\log\log T$ factor for the two-armed case.

研究论文的主题是关于可复现机器学习中的随机多臂赌博问题，介绍了一个确保算法行动序列不受数据集内固有随机性影响的可复现算法，同时提出了探索 - 执行算法和连续淘汰算法，并扩展了对线性赌博问题的应用。

多臂赌博机中的可复制性是渐进自由的

Replicability is Asymptotically Free in Multi-armed Bandits

In this research, we investigate the high-dimensional linear contextual
bandit problem where the number of features $p$ is greater than the budget $T$,
or it may even be infinite. Differing from the majority of previous works in
this field, we do not impose sparsity on the regression coefficients. Instead,
we rely on recent findings on overparameterized models, which enables us to
analyze the performance the minimum-norm interpolating estimator when data
distributions have small effective ranks. We propose an explore-then-commit
(EtC) algorithm to address this problem and examine its performance. Through
our analysis, we derive the optimal rate of the ETC algorithm in terms of $T$
and show that this rate can be achieved by balancing exploration and
exploitation. Moreover, we introduce an adaptive explore-then-commit (AEtC)
algorithm that adaptively finds the optimal balance. We assess the performance
of the proposed algorithms through a series of simulations.

研究高维线性情境赌博问题，提出了探索后承诺（EtC）算法和自适应探索后承诺（AEtC）算法，通过分析表明这些算法可以在探索和利用之间找到最佳平衡，最终对算法的性能进行了评估。