An ant system approach to Markov decision processes

In this paper, we develop an ant-system based algorithm for approximately solving large Markov decision process (MDP) problems for infinite horizon discounted cost criterion, extending the applicability of the ant-system meta-heuristic into stochastic sequential decision making problems. The algorithm inherits the spirit of the well-known policy iteration algorithm with an adaptation of the ant system into MDP settings with some modifications and extensions, while preserving the probabilistic convergence property of the ant system.