Non-Markovian Rewards Expressed in LTL: Guiding Search Via Reward Shaping

Proceedings of the International Symposium on Combinatorial Search, 10

Volume

Vol. 10 No. 1 (2017): Tenth Annual Symposium on Combinatorial Search

Extended Abstracts

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.

10.1609/socs.v8i1.18421