Convergence of Value-based RL

We often hear that reinforcement learning always converges to a unique fixed point. Why is that?

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.

Given a metric space $(\mathcal{X}, d)$, the infinite sequence $x_1,x_2,x_3…,$ is a Cauchy sequence if for every $\varepsilon\in\mathbb{R}^+$, there exists an $N\in\mathbb{Z}^+$ such that $d(x_a,x_b)<\varepsilon,a,b>N$. This definition formalises the notion of convergence to a fixed point. A metric space is complete if every possible Cauchy sequence among the elements of $\mathcal{X}$ converges to some fixed point that itself lies in $X$. Given a complete metric space $(\mathcal{X},d)$, a function $f:\mathcal{X}\rightarrow \mathcal{X}$ is a contraction if applying it to two elements $x,x’\in\mathcal{X}$ moves them closer together by a factor of at least $\gamma\in[0,1)$, i.e.

\[d(f(x),f(x'))\leq\gamma d(x,x')\]

The Banach fixed point theorem gives a proof of what is intuitively obvious: repeated application of a contraction induces a Cauchy sequence, and thus converges to a unique fixed point $x^\ast\in\mathcal{X}$.

Bellman optimality operator $\mathbb{B}:\mathbb{R}\rightarrow\mathbb{R}$.

\[\mathbb{B}[V(s)]=\underset{a}{\max}r(s,a)+\gamma\sum_{s'}P(s'\vert s,a)V(s')\]

$\mathbb{B}$ recursive can be used to generate a sequence of value functions.

Now let us use the infinity norm to define a metric space $(\mathbb{R},\lVert\cdot\rVert\infty)$. If we can show that $\mathbb{B}$ is a contractor in $(\mathbb{R},\lVert\cdot\rVert\infty)$, then we can conclude that it will eventually give a unique optimal value function $V^\ast$ and in turn, a unique optimal policy $\pi^\ast$. First, let’s write out the equation for the infinity norm after applying $\mathbb{B}$ to two value functions $V_1$, $V_2$:

\[\lVert\mathbb{B}[V_1(s)]-\mathbb{B}[V_2(s)]\rVert_\infty=\lVert\underset{a_1}{\max}(r(s,a_1)+\gamma\sum_{s'}P(s'\vert s,a_1)V_1(s'))-\underset{a_2}{\max}(r(s,a_2)+\gamma\sum_{s'}P(s'\vert s,a_2)V_2(s'))\rVert_\infty\]

The key trick here is to recognise that ==XXXXXXXXXXXXXXXXXXXX==

\[\leq\lVert\underset{a_1}{\max}(\cancel{r(s,a_1)}+\gamma\sum_{s'}P(s'\vert s,a_1)V_1(s'))-\cancel{r(s,a_1)}-\gamma\sum_{s'}P(s'\vert s,a_1)V_2(s'))\rVert_\infty=\gamma\lVert \underset{a_1}{\max}\sum_{s'}P(s'\vert s,a_1)(V_1(s')-V_2(s'))\rVert_\infty\]

Since the infinity norm returns the maximum value over the entire state space, this is equivalent to

\[=\gamma\underset{s',a_1}{\max}\sum_{s'}P(s'\vert s,a_1)(V_1(s')-V_2(s'))=\gamma\underset{s',\cancel{a_1}}{\max}(V_1(s')-V_2(s'))\cancelto{1}{\sum_{s'}P(s'\vert s,a_1)}=\gamma\lVert V_1(s')-V_2(s')\rVert_\infty\]

So therefore

\[\lVert\mathbb{B}[V_1(s)]-\mathbb{B}[V_2(s)]\rVert_\infty\leq\gamma\lVert V_1(s')-V_2(s')\rVert_\infty\]

which means that $\mathbb{B}$ is a contractor in $(\mathbb{R},\lVert\cdot\rVert_\infty)$.

FQI gives no guarantees of convergence to the optimal solution.

  • Proof: Mix of contraction under $\infty$-norm and $\ell 2$-norm.
  • $Q$ learning is not true gradient descent (semi-gradient) because we don’t take the gradient through the target value. Residual algorithms slow and not numerically stable (learning rates).
  • Also means that actor-critic won’t converge (policy gradient converges to local maximum, just like supervised learning).