Convergence of Policy Mirror Descent Beyond Compatible Function Approximation

Modern policy optimization methods roughly follow the policy mirror descent (PMD) algorithmic template, for which there are by now numerous theoretical convergence results. However, most of these either target tabular environments, or can be applied effectively only when the class of policies being optimized over satisfies strong closure conditions, which is typically not the case when working with parametric policy classes in largescale environments. In this work, we develop a theoretical framework for PMD for general policy classes where we replace the closure conditions with a strictly weaker variational gradient dominance assumption, and obtain upper bounds on the rate of convergence to the best-in-class policy. Our main result leverages a novel notion of smoothness with respect to a local norm induced by the occupancy measure of the current policy, and casts PMD as a particular instance of smooth non-convex optimization in non-Euclidean space.

Table 1: Comparison of assumptions and bounds of representative prior works for PMD with fixed step size. Columns refer to assumptions required either implicitly or explicitly by different works. VGD is implied by a natural extension of closure; see Appendix A.1 for further details. The Realizability column refers to approximate realizability, which is implied by closure conditions. The Rate column suppresses all factors other than 𝐾, and ignores error floors.

• Closure (perfect): The policy class is closed to a PMD update up to ℓ ∞ -norm error.

• Closure (approx): The policy class is closed to a PMD update up to error that depends on the sampling distribution.

• General dual with EMaP parametrization: EMaP stands for Exact Mirror and Project; in these works the policy class is induced by a general dual variable parametrization, combined with an operator that performs the mirror and project steps accurately. Paper VGD Π Convexity Realizability Closure Parametric Assumptions Rate Xiao (2022); Lan (2023) Yes No a Yes Yes (perfect) Tabular 1/𝐾 Yuan et al. (2023) Yes b No Yes Yes (approx) Log-linear 1/𝐾 Ju & Lan (2022) c Yes No Yes Yes (perfect) General dual w/ EMaP 1/ √ 𝐾 Alfano et al. (2023) Yes No Yes Yes (approx) General dual w/ EMaP 1/𝐾 This Work d Yes Yes e No No No 1/𝐾 2/3 a Prior works on the tabular setting typically assume the policy class is complete Π = Δ(A) S , and thus convex. However their arguments extend to the case that Π satisfies perfect closure, which eliminates the need for Π being convex. b We refer to the bounds obtained by Yuan et al. (2023) subject to bounded approximation error. Yuan et al. (2023) also obtain convergence subject to bounded transfer error -it is unclear to what extent (if at all) bounded transfer error implies VGD. c Ju & Lan (2022) also obtain an 𝑂 (1/𝐾) rate for regularized PMD. d We report our rate for Euclidean PMD. More generally, our bounds depend on the smoothness of the action regularizer, and dependence on 𝐾 degrades for non-Euclidean regularizers such as negative entropy. e Assuming only VGD without closure, our analysis requires convexity of Π. However, in the presence of closure assumptions such as those of Alfano et al. (2023), our analysis does not require convexity of Π (see Appendix A.2 for further details).