3
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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).

enter image description here

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.

enter image description here

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.

enter image description here

| improve this answer | |
$\endgroup$
  • 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 evaluation subroutine how is V(s) exactly updated? I get that in value iteration we are taking the value of the action that gives the maximum value, but what are we doing in the policy evaluation case? $\endgroup$ – PyWalker27 Apr 21 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$ – nbro Apr 21 at 23:16
  • $\begingroup$ The algorithm above, it appears is doing in an inplace update, right? $\endgroup$ – PyWalker27 Apr 21 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$ – nbro Apr 22 at 12:13

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.