Policy Mirror Descent with Lookahead
Authors: Kimon Protopapas
Anas Barakat
Venue: NeurIPS 2024 poster (2024)
Keywords: Policy mirror descent
policy gradient methods
policy iteration
multi-step greedy policy improvement
policy optimization
Primary area: reinforcement_learning

Abstract: Policy Mirror Descent (PMD) stands as a versatile algorithmic framework encompassing several seminal policy gradient algorithms such as natural policy gradient, with connections with state-of-the-art reinforcement learning (RL) algorithms such as TRPO and PPO. PMD can be seen as a soft Policy Iteration algorithm implementing regularized 1-step greedy policy improvement. However, 1-step greedy policies might not be the best choice and recent remarkable empirical successes in RL such as AlphaGo and AlphaZero have demonstrated that greedy approaches with respect to multiple steps outperform their 1-step counterpart. In this work, we propose a new class of PMD algorithms called $h$-PMD which incorporates multi-step greedy policy improvement with lookahead depth $h$ to the PMD update rule. To solve discounted infinite horizon Markov Decision Processes with discount factor $\gamma$, we show that $h$-PMD which generalizes the standard PMD enjoys a faster dimension-free $\gamma^h$-linear convergence rate, contingent on the computation of multi-step greedy policies. We propose an inexact version of $h$-PMD where lookahead action values are estimated. Under a generative model, we establish a sample complexity for $h$-PMD which improves over prior work. Finally, we extend our result to linear function approximation to scale to large state spaces. Under suitable assumptions, our sample complexity only involves dependence on the dimension of the feature map space instead of the state space size.

Policy Mirror Descent with Lookahead
Kimon Protopapas"
Anas Barakat"
Abstract
Policy Mirror Descent (PMD) stands as a versatile algorithmic framework encom- passing several seminal policy gradient algorithms such natural policy gradient, with connections with state-of-the-ard reinforcement learning (RI.) algorithms such TRPO and PPO. PMD can be seen soft Policy Iteration algorithm imple- menting regularized I 1-step greedy policy improvement. However, 1-step greedy policies might not be the best choice and recent remarkable empirical successes RL such as AlphaGo and AlphaZero have demonstrated that greedy approaches with respect to multiple steps outperform their 1-step counterpart. In this work, we propose a new class of PMD algorithms called h-PMD which incorporates multi-step greedy policy improvement with lookahead depth h to the PMD update rule. To solve discounted infinite horizon Markov Decision Processes with dis- count factor 7, we show that h-PMD which generalizes the standard PMD enjoys a faster dimension-free lllner convergence rate, contingent on the computation multi-step greedy policies. We propose an inexact version h-PMD where lookahead action values are estimated. Under generative model, we establish a sample complexity for h-PMD which improves over prior work. Finally, we extend our result linear function approximation scale large state spaces. Under suitable assumptions, our sample complexity only involves dependence on the dimension of the feature map space instead of the state space size.
Introduction
Policy Mirror Descent (PMD) is general class of algorithms for solving reinforcement learning (RL) problems. Motivated by the surge of interest understanding popular Policy Gradient (PG) methods, PMD has been recently investigated in line of works [25, 53, 29, 20]. Notably, PMD encompasses several PG methods as particular cases via its flexible mirror map. A prominent example is the celebrated Natural PG method. PMD has also close connections to state-of-the-a art methods such as TRPO and PPO [50] which have achieved widespread empirical success [41, 42], including most recently in fine-tuning Large Language Models via RL from human feedback [35]. Interestingly, PMD has also been inspired by one of the most fundamental algorithms in RL: Policy Iteration (PI). While PI alternates between policy evaluation and policy improvement, PMD regularizes the latter step to address the instability issue of PI with inexact policy evaluation.
Policy Iteration and its variants have been extensively studied in the literature, see e.g. [5, 39]. In particular, Pl has been studied in conjunction with the lookahead mechanism [12], i.c. using multi- step greedy policy improvement instead of single-step greedy policies. Intuitively, the idea is that the application of the Bellman operator multiple times before computing a greedy policy leads to a more accurate approximation of the optimal value function. Implemented via Monte Carlo Tree Search (MCTS), multi-step greedy policy improvement contributed to the empirical success of some of the
'Department of Computer Science ETH Zürich, Switzerland. Contact: kprotopapas@student ethz. ch, waraakkttnnnssgmaaaaa com. Most of this work was completed when both authors were affiliated with ETH Zürich, K.P as a Master student and A.B. as postdoctoral fellow. A.B. is currently affiliated with Singapore University of Technology and Design as research fellow.
Nott that this is different from n-step return approaches which are rather used policy evaluation [47].
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

most impressive applications of RL including AlphaGo, AlphaZero and MuZero [44, 46, 45, 40]. Besides this practical success, a body of work [12, 13, 49, 52, 51] has investigated the role of lookahead in improving the performance of RI. algorithms, reporting convergence rate speed-up when enhancing Pl with h-step greedy policy improvement with a reasonable computational overhead.
In this work, we propose to cross-fertilize the PMD class of algorithms with multi-step greedy policy improvement to obtain a novel class of PMD algorithms enjoying the benefits of lookahead. Our contributions are as follows:
We propose novel class of algorithms called h-PMD enhancing PMD with multi-step greedy policy updates where h is the depth of the lookahead. This class collapses to standard PMD when h = 1. When the stepsize parameter goes to infinity, we recover the PI algorithm with multiple-step greedy policy improvement previously analyzed in [12]. When solving Markov Decision Process problem with h-PMD, we show that the value suboptimality gap converges to zero geometrically with contraction factor of 7 This rate is faster than the standard convergence rate of PI and the similar rate for PMD which was recently established in [20] for 2 2. This rate improvement requires the computation of a htstep lookahead value function at each iteration which can be performed using planning methods such as tree-search. These results for exact h-PMD are exposed in Sec. 4, when value functions can be evaluated exactly.
We examine the inexact setting where the h-step action value functions are not available. In this setting, we propose a Monte Carlo sample-based procedure to estimate the unknown h- step lookahead action-value function at each state-action pair. We provide a sample complexity for this Monte Carlo procedure, improving over standard PMD thanks to the use of lookahead. Larger lookahead depth translates into better sample complexity and faster suboptimality gap convergence rate. However, this improvement comes at a more intensive computational effort to perform the lookahead steps. Sec. 5 discusses this inexact setting and the aforementioned tradeoff.
We extend our results to the function approximation setting to address the case of large state spaces where tabular methods are not tractable. In particular, we design h-PMD algorithm where the h-step lookahead action-value function is approximated using a linear combination of state-action feature vectors in the policy evaluation step. Under linear function approximation and using a generative sampling model, we provide performance bound for our h-PMD algorithm with linear function approximation. Our resulting sample complexity only depends on the dimension of the feature map space instead of the size of the state space and improves over prior work analyzing PMD with function approximation.
We perform simulations to verify our theoretical findings empirically on the standard DeepSea RL environment from Deep Mind's bsuite [34]. Our experiments illustrate the convergence rate improvement of h-PMD with increasing lookahead depth h in both the exact and inexact settings.
2 Preliminaries
Notation. For any integer n E N [0], the set of integers from 1 to denoted by [n]. For a finite set X, we denote by (AX) the probability simplex over the set X. For any d E N, we endow the Euclidean space IR with the norm || lloe defined for every v E Rd by ||0||oe == maxiejd [0:] where U3 is the i-th coordinate. The relative interior of a set Z is denoted by ri(Z).
Markov Decision Process (MDP). We consider an infinite horizon discounted Markov Decision Process M = (S, A, r, 7, p.p) where S and A are finite sets of states and actions respectively with cardinalities 5 = [8] and A = |A] respectively, P P:S. S x A - A(S) is the Markovian probability transition kernel, r: S x A [0, 1] is the reward function, 7 E (0, 1) is the discount factor and o e A(S) is the initial state distribution. A randomized stationary policy is a mapping specifying the probability [aass) of selecting action a in state s for any E S,a E A. The set of all such policies is denoted by 11. At each time step, the learning agent takes action with probability (a)a s). the environment transitions from the current state s E S to the next state s' S with probability P(s'|s, |s, a) and the agent receives reward r(s, a).
S ((A)
Value functions and optimal policy. For any policy т E II, we define the state value func- tion V= S-> IR for every 8 E S by V*(s) = Ex 1E 7'r(st, 4r)]s0 =s] The state- action value function Q" : x + R can be similarly defined for every 8 E S,a E A by Q" (s) E. IEr= 2rr(s,, ar) 0s s, ag a] where E, is the expectation over the state-

---

action Markov chain (st, induced by the MDP and the policy л generating actions. The goal is to find policy x maximizing V*, A classic result shows that there exists an optimal deterministic policy n' II maximizing V simultaneously for all the states [36]. In this work, we focus on searching for an e-optimal policy, i.e. a policy π satisfying ||V* - V* S E where V* :- =**
Bellman operators and Bellman equations. We will often represent the reward function r by vector in SA and the transition kernel by the operator P E R acting on vectors v E I (which can also be seen functions defined over S) as follows: (Pv) a) Ei'ss P(sl|s,a)u(s) for any
S, a E A. We further define the mean operator M² : RR + E mapping any vector Q E IR to vector in I whose components are given by (M)))(s) = EuEa ((s)s) and the maximum operator M SA I defined by (+) = maxaeAA Q a) for any E =.Q E RSA Using these notations, we introduce for any given policy π E the associated expected Bellman operator T" R + I defined for every V E I by TVV == (r + PVV and the Bellman optimality operator T : [R + ES defined by TV == Mr + YPV) for every V E R Using the notations rx Mr and pa
M P, can also simply write TVV = rd VPV and TV = max+en T for any V E R
The Bellman optimality operator T and the expected Bellman operator T for any given policy x E II are 7-contraction mappings w.r.t. the ||. ao norm and hence admit unique fixed points V and V respectively. In particular, these operators satisfy the following inequalities: - - V* I < g/| - Vr and [TV V* S >/lV Vo for any V E R Moreover, we recall that
for (1,1. 1) I and any Ez0, V R we have TT(V ce) T*V yee and T(V ce) = TV + yce. We recall that the set G(V*) := { E II: T = TV*] of -step
greedy policies w.r.t. the optimal value V coincides with the set of stationary optimal policies.
3 A Refresher on PMD and PI with Lookahead
3.1 PMD and its Connection to PI
Policy Gradient methods consist in performing gradient ascent updates with respect to objec- tive (vT) w.r.t. the policy æ parametrized by its values π (a]s) for 8, a E S x A in the case of a tabular policy parametrization. Interestingly, policy gradient methods have been recently shown be closely connected to a class of Policy Mirror Descent algorithms by using dynamical reweighting of the Bregman divergence with discounted visitation distribution coefficients in classical mirror descent update rule using policy gradients. We refer the reader to section 4 in [53] or section 3.1 in [20] for detailed exposition. The resulting PMD update rule is given by
A+1 argmax (A)(A) {n= m²)
Do( m)))
(PMD)
where we use the shorthand notations x = T& (-1s) and π. = (-1s), where (mc) is a sequence of positive stepsizes, Q R- is vector containing state action values for ny. state 8, and D& is the Bregman divergence induced by a mirror map @ dom Φ + R such that A(A) C dom Φ i.e. for any n, n E 11, 8, (5 -(())
(Vo(T() -(+))
-
n''),
where we suppose throughout this paper that the function o is of Legendre type, i.. strictly convex and essentially smooth in the relative interior of dom @ (see [37], section 26). The mirror map choice gives rise to a large class of algorithms. Two special cases are noteworthy: (a) When ş is the squared 2-norm, the Bregman divergence is the squared Euclidean distance and the resulting algorithm is a projected Q-ascent and (b) when Φ is the negative entropy, the corresponding Bregman divergence is the Kullback-Leibler (KL) divergence and (PMD) becomes the popular Natural Policy Gradient algorithm (see e.g. [53], section 4 for details).
Now, using our operator notations, one can observe that the (PMD) update rule above is equivalent to the following update rule (see Lemma A. for a proof),
T E argmax (Th 1T.T" DT(TT, [x))
(1)
where DTT TE) E RS is a vector whose components are given by Da m²)) for E S. Note that the maximization can be carried out independently for each state component.
3

---

Connection to Policy Iteration. As previously noticed in the literature [53, 20], PMD can be interpreted as a 'soft' PI. Indeed, taking infinite stepsizes T]s in PMD (or a null Bregman divergence)
immediately leads to the following update rule:
Th+1 E argmax {T* [**V")).
(PI)
which corresponds to synchronous Policy Iteration (PI). The method alternates between a policy evaluation step estimate the value function VT* of the current policy Ta and policy improvement step implemented as a one-step greedy policy with respect to the current value function estimate.
3.2 Policy Iteration with Lookahead
As discussed in [12], Policy Iteration can be generalized by performing h 2 1 greedy policy improvement steps at each iteration instead of a single step. The resulting h-PI update rule is:
Tb+1 E argmax (T*Th-LVTA)
(h-PI)
where E N \ {0}. The h-greedy policy nh+1 w.r.t T selects the first optimal action of a non-stationary hi-oorionn optimal control problem. It can also be
the 1-step greedy policy w.r.t. Th- In the rest of this paper, we will denote by Gr. (V) the set of h-step greedy policies w.r.t any value function V IR$, i.. (V) == argmax=E11 T*Thー1v = {x E 11: TTThT<h T'V}. Notice that 9 (V) = G(V). Overall, the h-PI method alternats between finding a h--geedy policy and estimating the value of this policy. Interestingly, similarly to PI, h-greedy policy guarantees monotonic improvement, i.e. V" V component for any π E II, n' (V*). Moreover, since T is a 7 contracctio,, it can be shown that the sequence (I]V* V** is contracting with coefficient 7" See section in [12] for further details about h-PI
Remark 3.1. While the iteration complexity always improves with larger depth h (see Theorem in [12]), each iteration becomes more computationally demanding. As mentioned in [14], when the model known, the h--geedy policy can be computed with Dynamic Programming (DP) in linear time in the depth h.
Another possibility is to implement& a tree-search of depth starting from the root state to compute the h-greedy policy in deterministic MDPs. We refer to [14] for further details. Sampling campling-bbsed tree search methods such as Monte Carlo Tree Search (MCTS) (see [9]) can be used to circumvent the exponential complexity in the depth h of tree search methods.
4 Policy Mirror Descent with Lookahead
In this section we propose our novel Policy Mirror Descent (PMD) algorithm which incorporates h-step lookahead for policy improvement: h-PMD.
4.1 PMP: Using ht-Step Greedy Updates
Similarly to the generalization of PI h-PI discussed in the previous section, we obtain our algorithm h-PMD by incorporating lookahead to PMD as follows:
Tk+1 argmax7en { mT Th vy DT(TT, m²)
(h-PMD
Notice that we recover (1), i.e. (PMD), by setting h = 1. We now provide an alternative way to write the 4-PMD update rule which is more convenient for its implementation. We introduce few additional notations for this purpose. For any policy π II, let V = Th-iV= for any integer h 2 1. Consider the corresponding action value function defined for every 8,
by:
(s, == r(s.a) a) + >PV, as)
(2)
Using these notations, it can be easily shown that the h-PMD rule above is equivalent to:
+++1 argmax+en ( (s, :), π.) Do(T,, -
(h-PMD')
Before moving to the analysis of this scheme, we provide two concrete examples for the implementa- tion of h-PMD' corresponding to the choice of two standard mirror maps.

---

(1) Projected -scennt When the mirror map ø is the squared 2-norm, the corresponding Bregman divergence is the squared Euclidean distance and h-PMD' becomes
+++1 (A)) ( + mh Q% :))
for every E S and (roja(A) is the projection operator on the simplex A(A).
(2) Multiplicative Qn -ascennt When the mirror map ø the negative entropy, the Bregman diver- gence D& is the Kullback-Leibler divergence and for every (s, a) E x A.
exp(n% Q (s, a))
Th+ 1 8) = TH (als)
(x) = Σ BEA
(8, (8,
(4)
7x(+))
Connection to AlphaZero. Before switching gears to the analysis, we point out an interesting connection between h--MD and the successful class of AlphaZero algorithms [46, 45, 40] which based on heuristies.
It has been shown in [16] that AlphaZero can be drawing a connection to the standard PMD algorithm (with h = 1). We argue that AlphaZero is more naturally connected our h-PMD algorithm. Indeed, the Q values in [16, Eq. (7) p. 3] correspond more closely to the lookahead action value function Q% approximated via tree search instead of the standard Q function with h = 1. This connection clearly delineates the dependence on the lookahead depth (or tree search depth) / which was not clear in [16]. We have implemented a version of our h-PMD algorithm with Deep Mind's MCTS implementation (see section D.6 and the code provided for details). Conducting further experiments to compare our algorithm to AlphaZero on similar large scale settings would be interesting. We are not aware of any theoretical convergence guarantee for AlphaZero which relies on many heuristics. In contrast, our ft-MDD algorithm enjoys theoretical guarantees that we establish in the next sections.
regularized policy optimization algorithm,
4.2 Convergence Analysis for Exact h-PMD
Using the contraction properties of the Bellman operators, it can be shown that the suboptimality gap | V* for PI iterates converges to zero at linear rate with contraction factor % regardless of the underlying MDP. This instance-independer convergence rate was generalized to PMD in [20]. In this section, we establish linear convergence rate for the subobtimality value function gap of the exact h-PMD algorithm with a contraction factor of of where h is the lookahead depth. We assume for that the value function 4** and a greedy policy T in (h-PMD) computed exactly. These assumptions will be relaxed in the next section dealing with inexact h-PMD.
be
Theorem 4.1 (Exact h- PMD). Let (ck) be a sequence of positive reals and let the stepsize ni in (h-PMD) satisfy 2 dx [lmin (V*L) Do(T, To)l where we recall that Gr (V**) is the set of greedy policies with respect to Th-lvax and that the minimum is computed component-wir Initialized at xo E ri(lI), the iterates (mT) of (h-PMD) with h E N \ {0} satisfy for every l e N.
&.
|
V 1100 S nhk
[
Vo 1100 +
1
Ct-1
1
hit
few remarks are in order regarding this result:
Compared to [20], our new algorithm achieves faster faster>" -rate where h is the depth of the lookahead. It should be noted that the approach [20] is claimed to be optimal over all methods that are guaranteed to increase the probability of the greedy action at each timestep. Adding lookahead to the policy improvement step circumvents this restriction.
Unlike prior work [53, 25] featuring distribution mismatch coefficients which can scale with the size of the state space, our convergence rate does not depend on any other instance-dependent quantities. This is thanks to the analysis which circumvents the use of the performance difference
lemma similarly to [20].
Choosing & = 2 cu for a positive constant co for every integer t, the bound becomes (after
bounding the geometric sum): ||V* V ||x Ti (IIV* |= I| to + (1-73² eo ). As Co - 0 we
recover the linear convergence result of h-PI established in [12].
5

---

This faster rate comes at the cost of more complex value function computation at each iteration. However, our experiments suggest that the benefits of the faster convergence rate greatly outweigh the extra cost of computing the lookahead, in terms of both overall running time until convergence and sample complexity (in the inexact case). See section and Appendix D) for evidence.
The cost of computing the adaptive stepsizes is typically simply that of computing Bregman divergence between two policies. See Appendix A.3, D.4 for a more detailed discussion.
We defer the proof Theorem 4.1 to Appendix A. Our proof highlights the relationship between h-PMD and h-Pl through the explicit use of Bellman operators. Notice that even in the particular case of h = 1, our proof more compact compared to the one [20] (see sec. and Lemma A.1 to A.3 therein for comparison) using convenient notations.
5 Inexact and Stochastic h-Policy Mirror Descent
In this section, we discuss the case where the lookahead action value 2h defined in (2) unknown. We propose procedure to estimate it using Monte Carlo sampling and briefly discuss an alternative using a tree search method. The resulting inexact h-PMD update rule for every s $
++1 argmax,,,a. { { (Q%% t (s, Ta) DT mt)}
(5)
where T is the estimated version of the lookahead action value 17,² induced by policy Ty. We conclude this section by providing a convergence analysis for inexact h-PMD and discussing its sample complexity using the proposed Monte Carlo estimator.
5.1 Monte Carlo h-Greedy Policy Evaluation
Estimating the lookahead action value function Q% for a given policy æ involves solving a h-horizon planning problem using samples from the MDP. Our estimation procedure combines standard planning method with Monte Carlo estimation under a generative model of the MDP. We give an algorithmic description of the procedure below, and defer the reader to Appendix B. for precise definition of the procedure. Applying the recursive algorithm below with == returns an estimate for the action value function Q7, (s. 0) at given state-action pair (s, a) SxX. A.
Algorithm 1 Lookahead Q-function Estimation via Monte Carlo Planning
Procedure Qkk, s, a, if k = then return r(,,a) ΣM (x() (where sf P(-ls, a) for [M]
else
return as) + M1 EM m Q(k 1, a', T)) (where of P(-|s, for e [M]
end if
Note that the base case of the recursion estimates the value function using Monte Carlo rollouts, see Appendix B.1.
Remark 5.1. Notice that actions exhaustively selected in procedure like in planning method. Using bandit ideas to guide Monte Carlo planning (see e.g. [23]) would be interesting to investigate for more efficiency. We leave the investigation of such selective action sampling and exploration for future work. In practice, lookahead policies are often computed using tree search techniques [12]. Remark 5.2. When h = 1, the procedure collapses to simple Monte Carlo estimate of the Q-value function Q each iteration of the h-PMD algorithm.
5.2 Analysis of Inexact h-PMD
The next theorem is a generalization of Theorem 4.1 to the inexact setting in which the lookahead function T can be estimated with some errors each iteration l of h-PMD.
Theorem 5.3 (Inexact h-PMD). Suppose there exists E R s.f. 11 - 2 alac S where the max- imum norm is over both the state and action spaces. Let Gr. argmax M= and let (cx) be sequence of positive reals and let the stepsize Tp in (h-PMD) satisfy mp 2 1 -lminze DØ(TT, Tk) lloc

---

where we recall that the minimum is computed component wise.... Initialized at To E ri(II), the iter- ates (TT) of inexact (h-PMD) with N {0} satisfy for every le N,
[ ( v 100 +
k
26
||V* - 1/** S 2/hh
+
The
()
The proof of this result is similar to the proof of Theeoem 4. 1 and consists in propagating the error b in the analysis. We defer it to Appendix B.
As can be directly seen from this formulation, the 7 convergence rate from the exact setting generalizes to the inexact setting. Therefore, higher lookahead depths lead to faster convergence rates. Another improvement with relation to [20] is that the additive error term has a milder dependence 2h on the effective horizon 1 - 7. the term (1-ク)(1ー" is smaller for all values of h > 2 than 46 (1-))²
Larger lookahead depths yield a smaller asymptotic error in terms of the suboptimality gap.
We are now ready to establish the sample complexity of inexact h-PMD under a generative model using Theorem 5.3 together with concentration results for our Monte Carlo lookahead action value estimator.
Theorem 5.4 (Sample complexity of h-PMD), Assume that inexact h-PMD run for a number of iterations K MI-7] 108(<)1=>(1--7>> using the choice of stepsize defined by the sequence (cx) = (1 ()) Additionally, suppose we are given target suboptimalliy value O. and probability threshold >> O. Finally, assume the lookahead value function QT is approximated at each iteration with the Monte Carlo estimation procedure described in section 5.1, with the following
parameter values: Mo = Õ (111-11111-00 x and for all j E [h] M, = - (1133)=2) ). Then, with probability at least 1 5, the suboptimality at all iterations satisfy the following bound:
22th
I|V V** 1100 S Sia (II*-V-' 1v0- +
1 1 hk
+
(6)
(1-7)(1-1)) -1)1)))))
Using this procedure, h-PMD uses at most M + hKMSA samples in total. The overall sample complexity of the inexact h-PMD is then given by Ö (1=00-100000"" + ((--))>) where the notation Ô hides at most polylogarithmic factors.
Compared to Theorem 5.1 in [20]. the dependence the effective horizon improves by factor of the order of 1/(1 -Y) for h > A (1-7) thanks to our Monte Carlo lookahead estimator. Their
sample complexity is of order Ô ((1 ), whereas for > A(177) ours becomes Ó ((>)~~7)) )
Our sample complexity does not depend on quantities such as the distribution mismatch coefficient used in prior work [53, 25], which may scale with the state space size.
6 Extension to Function Approximation
In MDPs with prohibitively large state action spaces, we represent each state-action pair (8, a) E S x A by a feature vector (s,, a) Id where typically d < SA and where & S x A + Rd is feature map, also represented as a matrix E SAxd Assuming that this feature map holds enough "information" about each state action pair (more rigorous assumptions will be provided later), is possible to approximate any value function using a matrix vector product V0, where 0 E Rd, In this section, we propose an inexact /-PMD algorithm using action value function approximation.
6.1 Inexact h-PMD with Function Approximation
Using the notations above, approximating Q TT by V0k,, the inexact 4-PMD update rule becomes:
k+1 argmax,,eart {TH (4V0)),, - (o(T,,T())
We note that the policy update above can implicit to avoid computing policy for every state. possible to implement this algorithm using Monte Carlo planning method in similar fashion
7

---

to [27]: use the procedure in section 1.1 to estimate 2% (s, a) for all state action pairs (s, in some set C C S A, and use these estimates as targets for a least squares regression to approximate Q% by v0, at time step k. See Appendix C for further details. We conclude this section with convergence analysis of h-PMD with linear function approximation.
6.2 Convergence Analysis of h-PMD with Linear Function Approximation
Our analysis follows the approach of [27]. We make the following standard assumptions. Assumption 6.1. The feature matrix V E R where d S SA is full rank.
Assumption 6.2 (Approximate Universal value function realizability). There exists 6PA >> 0 s.t. for any π E II, infagr 1[Q [ S EFΛ.
We defer discussion about Assumption 6.2 to Appendix C.2.
Theorem 6.3 (Convergence of h-PMD with linear function approximation). Let (6%) be the sequence of iterates produced by h-PMD with linear fanction approximation. run K iterations, starting with policy To E ri(TI), using stepsizes defined by (c+). Assume that targets Q7, were computed using the procedure described in sec. 5.1 such that with probability at least 6, vk S K,
C X A
the largets satisfy Qhh (z) 0% (z) S..
Then, there exists choice of C for which the policy iterates satisfy each iteration:
- -V* 100 S Sha hk
- V50
C-1 +
2v + 2 21
(1-7)(1-7
The proof of Theorem 6.3 can be found in Appendix C.3. Notice that our performance bound does not depend on the state space size like in sec. 5 and depends on the dimension d of the feature space instead. We should notice though that the choice of the set C is crucial for this result and given by the theorem [22] which guarantees that |C| = (dd²)
discussed in [27]. Moreover, our method for function approximation yields sample complexity that is instance independent. Existing results for PMD with function approximation [3, 54] depend on distribution mismatch coefficients which can scale with the size of the state space.
In terms of computational complexity, at each iteration, /-PMD uses O((MA)*) elementary opera- tions where M is the size of the minibatch of trajectories used, the size of the action space and is the lookahead depth. This computational complexity which scales exponentially in h is inherent to tree search methods. Despite this seemingly prohibitive computational scaling, tree search has been instrumental in practice for achieving state of the art results in some environments [40, 19] and modern implementations (notably using GPU-based search on vectorized environments) make tree search much more efficient in practice.
7 Simulations
We conduct simulations to investigate the effect of the lookahead depth on the convergence rate and illustrate our theoretical findings. We run the h-PMD algorithm for different values of h in both exact and inexact settings on the DeepSea environment from DeepMind's bsuite [34] using grid size of 64 by 64, and a discount factor 7 0.99. Additional experiments are provided in Appendix D. Our codebase where all our experiments can be replicated is available here: https: //gitlab com/kimon. prrotopapppmmd-looooo
Exact h-PMD. We run the exact h-PMD algorithm for 100 iterations for increasing values of using the KL divergence. Similar results were observed for the Euclidean divergence. We tested two different stepsize schedules: (a) in dotted lines in Fig. 1 (left), equal to its lower bound in sec. 4, with the choice e := 2h((++1) (note the dependence on h); and (b) in solid lines, 7h identical stepsize schedule across all values of with C := 2(+++) to isolate the effect of the lookahead. We clearly observe under both stepsize schedules that h-PMD converges in fewer iterations when lookahead value functions are used instead of regular Q functions.
Thiis can be achieved by choosing the parameters in Theorem 5.4 (see Appendix C for details).

---

0.5
0.20
0.230
0.0
||0/ -|/1|/0
0.3
0.10
0.10
0.2
0.05
0.05
6.0
0.00
0.00
10
00
25
50
75
Iteration:
Iseration
Runtime (+)
5-5
A-10
15
h=
Figure I: Suboptimality value function gap for h-PMD in the exact (left) and inexact (middle/right) settings, plotted against iterations in the exact case (left) and against both iterations (middle) and runtime (right) in the inexact case. 16 runs performed for each h, mean in solid line and standard deviation as shaded area. In dotted lines (left), the step size is equal to its lower bound in sec. 4, with the choice C := 7 2 (note the dependence on h) and in solid lines, the step size Mi is set using an identical stepsize schedule across all values of with C == 2 1) to isolate the effect of the lookahead. Notice that higher values of h still perform better even in terms of runtime.
Inexact h-PMD. In this setting, we estimated the value function Qn using the vanilla Monte Carlo planning procedure detailed in section 5 in stochastic variant of the DeepSea environment, and all the parameters except for h were kept identical across runs. As predicted by our results, h-PMD converges in fewer iterations when is increased (see Fig. 1 (middle)). We also observed in simulations that h-PMD uses less samples overall (see Appendix D for the total number of samples used each iteration), and usually converges after less overall computation time (see Fig. (right)). We also refer the reader to Appendix D where we have performed additional experiments with larger lookahead depth h 100. In this case, the algorithm converges in single iteration. This is theoretically expected as computing the lookahead values with very large h boils down to computing the optimal values like in value iteration with large number of iterations. We also performed additional experiments in continuous control tasks to illustrate the general applicability of our algorithm (see Fig. in Appendix D).
Remark 7.1. (Choice of the lookahead depth h.) The lookahead depth is hyperparameter of the algorithm and can be tuned similarly to other hyperparameters such as the step size of the algorithm. Of course, the value would depend the environment and the structure of the reward hand. Sparse and delayed reward settings will likely benefit from lookahead with larger depth values. We have performed several simulations with different values of h for each environment setting and the performance can potentially improve drastically with a better lookahead depth value (see also appendix D for further simulations). In addition, we observe that larger lookahead depth is not always better: see Fig. in the appendix for an example where large lookahead depth becomes slower and does not perform better. Note that this more challenging practical setting the best performance is not obtained for higher values of h: intermediate values of h perform better. This illustrates the tradeoff choosing the depth h between an improved convergence rate and the computational cost induced by a larger h. We believe further investigation regarding the selection of the depth parameter might be useful further improve the practical performance of the algorithm.
8 Related Work
Policy Mirror Descent and Policy Gradient Methods. Motivated by their empirical success
[41, 42], the analysis of PG methods has recently attracted lot of attention [1, 6, 21, 7, 53, 25, 20]. Among these works, line of research focused on the analysis of PMD [53, 25, 28, 29, 20, 3] as flexible algorithmic framework, and its particular instances such as the celebrated natural policy gradient [21, 54]. In particular, for solving unregularized MDPs (which is our main focus), Xiao [53] established linear convergence PMD the tabular setting with a rate depending on the instance dependent distribution mismatch coefficients, and extended their results to the inexact setting using generative model. Similar results were established for the particular case the natural policy gradient algorithm [6, 21]. More recently, Johnson, BekeBBurke, and Rebeschini [20] showed a dimension-fre free

---

rate for PMD with exact policy evaluation using adaptive stepsizes, closing the gap with PI. Notably, they further show that this rate is optimal and their analysis inspired from PI circumvents the use of the performance difference lemma which was prevalent in prior work. We improve over these results using lookahead and we extend our analysis beyond the tabular setting by using linear function approximation. To the best of our knowledge, the use of multi-step greedy policy improvement in PMD and its analysis are novel in the literature.
Policy Iteration with Multiple-Step Policy Improvement. Multi-step greedy policies have been successfully used in applications such as the game of Go and have been studied in a body of works [12, 13, 52, 15, 49]. In particular, multi-step greedy policy improvement has been studied in conjunction with PI in [12. 52]. Efroni al. [12] introduced h-PI which incorporates h-lookahead to Pl and generalized existing analyses on PI with 1-step greedy policy improvement to h-step greedy policies. However, their work requires access to an h-greedy policy oracle, and the h-P1 algorithm is unstable in the stochastic setting even for h = 1 because of potentially large policy updates. We address all these issues the present work with our h-PMD algorithm. Winnicki and Srikant [52] showed that a first-visit version of PI scheme using single sample path for policy evaluation converges to the optimal policy provided that the policy improvement step uses lookahead instead of a 1-step greedy policy. Unlike our present work, the latter work assumes access to a lookahead greedy policy oracle. More recently, Alegre et al. [2] proposed to use lookahead for policy improvement in a transfer learning setting. Extending Generalized Policy Improvement (GPI) [4] which identifies new policy that simultancously improves over all previously learned policies each solving a specific task, they introduce h-GPI which is multi-step extension of GPI. We rather consider lookahead version of PMD including policy gradient methods instead of PI. We focus on solving a single task and provide policy optimization guarantees in terms of iteration and sample complexities.
Lookahead-Basee Policy Improvement with Tree Search. Lookahead policy improvement is usually implemented via tree search methods [9, 43, 40, 24, 18, 14]. Recently, Dalal et al. [11] pro- posed a method combining policy gradient and tree search to reduce the variance of stochastic policy gradients. The method relies on softmax policy parametrization incorporating tree expansion. Our general h- h-D framework which incorporates a different lookahead policy improvement step also brings together PG and tree search methods. Morimura et al. [31] designed method with mixture policy of PG and MCTS for non-Markov Decision Processes. Grill et al. [17] showed that AlphaZero well as several other MCTS algorithms compute approximate solutions to a family of regularized policy optimization problems which bear similarities with our h-PMD algorithm update rule for h = 1 (see sec. 3.2 therein).
9 Conclusion
In this work, we introduced a novel class of PMD algorithms with lookahead inspired by the success of lookahead policies practice. We have shown an improved "atooveddllllnne --llinear convergence rate depending on the lookahead depth in the exact setting. We proposed a stochastic version of our algorithm enjoying an improved sample complexity. We further extended our results to scale to large state spaces via linear function approximation with performance bound independent of the state space size. Our paper offers several interesting directions for future research. A possible avenue for future work is to investigate the use of more general function approximators such as neural networks to approximate the lookahead value functions and scale to large satt-accioon spaces. Recent work for PMD along these lines [3] might be good starting point. Enhancing algorithm with exploration mechanisms (see e.g. the recent work [33) is an important future direction. Our PMD update rule might offer some advantage in this regard was recently observed in the literature [28]. Constructing more efficient fully online estimators for the lookahead action values using MCTS and designing adaptive lookahead strategies to select the tree search horizon [38] are promising avenues for future work. Our algorithm brings together two popular and successful families of RL algorithms: PG methods and tree search methods. Looking forward, we hope our work further stimulates research efforts to investigate practical and efficient methods enjoying the benefits of both classes of methods.
10

---

Acknowledgments and Disclosure of Funding
We would like to thank the anonymous area chair and reviewers for their useful comments which helped us to improve our paper. Most of this work was completed when A.B. was affiliated with ETH Zürich as a postdoctoral fellow. This work was partially supported by an ETH Foundations of Data Science (ETH-FDS) postdoctoral fellowship.
References
[1] A. Agarwal. M. Kakade, J. D. Lee, and Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. The Journal of Machine Learning Research, 22(1):4431-4506 2021.
[2] I. N. Alegre, A. Bazzan, A. Nowe, and B. C. da Silva. Multi-step generalized policy im- provement by leveraging approximate models. Advances Neural Information Processing Systems, volume 36, pages 38181-38205, 2023. 10
[3] C. Alfano, R. Yuan, and P. Rebeschini. A novel framework for policy mirror descent with general parameterization and linear convergence. In Thirty-seventh Conference Neural Information Processing Systems, 2023. 8, 9, 10
[4] A. Barreto, S. Hou, D. Borsa, D. Silver, and D. Precup. Fast reinforcement learning with generalized policy updates. Proceedings of the National Academy of Sciences, 117(48):30079- 30087, 2020. 10
[5] D. Bertsekas and J. N. Tsitsiklis. Neuro-dynamic programming. Athena Scientific, 1996. 1
[6] Bhandari and D. Russo. On the linear convergence of policy gradient methods for finite mdps. In International Conference on Artificial Intelligence and Statistics, pages 2386-2394, PMLR, 2021.
[7] J. Bhandari and D. Russo. Global optimality guarantees for policy gradient methods. Operations Research, 2024. 9
[8] G. Brockman, V. Cheung, L. Pettersson, J. Schneider, J. Schulman, J. Tang, and W. Zaremba. Openai gym, 2016. 31
[9] C. B. Browne, E. Powley, D. Whitehouse, S. M. Lucas, P. I. Cowling, P. Rohlfshagen, S. Tavener, D. Perez, Samothrakis, and S. Colton. survey of monte carlo tree search methods. IEEE Transactions Computational Intelligence and Al in games, 4(1):1-43, 2012. 4, 10
[10] G. Chen and M. Teboulle. Convergence analysis of a proximal-like minimization algorithm using bregman functions. SIAM Journal Optimization, 3(3):538- 543, 1993. 17
[11] G. Dalal, A. Hallak, S. Mannor, and G. Chechik. Softtreemax: Policy gradient with tree search, 2022. 10
[12] Y. Efroni, G. Dalal, B. Scherrer, and S. Mannor. Beyond the one-step greedy approach in reinforcement learning. In Proceedings the 35th International Conference on Machine Learming, volume 80 of Proceedings of Machine Learning Research, pages 1387-1396. PMLR, 10-15 Jul 2018. 1, 2, 6, 10
[13] Y. Efroni, G. Dalal, B. Scherrer, and S. Mannor. Multiple-step greedy policies in approximate and online reinforcement learning. In Advances in Neural Information Processing Systems, volume 31, 2018. 2, 10
[14] Y. Efroni, G. Dalal, Scherrer, and S. Mannor. How to combine tree-search methods in reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 3494-3501 2019. 4, 10
[15] Y. Efroni, M. Ghavamzadch, and S. Mannor. Online planning with lookahead policies, 2020. 10
11

---

[16] J.-B. Grill, F. Altché, Y. Tang, T. Hubert, M. Valko, I. Antonoglou, and R. Munos. Monte- carlo tree search as regularized policy optimization. In International Conference on Machine Learning, pages 3769-3778. PMLR, 2020. 5
[17] J.-B. Grill, F. Altché, Y. Tang. T. Hubert, M. Valko, I. Antonoglou, and R. Munos. Monte-Carle tree search as regularized policy optimization. In H. D. III and Singh, editors, Proceedings of the 37th International Conference on Machine Leurning, volume 119 of Proceedings of Machine Learning Research, pages 3769-3778. PMLR, 13-18 Jul 2020.
[18] A. Hallak, G. Dalal, Dalton, I. Frosio, S. Mannor, and G. Chechik. Improve agents without retraining: Parallel tree search with off-policy correction, 2023. 10
[19] M. Hessel, I. Danihelka, F. Viola, A. Guez, S. Schmitt, L. Sifre, T. Weber, D. Silver, and H. van Hasselt. Muesli: Combining improvements policy optimization, 2022. 8
[20] E. Johnson, C. Pike-Burke, and P. Rebeschini. Optimal convergence rate for exact policy mirror descent in discounted markov decision processes. In Thirly-seventh Conference on Neural Information Processing Systems, 2023. 1, 2, 3, 4, 5, 6, 7, 9, 16, 17, 18, 19, 29
[21] S. Khodadadian, P. R. Jhunjhunwala, S. M. Varma, and S. Maguluri. On linear and super- linear convergence of natural policy gradient algorithm. Systems & Control Letters, 164:105214 2022.
[22] Kiefer and J. Wolfowitz. The equivalence of two extremum problems. Canadian Journal of Mathematics, 12:363-366, 1960. 8, 27
[23] I.. Koesis and C. Szepesvári. Bandit based monte-carlo planning. In Machine Learning: ECML. 2006, pages 282-293, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg.
[24] L. Kocsis and C. Szepesvári. Bandit based monte-carlo planning. J. Fürnkranz, T. Schef- fer, and M. Spiliopoulou, editors, Machine Leurning: ECML 2006, pages 282-293,, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg. 10
[25] G. Lan. Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes. Mathematical programming, 198())1059-1110 2023. 1, 5, 7, 9, 18
[26] R. T. Lange. gymnax: A JAX-based reinforcement learning environment library, 2022. 30
[27] Lattimore and C. Szepesvari. Learning with good feature representations bandits and in with generative model. In International Conference Machine Learning, 2019. 8, 27, 28
[28] Y. Li and G. Lan. Policy mirror descent inherently explores action space. arXiv preprint arXiv:2303. 04386, 2023. 9, 10
[29] Y. Li, G. Lan, and Zhao. Homotopic policy mirror descent: policy convergence, algorithmic regularization, and improved sample complexity. Mathematical Programming, pages 1-57,
2023. 1,9, 9, 18
[30] Mei, B. Dai, A. Agarwal, M. Ghavamzadeh, C. Szepesvári, and Schuurmans. Ordering- based conditions for global convergence of policy gradient methods. Advances in Neural Information Processing Systems, 36, 2024. 27
[31] T. Morimura, K. Ota, K. Abe, and P. Zhang. Policy gradient algorithms with monte-carlo tree search for non-markov decision processes, 2022. 10
[32] R. Munos. Eroo bounds for approximate policy iteration. In Internation Conference on Machine Learning, volume 3, pages 560-567. Citeseer, 2003.
[33] B. O'Donoghue. Efficient exploration via epistemic-risk-seeking policy optimization, 2023. 10
[34] I. Osband, Y. Doron, M. Hessel, J. Aslanides, E. Sezener, A. Saraiva, McKinney, T. Lattimore, C. Szepesvári, S. Singh, B. Van Roy, R. Sutton, D. Silver, and H. van Hasselt. Behaviour suite for reinforcement learning. In International Conference on Learning Representations, 2020.
8, 28, 30, 31
12

---

[35] L. Ouyang. J. Wu, X. Jiang, D. Almeida, C. Wainwright, P. Mishkin. C. Zhang, S. Agarwal, K. Slama, A. Ray, al. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 35:27730-27744 2022. I
[36] M. L. Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014. 3
[37] R. T. Rockafellar. Convex Analysis. Princeton University Press, Princeton, 1970.
[38] A. Rosenberg, A. Hallak, S. Mannor, G. Chechik, and G. Dalal. Planning and learning with adaptive lookahead. Proceedings of the AAAI Conference on Artificial Intelligence, 37(8))9606-
9613, Jun. 2023. 10
[39] B. Scherrer. Improved and generalized upper bounds on the complexity of policy iteration. Advances Neural Information Processing Systems, 26, 2013.
[40] J. Schrittwieser, I. Antonoglou, T. Hubert, K. Simonyan, L.. Sifre, S. Schmitt, A. Guez, E. Lock- hart, D. Hassabis, T. Graepel, T. P. Lillicrap, and D. Silver. Mastering atari, go, chess and shogi by planning with a learned model. Nature, 588:604 609, 2019. 2, 5, 8, 10.
[41] J. Schulman, S. Levine, P. Abbeel, M. Jordan, and P. Moritz. Trust region policy optimization. In International conference on machine learning, pages 1889-1897. PMLR, 2015. 1,
[42] Schulman, Wolski, Dhariwal, A. Radford, and O. Klimov. Proximal policy optimization algorithms, 2017. 1,9
[43] D. Shah, Q. Xie, and Z. Xu. Non-asymptotic analysis of monte carlo tree search, 2020. 10
[44] D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. Van Den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot, al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484-489 2016. 2
[45] D. Silver, T. Hubert, J. Schrittwicser, I. Antonoglou, M. Lai, A. Guez, M. Lanctot, L. Sifre, D. Kumaran, T. Graepel. et al. A general reinforeement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419):1 140-1144, 2018. 2,5
[46] D. Silver, J. Schrittwieeer, K. Simonyan, I. Antonoglou, Huang, A. Guez, T. Hubert, Baker, M. Lai, A. Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7676)3354-333 359, 2017. 5,5
[47] R. S. Sutton and A. G. Barto. Reinforcement learning: An introduction. MIT press, 2018. 1
[48] C. Szepesvári. CMPUT 653: Theoretical Foundations of Reinforcement Learning. Lecture 6. Online planning Part II., 2023. 21, 23, 26
[49] M. Tomar, Y. Efroni, and M. Ghavamzadeh. Multi-step greedy reinforcement learning algo- rithms. In International Conference on Machine Learning, pages 9504 9513. PMLR, 2020. 2, 10
[50] M. Tomar, L. Shani, Y. Efroni, and M. Ghavamzadeh. Mirror descent policy optimization. In International Conference Learning Representations, 2022. I
[51] A. Winnicki, J. Lubars, M. Livesay, and R. Srikant. The role of lookahead and approximate policy evaluation in reinforcement learning with linear value function approximation. arXiv preprint arXiv:2109.13419 2021. 2
[52] A. Winnicki and R. Srikant. On the convergence of policy iteration reinforcement learning with monte carlo policy evaluation. In International Conference on Artificial Intelligence and Statistics, pages 9852-9878. PMLR, 2023. 2, 10
[53] L. Xiao. On the convergence rates of policy gradient methods. The Journal of Machine Learning Research, 23(1):12877-12922 2022. 1, 3, 4, 5, 7, 9, 15, 17, 18
[54] R. Yuan, S. S. Du, R. M. Gower, A. Lazaric, and L. Xiao. Linear convergence of natural policy gradient methods with log-linear policies. In The Eleventh International Conference on Learning Representations, 2023. 8,
13

---

Contents
Introduction
2 Preliminaries
3 A Refresher on PMD and with Lookahead
3.1 PMD and its Connection to Pl
3.2
Policy Iteration with Lookahead
Policy Mirror Descent with Lookahead
4.1
h-PMD: Using h-Step Greedy Updates
4.2
Convergence Analysis for Exact h- h-PMD
5
Inexact and Stochastic lt-Policy Mirror Descent
5.1
Monte Carlo h-Greedy Policy Evaluation
5.2 Analysis of Inexact h-PMD
6
Extension to Function Approximation
6.1
Inexact h-PMD with Function Approximation
6.2
Convergence Analysis of h-PMD with Linear Function Approximation
7
Simulations
Related Work
9
Conclusion
10
Additional Details and Proofs for Section Exact h-PMD
15
A.I
Auxiliary Lemma for the Proof of Theorem 4.1: Exact h-PMD
A.2 Proof of Theorem 4.1
16
A.3 Additional Comments About the Stepsizes Theorem 4.1
18
B Additional Details and Proofs for Section 5: Inexact h-PMD
19
B.1 Details and Precise Notation for Lookahead Computation
19
B.2 Proof of Theorem 5.3: Inexact h-PMD
19
B.3 Proof of Theorem 5,4
21
Additional Details and Proofs for Section h-PMD with Function Approximation
24
C.1 Inexact h-PMD with Linear Function Approximation
25
C.2 Discussion of Assumption 6.2
26
C.3 Convergence Analysis of Inexact h-PMD using Function Approximation
27
D Further Simulations
28
D.I Simulations for h-PMD with Euclidean Regularization
28
14

---

D.2 Sample Complexity Comparison for Different Lookahead Depths
28
D.3 Total Running Time Comparison for Different Lookahead Depths
28
D.4 About the Stepsizes in Simulations
29
D.5 Larger lookahead depths
29
D.6 Experiments with MCTS-based Lookahead Estimation
30
D.7 Continuous Control Experiments
D.8 Additional experiments
A Additional Details and Proofs for Section 4: Exact h-PMD
Lemma A.1. For any policies ı, x II and every state E S, we have (Q T.) TVV>>(s) As a consequence, the update rules (PMD) and (1) in the main part are equivalent.
Proof. Let n 11. For every E S, we have
10= F3) Een (s,a)
(by definition of the scalar product)
= Σ
r(s,a) +
Σ
P(s (()))s,a)V=((5)) =(als)
(Q" as a function of V
aEd
e'ES
= (s) + Σ
P(d'ss, v='(') (s')
s'ES
NEEA
(by rearranging and using the definition of r*)
(s) + + PT
(using the definition of Px)
=T'V" (s).
(8)
The second part of the statement holds by setting n' Tk
A.1 Auxiliary Lemma for the Proof of Theorem 4.1: Exact h-PMD
Lemma A.2 (Triple Point Descent Lemma for h-PMD), Let E N {0) Initialized at mo E ri(I)), the iterates of h-step greedy PMD remain in ri(ll) and satisfy the following inequality for any E N and any policy π E 11.
1/ T 1 < - + DØ(T, mT) Do(a, Tk41) Do(TT+I, Tx)
Proof. Recall the definition of the h-step greedy action value function denoted by 07 : S A + R
(2). Then, recall that for each state s and every i N, we have
10) (s, m.))))))))))))))
(9)
Applying the three point descent lemma (see Lemma in [53] with d(=) (Q (s, -), α) for
any π E II and C ((A) with the notation therein), we obtain for any policy II,
(Q" (s, -), m +1 + ( +²) S -m (Q7 (s, T.) + Do(TT + - Do n k+1)
We obtain the desired result by rearranging the above last inequality and using (9).
Lemma A.3. Let l E N NN (0} Initialized at To E ri(I), the iterates of h-step greedy PMD satisfy for every & E N,
-huithhlym < S ? 1-7 CgC,
where (cx) is the sequence of positive integers introduced in Theorem 4.1 such that de and dy [[minngg. Do(T, Do(TTTT)lll) Th)
S Ck
15

---

Proof. Let k E N. Recall that any policy π E GA(VE) satisfies T*Th-lv=, = T*, Using Lemma A.2 for E Gr, (V**) together with the previous identity and the nonnegativity of the Bregman divergence implies that for any for any policy E (V**),
di
ThV S -
T c
(10)
MJ
where the last inequality follows from the assumption on the stepsizes 7) We now prove by recurrence that for every N, T 1 v < (T V
(11)
with Σx= 7- for n 0. The base case for 0 is immediate. We now suppose that the result holds for n and we show that remains true for n 1. We have
T Thh11hh-
THNITh VT
(T V=E
TTT (T S TV for any V RRS and monotonicity of TT++1)
T (T + (2e)
(using (10) and monotonocity of T*++1)
(T
(T*(V + ne)= =TV + ice for any V E RR
S x
(Fe.n)atlrh-iv +
Σ
7 c 7
(using recurrence hypothesis and monotonicity of T
C5C + 7o.e
(TTe-1)+42hh-1
7'ce,
(12)
which concludes the recurrence proof of (11) for every N. To conclude, we take the limit in (11) and use the fact that for any V E R the sequence ((T*)1)"V),, converges to the fixed point V of the contractive operator T Hence, obtain
TEeITh-lys V
Σ E=1
Yae== T*++ + ? 1-7
cse
(13)
This concludes the proof.
Remark A.4. We note that although in our work the stepsise 77s is chosen to be the same for all states for simplicity, the same result holds for stepsize that is different for each state long as Thk (s) 2 o Do for each s E S. The same is true for all results depending on this lemma (or the inexact variant).
A.2 Proof of Theorem 4.1
As warmup, we start by reporting a convergence result for the standard PMD algorithm, recently established [20]. Using the contraction properties of the Bellman operators, it can be shown that the suboptimality gap || V*I for PI iterates converges to zero at a linear rate with contraction factor y, regardless the underlying MDP. This instance-independent convergence rate was generalized to PMD in [20]. Before stating this result, report useful three-point descent lemma to quantify the improvement of the PMD policy resulting from the proximal step compared to an arbitrary policy.
Lemma A.5 (Three Point Descent Lemma), Using the PMD update rule, we have for every k E N and every æ E II,
Tkk T Tht1 Th - Do(TT411 mT) Do(T,TT) - De(TT
(14)
16

---

This lemma results from an application of Lemma 6 in [53] which is variant of Lemma 3.2 in [10]. This same result was also used in [20].
Theorem A.6 (Exact PMD, [20]). Let (ck) be a sequence of positive reals and let the stepsize nk in (PMD) satisfy Th 2 1 |min DT(T, To)l where the minimum is computed component wise. Initialized at ri(ll), the iterates (TT)) of (PMD) satisfy for every lo E N.
|| - y 1100 S (IV-- V 1lo +
Ex-er
Cr c-11
We provide here a complete proof of this result as a warmup for our upcoming main result. Although equivalent, notice that our proof is more compact compared to the one provided in [20] (see section 6 and Lemma A. A.3 therein) thanks to the use of our convenient notations. and further highlights the relationship between PMD and Pl through the explicit use of Bellman operators.
Proof. Using Lemma A.5 with a policy G(V*)) for which T=VaN TV*K, have
1hs TV 11 Vo (D(T+ TR) + DO(T,, mx) - DT(T, TK+1).
(15)
Setting dz == |llmiin (l Do(T, Tx ak) and recalling that DT( лx) 2 for any policy IT, we obtain
dx
TV STh-IV
(16)
7/
Notice that for Policy Iteration we have TV = T v i.e. Th+1 E G(V*)). Instead, for PMD we have that T is approximately greedy (see (16)).
Applying Lemma A.5 again with x Tk, recalling that TT = T and that (o x') 2 0 for any π, x' E II, we immediately obtain VTA < T mh+ V Iterating this relation and using the monotonicity of the Bellman operator, we obtain V < *Tu+iIs. < (T**+1)2 (T"*-))\V* S S V where the last inequality follows from the fact that T has unique fixed point V*8+1 We are now ready to control the suboptimality gap follows:
< ... <
V V < V T V
=V* -V + TV T TT
V' TV d2
<V TV + c
where the first inequality follows from the inequality V 2 TR++1 proved above, the second one stems from (16), and the last a consequence of our assumption dx/1ı S Ck. We conclude the proof by taking the max norm, applying the triangle inequality and using the contractiveness of the Bellman optimality operator T.
Proof of Theorem 4.1
Proof. Similarly to Lemma A.5, we show that for any (V(m=)),
T/ Th < Tp The
(T(TT+II11)) m&) + (T TR) DT mx+t),
(17)
see Lemma A.2 for a proof. Setting de := ||min DØ(T, oloo (note the difference with da in the proof of Thcorem A.6), and recalling that ग E (VTAT)) implies that π E g(Th-lvTh) we obtain from (17) an inequality similar to (16),
ThV= < Noti Th + e.
(18)
1/b
17

---

Then, we observe that
T Th = -7au
< STtAIiThiEs
di
1
ds
- (T +
_
1/1
S (TTH11))TT-11 + +cc0.
(19)
where the second inequality follows from using (17) and monotonicity of T and the last inequality uses the assumption on the stepsizes. Then we show by recursion by iterating (19), taking the limit and using the fact that 7 * has unique fixed point V that
T Thetthh-1y <
VT
e
(20)
see Lemma A.3 for a complete proof. We now control the suboptimality gap as follows,
V V V T T h- 17
7
C&C
1-
V - -T
1 1-7 cxet T - ThELLTh-
SV -"
1 e
(21)
where the first inequality stems from (20) and the last one from reusing (18). Similarly Theorem A.6, we conclude the proof by taking the max norm, applying the triangle inequality and using the contractiveness of the Bellman optimality operator times to obtain
1
|| - Vo*+* 1loo S ~/1V'*
V** 1100 +
recursion gives the desired result.
A.3 Additional Comments About the Stepsizes in Theorem 4.1
About the cost of computing adaptive stepsizes. There is typically only one greedy policy each iteration, and in the case that there more than one it is possible to just pick any arbitrary greedy policy and the lower bound condition on the step size will still be satisfied. The cost of computing the step size is typically the cost computing a Bregman divergence between two policies. We claborate on this in the following using the discussion in [20] p. 7 in 'Computing the step size' paragraph which also applies to our setting. We use the step size condition V)k: 2 ||mingeG. (T(T,, Tk ll) We have a minimum in the condition which means we can just pick single greedy policy ă E G, (V**) (which can easily be computed given a lookahead value function in the exact setting or its estimate in an inexact setting). As for the maximum over the state space, this is because we use the same step size in all the states. This condition can readily replaced by state dependent step size na (8) 2 (* m=)(sss) which is enough for our results to hold.
About the condition on the stepsizes. First, notice that PMD has been analyzed using an increasing stepsize in the exact setting (see e.g. [25, 53, 29]) and this is natural as this corresponds emulating Policy Iteration. In the present work, notice that we do not require the stepsize to go to infinity and the stepsize does not typically go infinity under our condition. Recall that we only require the stepsize to satisfy the condition: 7i 2 1 [|minress. (V=*) Do(T, loo As the policy gets closer to the optimal one it should also get closer to a greedy policy (the optimal policy is greedy with respect its value function) and the term containing Bregman divergence will vanish (since the optimal policy is already greedy with respect to its own value function). This effect balances the decreasing Ck- Notice that we typically choose Ck = 7 2h(k+1)
We refer the reader to section D.4 for additional observations regarding stepsizes in experiments.
18

---

B Additional Details and Proofs for Section 5: Inexact /-PMD
B.1 Details and Precise Notation for Lookahead Computation
We describe here our approach to estimate Q% in more detail and introduce the notation necessary for the analysis the following sections. Assume that we are estimating (7, a) at given fixed state-action pair (s,a) a) E S x A. We define a sequence (S%) of sets of visited states as follows: Set S₁ = {s} and define for every l [0, h 1), for every E Sk+1 and for ever â E A the multiset SM, â) {&) P(-Iš, a) j E [M++1]] (including duplicated states) where M is the number of states sampled from each state & SK+1, and S Uses.aeA Se(5, a) U SE+1 (without
duplicated states). The estimation procedure is recursive. First we define the value function Vi by (5) := (3), Vš E So. where (*)()) is an estimate of (²( computed using Mo rollouts of the policy ı from state More precisely, we sample My trajectories (T)(5))) of length H 2 rolling out policy т, i.c. (3) = {(sk "g d())))sksH-H with si s and af x<-1s=) Then the Monte Carlo estimator is computed as (T) = Mo E Σ H- 7dt rtr(sk az) For each stage & E [1, hj for h 2 1, we define the following estimates for every & E Sr E A.
Qu a) = r(s
7 MR
E Vu()'), ( = max Qu (5, a), s'ES--1
(22)
aeA
The desired estimate Q a) is obtained with k = h. The recursive procedure described above can be represented as a (partial incomplete) tree where the root node is the state-action pair (s, a) and each sampled action leads to a new state node s' followed by new itateacction node (s', aa). To trigger the recursion, of the leaf state nodes 8 of this tree, i.e. the state level /t - 1 of this tree which corresponds to the last states visited in the sampled trajectories. The desired estimate (7,s, a) is given by the estimate obtained at the root state-action node (s, a). Recalling that (7, a) == r(s, a) + ((PV)) a) for any s E S, a A and V : Th-lv= the overall estimation procedure consists in using Monte Carlo rollouts to estimate the value function V before approximating V Th-1y= using approximate Bellman operator steps and finally computing the estimate (s, a) using a sampled version of Q7, (s, a) == a(s,a) + (s,)).
assign estimated values ($) of the true value function (*()) to each one
(s.
B.2 Proof of Theorem 5.3: Inexact h-PMD
Throughout this section, we suppose that the assumptions of Thcorem 5.3 hold.
Lemma B.1. Let π E II, E N. Suppose that the estimator QTT is such that 112 - -Q S for
some positive scalar b. Then the approximate h-step lookahead value function V (TT) = M Q²
a b-approximation of T w 1orphh-ye na i.e.
I (T) -
(23)
Proof. The Hölder inequality implies that for any policy क E II:
|| (T) T=7h- VT 11 max
1Q (0 (8, Q7,7 (s, T.)l
SE$
< max 1 (8, (x, ) || S b.
$E$
Lemma B.2 (Approximate h-Step Greedy Three-Point Descent Lemma). For any policy II, the
iterates Ty of approximate h-PMD satisfy the following inequality for every k 2 0:
l < 17 7 ThTThhthh + DD( - -
2m,be. (24)
Proof. We apply again the Three-Point Descent Lemma (see e.g. Lemma A.1 in (20]) to obtain:
( (s, :), T k+l > DD , < mm (s, m.) D DT -Do * (25)
19

---

which by rearranging and expressing in vector form gives:
?h h (T)
FL
S mh V/ (T++1) + DT(T, DØ(T, Tx+1) ( Tb).
(26)
Lemma B.1 implies that yielding the lemma.
h (अ) 2 T*Th- be and V (Tx+1) S Thk+t + be
The following lemma is analogue of (18) in the proof of Theorem 4.1 above, modified for the inexact case.
Lemma B.3. Assuming access at each iteration to an approximate Qn value function Q%*t with
1|0 17 20 S b, the iterates of inexact h-PMD satisfy for every k 2 0:
ThVaR -ToeIThh-Ins + 2be + dx
e. 7
(27)
Proof. Let ã be any true h-step greedy policy ग E Gn (V**), and let स be any approximate htstep greedy policy स argmax iTT (r). By definition of स and equation (26) we have: #Ell
1 Do(t, T&+1) 1
V (T)
(
S V (TT+1) + Do, TK)
Do (o(TT,1, (28)
71
The
1/s.
dx
ViTh (T++11)
e. 7
(29)
Finally we have the desired result using Lemma B.I, recalling the argument from the end of Lemma B.2 that Vith (#) T*Th-1aa be Thy - be and VTT (Tk+1) T Th--t1hh1pp bc.
Lemma B.4. Given Q7 with 11 - 1. & b, let ST, = argmaxxen V (x) denote the set of approximate h-step greedy policies and dN |min D(#, TT)ll Then the iterates of inexact h-PMD satisfy the following bound:
Tik T Th S mn V
21 1-9
7 be + 7 dge.
(30)
Proof. Analogously to Lemma A.3 we proceed by induction using Lemma B.3. We write for every k >
0,
(4)
17k
T
7
5 7 7 TTRIITAA
7h (T (T+e+1
+ 2ym 4d4e
(T mu+ 22th + 2ymbbe + 7dye
7h
77 (T 1 3 15= + nabe + 72 2d + 2ymbe + 7dge
2
m/ V + 21
7 be +
7 dge, 7
(31)
where (a) follows from the monotonicity of both Bellman operators T 11, T and the fact that 1 < TV82, (b) uses Lemma B.3 and monotonicity of the Bellman operators. The last inequality stems from the fact that for every V E R "i, (7*++:)"V / since V**+1 is the unique fixed point of the Bellman operator T which is c-contraction.
20

---

End of the proof of Theorem 5.3. We are now ready to conclude the proof of the theorem. Letting dx = -lminnze. a 2x) in the theorem, we have:
( V - V 2 V Thh11 Vv + 1 7 T)2
7 dx
2 7 be
1-9
7 dR
- - TT
Tht11 Th- 1 V +
e + +2
be
7 1]k
(6) V V + 1-
de
2
e +
be
1-7
where (i) follows from B.3 and (ii) from Lemma B.4. By the triangle inequality and the contraction property T we obtain a recursion similar to the previous theorems:
1 d2
2
|V V T 11 Ixx S ->" 1
v**
b.
1 7
Unfolding this recursive inequality concludes the proof.
B.3 Proof of Theorem 5.4
We first recall the notations used in lookahead value function estimation procedure before providing the proof. The procedure we use standard online planning method and our proof follows similar steps to the proof provided for example in the lecture notes [48]. Notice though that we are not approximating the optimal Q function but rather the lookahead value function Q7, induced by given policy II at any state action pair (s, a) S A.
Recall that for any & [2, 1], Vx and Qx are defined as follows:
Qx a) = r(5,
Σ Vi(s'), Aš Sb
(32)
Ms
s'ES
(8( = max Q - (3, a).
(3)
V3 E St
(33)
aEA
At the bottom of the recursion, recall that Vi is defined for every á E So by
1 Mo
vi(3) (3)
Σ *r(sk
Mo
k=0
using Mo trajectories (5)(5)) of length H 2 rolling out policy n. i.e. Ty(8) =
((s) ag, Josss-s with s/j 5 and ag ~ (-1s()
Note that the cardinality of each set Sg evidently upper bounded by S but also by Ah-k [[E M, as the number of states in each set grows by factor of at most AM, at step k. In this section we prove some concentration bounds on the above estimators, which will be useful for the rest of the analysis.
Lemma B.5 (Concentration Bounds of Lookahead Value Function Estimators), Let 6 (0, 1). For any state E So, with probability - 8 we have:
11
1
log(2/6)
(5)3) v=( < ())
(34)
I-
Mi
For any k E M) for state E Sy and for any action A, with probability 8 we have:
log(2/6)
(3) (JVZ) < of
?
(35)
1-71
M.
Finally. for any ls [1, for any E Sn, also with probability
5 we have:
(2g(2A/8)
M8+1 - (Tv)) (o)
(36)
1 1-7
Mr
21

---

Proof. The proof of this result is standard and relies on Hoeffding's 's inequality. We provide proof for completeness. Let Pr the probability measure induced by the interaction of the planner and the MDP simulator on an adequate probability space. We denote by E the corresponding expectation.
First we show the bound for the value function estimate Vi. This estimate is biased due to the truncation of the rollouts fixed horizon H. which the source of the first error term in the bound. For any state š E Su, the bias in (3) is given by
H
IE (3) (3) E Σ
r'r(st as) = 3,a (-111) S 1-7
(37)
The second term is due Hoeffding's inequality: each trajectory is ii., and the estimator is bounded with probability 1 by 1- Therefore (5) concentrates around its mean, and with probability 1 have:
[M(S E (1))
log(2/0)
(38)
1-71
M1
Now we prove the bound for the Qx function. Assume k E [1, hi] is arbitrary, and E Sk- For any action à E A, we can bound the error of Qx as follows:
ax( - (JV (JV)) = M&
M
(x(3() - (P
7
log(2/6)
(39)
1
Mr.
Finally we bound the Vg+1 function for 1. Assume & E [1, 1] is arbitrary, and E Sg. With probability at least 1 - we have:
V (TV)( - 1->1
?
log l2g(2A/8)
(40)
Ms
To show this last result, use standard union bound. For every / 2 0, have:
Pr([V++1 - (V) t)
PPr( max (=)
a'EA
< Primmax ''EA
Qu(3,a') max( 2) Pr(max (JV)( max (x(, ''EAA
a'EAA
ded
< Primma (Qe(3,a') (JV)) d') 2) + Pr(max (JV)) Qu(3, 21) W'EA
d'EA
$ Σ (3,))(3, - (JVK)(3, a) 2 2)) + Σ - -u(k))))))u(((,)))2 21)
aEA
aEA
(1 7)) Ma).
< 2A exep (-2
(41)
72
B.3.1 Estimation Error Bound for Qn
We start by defining some useful Bellman operators. The Bellman operator J RS + SxA and its sampled version j. S + S are defined for every V e R$ and any (s. E S b
(V(s, == r(s. + +s,Vs,,).
(42)
jV(s. = r(s, a) + Y Σ V(s')
(43)
s'EC(s.a)
where C(s, a) is set of states sampled i.i.d from the distribution P(-ss,a).
22

---

Lemma B.6. The operators T and T satisfy for every U. E R. ,SE S,EEA
- (s) JV(s, a) S -V (sU(s,a) JV(s,a)) S max s'C(s,,)
(44)
(U(s) V(s)
(45)
Proof. The proof is immediate and is hence omitted.
We now show how to bound the error of QR for any k E h2. We can bound the total error on Qk by decomposing the error into parts, accounting individually for the contribution of each stage in the estimation procedure. We will make use of the operators J as defined above and we will index them by the sets Sy (k E [1.4] for clarity. We use the notation || ||x for the infinity norm over any finite set X Recall that Q = r + PPT = JTk-iV=
for every & E [1, The following decomposition holds for any & [2, hj using the aforementioned contraction properties:
max [+ a) al)ss
aЕA
mmaaa (J a.) (JT - (,,a)sss
$ max (Jsr.. (3) (Js... (=)) + aed (P) (6,)ll
aEA
S < - - |1s,, + max (Js. Th (()))))(a))) - (JTh (;)))))sss
aEA
= - - MJTK-211111 MJT + maxl maxl (Jsx (M-I (JT (,
aEA
Symax Q - (,, - (1 (JT*-2V*( (.) + maxx T (() (JT* (7)
aEA
aed
= =mmax AEA
(x= 07 QT-((-a)ls + max] 7t (JT (JT~-V') (.
aed
(46)
which, after defining the terms AS = maxxaeAllQ4 QI(: a))ss and
& = max. T (1) yields the following recursion:
A S 7 &
(47)
and unrolling this recursion leads to the following bound on A
An
E
(48)
We begin by bounding A by partially applying the recursion above:
A max Qi(: .) JV (;,a)ss, = max jis, Vil: (Ga)l, S V*
aEA
(49)
which from Lemma B.5 we know to be bounded with probability at most 1 - S by:
H+1
log (255)
A < 7 1ss <
(50)
1
Mo
Finally, each term E, for j I k can be bounded using the following lemma below. The proof relies on a union bound over the states reached during the construction of the search tree, see the lemma towards the end of [48] for detailed explanation and proof.
Lemma B.7. Let rf)) = for j E [k]] and any k E [h), let S₁ be the root state of the tree search and for each 1 < & n(j) let S, E S, be the state reached at the - 1 simulator call such that n() S, = ( For 0 < 8 < 1 with probability
An(j)ō for any 1 $ S n(j) we have:
log(2/8)
) V a) - (JT* S 7
max
(51)
aeA
1-71 M,
23

---

Combining this result with (50) and the unrolled recursion gives the final concentration bound with probability least 1 by و for öv, ō, (0,1).
maxxl(Q((s,0000(()))) x H+ k aEAA
(gg())5ol/5) //lvv)
-1
log(2A So (A:
1)/6r)
Mo
(1 71-
M
(52)
by union bound over j I k, assuming M, M for all 1 isis 1
B.3.2 End of the Proof of Theorem 5.4
For any state-action pair (s,a) E S x A. define the set |S,] = {s} and the sets |Sy] accordingly for 0 S k h 1 1. Here |Sa| < |S || we can bound |So] deterministically as |Sp| < Mh. Using the bound in the previous section, it is possible to bound the error of Qs a) follows:
M, := M > 0, [1, Assuming the worst case growth of
(s, 07 (s. max a'EA
(:))'aa) ("(.a'))lls
7 H+h
7
log(2)Sol/óv)
Mo + 72 - --11)
log (2g(2))ooh//8)
+
1
(1 7)2
M
(53)
with probability at least 5y ōz-
Assume now we want to estimate the value function (s,, a) for all state action pairs (s, a) in some set C S x A: we want to achieve (,, [K(s, a) - ((s, a)l S b for some positive accuracy b with probability at least - 5v ōJ. This can be achieved by choosing the following parameters:
A1 و S h. M2 = M > 97 - ~ー
(2h 1og(2h.A|So/((//5))
(54)
7)2222
222h
Mo - 262 log(2(So|101/8v)
(55)
1
3rth
H
1 log 6(1 6(1-))
(56)
Picking = S x A gives I1Q, - 2o I action pairs, and the components of each value function are only computed state & E S, then the overall number of samples is of the order of KM H Sal + Kh |C] M. In particular, with C S x A, the number of samples becomes of the order of K KMHSS S Khs AM where we reuse estimators (which are in this case computed for each state-action pair (s, a) E S x A. Let K
If estimates for {Vi 1h are reused across state
most once for every
W[-ク] log( (11()(11---))) as in Theorem 5.4. Choosing dy 5 5/2 for some å 1)
and 6 = (11->((1~>)) yields the following bound with probability at least 1 8 (by Theorem 5.3):
vT 11x0 S tkk (IV- VT 1lo + - (1-
1- ni
(57)
7m) 7h)
To conclude, note that when k = K, we have:
1 1- AK
S AK 2(1 - h/)
c(1 11-
>/K (IV'--"0l flo (1 - 7) (
6
2 (58)
(1 - 7m)
C Additional Details and Proofs for Section 6: h-PMD with Function Approximation
To incorporate function approximation to h-PMD, the overall approach is as follows: compute an estimate of the lookahead value function by fitting a linear estimator using least squares, then perform an update step as in inexact PMD, taking advantage of the same error propagation analysis which is
24

---

agnostic to the source of errors in the value function. However a problem that arises is in storing the new policy, since classic tabular storage method would require (SS) memory, which we would like to avoid to scale to large state spaces. A solution to this problem will be presented later on in this section.
Since we are using lookahead in our h-PMD algorithm, we modify the targets in our least squares regression procedure order approximate Q7, rather than Q as in the standard PMD algorithm (with h 1).
C.1 Inexact h-PMD with Linear Function Approximation
Here we provide a detailed description of the h-PMD algorithm using function approximation to estimate the Q Qu-ffuction. Firstly we consider the lookahead depth h as a fixed input to the algorithm. We assume that the underlying MDP has finite state and action spaces S and A, with transition kernel
P: S x A - (AA), reward vector R E [o, 1| and discount factor y. We also assume we are given a feature map v x A + R", also written as & E R5Axd
We adapt the inexact h-P h-PMD algorithm from section 5 as follows:
1. Take as input any policy To E rint,(I), for example one that is uniform over actions in all states.
2. Initialize our memory containing To. and an empty list which will hold the parameters of our value function estimates computed at each iteration.
3. At each iteration & = O...., K. perform the following steps:
(a) Compute the targets R(=)= := (=()) for all C using the procedure described in section 5.1, using 7y as a policy.
(b) Compute 02 := argminges= Ezec (=)=(===)TO0-))))))))))))))))))) (())) and append to the list O.
(c) Using T0&g as an estimate for 0 compute T using the usual update from inexact h-PMD. This step can be merged with step 3a, the details are described below.
Computing the full policy my for every state at every iteration would require S2(S) operations, although the number of samples to the environment still depends only on d. If this is not limitation the policy update step can be performed as inexact h-PMD simply by using 1/ as an estimate for T described in step 3c. Otherwise, describe method below to compute Te demand when it is needed in the computation of the targets in step 3a, eliminating step 3c entirely.
1. The policy xn is already given for all states.
2. For any k > given we can compute Th+11 at any state using the following:
(a) Compute any greedy policy #(-Is) using Tog, for example #(a'ls) &
a' E argmax ( ((), aEA
(b) Compute 7/s := Spndeer Do Do(
(c) Finally, compute (+11)-)s) arginax {m ((V0)))) T(-13) - D+(T(-1ss), (e(()sss))((())))) (+(+))))
Remark C.I. This procedure can be used to compute (-Is) "on demand" for any k: > 0 and E S by recursively computing T& (-Is') any states s' required for the computation of v0 (since To is given). The memory cost requirement for this method is of the order of O(K A (iin(|S)/4 S}) in total which is always less than computing the full tabular policy at each iteration.
Remark C.2. Above, (Vv&)) denotes a vector in A that can be computed in ((A)) operations: each component in a is equal to (1s a) 02 which can be computed in O operations. Also, the stepsize пソ is chosen to be equal to its lower bound in the analysis of 5.3, with the value of c chosen to be equal to 22((++)), as it is needed for linear convergence. We also note that by memorizing policies as they are computed, we manage to perform just as many policy updates as are needed by the algorithm.
25

---

C.2
Discussion of Assumption 6.2
We make two preliminary comments before discussing the relevance of our assumption and alterna- tives to relax it below:
First, notice that we do not require Q% to be represented as linear function. Our assumption is an approximate action value function approximation.
When the lookahead depth h = 1, we recover the standard PMD algorithm. Notice that in this case our assumption is standard in the RL literature for linear function approximation.
Now, using notations, notice that for any policy M=Q". We have two alternatives:
II, O
7PTh-1
yPTh-1 = I
do in our assumption. In that case the targets used in regression procedure are estimates Q QT, Note also that this approach meaningful from practical point as we may directly use a neural network to approximate the lookahead Q-function which used in our h-PMD algorithm rather than approximating the Q-function first and then trying approximate from it the lookahead Q-function QT.
Directly approximate Qj
Approximate Q" with linear function approximation and use our propagation analysis (see section 5. and proof in appendix B.3.1, B.3.2) based on the link between Q7, and Q" high- lighted in the formula above. This approach which propagates the function approximation error on Q to Q% constitutes an alternative to Assumption 6.2 on Q% by an assumption Q" We discuss it further in the rest of this section.
In the following exposition provide more details regarding estimating Q" using linear function approximation and relaxing assumption 6.2 using the second approach discussed above.
Let Assumption 6.1 hold (as in Theorem 6.3). Instead of assumption 6.2. we introduce the following assumption on the Q-function Q" rather than the h-step lookahead Q-function QT.
Assumption C.3. 3e O, IT, infoers ||@ v00| 6.
We modify the h-PMD with function approximation algorithm follows: instead of directly ap- proximating Q7 using linear function approximation, we first use linear function approximation to method for inexact
approximate Q" from which h-PMD. This requires us to replace the regression targets with simpler ones, which are Monte Carlo estimates of Q instead of Q Specifically, these new targets are defined
construct estimate of Q similarly
Mu H-1
1
RM,
MD
t=
where (s
(.))) are state action pairs sampled according to the policy n, E
and (50 ,00
For any policy π we can use the same function approximation procedure as described in our paper (see Appendix C.I) to yield a Ô e d with ||Q vr < cu. (for some value of to be defined below) by simply plugging (Lecture 8). We reuse intermediate result therein (equation (7)) which guarantees the bound:
= 1. Note that this particular case was previously analysed in [48]
1
log (2g(2)C1/0)
IQ" - -0 (1 Val + vdl
(59)
1-7
1
1
2Mo
with probability at least 8 for some 8 1.
Now we reuse most of our estimation procedure in Section 5.1, simply by changing the definition of Vi to (s) = (als) for s E So. This evidently retains the guarantee that [V((s) - VT(() (0) with probability least - for each Sp. Finally, using the same error propagation analysis as in Appendix B.3.1, replacing CY ( ( with co() we obtain the following
26

---

bound for any individual state action pair (s, a):
- - (x) s 1- 1 2gg22/0%
t,² 1- -- A-1
log(2(h- 1)2
co(o))
(1 71- V
M₁
M
(60)
with probability at least - 8y¹ - -6%- -00-
Finally, the update rule as described in Appendix C.1 is replaced by (++1(-1s)
(2.(4) (Q (s, ))) (T m))). Note that we only compute T in the states where we need to compute T as described in Appendix C.I.
Unfortunately, is not clear how to directly obtain a result similar to Theorem 6.3 from this approach (controlling ||V* V* llxc at each iteration, i.e. uniformly over all states) beyond the bound that we provide above. naive union bound over the state action space would result in a bound with a logarithmic dependence on the size of the state space, unlike Theorem 6.3 which results in bound that is completely independent of the size of the state space.
We would like to add an additional comment regarding possible ways to relax Assumption 6.2 even for the standard case where h 1. Recently, Mei al. [30] proposed an interesting alternative approach relying on order-based conditions (instead of approximation error based ones) to analyze policy gradient methods with linear function approximation. We would like highlight though that their work only applies to the bandit setting to the best of our knowledge. The extension to MDPs is far from being straightforward and would require some specific investigation. It would be interesting to see if one can relax Assumption 6.2 using similar ideas.
C.3 Convergence Analysis of Inexact h-PMD using Function Approximation
Our analysis follows the same lines as the proof in [27] under our assumptions from section 6.
We compute Qn (z) for subset C of state action pairs using the vanilla Monte Carlo Planning algorithm presented in section 5. These will be our targets for estimating the value function using least squares. In order to control the extrapolation of these estimates to the full Q7, function, will need the following theorem.
Theorem C.4 ([22)). Assume 2 is finite and vb Z + Rd is such that the underlying matrix v E R xd is of rank d. Then there exist C C Z and a distribution C + 10, 1] (i.e. Esec = 1) satisfying the following conditions:
1. |CI S 11/2.
2. sup [uP=eall(())lop; S Vd where 9,:= Exec (1)))
S A. + [0, 1] be as described in the Kiefer- Wolfowitz theorem. Define i as follows:
i argmingeR
Σ ((=)(((=) Rm(22)²
(61)
ZEC
Assuming that Gp is nonsingular, a closed form solution for the above least squares problem given by Ø = 9,1 Exec (m)))))) This will be used to estimate our lookahead value function as V. We can control the extrapolation error of this estimate as follows:
Theorem C.5. Let 8 E (0, 1) and let 0 E Rdd such that [[Q7, +0 loo S G.. Assume that we estimate the targets Qn using the Monte Carlo planning procedure described in section 5.1 with parameters, M and Mo- There exists a subset C Z and distribution p : -> Rooooo which, with probability at least - 5, the least squares estimator satisfies:
11QT T011.0 S (ex(1 + Vdl + eQVa,
(62)
where
7 Hhhh h
log (4Zd2
+ 72 - 1h
log (4h /8)
EQ =
+
(63)
1 1-7
1-7
Mo
(1 7)
M
and Z: A
27

---

Proof. The proof of this theorem is identical to the one in [27], up to using our new targets and error propagation analysis instead of the typical function approximation targets for Q Q-function estimation (without lookahead). The subset C C S x A and distribution p C + [0, 1] are given by the Kiefer-Wai Woffer-Wofooiitz theorem stated above. We suppose we have access to such a set. Note that this assumption is key to controlling the extrapolation error a least squares estimate vr
We have now fully described how to estimate the lookahead value function Q using number of trajectories that does not depend on the size of the state space. In the previous section, described how to use this estimate an h-PMD style update, while maintaining a memory size that does not depend on S. Therefore we have an h-PMD algorithm that does not use memory, computation or number samples depending on
D Further Simulations
D.1 Simulations for h-PMD with Euclidean Regularization
Here we provide details of an additional experiment running h-PMD with Euclidean regularization. As in section 7, experiments were
the bsuite DeepSea environment [34] with y 0.99 and grid size 64x64. The figures are identical in structure to the ones in 7, 32 runs were performed for each value of h in 1, 5, 10, 15, and 20. In Fig. at each iteration for the same runs. When compared to the figures showing the convergence, is clearly that running the algorithm with higher values of lookahead results in convergence using fewer overall samples.
report the number of samples to the environment
0.6
0.2
0.2
0.2
0.1
0.0
Iterotiom
Iberstoo
A-1
A-5
0-10
A-15
20
Figure 2: Suboptimality value function gap for h-PMD using Euclidean Bregman divergence. in the exact (left) and inexact (right) settings. (Right) We performed 32 runs for each value of h, the mean shown solid line and the standard deviation as shaded area.
D.2 Sample Complexity Comparison for Different Lookahead Depths
We have recorded the sample complexity of our algorithm for different values of h in Figure Notice that the number of samples used at each iteration increases with h. However, notice that this increase small: h-PMD with 20 requires only 1.5 times more samples per iteration than h = as shown in Figure 3. Furthermore, increasing h greatly improves the convergence rate of the algorithm as described by our theory, which results in a much smaller number of iterations required until convergence (for example h 20 converges in at least 10 times fewer iterations than h = (see figure (right) section 7). Overall, the algorithm more sample efficient for higher values of h.
D.3 Total Running Time Comparison for Different Lookahead Depths
We provide plot accounting for running time instead of the number of iterations (see Figure 4). Observe that the overall performance is very similar to the same plot with the number of iterations on the x-axis.
28

---

X10
h=1
5
k=10
4
20
40
60
Iteration
Figure 3: Samples used by inexact h-PMD at each iteration. When compared with the first figure, clear to see the algorithm needs less samples to converge with higher values of h. Since far less iterations are needed with higher values of lookahead, the benefit of higher convergence rate greatly outweighs the additional cost per iteration.
0.
0.4
0.3
0.7
0.1
0.0
10
Time
0.5
0.0
90
50
50
Iterntions
b=1
h-
A=-20
Figure 4: Value function gap against running time. Note that the algorithms with higher values for h still converge faster in terms of runtime.
D.4 About the Stepsizes in Simulations
In our experiments we use the exaet same stepsizes described in our theory. We also observe in our simulations that the stepsize does not go infinity but rather decreases at some point and/or also note that the simulations reported in [20] (appendix D 18) also validate the fact that the stepsizes do not go to infinity (see the right plots therein for the stepsizes). We also observe a similar behavior for the stepsizes in our experiments (see Figure 5).
stabilizes. This is consequence the adaptivity of the stepsize discussed above.
D.5 Larger lookahead depths
In order to practically investigate the tradeoff increasing the lookahead depth ht we performed additional experiments where h was increased to 100 in the DeepSea bxuite environment. The plots in Figure show that increasing past the values in our initial experiments still results in better performance.
29

---

250
225
Auii
Figure 5: Behaviour of our adaptive stepsize Ti at each iteration of the algorithm for different values of h. Note that the stepsize does not diverge towards infinity, instead it usually vanishes after certain number of iterations.
0.5
0.3
0.4
0.3
0.3
0.1
0.1
0.0
0.0
Iterations
Time (6)
Am1
1=10
Am15
100
Figure 6: Value function gap plotted against number of iterations (left) and against running time (right) h-PMD in the DeepSea bsuite environment. Note that increasing the lookahead depth seems to result in better performance in terms of runtime and number of iterations.
D.6 Experiments with MCTS-based Lookahead Estimation
We have performed additional experiments in even more challenging and practical setting, on two enviromments from the bsuite [34] set: DeepSea and Catch. We have implemented our PMD algorithm with a Monte Carlo Tree Search (MCTS) algorithm (which we call PMD-MCTS) to compute the lookahead Q-function. We used DeepMind's MCTS implementation (MCTX)² in order to run this algorithm on any deterministic gym style environments implemented in JAX (we use gymnax [26] to implement these environments). Note that any tree search algorithm implementation can be used to estimate the lookahead function and plugged into our PMD method. See figures below. Note that this training procedure is more practical: we do not evaluate the value function at each state-action pair anymore each time step, we only evaluate the value function (and so only update the policy) in states that encounter using the current policy. This significantly relaxes the generative model assumption. Note that in this more challenging setting the best performance not obtained for higher values of h: intermediate values of perform better, illustrating the tradcoff in choosing the depth h.
'nttps://github. http::///gggtab...ooggolleeeeeee /nce
30

---

14-
4
0.2
033
130
500
1030
1500
30.00
Timo
0.5
2
10-3
230
400
210
500
1000
230
250)
-300
350
lteaatons
A-3
h-1
6
Figure Training curves of PMD-MCTS for the bsuite Catch (left) and DeepSea (right) environments. Note that the case of h fails to converge in any reasonable number of iterations in both environments.
D.7 Continuous Control Experiments
Finally, we performed experiments in classic continuous control environments in order to investigate the performance of h-PMD when applied to MDPs with large/infinite state spaces. For this continuous state space setting, we implemented a fully online variant of h-PMD based off of DeepMind's MuZero [40] algorithm. Experiments show that increasing the lookahead depth can lead better performance up to certain point, and the tradeoff seems to be environment-speccff..
CartPole.v1
Acrabotiv1
600
110
400
Beward
300
Rewwrd
-100
100
-500
25000
53000
75000
100000 125000 150000 175000 Stops
200005
100000
200000
300009
400003
530000
Stoae
h-3
hwd
h
Figure 8: Performance of h-PMD in two of OpenAl's gym [8] environments, CartPole-vl (left) and Acrobot-vl (right). In both figures the reward plotted against the total number environment steps evaluated, which can be understood the number of samples used. Note that higher values of h do lead to better performance for the CartPole-vl environment, but not necessarily for the Acrobot-v] environment.
D.8 Additional experiments
We conclude with results from a larger set of experiments designed to verify the robustness of our experimental results different environment parameters. We report performance of the h-PMD algorithm in the inexact setting in two different environments, DeepSea from bsuite [34], and the
31

---

classic Gridworld environment. The effect of is as expected: higher values of result in slower convergence, lower values of y yield faster convergence. The size of the environment ('chain length" for DeepSea and number of columns/rows for Gridworld) directly affects the number of iterations until convergence predictably: larger environments take more iterations to solve. Note that in all cases the effect of h is as expected, i.e. higher h leads to faster convergence.
DeepSea chein length 32, 0.99
DeepSee: daain leneth 16, 0.99
Thrratioon
Breratinss
6-1
R-5
N-10
h-15
R-20
A-1
A-5
R-10
A-15
2-20
DeepSea: chain length 32, 0.9
DeepSea: choin length 32, 0.990
0.3
11" 1/'1"
Itenatioe
Bemotions
Am5
Am10
fe-20
Jrse
A-100
h-15
Am
Gridoorld: 32 volomas, nows, 7y 0.90
Gridworld: 16 coluanss 8 nows, 7t 0.99
60
[1'* 1/
40
40-
Eisssiics
1==10
J=:00
Ame
10
bm15
Gridworld:: 32 cohumne, 16 rows, r - 0.9
Gridworldd:
moss, "t
2.5
155
0.5
000
-155
30
20
30
10
20
Tteratoee
Tomotion
2-5
b-10
A-1b
6=20
32

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Please see the abstract, the introduction and the results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Please see the future work discussion in the conclusion and the discussion about the computational tradeoff in Section 4. Assumptions for function approximation are discussed details in the Appendix.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
33

---

Answer:
[Yes]
Justification:
Please see the complete proofs in the different appendix sections.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: Details provided in the main part in the simulation sections and in the appendix, we also provide a link to an anonymous repository for the code.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
34

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: Please see link to an anonymous repository for the code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
cnisssioossoloicc for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
oniooicy))) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: This is discussed in the description of simulations in the main part and the appendix as well in the code provided.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We provide error bars (shaded area) based on runnning our simulations using different seeds and specify it is computed using the standard deviation.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
35

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We used CPUs and we also tracked running time (see relevant figures in the appendix). We performed several simulations for tuning which are not all reported in the paper. We reported several of them to show the robustness of our results to varying hyperparameters.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: http///eerppp.eeeee cwtpppp......cpeceop htcppubicc//thhicciideellliaa
Answer: [Yes]
Justification:
We checked the code and our paper conforms to it.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our contributions are mainly theoretical and focus on improving the perfor- mance of existing policy gradient methods.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
36

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our work does not involve such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best. faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We mention whenever specific existing code from some repositories and give credit appropriately.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
37

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, pwperswith thooee. cowccoo//a/o//o dataatasess has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: does not apply to our paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: does not apply to our work.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: does not apply to our work.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
38

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
39


Reviews:
[{"review_id": "MbZod6FLCf", "reviewer": "Reviewer_Pv8t", "summary": "This paper applies the idea of lookahead in policy improvement procedures under the PMD setting. They prove the $\\gamma^h$-linear convergence rate. They also propose the inexact version of h-PMD and extend to the function approximation case.", "questions": "- It's interesting to see that larger lookahead leads to faster training speed based on Figure 1. How about the sample complexities? Could you provide the used samples for each method?\n- The meaning of the dotted lines should be clarified in Figure 1 (Left).\n- Based on the theoretical result of the paper, does that mean larger $h$ leads to better performance? For Figure 1, what if we have a larger $h$?", "limitations": "The paper discusses some potential improvements in future work on the practical algorithm. However, they didn't discuss the limitations of the existing theoretical/practical results.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The writing of the paper is pretty good. The main idea and the results of the paper are easy to follow. \n\nThe paper is also complete. They propose the theoretical analysis in both tabular and function approximation settings.", "weaknesses": "Although the paper proved $\\gamma^h$-contraction property, it's not out of expectation.\n\nI'm still not completely convinced that $h$-horizon lookahead policy improvement could bring additional benefit in the function approximation case. Even in tabular cases, additional computational effort are required.\n\n\n\n\n\nMinor problems:\n\nLine 70: bsuite.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments. We are glad that the reviewer finds the writing \"pretty good\" and the \"main idea and the results of the paper easy to follow\". We address their remaining concerns in the following. Please let us know if you have any further questions, we will be happy to answer them.\n\n**I'm still not completely convinced that $h$-horizon lookahead policy improvement could bring additional benefit in the function approximation case. Even in tabular cases, additional computational effort are required.**\n\nWe also would like to add that multi-step greedy policy improvement contributed to the empirical success of some of the most impressive RL applications including AlphaGo, AlphaZero and MuZero. These practical algorithms have successfully used lookahead (via MCTS) and function approximation jointly in very large state-action space settings although they do not enjoy theoretical value function performance bound guarantees as our work. The benefit of using lookahead policy improvement has also been reported in Winnicki et al. 2021, 2023 [47, 48] for approximate policy iteration with linear function approximation. Using lookahead requires some additional computational effort and we show that it leads to a provably better sample complexity. We illustrate in our simulations how the benefit of using lookahead can greatly outweigh this overhead. Please see also e.g. Figures 6 and 7 in the appendix, in which it is very clear that $h = 1$ (no lookahead) is extremely slow to converge, whereas all versions with lookahead converge much faster. \n\n**Minor problems: Line 70: bsuite.**\n\n`Deep Mind’s bsuite’ (as written in l. 70) is the RL benchmark’s name as introduced in the reference [30]. We will make it in italic to avoid any confusion. \n\n**It's interesting to see that larger lookahead leads to faster training speed based on Figure 1. How about the sample complexities? Could you provide the used samples for each method?**\n\nAs we mentioned in l. 325-327 p. 8  in section 7, ‘we also observed in our simulations that h-PMD uses less samples overall (see Appendix D for the total number of samples used at each iteration)’. The number of samples used at each iteration increases but the algorithm requires much less iterations for higher values of the depth $h$. This results in a more sample efficient algorithm overall. Please see Fig. 3 (p. 28) and appendix D.2 (p. 27, l. 926-932) for a discussion along these lines. \n\n**The meaning of the dotted lines should be clarified in Figure 1 (Left).**\n\nThe meaning of the dotted lines is given in the text in l. 317-318 in section 7: ‘(a) in dotted lines in Fig. 1 (left), $\\eta_k$  equal to its lower bound in sec. 4, with the choice $c_k := \\gamma^{2h(k+1)})$  (note the dependence on $h$); and (b) in solid lines, $\\eta_k$  identical stepsize schedule across all values of $h$ with $c_k := \\gamma^{2(k+1)}$ to isolate the effect of the lookahead.’ We will add this to the caption of Figure 1 for clarity. \n\n**Based on the theoretical result of the paper, does that mean larger $h$ leads to better performance? For Figure 1, what if we have a larger $h$?**\n\nWe prove that a larger lookahead depth results in a better sample complexity and a faster suboptimality gap convergence rate. This improvement comes at the cost of an additional computational effort (compared to $h=1$ for 1-step policy improvement) to compute the lookahead value function at each iteration. However, our experiments suggest that the benefits of the faster convergence rate greatly outweigh the extra cost of computing the lookahead, in terms of both overall running time until convergence and sample complexity (in the inexact case). See section 7 and Appendix D for evidence and additional experiments. \n\nWe have performed additional experiments with larger $h$ ($h=100$), see Figure 1 in the attached pdf. In this case, the algorithm converges in a single iteration. This is theoretically expected as computing the lookahead values with very large $h$ boils down to computing the optimal values like in value iteration with a large number of iterations. \n\n**The paper discusses some potential improvements in future work on the practical algorithm. However, they didn't discuss the limitations of the existing theoretical/practical results.**\n\nWe thank the reviewer for the comment. We will further improve our discussion of the limitations of our work along the lines of investigating more general function approximation in even larger scale environments, adaptive lookahead depth selection as well as fully online estimators for the lookahead action values. We will also add further details regarding the computational tradeoff we mentioned for our lookahead algorithm.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Y5t4UMd5fY", "reviewer": "Reviewer_t6qC", "summary": "The paper introduces h-PMD, an extension of the Policy Mirror Descent (PMD) algorithm, which incorporates multi-step lookahead to improve policy updates in reinforcement learning. PMD is a general framework that includes several policy gradient methods and relates to advanced algorithms like TRPO and PPO. Recognizing that multi-step greedy policies often outperform their single-step counterparts, the authors propose h-PMD, which integrates multi-step lookahead depth into PMD. This new class of algorithms achieves a faster convergence rate for solving discounted infinite horizon MDPs, under both exact and inexact settings. The paper also extends these results to linear function approximation, demonstrating improved sample complexity that depends on the dimension of the feature map space rather than the state space size.", "questions": "1. Can you provide more detailed guidelines on how to implement the h-PMD algorithm in various practical settings, including both exact and inexact scenarios?\n\n2. How does the computational complexity of h-PMD compare to standard PMD and other state-of-the-art RL algorithms like TRPO and PPO in practice? Are there strategies to mitigate the increased computational burden?\n\n3. What methods or heuristics do you recommend for determining the optimal lookahead depth in different environments? How sensitive is the performance of h-PMD to the choice of ℎ?\n\n4. How critical is the assumption of a generative model for the theoretical guarantees provided in the paper? Can h-PMD be effectively applied in settings where a generative model is not available?\n\n5. How well does the h-PMD algorithm with linear function approximation perform in very high-dimensional or continuous state spaces? Have you explored other types of function approximation beyond linear?\n\n6. Can you provide more extensive empirical results across a variety of RL environments to demonstrate the robustness and general applicability of h-PMD?\n\n7. How does h-PMD compare to other advanced RL algorithms like AlphaZero, in terms of performance and computational efficiency? Have you conducted any comparative studies?\n\n8. What are the scalability limits of h-PMD in terms of state and action space sizes? Are there practical cases where h-PMD might not be feasible due to its complexity?\n\n9. Can you elaborate on the trade-offs involved in the inexact setting of h-PMD? How does the estimation of lookahead action values impact the overall performance and convergence rate?\n\n10. Have you applied h-PMD to any real-world RL problems or industrial applications? If so, what were the outcomes and challenges faced?", "limitations": "1. The multi-step lookahead in h-PMD increases the computational burden significantly, potentially making it impractical for real-time or resource-constrained applications.\n\n2. The performance of h-PMD is dependent on the chosen lookahead depth ℎ. Finding the optimal depth can be challenging and may require considerable computational resources for tuning.\n\n3. The sample complexity improvements are based on the assumption of a generative model, which may not always be available or practical in many real-world scenarios.\n\n4. While the extension to linear function approximation addresses scalability to large state spaces, the practical implementation and effectiveness of this approach in very high-dimensional or continuous spaces remain uncertain.\n\n5. The empirical validation is limited to the DeepSea RL environment. Broader validation across diverse and more complex environments would be necessary to confirm the general applicability and robustness of the proposed h-PMD algorithm.\n\n6. The paper might not provide sufficient practical implementation details, making it difficult for practitioners to apply the h-PMD algorithm to their specific problems without further guidance and experimentation.\n\n7. Some theoretical results assume exact policy evaluation, which may not be feasible in many practical settings where only approximate evaluations are possible.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The paper introduces a novel extension to the PMD framework by incorporating multi-step lookahead, enhancing the algorithm's performance and convergence rate.\n\n2. The proposed h-PMD algorithm achieves a faster 𝛾^ℎ-linear convergence rate, which is an improvement over standard PMD and Policy Iteration methods.\n\n3. The paper addresses both exact and inexact settings, providing a sample complexity analysis that demonstrates improved performance over previous methods, especially with increasing lookahead depth.\n\n4. By extending h-PMD to linear function approximation, the authors make the algorithm applicable to large state spaces, which is crucial for practical applications in complex environments.\n\n5. The theoretical findings are supported by empirical results from simulations on the DeepSea RL environment, illustrating the benefits of the h-PMD approach", "weaknesses": "1. The h-PMD algorithm, while improving convergence rates, also introduces higher computational complexity due to the multi-step lookahead, which can be demanding for large-scale problems.\n\n2. The paper might lack detailed guidance on implementing h-PMD in various practical scenarios, making it challenging for practitioners to adopt and utilize the algorithm effectively.\n\n3. The results are contingent on certain assumptions, such as the availability of multi-step greedy policies and the use of a generative model. These assumptions might limit the generalizability of the findings to all RL problems.\n\n4. The benefits of the h-PMD algorithm are closely tied to the lookahead depth ℎ. Determining the optimal ℎ in practice could be non-trivial and might require extensive experimentation.\n\n5. While the paper demonstrates the theoretical and empirical advantages of h-PMD, it may not provide a comprehensive comparative analysis against a wide range of existing RL algorithms, which would strengthen the case for its superiority.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time for assessing our work, for their feedback and questions. We reply to each of one of their questions (also covering their weaknesses and limitations comments) in what follows. We will be happy to address any further concern.\n\n**1. Can you provide more detailed guidelines on how to implement the h-PMD algorithm in various practical settings, including both exact and inexact scenarios?**\n\nTo support the description of our simulations in section 7, please note that the code for a full implementation of our algorithm is available in the anonymous code repository provided in l. 915-916 (link in section D of the appendix).  We have also implemented a version of our $h$-PMD algorithm with a Monte Carlo Tree Search (MCTS) algorithm to compute the  lookahead Q-function using DeepMind’s MCTS implementation (MCTX) (see section D.5 l. 945-950 in the appendix and the code provided for additional details). All our experiments can be replicated using this code. We will be glad to provide any further details that the reviewer might want to know regarding the implementation. \n\n**2. How does the computational complexity of h-PMD compare to standard PMD and other state-of-the-art RL algorithms like TRPO and PPO in practice? Are there strategies to mitigate the increased computational burden?**\n\nWe have compared the performance of our h-PMD algorithm to the standard PMD algorithm corresponding to $h=1$ (for fair comparison) in terms of running time in our simulations (see e.g. Figure 1 right and additional experiments in appendix D.3 Figure 4). We observe that the algorithms with higher values for $h$ still converge faster in terms of runtime, recall that they require less iterations. \n\nBeyond our simulations, exploiting parallel computing is an interesting strategy to further speed up the computation. For instance, this has been used in e.g. [8,15] (to name a few) for implementing tree search methods more efficiently. A version of our algorithm based on Deep Mind’s implementation of MCTS supports such a parallelization which can be useful in very large scale settings.  \nIn principle, using lookahead value functions can also be used in combination with TRPO and PPO.  Our focus in this work is on showing the potential of lookahead combined with PMD methods (as a general framework encompassing several PG methods as particular cases)  and providing theoretical guarantees supporting our algorithm design. We have performed additional experiments though, please see Figure 3 in our rebuttal, which illustrates the effect of modifying the PPO algorithm to use lookahead value functions. \n\n**3. What methods or heuristics do you recommend for determining the optimal lookahead depth in different environments?...**\n\nThe lookahead depth is a hyperparameter of the algorithm and can be tuned similarly to other hyperparameters such as the step size of the algorithm.  Of course, the value would depend on the environment and the structure of the reward at hand. Sparse and delayed reward settings will likely benefit from lookahead with larger depth values. We have performed several simulations with different values of $h$ for each environment setting and the performance can potentially improve drastically with a better lookahead depth value (see section 7 and appendix D for further simulations). \n\n**4. How critical is the assumption of a generative model for the theoretical guarantees provided in the paper? Can h-PMD be effectively applied in settings where a generative model is not available?**\n\nThe generative model assumption is important for our theoretical analysis. Relaxing this assumption is an interesting direction for future work. We would like to highlight that (a) this assumption is standard in RL theory and for analyzing PMD (h=1) in particular, see e.g. Xiao 2022 section 5.1, Lan 2023 section 5.1, Johnson et al. 2023, Yuan et al. 2023, Alfano et al. 2023, Li et al. 2023, Zhan et al. 2023 and (b) even under this standard assumption, the analysis requires a careful and involved analysis (see 5.2 and appendix B). Prior work considering lookahead policy iteration algorithms has even focused on the far less challenging deterministic setting assuming that lookahead value functions are accessible (see e.g. [9]).  \nIn practice, we refer the reader to section D.5, l. 950-956 for a discussion about how to relax it: We only evaluate the value function (and so only update the policy) in states that we encounter using the current policy. We have also implemented our PMD algorithm with a Monte Carlo Tree Search (MCTS) algorithm) to compute the  lookahead Q-function using DeepMind’s MCTS implementation (MCTX) (see section D.5 l. 945-950 in the appendix and the code provided for additional details). The design and analysis of a fully online algorithm is an interesting research question that requires further investigation and that we leave for future work. \n\n**5. How well does the h-PMD algorithm with linear function approximation perform in very high-dimensional or continuous state spaces? Have you explored other types of function approximation beyond linear?**\n\nThank you for this question. We believe this is an interesting question to address in the future to cover even larger settings as we briefly mention in the conclusion. Using linear function approximation requires designing state-action features which is a delicate task in general as it is notoriously known, especially in high-dimensional spaces. That being said, we have provided a theoretical performance bound for our algorithm in that setting. We are working on using neural networks for approximating the lookahead values to implement an actor-critic style algorithm with lookahead. Please see our experiments on continuous control tasks in Figure 3 of our rebuttal, which illustrates the use of neural net function approximation with h-PMD.\n\n**Please see response to remaining questions (6-10) in the global rebuttal.**", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "x7Y6zwiNlW", "reviewer": "Reviewer_SGix", "summary": "The author propose a multi-step greedy approach for Policy Mirror Descent. Combing PMD with multiple greedy policy updates results in a faster $\\gamma^{h}$ rate improved the previously thought optimal $\\gamma$ rate. Additionally, the authors extend their analysis to the stochastic setting and when using function approximation (with linear function approximation).", "questions": "How well does $h$-PMD perform against PI in the deterministic setting?\nCould you provide some intuition on why distribution mismatch coefficients does not appear in the stochastic setting? It's surprising to me since there isn't  any explicit exploration.", "limitations": "No concerns.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "The idea of combining lookahead to PMD is well-motivated and interesting.  The motivation and presentation of the results are explained well. All results also do not rely distribution mismatch coefficients, which is something that appears quite often in prior work", "weaknesses": "It seems that the analysis is done in the functional representation of the policy. It would be good to also discuss how the methods could extended for specific policy parameterization such as softmax policies.\nSince the resulting bounds do not rely on concentrability, it would be nice to see experiments where the state space is much larger.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback and for acknowledging the novelty and well-founded motivations of our paper as well as its presentation. We hope that the following discussion fully answers your questions.\n\n**It seems that the analysis is done in the functional representation of the policy. It would be good to also discuss how the methods could be extended for specific policy parameterization such as softmax policies.**\n\nThank you for your comment. While softmax tabular policies are covered by our analysis, we acknowledge that it would be interesting to consider more general policy parametrization. When introducing (neural network) policy parametrization and considering policy parameters as main variables, we lose part of the structure of the policy optimization problem and we introduce additional non-convexity (on top of the non-convexity of the value function as a function of the policy) into the problem when the objective is seen as a function of the policy parameters. Therefore, we expect to obtain weaker results using a different analysis based on gradient dominance properties of the policy optimization objective rather than contraction arguments.   \n\n**Since the resulting bounds do not rely on concentrability, it would be nice to see experiments where the state space is much larger.**\n\nWe have performed additional experiments during the rebuttal phase, please see Figure 3 in our rebuttal for experiments showing the feasibility of h-PMD in even continuous state spaces. In these experiments we test our algorithm in continuous control problems (CartPole-v1 and Acrobot-v1). Please note that our algorithm converges in a comparable number of iterations to the variant  without lookahead.\n\n**How well does $h$-PMD perform against PI in the deterministic setting?**\n\nThank you for this question. In the deterministic setting, h-PMD enjoys a faster $\\gamma^h$ convergence rate compared to PI without lookahead in terms of value function gap. h-PMD and h-PI enjoy similar guarantees in terms of value function gap when using our adaptive step sizes for h-PMD. In terms of policy convergence (rather than value function gap convergence), note that PI also enjoys some strong convergence guarantees: it is guaranteed to converge to an optimal policy in a finite number of iterations. As noted in (Efroni et al., 2018, Theorem 3) this result generalizes to $h$-PI as well, yielding a finite iteration complexity guarantee that improves monotonically with $h$. It would be interesting to see if h-PMD can also enjoy such a guarantee in future works, given the relationship between h-PI and h-PMD (see the discussion after Theorem 4.2). That being said about the deterministic setting, note that the true strength of $h$-PMD is in the stochastic setting, where PI is known to be unstable. Please see Figure 2 in our rebuttal which illustrates this in a practical setting. \n\n**Could you provide some intuition on why distribution mismatch coefficients does not appear in the stochastic setting? It's surprising to me since there isn't any explicit exploration.**\n\nFrom the technical viewpoint, we remove the dependence on distribution mismatch coefficients by avoiding the use of the performance difference lemma (as previously shown by Johnson et al. 2023) and by conducting an analysis which builds on the strong connection between h-PI and h-PMD.\nNotice that the performance error bound in Theorem 5.3 (for inexact h-PMD) features two terms: the first one which stems from the $\\gamma^h$ contractiveness of the $h$-step Bellman operator is the same as in the exact setting (Theorem 4.1) and does not involve any distribution mismatch coefficient whereas the second one is a bias term due to lookahead value function estimation that can be made arbitrarily small upon choosing the right minibatch size. In our stochastic setting, we rely on the standard generative model assumption. The (inexact) value function is being computed at every state in the tabular setting, precluding the need for exploration. In this setting, our results are consistent with the work of Johnson et al. 2023 [16] focusing on the particular case of $h=1$. We expect that exploration will play an important role in the online setting where the value function is estimated using online trajectories (i.e. generated according to the current policy at each time step).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZgZSEpTE3s", "reviewer": "Reviewer_vPQx", "summary": "The authors proposed a version of the policy mirror descent algorithm that uses a multi-step greedy policy improvement operator. Afterward, the authors showed the theoretical benefits of the proposed method by a better contraction rate $\\gamma^h$ instead of $\\gamma$-contraction for a usual 1-step greedy policy improvement algorithm. Finally, the inexact version of the algorithm was proposed with an improved sample complexity in the finite MDP setting and, under a linear functional approximation setup, guarantees that are independent of the state space size.", "questions": "- I think the paper may benefit from a theoretical example of h-PI with greedy updates not convergent whereas h-PMD converges.", "limitations": "The paper is mostly of theoretical nature and thus does not imply any negative societal impact.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The proposed combination of PMD and $h$-step greedy updates implies interesting theoretical results, such as reducing sample complexity with increasing the planning horizon in a very explicit way;\n- Strong result with linear functional approximation that gives an implementable algorithm with a polynomial (in $h$) running time;", "weaknesses": "- The experimental part of the paper might be improved by running continuous control experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive assessment of our work and for appreciating our theoretical contributions. We reply to their remaining comments in the following. \n\n\n**The experimental part of the paper might be improved by running continuous control experiments.**\n\nThank you for the suggestion, we have performed simulations in this setting in the rebuttal phase. Please see Figure 3 in our rebuttal which shows the results of running h-PMD in continuous control settings (CartPole-v1 and Acrobot-v1). We will make sure to include these in our paper. \n\n**I think the paper may benefit from a theoretical example of h-PI with greedy updates not convergent whereas h-PMD converges.** \n\nThank you for this interesting comment. It has been shown in Efroni et al. 2018 [9] that h-PI converges in the deterministic setting. We have observed that h-PI is unstable in the stochastic setting when the lookahead action values are not very accurately estimated and h-PMD fixes this instability. Such an instability has also been observed in prior work for $h=1$. We have performed simulations to illustrate this in an example in the attached pdf using the same lookahead action values estimation precision (see Figure 2 in our rebuttal). It has been shown in Winnicki and Srikant 2023 [48] that PI with lookahead might converge even in the stochastic setting thanks to using larger lookahead. However, such a result requires a sufficiently large lookahead (see their assumption 1.(b)). Our results for $h$-PMD hold for any lookahead depth value $h$. We believe it would be possible to find an instance where stochastic h-PI does not converge (for a fixed not too large $h$) whereas stochastic h-PMD does: This interesting question remains open.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qNajpcBuL3", "reviewer": "Reviewer_QSY1", "summary": "The paper studies policy mirror descent (PMD) where the policy improvement step is modified to include an action-value with $h$-step lookahead (contains $h-1$ applications of the Bellman optimality operator on the value of the policy from the previous iteration). In the exact tabular setting where the value functions can be computed exactly, this leads to an improvement of the linear convergence rate of standard PMD from $\\gamma$ to $\\gamma^h$. In the inexact tabular setting where the the lookahead Q-functions are estimated through Monte-Carlo rollouts, this gives a sample-complexity for finding a $\\varepsilon$-optimal policy of $\\tilde{O}(1/\\varepsilon^2(1-\\gamma)^7)$, improving by a factor of $1/(1-\\gamma)$ with respect to prior work. Finally, they extend their results beyond the tabular setting to a linear function approximation setting.", "questions": "This questions are related to choosing $h$ as discussed in the weaknesses.\n- It seems that one step of $h$-PI is equivalent to $h$ steps of value iteration with a policy produced at the end by acting greedily with respect to the last value. Is this the case ? If so, is there a way to choose a good value of $h$ that balances the benefits of VI and PI/PMD ?\n- In the simulations, it seems like taking $h$ bigger provides better convergence without the cost of longer runtime. Is this the case for all values of $h$ ? If not, it would be nice to see this reflected in the experiments (i.e. taking much larger values of $h$ which begin to impede on the runtime). If it is true for all values of $h$, is it essentially saying that value iteration is computationally more efficient than PI/PMD in the setting you consider ? And then it would be nice to consider settings where this perhaps is not the case ?", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is quite well written and easy to follow.\n- The paper presents an interesting extension of PMD to include look-ahead leading to faster convergence. The algorithm and results cover different settings from exact tabular to inexact with linear function approximation. Numerical experiments support these claims both in terms of iterations and runtime.", "weaknesses": "- The Analysis of Theorem 4.1 closely follows that of [16] while the remaining results (Theorem 5.4 and Theorem 6.3) follow using analyses similar to prior works (except for the estimation of the lookahead Q-function). Nevertheless, I recognise the merit and novelty in combining these with the idea of lookahead from [9]. Note - it would be good to explicitly state where the proof of Theorem 6.3 can be found in the Appendix.\n- It seems the only disadvantage of $h$-PMD over $1$-PMD is in the computational cost of computing a more complex value function (lines 212-215) but it is unclear exactly what this cost is (other than what is conveyed in the experiments). It would be nice to explicitly quantify the additional computation (e.g. in the tabular setting, computing the true value function can be done by finding the fixed point of $\\mathcal{T}^\\pi$ which involves inverting a $S\\times S$ matrix, then how much extra computation is required to achieve the value function with lookahead ?). Note: in lines 194-195, the assumption is not only that the value function $V^{\\pi_k}$ can be computed exactly but also the value function with lookahead $V^{\\pi_k}_h$ right ?\n- The rationale behind how to choose $h$ is not clear to me (see also questions below). For example, in Theorem 5.4 (line 270), if the overall sample complexity is $\\tilde{O} (\\frac{S}{h\\varepsilon^2(1-\\gamma)^6(1-\\gamma^h)^2} + \\frac{SA}{\\varepsilon^2 (1-\\gamma)^7})$, this seems to suggest that we should take $h \\rightarrow \\infty$. Besides the computational infeasibility of this, if the lookahead Q-functions are estimated using Algorithm 1, then taking $h \\rightarrow \\infty$ should also result in a sample complexity going to $\\infty$, it seems odd that this does not appear in the sample complexity. It would be nice to have an explanation of this.\n\n\nTypos:\n- Line 128: you are missing a “the” in front of squared Euclidean distance.\n- Line 564-565, in equation (12), $\\mathcal{T}^{\\pi_{k+1}}$ should be to the power of $n+2$ not squared.\n- Line 344: succesfully -> successfully", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive feedback on our work and for their useful comments. We are glad the reviewer found the paper \"quite well written and easy to follow\" and the idea of using lookahead in PMD \"interesting\".  We address their concerns in the following. \n\n**It would be good to explicitly state where the proof of Theorem 6.3 can be found in the Appendix.**\n\nThank you for the suggestion, we will add a pointer to the proof (in appendix C.3 p. 26) in the main part. \n\n**It seems the only disadvantage of $h$-PMD over $1$-PMD is in the computational cost of computing a more complex value function (lines 212-215) but it is unclear exactly what this cost is (other than what is conveyed in the experiments). It would be nice to explicitly quantify the additional computation...**\n\nThank you for the question which we now answer in detail in different settings: \n- Deterministic setting: in this case, the computational overhead of h-PMD over 1-PMD is given by the cost of computing the lookahead action values. These can be computed by performing h steps of VI as the reviewer mentioned. The total cost of this computation can be decomposed into the cost of computing a single value function plus the cost of applying the Bellman optimality operator h times. Overall, the total cost is $O(S^3 + h AS^2)$ which only scales linearly with h compared to h=1 (no lookahead) without any additional dependence on the state nor action space sizes.  \n\n- Stochastic setting: in this case, the computational overhead of h-PMD vs PMD is given by the cost of computing the Monte Carlo lookahead action values estimates. Following our procedure in section 5, the induced computational cost for any single state-action pair is that of performing h steps of approximate value iteration which gives a cost of the order of $O(h M S A + H M_0 S)$ where $h$ is the lookahead depth, $M$ is the minibatch size for the sampled transitions for planning, $M_0$ is the number of trajectories for value estimation and $H$ is their horizon length. \nThanks again for the question, we will add this discussion to the paper. \n\n**Note: in lines 194-195, the assumption is not only that the value function $V^{\\pi_k}$ can be computed exactly but also the value function with lookahead $V^{\\pi_k}_h$ right ?**\n\nIn these lines, notice that we suppose access to a `greedy policy with respect to the value function’ (and not the lookahead one) because greediness refers here to $h$-greedy as defined in l. 149. Another way to formulate it is to suppose access to the lookahead value function from which the 1-step greedy policy can be computed.   \n\n**The rationale behind how to choose $h$ is not clear to me (see also questions below). For example, in Theorem 5.4 (line 270), if the overall sample complexity is $\\tilde{O} (\\frac{S}{h\\varepsilon^2(1-\\gamma)^6(1-\\gamma^h)^2} + \\frac{SA}{\\varepsilon^2 (1-\\gamma)^7})$, this seems to suggest that we should take $h \\rightarrow \\infty$. Besides the computational infeasibility of this, if the lookahead Q-functions are estimated using Algorithm 1, then taking $h \\rightarrow \\infty$ should also result in a sample complexity going to $\\infty$, it seems odd that this does not appear in the sample complexity. It would be nice to have an explanation of this.**\n\nThe number of samples used for lookahead action value function estimation (at each iteration of h-PMD) is of the order of $O(h M S A  + H M_0 S)$ where $h$ is the lookahead depth, $M$ is the minibatch size for the sampled transitions for planning, $M_0$ is the number of trajectories for value estimation and $H$ is their horizon length. Indeed, this sample complexity explodes with a growing lookahead depth $h$. However, our theorem 5.4 shows that we need less and less iterations $K$ when $h$ grows, namely $K > 1/h(1-\\gamma) log(4/\\epsilon(1-\\gamma)(1-\\gamma^h))$ (see l. 263). Altogether, the total sample complexity is $O(K (h M S A  + H M_0 S))$ which implies that the $1/h$ in K cancels the multiplicative $h$ in the first term of the overall sample complexity. However, notice that the number of iterations $K$ of h-PMD has to be at least 1 to run our algorithm and this condition translates into a condition on the lookahead depth which needs to be no larger than the effective horizon. Increasing $h$ speeds up the convergence rate of the algorithm which allows us to afford a smaller number of iterations $K$. This number of iterations needs to be lower bounded by 1 though. \n\n**Typos:** Thank you for spotting these, we will make sure to correct them. \n\n**It seems that one step of  $h$-PI is equivalent to $h$ steps of value iteration with a policy produced at the end by acting greedily with respect to the last value. Is this the case ? If so, is there a way to choose a good value of $h$ that balances the benefits of VI and PI/PMD?** \n\nThank you for this interesting comment and question. Indeed, this is correct in the deterministic (exact) setting. It has been shown in Efroni et al. 2018 [9] (see their Theorem 3) that h-PI enjoys a finite iteration policy convergence guarantee which is monotonically improving with $h$ increasing. In the stochastic setting, we are not aware of any policy convergence result in a finite number of iterations for h-PI, let alone h-PMD. We believe it would be interesting to investigate if we can both guarantee value function convergence as well as policy convergence with a suitable lookahead value.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all the reviewers for their valuable time and feedback. We address the remaining concerns of the reviewers in our individual responses below. We have also performed additional experiments to support our responses. Please find figures relating to these experiments attached. These simulations include: a) testing the effect of a much larger lookahead depth (Reviewer Pv8t), b) comparing h-PI to h-PMD (Reviewers vPQx and SGix), c) testing h-PMD on two additional continuous control environments. Due to space constraints in our individual response to reviewer t6qC we include the rest of our response below in this general rebuttal. We hope that our responses address all of the questions of the reviewers, we also welcome any additional questions in the discussion period.

 --------

**End of response to reviewer t6qC**

**6. Can you provide more extensive empirical results across a variety of RL environments…?** 

We have provided additional simulations in appendix D, p. 27-31, including tests in the `Catch’ environment from Deepmind’s bsuite and a grid world with variable size. As for robustness of h-PMD, we have investigated (in the appendix) the use of a different PMD regularizer (Figure 2) as well as varying  lookahead depths, chain lengths, grid world sizes, discount factors  (p. 30-31). That being said, please notice that our main contributions are theoretical and our simulations primarily serve an illustrative purpose. 
During the rebuttal phase we performed additional experiments in continuous control tasks to illustrate the general applicability of our algorithm. 

**7. How does h-PMD compare to other advanced RL algorithms like AlphaZero, in terms of performance and computational efficiency?..**

Our h-PMD algorithm can be linked to the class of AlphaZero algorithms (see l. 180-187). It has been shown in [13] that AlphaZero can be seen as a regularized policy optimization algorithm, drawing a connection to the standard PMD algorithm (with h = 1). We argue that AlphaZero is even more naturally connected to our h-PMD algorithm with lookahead values. We have also implemented a version of our h-PMD algorithm with Deep Mind’s MCTS implementation (see section D.5 for details). Conducting further experiments to compare our algorithm to AlphaZero on similar large scale settings would be interesting and would deserve its own separate study. Note that we are not aware of any theoretical convergence guarantee for AlphaZero which relies on many heuristics. In contrast, our $h$-PMD algorithm enjoys nice theoretical guarantees ranging from the exact to the inexact, stochastic and function approximation settings.

**8. What are the scalability limits of h-PMD in terms of state and action space sizes?...**

We prove in theorem 5.4 p. 7 that the sample complexity of h-PMD scales with the product of the state and action space sizes in the tabular setting. Then, we employ linear function approximation to show a value function gap performance bound that only scales with the dimension of the state action feature map without any dependence on the state action space size. Please see the response to reviewer QSY1 for a more detailed discussion.
Tree search methods (used as subroutine in h-PMD for lookahead value estimation) have been successfully used in practice in a number of works, including in the most successful applications of RL such as AlphaGo, AlphaZero and MuZero to name a few. Notice also that we also rely on Deep Mind’s efficient MCTS implementation in our experiments in appendix D.5. Hence, we do not foresee any feasibility issue of h-PMD given all the existing efficient tree search implementations that can be readily used as subroutines. As PG methods are also notoriously suitable for high-dimensional settings, our h-PMD also inherits such a potential. Our additional experiments show that our algorithm can be modified to work smoothly in large or even continuous state spaces (see Figure 3 in the rebuttal pdf), and is still reasonable when the lookahead depth is scaled up dramatically (see Figure 1). We will add to our paper a more detailed discussion along these lines.

**9. Can you elaborate on the trade-offs involved in the inexact setting of h-PMD? …**

Comparing Theorem 4.1 (exact setting) and Theorem 5.3 (inexact setting), there is an additive bias term in the value function bound due to inexact approximation of the lookahead value functions. In Theorem 5.4, we control this bias and make it arbitrarily small by choosing an adequate mini-batch size (of the order of $1/\epsilon^2$ where $\epsilon$ is the desired accuracy) for our Monte-Carlo lookahead estimator. We then derive the overall improved sample complexity of Theorem 5.4. 
Hence the convergence rate (in terms of number of iterations) is now still geometric but up to the aforementioned bias and the overall sample complexity to reach an approximate optimal value function is improved. This is at the cost of computing approximate lookahead action values as discussed.

**10. Have you applied h-PMD to any real-world RL problems or industrial applications? …**

Thank you for this question which is definitely important. To support our contributions which are mainly theoretical, we have performed simulations in standard widely used RL benchmarks in the literature beyond existing simulations for h-PI which were restricted to the simple grid world environment (see e.g. [9]). These initial experiments are promising and we believe it will be interesting to test our algorithm on real-world RL problems.

**Some theoretical results assume exact policy evaluation, which may not be feasible …**

We completely relax exact policy evaluation in section 5. We do not suppose access to multi-step greedy policies, we rather provide a procedure to compute them approximately: See section 5.1 for lookahead Q-function estimation and its use in $h$-PMD in Eq. (5) as well as its extension to the function approximation setting (see Eq. (7) and section C).

Meta-review: This work studies a new generalization of Policy Mirror Descent (PMD), h-PMD, which uses an h-step lookahead improvement for evaluating the Q function, instead of merely estimating the standard Q-function. The authors generalize the PMD analysis to establish the convergence of h-PMD and study its performance in the approximate setting, where the Q functions are approximately correct. They also present experimental results of h-PMD and investigate its performance as the lookahead parameter increases.
To my knowledge, this is the first work that formalizes the idea of combining mirror descent (or gradient descent) with h-step optimal Q functions. This formalization is useful, especially due to the fact that planning-type algorithms (e.g., MCTS) combined with RL-type techniques are known to be used in practice.

Technically speaking, the theoretical results are extensions of existing PMD analysis, with a careful application of the gamma^h contraction property of the Bellman operator. Further, the authors derived new for the h-PMD performance in the approximate. 

Reviewers emphasized the empirical section of this work should be improved. Specifically:
1. The algorithm was tested only on a toy environment. In the rebuttal the authors shared results on additional environments.
2. The algorithm implementation in practice is not clear. h-PMD is only the high-level framework of the design, but the practical implementation is more nuanced. I would suggest the authors include the full algorithm in the appendix (e.g., how the loss functions are calculated per each batch? how often the h-step lookahead policy is calculated? are there any useful tricks worth mentioning?). I believe this can be incorporated in the camera ready version.
3. Is it worth scaling h to larger values in practice? Although the authors studied some aspects of this question in Appendix D, I believe further empirical investigation into this topic would be useful and should be presented in the main paper.

Even though there is more work to be done in this direction (e.g., how should we set h in practice?), I believe this work makes a substantial contribution and may pave the way for future advancements. I encourage the authors to incorporate the reviewers' and the aforementioned edits into the camera-ready version.
Decision: Accept (poster)