General limit value in dynamic programming

Previous Article
A primal condition for approachability with partial monitoring
JDG Home
This Issue
Next Article
Local stability of strict equilibria under evolutionary game dynamics

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

General limit value in dynamic programming

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

Abstract
Related Papers

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.
[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.
[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.
[4]	S. Lippman, Criterion equivalence in discrete dynamic programming,, Operations Research, 17 (1969), 920. doi: 10.1287/opre.17.5.920.
[5]	A. P. Maitra and W. D. Sudderth, Discrete Gambling and Stochastic Games,, Springer-Verlag, (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. doi: 10.1007/BF01769259.
[7]	D. Monderer and S. Sorin, Asymptotic properties in dynamic programming,, International Journal of Game Theory, 22 (1993), 1. doi: 10.1007/BF01245566.
[8]	J. Renault, Uniform value in dynamic programming,, Journal of the European Mathematical Society, 13 (2011), 309. 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, (2012).

show all references

References:

[1]	D. Blackwell, Discrete dynamic programming,, The Annals of Mathematical Statistics, 33 (1962), 719. doi: 10.1214/aoms/1177704593.
[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.
[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.
[4]	S. Lippman, Criterion equivalence in discrete dynamic programming,, Operations Research, 17 (1969), 920. doi: 10.1287/opre.17.5.920.
[5]	A. P. Maitra and W. D. Sudderth, Discrete Gambling and Stochastic Games,, Springer-Verlag, (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. doi: 10.1007/BF01769259.
[7]	D. Monderer and S. Sorin, Asymptotic properties in dynamic programming,, International Journal of Game Theory, 22 (1993), 1. doi: 10.1007/BF01245566.
[8]	J. Renault, Uniform value in dynamic programming,, Journal of the European Mathematical Society, 13 (2011), 309. 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, (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 & 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 & 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 & 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 & 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 & Continuous Dynamical Systems - A, 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 & Optimization, 2017, 7 (3) : 289-299. doi: 10.3934/naco.2017019
[7]	Guy Barles, Ariela Briani, Emmanuel Trélat. Value function for regional control problems via dynamic programming and Pontryagin maximum principle. Mathematical Control & Related Fields, 2018, 8 (3&4) : 509-533. doi: 10.3934/mcrf.2018021
[8]	Ó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 & Games, 2016, 3 (3) : 261-278. doi: 10.3934/jdg.2016014
[9]	Renato Iturriaga, Héctor Sánchez-Morgado. Limit of the infinite horizon discounted Hamilton-Jacobi equation. Discrete & Continuous Dynamical Systems - B, 2011, 15 (3) : 623-635. doi: 10.3934/dcdsb.2011.15.623
[10]	Andrzej Nowakowski, Jan Sokolowski. On dual dynamic programming in shape control. Communications on Pure & Applied Analysis, 2012, 11 (6) : 2473-2485. doi: 10.3934/cpaa.2012.11.2473
[11]	Fei Meng, Xiao-Ping Yang. Elastic limit and vanishing external force for granular systems. Kinetic & Related Models, 2019, 12 (1) : 159-176. doi: 10.3934/krm.2019007
[12]	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 & Continuous Dynamical Systems - B, 2017, 22 (11) : 1-25. doi: 10.3934/dcdsb.2018235
[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 & Management Optimization, 2006, 2 (3) : 287-296. doi: 10.3934/jimo.2006.2.287
[14]	Oliver Junge, Alex Schreiber. Dynamic programming using radial basis functions. Discrete & Continuous Dynamical Systems - A, 2015, 35 (9) : 4439-4453. doi: 10.3934/dcds.2015.35.4439
[15]	Eduardo Espinosa-Avila, Pablo Padilla Longoria, Francisco Hernández-Quiroz. Game theory and dynamic programming in alternate games. Journal of Dynamics & Games, 2017, 4 (3) : 205-216. doi: 10.3934/jdg.2017013
[16]	Rein Luus. Optimal control of oscillatory systems by iterative dynamic programming. Journal of Industrial & Management Optimization, 2008, 4 (1) : 1-15. doi: 10.3934/jimo.2008.4.1
[17]	Karl Kunisch, Markus Müller. Uniform convergence of the POD method and applications to optimal control. Discrete & Continuous Dynamical Systems - A, 2015, 35 (9) : 4477-4501. doi: 10.3934/dcds.2015.35.4477
[18]	Giuseppe Maria Coclite, Lorenzo di Ruvo, Jan Ernest, Siddhartha Mishra. Convergence of vanishing capillarity approximations for scalar conservation laws with discontinuous fluxes. Networks & Heterogeneous Media, 2013, 8 (4) : 969-984. doi: 10.3934/nhm.2013.8.969
[19]	Zhigang Wang. Vanishing viscosity limit of the rotating shallow water equations with far field vacuum. Discrete & Continuous Dynamical Systems - A, 2018, 38 (1) : 311-328. doi: 10.3934/dcds.2018015
[20]	Thomas Strömberg. A system of the Hamilton--Jacobi and the continuity equations in the vanishing viscosity limit. Communications on Pure & Applied Analysis, 2011, 10 (2) : 479-506. doi: 10.3934/cpaa.2011.10.479

Impact Factor:

American Institute of Mathematical Sciences