Answers.Body: <p>For tabular Q-learning, the q-values for state s and action a are updated according to</p>
  
  <p><span class="math-container">$$
  Q(s, a) \gets Q(s, a) + \alpha [(r + max_{a'} Q(s', a')) - Q(s,a)]
  $$</span></p>
  
  <p>where <span class="math-container">$\alpha$</span> is the learning rate and <span class="math-container">$(r + max_{a'} Q(s', a')) - Q(s,a)$</span> is the difference between the current estimate of the q-value, <span class="math-container">$Q(s,a)$</span>, and the target, <span class="math-container">$r + max_{a'} Q(s', a')$</span>.  </p>
  
  <p>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 <span class="math-container">$\epsilon$</span>-greedy) that is guaranteed to visit every state and action pair an infinite number of times.  See Section 6.5 of <a href="http://incompleteideas.net/book/the-book.html" rel="nofollow noreferrer">the Sutton and Barto book</a> for more details.</p>
  
  <p>In contrast to Q-learning, the target q-value for SARSA is <span class="math-container">$r + Q(s', a')$</span>, where <span class="math-container">$a'$</span> is chosen from an exploratory behavior policy like <span class="math-container">$\epsilon$</span>-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 <span class="math-container">$\epsilon$</span>-greedy behavior policy.</p>
  
  <p>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 <a href="https://deepmind.com/research/dqn/" rel="nofollow noreferrer">Deep Q-Networks paper</a>, the q-value function is updated using a target value based on the maximum q-value for the next state. Specifically, if <span class="math-container">$Q(s, a, w)$</span> is a q-value function parameterized by weights <span class="math-container">$w$</span>, then the weights are updated by</p>
  
  <p><span class="math-container">$$
  w \gets w + \alpha [(r + max_{a'} Q(s', a', w^-)) - Q(s, a, w)] \nabla_w Q(s,a,w)
  $$</span></p>
  
  <p>where <span class="math-container">$w^-$</span> 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</p>
  
  <p><span class="math-container">$$
  L(w) = E[(r + max_{a'} Q(s', a', w^-)) - Q(s, a, w)]^2
  $$</span></p>
  
  <p>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 <code>build_train</code> in the OpenAI Baselines <a href="https://github.com/openai/baselines/blob/master/baselines/deepq/build_graph.py" rel="nofollow noreferrer">DeepQ</a> code.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-04T13:47:48.377Z
Answers.Text: 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.
Answers.UserDisplayName: TVSuchty
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-04T05:07:11.100Z
Answers.LastActivityDate: 2019-01-04T05:07:11.100Z
Answers.UserDisplayName: todddeluca
Body: <p>I am trying to implement a Deep Q Network to play <a href="http://www.freeasteroids.org/welcome/" rel="nofollow noreferrer">Asteroids</a>. 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. </p>
  
  <p>At the moment, I am using the following formula to evaluate or update the Q value:</p>
  
  <p><span class="math-container">$$Q_{new,t} = reward + \gamma Q_{max,t+1}$$</span></p>
  
  <p>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.</p>
  
  <p>You can see the current implementation at the following URL:
  <a href="https://github.com/SuchtyTV/RLearningBird/blob/master/src/main/java/rlgame/Brain.java" rel="nofollow noreferrer">https://github.com/SuchtyTV/RLearningBird/blob/master/src/main/java/rlgame/Brain.java</a>.</p>
  
Tags: <reinforcement-learning><game-ai><q-learning><deep-rl>
Title: How do I update the Q values of a Deep Q Network when exploring?
UserDisplayName: TVSuchty
ThreadText: # How do I update the Q values of a Deep Q Network when exploring?
  
  (Asked by: username_0 on 2019-01-03)
  
  I am trying to implement a Deep Q Network to play [Asteroids](http://www.freeasteroids.org/welcome/). 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>.
  
  **Tags:** reinforcement-learning, game-ai, q-learning, deep-rl
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-01-04. Score: 3
  
  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](http://incompleteideas.net/book/the-book.html) 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](https://deepmind.com/research/dqn/), 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](https://github.com/openai/baselines/blob/master/baselines/deepq/build_graph.py) code.
  
  > **Comments:**
  > **username_0**: 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.  
  
  ---
  
  