3
$\begingroup$

In exercise 3.6 of the book, 'An Introduction to Reinforcement Learning' by Sutton, R. and Barto, A. They ask the following question at the very end of the chapter 3.5 (which introduces the Markov Property).

Broken Vision System: Imagine that you are a vision system. When you are first turned on for the day, an image floods into your camera. You can see lots of things, but not all things. You can't see objects that are occluded, and of course you can't see objects that are behind you.

i) After seeing that first scene, do you have access to the Markov state of the environment?

ii) Suppose your camera was broken that day and you received no images at all, all day. Would you have access to the Markov state then?

I don't quite understand what they are asking. What is the 'Markov state of the environment'?

What I've thought so far:

i) It doesn't have the Markov property, as what the state of the environment will be in the next image does not depend entirely on what is in the current image (although it may well be a good approximation). I don't quite know what that says about the Markov state of the environment though?

Or is the Markov state of the environment just all the information in the environment at that point in time? In which case it can't see occluded objects and objects not in field of view, so it doesn't have access to all that information (the state).

ii) I think its best I wait to get feedback on the first question before any kind of assumptions about answers to this second question.

Thanks, I'll be very grateful if you help me patch up my understanding of this :)

Improve this question
$\endgroup$

3 Answers 3

Reset to default
3
$\begingroup$

Here's the first, informal definition of Markov state given in that section (emphasis mine):

For example, a checkers position--the current configuration of all the pieces on the board--would serve as a Markov state because it summarizes everything important about the complete sequence of positions that led to it. Much of the information about the sequence is lost, but all that really matters for the future of the game is retained.

I won't duplicate the full formal definition, but it concludes thus:

In other words, a state signal has the Markov property, and is a Markov state, if and only if (3.5) is equal to (3.4) for all $s', r$ and histories $s_t, a_t, r_t \dots r_1, s_0, a_0$.

Note that (3.4) and (3.5) are the conditional probabilities of the next state-reward pair conditioned on the entire history (3.4) and just the current state (3.5).

Here's another useful point:

It also follows that Markov states provide the best possible basis for choosing actions. That is, the best policy for choosing actions as a function of a Markov state is just as good as the best policy for choosing actions as a function of complete histories.

If forced to wager, I'd suggest that the intent of the first question was to get the reader to reason through this definition and argue one way or the other. Example 3.5, the pole balancing problem, provides a useful skeleton:

In the pole-balancing task introduced earlier, a state signal would be Markov if it specified exactly, or made it possible to reconstruct exactly, the position and velocity of the cart along the track, the angle between the cart and the pole, and the rate at which this angle is changing (the angular velocity). In an idealized cart-pole system, this information would be sufficient to exactly predict the future behavior of the cart and pole, given the actions taken by the controller.

All to say that I think you're on the right track with an answer of "No, here's why." In particular, a single image would give no indication of prior movement.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks. So (even assuming that the environment is closed) you cannot predict the state that will be represented by the next image from the first image, since the existence and location (or even non-existence) of unseen items cannot be determined and thus how they will influence the state of the next image. With the pole-balancing example, the state signal is Markov if everything needed for future calculations is know. Going back to the vision system, it could be Markov if all the properties and physics of all the objects in the closed environment both seen and unseen were known. $\endgroup$
    – JasoonS
    Aug 25, 2016 at 13:03
  • 1
    $\begingroup$ @JasoonS Well, that's the right track, but I wouldn't use the language "cannot predict." It's that your prediction would be different if you knew the full history. Think of it this way: if you knew from prior states that a gremlin was behind the rock, you'd ascribe higher probability to the gremlin appearing in subsequent states. You could still predict its appearance given only the image of the rock, but would you ascribe the same probability? $\endgroup$
    – Sean Easter
    Aug 25, 2016 at 13:22
  • $\begingroup$ That makes sense. I wouldn't ascribe the same probability, no. I was going to say I could change it to say "cannot predict accurately", but feel slightly hesitant to say that too. The probability that a gremlin will come out from behind the stone could be 1%, and that could be an accurate probability (right?) if we know certain information about how likely a gremlin is to be behind a given stone, how often they move etc. But it may be a terrible prediction. Is such a distinction something that exists, or even should be considered? (or am I just being creative) $\endgroup$
    – JasoonS
    Aug 25, 2016 at 13:47
  • $\begingroup$ An analogy that comes to mind is a coin that may or may not be biased one way or another. Say it is either a 90% bias for heads or a 90% bias for tails, and each is equally likely. 50% chance for heads may be an accurate probability but a terrible prediction given the actual state after the first coin flip. So are accurate prediction and accurate probability two different concepts? $\endgroup$
    – JasoonS
    Aug 25, 2016 at 13:56
  • 1
    $\begingroup$ @JasoonS I think you're right to consider that distinction. Here's the hazy line I think you're brushing up against: For many problems, a model that fully adheres to the Markov property can obscure away realistic details. If you read the pole balancing example in full, you'll see that the authors note many physical details; they also say that a simplified, clearly non-Markov model performs well when treated as Markov. That's what I would guess the exercise would like you to think about: What you're obscuring away by using an assumed Markov model, and what state details can/not include. $\endgroup$
    – Sean Easter
    Aug 25, 2016 at 17:55
0
$\begingroup$

Source: Practice Quiz of Coursera Course

Answer: You have access to the Markov state in both Case 1 and 2.

Explanation: Because there is no history before the first image, the first state has the Markov property. The Markov property does not mean that the state representation tells all that would be useful to know, only that it has not forgotten anything that would be useful to know.

The case when the camera is broken is different, but again we have the Markov property. All the possible futures are the same (all white), so nothing needs to be remembered in order to predict them.

Improve this answer
$\endgroup$
-1
$\begingroup$

I had the same doubt, this is how I reasoned about it. By "Markov state of the environment" I believe the question means does the agent have any notion of how the states in the environment transition. Based on this definition the first time the agent receives an image it has no notion of transitions hence it does not have a Markov state of the environment. Please feel free to correct this post if its wrong.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ You seem not to distinguish states from transition probabilities. $\endgroup$
    – whuber ♦
    Aug 24, 2016 at 19:10
  • $\begingroup$ I am in no position to to correct you, sadly. But that does sound quite plausible. Thanks though. $\endgroup$
    – JasoonS
    Aug 24, 2016 at 19:23
  • $\begingroup$ @whuber yes I could be clearer. Perhaps this is another way to think about it. A 'markov state' is a state whose probability of being in (by an environment) depends on the environments previous state. This is essentially the definition of what it means to be 'markovian'. So I'm not sure what exactly the difference is between a 'markov state' and 'markovian' $\endgroup$
    – A.D
    Aug 24, 2016 at 19:26
  • 1
    $\begingroup$ "Markovian" means the next state of the process depends only on the current state and not on any previous states. A "Markov state" is one of the possible states of the process. "Markov state of the environment" therefore must refer to whatever aspects of the environment the authors are considering using in order to model it--it's unclear which ones. In a physically realistic model (with no forces), those would include the shapes, positions, orientations, momenta, and angular momenta of all rigid objects. They might be thinking of using less information, such as only positions and orientations. $\endgroup$
    – whuber ♦
    Aug 24, 2016 at 19:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.