Markov Models: Chains, Rewards, and Decisions

From Randomness to Agency: A Hierarchy of Models

At its heart, this course is about making optimal decisions in environments that evolve over time, partly in response to our choices and partly due to inherent randomness. To model this, we'll build up our framework in three stages.

1. Markov Chain (or Markov Process): The foundation, modeling only random state changes.
2. Markov Reward Process: Adds a notion of "value" or "desirability" to the states.
3. Markov Decision Process: Adds an agent with the ability to choose actions, influencing both transitions and rewards.

Let's explore each of these in turn.

1. Markov Chains: Modeling the Environment's Dynamics

The simplest model we'll consider is the Markov Chain, also known as a Markov Process. It describes a system that moves between different states randomly over time. The crucial assumption is that the system is "memoryless." This is formally known as the Markov property.

The Markov Property states that the future is independent of the past, given the present. In other words, to predict what will happen next, you only need to know the current state; the entire history of how the system arrived at that state is irrelevant.

To see a great visual explanation of this, watch the beginning of the lecture by David Silver. He introduces the concept and provides an intuitive example of a "student Markov chain."

As you saw in the video, a finite, time-stationary Markov chain is defined by two components:

• A finite set of states $S$.
• A state transition model $P$, which specifies the probability of moving from any state $s$ to any other state $s^{\prime }$, denoted $P(s^{\prime }|s)$.

These transition probabilities can be organized into a square matrix $P$, where the element $P_{s{s}^{\prime }}$ is the probability of transitioning from state $s$ to state $s^{\prime }$. Given your background in linear algebra, you'll recognize this as a row-stochastic matrix, where each row represents a probability distribution and its elements sum to 1. This matrix fully defines the dynamics of the system.

A Markov Chain answers the question: "Given the current state, what can happen next, and with what probability?" It models pure, uncontrolled stochastic evolution.

2. Markov Reward Processes: Adding Value Judgments

A Markov chain tells us how a system evolves, but it doesn't tell us whether a particular evolution is good or bad. To do that, we introduce rewards, turning our Markov chain into a Markov Reward Process (MRP).

An MRP is a Markov chain with value judgments. It tells us how much reward we accumulate as we traverse the state space. To formalize this, we add two components to our model.

Now, let's return to the video to see how rewards and the concept of "return" are added to the student example.

The video provided a great intuitive breakdown. To formalize it, an MRP is defined by a 4-tuple $(S,P,R,\gamma )$:

• $S$: A finite set of states.
• $P$: A state transition probability matrix, $P_{s{s}^{\prime }}=P(S_{t+1}=s^{\prime }|S_t=s)$.
• $R$: A reward function. In its simplest form, it's the expected immediate reward upon leaving a state $s$, denoted $R(s)=\mathbb{E}[R_{t+1}|S_t=s]$.
• $\gamma$: A discount factor, $\gamma \in [0,1]$.

The discount factor $\gamma$ is a crucial addition. It makes rewards received further in the future less valuable than rewards received now. A reward received $k$ timesteps in the future is discounted by a factor of ${\gamma }^k$. As the video discussed, this is not just a mathematical convenience to keep the sum of rewards (the return) finite; it also models real-world phenomena like economic inflation, uncertainty about the future, and the preference for immediate gratification.

The central goal in an MRP is typically to evaluate how "good" it is to be in a particular state. This is captured by the state-value function, $v(s)$, which is the expected total discounted reward, or expected return, starting from state $s$.

An MRP answers the question: "If I start in this state, what is my expected long-term reward?" It allows for the evaluation of a stochastic process, but still offers no control.

3. Markov Decision Processes: Adding Agency

We now arrive at the central object of this course: the Markov Decision Process (MDP). An MDP finally introduces an agent that can make decisions. It extends the MRP by adding a set of actions that the agent can choose from in each state. These actions influence both the state transitions and the rewards received.

Let's see how this final layer of complexity is added.

An MDP is formally defined by a 5-tuple $(S,A,P,R,\gamma )$:

• $S$: A finite set of states.
• $A$: A finite set of actions.
• $P$: A state transition probability model, where $P(s^{\prime }|s,a)$ is the probability of transitioning to state $s^{\prime }$ after taking action $a$ in state $s$.
• $R$: A reward function, where $R(s,a)$ is the expected immediate reward after taking action $a$ in state $s$.
• $\gamma$: A discount factor, $\gamma \in [0,1]$.

The key addition is the action set $A$. The agent's behavior is defined by its policy, $\pi$. A policy is a map from states to a probability distribution over actions, $\pi (a|s)$. It specifies how the agent chooses its actions.

An MDP answers the question: "In this state, what should I do to maximize my future rewards?" This is the core question of reinforcement learning.

The Key Relationship: How the Models Connect

The most important insight for distinguishing these three models is understanding how they relate to one another. An MRP is an MP with rewards. More subtly, an MDP, when combined with a fixed policy, reduces to an MRP.

Let's read a short, formal explanation of this crucial idea.

This relationship is fundamental. When you want to find the optimal way to behave in an MDP, you are searching for the best policy. But once you have a policy and want to know how good it is, you are essentially evaluating an MRP. Much of the machinery for solving MDPs involves alternating between evaluating a policy (treating the system as an MRP) and improving it.

Summary: A Side-by-Side Comparison

Let's summarize the distinctions in a table.

You can visualize the relationship as a hierarchy:

Conclusion

In this lesson, we have dissected the three foundational models that lead to the full Markov Decision Process framework. We started with the Markov Chain, a memoryless model of a system's random evolution. We then added rewards and a discount factor to create the Markov Reward Process, which allows us to evaluate the long-term value of being in different states. Finally, by introducing a set of actions and a policy for choosing them, we arrived at the Markov Decision Process, a complete framework for modeling sequential decision-making under uncertainty.

The key takeaway is this hierarchy of concepts: an MRP is an MP plus rewards, and an MDP under a fixed policy behaves exactly like an MRP.

In our next lesson, we will build on these definitions to formally specify all the components of a finite MDP in greater detail. This will prepare us for the next module, where we will begin to implement and simulate these models in Python.