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 recommender system or crowdsourcing applications of online learning, a
human's preferences or abilities are often a function of the algorithm's recent
actions. Motivated by this, a significant line of work has formalized settings
where an action's loss is a function of the number of times that action was
recently played in the prior $m$ timesteps, where $m$ corresponds to a bound on
human memory capacity. To more faithfully capture decay of human memory with
time, we introduce the Weighted Tallying Bandit (WTB), which generalizes this
setting by requiring that an action's loss is a function of a \emph{weighted}
summation of the number of times that arm was played in the last $m$ timesteps.
This WTB setting is intractable without further assumption. So we study it
under Repeated Exposure Optimality (REO), a condition motivated by the
literature on human physiology, which requires the existence of an action that
when repetitively played will eventually yield smaller loss than any other
sequence of actions. We study the minimization of the complete policy regret
(CPR), which is the strongest notion of regret, in WTB under REO. Since $m$ is
typically unknown, we assume we only have access to an upper bound $M$ on $m$.
We show that for problems with $K$ actions and horizon $T$, a simple
modification of the successive elimination algorithm has $O \left( \sqrt{KT} +
(m+M)K \right)$ CPR. Interestingly, upto an additive (in lieu of
mutliplicative) factor in $(m+M)K$, this recovers the classical guarantee for
the simpler stochastic multi-armed bandit with traditional regret. We
additionally show that in our setting, any algorithm will suffer additive CPR
of $\Omega \left( mK + M \right)$, demonstrating our result is nearly optimal.
Our algorithm is computationally efficient, and we experimentally demonstrate
its practicality and superiority over natural baselines.

研究了一个权重计数的赌博算法，其中动作损失与最近 $m$ 个时间步骤中该动作被播放的次数的加权求和有关，并引入了 “重复暴露最优性” 的条件来最小化完备策略遗憾，提出了简单的修改后的连续消除算法，并对其进行了理论和实验分析。

加权记分贝叶斯多臂老虎机算法：通过重复曝光优化解决计算难题

Weighted Tallying Bandits: Overcoming Intractability via Repeated  Exposure Optimality

In this paper, we introduce a multi-armed bandit problem termed max-min
grouped bandits, in which the arms are arranged in possibly-overlapping groups,
and the goal is to find the group whose worst arm has the highest mean reward.
This problem is of interest in applications such as recommendation systems and
resource allocation, and is also closely related to widely-studied robust
optimization problems. We present two algorithms based successive elimination
and robust optimization, and derive upper bounds on the number of samples to
guarantee finding a max-min optimal or near-optimal group, as well as an
algorithm-independent lower bound. We discuss the degree of tightness of our
bounds in various cases of interest, and the difficulties in deriving uniformly
tight bounds.

介绍了一种多臂赌博机问题，称为最大最小分组赌博机问题，其中将赌臂分组，并旨在找到最差赌臂平均回报最高的组；提出两种基于连续淘汰和鲁棒优化的算法，并导出保证找到最优或接近最优组的样本数的上界，以及一个独立于算法的下界。探讨了各种相关情况下上下限的紧度以及导出统一紧限的困难。