Optimistic Posterior Sampling for Reinforcement Learning: Worst-Case Regret Bounds I: An Extended MDP with δ-Optimistic Samples for Hitting Times Has Diameter at Most D/(1−δ)Research Paper
Regret bounds for reinforcement learning in a single, non-episodic Markov decision process (MDP) are stated in terms of the diameter of the MDP: the worst expected time needed to travel between two states when the travel policy is chosen well. UCRL2 (Jaksch, Ortner and Auer, 2010) achieves regret , against a lower bound of …