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

Question

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?

Answer 1

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.

Answer 2

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.