An Approximate Stochastic Annealing algorithm for finite horizon Markov decision processes

We present a simulation-based algorithm called Approximate Stochastic Annealing (ASA) for solving finite-horizon Markov decision processes (MDPs). The algorithm iteratively estimates the optimal policy by sampling from a sequence of probability distribution functions over the policy space. By exploiting a novel connection of ASA to the stochastic approximation method, we show that the sequence of distribution functions generated by the algorithm converges to a degenerated distribution that concentrates only on the optimal policy. Numerical examples are also provided to illustrate the algorithm.