Benign Nonconvex Landscape for Policy Optimization: Infinite-Horizon Discounted MDPs with General State and Action Spaces
Abstract
We study the optimization landscape for infinite-horizon discounted Markov decision processes (MDPs) with general state and action spaces under structured stationary policy classes. A general weighted policy-iteration approach to establishing global convergence guarantees for policy gradient methods requires closure under weighted policy improvement at every policy, a property that may fail even when the policy class contains an optimal policy. To address this issue, we propose weaker conditions that guarantee the absence of suboptimal stationary points and establish the Polyak--Lojasiewicz--Kurdyka (PLK) condition for the policy gradient objective with a finite concentrability coefficient. We also establish the PLK condition from a policy-improvement bound that holds at every state, without a concentrability assumption. Our general results encompass settings covered by the earlier framework when the common standing assumptions hold for the same policy class and parameter domain. We further verify our proposed conditions for two operations models: inventory systems with Markov-modulated demand and stochastic cash-balance problems. For both models, the Bellman equation yields approximate convexity of the Q-value functions in the action variable, with deviations controlled by the first-order stationarity measure. These estimates establish exponent-one and, under additional curvature assumptions, exponent-two PLK conditions, which, together with Lipschitz continuity of the policy gradient, imply an 𝒪(1/ε) iteration complexity and linear convergence, respectively, for projected gradient descent using exact policy gradients. To the best of our knowledge, we provide the first non-asymptotic convergence rates for solving infinite-horizon discounted inventory systems with Markov-modulated demand and stochastic cash-balance problems using policy gradient methods.
Related
- Horizon-Independent Contraction for Continuous-Time Discounted Regularized Mean-Field Games
- Ordinary Nonconvex SGD under Distance-Dependent Moments: Finite-Horizon Stationarity and Nagaev Bounds
- Horizon saddle connections and Veech groups of infinite-type dilation surfaces
- Fully Coupled Nonlinear Forward-Backward Stochastic Difference Equations: Spectral Contraction and Infinite-Horizon Maximum Principle
- Optimal Resource Extraction under Distribution Learning and Infinite-Horizon Stochastic Hamilton--Jacobi Equations
BibTeX
@misc{chen2026benign,
title = {{Benign Nonconvex Landscape for Policy Optimization: Infinite-Horizon Discounted MDPs with General State and Action Spaces}},
author = {Xin Chen and Minda Zhao},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.21433},
eprint = {2609.21433},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.21433},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - Benign Nonconvex Landscape for Policy Optimization: Infinite-Horizon Discounted MDPs with General State and Action Spaces
AU - Xin Chen
AU - Minda Zhao
PY - 2026
DA - 2026/09/18
PB - arXiv
DO - 10.48550/arxiv.2609.21433
UR - https://arxiv.org/abs/2609.21433
AB - We study the optimization landscape for infinite-horizon discounted Markov decision processes (MDPs) with general state and action spaces under structured stationary policy classes. A general weighted policy-iteration approach to establishing global convergence guarantees for policy gradient methods requires closure under weighted policy improvement at every policy, a property that may fail even when the policy class contains an optimal policy. To address this issue, we propose weaker conditions that guarantee the absence of suboptimal stationary points and establish the Polyak--Lojasiewicz--Kurdyka (PLK) condition for the policy gradient objective with a finite concentrability coefficient. We also establish the PLK condition from a policy-improvement bound that holds at every state, without a concentrability assumption. Our general results encompass settings covered by the earlier framework when the common standing assumptions hold for the same policy class and parameter domain. We further verify our proposed conditions for two operations models: inventory systems with Markov-modulated demand and stochastic cash-balance problems. For both models, the Bellman equation yields approximate convexity of the Q-value functions in the action variable, with deviations controlled by the first-order stationarity measure. These estimates establish exponent-one and, under additional curvature assumptions, exponent-two PLK conditions, which, together with Lipschitz continuity of the policy gradient, imply an 𝒪(1/ε) iteration complexity and linear convergence, respectively, for projected gradient descent using exact policy gradients. To the best of our knowledge, we provide the first non-asymptotic convergence rates for solving infinite-horizon discounted inventory systems with Markov-modulated demand and stochastic cash-balance problems using policy gradient methods.
ER -