2
$\begingroup$

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

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$)?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
5
  • 2
    $\begingroup$ 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. $\endgroup$ – Neil Slater Jun 4 at 14:45
  • 1
    $\begingroup$ 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). $\endgroup$ – nbro Jun 4 at 15:12
  • $\begingroup$ 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 thing could also be useful for the explanation. $\endgroup$ – nbro Jun 4 at 15:12
  • $\begingroup$ @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. $\endgroup$ – David Ireland Jun 4 at 15:46
  • 1
    $\begingroup$ @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 $\endgroup$ – Hermes Morales Jun 4 at 21:19
0
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$ – nbro Jun 4 at 16:50
  • $\begingroup$ 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. $\endgroup$ – Taw Jun 4 at 17:07
  • $\begingroup$ By the way, OP is referring to me? $\endgroup$ – Hermes Morales Jun 4 at 17:18
  • $\begingroup$ @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 $\endgroup$ – Neil Slater Jun 4 at 18:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.