Approximating Markov decision processes using expected state transitions (Q1075954)

For discounted Markov decision processes approximative solutions are obtained when in the optimality equation the expectation is replaced by the value at the expected new state. The approximate value and the true value for the approximative policy are compared to the unknown optimal value by establishing various types of bounds using e.g. Lipschitz conditions, Taylor expansions, convexity, monotonicity, and normal approximation. These bounds are demonstrated by a random walk model and by an inventory problem.