Non-Markovian Rewards Expressed in LTL: Guiding Search Via Reward Shaping
Alberto Rivas, Oscar Chen, Scott Sanner, Sheila A. McIlraith
2021Proceedings of the International Symposium on Combinatorial Search35 citationsDOIOpen Access PDF
Abstract
We propose an approach to solving Markov Decision Processes with non-Markovian rewards specified in Linear Temporal Logic interpreted over finite traces (LTL-f). Our approach integrates automata representations of LTL-f formulae into compiled MDPs that can be solved by off-the-shelf MDP planners, exploiting reward shaping to help guide search. Experiments with state-of-the-art UCT-based MDP planner PROST show automata-based reward shaping to be an effective method to guide search, producing solutions of superior quality, while maintaining policy optimality guarantees.
Topics & Concepts
Markov decision processLinear temporal logicAutomatonComputer scienceMarkov processTemporal logicMathematical optimizationPlannerState (computer science)Quality (philosophy)Finite-state machineTheoretical computer scienceArtificial intelligenceMathematicsAlgorithmStatisticsEpistemologyPhilosophyFormal Methods in VerificationSoftware Testing and Debugging TechniquesAdvanced Software Engineering Methodologies