Answers.Body: <p>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 <span class="math-container">$n$</span> times to further back up your <span class="math-container">$Q$</span> 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.</p>
  <p>Algorithms like vanilla <span class="math-container">$Q$</span>-learning are model free because they don't require a model of the environment to learn.</p>
  <p><a href="https://i.sstatic.net/VF35X.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/VF35X.png" alt="enter image description here" /></a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-09-25T21:30:08.410Z
Answers.Text: This answer is correct and I would upvote it, but if this question is a duplicate of [this one](https://ai.stackexchange.com/q/4456/2444), 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).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-09-26T11:09:16.447Z
Answers.Text: 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?
Answers.UserDisplayName: Tfovid
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-09-25T13:29:21.033Z
Answers.LastActivityDate: 2020-09-25T13:29:21.033Z
Answers.UserDisplayName: David
Answers.Body: <blockquote>
  <p>Q-learning is said to be &quot;model-free&quot;. Given the two examples above, is it because neither the lake's topology nor that of the mountain are changed by the actions taken?</p>
  </blockquote>
  <p>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 <strong>Markov decision process (MDP)</strong>, 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</p>
  <ul>
  <li>A set of actions <span class="math-container">$A$</span> (that the RL agent can take); for example, up and down, in some grid world</li>
  <li>A set of states <span class="math-container">$S$</span> (where the RL agent can be);</li>
  <li>A <strong>transition function</strong> <span class="math-container">$p(s_{t+1} = s' \mid s_{t} = s , a_t = a)$</span> (aka the <strong>model</strong>), which represents the probability of going to state <span class="math-container">$s'$</span> at time step <span class="math-container">$t+1$</span>, given that at time step <span class="math-container">$t$</span> the RL agent is in the state <span class="math-container">$s$</span> and takes action <span class="math-container">$a$</span>.</li>
  <li>A <strong>reward function</strong> <span class="math-container">$r(s, a, s')$</span> (sometimes also denoted as <span class="math-container">$r(s)$</span> or <span class="math-container">$r(s, s')$</span>, although <a href="https://ai.stackexchange.com/q/10442/2444">these can have different semantics</a>); 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 <span class="math-container">$p(s_{t+1} = s', r_{t+1} = r \mid s_{t} = s , a_t = a)$</span>, and this is the <strong>model</strong>: this is what we mean by <strong>model</strong> in reinforcement learning, it's this <span class="math-container">$p$</span> (which is a probability distribution)!</li>
  </ul>
  <p>A model-free algorithm is any algorithm that does not use or estimate this <span class="math-container">$p$</span>. Q-learning, <a href="http://www.incompleteideas.net/book/RLbook2020.pdf#page=153" rel="nofollow noreferrer">if you look at its pseudocode</a>, does not make use of this model. Q-learning estimates the value function <span class="math-container">$q(s, a)$</span> by interacting with the environment (taking actions and receiving rewards), but, meanwhile, it does not know or keep track of the dynamics (i.e. <span class="math-container">$p$</span>) of the environment, and that's why it's model-free.</p>
  <p>And, no, the value function is not what we mean by &quot;model&quot; in reinforcement learning. The value function is, as the name suggests, a function.</p>
  <blockquote>
  <p>How does one know that a problem is &quot;model-free&quot; in reinforcement learning?</p>
  </blockquote>
  <p>A problem is not model-free or model-based. An <strong>algorithm</strong> is model-free or model-based. Again, a model-free algorithm does not use or estimate <span class="math-container">$p$</span>, a model-based one uses (and/or estimates) it.</p>
  <blockquote>
  <p>Given the two examples above, is it because neither the lake's topology nor that of the mountain are changed by the actions taken?</p>
  </blockquote>
  <p>No. As stated in the <a href="https://ai.stackexchange.com/a/23749/2444">other answer</a>, you could apply the model-based algorithm Dyna-Q to these environments.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-09-27T11:12:54.590Z
Answers.LastActivityDate: 2020-09-27T13:35:53.027Z
Answers.LastEditDate: 2020-09-27T13:35:53.027Z
Answers.UserDisplayName: nbro
Body: <p>Consider <a href="https://youtu.be/FgzM3zpZ55o?list=PLoROMvodv4rOSOPzutgyCTapiGlY2Nd8u&amp;t=2705" rel="nofollow noreferrer">this slide</a> from a Stanford lecture on reinforcement learning. It states that a model is</p>
  <blockquote>
  <p>the agent's representation of how the world changes in response to the agent's action.</p>
  </blockquote>
  <p>I've been experimenting with Q-learning for simple problems such as OpenAI's <a href="https://gym.openai.com/envs/FrozenLake-v0/" rel="nofollow noreferrer">FrozenLake</a> and <a href="https://gym.openai.com/envs/MountainCar-v0/" rel="nofollow noreferrer">Mountain Car</a>, 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 &quot;worlds&quot; (aka. environments) in the two cases, respectively.</p>
  <p>Q-learning is said to be <a href="https://spinningup.openai.com/en/latest/_images/rl_algorithms_9_15.svg" rel="nofollow noreferrer">&quot;model-free&quot;</a>. Given the two examples above, is it because neither the lake's topology nor that of the mountain are changed by the actions taken?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-09-25T10:56:58.997Z
Comments.Text: Let me know if the answers to [this question](https://ai.stackexchange.com/q/4456/2444) 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.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-09-26T11:13:56.543Z
Comments.Text: @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.
Comments.UserDisplayName: Tfovid
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-09-26T11:30:43.850Z
Comments.Text: 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.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-09-26T11:33:53.917Z
Comments.Text: Please, [edit your post](https://ai.stackexchange.com/q/23745/2444) 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.
Comments.UserDisplayName: nbro
Tags: <reinforcement-learning><q-learning><dqn>
Title: How does one know that a problem is "model-free" in reinforcement learning?
UserDisplayName: Tfovid
ThreadText: # How does one know that a problem is "model-free" in reinforcement learning?
  
  (Asked by: username_0 on 2020-09-25)
  
  Consider [this slide](https://youtu.be/FgzM3zpZ55o?list=PLoROMvodv4rOSOPzutgyCTapiGlY2Nd8u&t=2705) 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](https://gym.openai.com/envs/FrozenLake-v0/) and [Mountain Car](https://gym.openai.com/envs/MountainCar-v0/), 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"](https://spinningup.openai.com/en/latest/_images/rl_algorithms_9_15.svg). Given the two examples above, is it because neither the lake's topology nor that of the mountain are changed by the actions taken?
  
  **Tags:** reinforcement-learning, q-learning, dqn
  
  > **Comments:**
  > **username_1**: Let me know if the answers to [this question](https://ai.stackexchange.com/q/4456/2444) 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.  
  > **username_0**: @username_1 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.  
  > **username_1**: 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.  
  > **username_1**: Please, [edit your post](https://ai.stackexchange.com/q/23745/2444) 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.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2020-09-27. Score: 5 | Accepted answer
  
  > 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](https://ai.stackexchange.com/q/10442/2444)); 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](http://www.incompleteideas.net/book/RLbook2020.pdf#page=153), 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](https://ai.stackexchange.com/a/23749/2444), you could apply the model-based algorithm Dyna-Q to these environments.
  
  
  ---
  
  ### Answer by username_2 on 2020-09-25. Score: 1
  
  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](https://i.sstatic.net/VF35X.png)](https://i.sstatic.net/VF35X.png)
  
  > **Comments:**
  > **username_1**: This answer is correct and I would upvote it, but if this question is a duplicate of [this one](https://ai.stackexchange.com/q/4456/2444), 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).  
  > **username_0**: 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?  
  
  ---
  
  