3
$\begingroup$

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). How can I still ensure that the algorithm gets these values (and their relative ranking) right?

EDIT 1

To provide a little more info: What happens currently 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?

EDIT 2

If this question is misleading (since reinforcement learning is an approximate dynamic programming method), please just let me know. I mean the algorithm usually does find an only slightly sub-optimal solution to the MDP.

EDIT 3

To answer some questions brought up in the comments:
(1) I do indeed have full control over the MDP including the reward function which in my case is sparse (0 until the terminal episode). The "true" Q-values I know from an analytical solution to the problem I am trying to solve using reinforcement learning.
(2) The rewards are the same for identical transitions. However, the rewards vary for any given state and action taken therein.
(3) 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.

$\endgroup$
  • $\begingroup$ Three questions for clarification: (1) Is your environment a "toy" one where you have set a learning challenge that you fully manage (it seems like it since you claim to know the "true" Q values)? (2) Does the stochastic behaviour manifest in reward values (given same transition), state transitions (given same start state and action) or both? (3) Is the environment highly stochastic starting from any state, or just from some subset? $\endgroup$ – Neil Slater Oct 27 '18 at 9:09
  • $\begingroup$ @NeilSlater I apologize for my late reply to your excellent questions. Please see the edit I made to the original question to adress them. $\endgroup$ – apitsch Oct 27 '18 at 16:22
4
+50
$\begingroup$

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.
$\endgroup$
  • 1
    $\begingroup$ I would add even in tabular case, OP has a problem. The guarantees of convergence are for infinite sampling, which is unrealistic, and tabular methods can also fail to fully converge in the same way. What the OP could do (and I might explain further in a separate answer) is get some measure of the variance in Q for the two actions, thus be able to estimate the standard error from taking N samples - this can give some rough bounds on how many samples of each action would be required to have, say, 99.9% chance of correctly ranking the two actions. $\endgroup$ – Neil Slater Oct 27 '18 at 9:23
  • 1
    $\begingroup$ Sorry, I meant variance in return, not in Q. The Q values in tabular case are roughly the means of sampled returns. So you can generate a standard error from measured variance in the return, and that is roughly your variance of the estimated Q value (assuming the policy is not changing much - we are close to correct ranking and optimal policy, except for those two pesky values that the OP complains about) $\endgroup$ – Neil Slater Oct 27 '18 at 9:29
  • 1
    $\begingroup$ @apitsch That said, I did just think of another point that may be very relevant for you: distributional RL. I've edited that as the new last point into the answer. $\endgroup$ – Dennis Soemers Oct 27 '18 at 17:18
  • 2
    $\begingroup$ @DennisSoemers: The trouble with scaling reward is that you also scale the variance of the reward by the same factor squared, meaning that there is no improvement in the learning agent's ability to discern between the two similar features based on the samples it has seen. $\endgroup$ – Neil Slater Oct 27 '18 at 18:04
  • 1
    $\begingroup$ Distributional Q learning is part of the "Rainbow" set of improvements to basic DQN, and some libraries do implement it. arxiv.org/abs/1710.02298 $\endgroup$ – Neil Slater Oct 27 '18 at 18:06

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.