Rollout algorithm like Monte Carlo search suggest model based reinforcement learning?

Question

From what I understand, Monte Carlo Tree Search Algorithm is a solution algorithm for model free reinforcement learning (RL).

Model free RL means agent doesnt know the transition and reward model. Thus for it to know which next state it will observe and next reward it will get is for the agent to actually perform an action.

my question is: if that is the case, then how come the agent knows which state it will observe during the rollout, since rollout is just a simulation, and the agent never actually perform that action ? (it never really interact with the environment: e.g it never really move the piece in a Go game during rollout or look ahead, thus cannot observed anything).

It can only assume observing anything when not actually interacting with environment (during simulation) if it knows the transition model as I understand it. The same arguments goes for the rewards during rollout/ simulation.

in this case, doesnt rollout in Monte Carlo Tree Search algorithm suggests that the agent knows the transition model and reward model and thus a solution algorithm for model based reinforcement learning and not model free reinforcement learning ?

** it makes sense in Alphago, since the agent is trained to estimate what it would observed. but MCTS (without policy and value netwrok) method assumes that agent knows what it would observed even though no additional training is included.

Answer 1

Whether or not MCTS is even a Reinforcement Learning algorithm at all may be up for debate, but let's assume that we view it as an RL algorithm here.

For practical purposes, MCTS really should be considered to be a Model-Based method. Below, I'm going to describe how you could view it as a Model-Free RL approach in some way... and then wrap back to why that viewpoint isn't really often useful in practice.

---

More specifically, following this paper, we'll think of an MCTS search process as a value-based RL algorithm (it learns estimates of a value function, very much like Sarsa, $Q$-learning, etc.), which limits itself to learning values for the states that it chooses to represent by nodes in the search tree (this set of states that it chooses to represent gradually grows over time during the search process).

Unlike traditional RL approaches, such an MCTS process doesn't really result in a policy or an exhaustive / generalizable value function estimator that can be extracted after the "training" process and re-used in many different states afterwards. We normally play a move after running MCTS, and then discard everything and start over again for the next move (maybe we'll keep a relevant part of the search tree and reuse that, but that's a minor detail... we certainly won't be able to re-use our search results in another match/game/episode).

The MCTS search process itself can be viewed as a Model-Free RL approach; every iteration of the search can be viewed as an actual episode of an "agent" that is collecting experience in a model-free manner in a "real" environment (but not as real as the game for which we're running the complete search process), where this "internal agent" first follows the Selection Policy for a while (e.g. UCB1), and then a Play-out policy for the remainder of the episode (e.g. uniform random).

This "internal" agent "inside" the MCTS iterations could be viewed as learning from a model-free RL process. The main problem with this view in practice is that, because MCTS "decides" to have a laser-like focus on a relatively small subset of states (around the root node), this process really only leads to something useful being learned for that state in the root node (and possibly some of the closest children/grandchildren/etc.). We don't really learn something that can easily be re-used in the future in MCTS. What this means in practice is that we have to be able to re-run the complete "Reinforcement Learning process" (or search) whenever we need to make a decision (i.e. every turn in a turn-based game).

That is feasible if you have a simulator, or model of the environment, in which you can do the learning... but then we really get back to actually have a model-based approach.

---

Fun fact: if you like to take the viewpoint of MCTS as a Model-Free RL approach, you could also turn that into a Model-Based approach again by incorporating additional forms of planning/search "inside" the MCTS iterations. For example, you can run little instances of MiniMax inside every MCTS iteration, and I suppose that would turn the approach into a Model-Based approach again even in this viewpoint.

Answer 2

From what I understand, Monte Carlo Tree Search Algorithm is a solution algorithm for model free reinforcement learning (RL).

Monte Carlo Tree Search is a planning algorithm. It can be considered part of RL, in a similar way to e.g. Dyna-Q.

As a planning algorithm MCTS does need access to a model of the environment. Specifically it requires a sampling model, i.e. a model that can accept a state and action, then return a single next state and reward with the same probabilities as the target system. The alternative model, used by other RL techniques such as Value Iteration, is a distribution model which provides the full distribution of probabilities for rewards and next states.

if that is the case, then how come the agent knows which state it will observe during the rollout, since rollout is just a simulation, and the agent never actually perform that action ?

It is not the case. The agent knows what it will observe during the simulation because the simulation is a sampling model.

In this case, doesnt rollout in Monte Carlo Tree Search algorithm suggests that the agent knows the transition model and reward model and thus a solution algorithm for model based reinforcement learning and not model free reinforcement learning ?

Yes. This is how most planning algorithms work.

The simulation can be driven purely by sampling from previous experience, which is how Dyna-Q works*. I would still consider that a model-based approach, and its success depends a lot on how well such a model can be learned. In many cases, variance due to errors in the learned model adversely affects learning. So MCTS works best in environments that can be accurately sampled, because they are strongly rules-driven. For example, board games.

---

* Functionally DynaQ is almost identical to experience replay. So much so, that whether you consider it a planning algorithm or experience replay added to basic Q learning is more a matter of how you present the design of the learning agent - e.g. perhaps a designer wants to focus on the model-learning side more, so has code that explicitly represents the learned model.