  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 \cite{efroni2018beyond}, 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.
