Horizon-Free Regret for Linear Markov Decision Processes

arXiv:2403.10738v1 Announce Type: new
Abstract: 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 …

abstract apply arxiv cs.lg decision free horizon however independent line linear markov planning polynomial process processes reinforcement reinforcement learning tabular transition type