Reinforcement Learning I

Optimal policies, Bellman operators, and dynamic programming

Will Gao · September 2026

Contents

1 Mathematical Prerequisites
2 Finite Discounted Markov Decision Processes
3 Policy Evaluation as a Fixed Point
4 Existence of an Optimal Policy
5 Policies with Memory
6 Value Iteration
7 Policy Iteration

This note is an alternative treatment of Sections 18.1.2–18.2.4 of Principles of Robot Autonomy (2026), reorganized to suit the way I learn. A reader can use it in place of those sections and then return to the book.

The book's treatment is excellent, but it largely takes the existence of an optimal policy for granted, and under its definitions that existence was not obvious to me. The main goal here is to prove it (Theorem 4.3) and to show how the proof leads directly to the two classical algorithms, value iteration and policy iteration.

I have done my best to ensure correctness, but errors may remain.

1Mathematical Prerequisites

Definition 1.1 (Metric space).

A metric space is a set $S$ together with a function $d : S \times S \to R$ , called a metric, such that for all $x, y, z \in S$ :

$d (x, y) \geq 0$ ;
$d (x, y) = 0 ⟺ x = y$ ;
$d (x, y) = d (y, x)$ ;
$d (x, z) \leq d (x, y) + d (y, z)$ .

Example 1.2.

Let $S$ be a nonempty set. The set of bounded real-valued functions on $S$ ,

ℓ^{\infty} (S) := {f : S \to R ∣ f is bounded},

is a metric space under $d (f, g) = sup_{x \in S} | f (x) - g (x) |$ , which is finite because $f$ and $g$ are bounded. We write ${‖ f ‖}_{\infty} := sup_{x \in S} | f (x) |$ , so that $d (f, g) = {‖ f - g ‖}_{\infty}$ . When $S$ is finite, every function on $S$ is bounded, and $ℓ^{\infty} (S)$ is simply $R^{| S |}$ with the max norm.

Definition 1.3 (Complete metric space).

A metric space $(S, d)$ is complete if every Cauchy sequence in $S$ converges to an element of $S$ .

It is straightforward to verify from the definitions that $ℓ^{\infty} (S)$ is complete.

Definition 1.4 (Contraction).

Let $(S, d)$ be a metric space. A map $T : S \to S$ is a contraction if there exists $c \in [0, 1)$ such that $d (T x, T y) \leq c d (x, y)$ for all $x, y \in S$ . We then call $T$ a $c$ -contraction.

Theorem 1.5 (Banach fixed-point theorem).

Let $(S, d)$ be a nonempty complete metric space and let $T : S \to S$ be a $c$ -contraction. Then:

there exists a unique $x^{*} \in S$ such that $T x^{*} = x^{*}$ ;
for any $x_{0} \in S$ , the iterates $x_{k + 1} = T x_{k}$ converge to $x^{*}$ , and $d (x_{k}, x^{*}) \leq c^{k} d (x_{0}, x^{*})$ .

We use this theorem without proof. (The error bound in part 2 follows by applying the contraction property $k$ times to $d (x_{k}, x^{*}) = d (T x_{k - 1}, T x^{*})$ .)

Order notation. For $f, g \in ℓ^{\infty} (S)$ we write $f \leq g$ if $f (x) \leq g (x)$ for every $x \in S$ . Convergence in $ℓ^{\infty} (S)$ implies pointwise convergence, so pointwise inequalities survive limits: if $f_{k} \to f$ and $f_{k} \leq g$ for all $k$ , then $f \leq g$ .

We will also need one elementary inequality.

Lemma 1.6.

Let $U$ be a finite set and let $a_{u}, b_{u} \in R$ for $u \in U$ . Then

| max_{u \in U} a_{u} - max_{u \in U} b_{u} | \leq max_{u \in U} | a_{u} - b_{u} | .

Proof.

Let $u^{*}$ attain $max_{u} a_{u}$ . Then $max_{u} a_{u} - max_{u} b_{u} \leq a_{u^{*}} - b_{u^{*}} \leq max_{u} | a_{u} - b_{u} |$ . Exchanging the roles of $a$ and $b$ gives the same bound for $max_{u} b_{u} - max_{u} a_{u}$ .

□

2Finite Discounted Markov Decision Processes

A finite discounted Markov decision process (MDP) is a tuple

M = (X, U, p, R, γ),

where $X$ is a finite set of states, $U$ is a finite set of actions,

p (x^{'} ∣ x, u) = Pr (x_{t + 1} = x^{'} ∣ x_{t} = x, u_{t} = u)

is the transition probability, $R : X \times U \to R$ is the reward function, and $γ \in [0, 1)$ is the discount factor. For every $x \in X$ and $u \in U$ ,

p (x^{'} ∣ x, u) \geq 0, \sum_{x^{'} \in X} p (x^{'} ∣ x, u) = 1.

Throughout, $n := | X |$ and $m := | U |$ .

A stationary stochastic policy $π$ assigns to each state $x$ a probability distribution $π (\cdot ∣ x)$ over actions:

π (u ∣ x) \geq 0, \sum_{u \in U} π (u ∣ x) = 1.

When the system is in state $x_{t}$ , the action $u_{t}$ is drawn from $π (\cdot ∣ x_{t})$ . “Stationary” means the distribution depends only on the current state, not on the time $t$ or on the earlier history. We write $Π$ for the set of all such policies. A deterministic policy is a map $π : X \to U$ ; we identify it with the stochastic policy that puts probability $1$ on $π (x)$ at each state $x$ . There are $m^{n}$ deterministic policies.

A finite trajectory of length $T$ has the form

τ = (x_{0}, u_{0}, x_{1}, u_{1}, \dots, u_{T - 1}, x_{T}) .

Conditional on the initial state $x_{0} = x$ , its probability under $π$ is

p_{π} (τ ∣ x_{0} = x) = \prod_{t = 0}^{T - 1} π (u_{t} ∣ x_{t}) p (x_{t + 1} ∣ x_{t}, u_{t}) .

For an infinite trajectory $(x_{0}, u_{0}, x_{1}, u_{1}, \dots)$ , the discounted return is

\sum_{t = 0}^{\infty} γ^{t} R (x_{t}, u_{t}) .

Since $X$ and $U$ are finite, $R$ is bounded: there is $R_{max} < \infty$ with $| R (x, u) | \leq R_{max}$ for all $x \in X$ , $u \in U$ . Therefore

| \sum_{t = 0}^{\infty} γ^{t} R (x_{t}, u_{t}) | \leq \sum_{t = 0}^{\infty} γ^{t} R_{max} = \frac{R_{max}}{1 - γ},

so the discounted return is well defined and bounded.

For a policy $π \in Π$ , the state-value function $V^{π} : X \to R$ is

V^{π} (x) = E_{π} [\sum_{t = 0}^{\infty} γ^{t} R (x_{t}, u_{t}) | x_{0} = x],

the expected discounted return when the process starts in $x$ and follows $π$ thereafter. By the bound above, $| V^{π} (x) | \leq R_{max} / (1 - γ)$ .

Conditioning on the first action $u_{0}$ and the next state $x_{1}$ , and using the Markov property, we obtain the Bellman equation

V^{π} (x) = \sum_{u \in U} π (u ∣ x) [R (x, u) + γ \sum_{x^{'} \in X} p (x^{'} ∣ x, u) V^{π} (x^{'})] .

(1)

3Policy Evaluation as a Fixed Point

We work in the complete metric space $ℓ^{\infty} (X)$ . Since $X$ is finite, this is just the space of all functions $X \to R$ , and in particular $V^{π} \in ℓ^{\infty} (X)$ .

For a policy $π \in Π$ , define the Bellman operator $T^{π} : ℓ^{\infty} (X) \to ℓ^{\infty} (X)$ by

(T^{π} f) (x) = \sum_{u \in U} π (u ∣ x) [R (x, u) + γ \sum_{x^{'} \in X} p (x^{'} ∣ x, u) f (x^{'})] .

Lemma 3.1.

For every $π \in Π$ :

$T^{π} V^{π} = V^{π}$ ;
$T^{π}$ is a $γ$ -contraction;
$T^{π}$ is monotone: if $f \leq g$ , then $T^{π} f \leq T^{π} g$ .

Proof.

Part 1 is the Bellman equation (1). For parts 2 and 3, note that for every $x$ ,

(T^{π} f) (x) - (T^{π} g) (x) = γ \sum_{u \in U} π (u ∣ x) \sum_{x^{'} \in X} p (x^{'} ∣ x, u) (f (x^{'}) - g (x^{'})),

because the reward terms cancel. The weights $π (u ∣ x) p (x^{'} ∣ x, u)$ are nonnegative and sum to $1$ . Hence

| (T^{π} f) (x) - (T^{π} g) (x) | \leq γ \sum_{u} π (u ∣ x) \sum_{x^{'}} p (x^{'} ∣ x, u) | f (x^{'}) - g (x^{'}) | \leq γ {‖ f - g ‖}_{\infty},

and taking the supremum over $x$ gives ${‖ T^{π} f - T^{π} g ‖}_{\infty} \leq γ {‖ f - g ‖}_{\infty}$ . If $f \leq g$ , the same identity (with $f$ and $g$ swapped) is a nonnegative combination of the nonnegative numbers $g (x^{'}) - f (x^{'})$ , so $T^{π} f \leq T^{π} g$ .

□

Corollary 3.2.

$V^{π}$ is the unique fixed point of $T^{π}$ , and for any $f \in ℓ^{\infty} (X)$ , $(T^{π})^{k} f \to V^{π}$ as $k \to \infty$ .

Proof.

Combine Lemma 3.1 with Theorem 1.5.

□

So we can compute $V^{π}$ to any accuracy by applying $T^{π}$ repeatedly, starting from any function (for example $f = 0$ ). This is called iterative policy evaluation.

4Existence of an Optimal Policy

Evaluating a given policy is not the end goal: we want the best one. Ideally we want a single policy that is at least as good as every other policy from every starting state.

Definition 4.1 (Optimal policy).

A policy $π^{*} \in Π$ is optimal if $V^{π^{*}} \geq V^{π}$ for every $π \in Π$ , that is, $V^{π^{*}} (x) \geq V^{π} (x)$ for every $π \in Π$ and every $x \in X$ .

Asking for domination at every state simultaneously is a strong requirement: a priori, one policy might be best from $x_{1}$ while a different policy is best from $x_{2}$ . Fortunately this cannot happen.

Define the Bellman optimality operator $T : ℓ^{\infty} (X) \to ℓ^{\infty} (X)$ by

(T f) (x) = max_{u \in U} [R (x, u) + γ \sum_{x^{'} \in X} p (x^{'} ∣ x, u) f (x^{'})] .

Lemma 4.2.

$T$ is a $γ$ -contraction.
For every $π \in Π$ and every $f \in ℓ^{\infty} (X)$ , $T^{π} f \leq T f$ .

Proof.

1. Fix $x$ . By Lemma 1.6,

\begin{aligned} | (T f) (x) - (T g) (x) | & \leq max_{u} | γ \sum_{x^{'} \in X} p (x^{'} ∣ x, u) (f (x^{'}) - g (x^{'})) | \\ \leq γ max_{u} \sum_{x^{'} \in X} p (x^{'} ∣ x, u) | f (x^{'}) - g (x^{'}) | \\ \leq γ max_{u} \sum_{x^{'} \in X} p (x^{'} ∣ x, u) {‖ f - g ‖}_{\infty} = γ {‖ f - g ‖}_{\infty} . \end{aligned}

Taking the supremum over $x$ gives ${‖ T f - T g ‖}_{\infty} \leq γ {‖ f - g ‖}_{\infty}$ .

2. $(T^{π} f) (x)$ is an average, with weights $π (u ∣ x)$ , of the bracketed quantities, and an average never exceeds the maximum, which is $(T f) (x)$ .

□

Theorem 4.3 (Existence of an optimal policy).

Every finite discounted MDP has an optimal policy, and it can be chosen to be deterministic. Moreover, if $V^{*}$ denotes the unique fixed point of $T$ , then $V^{π^{*}} = V^{*}$ for every optimal $π^{*}$ .

Proof.

Step 1: the fixed point. By Lemma 4.2 and Theorem 1.5, $T$ has a unique fixed point $h \in ℓ^{\infty} (X)$ .

Step 2: a policy that achieves $h$ . Since $U$ is finite, for each $x$ the maximum in $(T h) (x)$ is attained. Define a deterministic policy by choosing, for each $x$ ,

π^{*} (x) \in \underset{u \in U}{\arg \max} [R (x, u) + γ \sum_{x^{'} \in X} p (x^{'} ∣ x, u) h (x^{'})] .

Because $π^{*} (\cdot ∣ x)$ puts all its mass on a maximizing action,

(T^{π^{*}} h) (x) = R (x, π^{*} (x)) + γ \sum_{x^{'} \in X} p (x^{'} ∣ x, π^{*} (x)) h (x^{'}) = (T h) (x) = h (x) .

So $h$ is a fixed point of $T^{π^{*}}$ . By Corollary 3.2, the only fixed point of $T^{π^{*}}$ is $V^{π^{*}}$ ; hence $h = V^{π^{*}}$ .

Step 3: no policy does better. Let $π \in Π$ . By Lemma 4.2, $T^{π} h \leq T h = h$ . We claim that

(T^{π})^{k + 1} h \leq (T^{π})^{k} h for all k \geq 0.

The case $k = 0$ is the inequality just shown. If it holds for $k$ , applying the monotone operator $T^{π}$ (Lemma 3.1) to both sides gives it for $k + 1$ . Hence

h \geq T^{π} h \geq (T^{π})^{2} h \geq \dots,

so $(T^{π})^{k} h \leq h$ for all $k$ . By Corollary 3.2, $(T^{π})^{k} h \to V^{π}$ , and passing to the limit gives $V^{π} \leq h = V^{π^{*}}$ .

Thus $π^{*}$ is optimal. Finally, if $\tilde{π}$ is any optimal policy, then $V^{\tilde{π}} \geq V^{π^{*}}$ and $V^{π^{*}} \geq V^{\tilde{π}}$ , so $V^{\tilde{π}} = V^{π^{*}} = h = V^{*}$ .

□

$V^{*}$ is called the optimal value function, and the equation $V^{*} = T V^{*}$ is the Bellman optimality equation. The optimal value function is unique, but optimal policies need not be: any policy that is greedy with respect to $V^{*}$ , in the sense of Step 2, is optimal.

5Policies with Memory

Theorem 4.3 shows that $π^{*}$ is optimal among stationary policies. A natural worry is that a policy which looks at the clock, or remembers where it has been, could do better. This section shows it cannot.

Definition 5.1 (General policy).

A history at time $t$ is $h_{t} = (x_{0}, u_{0}, x_{1}, u_{1}, \dots, x_{t})$ . A general policy $σ$ assigns to each history $h_{t}$ a probability distribution $σ (\cdot ∣ h_{t})$ over actions, and the action at time $t$ is drawn as $u_{t} \sim σ (\cdot ∣ h_{t})$ .

For example, “take action $a$ for the first ten steps, then $b$ ” and “take $a$ if $x_{3}$ has been visited before, otherwise $b$ ” are general policies but not stationary ones. Stationary policies are the special case in which $σ (\cdot ∣ h_{t})$ depends only on the last state $x_{t}$ .

Under a general policy, the probability of a trajectory is

p_{σ} (τ ∣ x_{0} = x) = \prod_{t = 0}^{T - 1} σ (u_{t} ∣ h_{t}) p (x_{t + 1} ∣ x_{t}, u_{t}),

and its value is defined exactly as before,

V^{σ} (x) = E_{σ} [\sum_{t = 0}^{\infty} γ^{t} R (x_{t}, u_{t}) | x_{0} = x], | V^{σ} (x) | \leq \frac{R_{max}}{1 - γ} .

The environment is still Markov: whatever $σ$ does, the next state is drawn from $p (\cdot ∣ x_{t}, u_{t})$ . What changes is that $V^{σ}$ generally does not satisfy a Bellman equation of the form $V = T^{π} V$ , because how $σ$ behaves after reaching $x_{1}$ can depend on how it got there. So Step 3 of the proof of Theorem 4.3, which works through $T^{π}$ , does not apply. We need a different argument.

Proposition 5.2.

For every general policy $σ$ , $V^{σ} \leq V^{*}$ .

Proof.

Fix $σ$ and a start state $x_{0}$ . For $k \geq 0$ define

W_{k} = E_{σ} [\sum_{t = 0}^{k - 1} γ^{t} R (x_{t}, u_{t}) + γ^{k} V^{*} (x_{k})] .

(i) The start: $W_{0} = V^{*} (x_{0})$ . With $k = 0$ there are no rewards yet, only the term $V^{*} (x_{0})$ .

(ii) The limit: $W_{k} \to V^{σ} (x_{0})$ .

| W_{k} - V^{σ} (x_{0}) | \leq \sum_{t = k}^{\infty} γ^{t} R_{max} + γ^{k} {‖ V^{*} ‖}_{\infty} = γ^{k} (\frac{R_{max}}{1 - γ} + {‖ V^{*} ‖}_{\infty}) \to_{k \to \infty}^{} 0.

(iii) Each step goes down: $W_{k + 1} \leq W_{k}$ .

W_{k + 1} - W_{k} = γ^{k} E_{σ} [R (x_{k}, u_{k}) + γ V^{*} (x_{k + 1}) - V^{*} (x_{k})] .

Condition on the history $h_{k}$ and the action $u_{k}$ . However $σ$ chose $u_{k}$ , the next state is drawn from $p (\cdot ∣ x_{k}, u_{k})$ , so $E_{σ} [V^{*} (x_{k + 1}) ∣ h_{k}, u_{k}] = \sum_{x^{'}} p (x^{'} ∣ x_{k}, u_{k}) V^{*} (x^{'})$ . Hence

W_{k + 1} - W_{k} = γ^{k} E_{σ} [g (x_{k}, u_{k})], g (x, u) := R (x, u) + γ \sum_{x^{'}} p (x^{'} ∣ x, u) V^{*} (x^{'}) - V^{*} (x) .

Since $V^{*} (x) = (T V^{*}) (x)$ is the maximum over $u$ of the first two terms of $g (x, u)$ , we have $g (x, u) \leq 0$ for every state $x$ and every action $u$ . Therefore $W_{k + 1} - W_{k} \leq 0$ .

Conclusion. By (iii), $W_{k} \leq W_{k - 1} \leq \dots \leq W_{0}$ for every $k$ . By (i) and (ii), letting $k \to \infty$ gives $V^{σ} (x_{0}) \leq V^{*} (x_{0})$ . Since $x_{0}$ was arbitrary, $V^{σ} \leq V^{*}$ .

□

6Value Iteration

The proof is constructive. Starting from any $V_{0}$ (for example $V_{0} = 0$ ), iterate

V_{k + 1} = T V_{k} .

By Theorem 1.5, $V_{k} \to V^{*}$ and ${‖ V_{k} - V^{*} ‖}_{\infty} \leq γ^{k} {‖ V_{0} - V^{*} ‖}_{\infty}$ . This algorithm is called value iteration. After stopping, we output a policy that is greedy with respect to the final iterate, as in Step 2 of the proof. The next proposition says that a good approximation of $V^{*}$ yields a good policy.

Proposition 6.1.

Let $V \in ℓ^{\infty} (X)$ satisfy ${‖ V - V^{*} ‖}_{\infty} \leq ε$ , and let $π$ be greedy with respect to $V$ , i.e. $T^{π} V = T V$ . Then

{‖ V^{*} - V^{π} ‖}_{\infty} \leq \frac{2 γ ε}{1 - γ} .

Proof.

Using $V^{*} = T V^{*}$ , $V^{π} = T^{π} V^{π}$ and $T^{π} V = T V$ ,

V^{*} - V^{π} = (T V^{*} - T V) + (T^{π} V - T^{π} V^{*}) + (T^{π} V^{*} - T^{π} V^{π}) .

Each operator is a $γ$ -contraction, so ${‖ V^{*} - V^{π} ‖}_{\infty} \leq γ ε + γ ε + γ {‖ V^{*} - V^{π} ‖}_{\infty}$ . Rearranging gives the claim.

□

In fact, because there are only finitely many deterministic policies, once $V_{k}$ is close enough to $V^{*}$ the greedy policy is exactly optimal; but how close is “close enough” depends on gaps in the problem that are not known in advance, so in practice one stops at a tolerance.

Complexity. One application of $T$ costs $O (m n^{2})$ : for each of the $n$ states and $m$ actions, we sum over $n$ next states. With $V_{0} = 0$ we have ${‖ V_{0} - V^{*} ‖}_{\infty} = {‖ V^{*} ‖}_{\infty} \leq R_{max} / (1 - γ)$ , so ${‖ V_{k} - V^{*} ‖}_{\infty} \leq ε$ as soon as $γ^{k} R_{max} / (1 - γ) \leq ε$ , that is,

k \geq \frac{\log (R_{max} / ((1 - γ) ε))}{\log (1 / γ)} .

Since $\log (1 / γ) \geq 1 - γ$ , it suffices to take $k \geq \frac{1}{1 - γ} \log \frac{R_{max}}{(1 - γ) ε}$ . The total cost is therefore

O (\frac{m n^{2}}{1 - γ} \log \frac{R_{max}}{(1 - γ) ε}) .

7Policy Iteration

Policy iteration takes a different route: it moves through a sequence of deterministic policies, each strictly better than the last, until it reaches an optimal one.

For a policy $π$ , define the action-value function

Q^{π} (x, u) := R (x, u) + γ \sum_{x^{'} \in X} p (x^{'} ∣ x, u) V^{π} (x^{'}) .

$Q^{π} (x, u)$ is the expected discounted return from starting at $x$ , taking action $u$ once, and following $π$ thereafter. In this notation,

V^{π} (x) = \sum_{u} π (u ∣ x) Q^{π} (x, u) \leq max_{u} Q^{π} (x, u) = (T V^{π}) (x) .

The algorithm. Start from any policy $π_{0}$ . For $k = 0, 1, 2, \dots$ :

Policy evaluation: compute $V^{π_{k}}$ (see below).
Policy improvement: define a deterministic policy

$π_{k + 1} (x) \in \underset{u \in U}{\arg \max} Q^{π_{k}} (x, u),$

keeping $π_{k + 1} (x) = π_{k} (x)$ whenever $π_{k}$ is deterministic and $π_{k} (x)$ already attains the maximum.
Stop if $π_{k + 1} = π_{k}$ .

The tie-breaking rule in step 2 prevents the algorithm from cycling among equally good policies.

Proposition 7.1 (Policy improvement).

Let $π \in Π$ and let $π^{'}$ be greedy with respect to $V^{π}$ , i.e. $π^{'} (x) \in {\arg \max}_{u} Q^{π} (x, u)$ . Then

V^{π^{'}} \geq T V^{π} \geq V^{π} .

Consequently, if $(T V^{π}) (x) > V^{π} (x)$ at some state $x$ , then $V^{π^{'}} (x) > V^{π} (x)$ ; and if $T V^{π} = V^{π}$ , then $π$ is optimal.

Proof.

By construction, $T^{π^{'}} V^{π} = T V^{π} \geq V^{π}$ . Applying the monotone operator $T^{π^{'}}$ repeatedly, exactly as in Step 3 of the proof of Theorem 4.3 but with the inequalities reversed, gives

V^{π} \leq T^{π^{'}} V^{π} \leq (T^{π^{'}})^{2} V^{π} \leq \dots,

and this sequence converges to $V^{π^{'}}$ by Corollary 3.2. So $V^{π^{'}} \geq T^{π^{'}} V^{π} = T V^{π} \geq V^{π}$ . If $T V^{π} = V^{π}$ , then $V^{π}$ is a fixed point of $T$ , so $V^{π} = V^{*}$ and $π$ is optimal.

□

Corollary 7.2.

Policy iteration terminates after at most $m^{n}$ improvement steps, with an optimal deterministic policy.

Proof.

All $π_{k}$ with $k \geq 1$ are deterministic. If the algorithm stops, i.e. $π_{k + 1} = π_{k}$ , then $T V^{π_{k}} = T^{π_{k + 1}} V^{π_{k}} = T^{π_{k}} V^{π_{k}} = V^{π_{k}}$ , so $π_{k}$ is optimal by Proposition 7.1. If it does not stop, the tie-breaking rule means that at some state $x$ the action $π_{k} (x)$ does not attain $max_{u} Q^{π_{k}} (x, u)$ , so $(T V^{π_{k}}) (x) > V^{π_{k}} (x)$ , and Proposition 7.1 gives $V^{π_{k + 1}} \geq V^{π_{k}}$ with strict inequality at $x$ . Value functions therefore strictly increase, so no deterministic policy is visited twice. Since there are $m^{n}$ deterministic policies, the algorithm stops after at most $m^{n}$ steps.

□

Exact policy evaluation. Unlike value iteration, policy evaluation can be done exactly, for any stationary policy $π$ (deterministic or not). Define the matrix $P^{π} \in R^{n \times n}$ and the vector $r^{π} \in R^{n}$ by

P_{x x^{'}}^{π} = \sum_{u} π (u ∣ x) p (x^{'} ∣ x, u), r^{π} (x) = \sum_{u} π (u ∣ x) R (x, u) .

The Bellman equation (1) reads $V^{π} = r^{π} + γ P^{π} V^{π}$ , that is,

(I - γ P^{π}) V^{π} = r^{π} .

The matrix $I - γ P^{π}$ is invertible: if $(I - γ P^{π}) v = 0$ , then $v = γ P^{π} v$ , and since $P^{π}$ is row-stochastic, ${‖ v ‖}_{\infty} \leq γ {‖ v ‖}_{\infty}$ , which forces $v = 0$ .

Complexity. Solving this $n \times n$ linear system costs $O (n^{3})$ by Gaussian elimination, or $O (n^{ω})$ with fast matrix multiplication (for example, $ω = \log_{2} 7 \approx 2.807$ with Strassen's algorithm). The improvement step computes $Q^{π_{k}}$ at cost $O (m n^{2})$ . One iteration of policy iteration therefore costs

O (n^{3} + m n^{2}) .

In practice, policy iteration usually needs far fewer iterations than value iteration, but each iteration is more expensive.

1Mathematical Prerequisites

2Finite Discounted Markov Decision Processes

3Policy Evaluation as a Fixed Point

4Existence of an Optimal Policy

5Policies with Memory

6Value Iteration

7Policy Iteration

Continue reading