Problem Dependent Reinforcement Learning Bounds Which Can Identify
  Bandit Structure in MDPs
  In order to make good decision under uncertainty an agent must learn from
observations. To do so, two of the most common frameworks are Contextual
Bandits and Markov Decision Processes (MDPs). In this paper, we study whether
there exist algorithms for the more general framework (MDP) which automatically
provide the best performance bounds for the specific problem at hand without
user intervention and without modifying the algorithm. In particular, it is
found that a very minor variant of a recently proposed reinforcement learning
algorithm for MDPs already matches the best possible regret bound $\tilde O
(\sqrt{SAT})$ in the dominant term if deployed on a tabular Contextual Bandit
problem despite the agent being agnostic to such setting.
