Answers.Body: <p>Hi Hunnam and welcome to our community!</p>
  
  <blockquote>
    <p>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. </p>
  </blockquote>
  
  <p>No this is not exactly correct.<br>
  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.</p>
  
  <p>Note that the state isn't necessarily the observations. As you point out in the next paragraph:</p>
  
  <blockquote>
    <p>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 . </p>
  </blockquote>
  
  <p>At times we can use the history to represent the state. The history can be a series of observations.</p>
  
  <blockquote>
    <p>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. </p>
  </blockquote>
  
  <p>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.</p>
  
  <p>Perhaps an example of a situation where the history is necessary will help illustrate the differences.</p>
  
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-03T18:42:28.243Z
Answers.Text: 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.
Answers.UserDisplayName: Hunnam 
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-03T19:08:36.777Z
Answers.Text: 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.
Answers.UserDisplayName: Dimitris Monroe
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-02T20:32:14.620Z
Answers.LastActivityDate: 2019-10-03T04:11:12.537Z
Answers.LastEditDate: 2019-10-03T04:11:12.537Z
Answers.UserDisplayName: Dimitris Monroe
Body: <p>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. </p>
  
  <p>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 <span class="math-container">$s_t = h_t = o_1a_1\dots o_{t-1}a_{t-1}o_t$</span>. 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. </p>
  
  <p>Then it seems that the future states naturally depend on the past states and the past actions as well. What am I missing?</p>
  
Tags: <machine-learning><reinforcement-learning><markov-decision-process>
Title: Markov property in maze solving problem in reinforcement learning
UserDisplayName: Hunnam 
ThreadText: # Markov property in maze solving problem in reinforcement learning
  
  (Asked by: username_0 on 2019-10-02)
  
  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?
  
  **Tags:** machine-learning, reinforcement-learning, markov-decision-process
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-10-02. Score: 3 | Accepted answer
  
  Hi username_0 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.
  
  > **Comments:**
  > **username_0**: 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.  
  > **username_1**: 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.  
  
  ---
  
  