The Question

I'd like to prove that a function $V$ (like in reinforcement learning) is optimal iff it satisfies the Bellman equation. A lot of places online reference this fact, but none prove it.

Formal definitions

In reinforcement learning, a value function $V$ is used to derive a policy: $$\pi_{V}\left(a\mid s\right)=\begin{cases} 1 & a=\underset{a'}{\mathrm{argmax}}Q^{V}\left(s,a\right)\\ 0 & \text{otherwise} \end{cases}$$ where $$Q^{V}\left(s,a\right)=r\left(s,a\right)+\gamma\underset{s'\sim p\left(s'\mid s,a\right)}{\mathbb{E}}\left[V\left(s'\right)\right]$$ (here $r$ is the reward function and $p$ is the transition probability from a state to another based on the action)

A policy $\pi^\star$ is called optimal if $$\pi^{\star}=\underset{\pi}{\mathrm{argmax}}\mathbb{E}_{\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}\cdot r\left(s_{t},a_{t}\right)\mid s_{0}=s\right]$$ where $s$ is the initial state, and the expectation is over the transition probability under the assumption of following the policy $p$.

We also say that $V$ is optimal if $\pi_{V}$ is optimal.

The Theorem I want to prove is that a function $V^\star$ is optimal if and only if it satisfies the Bellman equation:



1 Answer 1


A friend of mine showed me the following "post", and the proof is actually quite short.

They prove that $$\lim_{k\to\infty}V_{k}=V^{\star}$$ where $V_k$ is defined in the post. Now if the original $V$ satisfies the bellman equation already, it means that $$\lim_{k\to\infty}V_{k}=V$$ and therefore $V^{\star}=V$. The other direction is of course easy.

  • $\begingroup$ why they proved the limit obtained by applying the bellman optimal operator is $V_{*}$ the optimal value function? $\endgroup$
    – piero
    Sep 24 at 3:50
  • $\begingroup$ @piero I'm not sure I understand the question. Could you rephrase? $\endgroup$ Sep 24 at 7:15
  • $\begingroup$ Sorry. In the post you mentioned, it is stated that $\lim{\cal T^*}^k V = V_{*}$, but actually they didn't show any proof of this fact. What I mean is that the banach theorem states that this limit converges, but why it converges to $V_{*}$? $\endgroup$
    – piero
    Sep 24 at 15:33
  • $\begingroup$ @piero they did prove that - Theorem 4 (which relies on previous theorems). [Note that $V_{k}$ is defined to be the result of repeatedly applying $\mathcal{T}$] $\endgroup$ Sep 24 at 15:52
  • $\begingroup$ it says "note that $V_{*}$ is a fixed point of $\cal T$", tha is my concern, because it was not proven. Also, I see that they $\textbf{assumed}$ $V_{*}$ satisfies the bellman optimality equation before, in this case it will obviously be a fixed point, but as I am saying it is not proved. $\endgroup$
    – piero
    Sep 24 at 16:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .