Multi-armed (MAB) bandit algorithms are designed to adapt their experimentation rapidly as evidence is gathered. By quickly shifting measurements away from less promising actions or `arms', they focus measurement effort where it is most useful. The efficiency benefits of adaptive allocation are highlighted in the foundational theory of [1]}. They show that asymptotically optimal procedures sample each suboptimal arm with frequency inversely proportional to its squared distance from optimalityMore generally, if rewards noise is non-Gaussian, sampling frequencies are inversely proportional to a certain Kullback-Leibler divergence.. Upper confidence bound (UCB) algorithms and Thompson sampling [2]} are simple adaptive algorithms known to match this long-run behavior [1]}, [4]}, [5]}, [6]}. These flexible algorithms have then become the dominant approach to efficient experimentation in more complicated sequential decision-making problems, including reinforcement learning (RL). In RL, it is well understood that non-adaptive experimentation can be hopelessly inefficientThe insight dates back at least to [7]}. See for instance [8]} for a detailed explanation of the inefficiency of various simple exploration policies. To converge on optimal behavior, these can require a number of measurements that scales exponentially in the number of states, which is prohibitive. Successful algorithms need to efficiently navigate to states of the Markov decision process in order to learn about them, which requires adjusting how actions are selected based on early feedback about the true transition probabilities..
