Optimal RL function approximation for TicTacToe game

Question

I modeled the TicTacToe game as a RL problem - with an environment and an agent.

At first I made an "Exact" agent - using the SARSA algorithm, I saved every unique state, and chose the best (available) action given that state. I made 2 agents learn by competing against each other.

The agents learned fast - it took only 30k games for them to reach a tie stand-off. And the agent clearly knew how to play the game.

I then tried to use function approximation instead of saving the exact state. My function was a FF-NN. My 1st (working) architecture was 9 (inputs) x 36 x 36 x 9 (actions). I used the semi-gradient 1-step SARSA. The agents took much longer time to learn. After about 50k games they were still less good than the exact agent. I then made a stand off between the Exact and the NN agent - the exact agent won 1721 games from 10k, the rest were tied. Which is not bad.

I then tried reducing the number of units in the hidden layers to 12, but didn't get good results (even after playing for 500k+ games total, tweaking stuff). I also tried playing with convolution architectures, again - not getting anywhere.

I am wondering if there's some optimal function approximation solution that can get as-good of results as the exact agent. TicTacToe doesn't seem like such a hard problem for me.

Conceptually I think there should be much less complexity involved in solving it then can be expressed in a 9x36x36x9 network. Am I wrong, and it's just an illusion of simplicity? Or are there better ways? Maybe modeling the problem differently?

Answer 1

I think you can break this problem down into two parts to try and find the solution.

1. Can the neural network model the desired function?

Take the tabular function you have learned in the exact agent, and treat it as training data for the neural network model, using the same loss function and other hyperparameters as you intend to use when the NN is being used online inside the RL inner loops.

You can answer two related questions with this:

• Does the loss reduce down to a low value after a suitable number of epochs? If so, then the NN has capacity to learn and can learn fast enough. If not, you need to look at the hyperparameters of the NN.

• Does the trained NN play well against the exact agent? Ideally it plays the same, but it is possible that even though the loss is low, one or two key values in the function are compromised, meaning it still loses. I am not entirely sure what you would do in this case, but either try changing the hyperparameters to increase the capacity of the NN, or try augmenting the data so that there are more examples of the "difficult" action values to learn, to see if the issue is something that can be solved in learning.

Probably you will find your NN architecture is good, or only requires minor changes to become useful. The more likely issues are in next section.

2. Is the RL framework set up correctly for function approximation?

It is quite hard to get this right. Bootstrapping value based methods can easily become unstable if converted naively from tabular to function approximation approaches. Some variants are moderately stable - most stable would probably be Monte Carlo approaches.

If you don't want to use Monte Carlo control, then the answer here would be to take ideas from DQN used originally to play Atari games:

• Don't learn online. Store transitions in an experience replay table - store $(s, a, r, s', done)$ tuples where $done$ is true if $s'$ is a terminal state - and sample a minibatch from it on every step. Reconstruct the bootstrap estimates of value functions to train from each time you sample, don't store and re-use the estimate from the time the action was taken.

• Optionally use two value estimators - the current learning one, used to select plays and which is updated on each step, and a "target" one used to calculate TD targets. Update the target network by cloning the learning network every N steps (e.g. every 100 games).

• To avoid figuring out hyperparameters for SARSA epsilon decay, I suggest use one-step Q learning. Also one issue you may be facing with SARSA combined epsilon decay is "catastrophic forgetting" where the agent gets good, starts to train itself only on play examples by good players, and forgets the values of states that it has not seen in the training data for many time steps. With Q learning you can avoid that by having a relatively high minimum epsilon e.g. 0.1.

In fact with TicTacToe learning through self-play, you can get away with $\epsilon = 1$ and Q learning should still work - i.e. it can learn optimal play by observing random self-play. This should apply equally tabular and function approximation agents. It doesn't scale to more complex games where random play would take too long to discover optimal strategies.