# American Institute of Mathematical Sciences

July  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

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.
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

Impact Factor: