Memory-Based and Kernel Methods

This builds on least-squares TD 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.¹

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.

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^{\prime }\mapsto g$ is the example in memory whose state $s^{\prime }$ 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.¹

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

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.

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 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.¹ 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^{\prime }\mapsto g$ based on the distance between $s^{\prime }$ 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^{\prime })$ as the weight given to data about $s^{\prime }$ when answering a query about $s$. Read this way, $k(s,s^{\prime })$ measures the strength of generalization from $s^{\prime }$ to $s$ — how relevant knowledge about one state is to another.²

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^{\prime })$ is the target stored for state $s^{\prime }$, kernel regression approximates the value function as

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

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

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

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^{\prime })$ directly, never mentioning feature vectors at all. This is the kernel trick. For many feature sets, $\mathbf{x}(s{)}^{\top }\mathbf{x}(s^{\prime })$ 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.²

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

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

with the emphasis determined recursively from the interest by

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

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

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.

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

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

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^{\prime })$ 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.

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, where combining approximation, bootstrapping, and off-policy training can make even these carefully weighted methods diverge.