Error bounds for nonnegative dynamic models. (English) Zbl 0946.90106
Summary: The extension of Markov reward models to dynamic models with nonnegative matrices is motivated by practical applications, such as economic input-output, employment, or population models. This paper studies the generalization of error bound theorems for Markov reward structures to dynamic reward structures with arbitrary nonnegative matrices. Both irreducible and reducible matrices are covered. In addition, results for the stochastic case are unified and extended. First, generalized expressions are derived for average reward functions. The special normalization case is distinguished and is shown to be transformable into the stochastic case. Its interpretation is of interest in itself. Next, error bound results are studied. Under a general normalization condition, it is shown that the results for the stochastic case can be extended. Both the average case and the transient case are included. A random walk-type example is included to illustrate the results.
MSC:
| 90C40 | Markov and semi-Markov decision processes |
Keywords:
Markov chains; nonnegative matrices; average rewards; error bounds; bias terms; normalized cases; input-output modelsReferences:
| [1] | Hunter, J. H., Generalized Inverses and Their Application to Applied Probability Problems, Linear Algebra and Its Applications, Vol. 45, pp. 157–198, 1982. · Zbl 0493.15003 · doi:10.1016/0024-3795(82)90218-X |
| [2] | Lamond, B. J., and Puterman, M. L., Generalized Inverses in Discrete-Time Markov Decision Processes, SIAM Journal on Matrix Analysis and Applications, Vol. 10, pp. 118–134, 1989. · Zbl 0662.60076 · doi:10.1137/0610009 |
| [3] | Meyer, C. D., Jr., The Condition of a Finite Markov Chain and Perturbation Bounds for the Limiting Probabilities, SIAM Journal on Algebraic and Discrete Methods, Vol. 1, pp. 273–283, 1980. · Zbl 0498.60071 · doi:10.1137/0601031 |
| [4] | Van Dijk, N. M., and Puterman, M. L., Perturbation Theory for Markov Reward Processes with Applications to Queueing Systems, Advances in Applied Probability, Vol. 20, pp. 79–98, 1988. · Zbl 0642.60100 · doi:10.2307/1427271 |
| [5] | Van Dijk, N. M., Perturbation Theory for Unbounded Markov Reward Processes with Applications to Queueing, Advances in Applied Probability, Vol. 20, pp. 99–111, 1988. · Zbl 0642.60099 · doi:10.2307/1427272 |
| [6] | Van Dijk, N. M., The Importance of Bias Terms for Error Bounds and Comparison Results, Numerical Solution of Markov Chains, Edited by W. J. Stewart, Marcel Dekker, New York, New York, pp. 617–642, 1991. · Zbl 0746.60089 |
| [7] | Hinderer, K., On Approximate Solutions of Finite-Stage Dynamic Programs, Dynamic Programming and Its Applications, Edited by M. L. Puterman, Academic Press, New York, New York, pp. 289–318, 1978. |
| [8] | Schweitzer, P. J., Perturbation Theory and Finite Markov Chains, Journal of Applied Probability, Vol. 5, pp. 401–413, 1968. · Zbl 0196.19803 · doi:10.1017/S0021900200110083 |
| [9] | Whitt, W., Approximations of Dynamic Programs, Part 1, Mathematics of Operations Research, Vol. 3, pp. 231–243, 1978. · Zbl 0393.90094 · doi:10.1287/moor.3.3.231 |
| [10] | Whittle, P., Optimization Over Time: Dynamic Programming and Stochastic Control, John Wiley and Sons, Chichester, England, 1983. · Zbl 0577.90046 |
| [11] | Tijms, H. C., Stochastic Models: An Algorithmic Approach, John Wiley and Sons, New York, New York, 1994. · Zbl 0838.60075 |
| [12] | Berman, A., and Plemmons, R. J., Nonnegative Matrices in the Mathematical Sciences, Academic Press, New York, New York, 1979. · Zbl 0484.15016 |
| [13] | Gantmakher, F. R., The Theory of Matrices, Chelsea, London, England, 1959. · Zbl 0050.24804 |
| [14] | Zijm, W. H. M., Noonegative Matrices in Dynamic Programming, Mathematical Centre Tracts, Amsterdam, Holland, 1983. · Zbl 0526.90059 |
| [15] | SladkÝ, K., Bounds on Discrete Dynamic Programming Recursions, Part 1, Kybernetika, Vol. 16, pp. 526–547, 1980. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
