1
$\begingroup$

I've been unsure about a principle of Q-Learning, I was hoping someone could clear it up.

When a new state is encountered, and thus there are no existing Q values, and that the algorithm decides to exploit, and not explore, how is the move chosen, since all the values are 0?

Is it chosen randomly? This intuitively would make sense, since after this, the state-move pair would have a value and thus the matrix would get filled up throughout the iterations. But I just want to make sure I understand this correctly...

Thanks

$\endgroup$
3
$\begingroup$

It depends on the implementation of the software package that you are using. If you call a function that returns the maximum value and all values are the same then it might return the value at first index or some other one. The point is it doesn't matter which action is chosen since all of them are the best at the same time. So it's basically random but you should treat it as if you are trying to pick the best action.

$\endgroup$
  • $\begingroup$ That's precisely the problem I'm having. Switching from an implementation where an random Q value is selected to one where the code selects the first one when they are all 0 drastically alters my agent's performance. Racking my brain trying to understand where this could come from... $\endgroup$ – Pete Apr 25 at 15:58
  • $\begingroup$ this is such a small thing to consider it's basically irrelevant since it only happens the first time you enter the state, it shouldn't affect the final performance. There must be a deeper reason why your performance differs so much. $\endgroup$ – Brale_ Apr 25 at 16:12
  • $\begingroup$ Yes I think there a few issues here. The main one is the size of the state space ($10^{12}$), although the number of states that are likely to come about is much smaller. Another issue that the agent is trained against a Minimax AI, which always follows the same path, and although it is able to win against it most times, a human player is not guaranteed to play the way a Minimax algorithm responds to changes in state. Perhaps unsuitable hyperparameters? Not sure... Thanks for the input though. $\endgroup$ – Pete Apr 25 at 16:20
  • $\begingroup$ Oh, so you are training on minimax and testing against human ? If that's the case it is possible that the agent overfits minimax player since MM player will usually choose the same move in the same position. When you play against human it is possible that agent visits states never met before (since there are so many states). If that happens behaviour is undefined since the agent didn't learn anything about those states before, you might get lucky or not. Have you considered "pretraining" it on a random agent ? Also $10^{12}$ states is quite a lot for tabular Q-learning to solve. $\endgroup$ – Brale_ Apr 25 at 16:37
  • $\begingroup$ Precisely. Perhaps I should not be testing against human player. I have tried training the agent against a random player, with around 500 000 games, reaching a win rate of about 70% against the random player. However, winning against a human player seems to be the real challenge. Perhaps I will limit my thesis to studying the correlations between MM agent and learning agent without taking into account human players. Since the result vs AI and random are quite good. The state space is indeed quite big. I used a different data structure, a dictionary with dynamically generated entries though. $\endgroup$ – Pete Apr 25 at 16: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.