Specifying a Finite Markov Decision Process

The Anatomy of a Finite MDP

A Markov Decision Process, in its most common form, is defined by a collection of mathematical components. A concise reading from a set of Stanford lecture notes provides an excellent formal definition of this structure.

As you saw in the reading, specifying an MDP requires us to define each of its parts. Let's examine them one by one, adding some important details and interpretations. For the remainder of this course, unless stated otherwise, we will focus on finite, stationary, infinite-horizon, discounted MDPs. This means the state and action sets are finite, the rules don't change over time, and we plan over a potentially infinite future using a discount factor.

1. State and Action Spaces ($S$ and $A$)

• The State Space $S$: This is the set of all possible situations the agent can be in. A state $s\in S$ must be Markov, meaning it summarizes all relevant information from the past. For a finite MDP, $S$ is a finite set, such as $\{s_1,s_2,\dots ,s_N\}$.
• The Action Space $A$: This is the set of all possible decisions the agent can make. For a finite MDP, $A$ is also a finite set, like $\{\text{north},\text{south},\text{east},\text{west}\}$. In many problems, the set of available actions may depend on the state, which we can denote as $A(s)\subseteq A$.

2. The Transition Kernel ($P$)

The transition kernel, or transition model, dictates the environment's dynamics. It is a function $P:S\times A\times S\to [0,1]$ that defines the probability of moving to a successor state $s^{\prime }$ after taking action $a$ in state $s$:
$P(s^{\prime }|s,a)=\mathrm{Pr}(S_{t+1}=s^{\prime }|S_t=s,A_t=a)$
For any given state-action pair $(s,a)$, the probabilities of transitioning to all possible next states must sum to one, forming a valid probability distribution:
$\forall s\in S,a\in A,{\sum }_{s^{\prime }\in S}P(s^{\prime }|s,a)=1$
Given your background in linear algebra, it's useful to think about how this is represented for a finite MDP. The entire transition kernel $P$ can be stored as a 3D tensor (or a three-dimensional array) with dimensions $|S|\times |A|\times |S|$. Each "slice" of this tensor for a fixed action $a$ is a transition matrix of size $|S|\times |S|$, just like the one we saw for Markov Chains.

3. The Reward Function ($R$)

The reward function defines the goal of the problem. It specifies the immediate value signal the agent receives. There are a few common conventions:

• The most general form depends on the full transition: $R(s,a,s^{\prime })$, representing the reward received after transitioning from state $s$ to state $s^{\prime }$ by taking action $a$.
• A more common form is the expected reward for a state-action pair, $R(s,a)$. This is the value we'll typically work with. It's the expectation of $R(s,a,s^{\prime })$ over the possible next states $s^{\prime }$:
  $R(s,a)=\mathbb{E}[R_{t+1}|S_t=s,A_t=a]={\sum }_{s^{\prime }\in S}P(s^{\prime }|s,a)R(s,a,s^{\prime })$
  This expected reward function can be represented as a matrix of size $|S|\times |A|$.

4. The Discount Factor ($\gamma$)

We introduced $\gamma \in [0,1]$ in the last lesson as a way to make future rewards less valuable than immediate ones. Let's delve deeper into the motivations for this. David Silver's lecture offers an excellent summary of why discounting is a cornerstone of the MDP framework.

To summarize the key points from the video:

• Mathematical Convenience: Using $\gamma <1$ ensures that the sum of rewards over an infinite horizon (the return) remains finite, which makes the analysis and algorithms tractable.
• Uncertainty: Discounting can implicitly model uncertainty about the future. If we don't fully trust our model's long-term predictions, it's prudent to prioritize shorter-term rewards.
• Real-World Analogs: Discounting naturally models financial settings (interest rates) and has been observed in the decision-making of both humans and animals, who often exhibit a preference for immediate gratification.

The choice of $\gamma$ fundamentally shapes the agent's behavior. A value close to 0 creates a "myopic" or short-sighted agent, while a value close to 1 creates a "far-sighted" agent that gives nearly equal weight to rewards far in the future.

5. The Initial-State Condition (${\mu }_0$)

Finally, we need to specify how the process begins. This is defined by an initial state distribution ${\mu }_0$, a probability distribution over the state space $S$.
${\mu }_0(s)=\mathrm{Pr}(S_0=s)$
In many cases, the process starts in a single, fixed state $s_0$. This is just a special case where ${\mu }_0(s_0)=1$ and ${\mu }_0(s)=0$ for all other states. For a finite MDP, ${\mu }_0$ is simply a vector of length $|S|$ whose elements are non-negative and sum to 1.

Example: Specifying a Grid World MDP

We have now defined all the abstract components. To make this concrete, let's see how these components are specified for a simple "tabular" MDP, where the states and actions are discrete and we can write down the probabilities and rewards in tables. The following video provides a perfect walkthrough.

As the video demonstrated, specifying the MDP means filling out these tables. For each state and action, we must define the probability of landing in every possible next state. For example, from state 2, if the agent chooses action 'North', it hits a wall. The rules dictate it stays in state 2 with 85% probability, and the remaining 15% is split among slipping to adjacent non-wall states. Writing this down for all state-action pairs fully specifies the transition kernel $P$. The same is done for the reward function $R$ and initial state distribution ${\mu }_0$.

Conclusion

In this lesson, we have moved from concept to formal specification. We have established that a finite, stationary, discounted MDP is fully defined by the tuple $(S,A,P,R,\gamma ,{\mu }_0)$. We broke down each component:

• The finite sets of states ($S$) and actions ($A$).
• The transition kernel ($P$), a function mapping state-action pairs to a probability distribution over next states, representable as a 3D tensor.
• The reward function ($R$), which provides the immediate value signal, often given as an expected value for each state-action pair.
• The discount factor ($\gamma$), which determines the agent's planning horizon and ensures mathematical convergence.
• The initial state distribution (${\mu }_0$), which specifies where the process begins.

This formal blueprint is the starting point for all planning algorithms. Before we can find an optimal policy, we must first be able to describe the world in this precise language.

In our next lesson, we will take a closer look at the most foundational assumption underlying this entire framework: the Markov property. We will explore what it means for a state representation to be "Markov" and why this is so critical for making MDPs a useful model of reality.