  What can an agent learn in a stochastic Multi-Armed Bandit (MAB) problem from
a dataset that contains just a single sample for each arm? Surprisingly, in
this work, we demonstrate that even in such a data-starved setting it may still
be possible to find a policy competitive with the optimal one. This paves the
way to reliable decision-making in settings where critical decisions must be
made by relying only on a handful of samples.
  Our analysis reveals that \emph{stochastic policies can be substantially
better} than deterministic ones for offline decision-making. Focusing on
offline multi-armed bandits, we design an algorithm called Trust Region of
Uncertainty for Stochastic policy enhancemenT (TRUST) which is quite different
from the predominant value-based lower confidence bound approach. Its design is
enabled by localization laws, critical radii, and relative pessimism. We prove
that its sample complexity is comparable to that of LCB on minimax problems
while being substantially lower on problems with very few samples.
  Finally, we consider an application to offline reinforcement learning in the
special case where the logging policies are known.
