In [1]:

```
%matplotlib inline
import matplotlib.pyplot as plt
import seaborn as sns
from IPython.display import Image
```

- Model-based methods: planning
- Model-free methods: learning

the heart of both kinds of methods is the computation of value functions.

a

*model*of the enviroment: anything that an agent can use to predict how the environment will respond to its actions.- model can be used to
*simulate*the environemt and produce*simulated experience*.

- model can be used to
distribution models: produce a descripiton of all possibilities and their probabilities.

- sample models: produce just one of the possibilities, sampled according to the probabilities.

\begin{equation*} \text{model} \xrightarrow{\text{planning}} \text{policy} \end{equation*}

- state-space planning: search through the state space for an optimal policy or an optimal path to a goal.
- plan-space planning: search through the space of plans. includes: evolutionary methods, partial-order planning.

common structure shared by all state-space planning methods:

\begin{equation*} \text{model} \longrightarrow \text{simulated experience} \xrightarrow{\text{backups}} \text{values} \longrightarrow \text{policy} \end{equation*}

planning uses simulated experience VS learning uses real experience.

In [3]:

```
Image('./res/fig8_1.png')
```

Out[3]:

In [4]:

```
Image('./res/fig8_2.png')
```

Out[4]:

Learning and planning are deeply integrated in the sense that they share almost all the same machinery, differing only in the source of their experience.

- Indirect methods: make fuller use of a limited amount of experiences.
- Direct methods: much simpler and are not effected by biases in the design of the model.

Models may be incorrect because:

- Environment is stochastic and only a limited number of samples have been observed;
- The model was learned using function approximation that has generalized imperfectly;
- Then environment has changed and its new behavior has not yet been observed:
- original optimial solution doesn't work any more.
- better solution exists after environemt changed.

=> conflict between exploration and exploitation => simple heuristics are often effective.

Dyna-Q+ agen: keeps track for each state-action pair. The more time that has elapsed, the greater the chance to be picked next time => special "bonus reward": $r + k \sqrt{\tau}$

In [2]:

```
Image('./res/fig8_5.png')
```

Out[2]:

In [3]:

```
Image('./res/fig8_6.png')
```

Out[3]:

uniform selection is usually not the best; planning can be much more efficient if simulated transitions and updates are focused on particular state-action pairs.

*backward focusing* of planning computations: work backward from aribitary states that have changed in value. (propagation)

*prioritized sweeping*: prioritize the updates according to a measure of their urgency, and perform them in order of priority.

In [4]:

```
Image('./res/prioritized_sweeping.png')
```

Out[4]:

Three questions:

- Whether the algorithm updates state values $v$, or action values $q$?
- Whether the algorithm estimates the value for the optimal policy $\ast$, or for an arbitrary given policy $\pi$?
- Whether the updates are expected updates, or sample updates?
- expected updates: better estimate (uncorrupted by sampling error), but more computation.
- sample updates: superior on problems with large stochastic branching factors and too many states to be solved exactly.

In [5]:

```
Image('./res/fig8_7.png')
```

Out[5]:

Two ways of distributing updates:

- classical approach: sweeps through the entire state space, updating each state once per sweep.
- sample from the state according to some distribution.
*trajectory sampling*: one simulates explicit individual trajectories and performs updates at the state encountered along the way.

- background planning: using simulated experience to gradually improve a policy or value function.
- decision-time planning: using simulated experience to select an action for the current state. (look much deeper than on-step-ahead and evaluate action choices leading to many different predicted state and reward trajectories).

three key ideas in common:

- seek to estimate value functions;
- operate by backing up values along actual or possible state trajectories;
- follow the general strategy of generalized policy iteration(GPI).

important dimensions along wich the methods vary:

- whether they are sample updates or expected updates.
- the depth of updates (to the degree of boostrapping).
- on-policy or off-policy.
- fuction approximation.