Solving Markov Decision Processes in Metric spaces Anonymous Author(s) Affiliation

Address email We present an approximation scheme for solving Markov Decision Processes (MDPs) in which the states are embedded in a metric space. Our algorithm has log log n a time bound of Õ(n ɛ), where n is the number of states and ɛ the approximation factor. This bound is independent of the numerical size of the input and the discount factor and is hence strongly polynomial. We present the result for deterministic MDPs and discuss extensions to stochastic domains. Unlike most MDP algorithms, ours does not make local iterative updates, but uses a divide and conquer approach. It partitions the space into nested regions and considers only policies that transition between partitions through portals. A simple dynamic program over the partitioned structure then returns a near-optimal policy. Our technique is very general and is likely to give insight into related problems like Reinforcement Learning and Partially Observable MDPs. In fact, using our algorithm in conjunction with a result from [1], we show a strongly polynomial reinforcement learning algorithm for metric MDPs.