  This note provides a simple example demonstrating that, if exact computations
are allowed, the number of iterations required for the value iteration
algorithm to find an optimal policy for discounted dynamic programming problems
may grow arbitrarily quickly with the size of the problem. In particular, the
number of iterations can be exponential in the number of actions. Thus, unlike
policy iterations, the value iteration algorithm is not strongly polynomial for
discounted dynamic programming.
