How can we estimate the transition model and reward function?

Question

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.)?

Answer 1

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 (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 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, 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.

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.

Answer 2

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 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 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 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.