I was going through an article where it is mentioned:

The Monte-Carlo methods require only knowledge base (history/past experiences)—sample sequences of (states, actions and rewards) from the interaction with the environment, and no actual model of the environment.

Aren't the model-based method dependent on past sequences? How is Monte Carlo is different than?


Model-based methods (such as value or policy iteration) use a model of the environment, which is usually represented as a Markov decision process. More specifically, the model consists of the transition and reward functions of the Markov decision process, which should represent the dynamics of the environment. For example, in policy iteration, the rewards (used to estimate the policy or value functions) are not the result of the interaction with the environment but given by the MDP (the model of the environment), so the decisions are made according to the reward function (and the transition function) of the MDP that represents the dynamics of the environment. Model-based methods are not (usually) dependent on past actions. For example, policy iteration converges to the optimal policy independently of the initial values of the states, the initial policy or the order of iteration through the states.

Monte Carlo methods do not use such a model (the MDP), even though the assumption that the environment can be represented as an MDP is (often implicitly) made (and the MDP might actually be available). In the case of Monte Carlo methods, all estimates are solely based on the interaction with the environment. In general, Monte Carlo methods are based on sampling (or random) operations. In the case of reinforcement learning, they sample the environment. The samples are the rewards that are obtained when certain actions are taken from certain states.

  • $\begingroup$ Thanks for the explanation. About the Monte Carlo(MC) not being MDP, is this always true? Or MC could be MDP as well? I am not sure if this makes sense, so far I had this intuition that everything is MDP. $\endgroup$ – tausif Jul 27 '19 at 13:52
  • $\begingroup$ @tausif: Everything in RL is based on MDP theory, including Monte Carlo control. The difference is that for model-based approaches you need the MDP or a decent proxy for it, that the agent can query directly (independently of having experience). There are broadly two types of model and two types of model-dependent RL - sampling models and distribution models - having the full MDP gives you a distribution model. I think the last paragraph here could make it clearer that there still is an assumed MDP for the Monte Carlo methods to work, just you do not need access to it $\endgroup$ – Neil Slater Jul 27 '19 at 13:57
  • $\begingroup$ @NeilSlater I would not say that everything in RL is based on MDP, unless by MDPs you mean all kinds of MDPs, including e.g. POMDPs. $\endgroup$ – nbro Jul 27 '19 at 14:07
  • $\begingroup$ @tausif As Neil stated, the common MC methods (often implicitly) assume that the environment can be represented as an MDP. However, this does not mean that they use or even know the MDP. $\endgroup$ – nbro Jul 27 '19 at 14:46

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.