Learning Non-Markovian Reward Models in MDPs

Understand

There are situations in which an agent should receive rewards only after having accomplished a series of previous tasks.

• In other words, the reward that the agent receives is non-Markovian.
• One natural and quite general way to represent history-dependent rewards is via a Mealy machine; a finite state automaton that produces output sequences (rewards in our case) from input sequences (state/action observations in our case).
• In our formal setting, we consider a Markov decision process (MDP) that models the dynamic of the environment in which the agent evolves and a Mealy machine synchronised with this MDP to formalise the non-Markovian reward function.