Markovian systems are widely used in reinforcement learning (RL), when the successful completion of a task
depends exclusively on the last interaction between an autonomous agent and its environment. Unfortunately,
real-world instructions are typically complex and often better described as non-Markovian. In this paper we
present an extension method that allows solving partially-observable non-Markovian reward decision processes (PONMRDPs) by solving equivalent Markovian models. This potentially facilitates Markovian-based
state-of-the-art techniques, including RL, to find optimal behaviours for problems best described as PONMRDP. We provide formal optimality guarantees of our extension methods together with a counterexample
illustrating that naive extensions from existing techniques in fully-observable environments cannot provide
such guarantees.