Policy Mirror Descent with Lookahead

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.

Strengths

- The paper is quite well written and easy to follow. - 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. - 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 ? - 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. Typos: - Line 128: you are missing a “the” in front of squared Euclidean distance. - Line 564-565, in equation (12), $\mathcal{T}^{\pi_{k+1}}$ should be to the power of $n+2$ not squared. - Line 344: succesfully -> successfully

Questions

This questions are related to choosing $h$ as discussed in the weaknesses. - 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 ? - 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 ?

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

Yes

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.

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; - 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.

Questions

- I think the paper may benefit from a theoretical example of h-PI with greedy updates not convergent whereas h-PMD converges.

Rating

7

Confidence

2

Soundness

3

Presentation

3

Contribution

3

Limitations

The paper is mostly of theoretical nature and thus does not imply any negative societal impact.

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).

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. Since the resulting bounds do not rely on concentrability, it would be nice to see experiments where the state space is much larger.

Questions

How well does $h$-PMD perform against PI in the deterministic setting? 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.

Rating

7

Confidence

2

Soundness

3

Presentation

4

Contribution

4

Limitations

No concerns.

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.

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. 2. The proposed h-PMD algorithm achieves a faster 𝛾^ℎ-linear convergence rate, which is an improvement over standard PMD and Policy Iteration methods. 3. 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. 4. 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. 5. 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. 2. 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. 3. 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. 4. 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. 5. 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.

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? 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? 3. 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 ℎ? 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? 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? 6. Can you provide more extensive empirical results across a variety of RL environments to demonstrate the robustness and general applicability of h-PMD? 7. 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? 8. 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? 9. 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? 10. Have you applied h-PMD to any real-world RL problems or industrial applications? If so, what were the outcomes and challenges faced?

Rating

4

Confidence

4

Soundness

3

Presentation

2

Contribution

2

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. 2. 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. 3. 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. 4. 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. 5. 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. 6. 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. 7. Some theoretical results assume exact policy evaluation, which may not be feasible in many practical settings where only approximate evaluations are possible.

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.

Strengths

The writing of the paper is pretty good. The main idea and the results of the paper are easy to follow. The 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. 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. Minor problems: Line 70: bsuite.

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? - The meaning of the dotted lines should be clarified in Figure 1 (Left). - 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$?

Rating

4

Confidence

3

Soundness

3

Presentation

3

Contribution

2

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.

Reminder to address the author's rebuttal

Dear Pv8t, please try to respond to the author's feedback today and elaborate if your opinion changed in light of it.

Reminder to address the author's rebuttal

Dear t6qC, please try to respond to the author's feedback today and elaborate if your opinion changed in light of it.