0
$\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. For formal details, see the following section, with the theorem at the end.

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^{\pi_{V}}\left(s,a\right)\\ 0 & otherwise \end{cases}$$ where $$Q^{\pi_{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]$$

Improve this question
$\endgroup$
5
  • $\begingroup$ I'll just give you a few tips. 1. To prove something of the form "A if and only if B", you need to prove 2 things: If A then B AND if B then A. 2. You need to know the definition of an optimal value function. How is an optimal value function different from a non-optimal one? But you also need to know the definition of a value function (in general). $\endgroup$
    – nbro
    Apr 29 at 18:39
  • 1
    $\begingroup$ I believe there is a proof in the David Silver's RL course, or the Sutton & Barto RL book $\endgroup$
    – Luca Anzalone
    Apr 29 at 19:20
  • $\begingroup$ Your definition of a policy above is circular, and also you need to first differentiate Bellman equation with its optimality equation version. $\endgroup$
    – mohottnad
    Apr 29 at 20:32
  • $\begingroup$ @mohottnad where is the circularity? $\endgroup$
    – snatchysquid
    Apr 30 at 8:06
  • $\begingroup$ @nbro haven't I defined what an optimal policy is? A non-optimal one is a policy with a smaller reward expectation $\endgroup$
    – snatchysquid
    Apr 30 at 8:08

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

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