---
cluster: D
day: D.1
contributors:
  - Leon Lang
  - David Quarel
title: "Reinforcement Learning"
summary: >-
  The Bellman equations and what follows from them: the existence of optimal
  policies, the policy improvement theorem, the rate of convergence of
  Bellman updates, and the convergence of Q-learning.
---

$\gdef\cS{\mathcal{S}}\gdef\cA{\mathcal{A}}\gdef\argmax{\operatorname*{arg\,max}}$

<LearningOutcomes>

- Understand Markov Decision Processes and the goal of the agent, for known environments.
- Understand the Bellman equation.
- Understand the policy improvement theorem, and how we can use it to iteratively solve for an optimal policy.
- Prove properties involving the Bellman equations, including the existence of optimal policies, the policy improvement theorem, rate of convergence of Bellman updates, and the convergence of Q-learning.

</LearningOutcomes>

## Setup

In this exercise sheet, we prove a variety of results that are behind the [ARENA Intro to RL materials](https://learn.arena.education/chapter2_rl/01_intro_rl/).

An **agent** interacts with an **environment** in discrete time steps $t = 0, 1, 2, \ldots$. On timestep $t$, the agent observes the current state $s_{t} \in \cS$ and selects an action $a_{t} \in \cA$ according to its policy. The environment then responds with a reward $r_{t+1}\in \mathbb{R}$ and a new state $s_{t+1}\in \cS$. (The reward and next state are indexed by $t+1$ because they are produced by the environment after the agent's action.) The goal is to act so as to maximize expected discounted future reward.

These environments are called **Markov decision processes** (MDPs). They satisfy two key properties: (i) **stationarity** — the transition and reward functions do not change over time, and (ii) the **Markov property** — the distribution over the next state and reward depends only on the current state and action, not on the full history of past interactions. Together, these properties mean that the current state $s_{t}$ is a sufficient summary of the past for the purpose of choosing optimal actions.

<Definition id="def-spaces">

**Definition 0.1 (Spaces and notation).** - $\cS$ — finite **state space**
- $\cA$ — finite **action space**
- $\gamma \in (0, 1)$ — **discount factor**
- $\Delta X$ — set of all probability distributions over a set $X$
- $\llbracket P \rrbracket$ — **Iverson bracket**: $1$ if $P$ is true, $0$ if false

</Definition>

<Definition id="def-environment">

**Definition 0.2 (Environment).** An MDP **environment** is specified by a pair $(T, R)$:

- $T : \cS \times \cA \to \Delta \cS$ is the **transition kernel**: given state $s$ and action $a$, the next state is drawn $s' \sim T(\cdot \mid s, a)$.
- $R : \cS \times \cA \times \cS \to \mathbb{R}$ is the **reward function**: on a transition from $s$ to $s'$ under action $a$, the agent receives reward $R(s, a, s')$. [^1]

</Definition>

<Definition id="def-policy">

**Definition 0.3 (Policy).** A **policy** $\pi : \cS \to \Delta \cA$ maps each state to a probability distribution over actions. Given state $s$:

- $\pi(\cdot \mid s)$ is a distribution over $\cA$,
- $\pi(a \mid s) \in [0, 1]$ is the probability of choosing action $a$,
- the agent samples $a \sim \pi(\cdot \mid s)$.

A policy is **deterministic** if $\pi(a \mid s) \in \{0, 1\}$ for all $a, s$. In this case, we abuse notation and write $\pi(s) := \argmax_{a \in \cA}\pi(a \mid s)$ for the unique action selected at state $s$.

</Definition>

<Definition id="def-trajectory">

**Definition 0.4 (Trajectory).** When policy $\pi$ interacts with environment $(T, R)$ starting from initial state $s_{0}$, the resulting **trajectory** $(s_{0}, a_{0}, r_{1}, s_{1}, a_{1}, r_{2}, s_{2}, a_{2}, r_{3}, \ldots)$ is generated by

$$
a_{k} \sim \pi(\cdot \mid s_{k}), \qquad s_{k+1}\sim T(\cdot \mid s_{k}, a_{k}), \qquad r_{k+1}= R(s_{k}, a_{k}, s_{k+1}),
$$

for $k = 0, 1, 2, \ldots$. We write $\mathbb{E}_{\pi}[\,\cdot\,]$ for expectations over such trajectories.

</Definition>

## 1. The Bellman equation

<Definition id="def-return">

**Definition 1.1 (Return).** The **return** from time $t$ is the discounted sum of future rewards:

$$
G_{t} \;:=\; \sum_{k=t+1}^{\infty}\gamma^{k-t-1}\, r_{k} \;=\; r_{t+1}+ \gamma\, r_{t+2}+ \gamma^{2}\, r_{t+3}+ \cdots.
$$

It satisfies the recursion

$$
G_{t} \;=\; r_{t+1}+ \gamma\, G_{t+1}.
$$

</Definition>

<Definition id="def-value">

**Definition 1.2 (Value function).** The **value function** of a policy $\pi$ is the expected return when starting from state $s$ and acting according to $\pi$:

$$
\begin{aligned}&V_{\pi}(s) \;=\; \mathbb{E}_{\pi}\!\left[G_{t} \;\middle|\; s_{t} = s\right] \\&=\; \mathbb{E}_{\pi}\!\left[\,r_{t+1}+ \gamma\, r_{t+2}+ \gamma^{2}\, r_{t+3}+ \cdots \;\middle|\; s_{t} = s\right] \\&=\; \sum_{a_t \in \cA}\pi(a_{t} \mid s)\! \sum_{s_{t+1} \in \cS}\!T(s_{t+1}\mid s, a_{t})\! \sum_{a_{t+1} \in \cA}\pi(a_{t+1}\mid s_{t+1}) \\&\quad \sum_{s_{t+2} \in \cS}\!T(s_{t+2}\mid s_{t+1}, a_{t+1})\, \cdots \\&\quad \bigl[\, R(s, a_{t}, s_{t+1}) + \gamma\, R(s_{t+1}, a_{t+1}, s_{t+2}) + \gamma^{2}\, R(s_{t+2}, a_{t+2}, s_{t+3}) + \cdots \,\bigr].\end{aligned}
$$

The expectation averages the return over all future trajectories $(a_{t}, s_{t+1}, a_{t+1}, s_{t+2}, \ldots)$ generated by sampling $a_{k} \sim \pi(\cdot \mid s_{k})$ and $s_{k+1}\sim T(\cdot \mid s_{k}, a_{k})$, starting from $s_{t} = s$.

</Definition>

<Exercise id="prob-bellman-proof">
**Exercise 1.1.** Prove the **Bellman equation**: for all $s \in \cS$,
<Callout type="note">

**Bellman Equation**

$$
V_{\pi}(s) = \sum_{a \in \cA}\pi(a \mid s) \sum_{s' \in \cS}T(s' \mid s, a)\bigl(R(s,a,s') + \gamma\, V_{\pi}(s')\bigr).
$$

</Callout>
*Hint:* condition on the first action and the first transition, then separate the immediate reward from the remaining return.
</Exercise>

<Solution>

Starting from the definition of $V_{\pi}$ and using the recursion $G_{t} = r_{t+1}+ \gamma\, G_{t+1}$:

$$
\begin{aligned}V_{\pi}(s)&= \mathbb{E}_{\pi}\!\left[G_{t} \;\middle|\; s_{t} = s\right] = \mathbb{E}_{\pi}\!\left[r_{t+1}+ \gamma\, G_{t+1}\;\middle|\; s_{t} = s\right].\end{aligned}
$$

Now condition on the first action $a_{t} = a$ and the first transition $s_{t+1}= s'$:

$$
\begin{aligned}V_{\pi}(s)&= \sum_{a \in \cA}\pi(a \mid s) \sum_{s' \in \cS}T(s' \mid s, a) \\&\qquad \times \mathbb{E}_{\pi}\!\left[r_{t+1}+ \gamma\, G_{t+1}\;\middle|\; s_{t} = s,\, a_{t} = a,\, s_{t+1}= s'\right].\end{aligned}
$$

Given $s_{t} = s$, $a_{t} = a$, and $s_{t+1}= s'$, the immediate reward is deterministic: $r_{t+1}= R(s, a, s')$. For the remaining return, by the Markov property the future trajectory from time $t+1$ onward depends only on $s_{t+1}= s'$, so

$$
\mathbb{E}_{\pi}\!\left[G_{t+1}\;\middle|\; s_{t} = s,\, a_{t} = a,\, s_{t+1}= s'\right] = \mathbb{E}_{\pi}\!\left[G_{t+1}\;\middle|\; s_{t+1}= s'\right] = V_{\pi}(s').
$$

Substituting both back gives

$$
V_{\pi}(s) = \sum_{a \in \cA}\pi(a \mid s) \sum_{s' \in \cS}T(s' \mid s, a)\bigl(R(s,a,s') + \gamma\, V_{\pi}(s')\bigr).
$$

</Solution>

<Definition id="def-q-function">

**Definition 1.3 (Action-value function).** The **action-value function** (or Q-function) of $\pi$ is the expected return starting from state $s$, taking action $a$, and acting according to $\pi$ thereafter:

$$
Q_{\pi}(s,a) \;=\; \mathbb{E}_{\pi}\!\left[G_{t} \;\middle|\; s_{t} = s,\, a_{t} = a\right].
$$

</Definition>

<Exercise id="prob-q-function">
**Exercise 1.2.** **(a)** Express $V_{\pi}(s)$ in terms of $Q_{\pi}$.

**(b)** Express $Q_{\pi}(s,a)$ in terms of $V_{\pi}$.

**(c)** Using these relations, derive a recursive equation for $Q_{\pi}$ analogous to the Bellman equation above.
</Exercise>

<Solution>

**(a)** Starting from the definition of $V_{\pi}(s)$ and conditioning on the first action $a_{t} = a$:

$$
\begin{aligned}V_{\pi}(s)&= \mathbb{E}_{\pi}\!\left[G_{t} \;\middle|\; s_{t} = s\right] \\&= \sum_{a \in \cA}\pi(a \mid s)\; \mathbb{E}_{\pi}\!\left[G_{t} \;\middle|\; s_{t} = s,\, a_{t} = a\right] \\&= \sum_{a \in \cA}\pi(a \mid s)\, Q_{\pi}(s, a).\end{aligned}
$$

**(b)** Starting from the definition of $Q_{\pi}(s,a)$ and using the recursion $G_{t} = r_{t+1}+ \gamma\, G_{t+1}$, we condition on the first transition $s_{t+1}= s'$:

$$
\begin{aligned}Q_{\pi}(s,a)&= \mathbb{E}_{\pi}\!\left[G_{t} \;\middle|\; s_{t} = s,\, a_{t} = a\right] \\&= \sum_{s' \in \cS}T(s' \mid s, a)\; \mathbb{E}_{\pi}\!\left[r_{t+1}+ \gamma\, G_{t+1}\;\middle|\; s_{t} = s,\, a_{t} = a,\, s_{t+1}= s'\right] \\&= \sum_{s' \in \cS}T(s' \mid s, a)\bigl(R(s, a, s') + \gamma\, V_{\pi}(s')\bigr),\end{aligned}
$$

where the last step uses $r_{t+1}= R(s,a,s')$ (deterministic given $s_{t}, a_{t}, s_{t+1}$) and the Markov property $\mathbb{E}_{\pi}[G_{t+1}\mid s_{t+1}= s'] = V_{\pi}(s')$.

**(c)** Substituting [Exercise 1.2(a)](#prob-q-function) into [Exercise 1.2(b)](#prob-q-function), replacing $V_{\pi}(s')$ by its expression in terms of $Q_{\pi}$:

$$
Q_{\pi}(s, a) = \sum_{s' \in \cS}T(s' \mid s, a)\!\left(R(s, a, s') + \gamma \sum_{a' \in \cA}\pi(a' \mid s')\, Q_{\pi}(s', a')\right).
$$

This is the Bellman equation for the action-value function. Note also that substituting [Exercise 1.2(b)](#prob-q-function) into [Exercise 1.2(a)](#prob-q-function) recovers the Bellman equation for $V_{\pi}$ from [Exercise 1.1](#prob-bellman-proof).

</Solution>

## 2. An example MDP

Consider the MDP with state space $\cS = \{s_{0}, s_{L}, s_{R}\}$, action space $\cA = \{a_{L}, a_{R}\}$, and deterministic transitions as shown:

<Figure src="/uploads/reinforcement-learning/tikz-7f28027bb4ad.svg" alt="diagram" />

From $s_{0}$, action $a_{L}$ leads deterministically to $s_{L}$ with reward $+1$, and action $a_{R}$ leads deterministically to $s_{R}$ with reward $+0$. From $s_{L}$ (resp. $s_{R}$), any action returns to $s_{0}$ with reward $+0$ (resp. $+2$).

Let $\pi_{L}$ denote the policy that always selects $a_{L}$, and $\pi_{R}$ the policy that always selects $a_{R}$.

<Exercise id="prob-small-mdp-values">
**Exercise 2.1.** Using the Bellman equation from [Exercise 1.1](#prob-bellman-proof), verify that

$$
V_{\pi_L}(s_{0}) = \frac{1}{1-\gamma^{2}}, \qquad V_{\pi_R}(s_{0}) = \frac{2\gamma}{1-\gamma^{2}}.
$$
</Exercise>

<Solution>

Under $\pi_{L}$ all transitions are deterministic, so the Bellman equation collapses to

$$
\begin{aligned}V_{\pi_L}(s_{0})&= R(s_{0}, a_{L}, s_{L}) + \gamma\, V_{\pi_L}(s_{L}) = 1 + \gamma\, V_{\pi_L}(s_{L}), \\ V_{\pi_L}(s_{L})&= R(s_{L}, a_{L}, s_{0}) + \gamma\, V_{\pi_L}(s_{0}) = 0 + \gamma\, V_{\pi_L}(s_{0}).\end{aligned}
$$

Substituting the second into the first gives $V_{\pi_L}(s_{0}) = 1 + \gamma^{2}\, V_{\pi_L}(s_{0})$, hence

$$
V_{\pi_L}(s_{0}) = \frac{1}{1-\gamma^{2}}.
$$

Similarly, under $\pi_{R}$:

$$
\begin{aligned}V_{\pi_R}(s_{0})&= R(s_{0}, a_{R}, s_{R}) + \gamma\, V_{\pi_R}(s_{R}) = 0 + \gamma\, V_{\pi_R}(s_{R}), \\ V_{\pi_R}(s_{R})&= R(s_{R}, a_{R}, s_{0}) + \gamma\, V_{\pi_R}(s_{0}) = 2 + \gamma\, V_{\pi_R}(s_{0}).\end{aligned}
$$

Substituting yields $V_{\pi_R}(s_{0}) = \gamma\bigl(2 + \gamma\, V_{\pi_R}(s_{0})\bigr) = 2\gamma + \gamma^{2}\, V_{\pi_R}(s_{0})$, hence

$$
V_{\pi_R}(s_{0}) = \frac{2\gamma}{1-\gamma^{2}}.
$$

</Solution>

<Exercise id="prob-small-mdp-optimal">
**Exercise 2.2.** Determine the best action from state $s_{0}$ as a function of the discount factor $\gamma \in (0, 1)$. Show that the breakeven point is $\gamma = \tfrac{1}{2}$.
</Exercise>

<Solution>

Since any action from $s_{L}$ or $s_{R}$ deterministically returns to $s_{0}$ with the same reward, the value of any policy at $s_{0}$ is determined entirely by the action chosen at $s_{0}$. Hence comparing $V_{\pi_L}(s_{0})$ and $V_{\pi_R}(s_{0})$ suffices:

$$
V_{\pi_L}(s_{0}) - V_{\pi_R}(s_{0}) \;=\; \frac{1 - 2\gamma}{1-\gamma^{2}}.
$$

Since $1 - \gamma^{2} > 0$ for $\gamma \in (0,1)$, the sign is determined by $1 - 2\gamma$:

- $\gamma < \tfrac{1}{2}$: $a_{L}$ is optimal — the immediate reward of $1$ outweighs a discounted future reward of $2$.
- $\gamma > \tfrac{1}{2}$: $a_{R}$ is optimal — the agent is patient enough to wait one step for the larger reward.
- $\gamma = \tfrac{1}{2}$: both actions are equally good (breakeven), and each gives $V^{*}(s_{0}) = \tfrac{4}{3}$.

</Solution>

## 3. Bellman operators and the existence of optimal policies

### Banach fixed-point theorem

In this and the following exercises, we will make use of the well-known Banach fixed point theorem:

<Theorem id="thm-banach">

**Theorem 3.1 (Banach Fixed Point Theorem).** Let $(X, d)$ be a complete metric space and let $F : X \to X$ be a contraction mapping, i.e. there exists $\gamma \in [0,1)$ such that

$$
d(F(x), F(y)) \le \gamma\, d(x, y) \quad \text{for all }x, y \in X.
$$

Then $F$ has a unique fixed point $x^{*} \in X$ satisfying $F(x^{*}) = x^{*}$. Moreover, for any initial point $x_{0} \in X$, one

has $\lim_{n \to \infty}d(F^{n}(x_{0}), x^{*}) = 0$ where $F^{n}$ is the $n$-fold composition of $F$ with itself. That is, $F^{n}(x_{0})$ converges to $x^{*}$ with respect to the metric $d$.

</Theorem>

### The problem

<Definition id="def-bellman-op">

**Definition 3.2 (Bellman optimality operator).** Let $\mathcal{V}= \{V : \cS \to \mathbb{R}\}$ denote the vector space of value functions, equipped with the sup-norm $\|V\|_{\infty} = \max_{s \in \cS}|V(s)|$. The **Bellman optimality operator** $\mathcal{B}: \mathcal{V}\to \mathcal{V}$ is defined by

$$
(\mathcal{B}V)(s) \coloneqq \max_{a \in \cA}\sum_{s' \in \cS}T(s' \mid s, a)\bigl(R(s,a,s') + \gamma\, V(s')\bigr).
$$

</Definition>

<Exercise id="prob-max-ineq">
**Exercise 3.1.** Let $f, g : \cA \to \mathbb{R}$ be real-valued functions on a finite set $\cA$. Prove that

$$
\left|\max_{a \in \cA}f(a) - \max_{a \in \cA}g(a)\right| \le \max_{a \in \cA}|f(a) - g(a)|.
$$
</Exercise>

<Solution>

Without loss of generality, assume $\max_{a}f(a) \ge \max_{a}g(a)$. Let $a^{*} \in \argmax_{a \in \cA}f(a)$. Then:

$$
\begin{aligned}\left|\max_{a \in \cA}f(a) - \max_{a \in \cA}g(a)\right|&= \max_{a \in \cA}f(a) - \max_{a \in \cA}g(a) \\&= f(a^{*}) - \max_{a \in \cA}g(a) \\&\le f(a^{*}) - g(a^{*}) \\&= |f(a^{*}) - g(a^{*})| \\&\le \max_{a \in \cA}|f(a) - g(a)|.\end{aligned}
$$

</Solution>

<Exercise id="prob-b-contraction">
**Exercise 3.2.** Using [Exercise 3.1](#prob-max-ineq), prove that $\mathcal{B}$ is a **contraction mapping** with contraction factor $\gamma$, i.e. for all $V, W \in \mathcal{V}$,

$$
\|\mathcal{B}V - \mathcal{B}W\|_{\infty} \le \gamma\, \|V - W\|_{\infty}.
$$
</Exercise>

<Solution>

Fix an arbitrary state $s \in \cS$. Define for each $a \in \cA$:

$$
\begin{aligned}f(a)&\coloneqq \sum_{s' \in \cS}T(s' \mid s, a)\bigl(R(s,a,s') + \gamma\, V(s')\bigr), \\ g(a)&\coloneqq \sum_{s' \in \cS}T(s' \mid s, a)\bigl(R(s,a,s') + \gamma\, W(s')\bigr).\end{aligned}
$$

Then $(\mathcal{B}V)(s) = \max_{a} f(a)$ and $(\mathcal{B}W)(s) = \max_{a} g(a)$. By [Exercise 3.1](#prob-max-ineq):

$$
\begin{aligned}\big|(\mathcal{B}V)(s) - (\mathcal{B}W)(s)\big|&\le \max_{a \in \cA}\big|f(a) - g(a)\big| \\&= \max_{a \in \cA}\left|\sum_{s' \in \cS}T(s' \mid s, a)\gamma\,\bigl(V(s') - W(s')\bigr)\right| \\&\le \gamma \max_{a \in \cA}\sum_{s' \in \cS}T(s' \mid s, a)\,\big|V(s') - W(s')\big| \\&\le \gamma \max_{a \in \cA}\sum_{s' \in \cS}T(s' \mid s, a)\,\|V - W\|_{\infty} \\&\le \gamma\,\|V - W\|_{\infty},\end{aligned}
$$

where the last step uses $\sum_{s'}T(s' \mid s, a) = 1$. Since this holds for every $s \in \cS$, taking the maximum over $s$ gives $\|\mathcal{B}V - \mathcal{B}W\|_{\infty} \le \gamma\,\|V - W\|_{\infty}$.

</Solution>

<Exercise id="prob-v-star-exists">
**Exercise 3.3.** Using [Theorem 3.1](#thm-banach), conclude that there exists a unique $V^{*} \in \mathcal{V}$ satisfying $\mathcal{B}V^{*} = V^{*}$, and that for any initial $V_{0} \in \mathcal{V}$, the iterates $\mathcal{B}^{n} V_{0} \to V^{*}$ as $n \to \infty$.
</Exercise>

<Solution>

The space $(\mathcal{V}, \|\cdot\|_{\infty})$ is a finite-dimensional normed vector space, hence complete. By [Exercise 3.2](#prob-b-contraction), $\mathcal{B}$ is a contraction on $\mathcal{V}$ with factor $\gamma < 1$. [Theorem 3.1](#thm-banach) then gives the existence of a unique fixed point $V^{*} = \mathcal{B}V^{*}$, and convergence $\mathcal{B}^{n} V_{0} \to V^{*}$ for any $V_{0} \in \mathcal{V}$.

</Solution>

<Exercise id="prob-bpi-contraction">
**Exercise 3.4.** Show that for any policy $\pi$, the operator $\mathcal{B}_{\pi} : \mathcal{V}\to \mathcal{V}$ defined by
<Callout type="note">

**Bellman Policy Operator**

$$
(\mathcal{B}_{\pi} V)(s) \coloneqq \sum_{a \in \cA}\pi(a \mid s) \sum_{s' \in \cS}T(s' \mid s, a)\bigl(R(s,a,s') + \gamma\, V(s')\bigr)
$$

</Callout>
is also a contraction with factor $\gamma$. Conclude that $V_{\pi}$ is its unique fixed point and that $\mathcal{B}^{n}_{\pi}V_{0} \to V_{\pi}$ for any initial $V_{0} \in \mathcal{V}$ as $n \to \infty$.

*Remark.* This shows that the numerical policy evaluation algorithm from the ARENA materials converges to the correct solution.
</Exercise>

<Solution>

Fix $V, W \in \mathcal{V}$ and an arbitrary state $s \in \cS$. Then:

$$
\begin{aligned}\big|(\mathcal{B}_{\pi} V)(s) - (\mathcal{B}_{\pi} W)(s)\big|&= \left|\sum_{a \in \cA}\pi(a \mid s) \sum_{s' \in \cS}T(s' \mid s, a)\,\gamma\bigl(V(s') - W(s')\bigr)\right| \\&\le \gamma \,\sum_{a \in \cA}\pi(a \mid s) \sum_{s' \in \cS}T(s' \mid s, a)\,\big|V(s') - W(s')\big| \\&\le \gamma \, \sum_{a \in \cA}\pi(a \mid s) \sum_{s' \in \cS}T(s' \mid s, a)\,\|V - W\|_{\infty}\\&\le \gamma\,\|V - W\|_{\infty},\end{aligned}
$$

where the last step uses $\sum_{s'}T(s' \mid s, a) = 1$ and $\sum_{a} \pi(a \mid s) = 1$. Taking the maximum over $s$ gives $\|\mathcal{B}_{\pi} V - \mathcal{B}_{\pi} W\|_{\infty} \le \gamma\,\|V - W\|_{\infty}$, so $\mathcal{B}_{\pi}$ is a contraction with factor $\gamma$.

By [Theorem 3.1](#thm-banach), $\mathcal{B}_{\pi}$ has a unique fixed point. By the Bellman equation ([Section 1](#1-the-bellman-equation)), $V_{\pi}$ satisfies $\mathcal{B}_{\pi} V_{\pi} = V_{\pi}$, so $V_{\pi}$ is this unique fixed point. The convergence statement also follows from [Theorem 3.1](#thm-banach).

</Solution>

<Exercise id="prob-greedy-equals-b">
**Exercise 3.5.** Let $V \in \mathcal{V}$ be any value function, and let $\pi_{V}$ be a greedy policy with respect to $V$, i.e.

$$
\pi_{V}(s) \in \argmax_{a \in \cA}\sum_{s' \in \cS}T(s' \mid s, a)\bigl(R(s,a,s') + \gamma\, V(s')\bigr).
$$

Show that $\mathcal{B}_{\pi_V}V = \mathcal{B}V$.
</Exercise>

<Solution>

Since $\pi_{V}$ is deterministic, $\pi_{V}(a \mid s) = \llbracket a = \pi_{V}(s) \rrbracket$, so the sum over $a$ in $\mathcal{B}_{\pi_V}$ collapses to the single term $a = \pi_{V}(s)$. For every $s \in \cS$:

$$
\begin{aligned}(\mathcal{B}_{\pi_V}V)(s)&= \sum_{s' \in \cS}T(s' \mid s, \pi_{V}(s))\bigl(R(s,\pi_{V}(s),s') + \gamma\, V(s')\bigr) \\&= \max_{a \in \cA}\sum_{s' \in \cS}T(s' \mid s, a)\bigl(R(s,a,s') + \gamma\, V(s')\bigr) \\&= (\mathcal{B}V)(s),\end{aligned}
$$

where the second equality holds because $\pi_{V}(s)$ selects a maximizing action by definition.

</Solution>

<Exercise id="prob-v-pi-star">
**Exercise 3.6.** Define the **greedy policy** with respect to $V^{*}$ by $\pi^{*} = \pi_{V^*}$ as in the previous part. Show that $V_{\pi^*}= V^{*}$, i.e. the value function of $\pi^{*}$ equals the fixed point of $\mathcal{B}$.

*Hint:* show that $V^{*}$ satisfies the same fixed-point equation as $V_{\pi^*}$.
</Exercise>

<Solution>

We have $\mathcal{B}_{\pi^*}V^{*} = \mathcal{B}V^{*} = V^{*}$ by [Exercise 3.5](#prob-greedy-equals-b) and [Exercise 3.3](#prob-v-star-exists). So $V^{*}$ is a fixed point of $\mathcal{B}_{\pi^*}$. By [Exercise 3.4](#prob-bpi-contraction), $V_{\pi^*}$ is the unique fixed point of $\mathcal{B}_{\pi^*}$. Therefore $V_{\pi^*}= V^{*}$.

</Solution>

<Exercise id="prob-optimality">
**Exercise 3.7.** Conclude that $\pi^{*}$ is an **optimal policy**: for every policy $\pi$ and every state $s \in \cS$,

$$
V_{\pi^*}(s) \ge V_{\pi}(s).
$$

*Hint:* show that $\mathcal{B}V_{\pi} \ge V_{\pi}$ pointwise, then iterate and take the limit.
</Exercise>

<Solution>

Let $\pi$ be any policy. Since the max over actions is at least as large as any weighted average:

$$
(\mathcal{B}V)(s) \ge (\mathcal{B}_{\pi} V)(s) \quad \text{for all }V \in \mathcal{V},\; s \in \cS.
$$

In particular, since $V_{\pi}$ is a fixed point of $\mathcal{B}_{\pi}$ ([Exercise 3.4](#prob-bpi-contraction)):

$$
(\mathcal{B}V_{\pi})(s) \ge (\mathcal{B}_{\pi} V_{\pi})(s) = V_{\pi}(s) \quad \text{for all }s \in \cS.
$$

Note that $\mathcal{B}$ is monotone: if $V(s) \ge W(s)$ for all $s$, then $(\mathcal{B}V)(s) \ge (\mathcal{B}W)(s)$. Applying $\mathcal{B}$ to both sides and using monotonicity, then iterating:

$$
V_{\pi} \le \mathcal{B}V_{\pi} \le \mathcal{B}^{2} V_{\pi} \le \cdots \le \mathcal{B}^{n} V_{\pi}.
$$

By [Exercise 3.3](#prob-v-star-exists), $\mathcal{B}^{n} V_{\pi} \to V^{*}$ as $n \to \infty$. Taking the limit:

$$
V_{\pi}(s) \le V^{*}(s) = V_{\pi^*}(s) \quad \text{for all }s \in \cS,
$$

where the last equality is [Exercise 3.6](#prob-v-pi-star). Since $\pi$ was arbitrary, $\pi^{*}$ is optimal.

</Solution>

## 4. Policy improvement theorem

Given a policy $\pi$, define the **improved policy** $\pi'$ greedily with respect to $V_{\pi}$:

<Callout type="note">

**Policy Improvement**

$$
\pi'(s) \in \argmax_{a \in \cA}\sum_{s' \in \cS}T(s' \mid s, a)\bigl(R(s,a,s') + \gamma\, V_{\pi}(s')\bigr).
$$

</Callout>

<Exercise id="prob-when-equality">
**Exercise 4.1.** In proving [Exercise 3.7](#prob-optimality), we already saw that for all $s \in \cS$, we have $(\mathcal{B}V_{\pi})(s) \ge V_{\pi}(s)$. When does equality hold for all states?
</Exercise>

<Solution>

We have

$$
\begin{aligned}(\mathcal{B}V_{\pi})(s)&= \max_{a \in \cA}\sum_{s' \in \cS}T(s' \mid s, a)\bigl(R(s,a,s') + \gamma\, V_{\pi}(s')\bigr) \\&\ge \sum_{a \in \cA}\pi(a \mid s) \sum_{s' \in \cS}T(s' \mid s, a)\bigl(R(s,a,s') + \gamma\, V_{\pi}(s')\bigr) \\&= V_{\pi}(s),\end{aligned}
$$

where we used the Bellman equation in the last step. If equality holds at every state $s$, then $V_{\pi}$ is a fixed point of $\mathcal{B}$, which by uniqueness ([Exercise 3.3](#prob-v-star-exists)) means $V_{\pi} = V^{*} = V_{\pi^*}$, i.e. $\pi$ is already optimal by [Exercise 3.7](#prob-optimality).

</Solution>

<Exercise id="prob-policy-improvement-thm">
**Exercise 4.2.** Show that $V_{\pi'}(s) \ge V_{\pi}(s)$ for all $s \in \cS$.

*Hint:* show that $\mathcal{B}_{\pi'}V_{\pi} \ge V_{\pi}$ pointwise using [Exercise 3.5](#prob-greedy-equals-b), then iterate $\mathcal{B}_{\pi'}$ and take the limit.
</Exercise>

<Solution>

By [Exercise 3.5](#prob-greedy-equals-b), $\mathcal{B}_{\pi'}V_{\pi} = \mathcal{B}V_{\pi} \ge V_{\pi}$ pointwise, where the inequality is from [Exercise 4.1](#prob-when-equality). Note that $\mathcal{B}_{\pi'}$ is monotone: if $V(s) \ge W(s)$ for all $s$, then $(\mathcal{B}_{\pi'}V)(s) \ge (\mathcal{B}_{\pi'}W)(s)$. Applying $\mathcal{B}_{\pi'}$ to both sides and iterating:

$$
V_{\pi} \le \mathcal{B}_{\pi'}V_{\pi} \le \mathcal{B}_{\pi'}^{2} V_{\pi} \le \cdots \le \mathcal{B}_{\pi'}^{n} V_{\pi}.
$$

By [Exercise 3.4](#prob-bpi-contraction), $\mathcal{B}_{\pi'}^{n} V_{\pi} \to V_{\pi'}$ as $n \to \infty$. Taking the limit gives $V_{\pi'}(s) \ge V_{\pi}(s)$ for all $s \in \cS$.

</Solution>

<Exercise id="prob-policy-iteration">
**Exercise 4.3.** The **policy iteration** algorithm generates a sequence of policies $\pi_{0}, \pi_{1}, \pi_{2}, \ldots$ where each $\pi_{k+1}$ is the greedy policy with respect to $V_{\pi_k}$. Show that this sequence converges to an optimal policy $\pi^{*}$ in a finite number of steps.

*Hint:* how many deterministic policies are there?
</Exercise>

<Solution>

By [Exercise 4.2](#prob-policy-improvement-thm), the sequence of value functions is monotonically improving: $V_{\pi_{k+1}}(s) \ge V_{\pi_k}(s)$ for all $s$ and all $k$. Since each $\pi_{k}$ is a deterministic policy and there are only $|\cA|^{|\cS|}$ deterministic policies, the sequence must eventually revisit a policy. If $\pi_{k+1}= \pi_{j}$ for some $j \le k$, then $V_{\pi_{k+1}}= V_{\pi_j}$, and by monotonicity $V_{\pi_j}= V_{\pi_{j+1}}= \cdots = V_{\pi_{k+1}}$. In particular $V_{\pi_k}= V_{\pi_{k+1}}$.

It remains to show this implies optimality. Since $\pi_{k+1}$ is greedy with respect to $V_{\pi_k}$, [Exercise 3.5](#prob-greedy-equals-b) gives $\mathcal{B}V_{\pi_k}= \mathcal{B}_{\pi_{k+1}}V_{\pi_k}$. Since $V_{\pi_{k+1}}$ is the fixed point of $\mathcal{B}_{\pi_{k+1}}$ and $V_{\pi_k}= V_{\pi_{k+1}}$, we get $\mathcal{B}_{\pi_{k+1}}V_{\pi_k}= V_{\pi_k}$. Combining: $\mathcal{B}V_{\pi_k}= V_{\pi_k}$, so $\pi_{k}$ is optimal by [Exercise 4.1](#prob-when-equality).

</Solution>

## 5. Bellman convergence rate

[Exercise 3.3](#prob-v-star-exists) showed that the iterates $V_{n} := \mathcal{B}^{n} V_{0}$ converge to $V^{*}$ for any starting $V_{0} \in \mathcal{V}$, but it did not tell us *how fast*, nor how to decide when to stop iterating. We derive some convergence rate bounds ([Puterman 1994](#bib-putermanmarkovdecisionprocesses1994), Chapter 6).

<Exercise id="prob-geometric-decay">
**Exercise 5.1.** Show that for any initial $V_{0} \in \mathcal{V}$, the iterates $V_{n} := \mathcal{B}^{n} V_{0}$ satisfy

$$
\|V_{n} - V^{*}\|_{\infty} \;\le\; \gamma^{n} \|V_{0} - V^{*}\|_{\infty}.
$$

*Remark.* This bound is not useful as a stopping criterion in practice as it depends on the unknown $V^{*}$.
</Exercise>

<Solution>

Since $V^{*} = \mathcal{B}V^{*}$ and $\mathcal{B}$ is a $\gamma$-contraction ([Exercise 3.2](#prob-b-contraction)),

$$
\|V_{n} - V^{*}\|_{\infty} \;=\; \|\mathcal{B}V_{n-1}- \mathcal{B}V^{*}\|_{\infty} \;\le\; \gamma\, \|V_{n-1}- V^{*}\|_{\infty}.
$$

Iterating $n$ times gives $\|V_{n} - V^{*}\|_{\infty} \le \gamma^{n} \|V_{0} - V^{*}\|_{\infty}$.

</Solution>

<Exercise id="prob-a-priori-bound">
**Exercise 5.2.** Show the **a priori bound**:

$$
\|V_{n} - V^{*}\|_{\infty} \;\le\; \frac{\gamma^{n}}{1-\gamma}\, \|V_{1} - V_{0}\|_{\infty}.
$$

This bound uses only $\|V_{1} - V_{0}\|_{\infty}$ — a quantity computable after a single iteration, independent of $V^{*}$.

*Hint:* write $V^{*} - V_{n} = \sum_{k=n}^{\infty}(V_{k+1}- V_{k})$ (valid since $V_{k} \to V^{*}$), and bound each term using the contraction of $\mathcal{B}$.
</Exercise>

<Solution>

By the contraction property applied repeatedly,

$$
\begin{aligned}\|V_{k+1}- V_{k}\|_{\infty} \;&=\; \|\mathcal{B}V_{k} - \mathcal{B}V_{k-1}\|_{\infty} \;\le\; \gamma\, \|V_{k} - V_{k-1}\|_{\infty} \\&\le\; \cdots \;\le\; \gamma^{k}\, \|V_{1} - V_{0}\|_{\infty}.\end{aligned}
$$

Since $V_{k} \to V^{*}$ ([Exercise 3.3](#prob-v-star-exists)), we have the telescoping identity $V^{*} - V_{n} = \sum_{k=n}^{\infty}(V_{k+1}- V_{k})$. Applying the triangle inequality and the geometric bound above:

$$
\begin{aligned}\|V^{*} - V_{n}\|_{\infty} \;&\le\; \sum_{k=n}^{\infty}\|V_{k+1}- V_{k}\|_{\infty} \;\le\; \sum_{k=n}^{\infty}\gamma^{k}\, \|V_{1} - V_{0}\|_{\infty} \\&=\; \frac{\gamma^{n}}{1-\gamma}\, \|V_{1} - V_{0}\|_{\infty}.\end{aligned}
$$

</Solution>

<Exercise id="prob-a-posteriori-bound">
**Exercise 5.3.** Show the **a posteriori bound**: for $n \ge 1$,

$$
\|V_{n} - V^{*}\|_{\infty} \;\le\; \frac{\gamma}{1-\gamma}\, \|V_{n} - V_{n-1}\|_{\infty}.
$$

*Hint:* telescope from $n$ as in [Exercise 5.2](#prob-a-priori-bound), but bound $\|V_{k+1}- V_{k}\|_{\infty}$ in terms of $\|V_{n} - V_{n-1}\|_{\infty}$ instead.
</Exercise>

<Solution>

*Step 1: bound each successive difference in terms of $\|V_{n} - V_{n-1}\|_{\infty}$.* Apply the contraction property of $\mathcal{B}$ once:

$$
\|V_{n+1}- V_{n}\|_{\infty} \;=\; \|\mathcal{B}V_{n} - \mathcal{B}V_{n-1}\|_{\infty} \;\le\; \gamma\, \|V_{n} - V_{n-1}\|_{\infty}.
$$

Apply it again, chaining with the previous bound:

$$
\|V_{n+2}- V_{n+1}\|_{\infty} \;\le\; \gamma\, \|V_{n+1}- V_{n}\|_{\infty} \;\le\; \gamma^{2}\, \|V_{n} - V_{n-1}\|_{\infty}.
$$

Continuing this pattern, for every $j \ge 0$:

$$
\|V_{n+j+1}- V_{n+j}\|_{\infty} \;\le\; \gamma^{j+1}\, \|V_{n} - V_{n-1}\|_{\infty}.
$$

*Step 2: telescope.* Since $V_{k} \to V^{*}$ ([Exercise 3.3](#prob-v-star-exists)), we have the telescoping identity

$$
V^{*} - V_{n} \;=\; (V_{n+1}- V_{n}) + (V_{n+2}- V_{n+1}) + (V_{n+3}- V_{n+2}) + \cdots.
$$

Applying the triangle inequality and the bounds from Step 1:

$$
\begin{aligned}\|V^{*} - V_{n}\|_{\infty}&\le\; \|V_{n+1}- V_{n}\|_{\infty} \;+\; \|V_{n+2}- V_{n+1}\|_{\infty} \\&\qquad +\; \|V_{n+3}- V_{n+2}\|_{\infty} \;+\; \cdots \\&\le\; \gamma\, \|V_{n} - V_{n-1}\|_{\infty} \;+\; \gamma^{2}\, \|V_{n} - V_{n-1}\|_{\infty} \\&\qquad +\; \gamma^{3}\, \|V_{n} - V_{n-1}\|_{\infty} \;+\; \cdots \\&=\; \bigl(\gamma + \gamma^{2} + \gamma^{3} + \cdots\bigr)\, \|V_{n} - V_{n-1}\|_{\infty} \\&=\; \frac{\gamma}{1-\gamma}\, \|V_{n} - V_{n-1}\|_{\infty}.\end{aligned}
$$

</Solution>

<Exercise id="prob-a-posteriori-tighter">
**Exercise 5.4.** Show that the a posteriori bound of [Exercise 5.3](#prob-a-posteriori-bound) is always at least as tight as the a priori bound of [Exercise 5.2](#prob-a-priori-bound): for all $n \ge 1$,

$$
\frac{\gamma}{1-\gamma}\, \|V_{n} - V_{n-1}\|_{\infty} \;\le\; \frac{\gamma^{n}}{1-\gamma}\, \|V_{1} - V_{0}\|_{\infty}.
$$

*Hint:* bound $\|V_{n} - V_{n-1}\|_{\infty}$ by repeated application of the contraction.
</Exercise>

<Solution>

Apply the contraction property of $\mathcal{B}$ to $V_{n} = \mathcal{B}V_{n-1}$ and $V_{n-1}= \mathcal{B}V_{n-2}$:

$$
\|V_{n} - V_{n-1}\|_{\infty} \;\le\; \gamma\, \|V_{n-1}- V_{n-2}\|_{\infty}.
$$

Continuing this $n-1$ times altogether, we eventually land on $\|V_{1} - V_{0}\|_{\infty}$:

$$
\|V_{n} - V_{n-1}\|_{\infty} \;\le\; \gamma^{n-1}\, \|V_{1} - V_{0}\|_{\infty}.
$$

Multiplying both sides by $\dfrac{\gamma}{1-\gamma}> 0$ preserves the inequality:

$$
\frac{\gamma}{1-\gamma}\, \|V_{n} - V_{n-1}\|_{\infty} \;\le\; \frac{\gamma^{n}}{1-\gamma}\, \|V_{1} - V_{0}\|_{\infty}.
$$

Both bounds from [Exercise 5.3](#prob-a-posteriori-bound) and [Exercise 5.2](#prob-a-priori-bound) upper-bound $\|V_{n} - V^{*}\|_{\infty}$, and the a posteriori one is smaller.

</Solution>

<Exercise id="prob-concrete-bound">
**Exercise 5.5.** Assume $|R(s,a,s')| \le R_{\max}$ for all $s,a,s'$. Show that if we initialize with $V_{0} \equiv 0$, then

$$
\|V_{n} - V^{*}\|_{\infty} \;\le\; \frac{\gamma^{n}}{1-\gamma}\, R_{\max}.
$$

This bound depends only on $n$, $\gamma$, and $R_{\max}$, so it can be evaluated before running a single iteration.
</Exercise>

<Solution>

With $V_{0} \equiv 0$:

$$
V_{1}(s) \;=\; (\mathcal{B}V_{0})(s) \;=\; \max_{a \in \cA}\sum_{s' \in \cS}T(s' \mid s, a)\, R(s,a,s').
$$

Each term is a convex combination of rewards, all bounded in absolute value by $R_{\max}$, so $|V_{1}(s)| \le R_{\max}$ for every $s$, hence $\|V_{1} - V_{0}\|_{\infty} = \|V_{1}\|_{\infty} \le R_{\max}$. Substituting into the a priori bound of [Exercise 5.2](#prob-a-priori-bound):

$$
\|V_{n} - V^{*}\|_{\infty} \;\le\; \frac{\gamma^{n}}{1-\gamma}\, \|V_{1} - V_{0}\|_{\infty} \;\le\; \frac{\gamma^{n}}{1-\gamma}\, R_{\max}.
$$

</Solution>

<Exercise id="prob-bound-tight">
**Exercise 5.6.** Show that the bound of [Exercise 5.5](#prob-concrete-bound) is **tight**: exhibit an MDP in which $\|V_{n} - V^{*}\|_{\infty} = \frac{\gamma^{n}}{1-\gamma}\, R_{\max}$ for every $n \ge 0$ (with $V_{0} \equiv 0$).
</Exercise>

<Solution>

Take $\cS = \{s\}$, $\cA = \{a\}$, $T(s \mid s, a) = 1$, and $R(s, a, s) = R_{\max}$. The Bellman optimality operator collapses to

$$
(\mathcal{B}V)(s) \;=\; R_{\max}+ \gamma\, V(s).
$$

Starting from $V_{0}(s) = 0$ and iterating,

$$
V_{n}(s) \;=\; R_{\max}\bigl(1 + \gamma + \gamma^{2} + \cdots + \gamma^{n-1}\bigr) \;=\; R_{\max}\cdot \frac{1 - \gamma^{n}}{1 - \gamma}.
$$

The fixed point $V^{*}(s)$ solves $V^{*}(s) = R_{\max}+ \gamma\, V^{*}(s)$, giving $V^{*}(s) = R_{\max}/(1-\gamma)$. Therefore

$$
\|V_{n} - V^{*}\|_{\infty} \;=\; V^{*}(s) - V_{n}(s) \;=\; \frac{R_{\max}}{1-\gamma}- \frac{R_{\max}(1 - \gamma^{n})}{1-\gamma}\;=\; \frac{\gamma^{n}}{1-\gamma}\, R_{\max},
$$

so the bound of [Exercise 5.5](#prob-concrete-bound) is attained with equality. No bound in terms of only $n$, $\gamma$, and $R_{\max}$ can be sharper.

</Solution>

*Remark.* Combining [Exercise 5.3](#prob-a-posteriori-bound), [5.2](#prob-a-priori-bound) and [5.5](#prob-concrete-bound) gives a chain of progressively weaker but increasingly upfront-computable bounds:

<Callout type="note">

**Convergence Bounds**

$$
\begin{aligned}\|V_{n} - V^{*}\|_{\infty} \;&\le\; \underbrace{\tfrac{\gamma}{1-\gamma}\, \|V_n - V_{n-1}\|_\infty}_{\text{a~posteriori, tightest}}\;\le\; \underbrace{\tfrac{\gamma^n}{1-\gamma}\, \|V_1 - V_0\|_\infty}_{\text{a~priori}}\\ \;&\le\; \underbrace{\tfrac{\gamma^n}{1-\gamma}\, R_{\max}}_{\text{upfront, assumes } V_0 \equiv 0,\, |R| \le R_{\max}}.\end{aligned}
$$

</Callout>
Each step weakens the bound by replacing realized information with something coarser: first the most recent step size $\|V_{n} - V_{n-1}\|_{\infty}$ with the worst-case geometric decay $\gamma^{n-1}\|V_{1} - V_{0}\|_{\infty}$ (contraction of $\mathcal{B}$ applied $n-1$ times), then the initial step size $\|V_{1} - V_{0}\|_{\infty}$ with the crude reward bound $R_{\max}$. In practice the leftmost bound is significantly tighter, since $\|V_{n} - V_{n-1}\|_{\infty}$ often decays strictly faster than $\gamma^{n-1}\|V_{1} - V_{0}\|_{\infty}$. It also yields a concrete stopping rule: to guarantee $\|V_{n} - V^{*}\|_{\infty} \le \varepsilon$, iterate until $\|V_{n} - V_{n-1}\|_{\infty} \le \frac{1-\gamma}{\gamma}\, \varepsilon$.

## 6. Convergence of Q-learning

The policy improvement theorem from [Section 4](#4-policy-improvement-theorem) shows that we can in principle find an optimal policy in MDPs. However, it makes the uncomfortable assumption that we know the environment dynamics via the transition kernel $T$. In this problem, we prove that $Q$-learning, which does not make such an assumption, converges to the optimal action-value function, from which one can trivially extract an optimal policy by choosing actions greedily.

### Stochastic approximation theorem

We will make use of the following stochastic approximation result, which we state without proof:

<Theorem id="thm-stochastic-approx">

**Theorem 6.1 (Stochastic Approximation for Contractions ([Tsitsiklis 1994](#bib-tsitsiklis1994), Theorem 3)).** Let $\mathcal{X}= \{x : I \to \mathbb{R}\}$ be the space of real-valued functions on a finite set $I$, equipped with the sup-norm $\|x\|_{\infty} = \max_{i} |x(i)|$. Let $F : \mathcal{X}\to \mathcal{X}$ be a contraction mapping with factor $\gamma \in [0,1)$ and unique fixed point $x^{*}$.

Fix an initial iterate $x_{0} \in \mathcal{X}$, and for each $t \geq 0$ let $\alpha_{t} : I \to [0,1]$ be a **learning rate** function and $w_{t} : I \to \mathbb{R}$ a random **noise** function (both functions on $I$, one value per coordinate). Consider the stochastic iteration

$$
x_{t+1}(i) = (1 - \alpha_{t}(i))\, x_{t}(i) + \alpha_{t}(i)\bigl[F(x_{t})(i) + w_{t}(i)\bigr] \qquad \text{for all }i \in I,
$$

where updates are applied to a single coordinate $i = i_{t}$ at each step (i.e. $\alpha_{t}(i) = 0$ for $i \neq i_{t}$). Suppose:

**(a)** **(Learning rate)** For each $i \in I$:

$$
\sum_{t=0}^{\infty}\alpha_{t}(i) = \infty, \qquad \sum_{t=0}^{\infty}\alpha_{t}(i)^{2} < \infty, \qquad \alpha_{t}(i) \in [0,1].
$$

**(b)** **(Noise)** For each $i \in I$, conditioned on the history $\mathcal{F}_{t} = \{x_{0}, \alpha_{0}, w_{0}, \alpha_{1}, w_{1}, \ldots, \alpha_{t-1}, w_{t-1}, x_{t}, \alpha_{t}\}$, the noise has zero mean and bounded variance:

$$
\mathbb{E}\big[w_{t}(i) \mid \mathcal{F}_{t}\big] = 0, \qquad \mathbb{E}\big[w_{t}(i)^{2} \mid \mathcal{F}_{t}\big] \le C\bigl(1 + \|x_{t}\|_{\infty}^{2}\bigr)
$$

for some constant $C > 0$.

Then $x_{t}(i) \to x^{*}(i)$ for all $i \in I$, with probability $1$.

</Theorem>

*What is stochastic?* The randomness of the iteration is carried by the noise: each $w_{t}(i)$ is a real-valued random variable, and $w_{t}$ is a random element of $\mathbb{R}^{I}$. Consequently, the iterates $x_{1}, x_{2}, \ldots$ are random (they depend on past noise $w_{0}, \ldots, w_{t-1}$), and the learning rates $\alpha_{t}(i)$ may be random as well if they depend on the history—e.g. on which coordinate was just visited. The contraction $F$, its fixed point $x^{*}$, the update rule itself, and the initial iterate $x_{0}$ are all deterministic. The theorem asserts that despite the noise, the random sequence $(x_{t})$ converges pointwise to $x^{*}$ almost surely.

*Remark on "with probability $1$".* The conclusion $x_{t}(i) \to x^{*}(i)$ with probability $1$ (also called **almost sure convergence**) means

$$
P\!\left(\lim_{t \to \infty}x_{t}(i) = x^{*}(i)\right) = 1 \quad \text{for all }i \in I.
$$

In other words, the probability that a run of the stochastic iteration fails to converge to $x^{*}$ is zero.

*Why should we believe this?* It helps to build up the result in three layers of increasing complexity.

**Layer 1: no noise, all coordinates at once.** If $w_{t} = 0$ and $\alpha_{t}(i) = 1$ for all $i$ and $t$, the iteration reduces to $x_{t+1}= F(x_{t})$. This converges to $x^{*}$ by [Theorem 3.1](#thm-banach).

**Layer 2: noise, but all coordinates at once.** Now suppose we observe $F(x_{t}) + w_{t}$ instead of $F(x_{t})$, and use a decreasing step size:

$$
x_{t+1}= (1 - \alpha_{t})\,x_{t} + \alpha_{t}\bigl[F(x_{t}) + w_{t}\bigr] = x_{t} + \alpha_{t}\bigl[\underbrace{F(x_t) - x_t}_{\text{signal}}+ \underbrace{w_t}_{\text{noise}}\bigr].
$$

The signal $F(x_{t}) - x_{t}$ always points toward $x^{*}$ (this is what the contraction property buys us). The noise $w_{t}$ is mean-zero, so it pushes us in random directions that partially cancel over time. The two conditions on the step size mediate between signal and noise:

- $\sum \alpha_{t} = \infty$ ensures the total step size is large enough to reach $x^{*}$ from any starting point.
- $\sum \alpha_{t}^{2} < \infty$ ensures the noise averages out. Each noise term $w_{t}$ enters the iteration scaled by $\alpha_{t}$, contributing a random displacement of size $\alpha_{t} w_{t}$. Although these displacements are not independent (each depends on the current iterate $x_{t}$), they are mean-zero conditioned on the past. For such sequences, the variance of the cumulative sum is the sum of the individual variances, which is proportional to $\sum \alpha_{t}^{2}$. Since this is finite, the total random drift converges and cannot overwhelm the steady pull of the signal toward $x^{*}$.

The signal accumulates coherently (always pulling toward $x^{*}$), while the noise averages out.

**Layer 3: one coordinate at a time.** The iteration updates only one coordinate $i = i_{t}$ per step, while the others stay frozen. This makes the analysis more difficult since the target $F(x_{t})(i)$ depends on all coordinates, including stale ones. The condition $\sum_{t} \alpha_{t}(i) = \infty$ for each $i$ ensures no coordinate is permanently neglected, and the contraction property of $F$ provides enough global coupling to prevent coordinates from drifting apart. Making this rigorous is the main technical content of the proof.

### The problem

Consider the following generalization of the Q-learning update from the ARENA materials, now with a time-varying learning rate $\alpha_{t} > 0$: given a current estimate $Q_{t} : \cS \times \cA \to \mathbb{R}$ and an observed transition $(s_{t}, a_{t}, r_{t+1}, s_{t+1})$ where $s_{t+1}\sim T(\cdot \mid s_{t}, a_{t})$ and $r_{t+1}= R(s_{t}, a_{t}, s_{t+1})$, the update is

<Callout type="note">

**Q-Learning Update**

$$
Q_{t+1}(s_{t}, a_{t}) = Q_{t}(s_{t}, a_{t}) + \alpha_{t}\bigl(r_{t+1}+ \gamma \max_{a' \in \cA}Q_{t}(s_{t+1}, a') - Q_{t}(s_{t}, a_{t})\bigr),
$$

</Callout>
with $Q_{t+1}(s,a) = Q_{t}(s,a)$ for all $(s,a) \neq (s_{t}, a_{t})$. We will show that, under appropriate conditions, Q-learning converges to the optimal action-value function $Q^{*}$.

Let $\mathcal{Q}= \{Q : \cS \times \cA \to \mathbb{R}\}$ denote the space of action-value functions, equipped with the sup-norm $\|Q\|_{\infty} = \max_{s,a}|Q(s,a)|$.

<Exercise id="prob-bq-contraction">
**Exercise 6.1.** Overloading the notation from [Definition 3.2](#def-bellman-op), define the **Bellman optimality operator** on action-value functions, $\mathcal{B}: \mathcal{Q}\to \mathcal{Q}$, by
<Callout type="note">

**Bellman Q-Operator**

$$
(\mathcal{B}Q)(s,a) \coloneqq \sum_{s' \in \cS}T(s' \mid s, a)\bigl[R(s,a,s') + \gamma \max_{a' \in \cA}Q(s', a')\bigr].
$$

</Callout>
(Here $\mathcal{B}$ takes a $Q$-function to a $Q$-function, whereas the earlier $\mathcal{B}$ in [Definition 3.2](#def-bellman-op) takes a $V$-function to a $V$-function — whether $\mathcal{B}$ denotes the $V$- or $Q$-version is always clear from its argument.) Show that $\mathcal{B}$ is a $\gamma$-contraction on $(\mathcal{Q}, \|\cdot\|_{\infty})$.

*Hint:* this is similar to the proof of [Exercise 3.2](#prob-b-contraction).
</Exercise>

<Solution>

Fix $Q, Q' \in \mathcal{Q}$ and $(s,a) \in \cS \times \cA$. By the inequality from [Exercise 3.1](#prob-max-ineq) (applied at each $s'$) and the triangle inequality:

$$
\begin{aligned}&\bigl|(\mathcal{B}Q)(s,a) - (\mathcal{B}Q')(s,a)\bigr| \\&\quad= \left|\sum_{s'}T(s' \mid s,a)\,\gamma\Bigl(\max_{a'}Q(s',a') - \max_{a'}Q'(s',a')\Bigr)\right| \\&\quad\le \sum_{s'}T(s' \mid s,a)\,\gamma\,\max_{a'}\bigl|Q(s',a') - Q'(s',a')\bigr| \\&\quad\le \sum_{s'}T(s' \mid s,a)\,\gamma\,\max_{a', s''}\bigl|Q(s'',a') - Q'(s'',a')\bigr| \\&\quad\le \gamma\,\|Q - Q'\|_{\infty}.\end{aligned}
$$

Taking the maximum over $(s,a)$ gives $\|\mathcal{B}Q - \mathcal{B}Q'\|_{\infty} \le \gamma\,\|Q - Q'\|_{\infty}$.

</Solution>

<Exercise id="prob-bellman-opt-q">
**Exercise 6.2.** Define $Q^{*} \coloneqq Q_{\pi^*}$, the action-value function of the optimal policy $\pi^{*}$ from [Section 3](#3-bellman-operators-and-the-existence-of-optimal-policies). We now show Bellman optimality equations and their consequences.

**(a)** Show that $Q^{*}(s,a) = \sum_{s' \in \cS}T(s' \mid s, a)\bigl[R(s,a,s') + \gamma\, V^{*}(s')\bigr]$.

**(b)** Show that $V^{*}(s) = \max_{a \in \cA}Q^{*}(s,a)$.

**(c)** Conclude that $Q^{*}$ is the unique fixed point of $\mathcal{B}$.
</Exercise>

<Solution>

**(a)** By [Exercise 1.2(b)](#prob-q-function) applied to $\pi^{*}$:

$$
Q_{\pi^*}(s,a) = \sum_{s' \in \cS}T(s' \mid s,a)\bigl[R(s,a,s') + \gamma\, V_{\pi^*}(s')\bigr].
$$

By [Exercise 3.6](#prob-v-pi-star), $V_{\pi^*}= V^{*}$. Substituting gives the result.

**(b)** By [Exercise 1.2(a)](#prob-q-function), $V_{\pi^*}(s) = \sum_{a}\pi^{*}(a \mid s)\, Q_{\pi^*}(s,a)$. Since $\pi^{*}$ is the greedy policy with respect to $V^{*}$ ([Exercise 3.5](#prob-greedy-equals-b) and [3.6](#prob-v-pi-star)), it is deterministic and selects $\pi^{*}(s) \in \argmax_{a} \sum_{s'}T(s' \mid s,a)[R(s,a,s') + \gamma\, V^{*}(s')]$. By [Exercise 6.2(a)](#prob-bellman-opt-q), the inner expression equals $Q^{*}(s,a)$, so $\pi^{*}(s) \in \argmax_{a} Q^{*}(s,a)$. Since $\pi^{*}$ is deterministic, $V^{*}(s) = V_{\pi^*}(s) = Q_{\pi^*}(s, \pi^{*}(s)) = Q^{*}(s, \pi^{*}(s)) = \max_{a} Q^{*}(s,a)$.

**(c)** Substituting [Exercise 6.2(b)](#prob-bellman-opt-q) into [Exercise 6.2(a)](#prob-bellman-opt-q):

$$
Q^{*}(s,a) = \sum_{s'}T(s' \mid s,a)\bigl[R(s,a,s') + \gamma \max_{a'}Q^{*}(s',a')\bigr] = (\mathcal{B}Q^{*})(s,a).
$$

So $Q^{*}$ is a fixed point of $\mathcal{B}$. Uniqueness follows from [Exercise 6.1](#prob-bq-contraction) and [Theorem 3.1](#thm-banach).

</Solution>

<Exercise id="prob-identify-sa">
**Exercise 6.3.** Rewrite the Q-learning update in the form of [Theorem 6.1](#thm-stochastic-approx):

$$
x_{t+1}(i) = (1 - \alpha_{t}(i))\, x_{t}(i) + \alpha_{t}(i)\bigl[F(x_{t})(i) + w_{t}(i)\bigr].
$$

Specifically, identify the index set $I$, the mapping $F$, the iterates $x_{t}$, and the learning rates $\alpha_{t}(i)$. Then give an explicit expression for the noise $w_{t}$.
</Exercise>

<Solution>

The identifications are:

- Index set: $I = \cS \times \cA$.
- Iterates: $x_{t} = Q_{t}$.
- Contraction: $F = \mathcal{B}$, with fixed point $x^{*} = Q^{*}$ ([Exercise 6.2](#prob-bellman-opt-q)).
- Learning rates: $\alpha_{t}(s,a) = \alpha_{t} \cdot \llbracket (s,a) = (s_{t}, a_{t}) \rrbracket$.

With these identifications, the Q-learning update becomes

$$
Q_{t+1}(s,a) = (1 - \alpha_{t}(s,a))\, Q_{t}(s,a) + \alpha_{t}(s,a)\bigl[(\mathcal{B}Q_{t})(s,a) + w_{t}(s,a)\bigr],
$$

where the noise at the updated coordinate is

$$
w_{t}(s_{t}, a_{t}) = R(s_{t}, a_{t}, s_{t+1}) + \gamma \max_{a'}Q_{t}(s_{t+1}, a') - (\mathcal{B}Q_{t})(s_{t}, a_{t}),
$$

i.e. the difference between the sampled target (using the single transition $s_{t+1}$) and its expectation over all possible transitions. For $(s,a) \neq (s_{t}, a_{t})$, we set $w_{t}(s,a) = 0$.

</Solution>

<Exercise id="prob-noise-zero-mean">
**Exercise 6.4.** Show that the noise satisfies $\mathbb{E}[w_{t}(s,a) \mid \mathcal{F}_{t}] = 0$ for all $(s,a) \in \cS \times \cA$, where $\mathcal{F}_{t}$ denotes the history up to time $t$ as in [Theorem 6.1](#thm-stochastic-approx).

*Hint:* conditioned on $\mathcal{F}_{t}$, the quantities $Q_{t}$, $s_{t}$, and $a_{t}$ are all determined. What is the only remaining source of randomness?
</Exercise>

<Solution>

Conditioned on $\mathcal{F}_{t}$, the quantities $Q_{t}$, $s_{t}$, $a_{t}$ are all determined. The only remaining randomness is in $s_{t+1}\sim T(\cdot \mid s_{t}, a_{t})$. Therefore:

$$
\begin{aligned}&\mathbb{E}[w_{t}(s_{t}, a_{t}) \mid \mathcal{F}_{t}] \\&\quad= \mathbb{E}\bigl[R(s_{t}, a_{t}, s_{t+1}) + \gamma \max_{a'}Q_{t}(s_{t+1}, a') \mid \mathcal{F}_{t}\bigr] - (\mathcal{B}Q_{t})(s_{t}, a_{t}) \\&\quad= \sum_{s'}T(s' \mid s_{t}, a_{t})\bigl[R(s_{t}, a_{t}, s') + \gamma \max_{a'}Q_{t}(s', a')\bigr] - (\mathcal{B}Q_{t})(s_{t}, a_{t}) \\&\quad= (\mathcal{B}Q_{t})(s_{t}, a_{t}) - (\mathcal{B}Q_{t})(s_{t}, a_{t}) = 0.\end{aligned}
$$

For $(s,a) \neq (s_{t}, a_{t})$, we have $w_{t}(s,a) = 0$ by definition, so $\mathbb{E}[w_{t}(s,a) \mid \mathcal{F}_{t}] = 0$ trivially.

</Solution>

<Exercise id="prob-noise-bounded-var">
**Exercise 6.5.** Assume $|R(s,a,s')| \le R_{\max}$ for all $s, a, s'$. Show that there exists a constant $C > 0$ (depending only on $R_{\max}$ and $\gamma$) such that

$$
\mathbb{E}\bigl[w_{t}(s,a)^{2} \mid \mathcal{F}_{t}\bigr] \le C\bigl(1 + \|Q_{t}\|_{\infty}^{2}\bigr).
$$

*Hint:* first show that $|w_{t}(s_{t}, a_{t})| \le 2(R_{\max}+ \gamma\, \|Q_{t}\|_{\infty})$.
</Exercise>

<Solution>

*Step 1: a pointwise bound on $w_{t}$.* Using $|R(s_{t}, a_{t}, s_{t+1})| \le R_{\max}$ and $|\max_{a'}Q_{t}(s_{t+1}, a')| \le \|Q_{t}\|_{\infty}$, the sampled target satisfies

$$
\bigl|R(s_{t}, a_{t}, s_{t+1}) + \gamma \max_{a'}Q_{t}(s_{t+1}, a')\bigr| \le R_{\max}+ \gamma\,\|Q_{t}\|_{\infty}.
$$

The same bound holds for $|(\mathcal{B}Q_{t})(s_{t}, a_{t})|$, since it is a convex combination (over $s'$) of terms each bounded by $R_{\max}+ \gamma\,\|Q_{t}\|_{\infty}$. By the triangle inequality:

$$
|w_{t}(s_{t}, a_{t})| \;\le\; 2\bigl(R_{\max}+ \gamma\,\|Q_{t}\|_{\infty}\bigr).
$$

This bound holds for *every* realization of $s_{t+1}$, not just in expectation.

*Step 2: passing to the conditional second moment.* Squaring the pointwise bound,

$$
w_{t}(s_{t}, a_{t})^{2} \;\le\; 4\bigl(R_{\max}+ \gamma\,\|Q_{t}\|_{\infty}\bigr)^{2} \quad \text{a.s.}
$$

Taking conditional expectation of both sides given $\mathcal{F}_{t}$ preserves the inequality (monotonicity of conditional expectation):

$$
\mathbb{E}\!\left[w_{t}(s_{t}, a_{t})^{2} \mid \mathcal{F}_{t}\right] \;\le\; \mathbb{E}\!\left[\,4(R_{\max}+ \gamma\,\|Q_{t}\|_{\infty})^{2} \mid \mathcal{F}_{t}\right].
$$

Now we simplify the right-hand side. It is a function of $Q_{t}$ (and the constants $R_{\max}, \gamma$), and $Q_{t}$ is determined once we condition on $\mathcal{F}_{t}$ (recall $\mathcal{F}_{t}$ records $Q_{0}, Q_{1}, \ldots, Q_{t}$). So the right-hand side is **$\mathcal{F}_{t}$-measurable**: given the history, it is a fixed real number, not random. Conditional expectation acts as the identity on $\mathcal{F}_{t}$-measurable quantities — i.e. $\mathbb{E}[Y \mid \mathcal{F}_{t}] = Y$ when $Y$ is $\mathcal{F}_{t}$-measurable — so

$$
\mathbb{E}\!\left[\,4(R_{\max}+ \gamma\,\|Q_{t}\|_{\infty})^{2} \mid \mathcal{F}_{t}\right] \;=\; 4\bigl(R_{\max}+ \gamma\,\|Q_{t}\|_{\infty}\bigr)^{2}.
$$

Combining,

$$
\mathbb{E}\!\left[w_{t}(s_{t}, a_{t})^{2} \mid \mathcal{F}_{t}\right] \;\le\; 4\bigl(R_{\max}+ \gamma\,\|Q_{t}\|_{\infty}\bigr)^{2}.
$$

*Step 3: putting it in the required form.* We want a constant $C$ such that the right-hand side is bounded by $C(1 + \|Q_{t}\|_{\infty}^{2})$. Applying $(a+b)^{2} \le 2(a^{2} + b^{2})$ with $a = R_{\max}$, $b = \gamma\,\|Q_{t}\|_{\infty}$:

$$
\begin{aligned}4\bigl(R_{\max}+ \gamma\,\|Q_{t}\|_{\infty}\bigr)^{2}&\le 8\bigl(R_{\max}^{2} + \gamma^{2}\,\|Q_{t}\|_{\infty}^{2}\bigr) \\&\le 8\max\!\bigl(R_{\max}^{2},\, \gamma^{2}\bigr)\bigl(1 + \|Q_{t}\|_{\infty}^{2}\bigr).\end{aligned}
$$

So $C = 8\max(R_{\max}^{2}, \gamma^{2})$ works. For $(s,a) \neq (s_{t}, a_{t})$, we have $w_{t}(s,a) = 0$, so the bound holds trivially with the same $C$.

</Solution>

<Exercise id="prob-q-learning-converge">
**Exercise 6.6.** Conclude: state the conditions on the learning rate schedule and the exploration policy under which Q-learning converges, i.e. $Q_{t} \to Q^{*}$ with probability $1$. *Remark.* The ARENA implementation uses a constant learning rate $\alpha$, which does not satisfy $\sum_{t} \alpha_{t}(s,a)^{2} < \infty$. In practice, constant-rate Q-learning does not converge exactly but oscillates in a neighbourhood of $Q^{*}$ whose size shrinks with $\alpha$.
</Exercise>

<Solution>

By [Exercises 6.1–6.5](#prob-bq-contraction), the Q-learning iteration satisfies all the hypotheses of [Theorem 6.1](#thm-stochastic-approx), provided the learning rate conditions hold: for each $(s,a) \in \cS \times \cA$,

$$
\sum_{t=0}^{\infty}\alpha_{t}(s,a) = \infty, \qquad \sum_{t=0}^{\infty}\alpha_{t}(s,a)^{2} < \infty, \qquad \alpha_{t}(s,a) \in [0,1].
$$

Under these conditions, [Theorem 6.1](#thm-stochastic-approx) gives $Q_{t} \to Q^{*}$ with probability $1$.

Note that the first condition already implies that each state-action pair $(s,a)$ must be visited infinitely often. A concrete way to achieve all three conditions is to use an exploration policy that visits every $(s,a)$ infinitely often together with a per-coordinate learning rate $\alpha_{t}(s,a) = 1/n_{t}(s,a)$, where $n_{t}(s,a)$ counts the number of visits to $(s,a)$ up to time $t$. This satisfies $\sum \alpha_{t}(s,a) = \sum_{k=1}^{\infty} 1/k = \infty$ and $\sum \alpha_{t}(s,a)^{2} = \sum_{k=1}^{\infty} 1/k^{2} < \infty$.

</Solution>

## 7. Exact policy evaluation

In [Exercise 3.4](#prob-bpi-contraction), we showed that iterating $\mathcal{B}_{\pi}$ converges to $V_{\pi}$; this is the numerical policy evaluation scheme used in the ARENA materials. When the state space is finite and the dynamics $(T, R)$ are known, there is also an *exact* (closed-form) solution: the Bellman equation becomes a linear system that can be solved directly. In this problem we derive that closed form for deterministic policies.

<Definition id="def-matrix-notation">

**Definition 7.1 (Matrix-vector notation for a deterministic policy).** Fix a deterministic policy $\pi$. Treating the value function as a vector in $\mathbb{R}^{|\cS|}$, define:

- $\mathbf{v}^{\pi} \in \mathbb{R}^{|\cS|}$ with $\mathbf{v}^{\pi}_{s} := V_{\pi}(s)$,
- $\mathbf{P}^{\pi} \in \mathbb{R}^{|\cS| \times |\cS|}$ with $\mathbf{P}^{\pi}_{s,s'}:= T(s' \mid s, \pi(s))$ (the **transition matrix** under $\pi$),
- $\mathbf{R}^{\pi} \in \mathbb{R}^{|\cS| \times |\cS|}$ with $\mathbf{R}^{\pi}_{s,s'}:= R(s, \pi(s), s')$ (the **reward matrix**),
- $\mathbf{r}^{\pi} \in \mathbb{R}^{|\cS|}$ with $\mathbf{r}^{\pi}_{s} := \sum_{s'}\mathbf{P}^{\pi}_{s,s'}\, \mathbf{R}^{\pi}_{s,s'}= \sum_{s'}T(s' \mid s, \pi(s))\, R(s, \pi(s), s')$ (the **expected immediate reward**).

</Definition>

<div id="fact-neumann">
<Callout type="note">

**Fact 7.2 (Neumann series).** Equip $\mathbb{R}^{n \times n}$ with the induced $\infty$-norm

$$
\|\mathbf{A}\|_{\infty} \;:=\; \max_{i} \sum_{j} |\mathbf{A}_{ij}| \qquad \text{(maximum absolute row sum).}
$$

If $\|\mathbf{A}\|_{\infty} < 1$, then $\mathbf{I}- \mathbf{A}$ is invertible, and

$$
(\mathbf{I}- \mathbf{A})^{-1}\;=\; \sum_{k=0}^{\infty}\mathbf{A}^{k}.
$$

</Callout>
</div>

<Exercise id="prob-exact-eval-derive">
**Exercise 7.1.** Starting from the Bellman equation ([Exercise 1.1](#prob-bellman-proof)) applied to a deterministic policy $\pi$, show that
<Callout type="note">

**Exact Policy Evaluation**

$$
\mathbf{v}^{\pi} \;=\; (\mathbf{I}- \gamma\, \mathbf{P}^{\pi})^{-1}\, \mathbf{r}^{\pi},
$$

</Callout>
assuming $\mathbf{I}- \gamma\, \mathbf{P}^{\pi}$ is invertible (which we prove in [Exercise 7.2](#prob-exact-eval-invertible)).

*Hint:* specialize the Bellman equation to a deterministic policy and write the resulting system of $|\cS|$ equations in matrix-vector form.
</Exercise>

<Solution>

Since $\pi$ is deterministic, $\pi(a \mid s) = \llbracket a = \pi(s) \rrbracket$, and the Bellman equation from [Exercise 1.1](#prob-bellman-proof) collapses the sum over actions:

$$
V_{\pi}(s) \;=\; \sum_{s' \in \cS}T(s' \mid s, \pi(s))\bigl(R(s, \pi(s), s') + \gamma\, V_{\pi}(s')\bigr).
$$

Splitting the reward and value terms and rewriting with the matrix notation of [Definition 7.1](#def-matrix-notation):

$$
\begin{aligned}\mathbf{v}^{\pi}_{s}&= \sum_{s'}\mathbf{P}^{\pi}_{s,s'}\, \mathbf{R}^{\pi}_{s,s'}+ \gamma \sum_{s'}\mathbf{P}^{\pi}_{s,s'}\, \mathbf{v}^{\pi}_{s'}= \mathbf{r}^{\pi}_{s} + \gamma\, (\mathbf{P}^{\pi} \mathbf{v}^{\pi})_{s}.\end{aligned}
$$

This holds for every $s$, so in vector form

$$
\mathbf{v}^{\pi} \;=\; \mathbf{r}^{\pi} + \gamma\, \mathbf{P}^{\pi} \mathbf{v}^{\pi} \;\;\Longleftrightarrow\;\; (\mathbf{I}- \gamma\, \mathbf{P}^{\pi})\, \mathbf{v}^{\pi} \;=\; \mathbf{r}^{\pi}.
$$

Assuming $\mathbf{I}- \gamma\, \mathbf{P}^{\pi}$ is invertible, left-multiplying by its inverse gives $\mathbf{v}^{\pi} = (\mathbf{I}- \gamma\, \mathbf{P}^{\pi})^{-1}\, \mathbf{r}^{\pi}$.

</Solution>

<Exercise id="prob-exact-eval-invertible">
**Exercise 7.2.** Prove that $\mathbf{I}- \gamma\, \mathbf{P}^{\pi}$ is invertible for any deterministic policy $\pi$ and any $\gamma \in (0, 1)$.

*Hint:* apply [Fact 7.2](#fact-neumann).
</Exercise>

<Solution>

The matrix $\mathbf{P}^{\pi}$ is **row-stochastic**: $\mathbf{P}^{\pi}_{s,s'}\ge 0$ and $\sum_{s'}\mathbf{P}^{\pi}_{s,s'}= \sum_{s'}T(s' \mid s, \pi(s)) = 1$ for every $s$. Therefore

$$
\|\mathbf{P}^{\pi}\|_{\infty} \;=\; \max_{s} \sum_{s'}|\mathbf{P}^{\pi}_{s,s'}| \;=\; \max_{s} \sum_{s'}\mathbf{P}^{\pi}_{s,s'}\;=\; 1,
$$

and so $\|\gamma\, \mathbf{P}^{\pi}\|_{\infty} = \gamma < 1$. By the Neumann series ([Fact 7.2](#fact-neumann)), $\mathbf{I}- \gamma\, \mathbf{P}^{\pi}$ is invertible, with

$$
(\mathbf{I}- \gamma\, \mathbf{P}^{\pi})^{-1}\;=\; \sum_{k=0}^{\infty}(\gamma\, \mathbf{P}^{\pi})^{k} \;=\; \sum_{k=0}^{\infty}\gamma^{k}\, (\mathbf{P}^{\pi})^{k}.
$$

Combining with [Exercise 7.1](#prob-exact-eval-derive),

$$
\mathbf{v}^{\pi} \;=\; \sum_{k=0}^{\infty}\gamma^{k}\, (\mathbf{P}^{\pi})^{k}\, \mathbf{r}^{\pi},
$$

which has a direct interpretation: $(\mathbf{P}^{\pi})^{k} \mathbf{r}^{\pi}$ is the vector of expected rewards exactly $k$ steps into the future under $\pi$, and $\mathbf{v}^{\pi}$ is their discounted sum.

</Solution>

*Remark.* The same derivation extends to stochastic policies by defining $\mathbf{P}^{\pi}_{s,s'}= \sum_{a}\pi(a \mid s)\, T(s' \mid s, a)$ and $\mathbf{r}^{\pi}_{s} = \sum_{a}\pi(a \mid s) \sum_{s'}T(s' \mid s, a)\, R(s, a, s')$. The matrix $\mathbf{P}^{\pi}$ remains row-stochastic, so the argument above applies unchanged.

## References

<div id="bib-putermanmarkovdecisionprocesses1994">

M. L. Puterman (1994). *Markov Decision Processes --- Discrete Stochastic Dynamic Programming*. Wiley.

</div>

<div id="bib-tsitsiklis1994">

John N. Tsitsiklis (1994). *Asynchronous Stochastic Approximation and Q-Learning*. Machine Learning.

</div>

[^1]: Noting that $\cS \times \cA \times \cS$ is a finite set, this implies that the rewards are bounded above by $R_{\text{max}}= \max_{s,a,s'}R(s,a,s')$.