DP may not be practical for very large problems, but compared with other
methods for solving MDPs, DP methods are actually quite efficient. If we ignore
a few technical details, then the (worst case) time DP methods take to find an
optimal policy is polynomial in the number of states and actions. If 
and 
denote the number of states and actions, this means
that a DP method takes a number of computational operations that is
less than some polynomial function of 
and 
. A DP method is
guaranteed to find an optimal policy in polynomial time even though the
total number of (deterministic) policies is 
. In this sense, DP is
exponentially faster than any direct search in policy space could be,
because direct search would have to exhaustively examine each policy to
provide the same guarantee. Linear programming methods can also be used to solve
MDPs, and in some cases their worst-case convergence guarantees are better than
those of DP methods. But linear programming methods become impractical at a much
smaller number of states than do DP methods (by a factor of about 100). For
the largest problems, only DP methods are feasible.
DP is sometimes thought to be of limited applicability because of the curse of dimensionality (Bellman, 1957a), the fact that the number of states often grows exponentially with the number of state variables. Large state sets do create difficulties, but these are inherent difficulties of the problem, not of DP as a solution method. In fact, DP is comparatively better suited to handling large state spaces than competing methods such as direct search and linear programming.
In practice, DP methods can be used with today's computers to solve MDPs with millions of states. Both policy iteration and value iteration are widely used, and it is not clear which, if either, is better in general. In practice, these methods usually converge much faster than their theoretical worst-case run times, particularly if they are started with good initial value functions or policies.
On problems with large state spaces, asynchronous DP methods are often preferred. To complete even one sweep of a synchronous method requires computation and memory for every state. For some problems, even this much memory and computation is impractical, yet the problem is still potentially solvable because only a relatively few states occur along optimal solution trajectories. Asynchronous methods and other variations of GPI can be applied in such cases and may find good or optimal policies much faster than synchronous methods can.