Answers.Body: <blockquote>
  <p>Given that model-based RL algorithms do not necessarily estimate or compute the transition model or reward function, in the case these are unknown, how can they be computed or estimated (so that they can be used by the model-based algorithms)?</p>
  </blockquote>
  <p>A generally reliable approach to creating learned models from interacting with the environment, then using those models internally for planning or explicitly model-based learning, is still something of a holy grail in RL. An agent that can do this across multiple domains might be considered a significant step in autonomous AI. Sutton &amp; Barto write in <a href="http://incompleteideas.net/book/RLbook2020.pdf" rel="nofollow noreferrer">Reinforcement Learning: An Introduction</a> (Chapter 17.5):</p>
  <blockquote>
  <p>More work is needed before planning with learned models can be effective. For example,the learning of the model needs to be selective because the scope of a model strongly affects planning efficiency. If a model focuses on the key consequences of the most important options, then planning can be efficient and rapid, but if a model includes details of unimportant consequences of options that are unlikely to be selected, then planning may be almost useless. Environment models should be constructed judiciously with regard to both their states and dynamics with the goal of optimizing the planning process. The various parts of the model should be continually monitored as to the degree to which they contribute to, or detract from, planning efficiency. <strong>The field has not
  yet addressed this complex of issues or designed model-learning methods that take into account their implications.</strong></p>
  </blockquote>
  <p>[Emphasis mine]</p>
  <p>This was written in 2019, so as far as I know still stands as a summary of state-of-the-art. There is ongoing research into this - for instance, the paper <a href="https://arxiv.org/pdf/1809.05214.pdf" rel="nofollow noreferrer">Model-Based Reinforcement Learning via Meta-Policy Optimization</a> considers using multiple learned models to assess reliability. I have seen a similar recent paper which also assesses the reliability of the learned model and chooses how much it should trust it over a simpler model-free prediction, but cannot recall the name or find it currently.</p>
  <p>One very simple form of a learned model is to memorise transitions that have been experienced already. This is functionally very similar to the experience replay table used in DQN. The <a href="https://medium.com/@ranko.mosic/online-planning-agent-dyna-q-algorithm-and-dyna-maze-example-sutton-and-barto-2016-7ad84a6dc52b" rel="nofollow noreferrer">classic RL algorithm for this kind of model is Dyna-Q</a>, where the data stored about known transitions is used to perform background planning. In its simplest form, the algorithm is almost indistinguishable from experience replay in DQN. However, this memorised set of transition records <em>is</em> a learned model, and is used as such in Dyna-Q.</p>
  <p>The basic Dyna-Q approach creates a tabular model. It does not generalise to predicting outcomes from previously unseen state, action pairs. However, this is relatively easy to fix - simply feed experience so far as training data into a function approximator and you can create a learned model of the environment that attempts to generalise to new states. This idea has been around for a long time. Unfortunately, it has problems - planning accuracy is strongly influenced by the accuracy of the model. This applies for both background planning and looking forward from the current state. Approximate models like this to date <a href="https://arxiv.org/abs/1906.05243" rel="nofollow noreferrer">typically perform worse than simple replay-based approaches</a>.</p>
  <p>This general approach - learn the model statistically from observations - can be refined and may work well if there is any decent prior knowledge that restricts the model. For example, if you want to model a physical system that is influenced by current air pressure and local gravity, you could have free parameters for those unknowns starting with some standardised guesses, and then refine the model of dynamics when observations are made, with strong constraints about the form it will take.</p>
  <p>Similarly, in games of chance with hidden state, you may be able to model the unknowns within a broader well-understood model, and use e.g. Bayesian inference to add constraints and best guesses. This is typically what you would do for a POMDP with a &quot;belief state&quot;.</p>
  <p>Both of the domain-specific approaches in the last two paragraphs can be made to work better than model-free algorithms alone, but they require deep understanding/analysis of the problem being solved by the researcher to set up a parametric model that is both flexible enough to match the environment being learned, but also constrained enough that it cannot become too inaccurate.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-24T13:59:41.637Z
Answers.Text: I think it's not strictly correct to say this "this memorised set of transition records is a learned model" or to say that the experience replay buffer is a model. I think it's more accurate to say that it "induces" a model, i.e. you can build a model from the dataset/buffer or stored transitions. For example, you might have more evidence for more tuples than others, so you may be more uncertain for certain tuples/transitions than others. So, the dataset alone doesn't define the model. You still need to define the probabilities (will you just use the empirical frequencies?) or how to sample.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-24T14:11:58.280Z
Answers.Text: @nbro Yes I see what you mean. What I was going for was more like this: kNN with k=1 is a model, so what is missing from the experience replay table to make it an explicit model like kNN is only lookup by $s,a$. I'm not sure whether "*induces* a model" is how I would phrase that.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-09-18T13:58:13.070Z
Answers.LastActivityDate: 2022-01-24T11:29:02.863Z
Answers.LastEditDate: 2022-01-24T11:29:02.863Z
Answers.UserDisplayName: Neil Slater
Answers.Body: <p>The original question about <em>both</em> the estimation of the <em>transition model</em>, often denoted as <span class="math-container">$T$</span>, and the <em>reward function</em>, sometimes denoted as <span class="math-container">$R$</span>, arose because I was thinking about the probability distribution often denoted as</p>
  <p><span class="math-container">$$\color{red}{p}\left(s^{\prime}, r \mid s, a\right) \doteq \operatorname{Pr}\left\{S_{t}=s^{\prime}, R_{t}=r \mid S_{t-1}=s, A_{t-1}=a\right\},$$</span></p>
  <p>which is often called the <em>model</em> (and <a href="http://incompleteideas.net/book/RLbook2020.pdf#page=70" rel="nofollow noreferrer">Sutton &amp; Barto</a> also call it the <em>dynamics function</em>, given that it defines the <em>dynamics</em> of the environment), which incorporates both the transition model and reward function. In fact, both the transition probability distribution (of the next state <span class="math-container">$s'$</span> given <span class="math-container">$s$</span> and <span class="math-container">$a$</span>) and <a href="https://ai.stackexchange.com/q/10442/2444">different types of reward functions</a> can be written as a function of this <em>dynamics function</em>. More precisely, we have the following results</p>
  <ol>
  <li><p><span class="math-container">$\color{orange}{p}\left(s^{\prime} \mid s, a\right) \doteq \operatorname{Pr}\left\{S_{t}=s^{\prime} \mid S_{t-1}=s, A_{t-1}=a\right\}=\sum_{r \in \mathcal{R}} \color{red}{p}\left(s^{\prime}, r \mid s, a\right)$</span></p>
  </li>
  <li><p><span class="math-container">$\color{blue}{r}(s, a) \doteq \mathbb{E}\left[R_{t} \mid S_{t-1}=s, A_{t-1}=a\right]=\sum_{r \in \mathcal{R}} r \sum_{s^{\prime} \in \mathcal{S}} \color{red}{p}\left(s^{\prime}, r \mid s, a\right)$</span></p>
  </li>
  <li><p><span class="math-container">$\color{cyan}{r}\left(s, a, s^{\prime}\right) \doteq \mathbb{E}\left[R_{t} \mid S_{t-1}=s, A_{t-1}=a, S_{t}=s^{\prime}\right]=\sum_{r \in \mathcal{R}} r \frac{\color{red}{p}\left(s^{\prime}, r \mid s, a\right)}{\color{orange}{p}\left(s^{\prime} \mid s, a\right)}$</span></p>
  </li>
  </ol>
  <p>Given that <a href="https://ai.stackexchange.com/a/23647/2444">this answer</a> already (partially) answers the question</p>
  <blockquote>
  <p>How can we estimate the transition model?</p>
  </blockquote>
  <p>but not the question</p>
  <blockquote>
  <p>How can we estimate the reward function?</p>
  </blockquote>
  <p>I will provide here an answer to this second question.</p>
  <p>We can use <strong>inverse reinforcement learning</strong> techniques, i.e. techniques that estimate the reward function given trajectories of the form <span class="math-container">$$\tau = (s_1, a_1, r_1, s_{2}, \dots, s_{T-1}, a_{T-1}, r_{T-1}, s_{T}),$$</span> which are often assumed to have been generated by some optimal policy <span class="math-container">$\pi^*$</span>, to estimate the reward function. An example of such a technique is <a href="https://arxiv.org/pdf/1710.11248.pdf" rel="nofollow noreferrer">AIRL</a>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-09T12:08:27.323Z
Answers.LastActivityDate: 2020-11-09T12:22:19.570Z
Answers.LastEditDate: 2020-11-09T12:22:19.570Z
Answers.UserDisplayName: nbro
Body: <p>In reinforcement learning (RL), there are model-based and model-free algorithms. In short, model-based algorithms use a transition model <span class="math-container">$p(s' \mid s, a)$</span> and the reward function <span class="math-container">$r(s, a)$</span>, even though they do not necessarily compute (or estimate) them. On the other hand, model-free algorithms do not use such a transition model or reward function, but they directly estimate a value function or policy by interacting with the environment, which allows the agent to infer the dynamics of the environment.</p>
  <p>Given that model-based RL algorithms do not necessarily estimate or compute the transition model or reward function, in the case these are unknown, how can they be computed or estimated (so that they can be used by the model-based algorithms)? In general, what are examples of algorithms that can be used to estimate the transition model and reward function of the environment (represented as either an MDP, POMDP, etc.)?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-09-18T13:27:27.963Z
Comments.Text: A similar question had already been asked [here](https://ai.stackexchange.com/q/2528/2444), but it focuses on the case where the transition matrix can be very big (in my question above, I don't put this restriction). [Here](https://ai.stackexchange.com/q/17350/2444) is another related question, but specific to POMDPs.
Comments.UserDisplayName: nbro
Tags: <reinforcement-learning><reference-request><algorithm-request><model-based-methods><model-free-methods>
Title: How can we estimate the transition model and reward function?
UserDisplayName: nbro
ThreadText: # How can we estimate the transition model and reward function?
  
  (Asked by: username_0 on 2019-02-16)
  
  In reinforcement learning (RL), there are model-based and model-free algorithms. In short, model-based algorithms use a transition model $p(s' \mid s, a)$ and the reward function $r(s, a)$, even though they do not necessarily compute (or estimate) them. On the other hand, model-free algorithms do not use such a transition model or reward function, but they directly estimate a value function or policy by interacting with the environment, which allows the agent to infer the dynamics of the environment.
  
  Given that model-based RL algorithms do not necessarily estimate or compute the transition model or reward function, in the case these are unknown, how can they be computed or estimated (so that they can be used by the model-based algorithms)? In general, what are examples of algorithms that can be used to estimate the transition model and reward function of the environment (represented as either an MDP, POMDP, etc.)?
  
  **Tags:** reinforcement-learning, reference-request, algorithm-request, model-based-methods, model-free-methods
  
  > **Comments:**
  > **username_0**: A similar question had already been asked [here](https://ai.stackexchange.com/q/2528/2444), but it focuses on the case where the transition matrix can be very big (in my question above, I don't put this restriction). [Here](https://ai.stackexchange.com/q/17350/2444) is another related question, but specific to POMDPs.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2020-09-18. Score: 1 | Accepted answer
  
  > Given that model-based RL algorithms do not necessarily estimate or compute the transition model or reward function, in the case these are unknown, how can they be computed or estimated (so that they can be used by the model-based algorithms)?
  
  A generally reliable approach to creating learned models from interacting with the environment, then using those models internally for planning or explicitly model-based learning, is still something of a holy grail in RL. An agent that can do this across multiple domains might be considered a significant step in autonomous AI. Sutton & Barto write in [Reinforcement Learning: An Introduction](http://incompleteideas.net/book/RLbook2020.pdf) (Chapter 17.5):
  
  > More work is needed before planning with learned models can be effective. For example,the learning of the model needs to be selective because the scope of a model strongly affects planning efficiency. If a model focuses on the key consequences of the most important options, then planning can be efficient and rapid, but if a model includes details of unimportant consequences of options that are unlikely to be selected, then planning may be almost useless. Environment models should be constructed judiciously with regard to both their states and dynamics with the goal of optimizing the planning process. The various parts of the model should be continually monitored as to the degree to which they contribute to, or detract from, planning efficiency. **The field has not
  > yet addressed this complex of issues or designed model-learning methods that take into account their implications.**
  
  [Emphasis mine]
  
  This was written in 2019, so as far as I know still stands as a summary of state-of-the-art. There is ongoing research into this - for instance, the paper [Model-Based Reinforcement Learning via Meta-Policy Optimization](https://arxiv.org/pdf/1809.05214.pdf) considers using multiple learned models to assess reliability. I have seen a similar recent paper which also assesses the reliability of the learned model and chooses how much it should trust it over a simpler model-free prediction, but cannot recall the name or find it currently.
  
  One very simple form of a learned model is to memorise transitions that have been experienced already. This is functionally very similar to the experience replay table used in DQN. The [classic RL algorithm for this kind of model is Dyna-Q](https://medium.com/@ranko.mosic/online-planning-agent-dyna-q-algorithm-and-dyna-maze-example-sutton-and-barto-2016-7ad84a6dc52b), where the data stored about known transitions is used to perform background planning. In its simplest form, the algorithm is almost indistinguishable from experience replay in DQN. However, this memorised set of transition records *is* a learned model, and is used as such in Dyna-Q.
  
  The basic Dyna-Q approach creates a tabular model. It does not generalise to predicting outcomes from previously unseen state, action pairs. However, this is relatively easy to fix - simply feed experience so far as training data into a function approximator and you can create a learned model of the environment that attempts to generalise to new states. This idea has been around for a long time. Unfortunately, it has problems - planning accuracy is strongly influenced by the accuracy of the model. This applies for both background planning and looking forward from the current state. Approximate models like this to date [typically perform worse than simple replay-based approaches](https://arxiv.org/abs/1906.05243).
  
  This general approach - learn the model statistically from observations - can be refined and may work well if there is any decent prior knowledge that restricts the model. For example, if you want to model a physical system that is influenced by current air pressure and local gravity, you could have free parameters for those unknowns starting with some standardised guesses, and then refine the model of dynamics when observations are made, with strong constraints about the form it will take.
  
  Similarly, in games of chance with hidden state, you may be able to model the unknowns within a broader well-understood model, and use e.g. Bayesian inference to add constraints and best guesses. This is typically what you would do for a POMDP with a "belief state".
  
  Both of the domain-specific approaches in the last two paragraphs can be made to work better than model-free algorithms alone, but they require deep understanding/analysis of the problem being solved by the researcher to set up a parametric model that is both flexible enough to match the environment being learned, but also constrained enough that it cannot become too inaccurate.
  
  > **Comments:**
  > **username_0**: I think it's not strictly correct to say this "this memorised set of transition records is a learned model" or to say that the experience replay buffer is a model. I think it's more accurate to say that it "induces" a model, i.e. you can build a model from the dataset/buffer or stored transitions. For example, you might have more evidence for more tuples than others, so you may be more uncertain for certain tuples/transitions than others. So, the dataset alone doesn't define the model. You still need to define the probabilities (will you just use the empirical frequencies?) or how to sample.  
  > **username_1**: @username_0 Yes I see what you mean. What I was going for was more like this: kNN with k=1 is a model, so what is missing from the experience replay table to make it an explicit model like kNN is only lookup by $s,a$. I'm not sure whether "*induces* a model" is how I would phrase that.  
  
  ---
  
  ### Answer by username_0 on 2020-11-09. Score: 1
  
  The original question about *both* the estimation of the *transition model*, often denoted as $T$, and the *reward function*, sometimes denoted as $R$, arose because I was thinking about the probability distribution often denoted as
  
  $$\color{red}{p}\left(s^{\prime}, r \mid s, a\right) \doteq \operatorname{Pr}\left\{S\_{t}=s^{\prime}, R\_{t}=r \mid S\_{t-1}=s, A\_{t-1}=a\right\},$$
  
  which is often called the *model* (and [Sutton & Barto](http://incompleteideas.net/book/RLbook2020.pdf#page=70) also call it the *dynamics function*, given that it defines the *dynamics* of the environment), which incorporates both the transition model and reward function. In fact, both the transition probability distribution (of the next state $s'$ given $s$ and $a$) and [different types of reward functions](https://ai.stackexchange.com/q/10442/2444) can be written as a function of this *dynamics function*. More precisely, we have the following results
  
  1. $\color{orange}{p}\left(s^{\prime} \mid s, a\right) \doteq \operatorname{Pr}\left\{S\_{t}=s^{\prime} \mid S\_{t-1}=s, A\_{t-1}=a\right\}=\sum\_{r \in \mathcal{R}} \color{red}{p}\left(s^{\prime}, r \mid s, a\right)$
  2. $\color{blue}{r}(s, a) \doteq \mathbb{E}\left[R\_{t} \mid S\_{t-1}=s, A\_{t-1}=a\right]=\sum\_{r \in \mathcal{R}} r \sum\_{s^{\prime} \in \mathcal{S}} \color{red}{p}\left(s^{\prime}, r \mid s, a\right)$
  3. $\color{cyan}{r}\left(s, a, s^{\prime}\right) \doteq \mathbb{E}\left[R\_{t} \mid S\_{t-1}=s, A\_{t-1}=a, S\_{t}=s^{\prime}\right]=\sum\_{r \in \mathcal{R}} r \frac{\color{red}{p}\left(s^{\prime}, r \mid s, a\right)}{\color{orange}{p}\left(s^{\prime} \mid s, a\right)}$
  
  Given that [this answer](https://ai.stackexchange.com/a/23647/2444) already (partially) answers the question
  
  > How can we estimate the transition model?
  
  but not the question
  
  > How can we estimate the reward function?
  
  I will provide here an answer to this second question.
  
  We can use **inverse reinforcement learning** techniques, i.e. techniques that estimate the reward function given trajectories of the form $$\tau = (s\_1, a\_1, r\_1, s\_{2}, \dots, s\_{T-1}, a\_{T-1}, r\_{T-1}, s\_{T}),$$ which are often assumed to have been generated by some optimal policy $\pi^\*$, to estimate the reward function. An example of such a technique is [AIRL](https://arxiv.org/pdf/1710.11248.pdf).
  
  
  ---
  
  