← Paper Digest

Racing the Clock: Teaching VLNs Budget-Conditioned Object Search

Maitree Meher, Siming He, S. Shankar Sastry, Jitendra Malik, Claire Tomlin, Jonas Frey

November 2026

TL;DR The authors fine-tune the Uni-NaVid navigation model to find as many target objects as it can within a step budget stated in the instruction. It learns from a room-level planner that cannot see inside unexplored rooms. On held-out HM3D scenes it finds 72.7% of reachable targets at 2000 steps, versus 65.5% when trained on a planner that knows every target location and 44.8% for the pretrained model.

What they do

Vision-language navigation (VLN) models are usually run under a step limit they never see. This paper defines budget-conditioned object search: given a target category and a countdown of remaining steps in the instruction, find as many distinct instances as possible. It then asks which expert a VLN should imitate. An expert that knows where every target is plans near-optimal routes. But its turns depend on objects the student cannot see, so a student imitating it learns an average over scenes it cannot tell apart.

How it works

  • Budget as text. Uni-NaVid sees RGB video history and an instruction such as “Find as many chairs as possible. You have b steps remaining,” with no architecture change. An object counts as found within 1.5 m and inside the camera’s field of view.
  • Two Bellman experts apply one budget-indexed recursion to different scene abstractions. The object-level expert knows all target locations and solves budgeted routing. The room-level expert knows only entered rooms and objects visible through doorways. It values unexplored rooms from outcomes recorded in 181 other HM3D scenes.
  • Distillation. Each expert fine-tunes a separate Uni-NaVid on matched scenes, budgets and record counts (388,199 records). A greedy frontier explorer supplies a third set of demonstrations.

Results

  • With all target locations, the object-level expert collects 91.3% at B = 150 versus 45.7% for the room-level expert. The gap shrinks to 2.0 points at B = 2000.
  • Students reverse this order. Room-level supervision gives the highest collection at every budget: 72.7% at B = 2000 versus 68.5% (frontier), 65.5% (object-level) and 44.8% (pretrained).
  • Changing only the countdown from 150 to 2000 changed the route in all six probe pairs, after 2-11 actions.
  • Zero-shot on a quadruped in a home with 14 chairs, mean chairs found rose from 3.4 at B = 50 to 9.2 at B = 2000 (5 runs each).

Limitations

At B = 2000 the student stays well below its expert (72.7% vs 98.0%). The non-learned frontier explorer beats every VLN from B = 800 on, and 92-93% of the student’s forward moves revisit cells it has already crossed. The room-level expert reads room types from simulator annotations. The two experts differ in both decision unit and information access, and the experiments do not separate the two.

Figures

From Figure 1: The learned policy rolled out from the same start in a held-out HM3D scene, with only the stated budge...
From Figure 1: The learned policy rolled out from the same start in a held-out HM3D scene, with only the stated budget changed. At B = 50/150/400/800/2000 it collects 4/11/10/12/12 of 13 reachable chairs.
From Figure 2: The room-level Bellman expert. (a) Only entered rooms are known, with the objects discovered in them. ...
From Figure 2: The room-level Bellman expert. (a) Only entered rooms are known, with the objects discovered in them. (b) Frontier rooms are valued from objects visible through the doorway and cross-scene Bellman estimates. (c) A visible target can interrupt a room sweep, after which the expert replans.
From Figure 3: (a) Expert collection with 95% bootstrap intervals: the object-level expert leads the room-level exper...
From Figure 3: (a) Expert collection with 95% bootstrap intervals: the object-level expert leads the room-level expert, which leads the frontier baseline. (b) After matched Uni-NaVid fine-tuning, the order of the two Bellman experts reverses.
From Figure 4: Real-robot routes in a multi-room home at budgets of 50, 150, 400 and 2000 steps, overlaid on the lida...
From Figure 4: Real-robot routes in a multi-room home at budgets of 50, 150, 400 and 2000 steps, overlaid on the lidar map. At B = 50 the robot searches near its start; larger budgets send it first toward the family room and kitchen.
Abstract

A rescue robot entering a building with thirty seconds on the clock should sprint toward the single most promising room; given ten minutes, it should instead explore a broader tour. Yet vision-language-navigation (VLN) models are typically evaluated under a fixed episode limit that the policy never observes, even though time-critical missions require behavior to adapt to the available budget. We study budget-conditioned object search: given a target category and an explicit action budget, an agent must find as many distinct target instances as possible before the budget expires. We investigate how to supervise VLNs for this task by comparing a privileged TSP expert, which plans near-optimal routes using the full map and true target locations, with a room-level Bellman expert that maximizes expected return under partial observability using high-level cross-scene semantic priors. Despite the TSP expert achieving substantially higher expert performance, its demonstrations are less effective for learning exploration: on held-out HM3D scenes, the Bellman-supervised VLN consistently outperforms the TSP-supervised VLN, with the advantage becoming more pronounced at longer budgets. At 2000 steps (500m), the Bellman-supervised VLN finds 71.4% of reachable target instances, compared with 65.5% for the TSP-supervised VLN and 44.8% for the pretrained VLN. These results highlight a distinction between optimal routing and optimal exploration: effective exploration supervision should optimize decisions under partial observability rather than imitate routes that are optimal only once the environment is fully known.

Summaries are written automatically from each paper's text. Figures and videos come from the paper and its project page; all credit goes to the authors.