Problem Dependent Reinforcement Learning Bounds Which Can Identify Bandit Structure in MDPs
This work addresses the problem of algorithm adaptability for researchers and practitioners in reinforcement learning, showing incremental progress by demonstrating that MDP algorithms can inherently handle bandit structures.
The paper investigates whether reinforcement learning algorithms for Markov Decision Processes (MDPs) can automatically achieve optimal performance bounds in simpler settings like Contextual Bandits without algorithm modification, finding that a minor variant of an existing MDP algorithm matches the best possible regret bound of ̃O(√SAT) in tabular Contextual Bandits.
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.