I'm running a q-learning agent in tic tac toe against a minimax agent and measuring the tie rate (since you can never win against minimax). When I run 10,000 training games, I've found that there seem to be two drastically different patterns: 1) Q-learning agent has a bad start and ends up with an overall tie rate of between 0.06 and 0.09. 2) Q-learning agent improves consistently and has an overall tie rate of around 0.7.
Why is this happening? Is the q-learning algorithm getting stuck in some local optima? Is this normal behavior for q-learning?