Horizon-Free Regret for Linear Markov Decision Processes
Zihan Zhang Jason D. Lee Yuxin Chen Simon S. Du
A recent line of works showed regret bounds in reinforcement learning (RL)
can be (nearly) independent of planning horizon, a.k.a.~the horizon-free
bounds. However, these regret bounds only apply to settings where a polynomial
dependency on the size of transition model is allowed, such as tabular Markov
Decision Process (MDP) and linear mixture MDP. We give the first horizon-free
bound for the popular linear MDP setting where the size of the transition model
can be exponentially large or even uncountable. In contrast to prior works
which explicitly estimate the transition model and compute the inhomogeneous
value functions at different time steps, we directly estimate the value
functions and confidence sets. We obtain the horizon-free bound by: (1)
maintaining multiple weighted least square estimators for the value functions;
and (2) a structural lemma which shows the maximal total variation of the
inhomogeneous value functions is bounded by a polynomial factor of the feature
dimension.