Answers.Body: <p>Value iteration is a dynamic programming algorithm used to compute the optimal policy for a Markov Decision Process (MDP) and in practice value iteration proceeds until the value function converges to a solution that is close enough to the optimal value function as stated on page 82 of Sutton &amp; Barto's RL book.</p>
  <blockquote>
  <p>value iteration formally requires an infinite number of iterations to converge exactly to <span class="math-container">$v_*$</span>. In practice, we stop once the value function changes by only a small amount in a sweep.</p>
  </blockquote>
  <p>Common choices for this small amount are small positive numbers such as <span class="math-container">$0.01, 0.001$</span>, or even smaller which is influenced by how much accuracy is needed in the value function and how long you're willing to wait for convergence on a case by case basis.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-09-15T07:28:13.363Z
Answers.Text: I am not referring to iteration, but only to the recursion part. As far as I know there is not validation happening.
Answers.UserDisplayName: Jack Miles
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-09-15T16:16:49.630Z
Answers.Text: @JackMiles There is no recursion used in Value Iteration. Current best estimate values are used to resolve $V(s')$.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-09-15T18:09:05.467Z
Answers.Text: But doesn't V(s') exactly suggest this?
Answers.UserDisplayName: Jack Miles
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-09-16T17:56:43.833Z
Answers.Text: @JackMiles It's called value iteration (not value recursion) and policy update (not policy iteration or recursion) for a reason. Yes it calls itself but there's no intrinsic conflict here, and in value iteration we're not really dealing with value functions but iterated approximated values.
Answers.UserDisplayName: cinch
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-09-16T21:07:36.480Z
Answers.Text: @JackMiles Yes, see foreverska's answer, you could create a method that recursed state values via the Bellman equation. That's not what value iteration does though. Such an approach would not be called value iteration, and would more like a tree search/evaluation.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-09-14T21:25:37.283Z
Answers.LastActivityDate: 2024-09-14T21:25:37.283Z
Answers.UserDisplayName: cinch
Answers.Body: <p>Historically value iteration was tabular.  So the “function” V(s) was just looking up a value in a table.  As such, there is no recursion (per se).</p>
  <p>There’s nothing that requires a table (or any other single step estimator).  If the estimator actually implemented recursion, there is fundamentally two ways for recursion to end.  First is that the environment is episodic and naturally ends on a long enough timeline.  The second is to discount future rewards, effectively making it episodic at infinity.  This doesn’t end recursion on its own but we must remember why we’re estimating V or Q, to decide on an action.  At some point, with finite rewards, the discount factor becomes so small that any further estimation won’t change action rankings.  This is a natural place to stop.  If rewards are not bounded, this no longer works and some other simplification is needed (setting an artificial limit to recursion depth).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-09-16T17:33:36.680Z
Answers.LastActivityDate: 2024-09-16T17:33:36.680Z
Answers.UserDisplayName: foreverska
Body: <p>Value iteration is a recursive function which calls itself to infinity. However, I can not find any mentioning how deep the recursion should go. Or in other words how often should the function call itself during one iteration?</p>
  <p>How would I end the recursion?</p>
  <p>The formula goes like this.:</p>
  <p><a href="https://i.sstatic.net/ZlEzfqmS.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/ZlEzfqmS.png" alt="[V(s)\leftarrow R(s)+\gamma \max_{a\in A}\sum R(s)*V(s')]" /></a></p>
  <p>The and V(s) should call it selft infinately time before evaluating anything.</p>
  
Tags: <value-iteration>
Title: How deep to go in recursion for value iteration
UserDisplayName: Jack Miles
ThreadText: # How deep to go in recursion for value iteration
  
  (Asked by: username_0 on 2024-09-14)
  
  Value iteration is a recursive function which calls itself to infinity. However, I can not find any mentioning how deep the recursion should go. Or in other words how often should the function call itself during one iteration?
  
  How would I end the recursion?
  
  The formula goes like this.:
  
  [![[V(s)\leftarrow R(s)+\gamma \max_{a\in A}\sum R(s)*V(s')]](https://i.sstatic.net/ZlEzfqmS.png)](https://i.sstatic.net/ZlEzfqmS.png)
  
  The and V(s) should call it selft infinately time before evaluating anything.
  
  **Tags:** value-iteration
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2024-09-14. Score: 1
  
  Value iteration is a dynamic programming algorithm used to compute the optimal policy for a Markov Decision Process (MDP) and in practice value iteration proceeds until the value function converges to a solution that is close enough to the optimal value function as stated on page 82 of Sutton & Barto's RL book.
  
  > value iteration formally requires an infinite number of iterations to converge exactly to $v\_\*$. In practice, we stop once the value function changes by only a small amount in a sweep.
  
  Common choices for this small amount are small positive numbers such as $0.01, 0.001$, or even smaller which is influenced by how much accuracy is needed in the value function and how long you're willing to wait for convergence on a case by case basis.
  
  > **Comments:**
  > **username_0**: I am not referring to iteration, but only to the recursion part. As far as I know there is not validation happening.  
  > **username_2**: @username_0 There is no recursion used in Value Iteration. Current best estimate values are used to resolve $V(s')$.  
  > **username_0**: But doesn't V(s') exactly suggest this?  
  > **username_1**: @username_0 It's called value iteration (not value recursion) and policy update (not policy iteration or recursion) for a reason. Yes it calls itself but there's no intrinsic conflict here, and in value iteration we're not really dealing with value functions but iterated approximated values.  
  > **username_2**: @username_0 Yes, see username_3's answer, you could create a method that recursed state values via the Bellman equation. That's not what value iteration does though. Such an approach would not be called value iteration, and would more like a tree search/evaluation.  
  
  ---
  
  ### Answer by username_3 on 2024-09-16. Score: 1
  
  Historically value iteration was tabular. So the “function” V(s) was just looking up a value in a table. As such, there is no recursion (per se).
  
  There’s nothing that requires a table (or any other single step estimator). If the estimator actually implemented recursion, there is fundamentally two ways for recursion to end. First is that the environment is episodic and naturally ends on a long enough timeline. The second is to discount future rewards, effectively making it episodic at infinity. This doesn’t end recursion on its own but we must remember why we’re estimating V or Q, to decide on an action. At some point, with finite rewards, the discount factor becomes so small that any further estimation won’t change action rankings. This is a natural place to stop. If rewards are not bounded, this no longer works and some other simplification is needed (setting an artificial limit to recursion depth).
  
  
  ---
  
  