Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds

Strong worst-case performance bounds for episodic reinforcement learning but fortunately in practice RL algorithms perform much better than such would predict. Algorithms and theory that provide strong-dependent bounds could help illuminate the key features of what makes a problem hard and reduce the barrier to using RL algorithms in practice. As a towards this we derive an algorithm for finite horizon discrete MDPs and analysis that both yields state-of-the art worst-case regret bounds the dominant terms and yields substantially tighter bounds if the RL has small environmental norm, which is a function of the variance the next-state value functions. An important benefit of our algorithmic is it does not require apriori knowledge of a bound on the environmental. As a result of our analysis, we also help address an open learning theory~\{jiang2018open} about episodic MDPs with a constant upper-bound the sum of rewards, providing a regret bound with no H-dependence in the term that scales a polynomial function of the number of episodes.