TransWikia.com

Bellman operator and contraction property

Data Science Asked on May 23, 2021

Currently, I am learning about Bellman Operator in Dynamic Programming and Reinforcement Learning. I would like to know why is Bellman operator contraction with respect to infinity norm? Why not another norm e.g. Euclidian norm?

One Answer

The proofs I have seen for contraction of the bellman operator (this page has a really nice run through, explicitly utilize the fact that an infinity norm is being used. This does not necessarily mean that contraction doesn't occur under other norms, but it does suggest one of two possibilities:

  • The contraction proof is only valid under the infinity norm.
  • The infinity norm is just the easiest metric to prove the contraction property.

When showing that the Bellman Operator converges to a fixed point it is satisfactory to simply show that it is a contraction, it doesn't matter what sort of contraction it is, so we would typically prove the contraction that is easiest to show.

That being said, intuitively, I would imagine that the question of whether or not this contraction holds under other norms would impact questions surrounding the rate of convergence to the fixed point (ie., how many times we must apply the bellman operator for convergence). After a cursory search I was not able to find any theory explicitly proving or disproving the contraction under other norms. This might be an interesting question to raise in the mathematics stack exchange.

Correct answer by James on May 23, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP