Introduction

The second article described a state not as merely the screen visible now, but as a summary containing the history needed to judge the future. We called it the Markov property when, once the current state is known, older history provides no additional information for predicting the next state.

$$P(S_{t+1} \mid S_t) = P(S_{t+1} \mid S_1, \ldots, S_t)$$

Defining one good state is not enough to complete a reinforcement-learning problem. We must also specify which next states the agent can reach, how often each transition occurs, which rewards it receives, and which actions it can choose.

Attaching these pieces in order gives a Markov Decision Process, or MDP.

When I first encountered the term MDP, it sounded like another algorithm. I thought there was a learning method named MDP beside Q-Learning. An MDP, however, is not an algorithm for solving a problem. It is closer to a mathematical format for writing down a reinforcement-learning environment.

In a Sudoku analogy, the MDP is the puzzle sheet and its rules. Q-Learning and policy gradient are methods for solving that puzzle. Separating the problem statement from the solution makes later algorithms much less confusing.

Rather than defining an MDP all at once, this article assembles it in three stages.

1. A Markov process containing only states and transitions
2. A Markov reward process that adds rewards and a discount factor
3. A Markov decision process that adds the agent's actions

Markov Process: States Move According to Probabilities

A Markov process is also called a Markov chain. It is a stochastic process in which states satisfying the Markov property continue over time.

$$S_1, S_2, S_3, \ldots$$

We need two elements to define this process.

$$\text{Markov Process} = \langle \mathcal{S}, \mathcal{P} \rangle$$

• $\mathcal{S}$: the set of possible states
• $\mathcal{P}$: the transition probabilities between states

For example, suppose I can be in one of the following places just before leaving work.

$$\mathcal{S} = \{\text{DESK}, \text{CAFE}, \text{HOME}, \text{GYM}, \text{SLEEP}\}$$

When the current state is DESK, the probability that the next state is CAFE is written as

$$\mathcal{P}_{ss'} = P(S_{t+1}=s' \mid S_t=s).$$

$s$ is the current state and $s'$ is the next state. The prime does not create a different kind of variable; it simply points to the next position in the same state set.

With a concrete value,

$$P(S_{t+1}=\text{CAFE} \mid S_t=\text{DESK})=0.6.$$

In words: “given that the current state is DESK, the probability that the next state is CAFE is $0.6$.”

In the figure, the probabilities leaving DESK are $0.6$ for CAFE, $0.3$ for HOME, and $0.1$ for GYM. The next state must be one of these three, so the probabilities sum to $1$.

$$0.6 + 0.3 + 0.1 = 1$$

In general, the probabilities of every possible next state from current state $s$ also sum to $1$.

$$\sum_{s' \in \mathcal{S}} \mathcal{P}_{ss'} = 1$$

Collecting one such row for every current state produces a state-transition matrix.

$$\mathcal{P} = \begin{bmatrix} \mathcal{P}_{11} & \cdots & \mathcal{P}_{1n} \\ \vdots & \ddots & \vdots \\ \mathcal{P}_{n1} & \cdots & \mathcal{P}_{nn} \end{bmatrix}$$

Each row corresponds to one current state, and each column to one next state. Every row therefore sums to $1$.

There is no agent and no action yet. I do not choose whether to go from DESK to CAFE or HOME; the next state appears according to the fixed probabilities. Despite the word “process,” nothing is being learned. This is only a description of the probabilistic rule by which states follow one another.

Is a Transition Wrong If Its Probability Is Not 1?

In early reinforcement-learning examples, arrows labeled $0.6$ or $0.3$ can make the environment seem imprecise. If I pressed a HOME button, should I not simply go HOME? Why do we need a probability?

Many environments can produce different outcomes from the same current situation.

• A robot walks forward but may slide sideways on a slippery floor.
• A game character attacks but can miss with some probability.
• A recommendation system shows the same item, but the user may click or ignore it.
• The same commute can take different amounts of time depending on traffic.

A transition probability does not mean the agent is indecisive. It represents uncertainty in the environment's outcome even under the same conditions.

Not every transition must be stochastic. In a simple environment where HOME always leads to SLEEP, the probability is $1.0$. We call such a transition deterministic. It is still included in the transition-probability framework as the special case with probability $1$.

Markov Reward Process: Attaching Scores to Transitions

A Markov process tells us how states change, but not which states are good. We still have no numerical basis for deciding whether CAFE or GYM is preferable.

Adding a reward function $\mathcal{R}$ and discount factor $\gamma$ gives a Markov Reward Process, or MRP.

$$\text{MRP} = \langle \mathcal{S}, \mathcal{P}, \mathcal{R}, \gamma \rangle$$

Two new elements have appeared.

• $\mathcal{R}$: the expected immediate reward in each state
• $\gamma$: the discount factor that determines how strongly future rewards affect the present

Following the notation in David Silver's lecture, the reward function of state $s$ is

$$\mathcal{R}_s = \mathbb{E}[R_{t+1} \mid S_t=s].$$

Read this as “the average reward received next when the current state is $s$.”

Expectation can look excessive in an environment where a reward is always the same number. But even in the same CAFE state, the wait may be short or an order may be wrong. Actual rewards can vary, so the reward function records what we receive on average over repeated experience.

The return from the first article appears again here.

$$G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots$$

In an MRP, the state sequence follows transition probabilities and rewards accumulate along that path. Even from the same DESK state, one day may pass through CAFE on the way HOME, while another may go directly to GYM. The actual return can therefore differ between episodes.

We do not yet calculate the average return of a state. That average is the value, the subject of the next article. For now, remember that an MRP describes where states move and which rewards appear along those transitions.

Why Reward Notation Differs Between Sources

Reinforcement-learning materials write the reward function in several forms.

$$\mathcal{R}(s), \qquad \mathcal{R}(s,a), \qquad \mathcal{R}(s,a,s')$$

Some define reward using only the current state. Others include the state and action, or the next state as well.

In a maze that gives $-1$ for hitting a wall, it is natural to describe the reward by “which action was taken and where the agent arrived” rather than by the current state alone. If simply remaining in a state determines the score, $\mathcal{R}(s)$ is enough.

Different notation does not describe different kinds of reinforcement learning. It only makes a different amount of the reward's conditioning explicit. Following David Silver's lectures, this series uses $\mathcal{R}_s$ for an MRP and $\mathcal{R}_s^a$ for an MDP.

Markov Decision Process: Adding the Agent's Choice

Now we add the final piece, actions. Adding an action set $\mathcal{A}$ from which the agent can choose turns an MRP into a Markov Decision Process.

$$\text{MDP} = \langle \mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma \rangle$$

In words, each symbol answers a question.

Because actions now exist, the transition probability gains another condition.

$$\mathcal{P}_{ss'}^a = P(S_{t+1}=s' \mid S_t=s, A_t=a)$$

In an MRP, the current state $s$ alone determined the next-state distribution. In an MDP, we must also know which action $a$ was selected.

The reward function includes the action in the same way.

$$\mathcal{R}_s^a = \mathbb{E}[R_{t+1} \mid S_t=s, A_t=a]$$

In words: “the average reward received next after taking action $a$ in state $s$.”

From the same DESK state, I can choose to study, go home, or work out. This choice is why the word “Decision” appears in the name.

Do not confuse an action with a next state. Even after selecting the action “go to GYM,” a blocked road or sudden closure might produce the next state HOME. The action is chosen by the agent. The next state is the outcome produced by the environment according to its transition probabilities.

Comparing MP, MRP, and MDP in One Table

Collecting the components we added one at a time makes the structure clearer.

Rather than memorizing the long names, it is easier to think of them as

$$\text{MP} \xrightarrow{+\mathcal{R},\,\gamma} \text{MRP} \xrightarrow{+\mathcal{A}} \text{MDP}.$$

Attaching scores to state transitions gives an MRP. Adding the right to choose gives an MDP.

Fixing a Policy Turns an MDP Back into an MRP

The first article defined policy $\pi(a \mid s)$ as the probability of choosing action $a$ in state $s$.

$$\pi(a \mid s) = P(A_t=a \mid S_t=s)$$

An MDP leaves several actions open. Once we fix a policy, we determine the proportion with which the agent chooses them—for example, STUDY with probability $0.6$, LEAVE with $0.3$, and WORK OUT with $0.1$ at DESK.

We can then replace the action-specific probabilities with one transition probability mixed by the policy.

$$\mathcal{P}_{ss'}^{\pi} = \sum_{a \in \mathcal{A}} \pi(a \mid s) \mathcal{P}_{ss'}^a$$

Read the right side in this order.

1. Take the probability $\pi(a \mid s)$ that the policy selects action $a$.
2. Multiply it by the probability $\mathcal{P}_{ss'}^a$ of reaching $s'$ after that action.
3. Sum over every possible action.

We can average rewards in the same way according to the policy's action frequencies.

$$\mathcal{R}_s^{\pi} = \sum_{a \in \mathcal{A}} \pi(a \mid s) \mathcal{R}_s^a$$

Thus, after fixing one policy in an MDP, the rule for the agent's choices is set and the resulting sequence of states and rewards can be viewed as one MRP.

This relationship matters because it turns policy evaluation into value calculation in an MRP. The question “how good is it to keep following this policy?” becomes the question of calculating the expected return in the MRP induced by the policy. The next article continues with that calculation.

Describing an MDP Does Not Mean Knowing Its Transition Matrix

Writing an MDP as $\langle \mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma \rangle$ does not mean that the agent initially knows every number in $\mathcal{P}$ and $\mathcal{R}$.

In an environment with completely specified rules, such as a board game, transitions and rewards may be known in advance. We then say that the environment model is known. Dynamic programming begins with this assumption.

For a real robot or a game run for the first time, the agent may not know which outcomes its actions produce before trying them. The environment can still be represented as an MDP; the agent simply does not know that MDP's transitions and rewards.

Keep the distinctions clear.

• MDP: What states, actions, transitions, and rewards structure the environment?
• Model-based status: Does the agent know or learn the transition and reward rules?
• RL algorithm: How does it use unknown information and experience to find a policy?

The existence of a problem structure and the solver's knowledge of its numbers are separate matters.

Terminal States and Processes That Never End

Reinforcement-learning environments can be divided into episodic tasks with an ending and continuing tasks that keep running.

A game, maze escape, or completed order has a clear ending, so we define a terminal state. In the example above, SLEEP could mark the end of a day. Reaching the terminal state ends the episode, and the next episode begins from a new starting state.

A temperature-control system or continuously moving robot may run indefinitely. Such settings often use discounted returns with $\gamma<1$ to keep the sum of rewards from growing without bound.

A terminal state is sometimes represented as an absorbing state that transitions to itself with probability $1$.

$$P(S_{t+1}=s_{\text{terminal}} \mid S_t=s_{\text{terminal}})=1$$

The episode has already ended in practice. Mathematically, the self-loop keeps the row of transition probabilities summing to $1$.

Common Points of Confusion

An MDP Is Not a Reinforcement-Learning Algorithm

An MDP is a format for expressing the problem. Keep it separate from methods such as Q-Learning, SARSA, and policy gradient that find a good policy.

An Action Does Not Necessarily Determine the Next State

The agent selects an action, but the environment's outcome may be stochastic. The same $(s,a)$ can produce different $s'$ and rewards.

Reward and Value Are Different

A reward is a number received one step later. A value is the average future return expected when starting from a state. Writing $R=+2$ beside a state in this article does not mean that the state's value is $+2$.

“Markov” Does Not Mean That the Past Was Never Needed

History may be used to construct a state. The property says that after a sufficient state has been constructed, the next transition and reward can be expressed conditional on that state.

What to Remember

The central idea of this article is

An MDP is the problem statement of reinforcement learning: it records which actions an agent can choose in each state and the probabilities with which next states and rewards follow.

More specifically:

1. A Markov process represents stochastic state transitions as $\langle \mathcal{S}, \mathcal{P} \rangle$.
2. An MRP adds rewards and a discount factor: $\langle \mathcal{S}, \mathcal{P}, \mathcal{R}, \gamma \rangle$.
3. An MDP adds actions: $\langle \mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma \rangle$.
4. Even after an action is selected, the next state and reward may vary stochastically.
5. Fixing a policy lets us view the resulting state and reward sequence in an MDP as an MRP.
6. Defining an MDP is different from the agent knowing its transition and reward numbers.

All ingredients of the reinforcement-learning problem are now present. But we still do not know which of DESK, CAFE, and HOME is better in the long run. Comparing immediate rewards alone can miss distant consequences.

The next article distinguishes reward, return, and value, then examines the questions answered by the state value $v(s)$ and action value $q(s,a)$. This is where reinforcement learning begins to predict the future in earnest.

References

• David Silver, UCL Reinforcement Learning Course
• David Silver, Lecture 2: Markov Decision Processes
• Google DeepMind, RL Course by David Silver - Lecture 2
• Seoul National University DSBA Lab, Introduction of Reinforcement Learning
• Sutton & Barto, Reinforcement Learning: An Introduction, 2nd Edition