<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>

CC BY-SA 4.0
2023-09-26T11:38:54.487Z
It's due to the _Principle of Optimality_ in Dynamic programming
Alberto
CC BY-SA 4.0
2023-09-27T18:07:20.740Z
@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
Neil Slater
CC BY-SA 4.0
2023-09-27T19:30:01.863Z
@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
Alberto
CC BY-SA 4.0
2023-09-27T20:10:04.993Z
@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.
Neil Slater
CC BY-SA 4.0
2023-09-28T20:36:11.813Z
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..
hugh
CC BY-SA 4.0
2023-10-06T08:24:13.270Z
@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
hugh
CC BY-SA 4.0
2023-10-06T09:59:17.837Z
@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.
Neil Slater
<bellman-equations><value-iteration><policy-iteration><dynamic-programming><tree-search>
Why solely a one-step-lookahead in value/policy-iteration?
hugh
# 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**: @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  
> **username_1**: @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  
> **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**: @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  
> **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

