Content deleted Content added
mNo edit summary |
|||
Line 77:
In this variant, the steps are preferentially applied to states which are in some way important – whether based on the algorithm (there were large changes in <math>V</math> or <math>\pi</math> around those states recently) or based on use (those states are near the starting state, or otherwise of interest to the person or program using the algorithm).
===Computational complexity===
Algorithms for finding optimal policies with [[time complexity]] polynomial in the size of the problem representation exist for finite MDPs. Thus, [[decision problem]]s based on MDPs are in computational [[complexity class]] [[P (complexity)|P]].<ref>{{cite journal
| |||