---
title: "Memory-Based and Kernel Methods"
module: Approximate Solution Methods
moduleNumber: 3
lessonNumber: 12
order: 312
summary: >
  Least-squares TD spent more compute to extract more from each
  example; this lesson drops the parametric form entirely. Memory-based methods
  store training examples untouched and answer a query locally at retrieval time —
  nearest neighbor, weighted average, locally weighted regression — so accuracy
  grows with the data and effort concentrates where the agent actually goes.
  Kernel-based methods weight stored examples by a similarity kernel $k(s,s')$,
  and every linear method turns out to be a kernel method. Interest and
  emphasis, finally, make the on-policy weighting itself a design choice, aiming
  scarce approximation capacity at the states that matter.
topics: [Approximation]
sources:
  - book: Sutton & Barto
    ref: "Ch. 9 — On-policy Prediction with Approximation; §9.9 Memory-based Function Approximation; §9.10 Kernel-based Function Approximation"
  - book: Sutton & Barto
    ref: "§9.11 Looking Deeper at On-policy Learning: Interest and Emphasis"
---

This builds on
[least-squares TD and memory-based methods](/reinforcement-learning/approximation/least-squares-and-memory-based-methods),
which stayed parametric — LSTD kept the linear form $\hat v = \mathbf{w}^\top
\mathbf{x}(s)$ and merely solved for its fixed point directly. This lesson drops the
parametric commitment altogether: store the examples themselves, and let the
approximation take whatever shape the data implies.

## Memory-based function approximation

Everything so far — linear or nonlinear, iterative or batch — has been
**parametric**. A parametric method commits to a functional form governed by a
fixed-size parameter vector $\mathbf{w}$; each update $s \mapsto g$ adjusts
$\mathbf{w}$ to reduce error, and afterward the training example can be discarded.
When a query state needs a value, the function is evaluated at that state using
the latest parameters. The whole of the data's influence has been squeezed into
$\mathbf{w}$.

**Memory-based** methods work differently, and the difference is fundamental.
They save training examples in memory as they arrive — or at least a subset —
**without updating any parameters at all**. When a value estimate is needed for a
**query state**, a set of examples is retrieved from memory and combined on the
spot to produce the estimate. Because the work of processing examples is postponed
until a query arrives, this is called **lazy learning**.[^sb-memory]

$$
% caption: Parametric versus memory-based approximation. The parametric method
% (top) folds each example into a fixed weight vector and discards it, evaluating
% $\hat v(s,\mathbf{w})$ at query time; the memory-based method (bottom) stores
% examples untouched and retrieves nearby ones only when a query state arrives.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=17mm, minimum height=9mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  % parametric row
  \node[anchor=east, font=\scriptsize] at (-0.3,1.6) {parametric};
  \node[box] (pd) at (1.0,1.6) {examples};
  \node[box, draw=acc, text=acc] (pw) at (4.0,1.6) {weights w};
  \node[box] (pq) at (7.2,1.6) {v(s,w)};
  \draw[->, black, thick] (pd) -- (pw) node[midway, above, font=\scriptsize] {fold in};
  \draw[->, acc, thick] (pw) -- (pq) node[midway, above, font=\scriptsize] {evaluate};
  % memory row
  \node[anchor=east, font=\scriptsize] at (-0.3,-0.6) {memory-based};
  \node[box] (md) at (1.0,-0.6) {examples};
  \node[box, draw=acc, text=acc, minimum width=20mm] (mm) at (4.0,-0.6) {stored memory};
  \node[box] (mq) at (7.2,-0.6) {v(s) at query};
  \draw[->, black, thick] (md) -- (mm) node[midway, above, font=\scriptsize] {store};
  \draw[->, acc, thick] (mm) -- (mq) node[midway, above, font=\scriptsize] {retrieve};
\end{tikzpicture}
$$

Memory-based methods are the prime example of **nonparametric** approximation. The
approximating function is not limited to a pre-specified class — linear functions,
polynomials, a fixed set of basis functions — but is determined jointly by the
stored examples and the rule for combining them. There is no fixed cap on
expressiveness: as more examples accumulate, a nonparametric method can produce an
ever more accurate approximation to any target function.

> **Definition (Nonparametric approximation).** An approximation whose functional
> form is not fixed in advance by a parameter vector but is determined by the
> training examples themselves, together with a rule for combining them. Its
> capacity grows with the amount of data, so accuracy improves as examples
> accumulate rather than saturating at a preset model size.

### Local learning: nearest neighbor and weighted average

The memory-based methods most useful here are **local-learning** methods, which
approximate the value function only in the neighborhood of the current query
state. They retrieve the examples judged most relevant to the query, where
relevance usually falls off with distance: the closer a stored example's state is
to the query state, the more it counts. Once the query has been answered, the
local approximation is discarded.

The simplest is the **nearest neighbor** method: find the stored example whose
state is closest to the query state $s$, and return that example's value. If the
query is $s$ and $s' \mapsto g$ is the example in memory whose state $s'$ is
closest to $s$, then $g$ is returned as the approximate value of $s$. A refinement
is the **weighted average**: retrieve a set of nearest examples and return a
weighted average of their target values, the weights decreasing with distance from
the query. More elaborate still is **locally weighted regression**, which fits a
surface to the values of a set of nearby states using a parametric fit that
minimizes a distance-weighted error, then evaluates that surface at the query
state — and, being memory-based, throws the fitted surface away afterward.[^sb-memory]

$$
% caption: Three local memory-based rules answering a query at $s$ (blue). Nearest
% neighbor copies the value of the single closest stored state; weighted average
% blends a set of neighbors with distance-decaying weights; locally weighted
% regression fits a small surface to the neighbors and evaluates it at $s$.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % --- nearest neighbor ---
  \begin{scope}
    \node[anchor=south, font=\scriptsize] at (1.2,2.5) {nearest neighbor};
    \foreach \p in {(0.3,0.5),(1.9,1.7),(2.2,0.6),(0.6,1.9),(1.5,1.2)}
      \fill[black] \p circle (1.8pt);
    \fill[acc] (1.15,1.0) circle (2.6pt);
    \node[acc, anchor=north, font=\scriptsize] at (1.15,0.9) {s};
    \draw[red, thick, ->] (1.15,1.0) -- (1.42,1.15);
    \fill[red] (1.5,1.2) circle (2.2pt);
  \end{scope}
  % --- weighted average ---
  \begin{scope}[xshift=4.4cm]
    \node[anchor=south, font=\scriptsize] at (1.2,2.5) {weighted average};
    \foreach \p in {(0.3,0.5),(1.9,1.7),(2.2,0.6),(0.6,1.9),(1.5,1.2)}
      \fill[black] \p circle (1.8pt);
    \fill[acc] (1.15,1.0) circle (2.6pt);
    \node[acc, anchor=north, font=\scriptsize] at (1.15,0.9) {s};
    \foreach \p in {(1.5,1.2),(0.6,1.9),(2.2,0.6)}
      \draw[red, thick] (1.15,1.0) -- \p;
  \end{scope}
  % --- locally weighted regression ---
  \begin{scope}[xshift=8.8cm]
    \node[anchor=south, font=\scriptsize] at (1.2,2.5) {local regression};
    \foreach \p in {(0.3,0.5),(1.9,1.7),(2.2,0.6),(0.6,1.9),(1.5,1.2)}
      \fill[black] \p circle (1.8pt);
    \fill[acc] (1.15,1.0) circle (2.6pt);
    \node[acc, anchor=north, font=\scriptsize] at (1.15,0.9) {s};
    \draw[red, thick] (0.1,0.7) -- (2.3,1.5);
  \end{scope}
\end{tikzpicture}
$$

**A weighted-average example.** Suppose the query state $s$ has three stored
neighbors with target values $g = 10, 6, 2$ at distances $d = 0.5, 1.0, 2.0$. A
common weighting is the Gaussian $k(d) = e^{-d^2/2h^2}$ with bandwidth $h = 1$,
giving weights $e^{-0.125} = 0.882$, $e^{-0.5} = 0.607$, and $e^{-2} = 0.135$. The
weighted average is

$$
\hat v(s) = \frac{0.882\cdot 10 + 0.607\cdot 6 + 0.135\cdot 2}{0.882 + 0.607 + 0.135} = \frac{8.82 + 3.64 + 0.27}{1.624} = \frac{12.73}{1.624} = 7.84.
$$

The nearest neighbor alone would return $10$; the weighted average pulls the
estimate toward $7.84$ by including the two farther examples at diminishing
weight. Shrinking the bandwidth $h$ toward zero recovers pure nearest neighbor
(only the closest example retains weight); growing it toward infinity recovers
the unweighted mean of all three, $6$. The bandwidth is the single parameter
that trades locality against smoothing.

$$
% caption: Bandwidth controls the weighted average. Small $h$ (left) concentrates
% all weight on the nearest example and approaches nearest neighbor; large $h$
% (right) spreads weight evenly and approaches the unweighted mean. The worked
% example ($h=1$) sits between, returning 7.84 for neighbors valued 10, 6, 2.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % small h
  \begin{scope}
    \node[anchor=south, font=\scriptsize] at (1.3,2.3) {small h: near NN};
    \draw[black] (0,0) -- (2.6,0);
    \draw[acc, thick] plot[domain=0.0:2.6, samples=40] (\x, {2.0*exp(-((\x-0.4)^2)/0.06)});
    \foreach \x in {0.4,1.0,2.0} \fill[red] (\x,0) circle (1.8pt);
  \end{scope}
  % medium h
  \begin{scope}[xshift=3.7cm]
    \node[anchor=south, font=\scriptsize] at (1.3,2.3) {h = 1: blend};
    \draw[black] (0,0) -- (2.6,0);
    \draw[acc, thick] plot[domain=0.0:2.6, samples=40] (\x, {2.0*exp(-((\x-0.4)^2)/0.5)});
    \foreach \x in {0.4,1.0,2.0} \fill[red] (\x,0) circle (1.8pt);
  \end{scope}
  % large h
  \begin{scope}[xshift=7.4cm]
    \node[anchor=south, font=\scriptsize] at (1.3,2.3) {large h: near mean};
    \draw[black] (0,0) -- (2.6,0);
    \draw[acc, thick] plot[domain=0.0:2.6, samples=40] (\x, {1.4*exp(-((\x-0.4)^2)/6.0)});
    \foreach \x in {0.4,1.0,2.0} \fill[red] (\x,0) circle (1.8pt);
  \end{scope}
\end{tikzpicture}
$$

Being nonparametric, local methods carry advantages that suit reinforcement
learning particularly well. They are not confined to a pre-chosen functional form,
so accuracy improves as data accumulates. Because
[trajectory sampling](/reinforcement-learning/tabular-methods/planning-and-learning)
concentrates experience on the states actually visited, local methods can focus
their approximation exactly there — there may be no need to approximate the value
of the vast regions of state space the policy never reaches. And a single new
example has an immediate, local effect on estimates in its neighborhood, whereas a
parametric method must incrementally adjust a global approximation into agreement.

Avoiding a global approximation is also a way to blunt the curse of
dimensionality. A tabular method storing a global approximation over a $k$-dimensional
space needs memory exponential in $k$. A memory-based method needs memory
proportional to $k$ per example, so storing $n$ examples is linear in $n$ and
linear in $k$ — nothing is exponential.[^sb-memory] The catch is speed. The
critical question is whether a memory-based method can answer queries fast enough
to be useful, and how retrieval slows as memory grows: finding nearest neighbors
in a large database can be too slow to be practical. Special data structures such
as $k$-d trees, which recursively split the space into regions arranged as a
binary tree, can quickly rule out large regions during a neighbor search and make
retrieval feasible where a naive scan would not be.

## Kernel-based function approximation

The local methods above all assign a weight to each stored example $s' \mapsto g$
based on the distance between $s'$ and the query $s$. The function that assigns
those weights is a **kernel function**, or simply a **kernel**. In the
weighted-average and locally-weighted-regression methods a kernel $k : \mathbb{R}
\to \mathbb{R}$ turns a distance into a weight. More generally the weight need not
depend on distance at all: a kernel $k : \mathcal{S} \times \mathcal{S} \to
\mathbb{R}$ assigns $k(s, s')$ as the weight given to data about $s'$ when
answering a query about $s$. Read this way, $k(s, s')$ measures the **strength of
generalization** from $s'$ to $s$ — how relevant knowledge about one state is to
another.[^sb-kernel]

> **Definition (Kernel function).** A function $k(s, s')$ that quantifies the
> strength of generalization from state $s'$ to state $s$ — the weight given to
> what is known about $s'$ when estimating the value of $s$. When it depends only
> on a distance $\lVert s - s'\rVert$ it is a distance kernel; more generally it
> can express any measure of similarity between states.

**Kernel regression** is the memory-based method that computes a kernel-weighted
average of the targets of _all_ examples in memory, and assigns the result to the
query. If $\mathcal{D}$ is the set of stored examples and $g(s')$ is the target
stored for state $s'$, kernel regression approximates the value function as

$$
\hat v(s, \mathcal{D}) \;=\; \sum_{s' \in \mathcal{D}} k(s, s')\, g(s').
$$

The weighted-average method of the previous section is the special case in which
$k(s, s')$ is nonzero only when $s$ and $s'$ are close, so the sum need not run
over all of $\mathcal{D}$.

$$
% caption: Kernel regression at query $s$. Each stored state $s'$ contributes its
% target $g(s')$ weighted by the kernel $k(s,s')$, which falls off with distance;
% the estimate $\hat v(s) = \sum_{s'} k(s,s')\,g(s')$ is the kernel-weighted
% average, and the bell curve traces how the RBF kernel weights range over states.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % axis
  \draw[black] (-0.3,0) -- (7.6,0) node[anchor=north west, font=\scriptsize] {state};
  % rbf kernel bell centered at query
  \draw[acc, thick] plot[domain=0.4:6.6, samples=60] (\x, {2.3*exp(-((\x-3.5)^2)/1.1)});
  % query point
  \fill[acc] (3.5,0) circle (2.4pt);
  \node[acc, anchor=north, font=\scriptsize] at (3.5,-0.08) {query s};
  % stored examples as ticks with weights (bar heights = kernel value)
  \foreach \x in {1.3,2.4,3.5,4.6,5.7} {
    \fill[red] (\x,0) circle (1.8pt);
    \draw[red, thick] (\x,0) -- (\x,{2.3*exp(-((\x-3.5)^2)/1.1)});
  }
  \node[red, anchor=west, font=\scriptsize] at (5.85,0.55) {stored states weighted by kernel};
  \node[acc, anchor=west, font=\scriptsize] at (4.8,2.05) {RBF kernel};
\end{tikzpicture}
$$

### RBF kernels and the kernel trick

A common choice is the Gaussian **radial basis function** (RBF) kernel. In the RBF
_features_ of the previous lesson, the RBFs were parametric: a fixed set of bumps
with pre-placed centers, whose _weights_ were learned by gradient descent. Kernel
regression with an RBF kernel differs on both counts. It is **memory-based** — the
RBFs are centered on the states of the stored examples, not on a fixed grid — and
it is **nonparametric** — there are no weights to learn, the response to a query
coming directly from the kernel-weighted sum above.[^sb-kernel]

The deeper point is that _any_ linear parametric method can be recast as a kernel
method. Take states represented by feature vectors $\mathbf{x}(s) = (x_1(s),
\dots, x_d(s))^\top$, exactly the linear setup of the previous lesson. That method
can be recast as kernel regression with the kernel

$$
k(s, s') \;=\; \mathbf{x}(s)^\top \mathbf{x}(s'),
$$

the inner product of the two states' feature vectors. Kernel regression with this
kernel produces the **same** approximation the linear parametric method would,
trained on the same data. The implication runs the other way too: instead of
constructing features and taking inner products, one can specify a kernel $k(s,
s')$ directly, never mentioning feature vectors at all. This is the **kernel
trick**. For many feature sets, $\mathbf{x}(s)^\top
\mathbf{x}(s')$ has a compact closed form that can be evaluated **without ever
computing in the high-dimensional feature space** — effectively working in an
expansive (even infinite-dimensional) feature space while touching only the stored
examples. When the feature space is large, kernel regression can be far cheaper
than the equivalent linear parametric method.[^sb-kernel]

$$
% caption: The kernel trick. A linear method maps each state to a
% high-dimensional feature vector $\mathbf{x}(s)$ and takes an inner product;
% the kernel $k(s,s') = \mathbf{x}(s)^\top\mathbf{x}(s')$ computes that same
% quantity directly from $s$ and $s'$, skipping the feature space entirely.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=20mm, minimum height=10mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box] (s) at (0,0) {two states\\s and t};
  \node[box] (feat) at (3.6,1.3) {features\\x(s), x(t)};
  \node[box] (ip) at (7.4,1.3) {inner product\\x(s) . x(t)};
  \node[box, draw=acc, text=acc] (k) at (7.4,-1.1) {kernel k(s,t)};
  \draw[->, black, thick] (s) -- (feat) node[midway, above, font=\scriptsize] {map (costly)};
  \draw[->, black, thick] (feat) -- (ip);
  \draw[->, acc, thick] (s) to[bend right=18] (k);
  \node[acc, anchor=north west, font=\scriptsize] at (2.6,-0.7) {direct: skip the feature space};
\end{tikzpicture}
$$

Not every kernel arises as an inner product of features, but any kernel that
_can_ be written this way inherits the parametric method's approximation while
potentially costing far less. The kernel trick underlies a great deal of machine
learning — support vector machines and Gaussian processes most prominently — and
it has been shown to benefit reinforcement learning as well.

## Interest and emphasis

One more assumption ran through the previous lesson: all states encountered are
treated as **equally important**. Every algorithm updated states in proportion to the on-policy
distribution $\mu$, and function-approximation resources — always limited — were
spread evenly across them. Often that is wrong. In a discounted episodic problem
we may care far more about valuing early states accurately than late ones whose
rewards, heavily discounted, barely affect the start state's value. In an
action-value setting we may care little about the precise value of poor actions
far below the greedy one. If the limited approximation resources could be aimed at
the states that matter, performance would improve.[^sb-emphasis]

The reason all states were weighted equally is that doing so, according to the
on-policy distribution, is where the stronger convergence results for
semi-gradient methods hold. Interest and emphasis generalize that distribution
rather than discard it. Introduce a non-negative scalar random variable $I_t$, the
**interest**, measuring how much we care about accurately valuing the state (or
state–action pair) at time $t$: zero if we do not care at all, larger where we
care more, set in any causal way — it may depend on anything up to time $t$. The
weighting $\mu$ in the objective $\overline{VE}$ is then redefined as the
distribution of states encountered while following the target policy, **weighted
by interest**. Second, introduce another non-negative scalar, the **emphasis**
$M_t$, which multiplies the learning update and so emphasizes or de-emphasizes the
learning done at time $t$. The general $n$-step update becomes

$$
\mathbf{w}_{t+n} \;\doteq\; \mathbf{w}_{t+n-1} + \alpha\, M_t\,\big[G_{t:t+n} - \hat v(S_t, \mathbf{w}_{t+n-1})\big]\,\nabla \hat v(S_t, \mathbf{w}_{t+n-1}),
\qquad 0 \le t < T,
$$

with the emphasis determined recursively from the interest by

$$
M_t \;=\; I_t + \gamma^n M_{t-n},
\qquad 0 \le t < T,
$$

taking $M_t = 0$ for all $t < 0$. Emphasis is not just the interest at $t$: it
accumulates a discounted echo of the interest at states that **bootstrap through**
$t$. A state whose interest is zero can still receive nonzero emphasis if an
interesting state's estimate depends, through bootstrapping, on it.[^sb-emphasis]

> **Definition (Interest and emphasis).** The **interest** $I_t \ge 0$ specifies
> how much accurate valuation of the state at time $t$ matters, redefining the
> weighting $\mu$ in $\overline{VE}$; the **emphasis** $M_t = I_t + \gamma^n
> M_{t-n} \ge 0$ scales that step's update. Emphasis propagates interest backward
> through bootstrapping, so states that feed an interesting estimate are learned
> even if their own interest is zero.

$$
% caption: A four-state Markov reward process. Interest is 1 only at the leftmost
% state ($I=1$) and 0 elsewhere; each transition earns reward +1 to a terminal
% state (gray). True values decrease left to right; the parameterization ties the
% first two states to one weight and the last two to another.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  st/.style={circle, draw, minimum size=9mm, inner sep=0pt, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[st, draw=acc, text=acc] (a) at (0,0) {w1};
  \node[st] (b) at (2.4,0) {w1};
  \node[st] (c) at (4.8,0) {w2};
  \node[st] (d) at (7.2,0) {w2};
  \node[draw, minimum size=7mm, fill=black!12] (t) at (9.4,0) {};
  \draw[->, black] (a) -- (b) node[midway, above, font=\scriptsize] {+1};
  \draw[->, black] (b) -- (c) node[midway, above, font=\scriptsize] {+1};
  \draw[->, black] (c) -- (d) node[midway, above, font=\scriptsize] {+1};
  \draw[->, black] (d) -- (t) node[midway, above, font=\scriptsize] {+1};
  \node[acc, anchor=south, font=\scriptsize] at (0,0.7) {I = 1};
  \foreach \x in {2.4,4.8,7.2} \node[anchor=south, font=\scriptsize] at (\x,0.7) {I = 0};
  \foreach \x/\v in {0/4, 2.4/3, 4.8/2, 7.2/1} \node[anchor=north, font=\scriptsize] at (\x,-0.7) {v = \v};
\end{tikzpicture}
$$

### How emphasis sharpens estimates

The four-state process above shows the effect. Episodes start at the left and step
right, reward $+1$ each step, so the true values are $4, 3, 2, 1$. The
parameterization has only two weights: the first two states share $w_1$, the last
two share $w_2$. No setting of $(w_1, w_2)$ can be right everywhere, so the method
must choose which states to fit. Suppose interest is $1$ at the leftmost state
alone and $0$ at the other three.[^sb-emphasis]

Without interest and emphasis, gradient Monte Carlo converges to $\mathbf{w}_\infty
= (3.5, 1.5)$ — $w_1 = 3.5$ splits the difference between the true $4$ and $3$ of
the first two states, giving the state we actually care about a value $3.5$ rather
than its correct $4$. The methods **with** interest and emphasis instead learn
$w_1 = 4$ exactly, valuing the interesting first state correctly, and never update
$w_2$ at all because emphasis is zero at every state but the leftmost. The
two-step semi-gradient TD case is sharper still: without emphasis it again reaches
$(3.5, 1.5)$; with emphasis it converges to $\mathbf{w}_\infty = (4, 2)$, exactly
correct at both the first state _and_ the third state — because the first state
bootstraps from the third, emphasis flows back to it, and both get valued
correctly even though the interest at the third state was zero.

$$
% caption: With versus without emphasis on the four-state process. Ordinary
% learning settles on $w_1 = 3.5$ (dashed), a compromise between true values 4 and
% 3; interest and emphasis pin $w_1 = 4$ (blue) — exact at the one state that
% matters — and, under two-step TD, pull the bootstrapped third state to its
% correct value too.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \draw[->, black] (0,0) -- (0,4.4) node[anchor=south east, font=\scriptsize] {value of state 1};
  \draw[black] (-0.1,0) -- (6.4,0);
  % true value reference
  \draw[black, dashed] (0,4.0) -- (6.2,4.0);
  \node[anchor=west, font=\scriptsize] at (6.25,4.0) {true v = 4};
  % without emphasis (compromise 3.5)
  \fill[red] (1.7,3.5) circle (2.6pt);
  \node[red, anchor=south, font=\scriptsize] at (1.7,3.6) {no emphasis: 3.5};
  \draw[red, dashed] (0,3.5) -- (1.7,3.5);
  % with emphasis (exact 4)
  \fill[acc] (4.4,4.0) circle (2.6pt);
  \node[acc, anchor=north, font=\scriptsize] at (4.4,3.88) {emphasis: 4.0};
\end{tikzpicture}
$$

Emphasis, then, is the on-policy weighting made adjustable. The equal weighting
assumed everywhere in the previous lesson is the special case $I_t = 1$ for all
$t$, which reduces $M_t$ to the on-policy distribution and recovers the ordinary
methods exactly. Setting some interests to zero concentrates the same limited
approximation capacity on the states that matter, and the recursion $M_t = I_t +
\gamma^n M_{t-n}$ ensures the states those states bootstrap from are learned along
with them.

## Gaussian processes and experience replay

The kernel and memory threads run well past Sutton and Barto. Treating the value function
as a draw from a **Gaussian process** turns kernel regression into a Bayesian
method that returns a full posterior — a value estimate _and_ a calibrated
uncertainty — at every query. Gaussian-process temporal-difference learning (Engel, Mannor, and Meir
2005, _ICML_, "Reinforcement Learning with Gaussian Processes") builds exactly this,
using the kernel to encode generalization between states and the posterior variance
to drive exploration toward states the model is unsure about.[^gptd] The same
GP-with-kernel machinery underlies **PILCO** (Deisenroth and Rasmussen 2011, _ICML_,
"PILCO: A Model-Based and Data-Efficient Approach to Policy Search"), a model-based
method that learns a GP dynamics model and remains one of the most sample-efficient
continuous-control algorithms known — a direct descendant of the kernel view that
any linear feature method is a kernel method.[^pilco]

Memory-based, lazy learning is also the ancestor of **experience
replay** (Lin 1992, "Self-improving reactive agents"), the technique of storing
past transitions in a buffer and re-drawing them to train an off-policy learner. Deep
Q-networks (Mnih et al. 2015, _Nature_) made replay standard practice — storing raw
transitions and reusing them is the same "keep the examples, process them at query
time" idea that defines memory-based approximation, moved from the value estimate to
the training loop.[^replay]

## Where this leaves us

Dropping the parametric commitment gives a different kind of flexibility. Memory-based
methods store the examples and answer queries locally, so accuracy grows with the
data and effort concentrates where trajectory sampling actually puts the agent.
Kernel methods systematize the local weighting into a kernel $k(s,s')$ and, through
the kernel trick, work implicitly in vast feature spaces while touching only stored
examples; every linear method is itself a kernel method. Interest
and emphasis make the on-policy weighting itself a design choice, aiming scarce
approximation capacity at the states that matter.

| Axis | Options | Trade |
| --- | --- | --- |
| Parametric vs. nonparametric | fixed $\mathbf{w}$ vs. stored examples | capacity fixed vs. grows with data |
| Global vs. local | one $\hat v$ everywhere vs. per-query fit | generalizes broadly vs. focuses where visited |
| Feature vs. kernel | $\mathbf{w}^\top\mathbf{x}(s)$ vs. $k(s,s')$ | explicit features vs. implicit similarity |

Across both halves of this pair, data efficiency can be traded for compute, as
in LSTD, or for memory, as in kernel and memory-based methods; the right point
on that curve depends on which resource is scarce. From here the subject leaves on-policy prediction for control at scale and
the
[deadly triad](/reinforcement-learning/approximation/off-policy-and-the-deadly-triad),
where combining approximation, bootstrapping, and off-policy training can make even
these carefully weighted methods diverge.

[^sb-memory]: **Sutton & Barto**, §9.9 — Memory-based Function Approximation: parametric versus memory-based (lazy) learning; nonparametric methods; local-learning methods — nearest neighbor, weighted average, and locally weighted regression; the advantages for trajectory-sampled RL and against the curse of dimensionality (memory linear in $k$ and $n$); and the retrieval-speed concern with $k$-d trees.
[^sb-kernel]: **Sutton & Barto**, §9.10 — Kernel-based Function Approximation: the kernel function $k(s,s')$ as strength of generalization; kernel regression $\hat v(s,\mathcal{D}) = \sum_{s'} k(s,s')g(s')$ (9.23); the RBF kernel as memory-based and nonparametric; the recasting of any linear parametric method as kernel regression with $k(s,s') = \mathbf{x}(s)^\top\mathbf{x}(s')$ (9.24); and the kernel trick working in high-dimensional feature spaces at low cost.
[^sb-emphasis]: **Sutton & Barto**, §9.11 — Looking Deeper at On-policy Learning: Interest and Emphasis: the interest $I_t$ redefining $\mu$ in $\overline{VE}$; the emphasis $M_t$ scaling the update (9.25) with the recursion $M_t = I_t + \gamma^n M_{t-n}$ (9.26); and Example 9.4, the four-state Markov reward process where interest and emphasis recover the exact value of the leftmost state (and, under two-step TD, the bootstrapped third state).
[^gptd]: **Engel, Mannor, and Meir (2005)**, "Reinforcement Learning with Gaussian Processes", _ICML_: models the value function as a Gaussian process, using the kernel to encode state generalization and the posterior variance as a calibrated uncertainty for exploration — a Bayesian form of the kernel regression this lesson describes.
[^pilco]: **Deisenroth and Rasmussen (2011)**, "PILCO: A Model-Based and Data-Efficient Approach to Policy Search", _ICML_: learns a Gaussian-process model of the environment dynamics and optimizes a policy through it; among the most sample-efficient continuous-control methods, built on the same GP-with-kernel machinery.
[^replay]: **Lin (1992)**, "Self-Improving Reactive Agents Based on Reinforcement Learning, Planning and Teaching", _Machine Learning_ 8: introduces experience replay, storing past transitions and re-drawing them for training. **Mnih et al. (2015)**, "Human-level control through deep reinforcement learning", _Nature_ 518: makes replay standard practice in deep Q-networks — a training-loop analogue of memory-based, lazy learning.