Consider a vector of values $V_k$ and consider the related value $V_{\pi_k}$ obtained by coming the policy $\pi_k$ by acting greedily according to it. i.e.

$$ \pi_k(i) := arg \min_{a \in A} \{ R(i,a) + \alpha \sum_{j \in S} P_{i,j}(a ) V_k \}$$

where $P_{ij}( a ) = Pr[j \mid i, a]$

my question is why is:

$$ V_k \neq V_{\pi_k } $$

my intuition (which is obviously wrong) says that we are acting according to the value function $V_k$ so we should get the same value function out. Why is this reasoning incorrect?

Note that I am sure we could cook up a boring example that shows Im wrong. I don't want that or need that. That won't provide insights to WHY I am wrong, just that I am which I already know.


Your intuition is off because the policy $\pi$ used to form $V_k$ (or what I will denote as $V^{\pi}$) will actually be different than the policy $\pi_k$ if $\pi$ is not optimal. We can show they will be different in the event $\pi$ is not optimal by investigating the following. We can first state the following definitions

\begin{align} V^{\pi}(s) &= R(s, \pi(s)) + \gamma \mathbb{E}_{s' \sim P(s,\pi(s))} \left[V^{\pi}(s')\right] \\ Q^{\pi}(s,a) &= R(s,a) + \gamma \mathbb{E}_{s' \sim P(s,a)} \left[V^{\pi}(s')\right] \end{align}

If we make note of the above definitions, it is clear that $V^{\pi}(s) = Q^{\pi}(s, \pi(s))$. We can also use these definitions to restate $\pi_k$ in the following manner

\begin{align} \pi_k(s) &= \arg \min_{a \in A(s)} \left\lbrace R(s,a) + \gamma \mathbb{E}_{s' \sim P(s,a)} \left[V^{\pi}(s')\right] \right\rbrace \\ &= \arg \min_{a \in A(s)} Q^{\pi}(s,a) \\ &= \arg \min_{a \in A(s)} \left\lbrace Q^{\pi}(s,a) - Q^{\pi}(s, \pi(s))\right\rbrace \end{align}

If we look at the final expression for $\pi_{k}(s)$, it is clear that for a given state $s$, $\pi_k(s)$ will be a better action than $\pi(s)$ unless $\pi(s)$ is already an optimal action for the given state $s$. This implies that $V^{\pi_k}(s) \leq V^{\pi}(s)$ for all $s \in S$. The way one can view it is that the $\arg \min$ step to construct $\pi_k(s)$ is effectively saying "For each state $s$, choose the action $a$ that is most optimal relative to $\pi(s)$ to make as the action choice for $\pi_k(s)$".

  • $\begingroup$ ok so essentially the equality is only true when the bellman equation is satisfied and thats only for the optimal policy. Right? $\endgroup$ – Pinocchio Apr 6 at 19:03
  • $\begingroup$ Right! Equality is only when you have the optimal policy. $\endgroup$ – spektr Apr 6 at 19:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.