What's the difference between model-free and model-based reinforcement learning?
It seems to me that any model-free learner, learning through trial and error, could be reframed as model-based. In that case, when would model-free learners be appropriate?
What's the difference between model-free and model-based reinforcement learning?
In Reinforcement Learning, the terms "model-based" and "model-free" do not refer to the use of a neural network or other statistical learning model to predict values, or even to predict next state (although the latter may be used as part of a model-based algorithm and be called a "model" regardless of whether the algorithm is model-based or model-free).
Instead, the term refers strictly as to whether, whilst during learning or acting, the agent uses predictions of the environment response. The agent can use a single prediction from the model of next reward and next state (a sample), or it can ask the model for the expected next reward, or the full distribution of next states and next rewards. These predictions can be provided entirely outside of the learning agent - e.g. by computer code that understands the rules of a dice or board game. Or they can be learned by the agent, in which case they will be approximate.
Just because there is a model of the environment implemented, does not mean that a RL agent is "model-based". To qualify as "model-based", the learning algorithms have to explicitly reference the model:
Algorithms that purely sample from experience such as Monte Carlo Control, SARSA, Q-learning, Actor-Critic are "model free" RL algorithms. They rely on real samples from the environment and never use generated predictions of next state and next reward to alter behaviour (although they might sample from experience memory, which is close to being a model).
The archetypical model-based algorithms are Dynamic Programming (Policy Iteration and Value Iteration) - these all use the model's predictions or distributions of next state and reward in order to calculate optimal actions. Specifically in Dynamic Programming, the model must provide state transition probabilities, and expected reward from any state, action pair. Note this is rarely a learned model.
Basic TD learning, using state values only, must also be model-based in order to work as a control system and pick actions. In order to pick the best action, it needs to query a model that predicts what will happen on each action, and implement a policy like $\pi(s) = \text{argmax}_a \sum_{s',r} p(s',r|s,a)(r + v(s'))$ where $p(s',r|s,a)$ is the probability of receiving reward $r$ and next state $s'$ when taking action $a$ in state $s$. That function $p(s',r|s,a)$ is essentially the model.
The RL literature differentiates between "model" as a model of the environment for "model-based" and "model-free" learning, and use of statistical learners, such as neural networks.
In RL, neural networks are often employed to learn and generalise value functions, such as the Q value which predicts total return (sum of discounted rewards) given a state and action pair. Such a trained neural network is often called a "model" in e.g. supervised learning. However, in RL literature, you will see the term "function approximator" used for such a network to avoid ambiguity.
It seems to me that any model-free learner, learning through trial and error, could be reframed as model-based.
I think here you are using the general understanding of the word "model" to include any structure that makes useful predictions. That would apply to e.g. table of Q values in SARSA.
However, as explained above, that's not how the term is used in RL. So although your understanding that RL builds useful internal representations is correct, you are not technically correct that this can be used to re-frame between "model-free" as "model-based", because those terms have a very specific meaning in RL.
In that case, when would model-free learners be appropriate?
Generally with current state of art in RL, if you don't have an accurate model provided as part of the problem definition, then model-free approaches are often superior.
There is lots of interest in agents that build predictive models of the environment, and doing so as a "side effect" (whilst still being a model-free algorithm) can still be useful - it may regularise a neural network or help discover key predictive features that can also be used in policy or value networks. However, model-based agents that learn their own models for planning have a problem that inaccuracy in these models can cause instability (the inaccuracies multiply the further into the future the agent looks). Some promising inroads are being made using imagination-based agents and/or mechanisms for deciding when and how much to trust the learned model during planning.
Right now (in 2018), if you have a real-world problem in an environment without an explicit known model at the start, then the safest bet is to use a model-free approach such as DQN or A3C. That may change as the field is moving fast and new more complex architectures could well be the norm in a few years.
Model-based reinforcement learning has an agent try to understand the world and create a model to represent it. Here the model is trying to capture 2 functions, the transition function from states $T$ and the reward function $R$. From this model, the agent has a reference and can plan accordingly.
However, it is not necessary to learn a model, and the agent can instead learn a policy directly using algorithms like Q-learning or policy gradient.
A simple check to see if an RL algorithm is model-based or model-free is:
If, after learning, the agent can make predictions about what the next state and reward will be before it takes each action, it's a model-based RL algorithm.
If it can't, then it’s a model-free algorithm.
In reinforcement learning (RL), there is an agent which interacts with an environment (in time steps). At each time step, the agent decides and executes an action, $a$, on an environment, and the environment responds to the agent by moving from the current state (of the environment), $s$, to the next state (of the environment), $s'$, and by emitting a scalar signal, called the reward, $r$. In principle, this interaction can continue forever or until e.g. the agent dies.
The main goal of the agent is to collect the largest amount of reward "in the long run". To do that, the agent needs to find an optimal policy (roughly, the optimal strategy to behave in the environment). In general, a policy is a function which, given a current state of the environment, outputs an action (or a probability distribution over actions, if the policy is stochastic) to execute in the environment. A policy can thus be thought of as the "strategy" used by the agent to behave in this environment. An optimal policy (for a given environment) is a policy which, if followed, will make the agent collect the largest amount of reward in the long run (which is the goal of the agent). In RL, we are thus interested in finding optimal policies.
The environment can be deterministic (that is, roughly, the same action in the same state leads to the same next state, for all time steps) or stochastic (or non-deterministic), that is, if the agent takes an action in a certain state, the resulting next state of the environment might not necessarily always be the same: there is a probability that it will be a certain state or another. Of course, these uncertainties will make the task of finding the optimal policy harder.
In RL, the problem is often mathematically formulated as a Markov decision process (MDP). A MDP is a way of representing the "dynamics" of the environment, that is, the way the environment will react to the possible actions the agent might take, at a given state. More precisely, an MDP is equipped with a transition function (or "transition model"), which is a function that, given the current state of the environment and an action (that the agent might take), outputs a probability of moving to any of the next states. A reward function is also associated with an MDP. Intuitively, the reward function outputs a reward, given the current state of the environment (and, possibly, an action taken by the agent and the next state of the environment). Collectively, the transition and reward functions are often called the model of environment. To conclude, the MDP is the problem and the solution to the problem is a policy. Furthermore, the "dynamics" of the environment are governed by the transition and reward functions (that is, the "model").
However, we often do not have the MDP, that is, we do not have the transition and reward functions (of the MDP associated the environment). Hence, we cannot estimate a policy from the MDP, because it is unknown. Note that, in general, if we had the transition and reward functions of the MDP associated with the environment, we could exploit them and retrieve an optimal policy (using dynamic programming algorithms).
In the absence of these functions (that is, when the MDP is unknown), to estimate the optimal policy, the agent needs to interact with environment and observe the responses of the environment. This is often referred to as the "reinforcement learning problem", because the agent will need to estimate a policy by reinforcing its beliefs about the dynamics of the environment. Over time, the agent starts to understand how the environment responds to its actions, and it can thus start to estimate the optimal policy. Thus, in the RL problem, the agent estimates the optimal policy to behave in an unknown (or partially known) environment by interacting with it (using a "trial-and-error" approach).
In this context, a model-based algorithm is an algorithm that uses the transition function (and the reward function) in order to estimate the optimal policy. The agent might have access only to an approximation of the transition function and reward functions, which can be learned by the agent while it interacts with the environment or it can be given to the agent (e.g. by another agent). In general, in a model-based algorithm, the agent can potentially predict the dynamics of the environment (during or after the learning phase), because it has an estimate of the transition function (and reward function). However, note that the transition and reward functions that the agent uses in order to improve its estimate of the optimal policy might just be approximations of the "true" functions. Hence, the optimal policy might never be found (because of these approximations).
A model-free algorithm is an algorithm that estimates the optimal policy without using or estimating the dynamics (transition and reward functions) of the environment. In practice, a model-free algorithm either estimates a "value function" or the "policy" directly from experience (that is, the interaction between the agent and environment), without using neither the transition function nor the reward function. A value function can be thought of as a function which evaluates a state (or an action taken in a state), for all states. From this value function, a policy can then be derived.
In practice, one way to distinguish between model-based or model-free algorithms is to look at the algorithms and see if they use the transition or reward function.
For instance, let's look at the main update rule in the Q-learning algorithm:
$$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha (R_{t+1} + \gamma \max_{a}Q(S_{t+1}, a) - Q(S_t, A_t))$$
As we can see, this update rule does not use any probabilities defined by the MDP. Note: $R_{t+1}$ is just the reward that is obtained at the next time step (after taking the action), but it is not necessarily known beforehand. So, Q-learning is a model-free algorithm.
Now, let's look at the main update rule of the policy improvement algorithm:
$$Q(s,a) \leftarrow \sum_{s' \in \mathcal{S}, r\in\mathcal{R}}p(s',r|s,a)(r+\gamma V(s'))$$
We can immediately observe it uses $p(s',r|s,a)$, a probability defined by the MDP model. So, policy iteration (a dynamic programming algorithm), which uses the policy improvement algorithm, is a model-based algorithm.
Although there are several good answers, I want to add this paragraph from Reinforcement Learning: An Introduction, page 303, for a more psychological view on the difference.
The distinction between model-free and model-based reinforcement learning algorithms corresponds to the distinction psychologists make between habitual and goal-directed control of learned behavioral patterns. Habits are behavior patterns triggered by appropriate stimuli and then performed more-or-less automatically. Goal-directed behavior, according to how psychologists use the phrase, is purposeful in the sense that it is controlled by knowledge of the value of goals and the relationship between actions and their consequences. Habits are sometimes said to be controlled by antecedent stimuli, whereas goal-directed behavior is said to be controlled by its consequences (Dickinson, 1980, 1985). Goal-directed control has the advantage that it can rapidly change an animal’s behavior when the environment changes its way of reacting to the animal’s actions. While habitual behavior responds quickly to input from an accustomed environment, it is unable to quickly adjust to changes in the environment.
It keeps going from there, and has a nice example afterwards.
I think the main point that was not always explained in the other answers, is that in a model-free approach you still need some kind of environment to tell you what is the reward associated with your action. The big difference is that you do NOT need to store any information about the model. You give the environment your chosen action, you update your estimated policy, and you forget about it. On the other hand, in model-based approaches, you either need to know the state transitions history as in Dynamic Programming, or you need to be able to calculate all possible next states and associated rewards, from the present state.
In Model-Free RL, the agent does not have access to a model of the environment. By environment I mean a function which predicts state transition and rewards.
As of the time of writing, model-free methods are more popular and have been researched extensively.
In Model-Based RL, the agent has access to a model of the environment.
Main advantage is that this allows the agent to plan ahead by thinking ahead. Agents distill the results from planning ahead into a learned policy. A famous example of Model-Based RL is AlphaZero.
The main downside is that many times a ground-truth representation of the environment is not usually available.
Below is a non-exhaustive taxonomy of RL algorithms, which may help you to visualize better the RL landscape.
According to OpenAI – Kinds of RL Algorithms, algorithms which use a model of the environment, i.e. a function which predicts state transitions and rewards, are called model-based methods, and those that don’t are called model-free. This model can either have been given the agent or learned by the agent.
Using a model allows the agent to plan by thinking ahead, seeing what would happen for a range of possible choices, and explicitly deciding between its options. This may be useful when faced with problems that require more long-term thinking. One way to perform planning is by using some kind of tree search, for example Monte Carlo tree search (MCTS), or—which I suspect could also be used—variants of the rapidly exploring random tree (RRT). See e.g. Agents that imagine and plan.
The agent can then distill the results from planning ahead into a learned policy – this is known as expert iteration.
A model can also be used to create a simulated, or "imagined," environment in which the state is updated by using the model, and make the agent learn inside of that environment, such as in World Models.
In many real-world scenarios, the ground-truth model of the environment is not available to the agent. If an agent wants to use a model in this case, it has to learn the model, which can be challenging for several reasons.
There are however cases in which the agent uses a model that is already known and consequently doesn't have to learn the model, such as in AlphaZero, where the model comes in form of the rules of the game.
