7
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ I edited your post to include your feedback (that you provided in a comment, which is now deleted) and to try to clarify your actual problem and to be consistent with the answer that you accepted (which doesn't actually provide many details about BP). Please, make sure that the current version of this post is consistent with what you wanted to ask. If not, edit this post to rewrite the parts of the post where I changed the meaning, or just roll back to a previous version of the post (but I don't advise you to do it, because I think the current version is consistent with the accepted answer). $\endgroup$ – nbro Dec 28 '20 at 13:12
  • $\begingroup$ Here and here you have two related questions. $\endgroup$ – nbro Dec 28 '20 at 13:49
8
$\begingroup$

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

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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)? $\endgroup$ – Yadeses Dec 5 '17 at 21:35
3
$\begingroup$

You should read up on these papers:

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.

$\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.