Our previous lecture introduced the Markov Decision Process (MDP) and the Bellman Equation. There, we evaluated a given policy by solving the linear system (Sutton and Barto 2018)
\[ \bv^\pi = \br^\pi + \gamma \bP^\pi \bv^\pi, \tag{1} \]
where \(\bv^\pi\) is the vector of value-function evaluations over all states, \(\br^\pi\) is the vector of expected rewards, \(\bP^\pi\) is the transition matrix under policy \(\pi\), and \(\gamma \in [0, 1)\) is the discount factor. Although this equation has a closed-form solution, computing or estimating all components can be difficult in practice, especially when the state or action space is large.
In this lecture, we instead view the Bellman Equation as a fixed-point equation for an operator acting on value functions. We will introduce the Bellman operator, verify that it is a contraction under the supremum norm, and show that repeated application of this operator converges to the true value function. This provides the foundation for iterative policy evaluation. We then use value iteration and policy iteration to improve a policy, before asking how to replace an exact Bellman expectation with observed transitions.
Section 2.4 and Appendix A of Szepesvári (2010) provide further details on dynamic programming and contraction mappings.
For clarity, we first focus on a stationary deterministic policy: the action at state \(s\) is given by \(a = \pi(s)\), with no randomness. The stochastic-policy extension is given below. Throughout this lecture, assume \(0\leq\gamma<1\), \(\sup_{s,a}\E[|R|\mid S=s,A=a]<\infty\), and bounded measurable candidate value functions. The reward condition ensures an integrable discounted return and a bounded mean reward function. Under a deterministic policy, the value function satisfies
\[ \begin{aligned} V^\pi(s) &= \E_\pi \left[ R + \gamma\, V^\pi(S') \mid S = s \right] \\ &= r(s, \pi(s)) + \gamma \E_{S' \sim \P(\cdot \mid s, \pi(s))} \left[ V^\pi(S') \right], \end{aligned} \]
where \(r(s,a)\) is the expected immediate reward and \(\P(s' \mid s,a)\) is the transition density or probability mass function. This motivates defining the Bellman operator \(\cT^\pi\), which maps any candidate value function \(V\) (a finite or infinite dimensional vector) to a new function:
\[ \cT^\pi V(s) = r(s, \pi(s)) + \gamma \E_{S' \sim \P(\cdot \mid s, \pi(s))} \left[ V(S') \right]. \tag{2} \]
The true value function \(V^\pi\) is the unique fixed point of this operator, meaning that
\[ \cT^\pi V^\pi = V^\pi. \]
We will show in the following that \(\cT^\pi\) is a contraction mapping on the space of bounded functions under the supremum norm. This contraction property implies not only that the fixed point exists and is unique, but also that iteratively applying the operator,
\[ V_\text{new} \;\leftarrow\; \cT^\pi V_\text{old}, \]
converges to \(V^\pi\) from any bounded starting function. This provides a practical method for policy evaluation when the Bellman expectation can be computed but solving the full linear system is inconvenient. If rewards or transition expectations must instead be estimated from data, their estimation error requires a separate analysis.
Before showing that the Bellman operator is a contraction, we review a classical result in functional analysis, the Banach Fixed-point Theorem.
(Banach Fixed-point Theorem) Let \(\cX\) be a complete metric space with distance metric \(d\), and let \(\cT : \cX \to \cX\) be a contraction mapping. That is, there exists a constant \(0 \le \gamma < 1\) such that \[ d(\cT(x_1), \cT(x_2)) \le \gamma \, d(x_1, x_2) \quad \text{for all } x_1, x_2 \in \cX. \] Then \(\cT\) has a unique fixed point \(x^\ast\), and the sequence \((\cT^n x_0)\) converges to \(x^\ast\) for any starting point \(x_0\).
We now verify that the Bellman operator \(\cT^\pi\) is a contraction mapping on the space of bounded value functions equipped with the supremum norm. Recall our definition in (2), consider any two value functions \(V_1\) and \(V_2\). Then
\[ \begin{aligned} \| \cT^\pi V_1 - \cT^\pi V_2 \|_\infty &= \sup_s \left| \gamma \E_{S' \sim \P(\cdot\mid s,\pi(s))} \left[ V_1(S') - V_2(S') \right] \right| \\ &\le \gamma \sup_s \E_{S'} \left[ \left| V_1(S') - V_2(S') \right| \right] \\ &\le \gamma \sup_{s'} \left| V_1(s') - V_2(s') \right| \\ &= \gamma \, \|V_1 - V_2\|_\infty. \end{aligned} \]
The second inequality uses the elementary fact that the expectation of a bounded function is bounded above by its supremum. This argument applies equally in the discrete case (using sums) and the continuous case (using integrals). Thus, \(\cT^\pi\) is a \(\gamma\)-contraction, and Banach’s theorem guarantees the existence and uniqueness of the fixed point \(V^\pi\), as well as convergence of the iteration
\[ V_\text{new} \leftarrow \cT^\pi V_\text{old} \]
to \(V^\pi\) for any bounded initial function \(V\). This result applies to both finite and infinite state spaces. When the state space is finite, the fixed point can also be obtained by solving the linear system in (1). When the space is large or continuous, we may instead approximate Bellman expectations using samples and regression. Contraction of the exact operator alone does not guarantee convergence of these approximate updates.
The above discussion can be easily extended to stochastic policies. In this case, the Bellman operator becomes a linear combination over all possible actions, weighted by the policy probabilities:
\[ \cT^\pi V(s) = \sum_a \pi(a \mid s) \left[ r(s,a) + \gamma \E_{S' \sim \P(\cdot \mid s,a)} \left[ V(S') \right] \right]. \]
The contraction property can be verified similarly since the expectation over actions is simply a weighted average and it would not violate the infinity norm bound. Thus, all results for deterministic policies carry over to stochastic policies without change.
When the state and action spaces are continuous, the Bellman operator is defined using integrals instead of sums. For example, if we assume a density function \(p(s' \mid s,a)\) for the transition kernel and a density \(\pi(a \mid s)\) for the stochastic policy, then
\[ \cT^\pi V(s) = \int_a \pi(a \mid s) \left[ r(s,a) + \gamma \int_{s'} p(s' \mid s,a) V(s') ds' \right] da. \]
The contraction property still holds because the integrals are linear operators and the same supremum norm bounds apply.
We can do a simple example to illustrate the iterative policy evaluation using the Bellman operator. Consider the MDP with 3 states and 2 actions from the preceding lecture. The transition probability matrices for action 1 and action 2 are given by
\[ P_1 = \begin{pmatrix} 0.8 & 0.1 & 0.1 \\ 0.05 & 0.05 & 0.9 \\ 0.2 & 0.2 & 0.6 \end{pmatrix} \]
\[ P_2 = \begin{pmatrix} 0.5 & 0.25 & 0.25 \\ 0.1 & 0.8 & 0.1 \\ 0.8 & 0.1 & 0.1 \end{pmatrix} \]
Our immediate reward function is
\[ r = \begin{pmatrix} 5 & 3 \\ 2 & 2.5 \\ 3 & 2 \end{pmatrix} \]
The following code performs iterative policy evaluation for the same stochastic policy as before, with action probabilities \((1/2,1/2)\), \((2/3,1/3)\), and \((1/3,2/3)\) in states 1, 2, and 3. We use \(\gamma=0.7\).
# Transition matrices and reward matrix as before
P1 = matrix(c(0.8, 0.1, 0.1,
0.05, 0.05, 0.9,
0.2, 0.2, 0.6), byrow=TRUE, nrow=3)
P2 = matrix(c(0.5, 0.25, 0.25,
0.1, 0.8, 0.1,
0.8, 0.1, 0.1), byrow=TRUE, nrow=3)
# define the expected reward for each state and each action
r = matrix(c(5, 3,
2, 2.5,
3, 2), byrow=TRUE, nrow=3)
gamma = 0.7
# Define a stochastic policy: each row is a state,
# Columns represent the probability of taking action 1 and action 2 respectively
Pi = matrix(c(1/2, 1/2,
2/3, 1/3,
1/3, 2/3), byrow = TRUE, nrow = 3)
# Induced reward vector r^pi(s) = sum_a pi(a|s) r(s,a)
r_pi = rowSums(r * Pi)
# Induced transition matrix P^pi(s, s') = sum_a pi(a|s) P_a(s, s')
P_pi = matrix(0, nrow = 3, ncol = 3)
for (s in 1:3) {
P_pi[s, ] = Pi[s, 1] * P1[s, ] + Pi[s, 2] * P2[s, ]
}
# Iterative policy evaluation: V_{k+1} = r^pi + gamma * P^pi V_k
V = c(0, 0, 0) # initial value function
niter = 100
for (k in 1:niter)
{
V_new = as.vector(r_pi + gamma * P_pi %*% V)
if (k <= 6 | k == niter)
{
if (k == niter) cat("\n--------------\n\n")
cat(paste("Iteration", k, "\n"))
print(V_new)
}
V = V_new
}
## Iteration 1
## [1] 4.000000 2.166667 2.333333
## Iteration 2
## [1] 6.371250 3.842778 4.651111
## Iteration 3
## [1] 7.939420 5.332968 6.236125
## Iteration 4
## [1] 9.029650 6.421778 7.329710
## Iteration 5
## [1] 9.793048 7.186129 8.093365
## Iteration 6
## [1] 10.327575 7.720821 8.627880
##
## --------------
##
## Iteration 100
## [1] 11.574868 8.968124 9.875168
# Exact solution (linear system)
cat("\nExact solution:\n")
##
## Exact solution:
V_exact = solve(diag(3) - gamma * P_pi, r_pi)
print(V_exact)
## [1] 11.574868 8.968124 9.875168So far we have focused on evaluating a given policy (policy evaluation). The next step in the MDP framework is to identify a policy that maximizes long-term return (policy learning). The optimal policy \(\pi^\ast\) yields the highest possible value at every state:
\[ V^\ast(s) = \sup_{\pi} \, V^\pi(s) = \E\!\left[ R + \gamma V^\ast(S') \,\big|\, S = s, A = \pi^\ast(s) \right]. \]
For this optimality discussion, assume a finite action set, so the action maximum is attained. The optimal policy selects the action that maximizes immediate reward plus discounted continuation value, leading to the Bellman Optimality Equation:
\[ V^\ast(s) = \max_{a} \left\{ r(s,a) + \gamma \E_{S' \sim p(\cdot \mid s,a)} \left[ V^\ast(S') \right] \right\}. \]
This equation defines the Bellman Optimality Operator, denoted \(\cT^\ast\), which acts on any candidate value function \(V\) as
\[ \cT^\ast V(s) = \max_{a} \left\{ r(s,a) + \gamma \E_{S' \sim p(\cdot \mid s,a)} \left[ V(S') \right] \right\}. \]
The true optimal value function \(V^\ast\) is the unique fixed point of this operator: \[ \cT^\ast V^\ast = V^\ast. \]
And naturally, the optimal policy can be extracted as the greedy policy with respect to \(V^\ast\):
\[ \pi^\ast(s) \in \arg\max_a \left\{ r(s,a) + \gamma \E_{S' \sim p(\cdot \mid s,a)} \left[ V^\ast(S') \right] \right\}. \]
The inequality \(|\max_a x_a-\max_a y_a|\leq\max_a|x_a-y_a|\), together with the same supremum norm bound, shows that \(\cT^\ast\) is also a \(\gamma\)-contraction. The full calculation is given in the optional details below. By Banach’s Fixed-point Theorem, the fixed point \(V^\ast\) exists, is unique, and can be obtained by repeatedly applying \(\cT^\ast\):
\[ V_\text{new} = \cT^\ast V_\text{old}, \]
Regardless of the initial guess \(V_0\), the sequence \((V_k)\) converges to the unique fixed point \(V^\ast\), with the optimal policy extracted as the greedy policy with respect to \(V^\ast\), defined previously. This iterative procedure to find the optimal value function is known as Value Iteration.
In the following, we illustrate how to apply the Bellman Optimality operator to the example MDP developed earlier. Since the transition probabilities and expected rewards are assumed known, this setting allows us to perform exact value iteration and observe the emergence of the optimal policy. We use the same transition matrices and reward structure as before. The example was designed such that
# Define the transition probability matrix and rewards
P1 = matrix(c(0.8, 0.1, 0.1,
0.05, 0.05, 0.9,
0.2, 0.2, 0.6), byrow=TRUE, nrow=3)
P2 = matrix(c(0.5, 0.25, 0.25,
0.1, 0.8, 0.1,
0.8, 0.1, 0.1), byrow=TRUE, nrow=3)
# define the expected reward for each state and each action
r = matrix(c(5, 3,
2, 2.5,
3, 2), byrow=TRUE, nrow=3)
gamma = 0.7
# start with some arbitrary value function
V = c(0, 0, 0)
# recursively update the value function using the Bellman Optimality operator
niter = 20
for (k in 1:niter)
{
# Calculate the Q function, for each state and each action
Q = matrix(NA, nrow=3, ncol=2)
Q[, 1] = r[, 1] + gamma * P1 %*% V
Q[, 2] = r[, 2] + gamma * P2 %*% V
# update the value function using the bellman optimality operator
V = apply(Q, 1, max)
SummaryMat = cbind("Policy" = apply(Q, 1, which.max),
"Value" = V)
if (k <= 4 | k == niter)
{
if (k == niter) cat("\n--------------\n\n")
cat(paste("Iteration", k, "\n"))
print(SummaryMat)
}
}
## Iteration 1
## Policy Value
## [1,] 1 5.0
## [2,] 2 2.5
## [3,] 1 3.0
## Iteration 2
## Policy Value
## [1,] 1 8.185
## [2,] 2 4.460
## [3,] 1 5.310
## Iteration 3
## Policy Value
## [1,] 1 10.26750
## [2,] 2 5.94225
## [3,] 2 7.26750
## Iteration 4
## Policy Value
## [1,] 1 11.674482
## [2,] 1 7.145866
## [3,] 2 8.674482
##
## --------------
##
## Iteration 20
## Policy Value
## [1,] 1 14.90083
## [2,] 1 10.37910
## [3,] 2 11.90083This gives a higher value than the previously defined stochastic policy. In fact, after just four iterations, the greedy actions have stabilized at the optimal policy \((1,1,2)\), but the value estimates take longer to converge. We can also approximate this policy’s value using Monte Carlo simulation:
# write a function to simulate the MDP
simulate_MDP <- function(n, policy, P1, P2, r, gamma, s0){
# prepare the data
S = rep(NA, n)
A = rep(NA, n)
R = rep(NA, n)
# lets start from the first state
S[1] = s0
# sequential simulation
for (t in 1:n){
# take an action based on the policy A_t
A[t] = sample(1:2, 1, prob = policy[S[t],])
# get the reward r(S_t, A_t) with a bit of noise
R[t] = r[S[t], A[t]] + rnorm(1)*0.1
if (t < n){
# get the next state depending on the action
if (A[t] == 1){
S[t+1] = sample(1:3, 1, prob = P1[S[t],])
} else {
S[t+1] = sample(1:3, 1, prob = P2[S[t],])
}
}
}
#record the cumulative discounted reward
return(list(S = S, A = A, R = R, cum_reward = sum(gamma^seq(0, n-1) %*% R)))
}
# Simulate the data
# generate 1000 simulations for each initial state
nsim = 1000
cum_reward = matrix(NA, nsim, 3)
set.seed(1)
# The optimal policy chooses actions 1, 1, and 2 in states 1, 2, and 3.
mypolicy = matrix(c(1, 0,
1, 0,
0, 1), byrow=TRUE, nrow=3)
nchain = 100
for (k in 1:nsim)
{
#record the cumulative discounted reward
cum_reward[k, 1] = simulate_MDP(nchain, mypolicy, P1, P2, r, gamma, 1)$cum_reward
cum_reward[k, 2] = simulate_MDP(nchain, mypolicy, P1, P2, r, gamma, 2)$cum_reward
cum_reward[k, 3] = simulate_MDP(nchain, mypolicy, P1, P2, r, gamma, 3)$cum_reward
}
# simulated mean value function
colMeans(cum_reward)
## [1] 14.79509 10.41573 11.87744The simulated means fluctuate around the exact policy values \((14.91,10.39,11.91)\). The 100-step trajectories approximate the continuing discounted return; with \(\gamma=0.7\), the contribution after 100 steps is negligible here.
Similarly to the value function version, we can also derive the Bellman operator and the Bellman optimality operator for the Q-function. Recall our Bellman equation of the Q function, we can correspondingly define the Bellman operator under a fixed policy \(\pi\) as:
\[ \cT_Q^\pi Q(s,a) = r(s,a) + \gamma \E_{S' \sim p(\cdot \mid s,a)} \left[ \sum_{a'} \pi(a' \mid S') Q(S', a') \right]. \]
Analogous to the value-function case, define the optimal Bellman operator on Q-functions as
\[ \cT_Q^\ast Q(s,a) = r(s,a) + \gamma \E_{S' \sim p(\cdot \mid s,a)} \big[ \max_{a'} Q(S', a') \big], \]
with the optimal policy extracted as the greedy policy with respect to \(Q^\ast\):
\[ \pi^\ast(s) \in \arg\max_a Q^\ast(s,a). \]
Under the supremum norm \(\|Q\|_\infty=\sup_{s,a}|Q(s,a)|\), both Q-operators are \(\gamma\)-contractions, by the same argument used for value functions. Their fixed points are \(Q^\pi\) and \(Q^\ast\), respectively; the full calculations are given in the optional details below.
Consider a finite MDP with bounded rewards and \(0<\gamma<1\). In its classical dynamic programming form, policy iteration alternates between two steps (at iteration \(k\)):
Policy Evaluation: Given a fixed policy \(\pi_k\), compute its value function \(V^{\pi_k}\) (or equivalently \(Q^{\pi_k}\)) by solving the Bellman equation for that policy. In the tabular finite-MDP setting, this can be done exactly by solving a system of linear equations. Alternatively, repeated Bellman updates converge to the value function; stopping after finitely many updates gives an approximation.
Policy Improvement: Using the evaluated value function, construct a new policy \[ \pi_{k+1}(s) \in \arg\max_a Q^{\pi_k}(s,a), \] which chooses, in each state, an action that maximizes the evaluated Q-function.
These two steps are repeated until the policy no longer changes. Policy iteration differs from value iteration because it evaluates a policy before improving it.1
A key theoretical result, called the Policy Improvement Theorem, guarantees that exact greedy improvement never decreases the policy value. With finite state and action spaces, exact evaluation, deterministic greedy policies, and a fixed rule for breaking ties, policy iteration terminates after finitely many policy updates at an optimal policy. This finite-termination result does not automatically extend to approximate evaluation or continuous action spaces.
When evaluating the policy, we can again use the Bellman equation to iteratively update the Q-function. Here is the example we used above for value iteration. Let’s modify the algorithm to perform policy iteration, starting from the deterministic policy \((2,2,1)\). State 1 offers the highest immediate reward, so returning there is attractive, but the objective is discounted cumulative reward, not minimum time to reach state 1. The transition probability matrices for action 1 and action 2 are given as follows:
\[ P_1 = \begin{pmatrix} 0.8 & 0.1 & 0.1 \\ 0.05 & 0.05 & 0.9 \\ 0.2 & 0.2 & 0.6 \end{pmatrix} \]
\[ P_2 = \begin{pmatrix} 0.5 & 0.25 & 0.25 \\ 0.1 & 0.8 & 0.1 \\ 0.8 & 0.1 & 0.1 \end{pmatrix} \]
Our immediate reward function is
\[ r = \begin{pmatrix} 5 & 3 \\ 2 & 2.5 \\ 3 & 2 \end{pmatrix} \]
# Transition matrices and reward matrix as before
P1 = matrix(c(0.8, 0.1, 0.1,
0.05, 0.05, 0.9,
0.2, 0.2, 0.6), byrow=TRUE, nrow=3)
P2 = matrix(c(0.5, 0.25, 0.25,
0.1, 0.8, 0.1,
0.8, 0.1, 0.1), byrow=TRUE, nrow=3)
# define the expected reward for each state and each action
r = matrix(c(5, 3,
2, 2.5,
3, 2), byrow=TRUE, nrow=3)
gamma = 0.7
# start from some arbitrary policy and Q function
use_policy = c(2, 2, 1)
Q = matrix(1, nrow=3, ncol=2)
niter = 2 # number of policy improvement iterations
n_eval_iter = 30 # (inner loop) number of evaluation iterations
# policy iteration
for (k in 1:niter)
{
# We need to first find the policy value of the current policy
# This involves a further iteration
# recall our Bellman equation for any policy
evaluated_policy = use_policy
for (j in 1:n_eval_iter)
{
# We will use the current estimate of Q as a starting point
# the corresponding value
V = Q[cbind(1:3, use_policy)]
# Use the Bellman Equation to update the Q function
Q[, 1] = r[, 1] + gamma * P1 %*% V
Q[, 2] = r[, 2] + gamma * P2 %*% V
}
# up to here, we have a good estimation of the Q function
# We can then update the policy
use_policy = apply(Q, 1, which.max)
# print some results
SummaryMat = cbind("Evaluated policy" = evaluated_policy,
"Improved policy" = use_policy,
"Q action 1" = Q[, 1],
"Q action 2" = Q[, 2])
if (k <= 3 | k == niter)
{
if (k == niter) cat("\n--------------\n\n")
cat(paste("Iteration", k, "\n"))
print(SummaryMat)
}
}
## Iteration 1
## Evaluated policy Improved policy Q action 1 Q action 2
## [1,] 2 1 11.625997 9.543939
## [2,] 2 2 8.675954 8.724445
## [3,] 1 1 9.581929 8.625997
##
## --------------
##
## Iteration 2
## Evaluated policy Improved policy Q action 1 Q action 2
## [1,] 1 1 14.681706 11.788493
## [2,] 2 1 9.834572 9.779745
## [3,] 1 2 11.076879 11.681706After 2 improvement steps, the policy is \((1,1,2)\), which is optimal for this example. Each outer step used 30 Bellman evaluation updates, so the outer iteration count alone does not measure computational cost. The displayed Q-values evaluate the policy before improvement, not the new policy in the same row. Classical policy iteration fully evaluates a policy before improving it; this code approximates that evaluation. In value iteration, one Bellman optimality update is followed implicitly by a new greedy choice, without fully evaluating that policy first.
Under the finite discounted-MDP conditions above, exact policy iteration converges to an optimal policy. The main ingredient is that greedy improvement applied to an exact policy value cannot reduce value.
(Policy Improvement Theorem) In the finite discounted MDP above, let \(\pi_0\) be a stationary policy. Let \(\pi\) be a policy that is greedy with respect to \(V^{\pi_0}\):
\[ \cT^\pi V^{\pi_0} = \cT^\ast V^{\pi_0} \]
Then \(\pi\) is an improvement upon \(\pi_0\), i.e.,
\[ V^\pi \geq V^{\pi_0} \]
The proof of this theorem is straightforward. Since we know that the policy improvement step is greedy, we have
\[ \cT^\pi V^{\pi_0} = \cT^\ast V^{\pi_0} \geq \cT^{\pi_0} V^{\pi_0} = V^{\pi_0}. \]
The first equation is due to the definition of the greedy policy, that we are picking the best action w.r.t the value function of \(\pi_0\). Hence, the Bellman corresponding to \(\pi\) is the same as the Bellman optimality operator applied to \(V^{\pi_0}\). The inequality is due to the fact that the Bellman optimality operator always gives a value no less than any other policy’s Bellman operator when applied to the same value function, simply because it picks the best action given the current value function \(V^{\pi_0}\). The last equality is due to the fact that \(V^{\pi_0}\) is the fixed point of the Bellman operator corresponding to policy \(\pi_0\).
The Bellman operator preserves pointwise inequalities. Applying \(\cT^\pi\) on both sides therefore gives
\[ (\cT^\pi)^2 V^{\pi_0} \geq \cT^\pi V^{\pi_0} \geq V^{\pi_0}, \]
and repeatedly applying this leads to
\[ (\cT^\pi)^n V^{\pi_0} \geq V^{\pi_0}. \]
Since \(\cT^\pi\) is a contraction, repeated application converges to \(V^\pi\). Taking the limit yields
\[ V^{\pi} = \lim_{n\to\infty}(\cT^\pi)^n V^{\pi_0} \geq V^{\pi_0}. \]
All of these dynamic programming updates use the transition model to average over the next state. What changes when we only observe transitions? For a candidate Q-function \(Q_k\), the exact optimality backup is
\[ \cT_Q^\ast Q_k(s,a) =\E\!\left[R+\gamma\max_{a'}Q_k(S',a')\mid S=s,A=a\right]. \]
An observed transition \((S,A,R,S')\) supplies one sampled target,
\[ Y_k=R+\gamma\max_{a'}Q_k(S',a'). \]
Its conditional mean is the exact backup above. The next lecture on fitted Q-iteration uses regression of these targets on \((S,A)\) to approximate the Bellman update from data. Unlike the exact operators studied here, regression introduces sampling and approximation errors, so the contraction result alone does not settle its behavior.
The policy-evaluation contraction proof gives the main argument for this lecture. The following calculations show the matrix expansion and the analogous proofs for the optimality and Q-operators.
To illustrate the exact iteration, return to the finite-state matrix representation. Starting from any \(V\), if we apply the Bellman operator twice, we get
\[ \begin{aligned} (\cT^\pi)^2 V &= \br^\pi + \gamma \bP^\pi (\br^\pi + \gamma \bP^\pi V) \\ &= \br^\pi + \gamma \bP^\pi \br^\pi + \gamma^2 (\bP^\pi)^2 V. \end{aligned} \]
A third application yields
\[ (\cT^\pi)^3 V = \br^\pi + \gamma \bP^\pi \br^\pi + \gamma^2 (\bP^\pi)^2 \br^\pi + \gamma^3 (\bP^\pi)^3 V. \]
We can now see a clear pattern: each application introduces an additional term \(\gamma^k (\bP^\pi)^k \br^\pi\), and the influence of the initial \(V\) is pushed forward by another factor of \(\gamma \bP^\pi\). A simple induction argument verifies that for any integer \(n \ge 1\),
\[ (\cT^\pi)^n V = \sum_{k=0}^{n-1} \gamma^k (\bP^\pi)^k \br^\pi + \gamma^n (\bP^\pi)^n V. \]
The last term represents the residual contribution of the initial function \(V\) after \(n\) iterations. Because \(\gamma \in [0,1)\) and \(\bP^\pi\) is a stochastic matrix2, this remainder term vanishes as \(n \to \infty\). Hence the sequence \((\cT^\pi)^n V\) converges to the infinite discounted sum
\[ \sum_{k=0}^{\infty} \gamma^k (\bP^\pi)^k \br^\pi. \]
Noticing that
\[ (\bI - \gamma \bP^\pi) \sum_{k=0}^{\infty} \gamma^k (\bP^\pi)^k = \bI, \]
Therefore,
\[ \lim_{n \to \infty} (\cT^\pi)^n V = (\bI - \gamma \bP^\pi)^{-1} \br^\pi = \bv^\pi. \]
Which is exactly the same as the one we obtained from solving the linear system in (1). This convergence can also be seen directly from the contraction property, by applying it repeatedly:
\[ \| (\cT^\pi)^n V_1 - (\cT^\pi)^n V_2 \|_\infty \le \gamma^n \|V_1 - V_2\|_\infty \longrightarrow 0, \quad n \to \infty. \]
We can also check that, although \(\cT^\ast\) involves a maximization, it retains the same contraction behavior as the policy-specific Bellman operator. For any two bounded value functions \(V_1\) and \(V_2\)
\[ \begin{aligned} \big\| \cT^\ast V_1 - \cT^\ast V_2 \big\|_\infty &= \sup_s \left| \max_a \left\{ r(s,a) + \gamma \E[V_1(S') \mid s,a] \right\} - \max_a \left\{ r(s,a) + \gamma \E[V_2(S') \mid s,a] \right\} \right| \\ &\le \sup_s \max_a \left| \gamma \E[V_1(S') - V_2(S') \mid s,a] \right| \\ &\le \gamma \sup_s \max_a \E\left[|V_1(S')-V_2(S')|\mid s,a\right] \\ &\le \gamma \sup_s \max_a \E\left[\| V_1 - V_2 \|_\infty\mid s,a\right] \\ &= \gamma \| V_1 - V_2 \|_\infty. \end{aligned} \]
where the first inequality uses the fact that the difference of two maxima is bounded by the maximum of their differences3, and the subsequent steps uses standard supremum norm bounds. Thus \(\cT^\ast\) is a \(\gamma\)-contraction under the supremum norm.
Under the supremum norm defined as \(\| Q \|_\infty = \sup_{s,a} |Q(s,a)|\), the policy-specific Q-operator is also a contraction mapping:
\[ \begin{aligned} &\big| (\cT_Q^\pi Q_1)(s,a) - (\cT_Q^\pi Q_2)(s,a) \big| \\ =& \, \gamma \, \left| \E\!\left[ Q_1(S',A') - Q_2(S',A') \,\big|\, S=s, A=a \right] \right| \\ \le& \, \gamma \, \E\!\left[ | Q_1(S',A') - Q_2(S',A') | \,\big|\, S=s, A=a \right] \\ \le& \, \gamma \, \E\!\left[ \| Q_1 - Q_2 \|_\infty \,\big|\, S=s, A=a \right] \\ =& \, \gamma \, \| Q_1 - Q_2 \|_\infty. \end{aligned} \]
Taking the supremum over \((s,a)\), we have
\[ \| \cT_Q^\pi Q_1 - \cT_Q^\pi Q_2 \|_\infty \le \gamma \| Q_1 - Q_2 \|_\infty. \]
The contraction of the optimality Q-operator can be validated with
\[ \begin{aligned} &\big| (\cT_Q^\ast Q_1)(s,a) - (\cT_Q^\ast Q_2)(s,a) \big| \\ =& \, \gamma \, \left| \E\!\left[ \max_{a'} Q_1(S',a') - \max_{a'} Q_2(S',a') \,\big|\, S=s, A=a \right] \right| \\ \le& \, \gamma \, \E\!\left[ \big| \max_{a'} Q_1(S',a') - \max_{a'} Q_2(S',a') \big| \,\big|\, S=s, A=a \right] \\ \le& \, \gamma \, \E\!\left[ \max_{a'} | Q_1(S',a') - Q_2(S',a') | \,\big|\, S=s, A=a \right] \\ \le& \, \gamma \, \sup_{s',a'} | Q_1(s',a') - Q_2(s',a') | \\ =& \, \gamma \, \| Q_1 - Q_2 \|_\infty. \end{aligned} \]
Therefore
\[ \| \cT_Q^\ast Q_1 - \cT_Q^\ast Q_2 \|_\infty \le \gamma \| Q_1 - Q_2 \|_\infty. \]
Value iteration applies the Bellman optimality operator to the current value estimate. A greedy policy can be extracted at every iteration, but the current estimate need not equal that policy’s value. Fitted Q-iteration, introduced in the next lecture, similarly fits Bellman optimality targets and can produce a greedy policy after every fit. Regression error and function approximation mean that the fitted update need not be a contraction.↩︎
The infinity norm of a matrix \(A\) is defined as \(\|A\|_\infty = \max_i \sum_j |a_{ij}|\), which for a stochastic matrix equals 1. Hence, applying the matrix repeatedly scales down any vector by at most a factor of 1, and multiplying by \(\gamma < 1\) ensures convergence to zero.↩︎
This inequality follows from the fact that for any two sets of real numbers \(\{x_a\}\) and \(\{y_a\}\), \(|\max_a x_a - \max_a y_a| \le \max_a |x_a - y_a|\).↩︎