Chapter 3: Finite Markov Decision Process (MDP)

1. The Agent-Environment Interaction

Before writing down any equations, let’s agree on the picture we have in mind. Reinforcement Learning is still Machine Learning, but the data does not arrive as a fixed dataset as in Supervised Learning: the agent gathers it by interacting with the world, and its actions change what it will encounter next. We therefore need to think in terms of a continuous loop of action and feedback.

The two main components of Reinforcement Learning (RL) are the Agent and the Environment.

• The environment is the world that the agent lives in and interacts withShow sidenoteThe Boundary Between Agent and Environment: This boundary is not physical (like the skin of a robot). Anything the Agent cannot change arbitrarily is considered part of the Environment (e.g., a robot’s battery level, as the Agent cannot command “Battery, become full” arbitrarily)..
• At each step (or time step), the agent perceives itself to be in a state of the environment and, based on that state, decides what it needs to doShow sidenoteAccording to [Achiam, 2018], there are two definitions we need to distinguish: state (a complete description of the world, like chess) and observation (an incomplete description, like poker). In this context, we assume descriptions are always complete, so $o = s$..

After performing an action, the agent receives a scalar reward signal (or simply reward) associated with the resulting transition. A reward need not measure the quality of the current state by itself; it may depend on the preceding state, action, and next state. Usually, it is a real number and indicates how good or bad the action or the current state is.

The agent’s goal is to maximize the cumulative reward it receives over time. We call this accumulated reward the Return.

The term “Markov” in MDP refers to the Markov property—the future depends only on the present state, not the historyShow sidenoteSutton and Barto’s also said that: “MDPs assume that regardless of the details of the agent (like torques, sensors, etc.) and regardless of the goal the agent is trying to achieve, any goal-directed problem can be reduced to three signals passing between the agent and its environment: a signal representing the choices made by the agent (action), a signal representing the basis on which choices are made (state), and a signal defining the agent’s goal (reward).”..

We can formalize this process as follows:

• At each time step $t$, the agent receives a representation of the environment’s state, $S_t \in \mathcal{S}$, where $\mathcal{S}$ is the set of all possible states.
• Based on $S_t$, the agent selects an Action $A_t \in \mathcal{A}(S_t)$ (note that the set of available actions may differ per state).
• One time step later (at $t+1$), the agent receives a reward $R_{t+1} \in \mathcal{R} \subset \mathbb{R}$ and finds itself in a new state $S_{t+1} \in \mathcal{S}$.

This sequence of interactions forms a trajectory. Where do $S_0$ and $A_0$ come from? We sample $S_0$ from an initial-state distribution, and then the policy selects $A_0$. This distribution matters because it changes which parts of the MDP we are likely to visit—and therefore which behavior our overall performance measure emphasizes (read more here).

In a finite MDP, the agent’s world (the environment) follows rules. These rules are probabilistic, and these rules are exactly the dynamics of the environment.

The next key point of MDPs is the Markov Property: The probability of $S_t$ and $R_t$ depends only on $S_{t-1}$ and $A_{t-1}$, not on the longer history. The current state encapsulates all information necessary to make decisions for the future.

From the dynamics $p$, we can compute other important information such as:

• State-transition probability: $$p(s' \mid s, a) = \sum_{r \in \mathcal{R}} p(s', r \mid s, a)$$
• Expected reward: The reward we expect to receive when taking action $a$ in state $s$. $$\begin{aligned} r(s, a) &= \mathbb{E}[R_{t} \mid S_{t-1} = s, A_{t-1} = a] \\ &= \sum_{r \in \mathcal{R}} r p(r \mid s, a) \\ &= \sum_{r \in \mathcal{R}} r \left[ \sum_{s' \in \mathcal{S}} p(s', r \mid s, a) \right] \end{aligned}$$

2. Goals, Rewards, and Returns

Sutton and Barto’s reward hypothesis proposes that a goal can be represented as maximizing the expected cumulative value of a scalar reward signal [Sutton et al., 2018]. This is a modeling hypothesis, not a theorem that every real objective admits a faithful scalar representation. Once adopted, the reward specifies what behavior the objective favors, while the policy and learning procedure determine how to pursue it.

So, what is the Agent’s true goal? It is not to get the highest reward immediately, but to maximize the total accumulated reward in the long run. We call this accumulated sum the Return ($G_t$). To be precise, $G_t$ is the sum of rewards the agent accumulates in the future (i.e., from time step $t+1$ until the end). Why future sums instead of past sums? Recall the agent’s purpose is to maximize the reward it accumulates—like constantly looking ahead and choosing the future path that yields the most reward.

Depending on the task type, the calculation of $G_t$ differs:

1. Episodic Tasks: Interaction breaks down into subsequences called episodes. Each episode ends in a terminal state at time $T$.

   $$G_t = R_{t+1} + R_{t+2} + \dots + R_T$$

2. Continuing Tasks: Interaction goes on forever ($T = \infty$). For the discounted formulation here, we assume rewards are uniformly bounded and choose $0 \leq \gamma < 1$.

   $$G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... = \sum_{k=0}^\infty \gamma^k R_{t+k+1}$$

Discounting serves two distinct purposes:

• Well-defined infinite-horizon returns: if rewards are uniformly bounded and $\gamma < 1$, the return converges absolutely because it is bounded by a geometric series.
• Time preference: $\gamma$ controls how strongly delayed rewards affect the objective. If $\gamma = 0$, the agent is myopic, caring only about the immediate reward.

For a continuing task with $\gamma = 1$, the discounted-return argument no longer guarantees convergence. Such problems require additional structure or a different objective, such as average reward, and are outside this note’s scope.

We can observe a recursive relationship:

The formula above is a critically important recursive property. It means: The return of the current sequence equals the immediate reward plus the discounted return of the next sequence.

To define a single return formula for both cases, we use:

In continuing cases, $T = \infty$ and $\gamma < 1$. In episodic cases, $\gamma$ may equal $1$ when the episode terminates with a finite return.

3. Policies and Value Functions

How does an agent know if a state is “good”? A state is only good if it leads to a high return. But the return depends on how the agent behaves in the future. Therefore, the agent needs to know how to select and evaluate its actions.

We use Value Functions to describe the goodness of a state (or a state-action pair). The goodness of a state $s$ is the expected return from that state under a particular policy. Meanwhile, the Policy is the agent’s brain—it tells the agent how to select actions from the current state.

We will keep our policies stationary and Markov: $\pi(a\mid s)$ depends on the current state, but not explicitly on the time step or the earlier history. This choice is what lets us write one value $v_\pi(s)$ for a state without carrying the whole trajectory into the notation.

There are two main types of Value Functions. We write both as infinite sums; for episodic tasks, the zero-reward absorbing-state convention in Appendix C makes every term after termination vanish.

1. State-value function $v_{\pi}(s)$: The expected return when starting in $s$ and following policy $\pi$ thereafter.

   $$v_{\pi}(s) = \mathbb{E}_{\pi}[G_{t} \mid S_{t} = s] = \mathbb{E}_{\pi}\left[ \sum_{k=0}^{\infty} \gamma^{k} R_{t+k+1} \mid S_{t} = s \right]$$

2. Action-value function $q_{\pi}(s, a)$: The expected return starting from $s$, taking action $a$, and then following policy $\pi$.

   $$q_{\pi}(s, a) = \mathbb{E}_{\pi}[G_{t} \mid S_{t} = s, A_{t} = a] = \mathbb{E}_{\pi} \left[ \sum_{k=0}^{\infty} \gamma^{k} R_{t+k+1} \mid S_t = s, A_t = a \right]$$

The Q-Learning algorithm uses $Q(s,a)$ for its estimate of the optimal action-value function [Watkins et al., 1992].

A key concept here is following policy $\pi$. At any state $s$, different policies may assign different action probabilities. The value function is the exact expected return defined by a particular policy and MDP; a learning algorithm may only approximate that value from data.

4. The Bellman Equation

Because $G_t$ is recursive, the Value Function must also be recursive. This relationship allows us to compute Value Functions by “backtracking” (or backing up) information from the next state to the current state. We can write $v_{\pi}$ recursively as:

The equation above is the Bellman equation for the state-value function (see Appendix A).

• The Bellman equation states that the value of the start state must equal the (discounted) value of the expected next state, plus the reward expected along the way. This is the Consistency Condition.
• It shows that the value of a state is the weighted average of the immediate rewards the agent expects, plus the discounted value of the states the agent enters next.

Similarly, we have the Bellman equation for the action-value function $q_{\pi}(s, a)$:

The derivation is given in Appendix B.

Why do we need $q(s, a)$ if we already have $v(s)$?

If we know only $v(s)$, selecting an action by one-step lookahead requires the environment dynamics. If we already know $q(s,a)$, action selection can compare actions directly without consulting an explicit dynamics model at decision time. Obtaining an accurate $q$-function still requires either a model or sufficient experience. This distinction motivates model-free value-based methods such as Q-learning, which estimate action values from sampled transitions.

Another important concept is the backup diagram, which visualizes the Bellman equation using the notation of Sutton and Barto [Sutton et al., 2018]. We can interpret it as a tree where leaves are future states and internal nodes aggregate the outcomes below them.

We call this operation a backup. Unlike a simulated transition, which moves forward from $s$ to a sampled $s'$, a backup updates information at $s$ using estimates or returns associated with later states. Dynamic programming and temporal-difference value methods explicitly use Bellman-style backups. Monte Carlo methods instead use sampled complete returns, while policy-gradient methods need not explicitly approximate a Bellman equation.

• Root (open circle, representing state): State $s$.
• First branch: Policy $\pi(a \mid s)$.
• First node (solid circle, representing state-action pair): Pair $(s, a)$.
• Second branch: Environment dynamics $p(s', r \mid s, a)$.
• Leaves: Next state $s'$, whose value $v_{\pi}(s')$ contributes to the backup at the current state $s$.

5. Bellman Optimality Equation

We have defined value functions for a specific policy $\pi$. But we don’t just want to evaluate a policy; we want to find the best policy (the Optimal Policy).

All optimal policies share the same state-value function, called the optimal state-value function:

Similarly, optimal policies share the same optimal action-value function:

Just like the value function for a specific policy $\pi$, the value function for the optimal policy $\pi^{\ast}$ can be written in a Bellman form, called the Bellman Optimality Equation.

The relationship between optimal action-value and optimal state-value is:

Bellman Optimality Equation for state-value function:

Bellman Optimality Equation for action-value function:

The arc between branches represents maximizing over actions instead of averaging them under a fixed policyShow sidenoteWhy is the Bellman optimality equation harder to solve? For a fixed policy, the Bellman expectation equation is a linear system; see Appendix D. Maximizing over actions makes the optimality operator nonlinear, so the same direct linear solve does not apply. Standard alternatives include value iteration, policy iteration, and a linear-programming formulation. Q-learning estimates $q_\ast$ from samples when the dynamics are unavailable. See Appendix E..

Two boundary checks make the equations easier to interpret:

• If $\gamma = 0$, then $v_\pi(s)$ is only the expected immediate reward under $\pi$.
• For an absorbing terminal state with zero subsequent reward, both its state value and every permitted terminal action value are zero.

6. References

Appendix

A. Proof of Bellman Equation for State-Value Function

We have:

There are two expectations we need to resolve: the expectation of the immediate reward and the expectation of the next return $G_{t+1}$.

Expectation of the next reward:

We have:

We need to “decompose” the probability $p(r \mid s)$ into two parts: the policy $\pi(a \mid s)$ and the dynamics $p(r, s' \mid s, a)$. Applying the sum rule and product rule, we get:

Substituting this back into the expectation:

Once $s$ and $a$ are fixed, $\pi(a \mid s)$ does not vary with $r$ or $s'$. We can therefore move it outside those sums and rearrange the finite sums:

Expectation of the return at the next time step:

Applying the law of total expectation, $\mathbb{E}[X] = \sum_{y}\mathbb{E}[X \mid Y = y] \text{Pr} \{ Y = y \}$, we get:

Further expanding the conditional expectation:

Here we also use the fact that $\pi$ is a stationary Markov policy: after we condition on $S_{t+1}=s'$, future actions depend on $s'$ rather than on the earlier state, action, or reward. Together with the Markov property of the dynamics, this lets us remove $S_t$, $A_t$, and $R_{t+1}$ from the inner conditional expectationShow sidenoteConditional Independence: If $P(A \mid B, C) = P(A \mid C)$, we say $A$ and $B$ are conditionally independent given $C$.:

Combining everything, we arrive at:

B. Proof of Bellman Equation for Action-Value Function

From the proof in Appendix A, we see:

Also:

To satisfy the recursive nature of the Bellman equation, we need to express $q_{\pi}$ in terms of another $q_{\pi}$. First:

The state name is only a dummy variable, so the same identity at the successor state is

Substituting this identity into $q_{\pi}(s, a)$ gives the final result:

C. Unified Notation for Episodic and Continuing Tasks

In an episodic task, the interaction stops when we reach a terminal state. But our continuing-task equations are easier to reuse if every state has a next transition. We can bridge the two views by extending the process after termination in a harmless way.

Let $\mathcal{S}$ contain the non-terminal states and let $\mathcal{S}^+ = \mathcal{S} \cup \{s_\dagger\}$ include an absorbing terminal state $s_\dagger$. We give this state one dummy action, $\mathcal{A}(s_\dagger)=\{a_\dagger\}$, and define:

What does this convention buy us?

• Once the process reaches $s_\dagger$, it stays there.
• Every later reward is zero, so extending the trajectory does not change the episodic return.
• The terminal value is therefore $v_\pi(s_\dagger)=0$.

The dynamics now remain normalized even at the terminal state:

This is a notational extension, not a claim that the real environment continues after the episode ends.

D. Linearity of the Bellman Equation

For each state $s$, we have a value $v_{\pi}(s)$. If we assume $n$ states, we can write $n$ equations, turning the task of finding $v_{\pi}$ into solving a system of equations:

Writing this system in matrix form shows that the Bellman equation for a specific policy is linear. First, define:

• State-transition matrix $P^{\pi}(s' \mid s)$: If the agent is in state $s$, what is the probability of transitioning to state $s'$, averaged over the actions of policy $\pi$? $$P^{\pi}(s' \mid s) = \sum_{a \in \mathcal{A}(s)} \pi(a \mid s) \sum_{r} p(s', r \mid s, a)$$
• Expected reward vector $R^{\pi}(s)$: If the agent is in state $s$, what is the expected reward, averaged over the actions of policy $\pi$? $$R^{\pi}(s) = \sum_{a \in \mathcal{A}(s)} \pi(a \mid s) \sum_{s', r} p(s', r \mid s, a)r$$

Thus, the Bellman equation becomes:

Writing this as a system:

Finally, the matrix form is:

If $0 \leq \gamma < 1$, then $\mathbf{P}_\pi$ is a stochastic matrix with spectral radius at most $1$. Therefore, $\mathbf{I}-\gamma\mathbf{P}_\pi$ is invertible, and we can solve:

Notice how the condition $\gamma<1$ matters here. If we include our absorbing state and set $\gamma=1$, the full transition matrix has eigenvalue $1$, so $\mathbf{I}-\mathbf{P}_\pi$ is singular. For an episodic problem, we instead impose $v_\pi(s_\dagger)=0$ and solve over the transient non-terminal states when the policy reaches termination with probability $1$.

Even when the inverse exists, we normally solve the linear system rather than explicitly forming the inverse. A direct dense solve costs roughly $\mathcal{O}(n^3)$, although sparse or iterative solvers may do much better. More fundamentally, large state spaces make the system expensive, and model-free settings do not give us $\mathbf{P}_\pi$ or $\mathbf{r}_\pi$ in the first place.

E. How to Find the Optimal Policy

Suppose we already know $v_\ast$. At each state, let $a_\ast(s)$ be any action attaining the maximum in the Bellman optimality equation:

We use $\in$ because several actions may tie. Setting $\pi_\ast(a_\ast(s)\mid s)=1$ gives a deterministic greedy policy, and in the finite discounted setting that policy is optimal.

There are two equivalent ways to make this choice: one uses $v_{\ast}$ and the dynamics, while the other uses $q_{\ast}$ directly.

Based on optimal state-value function:

• To find $\pi^{\ast}$ knowing $v_{\ast}$, we must know the environment dynamics $p(s', r \mid s,a)$. We must also perform a one-step (look-ahead) search, summing over all possible next states $s'$ and rewards $r$.
• This selection appears greedy because we only look at the immediate reward $r$ and the value of the next state $v_{\ast}(s')$. However, this yields the optimal result for the long term. This works because $v_{\ast}(s')$ already accounts for the optimal reward sequence in the future.

Based on optimal action-value function: If $q_\ast$ is already known, the agent does not need a one-step search; it can pick an action with the highest $q_{\ast}(s, a)$. The decision itself does not require an explicit dynamics model, although learning or computing $q_\ast$ still requires information obtained from a model or experience.