Discrete Dynamic Programming with Sensitive Discount Optimality Criteria (Q5575236)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3292529
Language Label Description Also known as
default for all languages
No label defined
    English
    Discrete Dynamic Programming with Sensitive Discount Optimality Criteria
    scientific article; zbMATH DE number 3292529

      Statements

      Discrete Dynamic Programming with Sensitive Discount Optimality Criteria (English)
      0 references
      1969
      0 references
      operations research
      0 references
      A sequence of sensitive discount optimality criteria, unifying two criteria previously suggested by Blackwell, is introduced for both continuous and discrete time parameter finite Markov decision chains. Let \( V_{\rho}(\pi) \) denote the expected discounted reward under the policy \( \pi \) where \( \rho \) is the rate of interest. For each \( n=-1,0, \ldots \), a policy \( \pi^{*} \) is called \( n^{ \pm} \)optimal if \[ \liminf _{\rho \rightarrow 0 \pm}|\rho|^{-n_{\rho}}\left[V_{\rho}\left(\pi^{*}\right)-V_{\rho}(\pi)\right] \geq 0 \] for all \( \pi \), and \(\pm\) optimal if \( V_{\rho}\left(\pi^{*}\right)-V_{\rho}(\pi) \geq 0 \) for all \( \pi \) and all \( 0< \pm \rho<\rho^{*} \) for some \( \rho^{*}>0 \). When \( n \) is as large as the number of states, \( n^{ \pm} \)optimality is shown to be equivalent to \(\pm\) optimality. The recent policy improvement algorithm of Miller and the author for finding \(\pm\) optimal policies is refined and simplified to find \( n^{ \pm} \)optimal policies. The algorithm exploits the fact that for stationary policies the Laurent expansion about the origin of the return \( V_{p}(\cdot))\) has a simple form. Detailed properties of the coefficients of this expansion are exhibited. Resolvents of substochastic matrices play a central role in this analysis. The methods of successive approximation (Shapley) and policy improvement (Howard) are applied to finding a policy \( \pi \) maximizing \( V_{\rho}(\pi) \) for a fixed negative \( p \), provided the series defining \( V_{\rho}(\cdot) \) is absolutely convergent for all stationary policies.
      0 references

      Identifiers