3
$\begingroup$

As I am trying to make an AI with reinforcement learning, I have found out and implemented a lot of things such as both these topics (NNs and RL) separately. But when trying to combine them, I have ran into trouble. I have not been able to find or think of a way to properly do backpropagation with RL. So what I was trying to do was a local search for all actions and then use a neural net for the Q(s, a) function. How would one do the backpropagation in such a neural net?

  • Up to this point, I have only done things with gradient descent. Should one use a different algorithm? Could one calculate the Q(s, a) value based on the output of the neural net with a discount factor?

This is what the formula would suggest, but I could not find any confirmation.

$\endgroup$
  • 1
    $\begingroup$ This is a bad post because it contains a lot of questions (and hence it should be closed as "too broad"). Ideally, a post should contain one question (if possible). $\endgroup$ – nbro Jul 9 '18 at 19:47
  • 1
    $\begingroup$ Can you clarify more about exactly what this hybrid system is supposed to do, and why you think combining NN's and RL is the right approach? I ask because superficially this question sounds a bit like "I'd like to combine this squirrel and this table saw, how do I do that?" $\endgroup$ – mindcrime Jul 10 '18 at 0:47
  • 1
    $\begingroup$ Okay, the question is a bit old, but basically I wondered about this after I had finished a course on machine learning at some kind of app (Udemy or udacity). They talked about a NN and RL separately, but they did say one could use a NN as the approximate in RL. And that was what I was trying to do here. Reinforcement learning with a NN as approximate. Though at the time of writing the question, I was not aware of that exact termonology. $\endgroup$ – Yadeses Jul 10 '18 at 5:17
6
$\begingroup$

Backpropagation is used to update the weights in a neural network. A possible implementation is to map a (state, action)-pair to a Q-value. Gradient descent can be used as an optimizer to learn a policy for an agent.

Action selection

The action that yields the highest Q-value is chosen in a particular state. A neural network can be designed in many different ways. A few are listed below:

  • 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.
  • 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.
  • Another option is to construct a neural network that accepts as input the state. The output layer consists of K-units where K are the amount of possible actions. Each output unit is trained to return the Q-value for a particular action.

Update policy

As described earlier, we choose the action for which the Q-value is maximal. Once the action has been performed we end up in a new state. This state has a reward r associated with it. The following update rule is used to update the policy:

Update rule

One can incorporate this update function and use backpropagation to update the weights of the 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 formula you can see the discount factor. 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$
  • $\begingroup$ I am sorry I marked it as an answer first. 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:

Deep Q-Networks

Asynchronous Deep Reinforcement Learning

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.