Q learning Neural network Tic tac toe - When to train net

Question

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?

Answer 1

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.