0
$\begingroup$

Consider a Markov decision process in which we transition from state $s_t \rightarrow s_{t+1}$ by taking action $a_t$, and then apply an update to a single entry from a table of $Q$-values based on a stochastic reward $r(s_t, a_t)$:

$$Q_{t+1}(s_t, a_t) = (1 - \alpha_t(s_t, a_t))Q_t(s_t, a_t) + \alpha_t(s_t, a_t)\left[ r(s_t, a_t) + \gamma Q_t(s_{t+1}, a_{t+1}) \right]$$

This is the update rule for $\texttt{SARSA}(0)$, which is an implementation of on-policy $Q$-learning. (*)

Can we assume the current reward is independent from the next state, or the current $Q$-values for the next state? In other words,

\begin{align} r(s_t, a_t) &\,\, \overset{?}{\perp\!\!\!\perp} \,\, s_{t+1} \\ r(s_t, a_t) &\,\, \overset{?}{\perp\!\!\!\perp} \,\, Q_t(s_{t+1}, \cdot) \end{align}

If not, what additional constraints are needed in order to make the weaker claim that they are uncorrelated? In the end, what I basically need to have is uncorrelatedness: $$E\left[ r(s_t, a_t) Q_t(s_{t+1}, \cdot) \right] = E\left[ r(s_t, a_t) \right]E\left[Q_t(s_{t+1}, \cdot)\right]$$

More generally, how can we determine this for various terms in such a stochastic process?

(*) Source: Convergence Results for Single-Step On-Policy Reinforcement-Learning Algorithms

$\endgroup$

2 Answers 2

3
+150
$\begingroup$

I believe that the current reward given the current state is independent of the next state (i.e. uncorrelated). This seems to be at the core of your intuition about the next state not providing any additional information about the current reward (so it seems like they should be uncorrelated).

However, the unconditional current reward obviously is not independent of the next state, because both depend on the current state. Thus, if you look at a time-series of (state[t], reward[t+1]) it is certainly possible to observe a correlation, and the conditions required to ensure that there is no correlation would presumably be some pretty convoluted conditions on the Markov transitions.

To re-phrase one more way, the next state doesn't provide us with additional information about the current reward only because we already know the current state. If we didn't know the current state, then knowing the next state would give us information about the current state, which we could leverage to learn something about the current reward.

$\endgroup$
2
  • $\begingroup$ I think it's safe to assume conditioning of the reward on the current state, because the reward depends explicitly on it (as the notation suggests)? $\endgroup$ May 16, 2016 at 18:40
  • 1
    $\begingroup$ Well, that's the question, and I think it's at the heart of the confusion between you and @makokal. The reward conditioned on the current state is independent of EVERYTHING, because it depends only on the current state. But if you look at the timeseries of rewards and states, and ask empirically whether there is a correlation between reward[t] and state[t+1], you will probably find one. The expression for uncorrelatedness in your original post is based on unconditional expectations, and you would likely observe a correlation. $\endgroup$ May 16, 2016 at 18:50
1
$\begingroup$

No, by the Markov assumption $r(s_t,a_t)$ only depends on $s_t$ and $a_t$. The Q value for that pair $(s_t, a_t)$ only depends on that state and future states (with discounting).

$\endgroup$
4
  • $\begingroup$ Wouldn't this indicate that the answer to my question should be "No"? Because $s_{t+1}$ is a future state. $\endgroup$ May 8, 2016 at 21:10
  • $\begingroup$ Yes, sorry for the confusion, edited the answer $\endgroup$
    – makokal
    May 9, 2016 at 15:01
  • $\begingroup$ This answer still isn't very clear to me. I thought the answer should be "yes" because intuitively knowing the next state will be $s_{t+1}$ shouldn't give us any more information about the current reward than without this knowledge. Formally, $P(r(s_t, a_t) = r \, | \, s_{t+1} = s) = P(r(s_t, a_t) = r)$ which implies independence. I am in need of some additional rigour. $\endgroup$ May 9, 2016 at 19:12
  • $\begingroup$ FYI I have not accepted this answer as valid and the bounty expires in 1 day. $\endgroup$ May 16, 2016 at 0:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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