Answers.Body: <p>To fully understand generically the transition dynamics from state <span class="math-container">$x$</span> to state <span class="math-container">$x′$</span> in terms of action values without state values involvement, we need to evaluate all possible combinations of actions for both states via their respective action values <span class="math-container">$q(x,u),q(x',u')$</span>. Since for each state there are at most <span class="math-container">$m$</span> possible actions, this means there are at most <span class="math-container">$m^2$</span> possible combinations of actions for <em>every</em> pair of states <span class="math-container">$x$</span> and <span class="math-container">$x′$</span>s. Furthermore there're at most <span class="math-container">$n^2$</span> state transition pairs obviously, therefore you arrive at complexity is inferior with <span class="math-container">$O(m^2·n^2)$</span>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-03-19T04:10:39.360Z
Answers.LastActivityDate: 2024-03-19T04:16:18.570Z
Answers.LastEditDate: 2024-03-19T04:16:18.570Z
Answers.UserDisplayName: cinch
Body: <p>Please see slide 32 in the following lecture slides on DP:</p>
  <p><a href="https://groups.uni-paderborn.de/lea/share/lehre/reinforcementlearning/lecture_slides/built/Lecture03.pdf" rel="nofollow noreferrer">https://groups.uni-paderborn.de/lea/share/lehre/reinforcementlearning/lecture_slides/built/Lecture03.pdf</a></p>
  <p>Let <span class="math-container">$m$</span> the size size of action space in MPD.
  Why are there up to <span class="math-container">$m^2$</span> action values when we consider the complexity of DP based on <span class="math-container">$q(x,u)$</span> ?</p>
  
Tags: <reinforcement-learning><markov-decision-process><dynamic-programming>
Title: Why are there up to $m^2$ action values when we consider the complexity of DP based on $q(x,u)$?
UserDisplayName: DSPinfinity
ThreadText: # Why are there up to $m^2$ action values when we consider the complexity of DP based on $q(x,u)$?
  
  (Asked by: username_0 on 2024-03-19)
  
  Please see slide 32 in the following lecture slides on DP:
  
  <https://groups.uni-paderborn.de/lea/share/lehre/reinforcementlearning/lecture_slides/built/Lecture03.pdf>
  
  Let $m$ the size size of action space in MPD.
  Why are there up to $m^2$ action values when we consider the complexity of DP based on $q(x,u)$ ?
  
  **Tags:** reinforcement-learning, markov-decision-process, dynamic-programming
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2024-03-19. Score: 2 | Accepted answer
  
  To fully understand generically the transition dynamics from state $x$ to state $x′$ in terms of action values without state values involvement, we need to evaluate all possible combinations of actions for both states via their respective action values $q(x,u),q(x',u')$. Since for each state there are at most $m$ possible actions, this means there are at most $m^2$ possible combinations of actions for *every* pair of states $x$ and $x′$s. Furthermore there're at most $n^2$ state transition pairs obviously, therefore you arrive at complexity is inferior with $O(m^2·n^2)$.
  
  
  ---
  
  