Detecting Hidden Triggers: Mapping Non-Markov Reward Functions to Markov
This addresses a fundamental limitation in RL for practitioners by enabling optimality guarantees without requiring predefined high-level symbols, though it is incremental as it builds on existing reward machine concepts.
The paper tackled the problem of non-Markov reward functions in Reinforcement Learning by proposing a framework to map them into equivalent Markov ones using learned reward automata, achieving empirical validation in domains like Officeworld and Breakfastworld.
Many Reinforcement Learning algorithms assume a Markov reward function to guarantee optimality. However, not all reward functions are Markov. This paper proposes a framework for mapping non-Markov reward functions into equivalent Markov ones by learning specialized reward automata, Reward Machines. Unlike the general practice of learning Reward Machines, we do not require a set of high-level propositional symbols from which to learn. Rather, we learn hidden triggers, directly from data, that construct them. We demonstrate the importance of learning Reward Machines over their Deterministic Finite-State Automata counterparts given their ability to model reward dependencies. We formalize this distinction in our learning objective. Our mapping process is constructed as an Integer Linear Programming problem. We prove that our mappings form a suitable proxy for maximizing reward expectations. We empirically validate our approach by learning black-box, non-Markov reward functions in the Officeworld domain. Additionally, we demonstrate the effectiveness of learning reward dependencies in a new domain, Breakfastworld.