1
$\begingroup$

Consider this slide from a Stanford lecture on reinforcement learning. It states that a model is

the agent's representation of how the world changes in response to the agent's action.

I've been experimenting with Q-learning for simple problems such as OpenAI's FrozenLake and Mountain Car, which both are amenable to the Q-learning framework (the latter upon discretization). I consider the topologies of the lake and the mountain to be the "worlds" (aka. environments) in the two cases, respectively.

Q-learning is said to be "model-free". Given the two examples above, is it because neither the lake's topology nor that of the mountain are changed by the actions taken?

$\endgroup$
  • 1
    $\begingroup$ Let me know if the answers to this question answer your question. If your question is not "What does model-free mean?", then, please, edit your post to clarify what your question really is. $\endgroup$ – nbro Sep 25 at 10:56
  • $\begingroup$ @nbro there is some overlap, but my question is much more concrete and dumbed-down: E.g., keeping in mind a specific example such as the car in the MountainCar problem, how can we tell that it is model-free? What would be the model in this case (e.g., a representation of the gravitational potential of the mountain)? As far as I see it, the Q-table that the agent (i.e. car) populates is an (implicit) representation of how the world changes, thereby making it model-based as per the definition. $\endgroup$ – Tfovid Sep 26 at 11:13
  • $\begingroup$ If you understand the answers to the duplicate question, you will understand what a "model" is and, therefore, conclude that a value function is not a model (or what we mean by "model" in RL). The model is the transition matrix (or function) of the MDP. If you have or use it, your algorithm is model-based, otherwise, it is not. For your algorithm to be model-based in MountainCar, you need to learn or know this transition matrix. If you don't know what a transition matrix is, I suggest that you look at the definition of an MDP. $\endgroup$ – nbro Sep 26 at 11:30
  • $\begingroup$ Please, edit your post to clarify your actual question. If you are asking "what is a model in reinforcement learning", then ask that. And please explain how your question is different than the linked one. $\endgroup$ – nbro Sep 26 at 11:33
4
$\begingroup$

Q-learning is said to be "model-free". Given the two examples above, is it because neither the lake's topology nor that of the mountain are changed by the actions taken?

No. That's not why Q-learning is model-free. Q-learning assumes that the underlying environment (FrozenLake or MountainCar, for example) can be modelled as a Markov decision process (MDP), which is a mathematical model that describes problems where decisions/actions can be taken and the outcomes of those decisions are at least partially stochastic (or random). More precisely, an MDP is composed of

  • A set of actions $A$ (that the RL agent can take); for example, up and down, in some grid world
  • A set of states $S$ (where the RL agent can be);
  • A transition function $p(s_{t+1} = s' \mid s_{t} = s , a_t = a)$ (aka the model), which represents the probability of going to state $s'$ at time step $t+1$, given that at time step $t$ the RL agent is in the state $s$ and takes action $a$.
  • A reward function $r(s, a, s')$ (sometimes also denoted as $r(s)$ or $r(s, s')$, although these can have different semantics); the reward function gives the reward (or reinforcement) to the RL agent when it takes an action in a certain state and moves to another state; the reward function can also be included in the transition function, i.e., often you will also see $p(s_{t+1} = s', r_{t+1} = r \mid s_{t} = s , a_t = a)$, and this is the model: this is what we mean by model in reinforcement learning, it's this $p$ (which is a probability distribution)!

A model-free algorithm is any algorithm that does not use or estimate this $p$. Q-learning, if you look at its pseudocode, does not make use of this model. Q-learning estimates the value function $q(s, a)$ by interacting with the environment (taking actions and receiving rewards), but, meanwhile, it does not know or keep track of the dynamics (i.e. $p$) of the environment, and that's why it's model-free.

And, no, the value function is not what we mean by "model" in reinforcement learning. The value function is, as the name suggests, a function.

How does one know that a problem is "model-free" in reinforcement learning?

A problem is not model-free or model-based. An algorithm is model-free or model-based. Again, a model-free algorithm does not use or estimate $p$, a model-based one uses (and/or estimates) it.

Given the two examples above, is it because neither the lake's topology nor that of the mountain are changed by the actions taken?

No. As stated in the other answer, you could apply the model-based algorithm Dyna-Q to these environments.

| improve this answer | |
$\endgroup$
1
$\begingroup$

A reinforcement learning algorithm is considered model based if it uses estimates of the environments dynamics to help learn. For instance, in the Tabular Dyna-Q algorithm, every time you visit a state action tuple you store in a look-up table the reward received and the next state transitioned to, and after every execution of an action you loop $n$ times to further back up your $Q$ table using these stored model values from the look-up table. I will attach a copy of the pseudo-code for an algorithm at the bottom of this post.

Algorithms like vanilla $Q$-learning are model free because they don't require a model of the environment to learn.

enter image description here

| improve this answer | |
$\endgroup$
  • $\begingroup$ This answer is correct and I would upvote it, but if this question is a duplicate of this one, I think it's better you answer there (although there are already many answers there, but none of them mentions Dyna-Q, apparently), because this will probably be closed as a duplicate of that one (I am just waiting for the OP's feedback). $\endgroup$ – nbro Sep 25 at 21:30
  • $\begingroup$ My question is more about the physical intuition of what the model is, hence my specific reference to the concrete examples of FrozenLake and MountainCar. If a model is "the agent's representation of how the world changes in response to the agent's action", then a Q-learning approach to MountainCar would be considered model-free because the car (i.e. the agent) does not have a representation of what the gravitational potential of the mountain is? $\endgroup$ – Tfovid Sep 26 at 11:09

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.