3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Could you clarify exactly what you are referring to when you say "Monte Carlo Search Algorithm"? Monte-Carlo is a very general concept, not one specific algorithm. Monte-Carlo Tree Search is more specific, that's one algorithm (or kind of a family of very closely related algorithms). I suspect you're confusing traditional model-free RL approaches based on Monte Carlo Returns (not search) with MCTS... but it would be easier to tell for sure if you mention in which textbook (and where in the textbook) you read that statement $\endgroup$ – Dennis Soemers Jan 30 at 9:04
  • 1
    $\begingroup$ Thanks for the reply Dennis, I meant MCTS, because this is what occurred to me when reading the explanation of of Alphago. Because from what I understand Alphago improve the search by also using policy and value network. I think MCTS without policy and value network in Go game is also a model free RL approaches ? and if that is the case i am still confuse about knowing the reward and transition during rollout .....*I editted the question to make it clearer $\endgroup$ – user21872 Jan 30 at 9:40
  • $\begingroup$ I see... I'll likely write a more detailed answer somewhere later today (may take a while) if noone else does in the meantime. But my very short answer would be: MCTS often isn't viewed as an RL algorithm at all, though sometimes it may be (see answers to ai.stackexchange.com/q/7589/1641). If you take that view of it being an RL algorithm... I would say that it is a model-free RL algorithm, but one that does require a model of the environment because you don't extract a reusable policy from it, but run it over and over again for every state you encounter (e.g. every turn in a game). $\endgroup$ – Dennis Soemers Jan 30 at 9:46
  • $\begingroup$ I see, thanks for the link. I think most of my confusion stems from MCTS sort of like estimating the value of the nodes which confused me with RL solution approach. So maybe this means that MCTS cant function without a sort of mechanism telling which states to go next upon taking an action or branching (I would assume a sort of transition model). But this is clear if I separate: agent learning & pure tree search algorithm (not exclusively apply for agent to learn value). Now this makes sense. Anyway I look forward to read your detailed answer too. Thanks ! $\endgroup$ – user21872 Jan 30 at 10:01
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is the common-sense answer, I guess my answer is the tinfoil-hat answer :D $\endgroup$ – Dennis Soemers Jan 30 at 18:01
  • $\begingroup$ Thanks Neil for the answer. Both you and Dennis helps me understand better on model free and model based RL. Of course my confusion is mistaking MCTS as RL solution algorithm instead of search algorithm. Merging them is wht makes things interesting like in Alphago. Thanks ! $\endgroup$ – user21872 Jan 31 at 20:05
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for the answer Dennis. Sorry for the delay I had problems accessing my account. The question started out with my confusion on MCTS and the MC approach for Q learning, but now im getting new insights and better understanding on RL. Thanks ! $\endgroup$ – user21872 Jan 31 at 19:59

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.