3
$\begingroup$

Both value iteration and policy iteration are General Policy Iteration (GPI) algorithms. However, they differ in the mechanics of their updates. Policy Iteration seeks to first find a completed value function for a policy, then derive the Q function from this and improve the policy greedily from this Q. Meanwhile, Value Iteration uses a truncated V function to then obtain Q updates, only returning the policy once V has converged.

What are the inherent advantages of using one over the other in a practical setting?

$\endgroup$
1
  • 2
    $\begingroup$ I think there's a typo here "V function to then obtain Q updates". What do you mean by "Q updates"? Maybe you mean "to obtain policy updates". $\endgroup$
    – nbro
    Oct 11 '21 at 22:20
0
$\begingroup$

Value Iteration Vs Policy Iteration

Below is the list of differences & similarities between value iteration and policy iteration

Differences

Value Iteration Policy Iteration
Architecture Value iteration networkVI Architecture reference Policy iteration architecture PI Architecture Reference
Execution starts with a random value function random policy
Algorithm simpler complex
Computation costs more expensive cheaper
Execution time Slower Faster
No of Iterations to converge significantly more takes fewer iteration to converge
Guaranteed to converge Yes Yes

Similarities

  • both are dynamic programming algorithms
  • both employ variations of Bellman updates
  • Both exploit one-step look-ahead
  • Both algorithms are guaranteed to converge to an optimal policy in the end

Policy iteration is reported to conclude faster than value iteration

USAGE PREFERENCE

As mentioned earlier in the difference, the main advantage for using Policy iteration over value iteration is its ability to conclude faster with fewer iterations thereby reducing its computation costs and execution time.

REFERENCES

  1. Research papers
  2. Book
    • Artificial Intelligence: A Modern Approach, by Peter Norvig and Stuart J. Russell Chapter 17 Making Complex decisions
  3. Architecture
$\endgroup$
4
  • 4
    $\begingroup$ The presentation/readability of this answer is good, but this does not answer the question "When to use one over the other?". Moreover, you do not explain 1. why value iteration is slower and more expensive than policy iteration and 2. who claimed that (i.e. cite something reliable). In any case, I don't understand why you say that policy iteration is "complex". Both algorithms are simple enough. $\endgroup$
    – nbro
    Oct 12 '21 at 6:45
  • 2
    $\begingroup$ I added the notice because you're not really citing anything that supports the claim e.g. that policy iteration "takes fewer iteration to converge". Provide inline references/citations to research papers or books that support those claims (e.g. you can use this mathjax style [\[1\][1]] and it will be shown as [1]. Moreover, your last edit actually made things worse. For example, the diagram for value iteration is wrong. You're confused. Please, do not provide wrong information to the site. If you're not reasonably familiar with the concepts, don't provide an answer just by guessing. $\endgroup$
    – nbro
    Dec 26 '21 at 18:52
  • 1
    $\begingroup$ @nbro: The claim that policy iteration is "complex" is made, though not explained, in this tutorial, on which this answer appears to be very closely based. $\endgroup$ Dec 29 '21 at 14:09
  • 1
    $\begingroup$ @Scortchi-ReinstateMonica Yes, thanks. It looks like this answer is based on that tutorial. The initial table provided by the OP is really analogous to the one given in that tutorial. This answer is now more misleading than originally. In the last edit, the OP provided the diagram of "Value Iteration Network", which is not "value iteration". We may need to delete this answer to avoid spreading misinformation, although some info in this answer may be correct. More importantly, this does not even answer the question "when to use one over the other?". Not sure why it was accepted. $\endgroup$
    – nbro
    Dec 29 '21 at 14:16
0
$\begingroup$

Value iteration (VI) is a truncated version of Policy iteration (PI).

PI has two steps:

  • the first step is policy evaluation. That is to calculate the state values of a given policy. This step essentially solves the Bellman equation $$v_\pi=r_\pi+\gamma P_\pi v_\pi$$ which is the matrix vector form of the Bellman equation. I assume that the basics are already known.
  • The second is policy improvement. That is to select the action corresponding to the greatest action value at each state (i.e., greedy policy): $$\pi=\arg\max_\pi(r_\pi+\gamma P_\pi v_\pi)$$

The key point is: the policy iteration step requires an infinite number of iterations to solve the Bellman equation (i.e., get the exact state value). In particular, we use the following iterative algorithm so solve the Bellman equation: $$v_\pi^{(k+1)}=r_\pi+\gamma P_\pi v_\pi^{(k)}, \quad k=1,2,\dots$$ We can prove that $v_\pi^{(k)}\rightarrow v_\pi$ as $k\rightarrow\infty$. There are three cases to execute this iterative algorithm:

  • Case 1: run an infinite number of iterations so that $ v_\pi^{(\infty)}=v_\pi$. This is impossible in practice. Of course, in practice, we may run sufficiently many iterations until certain metrics (such as the difference between two consecutive values) are small enough).
  • Case 2: run just one single step so that $ v_\pi^{(2)}$ is used for policy improvement step.
  • Case 3: run a few times (e.g., N times) so that $ v_\pi^{(N+1)}$ is used for the policy improvement step.

Case 1 is the policy iteration algorithm; case 2 is the value iteration algorithm; case 3 is a more general truncated version. Such a truncated version does not require infinite numbers of iterations and can converge faster than case 2, it is often used in practice.

$\endgroup$
16
  • 1
    $\begingroup$ GPI is not a practical algorithm as suggested in this answer, but instead a principle behind design of most value-based approaches. The attempt to define policy iteration as not used in practice, because no-one runs it in an infinite loop, is a bold move, and not something you would see in e.g. Sutton & Barto, where the issue is simply resolved by a hyperparameter $\theta$ that stops the evaluation loop. The resulting algorithm is still called Policy Iterationm and is used in practice without the need to invoke GPI $\endgroup$ Oct 22 '21 at 14:22
  • 1
    $\begingroup$ The GPI is not an actual algorithm that you can implement directly (with perhaps one or two free choices). Whilst PI and VI are. Of course you are free to categorise things how you like, but your choice here puts you at odds with the literature. $\endgroup$ Oct 23 '21 at 7:45
  • 1
    $\begingroup$ @Shiyu The best way to prove your point would have been to quote the book. However, if you read section 4.6 of the book we're talking about (2nd edition), you will see that they write something that is inconsistent with what you wrote in this answer and that is consistent with what Neil wrote above. For completeness, here's what they write. $\endgroup$
    – nbro
    Oct 23 '21 at 14:43
  • 1
    $\begingroup$ "We use the term generalized policy iteration (GPI) to refer to the general idea of letting policy-evaluation and policy-improvement processes interact, independent of the granularity and other details of the two processes. Almost all reinforcement learning methods are well described as GPI. That is, all have identifiable policies and value functions, with the policy always being improved with respect to the value function and the value function always being driven toward the value function for the policy, as suggested by the diagram to the right." $\endgroup$
    – nbro
    Oct 23 '21 at 14:44
  • 1
    $\begingroup$ So, GPI is not an algorithm. It's a general idea. You could say it's a class of algorithms, in the same way that "best-first search" is not an algorithm, but a class of algorithms, where (specific) algorithms like A*, B* or greedy BFS fall into. $\endgroup$
    – nbro
    Oct 23 '21 at 14:46

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.