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.
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.
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:
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
diff = learningRate * (reward - old_Q)
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.