1
$\begingroup$

I am taking on deep Q-learning and I am stuck at understanding one particular thing. I have googled multiple deep Q-learning examples, but literally everyone posting tutorials uses a cart-pole game to present the algorithm and this game does not encounter similar issues to my problem.

The original Deepmind's Volodymyr Mnih's paper (https://www.cs.toronto.edu/~vmnih/docs/dqn.pdf) states the algorithm as follows:

The algorithm

I do not understand the part where $y_j$ is set.

In my problem, my Q function is an ANN with 64 inputs, one hidden layer of 48 neurons and 8 outputs. Each output represents an action (= I assume there are 8 actions available).

How do I set the $y_j$ however? Let's say I evaluate a state $s_{j+1}$ with my model Q and my output looks like this: $\begin{bmatrix} 0.2 & 0.4 & 0.2 & 0.1 & 0.02 & 0.02 & 0.02 & 0.1\end{bmatrix}$. Therefore $\text{max}_{a'}Q(s_{j+1},a';\theta) = 1$ (first element of the vector is indexed with 0).

State $s_{j+1}$ is non-terminal and current observed reward $r_j$ is 1. How do I set $y_j$? It should be of length 8, am I right?

$\endgroup$
1
$\begingroup$

In my problem, my Q function is an ANN with 64 inputs, one hidden layer of 48 neurons and 8 outputs. Each output represents an action (= I assume there are 8 actions available).

How do I set the $y_j$ however? Let's say I evaluate a state $s_{j+1}$ with my model Q and my output looks like this: $\begin{bmatrix} 0.2 & 0.4 & 0.2 & 0.1 & 0.02 & 0.02 & 0.02 & 0.1\end{bmatrix}$. Therefore $\text{max}_{a'}Q(s_{j+1},a';\theta) = 1$ (first element of the vector is indexed with 0).

That seems wrong, are you confusing max with argmax? $\text{max}_{a'}Q(\phi_{j+1},a';\theta) = 0.4$ in your example, using the notation of storing $\phi_{j+1} = \phi(s_{j+1})$ to match the pseudo-code (although you can use $s$ and $\phi$ almost interchangeably throughout in this case, $\phi_j$ is just the NN's input representation for $s_j$).

Looks like the document you are using also confuses max with argmax when setting $a_t$ - in that case it should be an argmax.

State $s_{j+1}$ is non-terminal and current observed reward $r_j$ is 1. How do I set $y_j$? It should be of length 8, am I right?

Your training vector needs to be of length 8, but it is only related to $y_j$, it is not the same as it. $y_j$ is the estimate for the target of a single $Q(\phi_j, a_j)$ value, whilst your network outputs 8 different action values $\begin{bmatrix} Q(\phi_j, a_0) & Q(\phi_j, a_1) & Q(\phi_j, a_2) & . . . \end{bmatrix}$. The Q-learning algorithm itself is not designed around the structure of neural networks (or any specific approximator). Instead you have to make the neural network training fit to what Q-learning does.

$y_j = 1 + 0.9 * 0.4 = 1.36$ assuming $\gamma = 0.9$ and the non-terminal result as you said. It is a single scalar value, and it relates to the target output for $a_j$ only. The other 7 target values in your vector, you do not have training values for . . .

So, you know nothing about the actions that were not taken. You have two basic choices:

  • Alter the loss function or gradient calculations so that the only important output for training purposes is that for $a_j$. Assuming $a_j$ was 5 for instance then your training target could then be $\begin{bmatrix} 0 & 0 & 0 & 0 & 0 & 1.36 & 0 & 0\end{bmatrix}$. Whether or not you can do this depends on your NN framework, but this would be the most efficient approach.

  • Run the network forward for $Q(\phi_j, *)$ to get the current output vector, and adjust the value of just $a_j$ output to equal $y_j$ for training. Again assuming $a_j$ was 5 for instance, and that you ran the network forward to get the outputs $\begin{bmatrix} 1.1 & 2.1 & 1.5 & 0.3 & 0.9 & 1.7 & 1.3 & 1.4\end{bmatrix}$ training target could then be $\begin{bmatrix}1.1 & 2.1 & 1.5 & 0.3 & 0.9 & 1.36 & 1.3 & 1.4\end{bmatrix}$. This has the advantage of being simple to drop in to standard NN frameworks whilst not messing around with custom loss functions or gradient functions.

$\endgroup$
1
$\begingroup$

No, $y_j$ is not a vector of length 8. It is a single value.

$y_j$ describes the Q-value that agent has got by performing action $a_t$ in the state $s_t$.

Note : If you only want answer of your question, you can directly look at the last part of the answer. I've written initial part for explaining Deep Q Leaning algorithm.

So, to describe the entire scenario,

Agent is currently in state $s_t$ (State $s_t$ is one of many combinations possible from your 64 input neurons). Now Agent has to select an action from given state $s_t$. Here the situation is called explore-exploit dilemma. By selecting exploitation, Agent chooses best action it has learnt, and by choosing exploration, Agent randomly pick any action out of 8 possible actions. This action is $a_t$. By performing this action $a_t$ in a state $s_t$, Agent receives a reward $r_t$ from the environment and moves to the next step $s_t$$_+$$_1$. This is one step of RL process.

Now, based on this move we need to update Q-value. $y_t$ is the Q-value as mentioned earlier, which stores Q-value of the action $a_t$ in state $s_t$. We are using Bellman equation for updating Q-value.

As shown in the algorithm, if next state(means $s_t$$_+$$_1$) is a terminal state than Q-value is simply the environment reward $r_t$. But if it is a non-terminal state, then according to Bellman equation, we need to choose best action from all the possible actions in next state $s_t$$_+$$_1$(This is the meaning of that equation). For doing this, we need to supply state $s_t$$_+$$_1$ as the input in ANN ($s_t$$_+$$_1$ is again one of many combinations possible from your 64 input neurons), ANN will give values for all 8 actions, we need to pick highest value from those 8 values. Then multiply this highest value with discount factor gamma. And finally add environment reward $r_t$ in it. This gives the value for $y_t$ for non-terminal state. Remember this Q-value $y_t$ is for only the action $a_t$ in state $s_t$, and it is a single value, not a vector.

So, Finally to answer your question,

You have Q-values of all the 8 actions from state $s_t$$_+$$_1$ , which are

[0.2 0.4 0.2 0.1 0.02 0.02 0.02 0.1]

As per the Bellman equation, pick highest value, which is 0.4.

So,

$y_j$ = $r_j$ + gamma * $\text{max}_{a'}Q(s_{j+1},a';\theta)$

$y_j$ = 1 + gamma * 0.4 (gamma value of your choice such that 0= < gamma <= 1)

Note : Please treat $y_j$ and $y_t$ same throughout the answer.

$\endgroup$
  • $\begingroup$ Thank you for your extensive reply. It has helped me in understanding. But having $y_j$ as a single value, I am now confused with performing the gradient descent. My ANN representing the Q function should then be a different ANN than the one which selects the action? I thought it is the same one. So I have to have a separate ANN which will take state and action as inputs and outputs single number representing the Q value? $\endgroup$ – Erhan Mar 23 '18 at 22:00
  • $\begingroup$ My initial idea was to train the model on the minibatch sampled from my replay memory as follows (using Keras, but one can treat the following line as a pseudocode as well): model.fit(states, targets) where target is $y_j$. I guess this is really not the way to go. $\endgroup$ – Erhan Mar 23 '18 at 22:16
  • 1
    $\begingroup$ When we give state $s_t$ as an input in ANN, it gives Q-values of all possible 8 actions. We select any one action $a_t$(using exploration/exploitation) out of 8 possible actions. And now for the chosen action $a_t$, we calculate theoretical Q-value(Using Bellman equation). So, gradient descent calculates loss. So, loss is calculated based for action $a_t$ only, for all the other actions we take loss as 0, because that action isn't selected.So, loss is MSE between $y_j$ and actual Q-value for that action(O/P of ANN). Network is update using this loss only, for all remaining actions loss is 0. $\endgroup$ – Sanjay Chandlekar Mar 24 '18 at 3:02
  • $\begingroup$ As the answer of your first comment, only one ANN is enough to do this. ANN will take only states as the I/P and will O/P Q-values of all actions. $\endgroup$ – Sanjay Chandlekar Mar 24 '18 at 3:08
  • $\begingroup$ I give you one example for clearing your doubt. Suppose for I/P state $s_t$, we got following output from ANN, which is Q-values of all actions [0.2 0.4 0.2 0.1 0.02 0.02 0.02 0.1]. Now, suppose action 3 is selected (Q-value 0.1). We calculate $y_t$ for this action as mentioned in the answer, suppose that value is 1.2. So, for this state your expected O/P is [0.2 0.4 0.2 1.2 0.02 0.02 0.02 0.1], and you got [0.2 0.4 0.2 0.1 0.02 0.02 0.02 0.1] from ANN. model.train_on_batch(ip, trgt)/model.fit(ip/trgt) calculates MSE between this two vectors internally and update the ANN network. $\endgroup$ – Sanjay Chandlekar Mar 24 '18 at 3:20

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.