Iliad Intensive Curriculum

What you’ll learn

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.

Setup

In this exercise sheet, we prove a variety of results that are behind the ARENA Intro to RL materials.

An agent interacts with an environment in discrete time steps $t = 0, 1, 2, \dots$ . On timestep $t$ , the agent observes the current state $s_{t} \in S$ and selects an action $a_{t} \in A$ according to its policy. The environment then responds with a reward $r_{t + 1} \in R$ and a new state $s_{t + 1} \in S$ . (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 0.1 (Spaces and notation). - $S$ — finite state space

$A$ — finite action space
$γ \in (0, 1)$ — discount factor
$Δ X$ — set of all probability distributions over a set $X$
$[[P]]$ — Iverson bracket: $1$ if $P$ is true, $0$ if false

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

$T : S \times A \to Δ S$ is the transition kernel: given state $s$ and action $a$ , the next state is drawn $s^{'} \sim T (\cdot ∣ s, a)$ .
$R : S \times A \times S \to R$ is the reward function: on a transition from $s$ to $s^{'}$ under action $a$ , the agent receives reward $R (s, a, s^{'})$ . ¹

Definition 0.3 (Policy). A policy $π : S \to Δ A$ maps each state to a probability distribution over actions. Given state $s$ :

$π (\cdot ∣ s)$ is a distribution over $A$ ,
$π (a ∣ s) \in [0, 1]$ is the probability of choosing action $a$ ,
the agent samples $a \sim π (\cdot ∣ s)$ .

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

Definition 0.4 (Trajectory). When policy $π$ 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}, \dots)$ is generated by

a_{k} \sim π (\cdot ∣ s_{k}), s_{k + 1} \sim T (\cdot ∣ s_{k}, a_{k}), r_{k + 1} = R (s_{k}, a_{k}, s_{k + 1}),

for $k = 0, 1, 2, \dots$ . We write $E_{π} [\cdot]$ for expectations over such trajectories.

1. The Bellman equation

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

G_{t} := k = t + 1 \sum \infty γ^{k - t - 1} r_{k} = r_{t + 1} + γ r_{t + 2} + γ^{2} r_{t + 3} + \dots .

It satisfies the recursion

G_{t} = r_{t + 1} + γ G_{t + 1} .

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

V_{π} (s) = E_{π} [G_{t} ∣ s_{t} = s] = E_{π} [r_{t + 1} + γ r_{t + 2} + γ^{2} r_{t + 3} + \dots s_{t} = s] = a_{t} \in A \sum π (a_{t} ∣ s) s_{t + 1} \in S \sum T (s_{t + 1} ∣ s, a_{t}) a_{t + 1} \in A \sum π (a_{t + 1} ∣ s_{t + 1}) s_{t + 2} \in S \sum T (s_{t + 2} ∣ s_{t + 1}, a_{t + 1}) \dots [R (s, a_{t}, s_{t + 1}) + γ R (s_{t + 1}, a_{t + 1}, s_{t + 2}) + γ^{2} R (s_{t + 2}, a_{t + 2}, s_{t + 3}) + \dots] .

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

Exercise 1.1. Prove the Bellman equation: for all $s \in S$ ,

Bellman Equation

V_{π} (s) = a \in A \sum π (a ∣ s) s^{'} \in S \sum T (s^{'} ∣ s, a) (R (s, a, s^{'}) + γ V_{π} (s^{'})) .

Hint: condition on the first action and the first transition, then separate the immediate reward from the remaining return.

Solution

Starting from the definition of $V_{π}$ and using the recursion $G_{t} = r_{t + 1} + γ G_{t + 1}$ :

V_{π} (s) = E_{π} [G_{t} ∣ s_{t} = s] = E_{π} [r_{t + 1} + γ G_{t + 1} ∣ s_{t} = s] .

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

V_{π} (s) = a \in A \sum π (a ∣ s) s^{'} \in S \sum T (s^{'} ∣ s, a) \times E_{π} [r_{t + 1} + γ G_{t + 1} ∣ s_{t} = s, a_{t} = a, s_{t + 1} = s^{'}] .

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

E_{π} [G_{t + 1} ∣ s_{t} = s, a_{t} = a, s_{t + 1} = s^{'}] = E_{π} [G_{t + 1} ∣ s_{t + 1} = s^{'}] = V_{π} (s^{'}) .

Substituting both back gives

V_{π} (s) = a \in A \sum π (a ∣ s) s^{'} \in S \sum T (s^{'} ∣ s, a) (R (s, a, s^{'}) + γ V_{π} (s^{'})) .

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

Q_{π} (s, a) = E_{π} [G_{t} ∣ s_{t} = s, a_{t} = a] .

Exercise 1.2. (a) Express $V_{π} (s)$ in terms of $Q_{π}$ .

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

(c) Using these relations, derive a recursive equation for $Q_{π}$ analogous to the Bellman equation above.

Solution

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

V_{π} (s) = E_{π} [G_{t} ∣ s_{t} = s] = a \in A \sum π (a ∣ s) E_{π} [G_{t} ∣ s_{t} = s, a_{t} = a] = a \in A \sum π (a ∣ s) Q_{π} (s, a) .

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

Q_{π} (s, a) = E_{π} [G_{t} ∣ s_{t} = s, a_{t} = a] = s^{'} \in S \sum T (s^{'} ∣ s, a) E_{π} [r_{t + 1} + γ G_{t + 1} ∣ s_{t} = s, a_{t} = a, s_{t + 1} = s^{'}] = s^{'} \in S \sum T (s^{'} ∣ s, a) (R (s, a, s^{'}) + γ V_{π} (s^{'})),

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 $E_{π} [G_{t + 1} ∣ s_{t + 1} = s^{'}] = V_{π} (s^{'})$ .

(c) Substituting Exercise 1.2(a) into Exercise 1.2(b), replacing $V_{π} (s^{'})$ by its expression in terms of $Q_{π}$ :

Q_{π} (s, a) = s^{'} \in S \sum T (s^{'} ∣ s, a) (R (s, a, s^{'}) + γ a^{'} \in A \sum π (a^{'} ∣ s^{'}) Q_{π} (s^{'}, a^{'})) .

This is the Bellman equation for the action-value function. Note also that substituting Exercise 1.2(b) into Exercise 1.2(a) recovers the Bellman equation for $V_{π}$ from Exercise 1.1.

2. An example MDP

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

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 $π_{L}$ denote the policy that always selects $a_{L}$ , and $π_{R}$ the policy that always selects $a_{R}$ .

Exercise 2.1. Using the Bellman equation from Exercise 1.1, verify that

V_{π_{L}} (s_{0}) = \frac{1}{1 - γ ^{2}}, V_{π_{R}} (s_{0}) = \frac{2 γ}{1 - γ ^{2}} .

Solution

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

V_{π_{L}} (s_{0}) V_{π_{L}} (s_{L}) = R (s_{0}, a_{L}, s_{L}) + γ V_{π_{L}} (s_{L}) = 1 + γ V_{π_{L}} (s_{L}), = R (s_{L}, a_{L}, s_{0}) + γ V_{π_{L}} (s_{0}) = 0 + γ V_{π_{L}} (s_{0}) .

Substituting the second into the first gives $V_{π_{L}} (s_{0}) = 1 + γ^{2} V_{π_{L}} (s_{0})$ , hence

V_{π_{L}} (s_{0}) = \frac{1}{1 - γ ^{2}} .

Similarly, under $π_{R}$ :

V_{π_{R}} (s_{0}) V_{π_{R}} (s_{R}) = R (s_{0}, a_{R}, s_{R}) + γ V_{π_{R}} (s_{R}) = 0 + γ V_{π_{R}} (s_{R}), = R (s_{R}, a_{R}, s_{0}) + γ V_{π_{R}} (s_{0}) = 2 + γ V_{π_{R}} (s_{0}) .

Substituting yields $V_{π_{R}} (s_{0}) = γ (2 + γ V_{π_{R}} (s_{0})) = 2 γ + γ^{2} V_{π_{R}} (s_{0})$ , hence

V_{π_{R}} (s_{0}) = \frac{2 γ}{1 - γ ^{2}} .

Exercise 2.2. Determine the best action from state $s_{0}$ as a function of the discount factor $γ \in (0, 1)$ . Show that the breakeven point is $γ = \frac{1}{2}$ .

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_{π_{L}} (s_{0})$ and $V_{π_{R}} (s_{0})$ suffices:

V_{π_{L}} (s_{0}) - V_{π_{R}} (s_{0}) = \frac{1 - 2 γ}{1 - γ ^{2}} .

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

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

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 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 $γ \in [0, 1)$ such that

d (F (x), F (y)) \leq γ d (x, y) 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$ .

The problem

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

(B V) (s) : = a \in A max s^{'} \in S \sum T (s^{'} ∣ s, a) (R (s, a, s^{'}) + γ V (s^{'})) .

Exercise 3.1. Let $f, g : A \to R$ be real-valued functions on a finite set $A$ . Prove that

a \in A max f (a) - a \in A max g (a) \leq a \in A max ∣ f (a) - g (a) ∣.

Solution

Without loss of generality, assume $max_{a} f (a) \geq max_{a} g (a)$ . Let $a^{*} \in arg max_{a \in A} f (a)$ . Then:

a \in A max f (a) - a \in A max g (a) = a \in A max f (a) - a \in A max g (a) = f (a^{*}) - a \in A max g (a) \leq f (a^{*}) - g (a^{*}) = ∣ f (a^{*}) - g (a^{*}) ∣ \leq a \in A max ∣ f (a) - g (a) ∣.

Exercise 3.2. Using Exercise 3.1, prove that $B$ is a contraction mapping with contraction factor $γ$ , i.e. for all $V, W \in V$ ,

∥ B V - B W ∥_{\infty} \leq γ ∥ V - W ∥_{\infty} .

Solution

Fix an arbitrary state $s \in S$ . Define for each $a \in A$ :

f (a) g (a) : = s^{'} \in S \sum T (s^{'} ∣ s, a) (R (s, a, s^{'}) + γ V (s^{'})), : = s^{'} \in S \sum T (s^{'} ∣ s, a) (R (s, a, s^{'}) + γ W (s^{'})) .

Then $(B V) (s) = max_{a} f (a)$ and $(B W) (s) = max_{a} g (a)$ . By Exercise 3.1:

(B V) (s) - (B W) (s) \leq a \in A max f (a) - g (a) = a \in A max s^{'} \in S \sum T (s^{'} ∣ s, a) γ (V (s^{'}) - W (s^{'})) \leq γ a \in A max s^{'} \in S \sum T (s^{'} ∣ s, a) V (s^{'}) - W (s^{'}) \leq γ a \in A max s^{'} \in S \sum T (s^{'} ∣ s, a) ∥ V - W ∥_{\infty} \leq γ ∥ V - W ∥_{\infty},

where the last step uses $\sum_{s^{'}} T (s^{'} ∣ s, a) = 1$ . Since this holds for every $s \in S$ , taking the maximum over $s$ gives $∥ B V - B W ∥_{\infty} \leq γ ∥ V - W ∥_{\infty}$ .

Exercise 3.3. Using Theorem 3.1, conclude that there exists a unique $V^{*} \in V$ satisfying $B V^{*} = V^{*}$ , and that for any initial $V_{0} \in V$ , the iterates $B^{n} V_{0} \to V^{*}$ as $n \to \infty$ .

Solution

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

Exercise 3.4. Show that for any policy $π$ , the operator $B_{π} : V \to V$ defined by

Bellman Policy Operator

(B_{π} V) (s) : = a \in A \sum π (a ∣ s) s^{'} \in S \sum T (s^{'} ∣ s, a) (R (s, a, s^{'}) + γ V (s^{'}))

is also a contraction with factor $γ$ . Conclude that $V_{π}$ is its unique fixed point and that $B_{π}^{n} V_{0} \to V_{π}$ for any initial $V_{0} \in V$ as $n \to \infty$ .

Remark. This shows that the numerical policy evaluation algorithm from the ARENA materials converges to the correct solution.

Solution

Fix $V, W \in V$ and an arbitrary state $s \in S$ . Then:

(B_{π} V) (s) - (B_{π} W) (s) = a \in A \sum π (a ∣ s) s^{'} \in S \sum T (s^{'} ∣ s, a) γ (V (s^{'}) - W (s^{'})) \leq γ a \in A \sum π (a ∣ s) s^{'} \in S \sum T (s^{'} ∣ s, a) V (s^{'}) - W (s^{'}) \leq γ a \in A \sum π (a ∣ s) s^{'} \in S \sum T (s^{'} ∣ s, a) ∥ V - W ∥_{\infty} \leq γ ∥ V - W ∥_{\infty},

where the last step uses $\sum_{s^{'}} T (s^{'} ∣ s, a) = 1$ and $\sum_{a} π (a ∣ s) = 1$ . Taking the maximum over $s$ gives $∥ B_{π} V - B_{π} W ∥_{\infty} \leq γ ∥ V - W ∥_{\infty}$ , so $B_{π}$ is a contraction with factor $γ$ .

By Theorem 3.1, $B_{π}$ has a unique fixed point. By the Bellman equation (Section 1), $V_{π}$ satisfies $B_{π} V_{π} = V_{π}$ , so $V_{π}$ is this unique fixed point. The convergence statement also follows from Theorem 3.1.

Exercise 3.5. Let $V \in V$ be any value function, and let $π_{V}$ be a greedy policy with respect to $V$ , i.e.

π_{V} (s) \in a \in A arg max s^{'} \in S \sum T (s^{'} ∣ s, a) (R (s, a, s^{'}) + γ V (s^{'})) .

Show that $B_{π_{V}} V = B V$ .

Solution

Since $π_{V}$ is deterministic, $π_{V} (a ∣ s) = [[a = π_{V} (s)]]$ , so the sum over $a$ in $B_{π_{V}}$ collapses to the single term $a = π_{V} (s)$ . For every $s \in S$ :

(B_{π_{V}} V) (s) = s^{'} \in S \sum T (s^{'} ∣ s, π_{V} (s)) (R (s, π_{V} (s), s^{'}) + γ V (s^{'})) = a \in A max s^{'} \in S \sum T (s^{'} ∣ s, a) (R (s, a, s^{'}) + γ V (s^{'})) = (B V) (s),

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

Exercise 3.6. Define the greedy policy with respect to $V^{*}$ by $π^{*} = π_{V^{*}}$ as in the previous part. Show that $V_{π^{*}} = V^{*}$ , i.e. the value function of $π^{*}$ equals the fixed point of $B$ .

Hint: show that $V^{*}$ satisfies the same fixed-point equation as $V_{π^{*}}$ .

Solution

We have $B_{π^{*}} V^{*} = B V^{*} = V^{*}$ by Exercise 3.5 and Exercise 3.3. So $V^{*}$ is a fixed point of $B_{π^{*}}$ . By Exercise 3.4, $V_{π^{*}}$ is the unique fixed point of $B_{π^{*}}$ . Therefore $V_{π^{*}} = V^{*}$ .

Exercise 3.7. Conclude that $π^{*}$ is an optimal policy: for every policy $π$ and every state $s \in S$ ,

V_{π^{*}} (s) \geq V_{π} (s) .

Hint: show that $B V_{π} \geq V_{π}$ pointwise, then iterate and take the limit.

Solution

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

(B V) (s) \geq (B_{π} V) (s) for all V \in V, s \in S .

In particular, since $V_{π}$ is a fixed point of $B_{π}$ (Exercise 3.4):

(B V_{π}) (s) \geq (B_{π} V_{π}) (s) = V_{π} (s) for all s \in S .

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

V_{π} \leq B V_{π} \leq B^{2} V_{π} \leq \dots \leq B^{n} V_{π} .

By Exercise 3.3, $B^{n} V_{π} \to V^{*}$ as $n \to \infty$ . Taking the limit:

V_{π} (s) \leq V^{*} (s) = V_{π^{*}} (s) for all s \in S,

where the last equality is Exercise 3.6. Since $π$ was arbitrary, $π^{*}$ is optimal.

4. Policy improvement theorem

Given a policy $π$ , define the improved policy $π^{'}$ greedily with respect to $V_{π}$ :

Policy Improvement

π^{'} (s) \in a \in A arg max s^{'} \in S \sum T (s^{'} ∣ s, a) (R (s, a, s^{'}) + γ V_{π} (s^{'})) .

Exercise 4.1. In proving Exercise 3.7, we already saw that for all $s \in S$ , we have $(B V_{π}) (s) \geq V_{π} (s)$ . When does equality hold for all states?

Solution

We have

(B V_{π}) (s) = a \in A max s^{'} \in S \sum T (s^{'} ∣ s, a) (R (s, a, s^{'}) + γ V_{π} (s^{'})) \geq a \in A \sum π (a ∣ s) s^{'} \in S \sum T (s^{'} ∣ s, a) (R (s, a, s^{'}) + γ V_{π} (s^{'})) = V_{π} (s),

where we used the Bellman equation in the last step. If equality holds at every state $s$ , then $V_{π}$ is a fixed point of $B$ , which by uniqueness (Exercise 3.3) means $V_{π} = V^{*} = V_{π^{*}}$ , i.e. $π$ is already optimal by Exercise 3.7.

Exercise 4.2. Show that $V_{π^{'}} (s) \geq V_{π} (s)$ for all $s \in S$ .

Hint: show that $B_{π^{'}} V_{π} \geq V_{π}$ pointwise using Exercise 3.5, then iterate $B_{π^{'}}$ and take the limit.

Solution

By Exercise 3.5, $B_{π^{'}} V_{π} = B V_{π} \geq V_{π}$ pointwise, where the inequality is from Exercise 4.1. Note that $B_{π^{'}}$ is monotone: if $V (s) \geq W (s)$ for all $s$ , then $(B_{π^{'}} V) (s) \geq (B_{π^{'}} W) (s)$ . Applying $B_{π^{'}}$ to both sides and iterating:

V_{π} \leq B_{π^{'}} V_{π} \leq B_{π^{'}}^{2} V_{π} \leq \dots \leq B_{π^{'}}^{n} V_{π} .

By Exercise 3.4, $B_{π^{'}}^{n} V_{π} \to V_{π^{'}}$ as $n \to \infty$ . Taking the limit gives $V_{π^{'}} (s) \geq V_{π} (s)$ for all $s \in S$ .

Exercise 4.3. The policy iteration algorithm generates a sequence of policies $π_{0}, π_{1}, π_{2}, \dots$ where each $π_{k + 1}$ is the greedy policy with respect to $V_{π_{k}}$ . Show that this sequence converges to an optimal policy $π^{*}$ in a finite number of steps.

Hint: how many deterministic policies are there?

Solution

By Exercise 4.2, the sequence of value functions is monotonically improving: $V_{π_{k + 1}} (s) \geq V_{π_{k}} (s)$ for all $s$ and all $k$ . Since each $π_{k}$ is a deterministic policy and there are only $∣ A ∣^{∣ S ∣}$ deterministic policies, the sequence must eventually revisit a policy. If $π_{k + 1} = π_{j}$ for some $j \leq k$ , then $V_{π_{k + 1}} = V_{π_{j}}$ , and by monotonicity $V_{π_{j}} = V_{π_{j + 1}} = \dots = V_{π_{k + 1}}$ . In particular $V_{π_{k}} = V_{π_{k + 1}}$ .

It remains to show this implies optimality. Since $π_{k + 1}$ is greedy with respect to $V_{π_{k}}$ , Exercise 3.5 gives $B V_{π_{k}} = B_{π_{k + 1}} V_{π_{k}}$ . Since $V_{π_{k + 1}}$ is the fixed point of $B_{π_{k + 1}}$ and $V_{π_{k}} = V_{π_{k + 1}}$ , we get $B_{π_{k + 1}} V_{π_{k}} = V_{π_{k}}$ . Combining: $B V_{π_{k}} = V_{π_{k}}$ , so $π_{k}$ is optimal by Exercise 4.1.

5. Bellman convergence rate

Exercise 3.3 showed that the iterates $V_{n} := B^{n} V_{0}$ converge to $V^{*}$ for any starting $V_{0} \in 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, Chapter 6).

Exercise 5.1. Show that for any initial $V_{0} \in V$ , the iterates $V_{n} := B^{n} V_{0}$ satisfy

∥ V_{n} - V^{*} ∥_{\infty} \leq γ^{n} ∥ V_{0} - V^{*} ∥_{\infty} .

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

Solution

Since $V^{*} = B V^{*}$ and $B$ is a $γ$ -contraction (Exercise 3.2),

∥ V_{n} - V^{*} ∥_{\infty} = ∥ B V_{n - 1} - B V^{*} ∥_{\infty} \leq γ ∥ V_{n - 1} - V^{*} ∥_{\infty} .

Iterating $n$ times gives $∥ V_{n} - V^{*} ∥_{\infty} \leq γ^{n} ∥ V_{0} - V^{*} ∥_{\infty}$ .

Exercise 5.2. Show the a priori bound:

∥ V_{n} - V^{*} ∥_{\infty} \leq \frac{γ ^{n}}{1 - γ} ∥ 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 $B$ .

Solution

By the contraction property applied repeatedly,

∥ V_{k + 1} - V_{k} ∥_{\infty} = ∥ B V_{k} - B V_{k - 1} ∥_{\infty} \leq γ ∥ V_{k} - V_{k - 1} ∥_{\infty} \leq \dots \leq γ^{k} ∥ V_{1} - V_{0} ∥_{\infty} .

Since $V_{k} \to V^{*}$ (Exercise 3.3), 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:

∥ V^{*} - V_{n} ∥_{\infty} \leq k = n \sum \infty ∥ V_{k + 1} - V_{k} ∥_{\infty} \leq k = n \sum \infty γ^{k} ∥ V_{1} - V_{0} ∥_{\infty} = \frac{γ ^{n}}{1 - γ} ∥ V_{1} - V_{0} ∥_{\infty} .

Exercise 5.3. Show the a posteriori bound: for $n \geq 1$ ,

∥ V_{n} - V^{*} ∥_{\infty} \leq \frac{γ}{1 - γ} ∥ V_{n} - V_{n - 1} ∥_{\infty} .

Hint: telescope from $n$ as in Exercise 5.2, but bound $∥ V_{k + 1} - V_{k} ∥_{\infty}$ in terms of $∥ V_{n} - V_{n - 1} ∥_{\infty}$ instead.

Solution

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

∥ V_{n + 1} - V_{n} ∥_{\infty} = ∥ B V_{n} - B V_{n - 1} ∥_{\infty} \leq γ ∥ V_{n} - V_{n - 1} ∥_{\infty} .

Apply it again, chaining with the previous bound:

∥ V_{n + 2} - V_{n + 1} ∥_{\infty} \leq γ ∥ V_{n + 1} - V_{n} ∥_{\infty} \leq γ^{2} ∥ V_{n} - V_{n - 1} ∥_{\infty} .

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

∥ V_{n + j + 1} - V_{n + j} ∥_{\infty} \leq γ^{j + 1} ∥ V_{n} - V_{n - 1} ∥_{\infty} .

Step 2: telescope. Since $V_{k} \to V^{*}$ (Exercise 3.3), 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}) + \dots .

Applying the triangle inequality and the bounds from Step 1:

∥ V^{*} - V_{n} ∥_{\infty} \leq ∥ V_{n + 1} - V_{n} ∥_{\infty} + ∥ V_{n + 2} - V_{n + 1} ∥_{\infty} + ∥ V_{n + 3} - V_{n + 2} ∥_{\infty} + \dots \leq γ ∥ V_{n} - V_{n - 1} ∥_{\infty} + γ^{2} ∥ V_{n} - V_{n - 1} ∥_{\infty} + γ^{3} ∥ V_{n} - V_{n - 1} ∥_{\infty} + \dots = (γ + γ^{2} + γ^{3} + \dots) ∥ V_{n} - V_{n - 1} ∥_{\infty} = \frac{γ}{1 - γ} ∥ V_{n} - V_{n - 1} ∥_{\infty} .

Exercise 5.4. Show that the a posteriori bound of Exercise 5.3 is always at least as tight as the a priori bound of Exercise 5.2: for all $n \geq 1$ ,

\frac{γ}{1 - γ} ∥ V_{n} - V_{n - 1} ∥_{\infty} \leq \frac{γ ^{n}}{1 - γ} ∥ V_{1} - V_{0} ∥_{\infty} .

Hint: bound $∥ V_{n} - V_{n - 1} ∥_{\infty}$ by repeated application of the contraction.

Solution

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

∥ V_{n} - V_{n - 1} ∥_{\infty} \leq γ ∥ 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} \leq γ^{n - 1} ∥ V_{1} - V_{0} ∥_{\infty} .

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

\frac{γ}{1 - γ} ∥ V_{n} - V_{n - 1} ∥_{\infty} \leq \frac{γ ^{n}}{1 - γ} ∥ V_{1} - V_{0} ∥_{\infty} .

Both bounds from Exercise 5.3 and Exercise 5.2 upper-bound $∥ V_{n} - V^{*} ∥_{\infty}$ , and the a posteriori one is smaller.

Exercise 5.5. Assume $∣ R (s, a, s^{'}) ∣ \leq R_{m a x}$ for all $s, a, s^{'}$ . Show that if we initialize with $V_{0} \equiv 0$ , then

∥ V_{n} - V^{*} ∥_{\infty} \leq \frac{γ ^{n}}{1 - γ} R_{m a x} .

This bound depends only on $n$ , $γ$ , and $R_{m a x}$ , so it can be evaluated before running a single iteration.

Solution

With $V_{0} \equiv 0$ :

V_{1} (s) = (B V_{0}) (s) = a \in A max s^{'} \in S \sum T (s^{'} ∣ s, a) R (s, a, s^{'}) .

Each term is a convex combination of rewards, all bounded in absolute value by $R_{m a x}$ , so $∣ V_{1} (s) ∣ \leq R_{m a x}$ for every $s$ , hence $∥ V_{1} - V_{0} ∥_{\infty} = ∥ V_{1} ∥_{\infty} \leq R_{m a x}$ . Substituting into the a priori bound of Exercise 5.2:

∥ V_{n} - V^{*} ∥_{\infty} \leq \frac{γ ^{n}}{1 - γ} ∥ V_{1} - V_{0} ∥_{\infty} \leq \frac{γ ^{n}}{1 - γ} R_{m a x} .

Exercise 5.6. Show that the bound of Exercise 5.5 is tight: exhibit an MDP in which $∥ V_{n} - V^{*} ∥_{\infty} = \frac{γ ^{n}}{1 - γ} R_{m a x}$ for every $n \geq 0$ (with $V_{0} \equiv 0$ ).

Solution

Take $S = {s}$ , $A = {a}$ , $T (s ∣ s, a) = 1$ , and $R (s, a, s) = R_{m a x}$ . The Bellman optimality operator collapses to

(B V) (s) = R_{m a x} + γ V (s) .

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

V_{n} (s) = R_{m a x} (1 + γ + γ^{2} + \dots + γ^{n - 1}) = R_{m a x} \cdot \frac{1 - γ ^{n}}{1 - γ} .

The fixed point $V^{*} (s)$ solves $V^{*} (s) = R_{m a x} + γ V^{*} (s)$ , giving $V^{*} (s) = R_{m a x} / (1 - γ)$ . Therefore

∥ V_{n} - V^{*} ∥_{\infty} = V^{*} (s) - V_{n} (s) = \frac{R _{m a x}}{1 - γ} - \frac{R _{m a x} ( 1 - γ ^{n} )}{1 - γ} = \frac{γ ^{n}}{1 - γ} R_{m a x},

so the bound of Exercise 5.5 is attained with equality. No bound in terms of only $n$ , $γ$ , and $R_{m a x}$ can be sharper.

Remark. Combining Exercise 5.3, 5.2 and 5.5 gives a chain of progressively weaker but increasingly upfront-computable bounds:

Convergence Bounds

∥ V_{n} - V^{*} ∥_{\infty} \leq a posteriori, tightest \frac{γ}{1 - γ} ∥ V_{n} - V_{n - 1} ∥_{\infty} \leq a priori \frac{γ ^{n}}{1 - γ} ∥ V_{1} - V_{0} ∥_{\infty} \leq upfront, assumes V_{0} \equiv 0, ∣ R ∣ \leq R_{m a x} \frac{γ ^{n}}{1 - γ} R_{m a x} .

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 $γ^{n - 1} ∥ V_{1} - V_{0} ∥_{\infty}$ (contraction of $B$ applied $n - 1$ times), then the initial step size $∥ V_{1} - V_{0} ∥_{\infty}$ with the crude reward bound $R_{m a x}$ . In practice the leftmost bound is significantly tighter, since $∥ V_{n} - V_{n - 1} ∥_{\infty}$ often decays strictly faster than $γ^{n - 1} ∥ V_{1} - V_{0} ∥_{\infty}$ . It also yields a concrete stopping rule: to guarantee $∥ V_{n} - V^{*} ∥_{\infty} \leq ε$ , iterate until $∥ V_{n} - V_{n - 1} ∥_{\infty} \leq \frac{1 - γ}{γ} ε$ .

6. Convergence of Q-learning

The policy improvement theorem from Section 4 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 6.1 (Stochastic Approximation for Contractions (Tsitsiklis 1994, Theorem 3)). Let $X = {x : I \to 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 : X \to X$ be a contraction mapping with factor $γ \in [0, 1)$ and unique fixed point $x^{*}$ .

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

x_{t + 1} (i) = (1 - α_{t} (i)) x_{t} (i) + α_{t} (i) [F (x_{t}) (i) + w_{t} (i)] for all i \in I,

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

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

t = 0 \sum \infty α_{t} (i) = \infty, t = 0 \sum \infty α_{t} (i)^{2} < \infty, α_{t} (i) \in [0, 1] .

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

E [w_{t} (i) ∣ F_{t}] = 0, E [w_{t} (i)^{2} ∣ F_{t}] \leq C (1 + ∥ x_{t} ∥_{\infty}^{2})

for some constant $C > 0$ .

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

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 $R^{I}$ . Consequently, the iterates $x_{1}, x_{2}, \dots$ are random (they depend on past noise $w_{0}, \dots, w_{t - 1}$ ), and the learning rates $α_{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 (t \to \infty lim x_{t} (i) = x^{*} (i)) = 1 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 $α_{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.

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 - α_{t}) x_{t} + α_{t} [F (x_{t}) + w_{t}] = x_{t} + α_{t} [signal F (x_{t}) - x_{t} + noise w_{t}] .

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 α_{t} = \infty$ ensures the total step size is large enough to reach $x^{*}$ from any starting point.
$\sum α_{t}^{2} < \infty$ ensures the noise averages out. Each noise term $w_{t}$ enters the iteration scaled by $α_{t}$ , contributing a random displacement of size $α_{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 α_{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} α_{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 $α_{t} > 0$ : given a current estimate $Q_{t} : S \times A \to R$ and an observed transition $(s_{t}, a_{t}, r_{t + 1}, s_{t + 1})$ where $s_{t + 1} \sim T (\cdot ∣ s_{t}, a_{t})$ and $r_{t + 1} = R (s_{t}, a_{t}, s_{t + 1})$ , the update is

Q-Learning Update

Q_{t + 1} (s_{t}, a_{t}) = Q_{t} (s_{t}, a_{t}) + α_{t} (r_{t + 1} + γ a^{'} \in A max Q_{t} (s_{t + 1}, a^{'}) - Q_{t} (s_{t}, a_{t})),

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 $Q = {Q : S \times A \to R}$ denote the space of action-value functions, equipped with the sup-norm $∥ Q ∥_{\infty} = max_{s, a} ∣ Q (s, a) ∣$ .

Exercise 6.1. Overloading the notation from Definition 3.2, define the Bellman optimality operator on action-value functions, $B : Q \to Q$ , by

Bellman Q-Operator

(B Q) (s, a) : = s^{'} \in S \sum T (s^{'} ∣ s, a) [R (s, a, s^{'}) + γ a^{'} \in A max Q (s^{'}, a^{'})] .

(Here $B$ takes a $Q$ -function to a $Q$ -function, whereas the earlier $B$ in Definition 3.2 takes a $V$ -function to a $V$ -function — whether $B$ denotes the $V$ - or $Q$ -version is always clear from its argument.) Show that $B$ is a $γ$ -contraction on $(Q, ∥ \cdot ∥_{\infty})$ .

Hint: this is similar to the proof of Exercise 3.2.

Solution

Fix $Q, Q^{'} \in Q$ and $(s, a) \in S \times A$ . By the inequality from Exercise 3.1 (applied at each $s^{'}$ ) and the triangle inequality:

(B Q) (s, a) - (B Q^{'}) (s, a) = s^{'} \sum T (s^{'} ∣ s, a) γ (a^{'} max Q (s^{'}, a^{'}) - a^{'} max Q^{'} (s^{'}, a^{'})) \leq s^{'} \sum T (s^{'} ∣ s, a) γ a^{'} max Q (s^{'}, a^{'}) - Q^{'} (s^{'}, a^{'}) \leq s^{'} \sum T (s^{'} ∣ s, a) γ a^{'}, s^{''} max Q (s^{''}, a^{'}) - Q^{'} (s^{''}, a^{'}) \leq γ ∥ Q - Q^{'} ∥_{\infty} .

Taking the maximum over $(s, a)$ gives $∥ B Q - B Q^{'} ∥_{\infty} \leq γ ∥ Q - Q^{'} ∥_{\infty}$ .

Exercise 6.2. Define $Q^{*} : = Q_{π^{*}}$ , the action-value function of the optimal policy $π^{*}$ from Section 3. We now show Bellman optimality equations and their consequences.

(a) Show that $Q^{*} (s, a) = \sum_{s^{'} \in S} T (s^{'} ∣ s, a) [R (s, a, s^{'}) + γ V^{*} (s^{'})]$ .

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

(c) Conclude that $Q^{*}$ is the unique fixed point of $B$ .

Solution

(a) By Exercise 1.2(b) applied to $π^{*}$ :

Q_{π^{*}} (s, a) = s^{'} \in S \sum T (s^{'} ∣ s, a) [R (s, a, s^{'}) + γ V_{π^{*}} (s^{'})] .

By Exercise 3.6, $V_{π^{*}} = V^{*}$ . Substituting gives the result.

(b) By Exercise 1.2(a), $V_{π^{*}} (s) = \sum_{a} π^{*} (a ∣ s) Q_{π^{*}} (s, a)$ . Since $π^{*}$ is the greedy policy with respect to $V^{*}$ (Exercise 3.5 and 3.6), it is deterministic and selects $π^{*} (s) \in arg max_{a} \sum_{s^{'}} T (s^{'} ∣ s, a) [R (s, a, s^{'}) + γ V^{*} (s^{'})]$ . By Exercise 6.2(a), the inner expression equals $Q^{*} (s, a)$ , so $π^{*} (s) \in arg max_{a} Q^{*} (s, a)$ . Since $π^{*}$ is deterministic, $V^{*} (s) = V_{π^{*}} (s) = Q_{π^{*}} (s, π^{*} (s)) = Q^{*} (s, π^{*} (s)) = max_{a} Q^{*} (s, a)$ .

(c) Substituting Exercise 6.2(b) into Exercise 6.2(a):

Q^{*} (s, a) = s^{'} \sum T (s^{'} ∣ s, a) [R (s, a, s^{'}) + γ a^{'} max Q^{*} (s^{'}, a^{'})] = (B Q^{*}) (s, a) .

So $Q^{*}$ is a fixed point of $B$ . Uniqueness follows from Exercise 6.1 and Theorem 3.1.

Exercise 6.3. Rewrite the Q-learning update in the form of Theorem 6.1:

x_{t + 1} (i) = (1 - α_{t} (i)) x_{t} (i) + α_{t} (i) [F (x_{t}) (i) + w_{t} (i)] .

Specifically, identify the index set $I$ , the mapping $F$ , the iterates $x_{t}$ , and the learning rates $α_{t} (i)$ . Then give an explicit expression for the noise $w_{t}$ .

Solution

The identifications are:

Index set: $I = S \times A$ .
Iterates: $x_{t} = Q_{t}$ .
Contraction: $F = B$ , with fixed point $x^{*} = Q^{*}$ (Exercise 6.2).
Learning rates: $α_{t} (s, a) = α_{t} \cdot [[(s, a) = (s_{t}, a_{t})]]$ .

With these identifications, the Q-learning update becomes

Q_{t + 1} (s, a) = (1 - α_{t} (s, a)) Q_{t} (s, a) + α_{t} (s, a) [(B Q_{t}) (s, a) + w_{t} (s, a)],

where the noise at the updated coordinate is

w_{t} (s_{t}, a_{t}) = R (s_{t}, a_{t}, s_{t + 1}) + γ a^{'} max Q_{t} (s_{t + 1}, a^{'}) - (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$ .

Exercise 6.4. Show that the noise satisfies $E [w_{t} (s, a) ∣ F_{t}] = 0$ for all $(s, a) \in S \times A$ , where $F_{t}$ denotes the history up to time $t$ as in Theorem 6.1.

Hint: conditioned on $F_{t}$ , the quantities $Q_{t}$ , $s_{t}$ , and $a_{t}$ are all determined. What is the only remaining source of randomness?

Solution

Conditioned on $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 ∣ s_{t}, a_{t})$ . Therefore:

E [w_{t} (s_{t}, a_{t}) ∣ F_{t}] = E [R (s_{t}, a_{t}, s_{t + 1}) + γ a^{'} max Q_{t} (s_{t + 1}, a^{'}) ∣ F_{t}] - (B Q_{t}) (s_{t}, a_{t}) = s^{'} \sum T (s^{'} ∣ s_{t}, a_{t}) [R (s_{t}, a_{t}, s^{'}) + γ a^{'} max Q_{t} (s^{'}, a^{'})] - (B Q_{t}) (s_{t}, a_{t}) = (B Q_{t}) (s_{t}, a_{t}) - (B Q_{t}) (s_{t}, a_{t}) = 0.

For $(s, a) \neq = (s_{t}, a_{t})$ , we have $w_{t} (s, a) = 0$ by definition, so $E [w_{t} (s, a) ∣ F_{t}] = 0$ trivially.

Exercise 6.5. Assume $∣ R (s, a, s^{'}) ∣ \leq R_{m a x}$ for all $s, a, s^{'}$ . Show that there exists a constant $C > 0$ (depending only on $R_{m a x}$ and $γ$ ) such that

E [w_{t} (s, a)^{2} ∣ F_{t}] \leq C (1 + ∥ Q_{t} ∥_{\infty}^{2}) .

Hint: first show that $∣ w_{t} (s_{t}, a_{t}) ∣ \leq 2 (R_{m a x} + γ ∥ Q_{t} ∥_{\infty})$ .

Solution

Step 1: a pointwise bound on $w_{t}$ . Using $∣ R (s_{t}, a_{t}, s_{t + 1}) ∣ \leq R_{m a x}$ and $∣ max_{a^{'}} Q_{t} (s_{t + 1}, a^{'}) ∣ \leq ∥ Q_{t} ∥_{\infty}$ , the sampled target satisfies

R (s_{t}, a_{t}, s_{t + 1}) + γ a^{'} max Q_{t} (s_{t + 1}, a^{'}) \leq R_{m a x} + γ ∥ Q_{t} ∥_{\infty} .

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

∣ w_{t} (s_{t}, a_{t}) ∣ \leq 2 (R_{m a x} + γ ∥ Q_{t} ∥_{\infty}) .

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} \leq 4 (R_{m a x} + γ ∥ Q_{t} ∥_{\infty})^{2} a.s.

Taking conditional expectation of both sides given $F_{t}$ preserves the inequality (monotonicity of conditional expectation):

E [w_{t} (s_{t}, a_{t})^{2} ∣ F_{t}] \leq E [4 (R_{m a x} + γ ∥ Q_{t} ∥_{\infty})^{2} ∣ F_{t}] .

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

E [4 (R_{m a x} + γ ∥ Q_{t} ∥_{\infty})^{2} ∣ F_{t}] = 4 (R_{m a x} + γ ∥ Q_{t} ∥_{\infty})^{2} .

Combining,

E [w_{t} (s_{t}, a_{t})^{2} ∣ F_{t}] \leq 4 (R_{m a x} + γ ∥ Q_{t} ∥_{\infty})^{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} \leq 2 (a^{2} + b^{2})$ with $a = R_{m a x}$ , $b = γ ∥ Q_{t} ∥_{\infty}$ :

4 (R_{m a x} + γ ∥ Q_{t} ∥_{\infty})^{2} \leq 8 (R_{m a x}^{2} + γ^{2} ∥ Q_{t} ∥_{\infty}^{2}) \leq 8 max (R_{m a x}^{2}, γ^{2}) (1 + ∥ Q_{t} ∥_{\infty}^{2}) .

So $C = 8 max (R_{m a x}^{2}, γ^{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$ .

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 $α$ , which does not satisfy $\sum_{t} α_{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 $α$ .

Solution

By Exercises 6.1–6.5, the Q-learning iteration satisfies all the hypotheses of Theorem 6.1, provided the learning rate conditions hold: for each $(s, a) \in S \times A$ ,

t = 0 \sum \infty α_{t} (s, a) = \infty, t = 0 \sum \infty α_{t} (s, a)^{2} < \infty, α_{t} (s, a) \in [0, 1] .

Under these conditions, Theorem 6.1 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 $α_{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 α_{t} (s, a) = \sum_{k = 1}^{\infty} 1/ k = \infty$ and $\sum α_{t} (s, a)^{2} = \sum_{k = 1}^{\infty} 1/ k^{2} < \infty$ .

7. Exact policy evaluation

In Exercise 3.4, we showed that iterating $B_{π}$ converges to $V_{π}$ ; 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 7.1 (Matrix-vector notation for a deterministic policy). Fix a deterministic policy $π$ . Treating the value function as a vector in $R^{∣ S ∣}$ , define:

$v^{π} \in R^{∣ S ∣}$ with $v_{s}^{π} := V_{π} (s)$ ,
$P^{π} \in R^{∣ S ∣ \times ∣ S ∣}$ with $P_{s, s^{'}}^{π} := T (s^{'} ∣ s, π (s))$ (the transition matrix under $π$ ),
$R^{π} \in R^{∣ S ∣ \times ∣ S ∣}$ with $R_{s, s^{'}}^{π} := R (s, π (s), s^{'})$ (the reward matrix),
$r^{π} \in R^{∣ S ∣}$ with $r_{s}^{π} := \sum_{s^{'}} P_{s, s^{'}}^{π} R_{s, s^{'}}^{π} = \sum_{s^{'}} T (s^{'} ∣ s, π (s)) R (s, π (s), s^{'})$ (the expected immediate reward).

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

∥ A ∥_{\infty} := i max j \sum ∣ A_{ij} ∣ (maximum absolute row sum).

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

(I - A)^{- 1} = k = 0 \sum \infty A^{k} .

Exercise 7.1. Starting from the Bellman equation (Exercise 1.1) applied to a deterministic policy $π$ , show that

Exact Policy Evaluation

v^{π} = (I - γ P^{π})^{- 1} r^{π},

assuming $I - γ P^{π}$ is invertible (which we prove in Exercise 7.2).

Hint: specialize the Bellman equation to a deterministic policy and write the resulting system of $∣ S ∣$ equations in matrix-vector form.

Solution

Since $π$ is deterministic, $π (a ∣ s) = [[a = π (s)]]$ , and the Bellman equation from Exercise 1.1 collapses the sum over actions:

V_{π} (s) = s^{'} \in S \sum T (s^{'} ∣ s, π (s)) (R (s, π (s), s^{'}) + γ V_{π} (s^{'})) .

Splitting the reward and value terms and rewriting with the matrix notation of Definition 7.1:

v_{s}^{π} = s^{'} \sum P_{s, s^{'}}^{π} R_{s, s^{'}}^{π} + γ s^{'} \sum P_{s, s^{'}}^{π} v_{s^{'}}^{π} = r_{s}^{π} + γ (P^{π} v^{π})_{s} .

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

v^{π} = r^{π} + γ P^{π} v^{π} ⟺ (I - γ P^{π}) v^{π} = r^{π} .

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

Exercise 7.2. Prove that $I - γ P^{π}$ is invertible for any deterministic policy $π$ and any $γ \in (0, 1)$ .

Hint: apply Fact 7.2.

Solution

The matrix $P^{π}$ is row-stochastic: $P_{s, s^{'}}^{π} \geq 0$ and $\sum_{s^{'}} P_{s, s^{'}}^{π} = \sum_{s^{'}} T (s^{'} ∣ s, π (s)) = 1$ for every $s$ . Therefore

∥ P^{π} ∥_{\infty} = s max s^{'} \sum ∣ P_{s, s^{'}}^{π} ∣ = s max s^{'} \sum P_{s, s^{'}}^{π} = 1,

and so $∥ γ P^{π} ∥_{\infty} = γ < 1$ . By the Neumann series (Fact 7.2), $I - γ P^{π}$ is invertible, with

(I - γ P^{π})^{- 1} = k = 0 \sum \infty (γ P^{π})^{k} = k = 0 \sum \infty γ^{k} (P^{π})^{k} .

Combining with Exercise 7.1,

v^{π} = k = 0 \sum \infty γ^{k} (P^{π})^{k} r^{π},

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

Remark. The same derivation extends to stochastic policies by defining $P_{s, s^{'}}^{π} = \sum_{a} π (a ∣ s) T (s^{'} ∣ s, a)$ and $r_{s}^{π} = \sum_{a} π (a ∣ s) \sum_{s^{'}} T (s^{'} ∣ s, a) R (s, a, s^{'})$ . The matrix $P^{π}$ remains row-stochastic, so the argument above applies unchanged.

References

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

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

Noting that $S \times A \times S$ is a finite set, this implies that the rewards are bounded above by $R_{max} = max_{s, a, s^{'}} R (s, a, s^{'})$ . ↩

Setup

1. The Bellman equation

2. An example MDP

3. Bellman operators and the existence of optimal policies

Banach fixed-point theorem

The problem

4. Policy improvement theorem

5. Bellman convergence rate

6. Convergence of Q-learning

Stochastic approximation theorem

The problem

7. Exact policy evaluation

References

Footnotes