Answers.Body: <p>Exhaustive search is just trial and error for the specified problem which has a fixed start node X and a fixed end node Y, thus every possible travel route from X to Y has to be evaluated <em>independently</em> which requires 14 segment evaluations of their respective reward (i.e., the negative of cost-to-go length for shortest path problem) if you count the total 5 possible ways from X to Y in your directed graph.</p>
  <p>On the other hand, if you use model-based RL there're only 7 states as nodes and obviously its MDP's state and reward transitions are all deterministic with at most 3 actions at each state and only one action at some of the states. So by using backward dynamic programing's (DP) simplest one-sweep value iteration for this shortest path problem starting from the terminal node, the problem is decomposed into smaller subproblems represented by individual states. In many cases such as shortest path here, states closer to the terminal state have fewer successor states to consider, reducing the computational complexity and iterations to be able to directly compute optimal values within <em>one</em> iteration here instead of the generic algo's intermediate  <em>estimates</em> with many iterations as mentioned by my answer to your recent <a href="https://ai.stackexchange.com/questions/45092/how-to-derive-value-iteration-from-policy-iteration">post</a>.</p>
  <p>And since you've already known the one-line max operator algo for value iteration derived from Bellman <em>optimality</em> equation (not Bellman equation) in your recent post, it's easy to check for yourself here the optimal values for the 3 states closest to terminal state Y are <span class="math-container">$v_*(B)=-2, v_*(E)=-2, v_*(C)=-1$</span> assuming the terminal optimal value <span class="math-container">$v_*(Y)=0$</span>, and you only need 5 segment evaluations to arrive at these 3 optimal values (note to calculate state C's optimal value we can reuse optimal values of B &amp; E reducing the segment evaluation count essentially). Then similarly you just need another 5 segment evaluations to get the remaining 3 states' optimal values. Then you can extract shortest path from start state X by following the action with optimal value stored already in the above described step-by-step backward DP.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-03-15T05:05:52.777Z
Answers.LastActivityDate: 2024-03-15T05:20:45.970Z
Answers.LastEditDate: 2024-03-15T05:20:45.970Z
Answers.UserDisplayName: cinch
Answers.Body: <p>Like it's explained in the image's caption, DP techniques are based on the idea that you can reuse the solution to subproblems, so it assumes that you can break down the original problem into subproblems and that some subproblems overlap.</p>
  <p>So, in your example, you can get to <span class="math-container">$B$</span> from <span class="math-container">$C$</span> and <span class="math-container">$A$</span>. Similarly, you can get to <span class="math-container">$E$</span> from <span class="math-container">$C$</span> and <span class="math-container">$D$</span>. Once you know the shortest path from <span class="math-container">$B$</span> to <span class="math-container">$Y$</span>, you don't have to recalculate it. The same applies for <span class="math-container">$E$</span>. So, to be clearer, the shortest path to <span class="math-container">$C$</span> and <span class="math-container">$A$</span> share a common subproblem because they are both connected to <span class="math-container">$B$</span>. The same applies to the other example.</p>
  <p>Now, if you look at your example, there are 10 segments, so you don't go through a segment more than once. If you start from <span class="math-container">$Y$</span>, you can compute the solution in a bottom-up approach (see also the top-down approach in DP), and cache the results to any subproblem, so you don't have to re-evaluate anything.</p>
  <p>In the case of exhaustive search, you basically try every possible combination and you don't cache anything, so you may revisit a segment more than once. For example, you will visit the segment from <span class="math-container">$B$</span> to <span class="math-container">$Y$</span> twice because there are 2 paths that have that segment, i.e. <span class="math-container">$X \rightarrow A \rightarrow B \rightarrow Y$</span> and <span class="math-container">$X \rightarrow C \rightarrow B \rightarrow Y$</span>. You also visit the segment <span class="math-container">$X \rightarrow C$</span> several times because several paths have it. Try to enumerate all possible paths and then count all segments (even if repeated) - they should be 14 (I've just counted them, but you can count them yourself too)</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-03-15T14:59:21.323Z
Answers.LastActivityDate: 2024-03-15T15:10:13.963Z
Answers.LastEditDate: 2024-03-15T15:10:13.963Z
Answers.UserDisplayName: nbro
Body: <p>Why do exhaustive search require 14 travel segment evaluations but dynamic programming require 10 for this shortest path problem? I need a clear explanation.</p>
  <p><a href="https://i.sstatic.net/nJxqb.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/nJxqb.png" alt="enter image description here" /></a></p>
  <p><a href="https://i.sstatic.net/Afwq3.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Afwq3.png" alt="enter image description here" /></a></p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-03-15T14:43:51.073Z
Comments.Text: Can you please tell us where you took this image from?
Comments.UserDisplayName: nbro
Tags: <reinforcement-learning><markov-decision-process><dynamic-programming><shortest-path-problem>
Title: Why do exhaustive search require 14 travel segment evaluations but dynamic programming require 10 for this shortest path problem?
UserDisplayName: DSPinfinity
ThreadText: # Why do exhaustive search require 14 travel segment evaluations but dynamic programming require 10 for this shortest path problem?
  
  (Asked by: username_0 on 2024-03-15)
  
  Why do exhaustive search require 14 travel segment evaluations but dynamic programming require 10 for this shortest path problem? I need a clear explanation.
  
  [![enter image description here](https://i.sstatic.net/nJxqb.png)](https://i.sstatic.net/nJxqb.png)
  
  [![enter image description here](https://i.sstatic.net/Afwq3.png)](https://i.sstatic.net/Afwq3.png)
  
  **Tags:** reinforcement-learning, markov-decision-process, dynamic-programming, shortest-path-problem
  > **Comments:**
  > **username_1**: Can you please tell us where you took this image from?  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2024-03-15. Score: 2 | Accepted answer
  
  Like it's explained in the image's caption, DP techniques are based on the idea that you can reuse the solution to subproblems, so it assumes that you can break down the original problem into subproblems and that some subproblems overlap.
  
  So, in your example, you can get to $B$ from $C$ and $A$. Similarly, you can get to $E$ from $C$ and $D$. Once you know the shortest path from $B$ to $Y$, you don't have to recalculate it. The same applies for $E$. So, to be clearer, the shortest path to $C$ and $A$ share a common subproblem because they are both connected to $B$. The same applies to the other example.
  
  Now, if you look at your example, there are 10 segments, so you don't go through a segment more than once. If you start from $Y$, you can compute the solution in a bottom-up approach (see also the top-down approach in DP), and cache the results to any subproblem, so you don't have to re-evaluate anything.
  
  In the case of exhaustive search, you basically try every possible combination and you don't cache anything, so you may revisit a segment more than once. For example, you will visit the segment from $B$ to $Y$ twice because there are 2 paths that have that segment, i.e. $X \rightarrow A \rightarrow B \rightarrow Y$ and $X \rightarrow C \rightarrow B \rightarrow Y$. You also visit the segment $X \rightarrow C$ several times because several paths have it. Try to enumerate all possible paths and then count all segments (even if repeated) - they should be 14 (I've just counted them, but you can count them yourself too)
  
  
  ---
  
  ### Answer by username_2 on 2024-03-15. Score: 2
  
  Exhaustive search is just trial and error for the specified problem which has a fixed start node X and a fixed end node Y, thus every possible travel route from X to Y has to be evaluated *independently* which requires 14 segment evaluations of their respective reward (i.e., the negative of cost-to-go length for shortest path problem) if you count the total 5 possible ways from X to Y in your directed graph.
  
  On the other hand, if you use model-based RL there're only 7 states as nodes and obviously its MDP's state and reward transitions are all deterministic with at most 3 actions at each state and only one action at some of the states. So by using backward dynamic programing's (DP) simplest one-sweep value iteration for this shortest path problem starting from the terminal node, the problem is decomposed into smaller subproblems represented by individual states. In many cases such as shortest path here, states closer to the terminal state have fewer successor states to consider, reducing the computational complexity and iterations to be able to directly compute optimal values within *one* iteration here instead of the generic algo's intermediate *estimates* with many iterations as mentioned by my answer to your recent [post](https://ai.stackexchange.com/questions/45092/how-to-derive-value-iteration-from-policy-iteration).
  
  And since you've already known the one-line max operator algo for value iteration derived from Bellman *optimality* equation (not Bellman equation) in your recent post, it's easy to check for yourself here the optimal values for the 3 states closest to terminal state Y are $v\_\*(B)=-2, v\_\*(E)=-2, v\_\*(C)=-1$ assuming the terminal optimal value $v\_\*(Y)=0$, and you only need 5 segment evaluations to arrive at these 3 optimal values (note to calculate state C's optimal value we can reuse optimal values of B & E reducing the segment evaluation count essentially). Then similarly you just need another 5 segment evaluations to get the remaining 3 states' optimal values. Then you can extract shortest path from start state X by following the action with optimal value stored already in the above described step-by-step backward DP.
  
  
  ---
  
  