---
kind: concept
slug: farthest-point-sampling
title: Farthest-point sampling
summary: >-
  Greedy selection of a spread-out subset: start from one point, then repeatedly add the point farthest from the chosen set. One paper (author-reported) applies it to the actions in replayed episodes to pick subgoal states for a goal-conditioned world model. The paper leaves the distance metric and start rule open, and its released code uses FPS for only one of several subgoal strategies.
tags: [sampling, subgoal-selection, reinforcement-learning, world-models]
papers: ["2411.02446"]
related: [goal-conditioned-reinforcement-learning, model-based-reinforcement-learning, world-model, experience-replay]
status: draft
updated_at: 2026-10-25
---

## Overview

Farthest-point sampling (FPS) picks a subset of N points from a larger set so
that the chosen points are spread out. It is greedy. It starts from one point,
then repeatedly adds the point whose distance to the chosen set is largest. The
paper calls it the standard greedy algorithm for this job [arxiv:2411.02446
app. E.1].

FPS is used here as a subroutine. The paper does not run it on states. It runs
it on the actions of a batch of recorded steps, then keeps the states at the
chosen steps [arxiv:2411.02446 §3.2]. The output is therefore a set of
milestone states, not a set of actions.

This page covers one paper so far. Only one card in this wiki lists the slug,
so there is one variant below, plus one ablation that replaces FPS with a
fixed rule.

## Variants

### Action-space subgoal selection (DAD)

The paper calls this selection rule DAD. It takes recent episodes that used an
environment goal, flattens the actions of all their steps into one pool, runs
FPS on that pool, and keeps the states at the chosen steps as subgoals
[arxiv:2411.02446 §3.2] [alg. 2]. The authors argue that large action changes
mark milestones such as closing the gripper, grasping, lifting and releasing a
block [arxiv:2411.02446 §3.2]. Card:
[Learning World Models for Unconstrained Goal Navigation](/papers/2411.02446).

- **Candidate pool.** The released configs draw a batch of 45 episodes of 50
  steps in most task blocks, which gives about 2250 candidate steps per call.
  The paper does not state the pool size [arxiv:2411.02446 app. E.1].
- **Number chosen.** Table 2 sets 20 subgoals for five of the six simulated
  tasks and 10 for the sixth [arxiv:2411.02446 tab. 2].
- **Distance.** The paper does not state the metric [arxiv:2411.02446 app.
  E.1]. The card's Pitfalls section records the released code's choice.
- **Refresh.** The paper says the subgoal set is refreshed periodically, with
  no rate given [arxiv:2411.02446 alg. 1].
- **Limitation the authors name.** When the action space is complex or weakly
  tied to the goal space, DAD can select irrelevant states and this degrades
  the method [arxiv:2411.02446 app. B].

### Fixed-interval subgoals (ablation, no FPS)

MUN-noDAD replaces FPS with states taken at evenly spaced times in the sampled
episodes [arxiv:2411.02446 app. D.5] [alg. 8]. It keeps the rest of the
method. It is the paper's own control for the selection rule, and it is the
only other option on this page.

## When to use which

| Situation | Use | Why |
|---|---|---|
| Recorded actions show clear changes at task milestones | FPS over actions (DAD) | The paper's argument for action changes [arxiv:2411.02446 §3.2]. Its ablation favours DAD on three navigation tasks: 95 vs 81 on 3-Block, 96 vs 89 on Ant Maze, 89 vs 73 on Walker, author-reported [arxiv:2411.02446 tab. 3] [tab. 4] [tab. 5]. |
| Actions are high-dimensional or weakly related to the goal | Check the subgoals before relying on them | The authors name this as a failure case for DAD [arxiv:2411.02446 app. B]. |
| Compute or wall-clock time is the bottleneck | Plan for the full cost | One MUN run took 36 to 70 GPU hours on an A100 [arxiv:2411.02446 tab. 1] [app. E.2]. The card has no comparable cost for the fixed-interval variant. |
| You need results beyond simulation | Not covered | All evaluated tasks are simulated [arxiv:2411.02446 app. C]. |

## Implementation sketch

The core is greedy selection over a pool of vectors. Variants differ in what
the vectors are (actions here), how the distance is measured, and how the
chosen indices are mapped back to states.

```pseudocode
# Farthest-point sampling  [arxiv:2411.02446 app. E.1]
# Metric and start rule are not fixed by the paper

def farthest_point_sampling(points, num_samples):
    # Start from a random point  [arxiv:2411.02446 app. E.1]
    chosen = [random_index(len(points))]
    # Distance from each point to its nearest chosen point
    min_dist = distance(points, points[chosen[0]])
    for _ in range(num_samples - 1):
        # Take the point farthest from every chosen point
        nxt = argmax(min_dist)
        chosen.append(nxt)
        # Update each point's distance to its nearest chosen point
        min_dist = minimum(min_dist, distance(points, points[nxt]))
    return chosen  # indices into points
```

For DAD, `points` holds the flattened actions of the batch. The returned
indices are step numbers, so the caller keeps the state recorded at each step
as a subgoal [arxiv:2411.02446 alg. 2]. The paper's `eta` map is the identity
in this setting [arxiv:2411.02446 §2].

## Contradictions

- **Where FPS is used.** The paper describes DAD as the subgoal method for all
  tasks [arxiv:2411.02446 §3.2] [alg. 2]. The released code uses a different
  selection strategy for the 3-Block, Walker and Block Rotation configs, and
  implements FPS in only one of its strategies. The paper does not say which
  strategy produced its 3-Block figures. Details are in the card's
  [Paper vs code](/papers/2411.02446) section.
- **Stopping early.** The paper's pseudocode returns the requested number of
  points [arxiv:2411.02446 app. E.1]. The released code can return fewer, when
  the largest remaining distance falls below a small threshold. The card's
  [Pitfalls](/papers/2411.02446) section records this.

## Papers

- [Learning World Models for Unconstrained Goal Navigation](/papers/2411.02446):
  introduces DAD, which uses FPS over action vectors to choose subgoal states
  for training a goal-conditioned world model.