The Fragility of Optimized Bandit Algorithms: Optimized Bandit Algorithms Have Truncated Cauchy Regret TailsResearch Paper
The stochastic multi-armed bandit is the basic model of sequential decision-making under uncertainty: in each round an algorithm chooses one of arms, observes a random reward from that arm's distribution, and tries to play the best arm as often as possible. Since Lai and Robbins (1985) the standard of quality has been the expected regret, and an algorithm…