Reductive MDPs: A Perspective Beyond Temporal Horizons

2022/05/15 by Spooner, Thomas, Silva, Rui, Lockhart, Joshua +2
#Artificial Intelligence (cs.AI) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Probability (math.PR)

paper · doi:10.48550/arxiv.2205.07338

Abstract

Solving general Markov decision processes (MDPs) is a computationally hard problem. Solving finite-horizon MDPs, on the other hand, is highly tractable with well known polynomial-time algorithms. What drives this extreme disparity, and do problems exist that lie between these diametrically opposed complexities? In this paper we identify and analyse a sub-class of stochastic shortest path problems (SSPs) for general state-action spaces whose dynamics satisfy a particular drift condition. This construction generalises the traditional, temporal notion of a horizon via decreasing reachability: a property called reductivity. It is shown that optimal policies can be recovered in polynomial-time for reductive SSPs -- via an extension of backwards induction -- with an efficient analogue in reductive MDPs. The practical considerations of the proposed approach are discussed, and numerical verification provided on a canonical optimal liquidation problem.

Related

• Computational Approaches for Stochastic Shortest Path on Succinct MDPs
• Stochastic Shortest Paths and Weight-Bounded Properties in Markov\n Decision Processes
• A Fully Polynomial Time Approximation Scheme for Constrained MDPs and Stochastic Shortest Path under Local Transitions
• Speeding Up Planning in Markov Decision Processes via Automatically Constructed Abstractions
• Reversible Markov decision processes and the Gaussian free field