Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence

Runlong Zhou, Zihan Zhang, Maryam Fazel +1

We study horizon-free regret minimization for finite-horizon time-homogeneous tabular Markov decision processes with $S$ states, $A$ actions, horizon $H$, and per-trajectory total…