Nearest Neighbor Action Selection and Value Estimation

48 concepts38 papers2 proposals

Deep neural networks are remarkably powerful at generalizing patterns, but they suffer from a fundamental limitation: they are parametric. They compress an agent's entire history of interactions into a fixed set of weights via gradient descent. This compression creates a slow-learning bottleneck. When an agent discovers a rare, high-reward state, a parametric network requires thousands of optimization steps to propagate that reward signal backward through its policy. Furthermore, when faced with distribution shifts, gradient updates risk catastrophic forgetting—erasing old skills to acquire new ones.

To bypass this bottleneck, a growing body of research advocates for a non-parametric approach to decision-making and value estimation. Instead of compressing experiences exclusively into weights, these systems store raw historical transitions—states, actions, and rewards—directly in an explicit memory buffer.

When an agent encounters a new state, it does not rely solely on a neural network's global extrapolation. Instead, it uses an embedding model to perform a similarity search (such as a $k$-nearest neighbor lookup) across its memory bank. The agent then estimates the value of a potential action or selects its next move by interpolating the outcomes of the most similar past experiences. This paradigm shifts the burden of adaptation from slow, offline weight updates to fast, online retrieval.

As Samuel Ritter et al. demonstrate in Rapid Task-Solving in Novel Environments, maintaining a high-fidelity record of state transitions allows an agent to instantly exploit the structure of a newly explored environment without compressing it into a fixed-size hidden state.

Instantaneous Learning and Value Propagation

In environments with sparse rewards, finding a successful sequence of actions is rare. In a purely parametric model, the reward signal from a single successful trajectory takes many training epochs to diffuse through the network.

Non-parametric value estimation solves this by allowing immediate replication of successful behaviors. In Continuous Episodic Control, Zhao Yang et al. show that storing state-action pairs alongside their cumulative discounted rewards enables an agent to repeat high-reward actions the very next time a similar state is encountered.

Similarly, Xue Yan et al. in Memory-Driven Self-Improvement for Decision Making with Large Language Models demonstrate that experience retrieval allows agents to learn from rare successful events instantly, allowing small memory buffers to outperform standard deep Q-networks that rely on gradient updates.

This immediate propagation can also be structured sequentially. Xiaoteng Ma et al. utilize this in Offline Reinforcement Learning with Value-based Episodic Memory by recursively propagating value information along recorded trajectories in memory, bypassing the need for a learned transition model and accelerating value convergence.

Staying on the Manifold of Valid Behaviors

Parametric models are notorious for extrapolation error—predicting wildly inaccurate values or generating erratic actions when faced with states slightly outside their training distribution. Non-parametric retrieval anchors the agent's decisions in actual historical data.

Consider visual imitation learning in robotics. In The Surprising Effectiveness of Representation Learning for Visual Imitation, Jyothish Pari et al. show that a simple $k$-nearest neighbor lookup over a library of human demonstrations outperforms complex end-to-end neural policies. When the robot encounters an unfamiliar visual state, retrieving and averaging actions from the closest training examples keeps the agent firmly on the manifold of valid behaviors, preventing the catastrophic failures common to parametric extrapolation.

This grounding effect also applies to predicting the future. Generative world models often suffer from compounding errors and hallucinations over long horizons. To fix this, Federico Malato et al. introduce a zero-shot world model in Zero-shot World Models via Search in Memory that models environment dynamics simply by retrieving the most similar past transitions from a memory buffer, replacing generative transition functions with real historical data.

Hybrid Architectures: Decoupling Stability from Plasticity

The most powerful implementations of this idea do not discard parametric models entirely; instead, they combine them into semiparametric or hybrid architectures. This design decouples stable, long-term representation learning from rapid, runtime adaptation.

For instance, Mika Sarkin Jain et al. propose a value estimation architecture in Semiparametric Reinforcement Learning that pairs a non-parametric $k$-nearest neighbor lookup with a parametric neural network. The neural network is trained solely to predict a correction term for the retrieved values, smoothing out the raw episodic data. Similarly, Steven Hansen et al. augment parametric networks with non-parametric memory in Fast deep reinforcement learning using online adjustments from the past. to refine value estimates during action selection, achieving rapid adaptation without immediate gradient updates.

This hybrid approach is highly effective for scaling up complex agents and combinatorial solvers at inference time:

By shifting from global function approximation to local, retrieval-driven generalization, non-parametric value estimation provides a mathematically simple yet highly efficient path toward sample-efficient, robust, and rapidly adaptable intelligent agents.

Key Foundational Work

Fast, Robust Adaptive Control by Learning only Forward Models (1991) — contributed 1 concept elements to this direction.
Instance-Based State Identification for Reinforcement Learning (1994) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_non_parametric_value_estimation_031f1f2c,
  title = {non-parametric value estimation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-parametric-value-estimation/rdr_031f1f2c4da044d286ba5eda6f9d42ea},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_non_parametric_value_estimation_031f1f2c_v1,
  title = {non-parametric value estimation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-parametric-value-estimation/rdr_031f1f2c4da044d286ba5eda6f9d42ea/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake