Multiple-step greedy policies in online and approximate reinforcement learning

Yonathan Efroni (1) , Gal Dalal (1) , Bruno Scherrer (2, 3) , Shie Mannor (1)

1 EE-Technion - Department of Electrical Engineering - Technion [Haïfa]
2 BIGS - Biology, genetics and statistics
3 IECL - Institut Élie Cartan de Lorraine

Multiple-step lookahead policies have demonstrated high empirical competence in Reinforcement Learning, via the use of Monte Carlo Tree Search or Model Predictive Control. In a recent work [5], multiple-step greedy policies and their use in vanilla Policy Iteration algorithms were proposed and analyzed. In this work, we study multiple-step greedy algorithms in more practical setups. We begin by highlighting a counter-intuitive difficulty, arising with soft-policy updates: even in the absence of approximations, and contrary to the 1-step-greedy case, monotonic policy improvement is not guaranteed unless the update stepsize is sufficiently large. Taking particular care about this difficulty, we formulate and analyze online and approximate algorithms that use such a multi-step greedy operator.

Domaines: Optimisation et contrôle [math.OC]; Recherche opérationnelle [math.OC]; Complexité [cs.CC]; Apprentissage [cs.LG]; Statistiques [math.ST]

Yonathan Efroni, Gal Dalal, Bruno Scherrer, Shie Mannor. Multiple-step greedy policies in online and approximate reinforcement learning. NeurIPS 2018 - Thirty-second Conference on Neural Information Processing Systems, Dec 2018, Montréal, Canada. ⟨hal-01927962⟩