Markov property in maze solving problem in reinforcement learning
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 =ℎ=11…−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.