Memory of the past is required whenever failures and/or inadequacy arise in the perception layer of the robot thus affecting significantly its current representation of the world, forcing eventually to apply some sort of backtracking strategies.
Quoting S.D Whitehead and Long-Ji Lin in their paper "Reinforcement learning of non-Markov decision processes":
These non-Markov tasks are commonly referred to as hidden state tasks, since they occur whenever it is possible for a relevant piece of information to be hidden (or missing) from the agent’s representation of the current situation.
Hidden state tasks arise naturally in the context of autonomous learning robots. The simplest example of a hidden state task is one which occurs when the agent’s sensors are inadequate for the task at hand. Suppose a robot is charged with the task of sorting blocks into bins according to their color, say Bin-l for red, Bin-2 for blue. If the robot’s sensors are unable to distinguish red from blue, then for any given block it can do no better than guess a classification. If there are an equal number of blocks of each color, then guessing can do no better than chance. On the other hand, if the robot can detect color, it can easily learn to achieve 100% performance. The former case corresponds to a non-Markov decision problem, since relevant information is missing from the agent’s representation. The latter case is Markov since once a color sense is available the information needed to achieve optimal performance is always available. In general, if a robot’s internal representation is defined only by its immediate sensor readings, and if there are circumstances in which the sensors do not provide all the information needed to uniquely identify the state of the environment with respect to the task, then the decision problem is non-Markov.
