3
$\begingroup$

I'm implementing DQN algorithm from scratch on MountainCar simulation. I'm using a setup of $reward = 1.0$ when car hits the flag, and $0$ otherwise. Reward decay factor is set to $\gamma=0.99$. Algorithm starts with exploration factor of $\epsilon = 1.0$ and decreases that over time to $\epsilon = 0.1$.

If I understood correctly, $Q$ function for some state and action pair is defined as:

$Q(s_t, a_t) = r_t + \gamma \times \operatorname{arg\,max}_a Q(s_{t+1}, a_{t+1})$

So, $Q_{max}$ would satisfy the condition:

$Q_{max} = r_{max} + \gamma \times Q_{max}$

Which means:

$Q_{max} = \frac{r_{max}}{1 - \gamma}$

However, since my network only approximates the $Q$ function it is possible for it to sometimes produce value greater than $Q_{max}$. When that happens, further training causes the values to start growing exponentially, and the entire thing blows up.

When I clamp the error of expected value vs. current predicted value to some small number, it still causes the blowup just a bit slower.

The only solution I can think of is to clamp the predicted value $Q(s_{t+1}, a{t+1})$ to $Q_{max}$ and forcing it to never go above that. I have done that, and got OK results with it.

Does this make sense? Is this a situation that happens in DQN? Or maybe I missed something and my implementation is a bit buggy?

$\endgroup$
  • $\begingroup$ Could you explain the reward structure you are using? I normally see MountainCar solved using $r=-1$ for each time step and $\gamma=1$ which would make your analysis not useful for clamping reward. $\endgroup$ – Neil Slater Nov 11 '17 at 15:59
  • $\begingroup$ @NeilSlater Text edited, 1.0 when car hits the flag and 0 otherwise. $\endgroup$ – omittones Nov 11 '17 at 16:08
  • $\begingroup$ That should work with discounting, as the discount factor will encourage shorter episodes. I suggest you try a non-discounted episodic approach too for comparison. $\endgroup$ – Neil Slater Nov 11 '17 at 16:14
  • $\begingroup$ @NeilSlater Using rewards of -1 and 1? $\endgroup$ – omittones Nov 11 '17 at 16:16
  • $\begingroup$ Using reward of -1 for every time step (or any other fixed negative value). there is no need for positive reward at the end, the return is just $-N_{steps\_remaining}$ compared to your version $\gamma^{N_{steps\_remaining}}$ - both expressions are maximised by minimising the $N_{steps\_remaining}$ $\endgroup$ – Neil Slater Nov 11 '17 at 16:20
2
$\begingroup$

As MountainCar is often solved with $\gamma = 1$ and a negative reward per timestep, you would immediately hit a problem with your ability to calculate a maximum action value in that case. However, I don't think that is your problem here, the discounted return with positive reward at the end should still encourage desired behaviour for the problem.

It is likely that you are experiencing known problems with RL, and the "deadly triad":

  • Function approximation (neural network)

  • on a bootstrap method (Q-Learning or any TD-learning approach)

  • off policy (learning optimal policy from non-optimal behaviour*, which is a feature of Q-learning)

This combination is often unstable and difficult to train. Your Q value clamping is one way to help stabilise values. Some features of DQN approach are also designed to deal with this issue:

  • Experience replay. Agent does not learn online, but instead puts each sample (S, A, R, S') into a memory table and trains the neural network on mini-batches sampled from this memory. Commonly this minibatch update is run on every step (after enough experience collected) and might be e.g. size 32. So learning updates happen faster than experience is collected.

  • Frozen bootstrap target network. The network used to calculate $\operatorname{max}_{a'} Q(s', a')$ when setting the target values to learn (in td target $R + \gamma \operatorname{max}_{a'} Q(s', a')$) is kept stable, and refreshed to use a copy of the current weights after a certain number of steps (e.g. 100 or 1000, or once every 10 episodes).


* Technically off-policy learning is learning the cost function for any policy $\pi$ from a different behaviour policy $b$, but the common case is for control systems attempting to find an optimal policy from an exploratory policy.

$\endgroup$

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.