2
$\begingroup$

I have been working on a tic-tac-toe assignment for my Robot Learning class. We were asked to program a tic-tac-toe game and assign; +1 if X wins, -1 if O wins and 0 it the game results with a draw. In part 1, we were told to use Q table and in part 2 we were told to replace the Q table with a Neural network as the functional approximator.

It is my understanding that both methods should be achieving the optimal policy, can you confirm or deny my understanding?

$\endgroup$
1
$\begingroup$

It is my understanding that both methods should be achieving the optimal policy, can you confirm or deny my understanding?

Yes, I would expect a neural network for Q Learning to find the optimal policy, provided it remains stable*. The value estimates might be slightly inaccurate, but the resulting policy should be completely optimal. That is because in tic tac toe, all the value estimates should be -1, 0 or +1, and the data is cleanly separated.

You should be able to get a neural network to learn the optimal Q table from the first experiment using supervised learning. In fact that would be a good test of whether your NN has capacity to learn that table.

* Neural networks added naively to Q-learning agents are often not stable. In fact that is so common a problem in scaling up RL agents that it has a name: "the deadly triad". This is generally not solved by elegant mathematical changes to the agent, but by some engineering tricks:

  • Experience replay. Save observations (S, A, R, S') and sample from this memory table later to train in mini-batches.

  • Alternating networks. Use an old frozen copy of the neural network to calculate $\text{max}_{a'} Q(S',a')$ for the TD target $R + \gamma\text{max}_{a'} Q(S',a')$

$\endgroup$

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.