Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted Markov Decision Processes

Summary

This paper proposes a new analysis of the policy mirror descent algorithm and achieves a linear convergence rate with exact $Q$-function that does not contain any distribution mismatch coefficient. Furthermore, it also proposes lower bounds showing that the linear convergence rate is optimal under specific setting and policy-dependent learning rates are necessary to achieve this rate.

Strengths

- The convergence result for policy mirror descent is strong while the analysis is concise. - The proposed two lower bounds are also considered to be novel.

Weaknesses

One weakness of this paper lies in the lower bound stated in Theorem 4.2 only holds for $k<n$, which does not rule out possibility of stronger convergence rate when $k\geq n$. Therefore, it seems not very appropriate to claim that this result is optimal without any qualifiers. Another weakness is on the lack of experiments. Since the major results of this paper strongly rely on a delibrately designed learning rate, it will be much better to empirically (in some tabular MDPs) see that this choice of learning rate is indeed better than other choices.

Questions

- What are the difficulties of extending the result in Theorem 4.2 to the setting of $k\geq n$? - Is that possible to strengthen the Theorem 4.3 in a form saying that (under the same or similar setting for $n$, $\gamma$ and $\mathcal{S}$) policy-dependent learning rates are necessary whenever we hope to achieve $\Vert V^\star-V^k\Vert_{\infty}\leq c_0\gamma^k(\Vert V^\star-V^0\Vert_{\infty}+c_1)$ for any $c_0, c_1>0$? - Is $\eta_k$ always guaranteed to be finite?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

The limitations are not addressed very well as explained in the weakness section.

Summary

This paper studies the convergence rate of a general family of policy gradient methods called Policy Mirror Descent (PMD) in the setting of discounted MDP, unregularized objective, and tabular policy model. In prior work ((Xiao, 2022), [7] in the paper), it has been known that with a geometrically increasing step size schedule, all PMD algorithms enjoy nice convergence rate and sample complexity with respect to the discounting factor $\gamma$, but the bounds proved in [7] also depend on a "distribution mismatch coefficient" term. This paper shows that with a more adaptive step-size schedule, this "distribution mismatch coefficient" term can be removed from the bounds. The results are derived by simplifying the analysis in [7] with a value improvement property of PMD algorithms (Lemma A.2). The paper also presents theorems to argue that the convergence rate they proved is tight, and that the adaptive step-size schedule is necessary for achieving this rate.

Strengths

1. This paper seems to be a solid follow-up work after (Xiao, 2022) [7]. The paper gives a nice analysis to the PMD algorithms (removing unnecessary and "ugly" terms in previous results, simplifying the analysis framework, providing optimality/necessity arguments, etc.). 2. The results presented in this paper are nicely compared and contrasted with previous works.

Weaknesses

1. I am not very sure about the significance of the results presented by the paper. While it is nice to see that with carefully scheduled step sizes every PMD algorithm could match the performance of PI and NPG, the step-size schedule required does not look very practically feasible to me, and it's still not clear if any concrete and practical PMD algorithm can demonstrate better performance than PI and NPG. Because PI and NPG are two special cases of PMD, bounds applying to all PMD algorithms are necessarily subject to the bounds of PI and NPG, so I wonder if aiming at proving bounds that "universally" apply to all PMD algorithms, as this paper does, can be truly helpful in identifying *better* PMD algorithms. Maybe the authors can consider to better motivate this work. 2. I have some concern about whether Theorem 4.2 can indeed establish the optimality of the convergence rate as proved in the paper. If I understand correctly, Theorem 4.2 says that for any given state-space size $|S|$, there exists a MDP with $|S|$ states such that no PMD algorithm can be faster than the linear $\gamma$-rate in the first $|S|/2$ PMD iterations. But this result does not bound the asymptotic performance of PMD, right? As the paper already mentioned (Line 265), PI can converge exactly to the optimal policy in finite iterations, this fact means PI, as one instance in the PMD family, must converge faster than the linear $\gamma$-rate after the first $|S|/2$ iterations. In this case I am not sure why the linear bound in Theorem 4.1 must be optimal.

Questions

A. Table 1: Why isn't "linear $\gamma$-rate" checked for [7], while at Line 31 you said "*linear convergence of PMD was established by [7]*"? B. Line 264-266: I wonder if extending (7) to k>n will necessarily contradict with the fact that PI converges in finite iterations. Specifically, the latter implies that for large enough k, we have $||V^*-V^k||=0$. To have (7) hold for such k, we "only" need to have $\gamma^k ||V^*-V^0||\leq \frac{2\delta}{1-\gamma}$, which does not look impossible to me unless $\delta$ and $V^0$ have some special constraints -- can you explain a bit more here? Although (7) is linear to $\gamma^k$, does the negative constant term $-\frac{2\delta}{1-\gamma}$ in (7) actually allows exact convergence to $V^*$? C. Line 308: $(s^0_t, a^0_t)$ should be $(s^i_0, a^i_0)$ ?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

Yes.

Summary

This work considers the class of Policy Mirror Descent (PMD) methods and establishes a linear $\gamma$-rate which is dimension-free using adaptive step sizes. In particular, the convergence rate does not depend on visitation distribution mismatch coefficients or the state/action space sizes. It is further shown that this rate is optimal for PMD methods as it is the case for Policy Iteration via a matching lower bound. Adaptive step sizes are also shown to be necessary for this result to hold. Improving over prior work, the analysis which does not make use of the performance difference lemma is further extended to the inexact setting where the action value function needs to be estimated under a generative model.

Strengths

- The independence of the rate on the visitation distribution mismatch coefficients is interesting and the novel analysis avoids using the performance difference lemma to achieve this. The flexibility of the analysis offers the possibility to close the gap between the convergence rates of PG methods and value-based methods in terms of $1/(1-\gamma)$ and match the known lower bound. - The convergence rate which holds for the $l_{\infty}$ norm is shown to be optimal and the adaptive step size is also necessary. - The paper is well-written and the contributions are clearly presented. - The results are sound and the proof of the main result is clean.

Weaknesses

- The interesting dimension-free rate seems to come with the price of more complicated adaptive step sizes compared to the increasing steps in [7]. - Some recent related works going beyond the tabular setting are missing in the discussion, especially regarding l. 131-133. Yuan, R., Du, S. S., Gower, R. M., Lazaric, A., & Xiao, L. Linear convergence of natural policy gradient methods with log-linear policies. ICLR 2023 Alfano, C., & Rebeschini, P. (2022). Linear convergence for natural policy gradient with log-linear policy parametrization. arXiv preprint arXiv:2209.15382. Alfano, C., Yuan, R., & Rebeschini, P. (2023). A novel framework for policy mirror descent with general parametrization and linear convergence. arXiv preprint arXiv:2301.13139. - While a matching lower bound is provided for the convergence rate, the dependence with respect to $1/(1-\gamma)$ does not improve over prior work and does not match the known lower bound as acknowledged by the paper. - Leveraging a connection with Policy Iteration, a dimension free rate was previously established in the literature in [9] for the NPG method with adaptive step sizes which is a particular case of the PMD class of methods. The present work extends somehow this result with adaptive step sizes which are independent on the minimal sub-optimality gap, using a different analysis (as discussed in l. 237 to 253). The extension to the inexact setting follows the same lines as prior work [7]. **Minor:** - l. 174: The function $h$ is continuously differentiable on the relative interior of the simplex $\Delta(\mathcal{A})$, so I guess $\pi'$ belongs to the relative interior of $\Delta(\mathcal{A})$. **Typos:** - l. 184: mirror map h -> $h$ - Eq. (4) (and Eq. (9)): $p \in \Delta(\mathcal{A})$ and then $p_s$ is used in the argmin.

Questions

1. How easy is it to compute the adaptive step sizes in (5)? Is there any computational tradeoff? The step sizes seem to potentially involve dependence on the state/action space sizes and would require some computational efforts to be computed. For instance, computing the set $\mathcal{A}_s^k$ requires screening the action space. Could you comment on this and compare to the step sizes in [7] regarding this aspect? 2. Does Theorem 4.3 about adaptive step-size necessity only hold for the particular case of the negative entropy for $h$ unlike all other results which hold for the general class of PMD methods? Could you comment on the reasons for that? 3. In Eq. (8), is the definition of $\tilde{\pi}_{s_i}^{k_i + 1}$ the same as in (5)? What are the states ${s_i}$ in l. 289?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

The suboptimality in terms of the dependence on $1/(1-\gamma)$ (which does not match the known lower bound) is discussed both in l. 330-332 and in the conclusion.

Summary

The paper studies the convergence rate of Policy Mirror Descent. The authors prove a $\gamma$-rate for exact PMD update and a matching lower bound for this class of algorithm. Then they prove a sample complexity bound of $O(\epsilon^{-2}(1-\gamma)^{-8})$.

Strengths

The paper analyses an interesting problem on the convergence rate for a general class of RL algorithms. The work is nicely structured and the theoretical results seems not trivial to obtain.

Weaknesses

In the reviewer's opinion the paper does not convey clearly the contribution of the paper. More specifically it's hard to understand if the paper advances theoretically the field of RL or just the theoretical understanding of PMD. Minor: The following sentence in the abstract: "Motivated by the instability of policy iteration (PI) with inexact policy evaluation, unregularised PMD algorithmically regularises the policy improvement step of PI without regular5 ising the objective function" sounds convoluted and maybe even grammatically incorrect. Please have a look

Questions

1) A lower bound on a class of algorithm and not on the problem seems strange. Could please the author elaborate on this point? Is this standard in RL literature? 2) The terminology: Unregularized PMD is not explicitly explained in text. It would be helpful to clarity it explicitly.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

1: Your assessment is an educated guess. The submission is not in your area or the submission was difficult to understand. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

yes

Response

Thank you very much for your rebuttal and most of my concerns have been addressed. However, the optimality in Theorem 4.2 still feels questionable to me. In particular, if I didn't make any mistake, PI can converge within finite number of iterations mainly because we only have finite number of deterministic policies in a tabular MDP. Nevertheless, the number of policies scales in an order of $A^S$, which is much larger than the number of iterations guaranteed in Theorem 4.2, where $n$ is close to the number of states. That is, even though PI can achieve the optimal policy within finite number of iterations, this number of iterations may be much larger than $n$. Meanwhile, just as shown in your additional experiments, potential super-linear convergence is possible when the number of iterations is large. Therefore, although I acknowledge that Theorem 4.2 is a valuable result, whether it really captures the optimality of PMD still remains questionable for me.

post rebuttal

I thank the authors for their detailed responses to my questions and relevant clarifications as well as their additional experiments which illustrate in practice the behavior of the adaptive steps on the hard provided instance. I also went through the other reviews and responses and I maintain my original positive score.