Banach Fixed Point

Theorem
Dr. D. John Pradeep
Associate Professor
VIT-AP University
Table of contents
• Fixed point problem
• Metric space
• Cauchy sequence
• Complete Metric space
• Contraction mapping
• Banach fixed point theorem
• Application of BFPT to Bellman’s Equation
Overview
The claim
For each MDP, there is always at least one policy that
is better than or equal to all other policies.
The claim is proved with the following theorem
Theorem: For any finite MDP, there exists an optimal policy π*
such that it is better than or equal to every other possible policy
π.
When is one policy (π1) considered better than the other policy
(π2)?
Overview
• If the value of a state derived using π1 is better than or equal the
value of a state derived using π2 for every state in the
environment, then the policy π1 is said to be better than policy
π2 .

• Now that we know how to compare policies, we need to prove

that there always exists a policy that is better than all other
policies.
Overview
• We are going to prove this using the Banach fixed point
theorem by showing that the Bellman optimality
operator is a contraction over a complete metric space of
real numbers with metric L-infinity norm.
• For this, we will first discuss the fixed point
problem and complete metric spaces with respect to
the Cauchy sequence.
Fixed point problem
• Usually we solve for x such that a function f(x) = 0.
• If we solve for x such that f(x) = x  fixed point problem
• As the name suggests, x is a fixed point, it does not change even
on the application of the function.
• A fixed point problem can be converted into a problem of
finding roots by forming another function g(x) = f(x) - x = 0.
Fixed point problem
• To solve a fixed point problem, choose a random starting value
of x and repeatedly apply f(x) infinite times. If the function is
convergent and you’re lucky, you will find the solution.
• Mathematically

• Now, if the function is convergent then it must converge to some

value, say, x*. This value, x* is indeed the solution to the fixed
point problem
Fixed point problem
• Let's choose some arbitrary value x0 and
apply the function f(.) on x0 for infinite
times to get x*, and then use that to solve
the fixed point problem:
• The intuition behind this is pretty simple,
if a function has converged at some point
then the value of this function at that
convergent point will be the convergent
point itself
Metric space
• A metric space is simply a set with a metric defined to measure
the distance between any two elements of the set.
• For example, the Euclidean space is a metric space with distance
defined as the Euclidean distance in the set of real numbers.
• A metric space M is represented as (X, d) where X is the set and
d is some sort of metric.
• Metric d can be something that can be used to measure the size
of the vector in the defined space  Norm
• There are certain properties that the metric d must satisfy.
Metric space
• Identify d(x, x) = 0
• Non-Negativity d(x, y) >0
• Symmetry: d(x, y) = d(y, x)
• Triangular inequality: d(x, z) ≤ d(x, y)+d(y, z)
Cauchy sequence
• For a metric space (X, d) the sequence of elements of the set X,
(x1, x2, x3…. xn) is a Cauchy sequence if, for every positive real
number ε, there exists an integer N such that the following
equation holds:

• A sequence of elements of a metric space is Cauchy if this

sequence converges at some point (the distance between them
becomes constant).
Cauchy sequence
• Let Cauchy sequence be x1, x2, x3………. For any , we can find
some point in sequence beyond which if we pick two elements,
they are within of each other.
• For any small distance, there is a certain index past which any
two terms are within that distance of each other, which captures
the intuitive idea of the terms becoming close
Complete Metric space
• A metric space (X, d) is complete if every possible Cauchy
sequence of the elements in the set X converges to an element
that also belongs to the set X.
• That is to say, the convergent limit of every Cauchy sequence of
the elements of set lies in the set itself. Which is why it’s called
“complete”.
Contraction
• A function (or operator or mapping) defined on the elements of
the metric space (X, d) is a contraction (or contractor) if there
exists some constant γ [0,1) such that for any two elements of
the metric space x1 and x2, the following condition holds:

• This means that after applying the mapping f(.) on the elements
x1 and x2, they got closer to each other by at least a factor γ.
Contraction
• The smallest value of such a constant γ is called the Lipschitz
constant (this is an important constant for generative
adversarial networks).
• If γ=1, the mapping is no more a contraction but rather a short
mapping.
• Intuitively, it can be observed that the sequential values of the
elements are getting closer after applying the contraction
mapping.
Banach Fixed point Theorem
• Informally, this theorem says that for a complete metric space,
the application of a contractor on the elements of the set, again
and again, would eventually get us to an optimal, unique value.
We know:
• Contractors bring the elements of the set together.
• Applying this contractor, again and again, would get us a
sequence. (Cauchy?)
• The Cauchy sequences in a complete metric space always
converge to a value that is part of the metric space.
Proof of Uniqueness
Theorem: Let (X, d) be a complete metric space and a function f:
X->X be a contractor then, f has a unique fixed point x* X (i.e.
f(x*)=x*) such that the sequence f(f(f(…f(x)))) converges to x*.
To prove this mathematically, we need to prove both the
uniqueness and existence of x*
Proof of Uniqueness
• Uniqueness: We will prove this by contradiction. Let us assume that
the convergence value is not unique and x1* and x2* are two values at
which the sequence of contractor converges then, we will have:

• Also, note that f is a contractor so it must hold the following

property:

• Now since γ [0,1), it’s impossible to satisfy both equation 1 and 2

simultaneously. Therefore our assumption must be wrong. Hence, by
contradiction, x* must be unique.
Proof of existence
• Now that we’ve proved that x* is unique, we need to prove that
x* exists. Let (x1, x2, x3, …. xn) be the sequence formed by
repeatedly applying the contractor.

• If we assume that the sequence (x1, x2, x3, …. xn) is Cauchy, we

know for certain that this sequence will converge to some point,
say, x*. Also, since the metric space is complete, this convergent
point, x* will belong to the metric space (X, d)
• we just need to prove that this sequence is Cauchy.
Proof that the sequence is Cauchy
• Assume two elements of the set xn and xm such that m>>n and,
m is very large, then by repeatedly applying the triangular
inequality property of the metric d, we have:
Proof that the sequence is Cauchys
• Now, since f is a contractor, we know that:

• We can further reduce d(xm, xn) as follows:

Proof that the sequence is Cauchys

• Now, by choosing n to be sufficiently large, we can make the

RHS of the above equation less than any positive real number ε.
Hence, the sequence (x1, x2, x3, …. xn) is Cauchy and an optimal
x* X exists.
 Bellman Optimality Equation
• For the value function, V(s) we define a new operator, the
optimal Bellman operator, B which takes in a value function and
returns another value function.

• It can easily be observed, B is a recursive operator. Therefore,

this will generate a sequence of value functions.
• If we can show that B is indeed a contractor for some metric
space (X, d) then by the Banach fixed point theorem, we can
conclude that the repeated application of the optimal Bellman
operator will eventually give a unique optimal value function
using which an optimal (best) policy can be derived.
Bellman Optimality Equation
• Therefore, all our work now reduces to proving that B is a
contractor.
• Metric space (X,d): The set X is the set of real numbers defined
as follows:

• For the metric, we use the L-infinity norm defined as follows:

Bellman Optimality Equation
• According to L∞ norm, the distance between the two value
functions will be equal to the highest element-wise absolute
difference between the two.
• For finite MDPs with finite rewards, the value functions will
always stay in the real space.
• It is impossible for the value function to not be in the real space,
therefore, this finite space will always be complete.
Bellman Optimality Equation
Theorem: Bellman operator B is a contraction mapping in the
finite space (R, L-infinity)
Proof: Let V1 and V2 be two value functions. Then:
Bellman Optimality
• In the second step above, we introduce inequality by replacing a’
by a for the second value function. This is because by replacing
its optimal action a’ by some other action a, we have reduced its
overall value thereby introducing an inequality.
• In the fourth step, we remove the L-infinity norm by taking the
max over s’ (recall the definition of L-infinity with respect to
value functions in our setting)
• In the final step, we remove the sigma because the sum of
probabilities is always 1.
Bellman Optimality
Now we know:
• (R, L-infinity) is a complete metric space
• Bellman operator B is a contractor
• Hence, by the Banach fixed point theorem, we conclude that
there exists a unique optimal value function V* for every MDP.
Using this V*, we can derive the optimal policy π*.
• Hence proved, for any finite MDP, there exists an optimal policy
π* such that it is better than or equal to every other possible
policy π.
What next??
• Now, how to find this optimal policy and value function?
• One way is to just repeatedly apply the Bellman operator to a
random initial value function to get the optimal function. But,
this is computationally very expensive and often downright
infeasible.
• Use iterative methods like value and policy iteration or temporal
difference methods like Q-Learning or SARSA.
Reference
Mathematical Analysis of Reinforcement Learning — Bellman
Optimality Equation | by Vaibhav Kumar | Towards Data Science