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]

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

Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021
[3]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023
[4]

Xinyuan Liao, Caidi Zhao, Shengfan Zhou. Compact uniform attractors for dissipative non-autonomous lattice dynamical systems. Communications on Pure & Applied Analysis, 2007, 6 (4) : 1087-1111. doi: 10.3934/cpaa.2007.6.1087
[5]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[6]

Simone Cacace, Maurizio Falcone. A dynamic domain decomposition for the eikonal-diffusion equation. Discrete & Continuous Dynamical Systems - S, 2016, 9 (1) : 109-123. doi: 10.3934/dcdss.2016.9.109
[7]

Thomas Alazard. A minicourse on the low Mach number limit. Discrete & Continuous Dynamical Systems - S, 2008, 1 (3) : 365-404. doi: 10.3934/dcdss.2008.1.365
[8]

Jon Aaronson, Dalia Terhesiu. Local limit theorems for suspended semiflows. Discrete & Continuous Dynamical Systems - A, 2020, 40 (12) : 6575-6609. doi: 10.3934/dcds.2020294
[9]

M. Mahalingam, Parag Ravindran, U. Saravanan, K. R. Rajagopal. Two boundary value problems involving an inhomogeneous viscoelastic solid. Discrete & Continuous Dynamical Systems - S, 2017, 10 (6) : 1351-1373. doi: 10.3934/dcdss.2017072
[10]

Fritz Gesztesy, Helge Holden, Johanna Michor, Gerald Teschl. The algebro-geometric initial value problem for the Ablowitz-Ladik hierarchy. Discrete & Continuous Dynamical Systems - A, 2010, 26 (1) : 151-196. doi: 10.3934/dcds.2010.26.151
[11]

Xianchao Xiu, Ying Yang, Wanquan Liu, Lingchen Kong, Meijuan Shang. An improved total variation regularized RPCA for moving object detection with dynamic background. Journal of Industrial & Management Optimization, 2020, 16 (4) : 1685-1698. doi: 10.3934/jimo.2019024
[12]

Yuncherl Choi, Taeyoung Ha, Jongmin Han, Sewoong Kim, Doo Seok Lee. Turing instability and dynamic phase transition for the Brusselator model with multiple critical eigenvalues. Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021035
[13]

Xianming Liu, Guangyue Han. A Wong-Zakai approximation of stochastic differential equations driven by a general semimartingale. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2499-2508. doi: 10.3934/dcdsb.2020192
[14]

J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008
[15]

Fernando P. da Costa, João T. Pinto, Rafael Sasportes. On the convergence to critical scaling profiles in submonolayer deposition models. Kinetic & Related Models, 2018, 11 (6) : 1359-1376. doi: 10.3934/krm.2018053
[16]

Alberto Bressan, Carlotta Donadello. On the convergence of viscous approximations after shock interactions. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 29-48. doi: 10.3934/dcds.2009.23.29
[17]

Caifang Wang, Tie Zhou. The order of convergence for Landweber Scheme with $\alpha,\beta$-rule. Inverse Problems & Imaging, 2012, 6 (1) : 133-146. doi: 10.3934/ipi.2012.6.133
[18]

Elena Bonetti, Pierluigi Colli, Gianni Gilardi. Singular limit of an integrodifferential system related to the entropy balance. Discrete & Continuous Dynamical Systems - B, 2014, 19 (7) : 1935-1953. doi: 10.3934/dcdsb.2014.19.1935
[19]

Naeem M. H. Alkoumi, Pedro J. Torres. Estimates on the number of limit cycles of a generalized Abel equation. Discrete & Continuous Dynamical Systems - A, 2011, 31 (1) : 25-34. doi: 10.3934/dcds.2011.31.25
[20]

Ademir Fernando Pazoto, Lionel Rosier. Uniform stabilization in weighted Sobolev spaces for the KdV equation posed on the half-line. Discrete & Continuous Dynamical Systems - B, 2010, 14 (4) : 1511-1535. doi: 10.3934/dcdsb.2010.14.1511

 Impact Factor: 

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences