Video Summary - Lpi Convergence

Main ideas and lessons conveyed

Goal of the lecture segment: Show that the optimal value iteration operator converges by establishing that it acts on a well-behaved function space (a complete metric space) under the max norm.

(V) is defined as the space of componentwise bounded value functions (functions over states).
The key notion: each component is bounded (no component is allowed to blow up).

To prove convergence, the speaker argues that with the max norm, the subset (V) of bounded functions behaves like a complete space.
Meaning: Cauchy sequences converge to something still inside (V).

The operator (T) is introduced (informally) as a mapping that updates a value function (v) by taking a max over actions:
- For each state (s), ((Tv)(s)) is computed by maximizing the expected return over actions.
The speaker claims this operator is an (\ell_\infty)-contraction (via a contraction mapping argument).

Because (T) is a contraction on a complete metric space, the lecture claims:
- There exists a unique fixed point (v^*).
- Iterating (T) from any starting value converges to (v^*).

If multiple actions tie for the maximum in some state, the set of optimal actions can contain multiple elements.
Even if multiple optimal actions exist, the optimal value for that state is the same.
In deterministic MDP settings, the speaker emphasizes that it is sufficient to consider deterministic optimal policies—stochastic “ties” are not necessary for the optimal value argument.

Start from an arbitrary initial value function.
Repeatedly apply the Bellman optimality operator (T) (update (v \leftarrow Tv)).
Stop when convergence is detected using a stopping criterion based on changes between successive iterations.

The speaker distinguishes:
- A “simple” practical stopping rule (“do it several times”),
- From having a guarantee on how close the current value (v) is to (v^*).
The more interesting point is converting “successive iterations look close” into a formal error bound to (v^*).

The speaker corrects confusion about what the operator acts on:
- (Tv) means the operator takes the entire value function (v) and outputs a new value function.
- It is not applied to a single state component in isolation.

Define (V) as the set of componentwise bounded value functions over the finite/discrete state space.
Equip (V) with the max norm (|\cdot|_\infty).
Show:
- (V) is effectively complete under the max norm (Cauchy sequences of bounded value functions converge to a bounded limit).
- The Bellman optimality operator (T) is an (\ell_\infty)-contraction.
Conclude using the contraction mapping principle:
- (T) has a unique fixed point (v^*),
- Iterating (v_{k+1} = Tv_k) converges to (v^*).

For each state (s):
- compute expected return for each action (a),
- take the max over actions.
This yields a mapping:
- (T: V \rightarrow V),
- where (Tv) is again a bounded value function.

For each state (s), choose actions that achieve the maximizing value:
- (a^*(s) \in \arg\max_a (\text{expected return using } v)).
If multiple actions maximize, the policy can include any of those maximizing actions without changing the optimal value.

Initialize: pick an arbitrary starting value function (v_0).
Loop: compute (v_{k+1} = Tv_k).
Stopping rule: stop when successive iterates are sufficiently close.
- The speaker suggests this is better than “just run many times.”
- Optionally, use a criterion that yields a guarantee on (|v_k - v^*|).