In our last lesson, we constructed the formal blueprint of a Markov Decision Process, defining it as a tuple . We noted that the state space is perhaps the most crucial component, as it must encapsulate all information relevant to future decisions. Today, we will delve into the precise meaning of this requirement by exploring the Markov property.
Your objective is to learn how to determine whether a given state representation satisfies this foundational property. Understanding this concept is critical because the entire mathematical framework of MDPs—and the algorithms we'll use to solve them—rests upon it. Without the Markov property, the elegant transition function we defined would be insufficient, and the problem would become vastly more complex.
What is the Markov Property?
At its heart, the Markov property is a statement about informational sufficiency. It asserts that the current state provides a complete summary of the past. Once you know the current state, the history of how the agent arrived there offers no additional predictive power about the future.
A popular, informal way to phrase this is: "The future is independent of the past, given the present."
For an MDP, this means that the probability distribution over the next state and the next reward depends only on the current state and the current action .
Let's formalize this. Let the history at time be the entire sequence of past states and actions: . A state representation satisfies the Markov property if, for all possible histories, states, actions, and next states:
This equation is the bedrock of our ability to use the simple transition kernel that we defined in the previous lesson. If this property did not hold, our transition probabilities would need to be conditioned on the entire history , making the problem computationally intractable.
The following resources provide clear, complementary explanations of this core idea.
Constructing Markov States for Reinforcement Learning
Start reading from the beginning of Section 3. Pay close attention to the paragraphs that follow the introduction of the transition probability P(s'|s,a).
The authors provide a crisp definition of the Markov assumption in the context of an MDP. Focus on their statement about what the reward and transition probabilities do and do not depend on. The document also stresses a key insight: the Markov property is a requirement on the state representation, not a restriction on the world itself.
Markov Decision Processes Three - Georgia Tech - Machine Learning
Watch the first minute of this video from the Georgia Tech Machine Learning course.
This short clip provides a conversational and intuitive explanation of the property. Note how the transition function is simplified because it only needs to depend on the current state S and action A, not any prior states.
Why a Non-Markovian State Fails
To truly understand the property, it's best to see what happens when it's violated. A state representation is non-Markovian if some information from the past, which is not captured in the current state, is necessary to predict the future.
Consider a simple example: a robot moves on a line. Its state is its integer position, . The robot has momentum: if it just moved right, it's more likely to continue moving right.
- Let's say the action is "push," which applies a force.
- If the robot is at and it arrived there from , its velocity is +1. A "push" might result in a high probability of moving to .
- If the robot is at but arrived from , its velocity is -1. The same "push" action might now result in a high probability of moving to .
In this case, the state is not Markov. The probability of the next state depends not just on the current state and the action "push," but also on the previous state . The history matters.
State Augmentation: Restoring the Markov Property
The problem in the robot example isn't that the world is unsolvable; it's that our state representation is impoverished. We can fix this by augmenting the state to include the missing information.
If we redefine the state to be , where is the position and is the velocity, the Markov property is restored.
- If the current state is , the dynamics for the next state are fully defined. We know the robot has rightward momentum.
- If the current state is , the dynamics are also fully defined. We know it has leftward momentum.
The past (e.g., ) no longer provides any additional information. All the relevant information has been packed into our new, augmented state. The state is a sufficient statistic of the past, meaning it summarizes all the history needed to predict the future.
The following reading provides excellent, compact examples of this process.
A Guided Tour of Chapter 3: Markov Process and ...
This document uses the example of a random walk in stock prices to demonstrate the Markov property.
First, read the page titled "Markov Property - Stock Price Random Walk Process" (page 3). Note the formal definition of the Markov property and the phrase sufficient statistic. Next, review the two subsequent pages, "Another Stock Price Random Walk Process" and "Yet Another Stock Price Random Walk Process" (pages 5-6). For each one, identify: Why the simple state S_t = X_t (the price) is not Markov. What minimal state representation is proposed to restore the property. This demonstrates the art of state design: including enough information, but no more than necessary.
The key takeaway is that the Markov property is a feature of your model, not an inherent property of the world. By carefully designing the state space, we can often create a Markovian representation of a seemingly non-Markovian problem.
How to Test for the Markov Property
So, how can you determine if a proposed state representation is Markov? The fundamental test is a thought experiment based on conditional independence.
Imagine two agents who have taken different historical paths but have ended up in the exact same proposed state . If, for any action they might take, their probability distribution over future events is identical, then the state is Markov. If their different histories give them different future outlooks despite being in the same "state," then the state representation is not Markov.
A paper on applying MDPs to marketing provides an excellent analogy using baseball.
Constructing Markov States for Reinforcement Learning
Find the paragraph in Section 3 that begins "This approach is directly applicable...".
Read the explanation of the baseball example. The authors argue that a state like "runner on first, one out" is Markov only if the expected number of future runs is the same regardless of how that state was reached (e.g., a walk vs. a single). This provides a very clear conceptual test.
This idea can be extended to building more complex models, as discussed in the following video.
Markov Decision Processes - Computerphile
Watch the following segments from this engaging video on MDPs.
First, watch the brief explanation of the Markov assumption. Next, consider the example of waiting for a train starting around the waiting room. Your decision to keep waiting or go home might depend on how many times you've already had to wait. Finally, see how the speaker resolves this by discussing augmenting the state with extra information, like "how many times we've waited," and again at factoring this into the decision. This directly illustrates how to repair a non-Markovian state representation.
Conclusion
In this lesson, we have dissected the Markov property, the assumption that underpins the entire MDP framework. You now have both a formal definition and a set of practical tests to determine if a state representation is valid.
The key takeaways are:
- Definition: The Markov property states that the future is conditionally independent of the past, given the present state and action. The current state is a sufficient statistic of the history.
- A Property of the Model: The Markov property is not a feature of the world, but of the state representation we choose. We can often engineer a state space to satisfy the property.
- The Test: To check if a state is Markov, ask: "If two agents arrive at this state via different histories, do they have the exact same probability distribution over all future outcomes?" If the answer is yes, the state is Markov.
- State Augmentation: If a state is not Markov, the solution is to augment it with the necessary information from the past (e.g., velocity, time waited, items in inventory).
So far, we have focused on the environment's side of the equation: its states and dynamics. In our next lesson, we will shift our focus to the agent's behavior. We will define what a policy is and distinguish between different types, such as deterministic, stochastic, and stationary policies. This will set the stage for our ultimate goal: finding the optimal policy.