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
+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$
  • $\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$ – Aaron Voelker May 16 '16 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$ – Jacob Socolar May 16 '16 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$
  • $\begingroup$ Wouldn't this indicate that the answer to my question should be "No"? Because $s_{t+1}$ is a future state. $\endgroup$ – Aaron Voelker May 8 '16 at 21:10
  • $\begingroup$ Yes, sorry for the confusion, edited the answer $\endgroup$ – makokal May 9 '16 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$ – Aaron Voelker May 9 '16 at 19:12
  • $\begingroup$ FYI I have not accepted this answer as valid and the bounty expires in 1 day. $\endgroup$ – Aaron Voelker May 16 '16 at 0:34

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.