1
$\begingroup$

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:

$$V^{\star}\left(s\right)=\max_{a}r\left(s,a\right)+\gamma\mathbb{E}\left[V^{\star}\left(s'\right)\right]$$

$\endgroup$
4
  • $\begingroup$ The proof is too long to be given here: I suggest reading up on Reinforcement Learning by Sutton and Barto. Long story short, the bellman operator $B(F)\mathbb{E}[R(s, a) + \gamma F]$ ($F \in R^n$)forms a contraction mapping on the Banach space of $(R^n, ||.||_{\inf})$, which has the fixed point stated in your question. $\endgroup$
    – cybershiptrooper
    Commented May 7, 2023 at 22:10
  • $\begingroup$ @cybershiptrooper could you perhaps point me to an existing proof? I tried looking at RL by Sutton and Barto, but I didn't find a proof there, only "explanations" $\endgroup$
    – snatchysquid
    Commented May 8, 2023 at 4:17
  • $\begingroup$ drive.google.com/file/d/1X2a5HTZ1uVz66PAz_o2S6ItkAKROAIMO/… $\endgroup$
    – cybershiptrooper
    Commented May 8, 2023 at 5:52
  • $\begingroup$ drive.google.com/file/d/13RsweuRjplu7bm0sRoJMOpldy4HN4skP/view $\endgroup$
    – cybershiptrooper
    Commented May 8, 2023 at 5:52

1 Answer 1

Reset to default
0
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ why they proved the limit obtained by applying the bellman optimal operator is $V_{*}$ the optimal value function? $\endgroup$
    – piero
    Commented Sep 24, 2023 at 3:50
  • $\begingroup$ @piero I'm not sure I understand the question. Could you rephrase? $\endgroup$
    – snatchysquid
    Commented Sep 24, 2023 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
    Commented Sep 24, 2023 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$
    – snatchysquid
    Commented Sep 24, 2023 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
    Commented Sep 24, 2023 at 16:01

You must log in to answer this question.

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