5
$\begingroup$

In Sutton and Barto's book about reinforcement learning, policy iteration and value iterations are presented as separate/different algorithms.

This is very confusing because policy iteration includes an update/change of value and value iteration includes a change in policy. They are the same thing, as also shown in the Generalized Policy Iteration method.

Why then, in many papers as well, they (i.e. policy and value iterations) are considered two separate update methods to reach an optimal policy?

$\endgroup$
3
$\begingroup$

Policy iteration is made up of two steps. The first is a full policy evaluation, where a value function is calculated for the current policy. The second is policy improvement, where the policy is made greedy with respect to the value function.

Value iteration looks to speed things up by stopping policy evaluation after one iteration, make the policy greedy with respect to that value function, and repeat until convergence.

Clearly, these are two different algorithms, hence why they are considered to be different. They are, however, very closely linked, which is why you might consider them to be 'the same thing'. I guess you could say they belong to the same family of algorithm.

| improve this answer | |
$\endgroup$
1
$\begingroup$

Policy iteration is based on the insight that for a given policy, it is straightforward to compute the value function (the long-run expected discounted value of being in a given stage) exactly -- it is a set of linear equations at that point. So, we update the policy, then calculate the exact values of the states for always following that particular policy, and based on that we update the policy again, etc.

Value iteration, in contrast, does not use that insight. It just updates estimates of the values of being in the states one step at a time. If these values are initialized at 0, you can think of this of the $i$th iteration computing the value of what would be the optimal policy if we knew the MDP would end after $i$ iterations. We never really have to think explicitly about policies (though we are in effect computing a policy each iteration), and never directly calculate the infinite sum of expected discounted rewards.

These are just the vanilla variants and it is possible to mix and match these ideas -- e.g., you might not evaluate a policy by explicitly solving a system of linear equations but rather just do some iterations -- but the vanilla variants are clearly distinct.

| improve this answer | |
$\endgroup$

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.