Background
The main difference between Q-Learning and Deep Q-Learning is that we cannot update the Q-value for a single state-action pair using Deep Q-Learning. Every time we update the policy, the whole distribution over the action space changes.
Question
I am wondering if there are methods to overcome this specific problem for value-based RL, so that we can have the best of Q-Learning (i.e convergence is mathematically guaranteed) and the best of Deep Q L-Learning (i.e. possibility to generalize over a continuous state space). I am familiar with different possible improvements (Double Deep Q-Learning, Dueling Deep Q-learning, the use of target networks, different strategies for experience replay), but I was wondering if there are ways to improve this specific cause of instability, which is inherent in Neural networks.
1 Answer
I was wondering if there are ways to improve this specific cause of instability, which is inherent in Neural networks.
No. In fact we want this:
Every time we update the policy, the whole distribution over the action space changes.
This improves generalisation. Any method which isolates $\hat{q}(s,a)$ values, trains on $s_1,a_1$ to $s_n,a_n$ will not produce a meaningful value for $\hat{q}(s_{n+1},a_{n+1})$ if the combination has not been seen before.
Without generalisation, RL cannot be extended to large state or state/action spaces. The guarantees of convergence in tabular Q learning only apply in the limit of large numbers of visits to each relevant state/action pair. They are not of practical concern when doing so is computationally infeasible. Approximate methods which generalise from observed values to new ones are the approach used to solve this problem, and these must come with the trait (of non-isolation between estimates) that you would like to remove.
This is one of many trade offs that you have to consider in machine learning. In this case, the better your estimator generalises, the faster it will learn, but the more inaccurate it will be over the whole space. Deep RL implemented with complex neural networks errs towards allowing for better accuracy, and pays for this by requiring large numbers of samples in order to learn a value function or policy.
There are approaches you can take to minimise this effect. Some are essentially feature engineering - for instance if you have a good intuition or understanding of how a specific state feature will generalise, you can take advantage of that by converting it using a suitable function.
In some cases, it might be possible to find a tiling or other binary grouping function that recovers a small enough finite state space that has excellent generalisation properties. In which case you could use a linear regression model or even tabular approach for $\hat{q}(s,a)$ and have an approach with better guarantees for convergence. Whether or not this is possible will depend on the problem. If your state includes some very complex data - e.g. a computer vision component - then it is unlikely you will find a useful transformation.
