Answers.Body: <p>The first sentence simply asserts the base heuristic accidentally produces an optimal control sequence, otherwise the rollout algo starting from initial state <span class="math-container">$x_0$</span>  would not be strictly inferior to the one produced by the base heuristic starting from the same <span class="math-container">$x_0$</span> as the author stated later.</p>
  <p>This unwanted result of rolling out a strict inferior target policy under this section's deterministic problems assumption is due to violation of the base heuristic's <em>sequential improvement</em> property, which is a weaker property than <em>sequential consistency</em> shared by a deterministic policy, for example. Thus the base heuristic <span class="math-container">$H$</span> here must not be a deterministic policy such as the <a href="https://en.wikipedia.org/wiki/Hill_climbing#Variants" rel="nofollow noreferrer">random-restart hill climbing search</a> algo applied for the traveling salesman problem.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-03-17T13:25:07.390Z
Answers.Text: Your explanation is less clearer than the explanation in the book.
Answers.UserDisplayName: DSPinfinity
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-03-16T23:06:22.483Z
Answers.LastActivityDate: 2023-03-17T01:36:41.287Z
Answers.LastEditDate: 2023-03-17T01:36:41.287Z
Answers.UserDisplayName: cinch
Body: <p>Below is an example (p.89) from &quot;RL and Optimal Control&quot; book by D.Bertsekas on the construction of a a case study where the rollout algorithm is worse than the base heuristic on which the rollout algorithm is constructed.</p>
  <p>It is not clear why sequential improvement is violated. First of all,
  the first sentence is not clear to me: is it the rollout algorithm
  or the base heuristic that accidentally produces an optimal control sequence?</p>
  <p>It is not clear to me why sequential improvement is violated in the provided example. I will be happy for clear explanation.</p>
  <p><a href="https://i.sstatic.net/Di7k4.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Di7k4.png" alt="enter image description here" /></a></p>
  
Tags: <reinforcement-learning>
Title: It is not clear why sequential improvement is violated in the constructed rollout algorithm
UserDisplayName: DSPinfinity
ThreadText: # It is not clear why sequential improvement is violated in the constructed rollout algorithm
  
  (Asked by: username_0 on 2023-03-16)
  
  Below is an example (p.89) from "RL and Optimal Control" book by D.Bertsekas on the construction of a a case study where the rollout algorithm is worse than the base heuristic on which the rollout algorithm is constructed.
  
  It is not clear why sequential improvement is violated. First of all,
  the first sentence is not clear to me: is it the rollout algorithm
  or the base heuristic that accidentally produces an optimal control sequence?
  
  It is not clear to me why sequential improvement is violated in the provided example. I will be happy for clear explanation.
  
  [![enter image description here](https://i.sstatic.net/Di7k4.png)](https://i.sstatic.net/Di7k4.png)
  
  **Tags:** reinforcement-learning
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2023-03-16. Score: 0
  
  The first sentence simply asserts the base heuristic accidentally produces an optimal control sequence, otherwise the rollout algo starting from initial state $x\_0$ would not be strictly inferior to the one produced by the base heuristic starting from the same $x\_0$ as the author stated later.
  
  This unwanted result of rolling out a strict inferior target policy under this section's deterministic problems assumption is due to violation of the base heuristic's *sequential improvement* property, which is a weaker property than *sequential consistency* shared by a deterministic policy, for example. Thus the base heuristic $H$ here must not be a deterministic policy such as the [random-restart hill climbing search](https://en.wikipedia.org/wiki/Hill_climbing#Variants) algo applied for the traveling salesman problem.
  
  > **Comments:**
  > **username_0**: Your explanation is less clearer than the explanation in the book.  
  
  ---
  
  