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 and 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-726. doi: 10.1214/aoms/1177704593.

[2]

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

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

show all references

References:
[1]

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

[2]

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

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[1]

Matthew Bourque, T. E. S. Raghavan. Policy improvement for perfect information additive reward and additive transition stochastic games with discounted and average payoffs. Journal of Dynamics and Games, 2014, 1 (3) : 347-361. doi: 10.3934/jdg.2014.1.347
[2]

Beatris Adriana Escobedo-Trujillo, José Daniel López-Barrientos. Nonzero-sum stochastic differential games with additive structure and average payoffs. Journal of Dynamics and Games, 2014, 1 (4) : 555-578. doi: 10.3934/jdg.2014.1.555
[3]

Beatris Adriana Escobedo-Trujillo, Alejandro Alaffita-Hernández, Raquiel López-Martínez. Constrained stochastic differential games with additive structure: Average and discount payoffs. Journal of Dynamics and Games, 2018, 5 (2) : 109-141. doi: 10.3934/jdg.2018008
[4]

Qing Liu, Armin Schikorra. General existence of solutions to dynamic programming equations. Communications on Pure and Applied Analysis, 2015, 14 (1) : 167-184. doi: 10.3934/cpaa.2015.14.167
[5]

Xiaoxi Li, Marc Quincampoix, Jérôme Renault. Limit value for optimal control with general means. Discrete and Continuous Dynamical Systems, 2016, 36 (4) : 2113-2132. doi: 10.3934/dcds.2016.36.2113
[6]

Stéphane Chrétien, Sébastien Darses, Christophe Guyeux, Paul Clarkson. On the pinning controllability of complex networks using perturbation theory of extreme singular values. application to synchronisation in power grids. Numerical Algebra, Control and Optimization, 2017, 7 (3) : 289-299. doi: 10.3934/naco.2017019
[7]

Cheng-Jie Liu, Feng Xie, Tong Yang. Uniform regularity and vanishing viscosity limit for the incompressible non-resistive MHD system with TMF. Communications on Pure and Applied Analysis, 2021, 20 (7&8) : 2725-2750. doi: 10.3934/cpaa.2021073
[8]

Guy Barles, Ariela Briani, Emmanuel Trélat. Value function for regional control problems via dynamic programming and Pontryagin maximum principle. Mathematical Control and Related Fields, 2018, 8 (3&4) : 509-533. doi: 10.3934/mcrf.2018021
[9]

Hua Chen, Jian-Meng Li, Kelei Wang. On the vanishing viscosity limit of a chemotaxis model. Discrete and Continuous Dynamical Systems, 2020, 40 (3) : 1963-1987. doi: 10.3934/dcds.2020101
[10]

Óscar Vega-Amaya, Joaquín López-Borbón. A perturbation approach to a class of discounted approximate value iteration algorithms with borel spaces. Journal of Dynamics and Games, 2016, 3 (3) : 261-278. doi: 10.3934/jdg.2016014
[11]

Renato Iturriaga, Héctor Sánchez-Morgado. Limit of the infinite horizon discounted Hamilton-Jacobi equation. Discrete and Continuous Dynamical Systems - B, 2011, 15 (3) : 623-635. doi: 10.3934/dcdsb.2011.15.623
[12]

Andrzej Nowakowski, Jan Sokolowski. On dual dynamic programming in shape control. Communications on Pure and Applied Analysis, 2012, 11 (6) : 2473-2485. doi: 10.3934/cpaa.2012.11.2473
[13]

X. X. Huang, D. Li, Xiaoqi Yang. Convergence of optimal values of quadratic penalty problems for mathematical programs with complementarity constraints. Journal of Industrial and Management Optimization, 2006, 2 (3) : 287-296. doi: 10.3934/jimo.2006.2.287
[14]

Fei Meng, Xiao-Ping Yang. Elastic limit and vanishing external force for granular systems. Kinetic and Related Models, 2019, 12 (1) : 159-176. doi: 10.3934/krm.2019007
[15]

Vladimir Gaitsgory, Alex Parkinson, Ilya Shvartsman. Linear programming based optimality conditions and approximate solution of a deterministic infinite horizon discounted optimal control problem in discrete time. Discrete and Continuous Dynamical Systems - B, 2019, 24 (4) : 1743-1767. doi: 10.3934/dcdsb.2018235
[16]

Alberto Bressan, Marco Mazzola, Hongxu Wei. A dynamic model of the limit order book. Discrete and Continuous Dynamical Systems - B, 2020, 25 (3) : 1015-1041. doi: 10.3934/dcdsb.2019206
[17]

Oliver Junge, Alex Schreiber. Dynamic programming using radial basis functions. Discrete and Continuous Dynamical Systems, 2015, 35 (9) : 4439-4453. doi: 10.3934/dcds.2015.35.4439
[18]

Eduardo Espinosa-Avila, Pablo Padilla Longoria, Francisco Hernández-Quiroz. Game theory and dynamic programming in alternate games. Journal of Dynamics and Games, 2017, 4 (3) : 205-216. doi: 10.3934/jdg.2017013
[19]

Rein Luus. Optimal control of oscillatory systems by iterative dynamic programming. Journal of Industrial and Management Optimization, 2008, 4 (1) : 1-15. doi: 10.3934/jimo.2008.4.1
[20]

Karl Kunisch, Markus Müller. Uniform convergence of the POD method and applications to optimal control. Discrete and Continuous Dynamical Systems, 2015, 35 (9) : 4477-4501. doi: 10.3934/dcds.2015.35.4477

 Impact Factor: 

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy