I am trying to implement a Deep Q Network to play Asteroids. Unfortunately, I am not sure how to calculate the Q value exactly, if I am exploring. For example, the agent is exploring for 1 second (otherwise makes no sense; I cannot let it just explore one step). Unfortunately, it makes a mistake at 0.99s, and the reward collapses.

At the moment, I am using the following formula to evaluate or update the Q value:

$$Q_{new,t} = reward + \gamma Q_{max,t+1}$$

But how do I know the max Q value of the next step? I could consider the best Q value the network says, but this is not necessarily true.

You can see the current implementation at the following URL: https://github.com/SuchtyTV/RLearningBird/blob/master/src/main/java/rlgame/Brain.java.


For tabular Q-learning, the q-values for state s and action a are updated according to

$$ Q(s, a) \gets Q(s, a) + \alpha [(r + max_{a'} Q(s', a')) - Q(s,a)] $$

where $\alpha$ is the learning rate and $(r + max_{a'} Q(s', a')) - Q(s,a)$ is the difference between the current estimate of the q-value, $Q(s,a)$, and the target, $r + max_{a'} Q(s', a')$.

The target q-value is based on the greedy policy, not the exploratory policy. Q-learning is theoretically guaranteed to converge to the optimal policy for any behavior policy (like $\epsilon$-greedy) that is guaranteed to visit every state and action pair an infinite number of times. See Section 6.5 of the Sutton and Barto book for more details.

In contrast to Q-learning, the target q-value for SARSA is $r + Q(s', a')$, where $a'$ is chosen from an exploratory behavior policy like $\epsilon$-greedy. For SARSA the learned q-values are dependent on the behavior policy and therefore not guaranteed to converge to the optimal policy. A behavior policy that intentionally acted randomly for multiple consecutive actions, as in your example Asteroids exploratory policy, would likely lead to learning different q-values than would be learned for an $\epsilon$-greedy behavior policy.

Unfortunately Q-learning's theoretical guarantees of convergence to an optimal policy go out the window when nonlinear function approximation is introduced, as is the case for deep neural networks. Nevertheless, in the Deep Q-Networks paper, the q-value function is updated using a target value based on the maximum q-value for the next state. Specifically, if $Q(s, a, w)$ is a q-value function parameterized by weights $w$, then the weights are updated by

$$ w \gets w + \alpha [(r + max_{a'} Q(s', a', w^-)) - Q(s, a, w)] \nabla_w Q(s,a,w) $$

where $w^-$ are the parameters of the target network used to stabilize training. (See the paper for more details). This update rule is chosen to minimizes the loss function

$$ L(w) = E[(r + max_{a'} Q(s', a', w^-)) - Q(s, a, w)]^2 $$

For your own implementation, it may be helpful to see a code example of the Deep Q-Networks parameter updates. A tensorflow implementation is available in the function build_train in the OpenAI Baselines DeepQ code.

  • $\begingroup$ Thanks for your answer. Unfortunately, reading the python code of tensorflow is beyond my grasp. Maybe you can help me with this concrete example. A Game lasts 3 steps. First: the NN goes left then right, then up It gets the rewards 0,0,1. It calculated the q value of the first action to be -1. So what I would have to do step by step to calculate the new q value. $\endgroup$
    – TVSuchty
    Jan 4 '19 at 13:47

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.