Answers.Body: <p>Let's first start with the intuitive explanation. If you just use q-learning (or any other temporal difference method like SARSA) you usually just look ahead one step. The other extreme is a monte-carlo method where you don't rely on estimates of the state-value function at all (your policy might depend on an estimate, but your updates don't). Monte-carlo methods can be viewed as an <span class="math-container">$\infty$</span>-lookahead. So <span class="math-container">$l$</span>-step lookaheads are somewhere in between (they take <span class="math-container">$l$</span> rewards in a monte carlo fashion and then only bootstrap from there), so they reduce the dependency on the estimates by quite some margin. Therefore you can have an estimate of the state-value function with higher variance for <span class="math-container">$l$</span>-step lookahead as you could with only <span class="math-container">$1$</span>-step lookaheads.</p>
  <p>Now let's have a look at a more quantitative explanation. You are looking for the <em>error reduction property</em> (<a href="https://ai.stackexchange.com/a/9426/67543">see derivation in Sutton-Barto notation</a>) of <span class="math-container">$l$</span>-step lookaheads, which can generally be given by
  <span class="math-container">\begin{equation}
  \min\limits_x \Bigl\lvert \mathbb{E}_{\pi}[T^{l-1}\tilde{J}_{t}| X_{t}=x] - J_{\pi}\Bigr\rvert \le \gamma^{l} \min\limits_s \Bigl\lvert \tilde{J}_{t} - J_{\pi}\Bigr\rvert
  \end{equation}</span></p>
  <p>This shows that the <span class="math-container">$l$</span>-step lookahead will always have lower errors than a simple <span class="math-container">$1$</span> step solution. Hence one can have worse estimations to achieve the same quality of results with multi-step learning.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-02T20:43:02.167Z
Answers.LastActivityDate: 2023-02-02T20:43:02.167Z
Answers.UserDisplayName: pythonic833
Body: <p>The following is from the book &quot;Reinforcement learning and optimal control&quot;, by D. P. Bertsekas.</p>
  <p>Chapter 2, page 52:</p>
  <p>&quot;The motivation for <span class="math-container">$l$</span>-step lookahead is that for increasing values of <span class="math-container">$l$</span>,
  one may require a less accurate approximation <span class="math-container">$\tilde{J}_{k+l}$</span> to obtain good
  performance. Otherwise expressed, for the same quality of cost function approximation,
  better performance maybe obtained as <span class="math-container">$l$</span> becomes larger. This makes intuitive sense,
  since in this case, the cost of more stages is treated exactly with optimization.&quot;</p>
  <p>My question:</p>
  <p>Why is it that for increasing values of <span class="math-container">$l$</span>,
  one may require a less accurate approximation <span class="math-container">$\tilde{J}_{k+l}$</span> to obtain good
  performance?</p>
  
Tags: <reinforcement-learning>
Title: Why is $l$-step lookahead better in RL?
UserDisplayName: DSPinfinity
ThreadText: # Why is $l$-step lookahead better in RL?
  
  (Asked by: username_0 on 2023-01-27)
  
  The following is from the book "Reinforcement learning and optimal control", by D. P. Bertsekas.
  
  Chapter 2, page 52:
  
  "The motivation for $l$-step lookahead is that for increasing values of $l$,
  one may require a less accurate approximation $\tilde{J}\_{k+l}$ to obtain good
  performance. Otherwise expressed, for the same quality of cost function approximation,
  better performance maybe obtained as $l$ becomes larger. This makes intuitive sense,
  since in this case, the cost of more stages is treated exactly with optimization."
  
  My question:
  
  Why is it that for increasing values of $l$,
  one may require a less accurate approximation $\tilde{J}\_{k+l}$ to obtain good
  performance?
  
  **Tags:** reinforcement-learning
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2023-02-02. Score: 1
  
  Let's first start with the intuitive explanation. If you just use q-learning (or any other temporal difference method like SARSA) you usually just look ahead one step. The other extreme is a monte-carlo method where you don't rely on estimates of the state-value function at all (your policy might depend on an estimate, but your updates don't). Monte-carlo methods can be viewed as an $\infty$-lookahead. So $l$-step lookaheads are somewhere in between (they take $l$ rewards in a monte carlo fashion and then only bootstrap from there), so they reduce the dependency on the estimates by quite some margin. Therefore you can have an estimate of the state-value function with higher variance for $l$-step lookahead as you could with only $1$-step lookaheads.
  
  Now let's have a look at a more quantitative explanation. You are looking for the *error reduction property* ([see derivation in Sutton-Barto notation](https://ai.stackexchange.com/a/9426/67543)) of $l$-step lookaheads, which can generally be given by
  \begin{equation}
  \min\limits\_x \Bigl\lvert \mathbb{E}\_{\pi}[T^{l-1}\tilde{J}\_{t}| X\_{t}=x] - J\_{\pi}\Bigr\rvert \le \gamma^{l} \min\limits\_s \Bigl\lvert \tilde{J}\_{t} - J\_{\pi}\Bigr\rvert
  \end{equation}
  
  This shows that the $l$-step lookahead will always have lower errors than a simple $1$ step solution. Hence one can have worse estimations to achieve the same quality of results with multi-step learning.
  
  
  ---
  
  