2
$\begingroup$

Recently, I have come across the information (lecture 8 and 9 about MDPs of this UC Berkeley AI course) that the time complexity for each iteration of the value iteration algorithm is $\mathcal{O}(|S|^{2}|A|)$, where $|S|$ is the number of states and $|A|$ the number of actions.

Here is the equation for each iteration:

$$ V_{k+1}(s) \gets \max_a \sum_{s'} T(s, a, s') [R(s, a, s') + \gamma V_k(s')] $$

I could't understand why the time complexity is $\mathcal{O}(|S|^{2}|A|)$. I searched the internet, but I didn't find any good explanation.

$\endgroup$
1
$\begingroup$

The update equation for value iteration that you show is time complexity $O(|\mathcal{S}\times\mathcal{A}|)$ for each update to a single $V(s)$ estimate, because it iterates over all actions to perform $\text{max}_a$ and over all next states for $\sum_{s'}$.

The sources you have found are probably counting an entire sweep through the state space as an "iteration" i.e. $\forall \space s \in \mathcal{S}: V_{k+1}(s) \leftarrow \text{max}_a \sum_{s'} T...$ That adds another factor of $|\mathcal{S}|$ making the overall complexity $O(|\mathcal{S}\times\mathcal{S}\times\mathcal{A}|)$ or $O(|\mathcal{S}|^2|\mathcal{A}|)$

This definition of iteration makes sense, as the basic value iteration algorithm is required to sweep through the whole state space in order to converge. This also matches the standard test for convergence, which is made after each full sweep, and checks what the largest absolute update was at the end of the sweep - if it is below some target value for accuracy then the process is declared complete.

$\endgroup$
  • $\begingroup$ Thanks Neil. I think that’s the answer. They have considered the whole state space. $\endgroup$ – Shifat E Arman Nov 17 '18 at 16:00
  • $\begingroup$ @ShifatEArman: Yes. Also, in practice $\sum_{s'}$ may not be a full multiplier of $|\mathcal{S}|$ for deterministic or easy-to-calculate transitions. But in the general case it is. $\endgroup$ – Neil Slater Nov 17 '18 at 16:08

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.