4
$\begingroup$

I'm trying to implement Q-learning to train an AI bot to play Pokemon battles. Since there is a large state space (corresponding to all possible states a battle can have in between moves), I can't use tables, so I'm using (nonlinear) function approximation. I found this formula to update the weights in a NN for Q, but I don't understand why it works:

$$ \theta_i \leftarrow \theta_i + \alpha \left( r + \beta \max_{a'} \hat{Q}(s', a') - \hat{Q}(s, a) \right) \frac{\partial \hat{Q}(s, a)}{\partial \theta_i} $$

It seems related to backpropogation but I'm not sure how it's supposed to work. For example, there isn't an error function we're trying to minimize; the only feedback we get from the environment is the reward, and I don't see how updating the weights in this way is supposed to result in a closer approximation to the actual $Q(s, a)$. Can someone please translate this intuitively, or provide a proof of convergence? Thanks.

$\endgroup$
6
+50
$\begingroup$

The update formula in single-step Q learning is directly related to the Bellman equation for optimal value function:

$$q(s,a) = \sum_{s',r}p(s',r|s,a)(r + \gamma \max_{a'}q(s',a'))$$

(NB the $\gamma$ here is the same as the $\beta$ in your update, it is the discount factor)

This applies to any finite Markov decision process, and can be derived simply from definitions of action value Q (expected return following a specific state, action pair) state transition and policy. The policy improvement theorem explains how this optimal equality can be approached by getting accurate estimates of Q under any policy, then altering the policy to be greedy with respect to the current Q values. Q learning combines evaluation and improvement steps, and is a stochastic sampling version of value iteration that approaches this optimal equality for all states and actions in expectation.

When you add function approximation, and optimise by gradient descent, then there is an implied loss function for the approximation:

$$\overline{VE} = \sum_{s \in \mathcal{S}} \sum_{a \in \mathcal{A}(s)} \mu(s,a)(q(s,a) - \hat{q}(s,a,\theta))^2$$

Where $\mu(s,a)$ is the relative proportion of time steps sampled in state $s$ and take action $a$, according to the behaviour policy (typically $\epsilon$-greedy policy over Q values). This proportion changes over time as the policy improves, so the distribution is non-stationary.

If you take the gradient w.r.t. $\theta$ for the above equation, you get:

$$\nabla \overline{VE} = 2 \sum_{s \in \mathcal{S}} \sum_{a \in \mathcal{A}(s)} \mu(s,a)(\hat{q}(s,a,\theta) - q(s,a))\nabla \hat{q}(s,a,\theta)$$

Your update rule is stochastic gradient descent based on this, shown for one element of $\theta$.

Although this is the loss function that you are working to due to the update in Q learning, it is not necessarily the best loss function you could have. That is still a matter of research, and it is not clear how much weight it is worth putting on $s,a$ pairs that are not visited due to the current behaviour policy for instance, in order to avoid issues such as catastrophic forgetting.

In addition, you don't have access to the true value of $q(s,a)$ and are using the bootstrap estimate $r + \gamma \max_{a'}\hat{q}(s',a', \theta)$ for it instead.

Finally, the bootstrap value or TD Target is based on your estimator, which depends on $\theta$, but that is not being included in the gradient. That makes DQN a semi-gradient method.

It seems related to backpropogation but I'm not sure how it's supposed to work.

There is no back propagation in the formula. However, if you have a neural network, you will need to work out the gradient for all $\theta$ at specific value of $\hat{q}(s, a, \theta)$ and use that. At that point, this is the same update rule as regression with the TD Target as the label, so you can just create $x = (s,a)$ and $y$ = (TD Target, calculated anew each time) training pairs, updating a NN with MSE loss as if it were part of a supervised learning problem.

$\endgroup$
0

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.