2
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Hunnam
    Commented Oct 3, 2019 at 18:42
  • 1
    $\begingroup$ 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. $\endgroup$
    – Dimitris Monroe
    Commented Oct 3, 2019 at 19:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .