2
$\begingroup$

In AlphaGo Zero, MCTS is used along with policy networks. Some sources say MCTS (or planning in general) increases the sample efficiency.

Assumed the transition model is known and the computational cost of interacting through planning is the same as interacting with the environment, I do not see the difference between playing many games versus playing a single game, but plan at each step.

Furthermore, given a problem with a known transition model, how do we know combining learning and tree search will likely be better than pure learning?

$\endgroup$
2
  • $\begingroup$ This post is not very clear and it's not clear to me what your question really is. In the title, you have a very general question, but in the body you have "given a problem with the known transition model, how do we know combining learning and tree search will likely be better than pure learning?", which seems to be more specific, but it's not clear what you mean by "learning". Moreover, you also say "I do not see the difference between playing many games versus playing a single game, but plan at each step.", which is not entirely clear. Do you know what "transition model" is used for? $\endgroup$ – nbro Nov 5 '20 at 11:44
  • $\begingroup$ Question for you: is the transition model known in go? Do you know what planning means in the context of RL? Try to answer these questions and then think about what your question really is. So, please, edit your post to ask only one question (and make the question in the title the same as the question in the body!). $\endgroup$ – nbro Nov 5 '20 at 11:46
1
$\begingroup$

Some sources say MCTS (or planning in general) increases the sample efficiency.

If we're thinking purely about experiments run in simulations, then I'd estimate there may be cases where a combination of pure learning + MCTS (or some other form of planning / model-based aspect) may be more efficient, and there may be different cases where only a single one of those techniques on its own may perform better. So then I wouldn't say this is always necessarily true.

Often though, when saying "sample efficiency", we would only count the steps actually taken in a "real" environment, but maybe not count steps taken in a lookahead search or planning algorithm. In pure simulations this may seem like a weird distinction to make, but it's more sensible when you consider that we often use simulations just because they're convenient ways to evaluate and compare new algorithms, but often not the end goal. Often, the end goal would be to apply something in the "real world", for example on a robot or something. In such a situation, collecting pure learning experiences can be very expensive (time-consuming, maybe also risky because the robot may fall over and break, etc.). But you may be able to also provide that robot with a learned model, or simulator, and have the robot use that to also run its own search or planning algorithms on an approximated version of the real world. This is a clear case where performing such is much faster and cheaper and less risky than collecting true experiences in the real world for pure RL.


Assumed the transition model is known and the computational cost of interacting through planning is the same as interacting with the environment, I do not see the difference between playing many games versus playing a single game, but plan at each step.

Jumping back to the case where we actually are working purely in simulation, and where there's no difference in computational cost between steps taken for pure learning vs. steps taken in search/planning, there absolutely are still some differences. If you run search, you use extra time and have temporary extra memory usage (which frees up again after completing your search algorithm) to make one really good decision in the "main" environment. You could view the steps taken in MCTS simulations as a form of learning as well, but they have a different purpose from the steps taken in a pure RL setting; these steps are taken with the sole goal of learning how to act well in the root state. All search time and memory usage is dedicated to that single decision. This can enable smarter decision-making than if you're going purely off of what you learned through pure RL, due to 1) focusing more effort on just a single decision, and 2) not being constrained by the capacity of your learning algorithm to actually learn a good decision (simple function approximators may simply not be capable of accurately representing strong policies, and more complex function approximators will take a huge amount of time to learn). This smarter decision-making thanks to search can in turn also improve the quality of the experience used by your pure RL component.


Finally, since you started out by mentioning AlphaGo Zero, I'd like to emphasise that AlphaGo Zero and similar approaches are typically used in multi-agent adversarial domains (like zero-sum games). Pure RL approaches for such multi-agent settings do exist, but there has been significantly less research towards them than pure RL approaches for single-agent settings. Most of these pure RL approaches are really only applicable to single-agent settings, and can easily have poor performance when applied to these kinds of multi-agent settings. Search algorithms like MCTS on the other hand are very well-established techniques in these adversarial domains like games, and the combination of them with learning approaches appears to allow even for learning approaches to be used which are not explicitly "aware" of the fact that they're operating in such a multi-agent domain.

$\endgroup$
2
  • $\begingroup$ Nice explanation. Thank you. Just a question: assume known transition model, are there circumstances in which pure RL have advantages over RL + search (other than the cases where pure RL already meets the expectation)? Wouldn't RL + search always have equal/better performances as it can put more effort on each single decision? $\endgroup$ – SmoothKen Nov 11 '20 at 19:29
  • $\begingroup$ @SmoothKen Sure. There's cases where you want to work with a pre-built simulator for instance, and that simulator may not have been designed in such a way that it easily exposes some of the functions you'd want to have for tree search (like copying/resetting states). This is the case with StarCraft / DOTA research for instance. There's also problems with continuous state and/or action spaces, for which there are pure RL techniques, but tree search is very difficult. And probably lots of other things that don't immediately come to mind right now for me $\endgroup$ – Dennis Soemers Nov 11 '20 at 19:43

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.