I'm reading Szepesvári's book on RL. My question is concerning the proof of Theorem A.10 (p. 71).

Theorem Let $V$ be the fixed point of $T^∗$ and assume that there is policy $π$ which is greedy w.r.t $V:T^πV=T^∗V$. Then $V=V^∗$ and $π$ is an optimal policy.

With the Bellman Optimality Operator, which is a contraction, defined as $$(T^∗V )(x)=\text{sup}_{a\in \mathcal{A}}\Bigl\{ r(x,a)+ \gamma \sum_{y\in \mathcal{X}}P(x, a, y) V(y) \Bigr\},\ x\in \mathcal{X}$$

and the optimal value-functions defined as $$V^*(x) = \text{sup}_{a \in \mathcal{A}} Q^*(x, a), \ x\in\mathcal{X}$$ $$Q^*(x, a) = r(x, a) + \gamma\sum_{y \in\mathcal{X}}P(x,a,y) V^*(y), \ x\in\mathcal{X}, a\in\mathcal{A}.$$ Thus $$V^*(x) = \text{sup}_{a \in \mathcal{A}} \Bigl\{ r(x,a) + \gamma\sum_{y\in \mathcal{X}} P(x, a, y) V^*(y) \Bigr\}, \ x \in \mathcal{X}.$$

In the proof of the Theorem, Szepesvári states that we cannot know if $V=V^*$ or not. My Question is: Why can't we? Applying $T^*$ to $V^*$ we get $T^*V^*=V^*$ and due to Banach's fixed point theorem the fixed point of $T^*$ is unique, hence $V=V^*$.


1 Answer 1


Your reference link is broken, however, there's no theoretical reason you can immediately arrive at $T^∗V^∗=V^*$ merely by their definitions, where $T^*$ is assumed to be the Bellman optimality operator and $V^*$ is assumed to be the optimal state value function. This theorem seems just to try to establish this unavoidable conclusion. First the author assumes $V$ to be the fixed point of $T^*$ which could be proved to be a contraction map from analysis, but in order to achieve above goal an additional assumption (there exists a policy $π$ which is greedy w.r.t $V$) is required. Then we can immediately arrive at $T^πV=T^∗V$ since $T^∗$ is greedy by definition and then we have $T^πV=V$ by the above first assumption of this theorem which is nothing but the ordinary Bellman equation following the assumed policy $π$. Now by your reasoning and background knowledge if $V^*$ is the optimal state value then the said $π$ must be its corresponding policy which is also optimal. So the remaining work of this theorem is to prove the fixed point is indeed the optimal state value, and in fact the value iteration algorithm was inspired by such a proof.

  • $\begingroup$ First of all, thanks for the answer! But I still don't get it. If I replace $V$ by $V^*$ in the definition of $T$, then the right hand side of that definition will equal the right hand side of the definiton of $V^*$, right? $\endgroup$ Commented Mar 26, 2023 at 15:02
  • 1
    $\begingroup$ Note here $T^π$ is the common Bellman operator following policy $π$, while $T^*$ is the greedy Bellman optimality operator which doesn't explicitly depend on any specific policy and only the latter can be proved to have a (unique) fixed point while itself doesn't directly claim satisfying the common Bellman equation. The gist of this theorem is to prove the existence and uniqueness of the optimal state value $V^*$ and its corresponding (optimal greedy) policy $π$ (may not be unique though) via the common Bellman equation with operator $T^π$. This difference hopefully clarifies your confusion $\endgroup$
    – cinch
    Commented Mar 26, 2023 at 20:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.