Cs234 lecture 6 deep q learning and nn
Nonlinear function approximations for RL:
- Kernel Based Approaches (Convergence Properties but don’t scale well)
- Neural Networks
History of NN approaches to RL:
- 1994 TD Backgammon.
- 1995-1990 Was proved that Function approximation + off policy control + bootstrapping (“the deadly triad”) can fail to converge and even simple cases can fail. People felt discouraged from using NN approaches.
- 2014 Atari
Deep Q Learning and Improvements
In 2014 Atari Paper, DQN Used Q-learning with CNN as Value Function Approximator. They used two tricks to make it work:** Experience Replay** and Fixed Q Targets.
Experience Replay
Keep a store of prior experience and sample from that store with replacement as the training dataset.
Benefits - allows us to use a lot more data - experience is not just thrown away after being used.
Note that each sampled action (s,a,r,s’) will update the weights a different amount even if the same action (s,a,r,s’) was sampled before - because the Q function was different from before, so the update is now different.
Expereince replay was super super important for success (Appendix 1)!
Fixed Q Targets
Basically, instead of updating the target weights evert step, when calculating the bootstrap value use the same weights for every couple of steps (freeze its value) and then reset the frozen value to the new learned value every n steps. This is no longer precise gradient descent but improves stability in the training with little loss.
**
**
Some Improvements over Original DeepQL Paper.
Double DQN
Improvement over Original Deep QL Paper.
Basically Double Q-learning applied to DQN.
Easy to Implement, impressive Results (Apendix 1)
Prioritized Replay: In TD Learning, the order of sampling from the replay experience affects the speed of learning, becuase it determines whether or not some updates will propagate to other states.
The authors proposed sampling updates with probability proportional to their DQN error. So tuples (s,a,r,s’) for which the DQN update is more accurate is sampled more often.
This seems to have a very high impact also! (Appendix 1) (See Appendix 2 for example)
**
**
If we knew the optimal order in which to sample, the above paper proved that the time to convergence can be reduced by an exponential factor! Of course it is computationally infeasible to know the exact optimal order, but we can estimate it with heuristics.
(note: alpha is a temperature setting which, if 0 gives requal prob for all actions and if large gives the max action every time).
Dueling QN:
Also very good effects! (Appendix 1)
Intuition: The features that you might need to write down the values of the state might be different from the features you need to specify the relative benefit of differnet actions (advantage functions) in that state.
Idea: Instead of estimating the Q value function, estimate the advantage function.
**
**
However, the advantage function is unidedentifiable (there is not a unique V and A you can decompose Q into - you can add a constant to one and subtract the same from the other and get the same Q. So we add an additional constraint to force out a particular V, A.
Practical Tips for training DQNs:
**
**
**
**
** **
Appendix 1: DQN for Atari, Summary and Results
** **
**
**
Appendix 2: Mars Rover example for different values of estimate for differnet orders sampling.
Tip: Build and debug your Q-learning implementation first before you test on Atari, Atari could take several hours.