The existence of good Markov strategies for decision processes with general payoffs (Q1092823)

For countable-state stochastic dynamic programming problems and a rather general class of reward structures it is shown that randomized Markov strategies are as good as general strategies. Under additional boundedness and convexity assumptions non-randomized Markov strategies are sufficient. The general class of strategies includes the classical cases of total and average expected rewards as well as rewards of product form and lim inf form.