Why is tree search/planning used in reinforcement learning?
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 &quot;sample efficiency&quot;, we would only count the steps actually taken in a &quot;real&quot; 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 &quot;real world&quot;, 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 &quot;main&quot; 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 &quot;aware&quot; of the fact that they're operating in such a multi-agent domain.