# Markov property in maze solving problem in reinforcement learning

By definition, every state in RL has Markov property, which means that the future state depends only on the current state, not the past states.

However, I saw that in some case we can define a state to be the history of observations and actions taken so far, such as $$s_t = h_t = o_1a_1\dots o_{t-1}a_{t-1}o_t$$. I think maze solving can be of that case since the current state, or the current place in a maze, clearly depends on which places the agent has been and which ways the agent has taken so far.

Then it seems that the future states naturally depend on the past states and the past actions as well. What am I missing?

Hi Hunnam and welcome to our community!

By definition, every state in RL has Markov property, which means that the future state depends only on the current state, not the past states.

No this is not exactly correct.
We can use RL to solve problems with the Markov Property exactly because the current state is a sufficient statistic of the future. In other words, the state encodes the distribution of future states.

Note that the state isn't necessarily the observations. As you point out in the next paragraph:

However, I saw that in some case we can define a state to be the history of observations and actions taken so far, such as 𝑠𝑡=ℎ𝑡=𝑜1𝑎1…𝑜𝑡−1𝑎𝑡−1𝑜𝑡 .

At times we can use the history to represent the state. The history can be a series of observations.

I think maze solving can be of that case since the current state, or the current place in a maze, clearly depends on which places the agent has been and which ways the agent has taken so far.

This isn't correct in the general case. Given a maze which you know how to solve, regardless of where you start, you know how to reach the exit. This is the markov property. Given the current position, you have enough information to make a certain and optimal decision.

Perhaps an example of a situation where the history is necessary will help illustrate the differences.

Suppose you are playing Pong. If you take a single frame, it doesn't contain enough information to know the direction of the ball. Therefore the observations alone are insufficient. What if you remember the previous frame? Then combining the two observations gives you all the information you need in order to make an optimal move.

• Perfect answer. Thank you so much. – Hunnam Oct 3 '19 at 18:39
• I would appreciate it if you could answer one more question. When we use the history to represent the state, can the history include the rewards that have been revealed with the actions chosen thus far? I guess this is wrong by definition of MDP or reinforcement learning. – Hunnam Oct 3 '19 at 18:42
• Ideally the observation or the series of observations would encode a significant reward. I can't think of an example where knowledge of the reward is beneficial. On the contrary, having a reward be part of the state means that you have an additional dimension to explore before converging and it means you may need to discretize (turn a real number into an integer). The definition of MDPs permit any form of state, as long as it gives enough information about the future. You could add in the state a boolean that means high reward seen on the last 5 observations without keeping it. – Dimitris Monroe Oct 3 '19 at 19:08