Exercise 3.3.2

Policy iteration: time complexity with V(s) versus Q(s,a)

MediumWritten

Consider the policy iteration algorithm for estimating \(\pi \approx \pi_*\). What is the time complexity of policy iterations using \(V(s)\) and using \(Q(s,a)\)? Provide the answer in big-\(O\) notation and assume evaluation takes \(K\) iterations to converge and the algorithm as a whole to take \(K'\) steps to converge. Additionally, assume the 3-argument transition function \(p(s'|s,a) = \sum_r p(s',r|s,a)\) is used instead of the 4-argument one and that we have a deterministic policy where lookup takes \(O(1)\) time.

boxed text
Policy iteration pseudocode from Sutton & Barto (2018), Section 4.3.