  In this paper, we introduce the notion of replicable policies in the context
of stochastic bandits, one of the canonical problems in interactive learning. A
policy in the bandit environment is called replicable if it pulls, with high
probability, the exact same sequence of arms in two different and independent
executions (i.e., under independent reward realizations). We show that not only
do replicable policies exist, but also they achieve almost the same optimal
(non-replicable) regret bounds in terms of the time horizon. More specifically,
in the stochastic multi-armed bandits setting, we develop a policy with an
optimal problem-dependent regret bound whose dependence on the replicability
parameter is also optimal. Similarly, for stochastic linear bandits (with
finitely and infinitely many arms) we develop replicable policies that achieve
the best-known problem-independent regret bounds with an optimal dependency on
the replicability parameter. Our results show that even though randomization is
crucial for the exploration-exploitation trade-off, an optimal balance can
still be achieved while pulling the exact same arms in two different rounds of
executions.
