Recently, some work has been done planning and learning in Non-Markovian Decision Processes, that is, decision-making with temporally extended rewards. In these settings, a particular reward is received only when a particular temporal logic formula is satisfied (LTL or CTL formula). However, i cannot find any work about learning which rewards correspond to which temporally extended behavior.
In my searches, i came across k-order MDPs (which are non-Markovian). I did not find RL research done on k-order MDPs.
I think that people often do not mention that they are using k-order MDPs because you can reduce it to a standard MDP. You can basically do so by letting a state depend not only on the current observation, but also on previous observations. DeepMind's DQN, for example, is effectively a 4-order MDP because a state does not only consist of the current frame, but of the last 4 frames. In general, if you want to represent a transition probability function of the form p(s | a, s1, ..., sk), you can reduce this to a markovian transition probability function by considering k-tuples of states. Your transition probability function then looks like p((s, s1, ..., sk-1) | a, (s1, ..., sk)) where (s, s1, ..., sk-1) and (s1, ..., sk) are just states (k-tuples) of another MDP.
Thanks, Nico. I suspected something like that, and your formal explanation confirms it.
Your answer related to k-order MDPs, but there is still the case of learning LTL-like specifications for rewards. I've not yet come across such work. There are methods for learning Finite and Büchi (infinite) Automata, but i haven't come across such work in the area of MDPs/RL.
- Badges
- Science topic
- Similar topics
- Psychology
- Mental Processes
- Learning