1
$\begingroup$

This is another question I have on a q learning neural network being used to win tic tac toe, which is that im not sure i understand when to actually back propogate through the network.

What i am currently doing is when the program plays through the game, if the number of game sets recorded has reached the max amount, every time the program makes a move, it will pick a random game state from its memory and back propagate using that game state and reward. this will then continue every time the program makes a move as the replay memory will always be full from then on.

The association between rewards and game state and action from history, is that when a game has been completed, and the rewards have been calculated for each step, meaning that the total reward per step has been calculated, the method i use to calculate the reward is:

Q(s,a) += reward * gamma^(inverse position in game state)

in this case, gamma is a value predetermined to reduce the amount that the reward is taken into account the further you go back, and the inverse position in game state means that if there have been 5 total moves in a game, then the inverse position in game state when changing the reward for the first move would be 5, then for the second, 4, third 3 and so on. this just allows the reward to be taken less into account the earlier the move is.

Should this allow the program to learn correctly?

$\endgroup$
  • $\begingroup$ Thank you, I have put an edit in the question if that makes any more sense now. $\endgroup$ – Peter Jamieson Jan 14 '18 at 7:17
2
$\begingroup$

This update scheme:

Q(s,a) += reward * gamma^(inverse position in game state)

has a couple of problems:

  • You are - apparently - incrementing Q values rather than training them to a reference target. As a result, the estimate for Q will likely diverge, predicting total rewards that are impossibly high or low. Although in your case with a zero sum game and initial random moves, it may just random walk around zero for a long time first.

  • Ignoring the increment, the formula you are using is not from Q-learning, but effectively on policy Monte Carlo control, because you use the end-of-game sum of rewards as the Q value estimate. In theory, with a few tweaks this can be made to work, but it is a different algorithm than you say you want to learn.

It is worth clarifying a few related terms (you clearly know these already, but I want to make sure you have them separated in your understanding of the rest of the answer):

  • Reward. In RL, a reward (a real number) can be returned on every increment, after taking an action. The set of rewards is part of the problem definition. Often noted as $R$ or $r$.

  • Return (aka Utility). The sum of all - maybe discounted - rewards from a specific point. Often noted as $G$ or $U$.

  • Value, as in state value or action value. This is usually the expected return from a specific state or state, action pair. $Q(S_t, A_t)$ is the expected return when in state $S_t$ and taking action $A_t$. Note that using $Q$ does not make your algorithm Q-learning. The $Q$ action value is the basis for several RL algorithms.

Your formula reward * gamma^(inverse position in game state) gives you the Return, $G$ seen in a sampled training game, $G_t = \gamma^{T-t} R_T$ where $T$ is the last time step in the game. That's provided the game only has a single non-zero reward at the end - in your case that is true. So you could use it as a training example, and train your network with input $S_t, A_t$ and desired output of $G_t$ calculated in this way. That should work. However, this will only find the optimal policy if you decay the exploration parameter $\epsilon$ and also remove older history from your experience table (because the older history will estimate returns based on imperfect play).

Here is the usual way to use experience replay with Q learning:

  • When saving experience, store $S_t, A_t, R_{t+1}, S_{t+1}$ - note that means storing immediate Reward, not the Return (yes you will store a lot of zeroes). Also note you need to store the next state.

  • When you have enough experience to sample from, typically you do not learn from just one sample, but pick a minibatch size (e.g. 32) and train with that many each time. This helps with convergence.

  • For Q-learning, your TD target is $R_{t+1} + \gamma \text{max}_{a'} Q(S_{t+1}, a')$, and you bootstrap from your current predictions for Q, which means:

    • For each sample in the minibatch, you need to calculate the predicted Q value of all allowed actions from the next state $S_{t+1}$ - using the neutral network. Then use the maximum value from each state to calculate $\text{max}_{a'} Q(S_{t+1}, a')$.

    • Train your network on the minibatch for a single step of gradient descent, with NN inputs $[S_t, A_t]$ and training label of the TD target from each example.

    • Yes that means you use the same network to first predict and then learn from a formula based on those predictions. This can be a source of problems, so you may need to maintain two networks, one to predict and one that learns. Every few hundred updates, refresh the prediction network as a copy of the current learning network. This is quite common addition to experience replay (it is something that Deep Mind did for DQN), although may not be necessary in your case for a game as simple as Tic Tac Toe.

    • The TD target is a bootstrapped and biased estimate of expected $G$. The bias is a potential source of problems (you may read that using NNs with Q-learning is not stable, this is one of the reasons why). However, with the right precautions, such as experience replay, the bias will reduce as the system learns.

  • In case you are wondering, it is the use of both $S_t$ (as NN input) and $S_{t+1}$ (to calculate TD target) in the Q-learning algorithm, which effectively distributes the end-of-game reward back to the start of the game's Q value.

  • In your case (and in many episodic games), it should be fine to use no discount, i.e. $\gamma = 1$


From your previous question, you noted that you were training two competing agents. That does in fact cause a problem for experience replay. The trouble is that the next state you need to train against will be the state after the opponent has made a move. So the opponent is technically viewed as being part of the environment for each agent. The agent learns to beat the current opponent. However, if the opponent is also learning an improved strategy, then its behaviour will change, meaning your stored experiences are no longer valid (in technical terms, the environment is non-stationary, meaning a policy that is optimal at one time may become suboptimal later). Therefore, you will want to discard older experience relatively frequently, even using Q-learning, if you have two self-modifying agents.

$\endgroup$
  • $\begingroup$ OK thank you for all the info, just a couple things i would like to clarify that i may not understand properly, does this mean that maxa′Q(St+1,a′) is the largest q value found for a given state's possible actions? and do you re-calculate this for all minibatches if the neural network has just been trained with one minibatch as it will produce a slightly different value now. and so by using immediate reward + the best q value, that then becomes the target that i train the NN on? or in this case is the reward **Rt+1 **the sum of the rewards in the future as well? $\endgroup$ – Peter Jamieson Jan 14 '18 at 16:01
  • $\begingroup$ "does this mean that $\text{max}_{a′}Q(S_{t+1},a′)$ is the largest q value found for a given state's possible actions?" Yes. You have to run the network forward for all possible state, action pairs to calculate this - i.e. with one state ($S_{t+1}$) and all possible actions from that state. Yes you re-calculate this each time, you don't store it in the experience table. I used the terms as defined: $R_{t+1}$ is the immediate reward at time step $t+1$ - if I meant that you should take a sum, I would have shown the sum in the equation, or used $G_t$ or used the word "Return" instead of "Reward". $\endgroup$ – Neil Slater Jan 14 '18 at 16:06
  • $\begingroup$ ah ok brilliant, i will let you know if i come into any other info that i dont understand properly. Thank you again for all your help I will try to bug you less in the future :) $\endgroup$ – Peter Jamieson Jan 14 '18 at 16:10
  • $\begingroup$ Ok I'm Probably being an idiot here, but with maxa'Q(St+1,a') , you are calculating the q value for actions in the next state, but if the minibatch that you are calculating this for is the winning move, so the move has been won in this state and action, the next state would be being played into an already finished game, I feel like i am misinterpreting what you are saying and that the next action in the next state means something else, but what should the program do in this situation? $\endgroup$ – Peter Jamieson Jan 14 '18 at 19:15
  • 1
    $\begingroup$ @PeterJamieson: You are correct. It's a practical consideration when you implement this using neural nets. There is no action possible in the terminal state, and no future reward can be had. In that case you cannot use the NN - instead you should assume that $\text{max}_{a′}Q(S_{T},a') = 0$ and/or can shortcut the TD target to be equal to just $R_{T}$ i.e. the +1, 0 or -1 for win, draw, lose. Either way, you need extra logic to detect this end of game state for $S_{t+1}$, and handle it differently, because it cannot be bootstrapped via the NN. $\endgroup$ – Neil Slater Jan 14 '18 at 19:48

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.