I am trying to implement value and policy iteration algorithms. My value function from policy iteration looks vastly different from the values from value iteration, but the policy obtained from both is very similar. How is this possible? And what could be the possible reasons for this?
$\begingroup$
$\endgroup$
0
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
Both value iteration (VI) and policy iteration (PI) algorithms are guaranteed to converge to the optimal policy, so it is expected that you get similar policies from both algorithms (if they have converged).
However, they do this differently. VI can be seen as truncated version of PI.
Let me first illustrate the pseudocode of both algorithms (taken from Barto and Sutton's book), which I suggest you get familiar with (but you are probably already familiar with them if you implemented both algorithms).
As you can see, policy iteration updates the policy multiple times, because it alternates a step of policy evaluation and a step of policy improvement, where a better policy is derived from the current best estimate of the value function.
On the other hand, value iteration updates the policy only once (at the end).
In both cases, the policies are derived from the value functions in the same way. So, if you obtain similar policies, you may think that they are necessarily derived from similar final value functions. However, in general, this may not the case, and this is actually the motivation for the existence of value iteration, i.e. you may derive an optimal policy from an non-optimal value function.
Barto and Sutton's book provide an example. See figure 4.1 on page 77 (p. 99 of the pdf). For completeness, here's a screenshot of the figure.
-
1$\begingroup$ That cleared it up a little! Thank you! Thanks for making the question more clear too! I also have an implementation related question, in the policy iteration,
policy evaluationsubroutine how is V(s) exactly updated? I get that invalue iterationwe are taking the value of the action that gives the maximum value, but what are we doing in thepolicy evaluationcase? $\endgroup$– r4bb1tApr 21, 2020 at 22:46 -
$\begingroup$ @PyWalker27 There are actually two possible implementations of PE: one where you update V in place and the other where you maintain two arrays. Sutton and Barto's book explain this. Have a look at chapter 4. $\endgroup$– nbroApr 21, 2020 at 23:16
-
$\begingroup$ The algorithm above, it appears is doing in an inplace update, right? $\endgroup$– r4bb1tApr 21, 2020 at 23:18
-
1$\begingroup$ @PyWalker27 Yes, it appears to be in-place (but I suggest you read the section about the topic of chapter 4 to confirm that this is the case). If it wasn't in-place, we should be using a different
V(s)on the left-hand side of $\leftarrow$. $\endgroup$– nbroApr 22, 2020 at 12:13
$\begingroup$
$\endgroup$
More comments in addition to the accepted answer.
The OP says the two algorithms have different value functions. This is actually not precise and may be the source of confusion. In particular, only in the policy iteration algorithm, the value of $v$ is the state value function, which is the solution to the Bellman equation. However, the value of $v$ in value iteration is not a state value function! That is simply because it is not the solution to any Bellman equation in general. Then, what is the $v$ in value iteration? See another answer of mine.
Why value iteration, which does not calculate the state values, can find the optimal policy? It would be easier to see that if you think of it as a simple numerical iterative algorithm solving the Bellman optimality equation. The algorithm follows from the contraction (or called fixed-point) theorem when we analyze the Bellman optimality equation.