3
$\begingroup$

How the Agent make the association between the current $Q_t(s_t,a_t)$ and a far future reward that by nature of my environment we get reward at least after 10-15 time steps from the action taken. If the rewards are collected in Replay Buffer and sampled at random then its probably gonna be broken, else if online training is used what part of the $Q$ update will consider the future reward ?

Edit: I have noticed another similar question Delayed Rewards in Reinforcement Learning. Yet, but it had fixed delay period, here the delay is stochastic and reward may not occur.

$\endgroup$

1 Answer 1

4
$\begingroup$

All value-based reinforcement learning (RL) methods use some form of backup between time steps. The backups take values known from later time steps, and use it to calculate values expected at earlier time steps.

This is an important part of RL method theory and design, and there is a visualisation of it called "backup diagrams" which you will find many examples of in the early chapters of Reinforcement Learning: An Introduction.

In Q learning, you can see the relationship between values at $t$ and $t+1$ in the update:

$$Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha(r_{t+1} + \gamma \text{max}_{a'} Q(s_{t+1}, a') - Q(s_t, a_t))$$

That is, the value of $Q(s_t, a_t)$ is being updated, and the values of $r_{t+1}$ and $s_{t+1}$ are used directly in the caclulation of that update. Over many repetitions of this update rule, values are backed up from later time steps (where you have better knowledge of the eventual rewards seen) to earlier time steps.

Specifically for tabular Q learning, you were concerned about initial inaccuracy of the bootstrap estimates. The resulting bias is a concern, and in some off-policy methods it can prevent covergence. However, with reasonable assumptions in tabular Q learning, it can be proved to converge.

$\endgroup$
5
  • $\begingroup$ I did briefly look for an open licensed image for backup diagram, but couldn't find one, so I just linked an article instead. $\endgroup$ Commented Sep 27, 2020 at 14:24
  • $\begingroup$ Thanks alot for your answer and yes the backup can be helpful in alot of cases, but the problem with backup using bellman unrolling is that we assume that our action selection during experience gathering (or our policy) was optimal. and if it wasn't then our calculated value for $Q(s_t, a_t)$ may be smaller than the optimal value of the state (as some steps have been taken randomly, but not following the most promising paths by maximizing the Q-value).The more steps on which we unroll the Bellman equation, the more incorrect our update could be. $\endgroup$
    – Ramzy
    Commented Sep 27, 2020 at 14:43
  • $\begingroup$ @Ramzy The future-to-past copy of rewards is due to backup process in general as described here. I think that answers your question as posed. There is proof of convergence for Q learning that shows that (in the tabular case) that the bootstrapping process - related to the specific backup choice in Q learning - will converge to accurate values. I will add a link. $\endgroup$ Commented Sep 27, 2020 at 15:20
  • $\begingroup$ I am not disagreeing as much as i want to find other options, as this is perfect for tabular case as it has considerably finite states. in a restricted environment it would be great idea to depend on such faith in reaching optimality, but my environment is quite complex, and it need modifications and debugging for every part of the framework. its usually an action, followed by silence, followed by reward (positive or negative). i could always map the action to the reward. but would it make sense in terms of RL to skip the intermediate states and go for the state where i got the reward ? $\endgroup$
    – Ramzy
    Commented Sep 27, 2020 at 16:05
  • $\begingroup$ Thanks again for your patience and your explanation is much appreciated. $\endgroup$
    – Ramzy
    Commented Sep 27, 2020 at 16:07

Your Answer

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

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