Answers.Body: <p>I think that this is an intentional subtle detail of the algorithm that ensures the convergence property.  The claim in the book is that for any <span class="math-container">$b$</span> that provides us with <em>&quot;an infinite number of returns for each pair of state and action&quot;</em> the target policy <span class="math-container">$\pi$</span> will converge to optimal.</p>
  <p>Imagine now that we have such a bad policy <span class="math-container">$b$</span> that it never aligns with the target policy action at the last step <span class="math-container">$t=T-1$</span> of each generated episode: <span class="math-container">$A_{T-1} = \pi(S_{T-1})$</span>. In that case the weight value will stay <span class="math-container">$W=1$</span> and the the algorithm will be reduced to (ignoring <span class="math-container">$t$</span> indices for the last <span class="math-container">$S,A,R$</span> triplet):
  <span class="math-container">$$\begin{array}{l} C(S,A) \leftarrow C(S,A) + 1 \\ 
  Q(S,A) \leftarrow Q(S,A) + \frac{1}{C(S,A)}\left[R - Q(S,A)\right]
  \end{array}$$</span><br />
  Which is just the tabular incremental averaging for the Q values (see for example eq. (2.3)).</p>
  <p>If we bail from the for loop before these updates, then no updates would happen at all. And authors won't be able to claim convergence to optimal policy for all those &quot;good&quot; sampling policies <span class="math-container">$b$</span>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-15T23:47:04.873Z
Answers.Text: Thank you. I wish they at least had a brief comment stating this. To leave this completely without comment seems strange (it was driving me crazy). Thank you again. Regarding, "we have such a bad policy  that it never aligns with the target policy action at the last step =−1 of each generated episode". I suppose that is not possible given coverage, right? It might be super slow but has to align from time to time.
Answers.UserDisplayName: Curious2learn
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-15T23:54:27.690Z
Answers.Text: @Curious2learn I agree that this point should've been stressed, as far as I understand the algorithm is not too practical and authors wanted to move on to the next chapters that discuss all the (authors' original) improvements to this approach.
Answers.UserDisplayName: Kostya
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-15T23:57:06.690Z
Answers.Text: @Curious2learn As for the possibility of such a "bad" $b$. I guess that depends on concrete MDP - there are definitely MDPs where it is inconsistent with coverage, but I think one can come up with an MDP where it is possible.
Answers.UserDisplayName: Kostya
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-16T00:59:50.950Z
Answers.Text: Thank you. Another reason why such an update might make sense is the following. Say the initial target policy specifies an action $a$ in state $s$ in $T-1$. Suppose the updated value of $Q(s, a) $ is greater than 0, and all other initial $Q(s, a') <= 0$. Then if $Q(s, a2) > Q(s, a)$, and even if the behavior policy takes actions a2 from time to time, any experience from that would never be used to improve the target policy. But updating even when the sample action is inconsistent with the target policy can help improve the action under the target policy.
Answers.UserDisplayName: Curious2learn
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-15T20:54:44.403Z
Answers.LastActivityDate: 2021-05-16T11:12:26.467Z
Answers.LastEditDate: 2021-05-16T11:12:26.467Z
Answers.UserDisplayName: Kostya
Answers.Body: <blockquote>
  <p>The algorithm as stated seems problematic to me. For example, if say the target policy  is deterministic and behavior policy  is stochastic. If in period −1 the behavior policy takes an action that is not consistent with  then the importance sampling ratio −1:−1=0. However, the algorithm as shown would update (−1,−1) since the checks I referred to above don't occur until the end of the inner loop. What am I missing here?</p>
  </blockquote>
  <p>Why is this problematic? You are trying to estimate Q(s, a), which is the expected reward <em>given that a has been played in state s</em>, assuming to behave according to the target policy <em>in the future</em>.</p>
  <p>If you were learning it on-policy, you would sample future states and actions based on the target policy. Here, you sample according to the behaviour policy and then correct with the ratio of probabilities of future states and actions under the two policies.</p>
  <p>But <em>you are conditioning everything on having played action a in state s</em> in the first place, so the probability of that happening does not enter the computation.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-07-21T17:09:31.897Z
Answers.LastActivityDate: 2024-07-21T17:11:14.933Z
Answers.LastEditDate: 2024-07-21T17:11:14.933Z
Answers.UserDisplayName: Mattia Scardecchia
Body: <p>I have a question about the <span class="math-container">$W$</span> term in the off-policy MC control algorithm on <a href="http://incompleteideas.net/book/RLbook2020.pdf#page=133" rel="nofollow noreferrer">Page 111 of Sutton &amp; Barto</a>. I have also included it in the figure below.</p>
  <p><a href="https://i.sstatic.net/rqfCt.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/rqfCt.png" alt="Algorithm from Sutton Barto" /></a></p>
  <p>My question: shouldn't the check <span class="math-container">$A_{t} = \pi(S_{t})$</span> be made before updating <span class="math-container">$C(S_{t}, A_{t})$</span> and <span class="math-container">$Q(S_{t}, A_{t})$</span>? And, at this point if <span class="math-container">$A_{t} \neq \pi(S_{t}) $</span> then the inner loop should exit before updating <span class="math-container">$Q(\cdot)$</span>. If <span class="math-container">$A_{t} = \pi(S_{t})$</span> then shouldn't <span class="math-container">$W$</span> be updated to
  <span class="math-container">$W = W \frac{1}{b(A_{t}|S_{t})} $</span> before updating the <span class="math-container">$Q(s, a)$</span> and $C(s, a) functions?</p>
  <p>The algorithm as stated seems problematic to me. For example, if say the target policy <span class="math-container">$\pi$</span> is deterministic and behavior policy <span class="math-container">$b$</span> is stochastic. If in period <span class="math-container">$T-1$</span> the behavior policy takes an action that is not consistent with <span class="math-container">$\pi$</span> then the importance sampling ratio <span class="math-container">$\rho_{T-1:T-1} = 0$</span>. However, the algorithm as shown would update <span class="math-container">$Q(S_{T-1}, A_{T-1})$</span> since the checks I referred to above don't occur until the end of the inner loop. What am I missing here?</p>
  
Tags: <reinforcement-learning><monte-carlo-methods><off-policy-methods><sutton-barto>
Title: In off-policy MC control algorithm by Sutton & Barto, why do we perform a last update when sample action is inconsistent with target policy?
UserDisplayName: Curious2learn
ThreadText: # In off-policy MC control algorithm by Sutton & Barto, why do we perform a last update when sample action is inconsistent with target policy?
  
  (Asked by: username_0 on 2021-05-15)
  
  I have a question about the $W$ term in the off-policy MC control algorithm on [Page 111 of Sutton & Barto](http://incompleteideas.net/book/RLbook2020.pdf#page=133). I have also included it in the figure below.
  
  [![Algorithm from Sutton Barto](https://i.sstatic.net/rqfCt.png)](https://i.sstatic.net/rqfCt.png)
  
  My question: shouldn't the check $A\_{t} = \pi(S\_{t})$ be made before updating $C(S\_{t}, A\_{t})$ and $Q(S\_{t}, A\_{t})$? And, at this point if $A\_{t} \neq \pi(S\_{t}) $ then the inner loop should exit before updating $Q(\cdot)$. If $A\_{t} = \pi(S\_{t})$ then shouldn't $W$ be updated to
  $W = W \frac{1}{b(A\_{t}|S\_{t})} $ before updating the $Q(s, a)$ and $C(s, a) functions?
  
  The algorithm as stated seems problematic to me. For example, if say the target policy $\pi$ is deterministic and behavior policy $b$ is stochastic. If in period $T-1$ the behavior policy takes an action that is not consistent with $\pi$ then the importance sampling ratio $\rho\_{T-1:T-1} = 0$. However, the algorithm as shown would update $Q(S\_{T-1}, A\_{T-1})$ since the checks I referred to above don't occur until the end of the inner loop. What am I missing here?
  
  **Tags:** reinforcement-learning, monte-carlo-methods, off-policy-methods, sutton-barto
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2021-05-15. Score: 1 | Accepted answer
  
  I think that this is an intentional subtle detail of the algorithm that ensures the convergence property. The claim in the book is that for any $b$ that provides us with *"an infinite number of returns for each pair of state and action"* the target policy $\pi$ will converge to optimal.
  
  Imagine now that we have such a bad policy $b$ that it never aligns with the target policy action at the last step $t=T-1$ of each generated episode: $A\_{T-1} = \pi(S\_{T-1})$. In that case the weight value will stay $W=1$ and the the algorithm will be reduced to (ignoring $t$ indices for the last $S,A,R$ triplet):
  $$\begin{array}{l} C(S,A) \leftarrow C(S,A) + 1 \\
  Q(S,A) \leftarrow Q(S,A) + \frac{1}{C(S,A)}\left[R - Q(S,A)\right]
  \end{array}$$  
  Which is just the tabular incremental averaging for the Q values (see for example eq. (2.3)).
  
  If we bail from the for loop before these updates, then no updates would happen at all. And authors won't be able to claim convergence to optimal policy for all those "good" sampling policies $b$.
  
  > **Comments:**
  > **username_0**: Thank you. I wish they at least had a brief comment stating this. To leave this completely without comment seems strange (it was driving me crazy). Thank you again. Regarding, "we have such a bad policy  that it never aligns with the target policy action at the last step =−1 of each generated episode". I suppose that is not possible given coverage, right? It might be super slow but has to align from time to time.  
  > **username_1**: @username_0 I agree that this point should've been stressed, as far as I understand the algorithm is not too practical and authors wanted to move on to the next chapters that discuss all the (authors' original) improvements to this approach.  
  > **username_1**: @username_0 As for the possibility of such a "bad" $b$. I guess that depends on concrete MDP - there are definitely MDPs where it is inconsistent with coverage, but I think one can come up with an MDP where it is possible.  
  > **username_0**: Thank you. Another reason why such an update might make sense is the following. Say the initial target policy specifies an action $a$ in state $s$ in $T-1$. Suppose the updated value of $Q(s, a) $ is greater than 0, and all other initial $Q(s, a') <= 0$. Then if $Q(s, a2) > Q(s, a)$, and even if the behavior policy takes actions a2 from time to time, any experience from that would never be used to improve the target policy. But updating even when the sample action is inconsistent with the target policy can help improve the action under the target policy.  
  
  ---
  
  ### Answer by username_2 on 2024-07-21. Score: 0
  
  > The algorithm as stated seems problematic to me. For example, if say the target policy is deterministic and behavior policy is stochastic. If in period −1 the behavior policy takes an action that is not consistent with then the importance sampling ratio −1:−1=0. However, the algorithm as shown would update (−1,−1) since the checks I referred to above don't occur until the end of the inner loop. What am I missing here?
  
  Why is this problematic? You are trying to estimate Q(s, a), which is the expected reward *given that a has been played in state s*, assuming to behave according to the target policy *in the future*.
  
  If you were learning it on-policy, you would sample future states and actions based on the target policy. Here, you sample according to the behaviour policy and then correct with the ratio of probabilities of future states and actions under the two policies.
  
  But *you are conditioning everything on having played action a in state s* in the first place, so the probability of that happening does not enter the computation.
  
  
  ---
  
  