4
$\begingroup$

In the previous research, in 2015, Deep Q-Learning shows its great performance on single player Atari Games. But why do AlphaGo's researchers use CNN + MCTS instead of Deep Q-Learning? is that because Deep Q-Learning somehow is not suitable for Go?

$\endgroup$
5
+50
$\begingroup$

$Q$-learning (and also its deep variant, and most of the other well-known reinforcement learning algorithms) are inherently learning approaches for single-agent environments. The entire problem setting that these algorithms are developed for (Markov decision processes, or MDPs) is always framed in terms of a single agent situated in some environment, where that agent can take actions that have some level of influence over the states that they lead to, and rewards may be observed.

If you have a problem that is, in reality, a multi-agent environment, there is a way to translate this environment to a single-agent setting; you simply have to assume that all other agents (i.e. your opponent in Go) are an inherent part of "the world" or "the environment", and that all the states in which these other agents make moves are not really states (not visible to your agent), but just intermediate steps where these part-of-the-environment-agents cause the environment to change and, as a result, create state transitions.

The primary issue with this approach is; we still need to model the decision-making of these agents in order to implement this new view of "the world", where our opponents are really a part of the world. Whatever implementation we give them, that is what our single-agent RL algorithm will learn to play against. We can just implement our opponents to be random agents, and run a single-agent RL algorithm like DQN, and then we will likely learn to play well against random agents. We'll probably still be very bad against strong opponents though. If we want to use a single-agent RL algorithm to learn to play well against strong opponents, we need to have an implementation for those strong opponents first. But if we already have that... why even bother with learning at all? We've already got the strong Go player, so we're already done and don't need to learn!

MCTS is a tree search algorithm, one that actively takes into account the fact that there is an opponent with opposing goals, and tries to model the choices that this opponent can make, and can do so better the more computation time we give it. This algorithm, and learning approaches built around it, are inherently designed to tackle the multi-agent setting (with agents having opposing goals).

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for the answer! I also thought like that but I don't have much theoretical basis, so I can't speak much. But your answer is very clear and has good intuition! $\endgroup$ – malioboro Jul 12 at 5:02
3
$\begingroup$

Deep Q Learning is a model-free algorithm. In the case of Go (and chess for that matter) the model of the game is very simple and deterministic. It's a perfect information game, so it's trivial to predict the next state given your current state and action (this is the model). They take advantage of this with MCTS to speed up training. I suppose Deep Q Learning would also work, but it would be at a huge disadvantage.

| improve this answer | |
$\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.