🍥 Convergence

We can prove the convergence of certain ♟️ Reinforcement Learning algorithms, specifically tabular methods, via some linear algebra. First, let reward, transition probabilities, and value functions be defined as matrices,

In this notation, we can express 💎 Value Iteration as

where can be seen as the Bellman optimality operator. To prove that value iteration converges, we can first show that for any two and , the operator follows

Intuitively, this is saying that after applying , and get closer together (by a factor of ).

Next, consider the optimal value function , which is stationary under the Bellman optimality operator,

With the result from above, we then have

and applying it times as goes to infinity, we have