Body: <p>In value iteration and policy iteration we solely consider a one-step-lookahead where the lookahead is from the previous iteraiton and therefore need to sweep over all states and iterate this procedure.</p>
  <p>Why dont we do one sweep over all states but instead of using a one-step-lookahead we build a complete scenario-tree thus a full-step-lookahead.</p>
  <p><strong>Question</strong> Is it due to efficiency, computational challenges(obviously you cant if the horizon is infinite), it is due to loops?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-09-26T11:38:54.487Z
Comments.Text: It's due to the _Principle of Optimality_ in Dynamic programming
Comments.UserDisplayName: Alberto
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-09-27T18:07:20.740Z
Comments.Text: @alberto the principle shows that a single step look ahead works, not that it is the only or best choice. Also better to write up an answer, rather than a half answer as a comment. If a question seems stuck, and the best possible is to give a pointer, then it's kind of ok, because it might help the OP, which is better than nothing
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-09-27T19:30:01.863Z
Comments.Text: @NeilSlater, no, it shows that if that property holds, that full traversal, or a recursively solution, are equivalent... I cannot find an example where a full traversal per each state is more accurate then a recursive DP solution
Comments.UserDisplayName: Alberto
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-09-27T20:10:04.993Z
Comments.Text: @Alberto - equivalent results, yes. Not necessarily equivalent performance, or equivalent in other ways. In reinforcement learning you also add the policy handling, which is not core to dynamic programming.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-09-28T20:36:11.813Z
Comments.Text: i.e they will reach the same result in all cases...the main question still sticks, any input on it? -> a part of the reasons must be the reasons i mentioned? it strikes me that i cant find any introductory RL-courses talking about this..
Comments.UserDisplayName: hugh
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-10-06T08:24:13.270Z
Comments.Text: @NeilSlater are you aware of any resources i can check at that compares the two approaches, seems so strange that noone really discusses it, i cant see intuitively how it is obvious that a onestep lookahead is better in all cases
Comments.UserDisplayName: hugh
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-10-06T09:59:17.837Z
Comments.Text: @hugh I have not answered, because not 100% certain, I think that the reduced complexity wins most of the time. And if you are looking at the kind of problem that might benefit from deeper traversal, chances are the space is not easy to run full sweeps on. There are approximate versions of DP, and versions that don't run full sweeps, but they are kind of specialist compared to e.g. DQN.
Comments.UserDisplayName: Neil Slater
Tags: <bellman-equations><value-iteration><policy-iteration><dynamic-programming><tree-search>
Title: Why solely a one-step-lookahead in value/policy-iteration?
UserDisplayName: hugh
ThreadText: # Why solely a one-step-lookahead in value/policy-iteration?
  
  (Asked by: username_0 on 2023-09-25)
  
  In value iteration and policy iteration we solely consider a one-step-lookahead where the lookahead is from the previous iteraiton and therefore need to sweep over all states and iterate this procedure.
  
  Why dont we do one sweep over all states but instead of using a one-step-lookahead we build a complete scenario-tree thus a full-step-lookahead.
  
  **Question** Is it due to efficiency, computational challenges(obviously you cant if the horizon is infinite), it is due to loops?
  
  **Tags:** bellman-equations, value-iteration, policy-iteration, dynamic-programming, tree-search
  
  > **Comments:**
  > **username_1**: It's due to the _Principle of Optimality_ in Dynamic programming  
  > **username_2**: @username_1 the principle shows that a single step look ahead works, not that it is the only or best choice. Also better to write up an answer, rather than a half answer as a comment. If a question seems stuck, and the best possible is to give a pointer, then it's kind of ok, because it might help the OP, which is better than nothing  
  > **username_1**: @username_2, no, it shows that if that property holds, that full traversal, or a recursively solution, are equivalent... I cannot find an example where a full traversal per each state is more accurate then a recursive DP solution  
  > **username_2**: @username_1 - equivalent results, yes. Not necessarily equivalent performance, or equivalent in other ways. In reinforcement learning you also add the policy handling, which is not core to dynamic programming.  
  > **username_0**: i.e they will reach the same result in all cases...the main question still sticks, any input on it? -> a part of the reasons must be the reasons i mentioned? it strikes me that i cant find any introductory RL-courses talking about this..  
  > **username_0**: @username_2 are you aware of any resources i can check at that compares the two approaches, seems so strange that noone really discusses it, i cant see intuitively how it is obvious that a onestep lookahead is better in all cases  
  > **username_2**: @username_0 I have not answered, because not 100% certain, I think that the reduced complexity wins most of the time. And if you are looking at the kind of problem that might benefit from deeper traversal, chances are the space is not easy to run full sweeps on. There are approximate versions of DP, and versions that don't run full sweeps, but they are kind of specialist compared to e.g. DQN.  
  
  ---
  
  ## 0 answers
  
  