To the best of the knowledge, this work provides 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.
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 $\mathcal{O}(1/\epsilon)$ 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.
It is shown that the approximate value functions obtained by value iteration and LP asymptotically converge to the optimal value function, and the policies generated by policy iteration converge in value to an optimal policy.
J. Zhang, Saumya Sinha, Mehdi Hemmati et al.· 0 citations
Combining the policy-iteration error with a quantitative soft-max approximation bound, it is shown that the iterated policies constitute weighted $\varepsilon$-equilibria for the original unregularized problem and derive an explicit regret estimate.
It is shown that, even for the covariance steering problem with a broad class of commonly used state and control safety constraints, the synthesized Markovian policy almost surely produces the same control actions as the history-dependent policy and therefore the same state trajectories, cost, and moments.
This work develops a general, statistically efficient framework for last-iterate convergence in structured Constrained MDPs (CMDPs), and validate the stabilising effect predicted by the theory on a synthetic linear CMDP: the regularised method exhibits stable last-iterate behaviour, whereas its unregularised counterpar...
Nam Phuong Tran, Trinh Ha Mai Huynh, T. P. Le et al.· 0 citations
We study the monotonicity properties of optimal policies for a class of fully/partially observable Markov decision processes (MDPs) motivated by renewable natural resource management. We first introduce a new class of deterministic monotonic MDPs with continuous state and action spaces, and we prove that their optimal...
Jun Ju, J. Filar, D.P. Kroese et al.· Operations Research Forum· 0 citations
Motivated by many application problems, we consider Markov decision processes (MDPs) with a general loss function and unknown parameters. To mitigate the epistemic uncertainty associated with unknown parameters, we take a Bayesian approach to estimate the parameters from data and impose a coherent risk functional (with...