Why Do Dynamic Programming Algorithms Converge?

TL;DR

Dynamic programming algorithms converge because Bellman operators can be treated as contraction mappings whose unique fixed points are the desired value functions. Under the maximum norm, the Bellman optimality operator contracts distances by the MDP discount factor, so repeated application approaches the optimal value function geometrically while preserving pointwise ordering between functions.

Transcript

hi everybody and welcome back to our fourth lecture on reinforcement learning today we're going to go deeper into the fundamentals of dynamic programming and revisit some of the algorithms we've introduced the last time we see their theoretical properties as a reminder last lecture we've introduced the framework of markup decision processes we also... Read More

Key Insights

• A norm is a mapping from a vector space to the real numbers that is always positive, homogeneous, and compliant with the triangle inequality. The lecture primarily uses the maximum norm and occasionally the L2 norm, including versions weighted by a distribution.
• A contraction mapping reduces the distance between any two points by at least a specified coefficient. A mapping is non-expanding when that coefficient lies between zero and one, and it is a full contraction when the coefficient is strictly less than one.
• Every contraction mapping described in the lecture is Lipschitz and therefore continuous. Consequently, when a sequence converges to a point under the chosen norm, applying the mapping to every sequence element produces another sequence that converges to the mapping of that point.
• A fixed point is an element that remains unchanged when an operator is applied to it. Fixed points connect Bellman equations to dynamic programming because the target value function satisfies the relevant Bellman equation and is therefore unchanged by its associated Bellman operator.
• The Banach fixed-point theorem states that a contraction on a complete normed space has one unique fixed point. Starting from an initial element and repeatedly applying the contraction produces a sequence that approaches this fixed point at a geometric rate.
• A state-value function is the expected discounted return obtained by starting in a state and following a policy. An action-value function additionally conditions on taking a specified first action, which does not have to follow the policy, before following that policy afterward.
• The Bellman optimality operator maps a bounded real function over the state space to another function by maximizing over actions and combining expected rewards with discounted next-state values. Substituting the optimal value function returns that same function, making it a fixed point.
• The Bellman optimality operator is a contraction under the maximum norm, with the MDP discount factor serving as its contraction coefficient. It is also monotonic, meaning that pointwise dominance between two functions is preserved after the operator is applied to both.

Questions & Answers

Q: Why do dynamic programming algorithms converge?

Dynamic programming convergence can be established by expressing the update as repeated application of a Bellman operator. The Bellman optimality operator is a contraction under the maximum norm, with the MDP discount factor as its contraction coefficient. The Banach fixed-point theorem then guarantees one unique fixed point and says that successive applications approach it at a geometric rate. For this operator, that fixed point is the optimal value function.

Q: What is a contraction mapping in reinforcement learning?

A contraction mapping is an operator that brings any two elements of a normed vector space closer together. If its coefficient is alpha, the distance between the transformed elements is no greater than alpha times their original distance. In the lecture's reinforcement learning setting, the Bellman optimality operator is a contraction under the maximum norm, and its contraction coefficient is the MDP discount factor.

Q: What does the Banach fixed-point theorem guarantee?

The Banach fixed-point theorem guarantees that a contraction mapping on a complete normed space has exactly one fixed point. It also provides an iterative route to that point: define each new sequence element by applying the mapping to the preceding element. This sequence converges to the unique fixed point geometrically, because the upper bound on its distance from that point shrinks as the number of iterations increases.

Q: What is the Bellman optimality operator?

The Bellman optimality operator is a mapping from the space of bounded real functions over states back into that same space. It takes a candidate function, evaluates expected immediate rewards and discounted next-state values for available actions, and maximizes over those actions. Its expression mirrors the Bellman optimality equation. When the candidate is the optimal value function, the operator returns that function unchanged.

Q: Why is the optimal value function a fixed point?

The optimal value function satisfies the Bellman optimality equation. The Bellman optimality operator is defined using the right-hand side of that equation, including maximization over actions, transition dynamics, expected rewards, the discount factor, and next-state values. Substituting the optimal value function into the operator therefore returns the same function. This makes the optimal value function a fixed point, and the contraction property makes that fixed point unique.

Q: How is the Bellman optimality operator proved to be a contraction?

The proof begins by expanding the maximum-norm distance between the operator applied to two candidate functions. It then uses an inequality that bounds the absolute difference between two maxima by the maximum absolute difference of their underlying expressions. The shared reward terms cancel, transition probabilities combine the remaining next-state differences, and the discount factor scales the resulting bound, yielding the required contraction relationship under the maximum norm.

Q: What does monotonicity mean for a Bellman operator?

Monotonicity means that the operator preserves pointwise ordering. If one bounded function is less than or equal to another function at every state, applying the Bellman optimality operator to both maintains that relationship at every state. This condition concerns complete pointwise dominance, not cases where one function is larger in some states and smaller in others, which provide only a partial ordering.

Q: What is the difference between state-value and action-value functions?

A state-value function gives the expected discounted return when the process starts in a particular state and then follows a specified policy. An action-value function conditions on both a starting state and a selected first action. That first action does not have to be chosen according to the policy. After it is taken, subsequent actions follow the specified policy, and the expected discounted return is evaluated from that setup.

Summary & Key Takeaways

• The lecture introduces the minimum functional analysis needed to study dynamic programming theoretically. It reviews normed vector spaces, contraction mappings, continuity, fixed points, complete normed spaces, and the Banach fixed-point theorem, which connects repeated application of a contraction to convergence toward one unique fixed point at a geometric rate.

• Markov decision processes, discounted returns, state-value functions, action-value functions, and optimal value functions are reviewed before the new analysis begins. Bellman expectation equations characterize values under a fixed policy, while Bellman optimality equations characterize optimal values obtained by maximizing over policies and selecting actions through the transition and reward model.

• The Bellman optimality operator maps bounded real functions over states to other bounded real functions. Its unique fixed point is the optimal value function. The operator is a contraction under the maximum norm with coefficient equal to the discount factor, and it is monotonic because pointwise ordering is preserved after applying the operator.