American Institute of Mathematical Sciences

Advanced
July  2014, 1(3): 471-484. doi: 10.3934/jdg.2014.1.471

General limit value in dynamic programming

Jérôme Renault 1,

1. 

TSE (GREMAQ, Université Toulouse 1 Capitole and GDR 2932 Théorie des Jeux), 21 allée de Brienne, 31000 Toulouse, France

Received  December 2012 Revised  May 2013 Published  July 2014

We consider a dynamic programming problem with arbitrary state space and bounded rewards. Is it possible to uniquely define a limit value for the problem, when the ``patience" of the decision-maker tends to infinity ? We consider, for each evaluation $\theta$ (a probability distribution over positive integers) the value function $v_{\theta}$ of the problem where the weight of any stage $t$ is given by $\theta_t$, and we investigate the uniform convergence of a sequence $(v_{\theta^k})_k$ when the ``impatience" of the evaluations vanishes, in the sense that $\sum_{t} | \theta^k_{t}-\theta^k_{t+1}| \rightarrow_{k \to \infty} 0.$ We prove that this uniform convergence happens if and only if the metric space $\{v_{\theta^k}, k\geq 1\}$ is totally bounded. Moreover there exists a particular function $v^*$, independent of the particular chosen sequence $({\theta^k})_k$, such that any limit point of such sequence of value functions is precisely $v^*$. The result applies in particular to discounted payoffs when the discount factor vanishes, as well as to average payoffs where the number of stages goes to infinity, and extends to models with stochastic transitions.
Keywords: average payoffs, vanishing impatience, Dynamic programming, uniform convergence of the values., discounted payoffs, limit value, general evaluations.
Mathematics Subject Classification: Primary: 90C39, 49L20; Secondary: 90C4.
Citation: Jérôme Renault. General limit value in dynamic programming. Journal of Dynamics & Games, 2014, 1 (3) : 471-484. doi: 10.3934/jdg.2014.1.471
References:
[1]

D. Blackwell, Discrete dynamic programming,, The Annals of Mathematical Statistics, 33 (1962), 719.  doi: 10.1214/aoms/1177704593.  Google Scholar

[2]

E. Lehrer and D. Monderer, Discounting versus averaging in dynamic programming,, Games and Economic Behavior, 6 (1994), 97.  doi: 10.1006/game.1994.1005.  Google Scholar

[3]

E. Lehrer and D. Monderer, A uniform tauberian theorem in dynamic programming,, Mathematics of Operations Research, 17 (1992), 303.  doi: 10.1287/moor.17.2.303.  Google Scholar

[4]

S. Lippman, Criterion equivalence in discrete dynamic programming,, Operations Research, 17 (1969), 920.  doi: 10.1287/opre.17.5.920.  Google Scholar

[5]

A. P. Maitra and W. D. Sudderth, Discrete Gambling and Stochastic Games,, Springer-Verlag, (1996).  doi: 10.1007/978-1-4612-4002-0.  Google Scholar

[6]

J.-F. Mertens and A. Neyman, Stochastic games,, International Journal of Game Theory, 10 (1981), 53.  doi: 10.1007/BF01769259.  Google Scholar

[7]

D. Monderer and S. Sorin, Asymptotic properties in dynamic programming,, International Journal of Game Theory, 22 (1993), 1.  doi: 10.1007/BF01245566.  Google Scholar

[8]

J. Renault, Uniform value in dynamic programming,, Journal of the European Mathematical Society, 13 (2011), 309.  doi: 10.4171/JEMS/254.  Google Scholar

[9]

J. Renault and X. Venel, A distance for probability spaces, and long-term values in Markov Decision Processes and Repeated Games,, preprint, (2012).   Google Scholar

show all references

References:
[1]

D. Blackwell, Discrete dynamic programming,, The Annals of Mathematical Statistics, 33 (1962), 719.  doi: 10.1214/aoms/1177704593.  Google Scholar

[2]

E. Lehrer and D. Monderer, Discounting versus averaging in dynamic programming,, Games and Economic Behavior, 6 (1994), 97.  doi: 10.1006/game.1994.1005.  Google Scholar

[3]

E. Lehrer and D. Monderer, A uniform tauberian theorem in dynamic programming,, Mathematics of Operations Research, 17 (1992), 303.  doi: 10.1287/moor.17.2.303.  Google Scholar

[4]

S. Lippman, Criterion equivalence in discrete dynamic programming,, Operations Research, 17 (1969), 920.  doi: 10.1287/opre.17.5.920.  Google Scholar

[5]

A. P. Maitra and W. D. Sudderth, Discrete Gambling and Stochastic Games,, Springer-Verlag, (1996).  doi: 10.1007/978-1-4612-4002-0.  Google Scholar

[6]

J.-F. Mertens and A. Neyman, Stochastic games,, International Journal of Game Theory, 10 (1981), 53.  doi: 10.1007/BF01769259.  Google Scholar

[7]

D. Monderer and S. Sorin, Asymptotic properties in dynamic programming,, International Journal of Game Theory, 22 (1993), 1.  doi: 10.1007/BF01245566.  Google Scholar

[8]

J. Renault, Uniform value in dynamic programming,, Journal of the European Mathematical Society, 13 (2011), 309.  doi: 10.4171/JEMS/254.  Google Scholar

[9]

J. Renault and X. Venel, A distance for probability spaces, and long-term values in Markov Decision Processes and Repeated Games,, preprint, (2012).   Google Scholar

[1]

Tengfei Yan, Qunying Liu, Bowen Dou, Qing Li, Bowen Li. An adaptive dynamic programming method for torque ripple minimization of PMSM. Journal of Industrial & Management Optimization, 2021, 17 (2) : 827-839. doi: 10.3934/jimo.2019136
[2]

Mahdi Karimi, Seyed Jafar Sadjadi. Optimization of a Multi-Item Inventory model for deteriorating items with capacity constraint using dynamic programming. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021013
[3]

Yi-Long Luo, Yangjun Ma. Low Mach number limit for the compressible inertial Qian-Sheng model of liquid crystals: Convergence for classical solutions. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 921-966. doi: 10.3934/dcds.2020304
[4]

Shengxin Zhu, Tongxiang Gu, Xingping Liu. AIMS: Average information matrix splitting. Mathematical Foundations of Computing, 2020, 3 (4) : 301-308. doi: 10.3934/mfc.2020012
[5]

Lars Grüne, Matthias A. Müller, Christopher M. Kellett, Steven R. Weller. Strict dissipativity for discrete time discounted optimal control problems. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020046
[6]

Håkon Hoel, Gaukhar Shaimerdenova, Raúl Tempone. Multilevel Ensemble Kalman Filtering based on a sample average of independent EnKF estimators. Foundations of Data Science, 2020, 2 (4) : 351-390. doi: 10.3934/fods.2020017
[7]

Zhouxin Li, Yimin Zhang. Ground states for a class of quasilinear Schrödinger equations with vanishing potentials. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020298
[8]

George W. Patrick. The geometry of convergence in numerical analysis. Journal of Computational Dynamics, 2021, 8 (1) : 33-58. doi: 10.3934/jcd.2021003
[9]

Matania Ben–Artzi, Joseph Falcovitz, Jiequan Li. The convergence of the GRP scheme. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 1-27. doi: 10.3934/dcds.2009.23.1
[10]

Fengwei Li, Qin Yue, Xiaoming Sun. The values of two classes of Gaussian periods in index 2 case and weight distributions of linear codes. Advances in Mathematics of Communications, 2021, 15 (1) : 131-153. doi: 10.3934/amc.2020049
[11]

Elvio Accinelli, Humberto Muñiz. A dynamic for production economies with multiple equilibria. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021002
[12]

Xinfu Chen, Huiqiang Jiang, Guoqing Liu. Boundary spike of the singular limit of an energy minimizing problem. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3253-3290. doi: 10.3934/dcds.2020124
[13]

Hai-Liang Li, Tong Yang, Mingying Zhong. Diffusion limit of the Vlasov-Poisson-Boltzmann system. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2021003
[14]

Hideki Murakawa. Fast reaction limit of reaction-diffusion systems. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1047-1062. doi: 10.3934/dcdss.2020405
[15]

Jose Anderson Cardoso, Patricio Cerda, Denilson Pereira, Pedro Ubilla. Schrödinger Equations with vanishing potentials involving Brezis-Kamin type problems. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020392
[16]

Lei Yang, Lianzhang Bao. Numerical study of vanishing and spreading dynamics of chemotaxis systems with logistic source and a free boundary. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 1083-1109. doi: 10.3934/dcdsb.2020154
[17]

Yahia Zare Mehrjerdi. A new methodology for solving bi-criterion fractional stochastic programming. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020054
[18]

Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102
[19]

Pablo Neme, Jorge Oviedo. A note on the lattice structure for matching markets via linear programming. Journal of Dynamics & Games, 2020  doi: 10.3934/jdg.2021001
[20]

Ke Su, Yumeng Lin, Chun Xu. A new adaptive method to nonlinear semi-infinite programming. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021012

 Impact Factor: 

Tools

Metrics

  • PDF downloads (35)
  • HTML views (0)
  • Cited by (10)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences