Welcome to your next lesson on the formal foundations of Markov Decision Processes. In our previous session, we focused on the agent's decision-making logic, defining what a policy is and distinguishing between deterministic, stochastic, stationary, and time-dependent types. We now have all the necessary components in place: the environment's dynamics, described by the MDP's transition probabilities, and the agent's behavior, described by its policy.
This lesson brings these two pieces together. We will investigate what happens when an agent executes a policy within an MDP over a sequence of time steps. This sequence of states and actions is known as a trajectory. Our goal is to learn how to compute the probability of any given finite trajectory. Understanding this is fundamental, as it forms the basis for evaluating policies and, ultimately, for finding the best policy.
From Rules to Reality: The Trajectory
When an agent follows a policy within an MDP, it generates a sequence of states and actions that unfolds over time. This sequence, often denoted by the Greek letter (tau), is called a trajectory or a history. A trajectory starting at time looks like this:
where is the state at time and is the action taken at time .
Since both the environment's transitions and potentially the agent's policy can be stochastic, this trajectory is a random sequence. Our objective is to determine the probability of a specific, finite-length trajectory, say .
The Ingredients of Trajectory Probability
To calculate the probability of a trajectory, we need to combine three key probabilistic elements we've already discussed:
- The Initial State Distribution (): The process must begin in some state. The MDP specifies an initial state distribution, , which gives the probability that the starting state is .
- The Policy (): At each state , the agent selects an action . The probability of this choice is given by the policy, .
- The Transition Dynamics (): After the agent takes action in state , the environment moves to a new state . The probability of this transition is given by the dynamics model, .
Assembling the Probability with the Chain Rule
Given your background in probability, you'll recognize that we can combine these elements using the chain rule of probability. Let's build the probability of a trajectory step by step.
Consider a very short trajectory consisting of just the first state, action, and next state: . The joint probability can be factored as:
Let's map our three ingredients to these terms:
- is simply the initial state probability, .
- is precisely the agent's policy, .
- is the environment's transition probability, , due to the Markov property.
Putting it all together, the probability of this short sequence is:
This same logic extends to a trajectory of any finite length. By repeatedly applying the chain rule, we find that the probability of a trajectory is the product of the probabilities of each event in the sequence.
The following reading provides a rigorous derivation of this result. It uses a slightly more general notation that allows for time-dependent policies () and histories (), but the underlying principle is exactly what we have just discussed.
These lecture notes from RLtheory.github.io formally show how the interaction between a policy and an MDP defines a probability distribution over trajectories.
Please read the section titled "Initial State Distributions, Distributions over Trajectories." Follow the derivation carefully. It uses the chain rule to break down the probability of a history H_t into the product of initial state, policy, and transition probabilities. Note how the Markov property and the definition of a policy are used to simplify the conditional probabilities at each step. The final equations for \mathbb{P}(H_t=h_t) are the key result.
As you saw in the reading, for a finite trajectory up to a certain time , the probability is a product of terms. If we consider a trajectory , and assume a stationary policy for simplicity, the probability is:
This equation is central to the analysis of MDPs. It tells us how likely any sequence of events is, given the rules of the environment and the strategy of the agent.
To reinforce this, let's look at another resource that presents the same concept, using a slightly different but common notation. Here, the initial state distribution is denoted .
Part 1: Key Concepts in RL — Spinning Up documentation
The "Spinning Up" guide from OpenAI provides a concise summary of key reinforcement learning concepts. This section gives the final formula for trajectory probability.
In the section titled "The RL Problem," focus on the part that begins "To talk about expected return..." and read down to the equation for the probability of a T-step trajectory. This gives a clear, consolidated view of the formula we just derived.
A Note on Infinite Trajectories
You might wonder about the probability of an infinitely long trajectory. As the first reading hints, this is a subtle topic. If any of the probabilities in the infinite product are less than 1, the overall probability of any single, specific infinite trajectory will be zero. This does not mean that infinite trajectories are impossible! Rather, it means that we cannot analyze them by assigning probabilities to individual outcomes. Instead, one must use the more advanced tools of measure theory to assign probabilities to sets of trajectories. For the scope of our course, we will primarily be concerned with finite trajectories or quantities derived from them, so we will not need to delve into measure theory, but it is valuable to be aware of this distinction.
Conclusion
In this lesson, we have connected the components of an MDP and a policy to understand the stochastic process they jointly define. This allowed us to derive a concrete formula for the probability of any finite sequence of states and actions.
Here are the key takeaways:
- An agent's interaction with an MDP produces a trajectory: a sequence of states and actions .
- The probability of a specific finite trajectory is the product of three factors at each step: the initial state probability, the policy probabilities, and the state transition probabilities.
- For a trajectory , this probability is given by the fundamental equation:
We now have a way to describe not just what can happen, but how likely it is to happen. The next logical question is: how "good" is a particular trajectory? To answer this, we need to introduce the concept of rewards. In our next lesson, we will define the return, which is a way of accumulating the rewards received along a trajectory, and learn to compute it for different scenarios.