  We formulate a multi-armed bandit (MAB) approach to choosing expert policies
online in Markov decision processes (MDPs). Given a set of expert policies
trained on a state and action space, the goal is to maximize the cumulative
reward of our agent. The hope is to quickly find the best expert in our set.
The MAB formulation allows us to quantify the performance of an algorithm in
terms of the regret incurred from not choosing the best expert from the
beginning. We first develop the theoretical framework for MABs in MDPs, and
then present a basic regret decomposition identity. We then adapt the classical
Upper Confidence Bounds algorithm to the problem of choosing experts in MDPs
and prove that the expected regret grows at worst at a logarithmic rate.
Lastly, we validate the theory on a small MDP.
