Answers.Body: <p>The action-value function DOES take into account the policy being followed - that's precisely what the notation <span class="math-container">$\mathbb{E}_\pi$</span> is for. Specifically, <span class="math-container">$\mathbb{E}_\pi$</span> is a shorthand for
  <span class="math-container">\begin{align*} 
  \mathbb{E}_{a_i \sim~ \pi(a_i \,|\, s_i), \, (r_{i+1}, s_{i+1}) \sim p(r_{i+1}, s_{i+1} \, |\, s_{i}, \, a_{i}), \, \forall i}
  \end{align*}</span>
  where <span class="math-container">$p$</span> represents the environment's joint distribution of reward/transitions. This means that the expectation is with respect to the actions, states, and rewards you see under the policy <span class="math-container">$\pi$</span>. If you want to make this more concrete, we can write out the expectation like this
  <span class="math-container">\begin{align*} 
  &amp; \mathbb{E}_\pi\left[\sum_{k=0}^{\infty}\gamma^k r_{k+t+1} | s_t, a_t \right] \\
  :=&amp; \int_{(r_{t+1}, s_{t+1})}p(r_{t+1}, s_{t+1})\bigg[r_{t+1} + \int_{a_{t+1}}\pi(a_{t+1})\int_{(r_{t+2}, s_{t+2})}p(r_{t+2}, s_{t+2})\bigg[r_{t+2} + \ldots
  \end{align*}</span>
  (Really, you should be integrating over dummy variables, and I've omitted the conditional expectations, e.g. <span class="math-container">$p(r_{t+1}, s_{t+1})$</span> should be <span class="math-container">$p(r_{t+1}, s_{t+1} | s_t, a_t)$</span>). Of course you can just replace the integrals with sums if you want discrete actions and/or states. So you can see just writing <span class="math-container">$\mathbb{E}_\pi$</span> sweeps a lot of the notation and true meaning under the rug, and I assume that is the source of the confusion.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-06-04T16:50:11.443Z
Answers.Text: The question was about Q-learning (not about the definition of the value function), which the OP assumed that it does not take into account the policy being followed.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-06-04T17:07:20.237Z
Answers.Text: My interpretation of the question is that OP thought that Eq. (3.13) indicates that the action-value depends only on the state, action $(s, a)$. My answer is that there is dependence on all the future states/actions which is meant by the $\mathbb{E}_\pi$ notation. It's possible the OP meant something different, but I'm not sure the OP's question is as deep as some of the other comments are implying.
Answers.UserDisplayName: Taw
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-06-04T17:18:01.380Z
Answers.Text: By the way, OP is referring to me?
Answers.UserDisplayName: Hermes Morales
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-06-04T18:12:55.817Z
Answers.Text: @HermesMorales Yes - it stands for Original Poster (I think). If you'd like to clarify what you are asking about, or discuss what people are asssuming you are asking, please post a comment/reply
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-06-04T16:43:06.003Z
Answers.LastActivityDate: 2021-06-04T16:43:06.003Z
Answers.UserDisplayName: Taw
Answers.Body: <p>Q-learning can learn about the greedy policy (the policy that we define as <span class="math-container">$\pi(s) = \arg\max_a Q(s, a)$</span>) whilst following some arbitrary exploratory policy because Q-learning is an <em>off-policy</em> algorithm.</p>
  <p>In Q-learning, we are updating our values of <span class="math-container">$Q(s, a)$</span> using a bootstrapped value from one time step in the future. This means that we don't need to worry about any importance sampling type re-weighting of the action chosen by the exploratory policy that we use for action selection because of how <span class="math-container">$Q(\cdot, \cdot)$</span> is defined:
  <span class="math-container">$$Q(s, a) = \mathbb{E}_\pi \left[ G_t | S_t = s, A_t = a \right] \; ;$$</span>
  where <span class="math-container">$G_t$</span> is the (discounted) future returns defined in Sutton and Barto. Now, because we have defined <span class="math-container">$Q(\cdot, \cdot)$</span> such that we condition on <em>knowing</em> action <span class="math-container">$A_t$</span>, it really doesn't matter which distribution this action came from, because as mentioned we have conditioned on knowing it. This allows us to make updates in Q-learning for any state-action pair using the target from the optimal policy despite us not using this for action selection in the environment.</p>
  <p>If we were to do some kind of <span class="math-container">$n$</span>-step Q-learning with an update target looking something like
  <span class="math-container">$$R(s_t, a_t) + R(s_{t+1}, a_{t+1}) + ... + R(s_{t+n}, a_{t+n}) + \max_{a'} Q(s_{t+n+1}, a')$$</span>
  then we would need to use importance sample to re-weight the trajectory to account for the actions <span class="math-container">$a_{t+i}$</span> for <span class="math-container">$i \geq 1$</span> as these are actions that the optimal policy may not have taken, as they were taken from the exploratory policy and the Q-function assumed that the trajectory (i.e. future actions) is generated under the policy associated with the Q-function.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-06-04T14:45:47.830Z
Answers.Text: I think OP was not quite asking about off-policy, although related. I think they are aiming to ask about the non-stationary nature of value functions in generalised policy iteration. Also, "This allows us to make updates in Q-learning for any state-action pair using the target from the **optimal policy**" is not quite correct. Q learning does not directly target the _optimal_ policy action values, but the current _greedy_ policy action values. The difference is minor but may be an important detail for questions like this one where OP is trying to reconcile prediction vs control issues.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-06-04T15:12:11.607Z
Answers.Text: I think the importance sampling part may not be necessary, if the user is not familiar with it. I think this answer does not emphasize certain aspects that should be emphasized, IMHO, but I think the off-policy part is relevant. In the definition given by Sutton & Barto, they define the $q$ function given a specific policy $\pi$. What is this policy in the context of Q-learning? I think that the direct answer to the OP's question is that Q-learning actually takes into account the policy that we assume to follow from the next state, i.e. the greedy policy (wrt the current value estimate).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-06-04T15:12:13.017Z
Answers.Text: Then we should probably explain how this relates to the off-policy nature of Q-learning. It's also important to emphasize the difference between a definition of a function (defined as an expectation) and an algorithm that _attempts_ to estimate this function. As Neil pointed out, probably, the [generalised policy iteration](http://incompleteideas.net/book/first/ebook/node46.html) thing could also be useful for the explanation.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-06-04T15:46:11.990Z
Answers.Text: @NeilSlater agreed RE the terminology used surrounding the optimal policy.. we use a greedy target which will converge to optimal (in tabular setting) -- I'll edit this. I'm not really sure what to do about the rest. If OP isn't asking the question I've answered, then I'm not really sure what he is asking and he'd need to make the question clearer before I know if I can answer it, I will wait to see what OP says.
Answers.UserDisplayName: David
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-06-04T21:19:59.963Z
Answers.Text: @DavidIreland You saw my point. I must take into account that the actions used for defining the optima state-action-value by Q-learning are known. As I now understand Q-learning assumes a greedy policy as stated also by nbro. Another important point seems to be that Q-learning directly approximate the optimal q_value. My confussion really is " aiming to ask about the non-stationary nature of value functions in generalised policy iteration." as asked by NeilSlater. Your answers and discussion helped me, even if I must continue to explore the point
Answers.UserDisplayName: Hermes Morales
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-06-04T13:53:41.803Z
Answers.LastActivityDate: 2021-06-04T15:46:45.467Z
Answers.LastEditDate: 2021-06-04T15:46:45.467Z
Answers.UserDisplayName: David
Body: <p>From my readings, I have been taught that the state-action value depends on the policy being followed. That seems logical because the expected return from actual actions will be different depending on which actions follow it.</p>
  <p>On page 58 of Sutton &amp; Barto's book, we have</p>
  <p><a href="https://i.sstatic.net/XwRba.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/XwRba.png" alt="State action value definition" /></a></p>
  <p>So, how is it possible that Q-learning can learn a state-action value without taking into account the policy followed thereafter (i.e. the policy followed after having taken action <span class="math-container">$a$</span> in the state <span class="math-container">$s$</span>)?</p>
  
Tags: <reinforcement-learning><q-learning>
Title: How is it possible that Q-learning can learn a state-action value without taking into account the policy followed thereafter?
UserDisplayName: Hermes Morales
ThreadText: # How is it possible that Q-learning can learn a state-action value without taking into account the policy followed thereafter?
  
  (Asked by: username_0 on 2021-06-04)
  
  From my readings, I have been taught that the state-action value depends on the policy being followed. That seems logical because the expected return from actual actions will be different depending on which actions follow it.
  
  On page 58 of Sutton & Barto's book, we have
  
  [![State action value definition](https://i.sstatic.net/XwRba.png)](https://i.sstatic.net/XwRba.png)
  
  So, how is it possible that Q-learning can learn a state-action value without taking into account the policy followed thereafter (i.e. the policy followed after having taken action $a$ in the state $s$)?
  
  **Tags:** reinforcement-learning, q-learning
  
  ---
  
  ## 2 answers
  
  ### Answer by username_4 on 2021-06-04. Score: 2 | Accepted answer
  
  Q-learning can learn about the greedy policy (the policy that we define as $\pi(s) = \arg\max\_a Q(s, a)$) whilst following some arbitrary exploratory policy because Q-learning is an *off-policy* algorithm.
  
  In Q-learning, we are updating our values of $Q(s, a)$ using a bootstrapped value from one time step in the future. This means that we don't need to worry about any importance sampling type re-weighting of the action chosen by the exploratory policy that we use for action selection because of how $Q(\cdot, \cdot)$ is defined:
  $$Q(s, a) = \mathbb{E}\_\pi \left[ G\_t | S\_t = s, A\_t = a \right] \; ;$$
  where $G\_t$ is the (discounted) future returns defined in Sutton and Barto. Now, because we have defined $Q(\cdot, \cdot)$ such that we condition on *knowing* action $A\_t$, it really doesn't matter which distribution this action came from, because as mentioned we have conditioned on knowing it. This allows us to make updates in Q-learning for any state-action pair using the target from the optimal policy despite us not using this for action selection in the environment.
  
  If we were to do some kind of $n$-step Q-learning with an update target looking something like
  $$R(s\_t, a\_t) + R(s\_{t+1}, a\_{t+1}) + ... + R(s\_{t+n}, a\_{t+n}) + \max\_{a'} Q(s\_{t+n+1}, a')$$
  then we would need to use importance sample to re-weight the trajectory to account for the actions $a\_{t+i}$ for $i \geq 1$ as these are actions that the optimal policy may not have taken, as they were taken from the exploratory policy and the Q-function assumed that the trajectory (i.e. future actions) is generated under the policy associated with the Q-function.
  
  > **Comments:**
  > **username_3**: I think OP was not quite asking about off-policy, although related. I think they are aiming to ask about the non-stationary nature of value functions in generalised policy iteration. Also, "This allows us to make updates in Q-learning for any state-action pair using the target from the **optimal policy**" is not quite correct. Q learning does not directly target the _optimal_ policy action values, but the current _greedy_ policy action values. The difference is minor but may be an important detail for questions like this one where OP is trying to reconcile prediction vs control issues.  
  > **username_2**: I think the importance sampling part may not be necessary, if the user is not familiar with it. I think this answer does not emphasize certain aspects that should be emphasized, IMHO, but I think the off-policy part is relevant. In the definition given by Sutton & Barto, they define the $q$ function given a specific policy $\pi$. What is this policy in the context of Q-learning? I think that the direct answer to the OP's question is that Q-learning actually takes into account the policy that we assume to follow from the next state, i.e. the greedy policy (wrt the current value estimate).  
  > **username_2**: Then we should probably explain how this relates to the off-policy nature of Q-learning. It's also important to emphasize the difference between a definition of a function (defined as an expectation) and an algorithm that _attempts_ to estimate this function. As Neil pointed out, probably, the [generalised policy iteration](http://incompleteideas.net/book/first/ebook/node46.html) thing could also be useful for the explanation.  
  > **username_4**: @NeilSlater agreed RE the terminology used surrounding the optimal policy.. we use a greedy target which will converge to optimal (in tabular setting) -- I'll edit this. I'm not really sure what to do about the rest. If OP isn't asking the question I've answered, then I'm not really sure what he is asking and he'd need to make the question clearer before I know if I can answer it, I will wait to see what OP says.  
  > **username_0**: @DavidIreland You saw my point. I must take into account that the actions used for defining the optima state-action-value by Q-learning are known. As I now understand Q-learning assumes a greedy policy as stated also by nbro. Another important point seems to be that Q-learning directly approximate the optimal q_value. My confussion really is " aiming to ask about the non-stationary nature of value functions in generalised policy iteration." as asked by NeilSlater. Your answers and discussion helped me, even if I must continue to explore the point  
  
  ---
  
  ### Answer by username_1 on 2021-06-04. Score: 0
  
  The action-value function DOES take into account the policy being followed - that's precisely what the notation $\mathbb{E}\_\pi$ is for. Specifically, $\mathbb{E}\_\pi$ is a shorthand for
  \begin{align\*}
  \mathbb{E}\_{a\_i \sim~ \pi(a\_i \,|\, s\_i), \, (r\_{i+1}, s\_{i+1}) \sim p(r\_{i+1}, s\_{i+1} \, |\, s\_{i}, \, a\_{i}), \, \forall i}
  \end{align\*}
  where $p$ represents the environment's joint distribution of reward/transitions. This means that the expectation is with respect to the actions, states, and rewards you see under the policy $\pi$. If you want to make this more concrete, we can write out the expectation like this
  \begin{align\*}
  & \mathbb{E}\_\pi\left[\sum\_{k=0}^{\infty}\gamma^k r\_{k+t+1} | s\_t, a\_t \right] \\
  :=& \int\_{(r\_{t+1}, s\_{t+1})}p(r\_{t+1}, s\_{t+1})\bigg[r\_{t+1} + \int\_{a\_{t+1}}\pi(a\_{t+1})\int\_{(r\_{t+2}, s\_{t+2})}p(r\_{t+2}, s\_{t+2})\bigg[r\_{t+2} + \ldots
  \end{align\*}
  (Really, you should be integrating over dummy variables, and I've omitted the conditional expectations, e.g. $p(r\_{t+1}, s\_{t+1})$ should be $p(r\_{t+1}, s\_{t+1} | s\_t, a\_t)$). Of course you can just replace the integrals with sums if you want discrete actions and/or states. So you can see just writing $\mathbb{E}\_\pi$ sweeps a lot of the notation and true meaning under the rug, and I assume that is the source of the confusion.
  
  > **Comments:**
  > **username_2**: The question was about Q-learning (not about the definition of the value function), which the OP assumed that it does not take into account the policy being followed.  
  > **username_1**: My interpretation of the question is that OP thought that Eq. (3.13) indicates that the action-value depends only on the state, action $(s, a)$. My answer is that there is dependence on all the future states/actions which is meant by the $\mathbb{E}_\pi$ notation. It's possible the OP meant something different, but I'm not sure the OP's question is as deep as some of the other comments are implying.  
  > **username_0**: By the way, OP is referring to me?  
  > **username_3**: @HermesMorales Yes - it stands for Original Poster (I think). If you'd like to clarify what you are asking about, or discuss what people are asssuming you are asking, please post a comment/reply  
  
  ---
  
  