Answers.Body: <p>You should read up on these papers:</p>
  <ul>
  <li><p><a href="https://www.nature.com/articles/nature14236" rel="nofollow noreferrer">Deep Q-Networks</a></p>
  </li>
  <li><p><a href="http://proceedings.mlr.press/v48/mniha16.pdf" rel="nofollow noreferrer">Asynchronous Deep Reinforcement Learning</a></p>
  </li>
  </ul>
  <p>Both by DeepMind. They achieved super-human results on video-games and other tasks. They describe the algorithms quite well. It is not as simple as the previous answer, which won't converge to a policy in complex environments.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2017-12-07T17:19:40.573Z
Answers.LastActivityDate: 2020-12-28T13:42:43.923Z
Answers.LastEditDate: 2020-12-28T13:42:43.923Z
Answers.UserDisplayName: BlueMoon93
Answers.Body: <h3>Gradient descent and back-propagation</h3>
  <p>In deep learning, gradient descent (GD) and back-propagation (BP) are used to update the weights of the neural network.</p>
  <p>In reinforcement learning, one could map (state, action)-pairs to Q-values with a neural network. Then GD and BP can be used to update the weights of this neural network.</p>
  <h3>How to design the neural network?</h3>
  <p>In this context, a neural network can be designed in different ways. A few are listed below:</p>
  <ol>
  <li><p>The state and action are concatenated and fed to the neural network. The neural network is trained to return a single Q-value belonging to the previously mentioned state and action.</p>
  </li>
  <li><p>For each action, there is a neural network that provides the Q-value given a state. This is not desirable when a lot of actions exist.</p>
  </li>
  <li><p>Another option is to construct a neural network that accepts as input the state. The output layer consists of <span class="math-container">$K$</span>-units where <span class="math-container">$K$</span> is the number of possible actions. Each output unit is trained to return the Q-value for a particular action.</p>
  </li>
  </ol>
  <h3>Q-learning update rule</h3>
  <p>This is the Q-learning update rule</p>
  <p><img src="https://i.sstatic.net/OMzXf.png" alt="Update rule" /></p>
  <p>So, we choose an action <span class="math-container">$a_t$</span> (for example, with <span class="math-container">$\epsilon$</span>-greedy behavior policy) in the state <span class="math-container">$s_t$</span>. Once the action <span class="math-container">$a_t$</span> has been taken, we end up in a new state <span class="math-container">$s_{t+1}$</span> and receive a reward <span class="math-container">$r_{t+1}$</span> associated with it. To perform the update, we also need to choose the Q-value in <span class="math-container">$s_{t+1}$</span> associated with the action <span class="math-container">$a$</span>, i.e. <span class="math-container">$\max _{a} Q\left(s_{t+1}, a\right)$</span>. Here, <span class="math-container">$\gamma$</span> is the discount factor and <span class="math-container">$\alpha$</span> is the learning rate.</p>
  <h3>Back-propagation and Q-learning</h3>
  <p>If we use a neural network to map states (or state-action pairs) to Q-values, we can use a similar update rule, but we use GD and BP to update the weights of this neural network.</p>
  <p>Here's a possible implementation of a function that would update the weights of such a neural network.</p>
  <pre><code>def update(self, old_state, old_action, new_state, 
    reward, isFinalState = False):
   
    # The neural network has a learning rate associated with it. 
    # It is advised not to use two learning rates
    learningRate = 1
    
    # Obtain the old value
    old_Q = self.getQ(old_state, old_action)
  
    # Obtain the max Q-value
    new_Q = -1000000
    action = 0
    for a in self.action_set:
      q_val = self.getQ(new_state, a)
      if (q_val &gt; new_Q):
        new_Q = q_val
        action = a  
  
    # In the final state there is no action to be chosen
    if isFinalState:
      diff = learningRate * (reward - old_Q)
    else:
      diff = learningRate * (reward + self.discount * new_Q - old_Q)
  
    # Compute the target 
    target = old_Q + diff
  
    # Update the Q-value using backpropagation
    self.updateQ(action, old_state, target)
  </code></pre>
  <p>In the pseudocode and in the Q-learning update formula above, you can see the discount factor <span class="math-container">$\gamma$</span>. This simply denotes whether we are interested in an immediate reward or a more rewarding and enduring reward later on. This value is often set to 0.9.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-05T21:35:23.863Z
Answers.Text: I am sorry, there actually is one thing not entirely clear to me. How would one do backpropagation with the last option (one net giving the quality for K actions)?
Answers.UserDisplayName: Yadeses
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2017-12-05T18:39:00.997Z
Answers.LastActivityDate: 2020-12-28T13:44:27.907Z
Answers.LastEditDate: 2020-12-28T13:44:27.907Z
Answers.UserDisplayName: Daemonstool
Body: <p>I have followed a course on machine learning, where we learned about the gradient descent (GD) and back-propagation (BP) algorithms, which can be used to update the weights of neural networks, and reinforcement learning, in particular, Q-learning. I implemented these concepts separately.</p>
  <p>Now, I was thinking about using a neural network to approximate the Q-function, <span class="math-container">$Q(s, a)$</span>, but I don't really know how to design the neural network and how to use back-propagation to update the weights of this neural network (NN).</p>
  <ol>
  <li><p>What should the inputs and outputs of this NN be?</p>
  </li>
  <li><p>How can I use GD and BP to update the weights of such an NN? Or should I use a different algorithm to update the weights?</p>
  </li>
  </ol>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-28T13:49:14.917Z
Comments.Text: [Here](https://ai.stackexchange.com/q/25277/2444) and [here](https://ai.stackexchange.com/q/21669/2444) you have two related questions.
Comments.UserDisplayName: nbro
Tags: <neural-networks><reinforcement-learning><dqn><deep-rl><backpropagation>
Title: How to combine backpropagation in neural nets and reinforcement learning?
UserDisplayName: Yadeses
ThreadText: # How to combine backpropagation in neural nets and reinforcement learning?
  
  (Asked by: username_0 on 2017-12-04)
  
  I have followed a course on machine learning, where we learned about the gradient descent (GD) and back-propagation (BP) algorithms, which can be used to update the weights of neural networks, and reinforcement learning, in particular, Q-learning. I implemented these concepts separately.
  
  Now, I was thinking about using a neural network to approximate the Q-function, $Q(s, a)$, but I don't really know how to design the neural network and how to use back-propagation to update the weights of this neural network (NN).
  
  1. What should the inputs and outputs of this NN be?
  2. How can I use GD and BP to update the weights of such an NN? Or should I use a different algorithm to update the weights?
  
  **Tags:** neural-networks, reinforcement-learning, dqn, deep-rl, backpropagation
  
  > **Comments:**
  > **username_1**: [Here](https://ai.stackexchange.com/q/25277/2444) and [here](https://ai.stackexchange.com/q/21669/2444) you have two related questions.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_3 on 2017-12-05. Score: 8 | Accepted answer
  
  ### Gradient descent and back-propagation
  
  In deep learning, gradient descent (GD) and back-propagation (BP) are used to update the weights of the neural network.
  
  In reinforcement learning, one could map (state, action)-pairs to Q-values with a neural network. Then GD and BP can be used to update the weights of this neural network.
  
  ### How to design the neural network?
  
  In this context, a neural network can be designed in different ways. A few are listed below:
  
  1. The state and action are concatenated and fed to the neural network. The neural network is trained to return a single Q-value belonging to the previously mentioned state and action.
  2. For each action, there is a neural network that provides the Q-value given a state. This is not desirable when a lot of actions exist.
  3. Another option is to construct a neural network that accepts as input the state. The output layer consists of $K$-units where $K$ is the number of possible actions. Each output unit is trained to return the Q-value for a particular action.
  
  ### Q-learning update rule
  
  This is the Q-learning update rule
  
  ![Update rule](https://i.sstatic.net/OMzXf.png)
  
  So, we choose an action $a\_t$ (for example, with $\epsilon$-greedy behavior policy) in the state $s\_t$. Once the action $a\_t$ has been taken, we end up in a new state $s\_{t+1}$ and receive a reward $r\_{t+1}$ associated with it. To perform the update, we also need to choose the Q-value in $s\_{t+1}$ associated with the action $a$, i.e. $\max \_{a} Q\left(s\_{t+1}, a\right)$. Here, $\gamma$ is the discount factor and $\alpha$ is the learning rate.
  
  ### Back-propagation and Q-learning
  
  If we use a neural network to map states (or state-action pairs) to Q-values, we can use a similar update rule, but we use GD and BP to update the weights of this neural network.
  
  Here's a possible implementation of a function that would update the weights of such a neural network.
  
  ```
  def update(self, old_state, old_action, new_state, 
    reward, isFinalState = False):
   
    # The neural network has a learning rate associated with it. 
    # It is advised not to use two learning rates
    learningRate = 1
    
    # Obtain the old value
    old_Q = self.getQ(old_state, old_action)
  
    # Obtain the max Q-value
    new_Q = -1000000
    action = 0
    for a in self.action_set:
      q_val = self.getQ(new_state, a)
      if (q_val > new_Q):
        new_Q = q_val
        action = a  
  
    # In the final state there is no action to be chosen
    if isFinalState:
      diff = learningRate * (reward - old_Q)
    else:
      diff = learningRate * (reward + self.discount * new_Q - old_Q)
  
    # Compute the target 
    target = old_Q + diff
  
    # Update the Q-value using backpropagation
    self.updateQ(action, old_state, target)
  
  ```
  
  In the pseudocode and in the Q-learning update formula above, you can see the discount factor $\gamma$. This simply denotes whether we are interested in an immediate reward or a more rewarding and enduring reward later on. This value is often set to 0.9.
  
  > **Comments:**
  > **username_0**: I am sorry, there actually is one thing not entirely clear to me. How would one do backpropagation with the last option (one net giving the quality for K actions)?  
  
  ---
  
  ### Answer by username_2 on 2017-12-07. Score: 3
  
  You should read up on these papers:
  
  * [Deep Q-Networks](https://www.nature.com/articles/nature14236)
  * [Asynchronous Deep Reinforcement Learning](http://proceedings.mlr.press/v48/mniha16.pdf)
  
  Both by DeepMind. They achieved super-human results on video-games and other tasks. They describe the algorithms quite well. It is not as simple as the previous answer, which won't converge to a policy in complex environments.
  
  
  ---
  
  