Answers.Body: <p>The update equation for <a href="https://artint.info/html/ArtInt_227.html" rel="nofollow noreferrer">value iteration</a> that you show is time complexity <span class="math-container">$O(|\mathcal{S}\times\mathcal{A}|)$</span> for each update to a single <span class="math-container">$V(s)$</span> estimate, because it iterates over all actions to perform <span class="math-container">$\text{max}_a$</span> and over all next states for <span class="math-container">$\sum_{s'}$</span>.</p>
  
  <p>The sources you have found are probably counting an entire <em>sweep</em> through the state space as an "iteration" i.e. <span class="math-container">$\forall \space s \in \mathcal{S}: V_{k+1}(s) \leftarrow \text{max}_a \sum_{s'} T...$</span> That adds another factor of <span class="math-container">$|\mathcal{S}|$</span> making the overall complexity <span class="math-container">$O(|\mathcal{S}\times\mathcal{S}\times\mathcal{A}|)$</span> or <span class="math-container">$O(|\mathcal{S}|^2|\mathcal{A}|)$</span></p>
  
  <p>This definition of iteration makes sense, as the basic value iteration algorithm is <em>required</em> 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. </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-11-17T16:00:26.190Z
Answers.Text: Thanks Neil. I think that’s the answer. They have considered the whole state space.
Answers.UserDisplayName: Shifat E Arman
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-11-17T16:08:52.597Z
Answers.Text: @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.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-11-17T14:07:25.403Z
Answers.LastActivityDate: 2018-11-17T14:55:12.840Z
Answers.LastEditDate: 2018-11-17T14:55:12.840Z
Answers.UserDisplayName: Neil Slater
Body: <p>Recently, I have come across the information (lecture 8 and 9 about MDPs of <a href="http://ai.berkeley.edu/lecture_slides.html" rel="nofollow noreferrer">this UC Berkeley AI course</a>) that the time complexity for each iteration of the value iteration algorithm is <span class="math-container">$\mathcal{O}(|S|^{2}|A|)$</span>, where <span class="math-container">$|S|$</span> is the number of states and <span class="math-container">$|A|$</span> the number of actions.</p>
  
  <p>Here is the equation for each iteration:</p>
  
  <p><span class="math-container">$$
  V_{k+1}(s) \gets \max_a \sum_{s'} T(s, a, s') [R(s, a, s') + \gamma V_k(s')]
  $$</span></p>
  
  <p>I could't understand why the time complexity is <span class="math-container">$\mathcal{O}(|S|^{2}|A|)$</span>. I searched the internet, but I didn't find any good explanation. </p>
  
Tags: <reinforcement-learning><algorithm><time-complexity><value-iteration>
Title: What is the time complexity of the value iteration algorithm?
UserDisplayName: Shifat E Arman
ThreadText: # What is the time complexity of the value iteration algorithm?
  
  (Asked by: username_0 on 2018-11-17)
  
  Recently, I have come across the information (lecture 8 and 9 about MDPs of [this UC Berkeley AI course](http://ai.berkeley.edu/lecture_slides.html)) 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.
  
  **Tags:** reinforcement-learning, algorithm, time-complexity, value-iteration
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2018-11-17. Score: 1 | Accepted answer
  
  The update equation for [value iteration](https://artint.info/html/ArtInt_227.html) 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.
  
  > **Comments:**
  > **username_0**: Thanks username_1. I think that’s the answer. They have considered the whole state space.  
  > **username_1**: @username_0: 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.  
  
  ---
  
  