On Submodular Value Functions of Dynamic Programming

Abstract : We investigate in this paper submodular properties of the value function arrizing in complex Dynamic programming (DPs). We consider in particular DPs that include concatenation and linear combinations of standard DP operators, as well as combination of maximizations and minimizations. These DPs have many applications and interpretations, both in stochastic control (and stochastic zero-sum games as well as in the analysis of (non-controlled) discrete-event dynamic systems. The submodularity implies the monotonicity of the selectors appearing in the DP equations, which translates, in the context of stochastic control and stochastic games, to monotone optimal policies. Our work is based on the score-space approach of Glasserman and Yao.
Type de document :
Rapport
RR-2658, INRIA. 1995
Liste complète des métadonnées

https://hal.inria.fr/inria-00074031
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 14:21:24
Dernière modification le : jeudi 11 janvier 2018 - 16:40:57
Document(s) archivé(s) le : jeudi 24 mars 2011 - 13:58:45

Fichiers

Identifiants

  • HAL Id : inria-00074031, version 1

Collections

Citation

Eitan Altman, Ger Koole. On Submodular Value Functions of Dynamic Programming. RR-2658, INRIA. 1995. 〈inria-00074031〉

Partager

Métriques

Consultations de la notice

125

Téléchargements de fichiers

179