How can I ensure convergence of DDQN, if the true Q-values for different actions in the same state are very close?

Question

I am applying a Double DQN algorithm to a highly stochastic environment where some of the actions in the agent's action space have very similar "true" Q-values (i.e. the expected future reward from either of these actions in the current state is very close). The "true" Q-values I know from an analytical solution to the problem.

I have full control over the MDP, including the reward function, which in my case is sparse (0 until the terminal episode). The rewards are the same for identical transitions. However, the rewards vary for any given state and action taken therein. Moreover, the environment is only stochastic for a part of the actions in the action space, i.e. the action chosen by the agent influences the stochasticity of the rewards.

How can I still ensure that the algorithm gets these values (and their relative ranking) right?

Currently, what happens is that the loss function on the Q-estimator decreases rapidly in the beginning, but then starts evening out. The Q-values also first converge quickly, but then start fluctuating around.

I've tried increasing the batch size, which I feel has helped a bit. What did not really help, however, was decreasing the learning rate parameter in the loss function optimizer.

Which other steps might be helpful in this situation?

So, the algorithm usually does find only a slightly suboptimal solution to the MDP.

Answer 1

Let $Q^*(s, a)$ denote the "true" $Q$-value for a state-action pair $(s, a)$, i.e. the values that we're hoping to learn to approximate using a neural network that outputs $Q(s, a)$ values.

The problem you describe is basically that you have situations where $Q^*(s, a_1) = Q^*(s, a_2) + \epsilon$ for some very small value $\epsilon$, where $a_1 \neq a_2$.

An important thing to note is that the "true" $Q^*$ values are directly determined by the reward function, which essentially encodes your objective. If your reward function is constructed in such a way that it results in the situation described above, that means the reward function is essentially saying: "it doesn't really matter much whether we pick action $a_1$ or $a_2$, there is some difference in returns but it's a tiny difference, we hardly care." The objective implied by the reward function in some sense contradicts what you describe in the question that you want. You say that you care (quite a lot) about a tiny difference in $Q^*$-values, but normally the "extent to which we care" is proportional to the difference in $Q^*$-values. So, if there is only a tiny difference in $Q^*$-values, we should really only care a tiny bit.

Now, with tabular RL algorithms (like standard $Q$-learning), we do expect to be able to eventually converge to the truly correct solutions, we expect to eventually be capable of correctly ranking different actions even when the differences in $Q^*$-values are small. When you enter function approximation (especially neural networks), this story changes. It's pretty much in the name already; function approximation, we cannot guarantee being able to do better than just approximating. So, 100% ensuring that you'll be able to learn the correct rankings is not going to be feasible. There may be some things that can help though:

• If you are "in control" of your environment and its reward function (meaning, you implemented it yourself and/or can modify it if you like), modifying the reward function would probably be the single most effective solution to your problem. As I described above, a reward function that results in tiny differences in $Q^*$-values essentially encodes that you only care about those difference to a tiny (negligible) extent. If that's not the case, if you actually do care about those tiny differences... well, you can try changing the reward function to accentuate those tiny differences. For example, you could try simply multiplying all rewards by $100$, then all differences in returns are also multipled by $100$. Note that this does mean you get larger values everywhere (larger losses, larger gradients, etc.), so it would require changing hyperparameters (like learning rate) accordingly, and could destabilize things. But at least it will emphasize those small differences in $Q^*$-values. (probably won't work, see Neil's comment)
• Increasing batch size. You already mentioned this yourself, but I'll also explain why it can help. A major issue in your problem is that you described the environment to be highly stochastic. This means you get a large amount of variance in your observed returns, and therefore also in your updates. If the true differences in $Q^*$-values are very small, these differences will get dominated and become completely invisible due to high variance in observations. You can smooth out this variance by increasing the batch size.
• Decreasing learning rate. You also mentioned this in the question, and that it didn't really help. I suppose a high learning rate early on can help to learn more quickly, but decreasing it later on can help to take more "careful", small update steps that don't take "jumps" of a magnitude greater than the true difference in $Q^*$-values.
• Distributional Reinforcement Learning: algorithms like $Q$-learning, DQN, Double DQN, etc., they all learn what we can call values, or scalars, or point estimates. Given a state-action pair $(s, a)$, such a $Q$-value represents the expected returns obtained by executing $a$ in $s$ and continuing with a greedy policy afterwards. In stochastic environments, it is possible that the true expected value $Q^*(s, a)$ never coincides with any conrete observation at the end of an actual trajectory. For example, suppose that in some state $s$, an action $a$ has a probability of $0.5$ of giving a reward of $1$ and instantly terminating afterwards, but also has a probability of $0.5$ of giving a reward of $0$ and instantly terminating. Then, we have $Q^*(s, a) = 0.5$, but we never actually observe a return of $0.5$; we always observe returns of either $0$ or $1$. When comparing the output of the learned $Q$-function (which should hopefully be around $0.5$ in such a situation) to any observed trajectories, we'll almost always have a non-zero error and take update steps that keep bouncing around the optimal solution, rather than converging to the optimal solution. Since you mentioned that you see $Q$-values fluctuating around, you may have observed this. Excessive fluctuations around $Q$-value estimates will likely make it difficult to get a consistent, stable ranking when the optimal $Q$-values that you are fluctuating around are themselves very close to each other. There is a class of algorithms (extensions of DQN mostly) referred to as distributional RL, which aim to address this issue by learning a full distribution of returns we expect to be capable of observing, rather than the single-point estimates that $Q$-values essentially are. I believe the first major paper on this topic was the following: https://arxiv.org/abs/1707.06887. There have been multiple follow-up papers too, the most recent of which I believe (but may be wrong here) to be this one: https://arxiv.org/abs/1806.06923. In general, I do know Marc Bellemare and Rémi Munos at least have done quite some work on that, so you could search for those names too.