I am trying to understand the different reward functions modelled in a reinforcement learning problem. I want to be able to know how the temporal credit assignment problem, (where the reward is observed only after many sequences of actions, and hence no immediate rewards observed) can be mitigated.

From reading the DQN paper, I am not able to sieve out how the immediate rewards are being modelled when $Q_{target}(s,a; \theta) = r_s + argmax_aQ(s',a'; \theta)$. What is $r_s $ used in the case where the score has not changed ? Therefore what is the immediate rewards being modelled for temporal credit assignment problems in atari game ?

If $r_s$ is indeed 0 until score changes, would it affect the accuracy of the DQN ? it seems like the update equation would not be accurate if you do not even know what is the immediate reward if you take that action.

What are some of the current methods used to solve the temporal credit assignment problem ?

Also, I can't seem to find many papers that address the temporal credit assignment problem

  • $\begingroup$ Hi Neil, yes immediate reward is the word. I will change it $\endgroup$ – calveeen Feb 11 '20 at 17:02

To answer your questions in order:

What is $r_s $ used in the case where the score has not changed ?

It is $0$.

Therefore what is the immediate rewards being modelled for temporal credit assignment problems in atari game ?

Rewards can be re-modelled to aid speed of learning. This is called "reward shaping", and is typically done by domain experts who can adjust numbers to reward known good intermediate states and actions.

For DQN Atari, this was not done. Instead, the researchers performed a reward normalisation/scaling so that games which used moderate scoring system in single digits could be handled by the same neural network approximator as games that handed out thousands of points at a go.

Using sparse rewards is standard practice in reinforcement learning, and the credit assignment problem is solved to some degree by all reinforcement learning methods. Essentially the value functions work as a prediction mechanism theoretically whatever the reward sparsity, so if they are correct, thay can be used to drive policy whether the next reward is 1, 50 or 1000 time steps away. The reward backup updates in everything from Value Iteration, through Monte Carlo Control, SARSA, Q-Learning and Actor-Critic all backup values to states/actions seen in earlier time steps. This value backup is a basic mechanism that addresses credit assignment in principle. The credit assignment problem is then a matter of degree and difficulty of different environments, such that sometimes it is readily solved, and other times it is a major hurdle.

In the case of video games, especially older arcade games, it is often not a very hard part of the problem. The games are designed to reward human players by incrementing scores frequently, with very many sub-goals already within the game. In fact this is one of the attractions of video games as toy environments for developing new algorithms.

For example the classic space invaders does not simply score +1 for surviving a wave of enemies, but adds points for every player missile that hits. Although the score does not increment on every frame, the reward sparsity is relatively low for games like this, and simple single-step Q learning with experience replay can solve the credit assignment problem readily for that environment (experience replay does help a little with credit assignment). This was what was demonstrated with the original DQN Atari paper, there were no extra allowances made for reward sparsity.

If $r_s$ is indeed 0 until score changes, would it affect the accuracy of the DQN ?

Not directly, the DQN predicts future expected rewards and can in principle account for delay and sparsity in its estimates. However, if this becomes very sparse you get two problems:

  • Discovering the positive rewards within the environment may take a long time, and may require more advanced techniques, such as reward shaping to encourage searching behaviour (a small negative reward per time step) or "curiousity"

  • Credit assignment becomes much harder as the possible number of combinations that could of contributed to success can grow exponentially with temporal distance between rewards. Resolving whch ones are important, especially early in a trajectory leading to reward, can take many samples.

What are some of the current methods used to solve the temporal credit assignment problem ?

As noted above, this is core problem in RL, so there are many approaches in the literature. Some standard approaches are:

  • Background planning as used by DynaQ, or experience replay. This re-evaluates states and actions seen before whilst using latest estimates, and can backup values to where important decisions are made within a trajectory. Prioritised experience replay helps even more by focusing on updates that make the most difference to the current estimates.

  • TD($\lambda$) with eligibility traces. Eligibility traces are intuitively a credit-assignment mechanism, they track state features that were active recently and multiply value updates based on the trace vector. Again, this causes state or state action values to backup to earlier parts of trajectories faster.

  • Reward shaping as discussed above. In some research settings this might be seen as "cheating" - for instance when facing a standardised environment test for developing algorithms, adding in domain knowledge to help the agent just demonstrates the core algorithm is weaker than claimed. However, when the challenge presented is to solve an environment with the best agent possible, it is fine to use any knoweldge (or of course not to use RL at all).

  • 1
    $\begingroup$ hey Neil thank you for the detailed explanation above ! but why would you need to normalise the rewards for a NN to handle large and moderate rewards and what do you mean by reward backup ? $\endgroup$ – calveeen Feb 12 '20 at 1:36
  • 1
    $\begingroup$ @calveeen: i explain why you need to normalise the rewards in the answer - to prevent the NN needing to handle value predictions (and associated errors) ranging from +1 to +10000 depending on the game. This would impact hyperparameters such as learning rate, and the goal of the exercise was to have one agent that could solve all games without interventions such as hyperparameter search specific to each game. I.e. the agent is ia generalist Atarii game solver out of the box. $\endgroup$ – Neil Slater Feb 12 '20 at 7:40
  • 1
    $\begingroup$ @calveeen: reward backup is the process of propagating reward values seen backwards through the trajectory, which is what all the value-based methods do in their update steps. It is related to the backup diagrams, see towardsdatascience.com/all-about-backup-diagram-fefb25aaf804 $\endgroup$ – Neil Slater Feb 12 '20 at 7:43

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.