What is the time complexity of the value iteration algorithm?

Question

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.

Answer 1

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.