On the existence of good Markov strategies

Hill, Theodore Preston

doi:10.1090/S0002-9947-1979-0517690-9

On the existence of good Markov strategies
HTML articles powered by AMS MathViewer

by Theodore Preston Hill PDF

Trans. Amer. Math. Soc. 247 (1979), 157-176 Request permission

Abstract:

In contrast to the known fact that there are gambling problems based on a finite state space for which no stationary family of strategies is at all good, in every such problem there always exist $\varepsilon$-optimal Markov families (in which the strategy depends only on the current state and time) and also $\varepsilon$-optimal tracking families (in which the strategy depends only on the current state and the number of times that state has been previously visited). More generally, this result holds for all finite state gambling problems with a payoff which is shift and permutation invariant.

References

David Blackwell, Discounted dynamic programming, Ann. Math. Statist. 36 (1965), 226–235. MR 173536, DOI 10.1214/aoms/1177700285
J. L. Doob, Stochastic processes, John Wiley & Sons, Inc., New York; Chapman & Hall, Ltd., London, 1953. MR 0058896
Lester E. Dubins and Leonard J. Savage, Inequalities for stochastic processes (how to gamble if you must), Dover Publications, Inc., New York, 1976. Corrected republication of the 1965 edition. MR 0410875
Lester E. Dubins and William D. Sudderth, An example in which stationary strategies are not adequate, Ann. Probability 3 (1975), no. 4, 722–725. MR 378098, DOI 10.1214/aop/1176996312
Lester E. Dubins and William D. Sudderth, Persistently $\varepsilon$-optimal strategies, Math. Oper. Res. 2 (1977), no. 2, 125–134. MR 456570, DOI 10.1287/moor.2.2.125

An introduction to probability theory and its applications

Paul-A. Meyer, Probability and potentials, Blaisdell Publishing Co. [Ginn and Co.], Waltham, Mass.-Toronto, Ont.-London, 1966. MR 0205288
Donald Ornstein, On the existence of stationary optimal strategies, Proc. Amer. Math. Soc. 20 (1969), 563–569. MR 253756, DOI 10.1090/S0002-9939-1969-0253756-8
Roger A. Purves and William D. Sudderth, Some finitely additive probability, Ann. Probability 4 (1976), no. 2, 259–276. MR 402888, DOI 10.1214/aop/1176996133
William D. Sudderth, On the existence of good stationary strategies, Trans. Amer. Math. Soc. 135 (1969), 399–414. MR 233595, DOI 10.1090/S0002-9947-1969-0233595-9
William D. Sudderth, On measurable gambling problems, Ann. Math. Statist. 42 (1971), 260–269. MR 282404, DOI 10.1214/aoms/1177693510