Related Work
Uncertainty Estimation
Bayesian approximations, deep ensembles, and selective prediction yield uncertainty or abstention scores, while classical robotics represents and propagates probabilistic states. These methods do not generally provide distribution-free finite-sample coverage at a chosen error level.
Problem Formulation
This section formulates vision-and-language navigation as sequential classification in a discrete graph, defines the three nonconformity scores used in commonly used conformal prediction, and shows why calibration over pooled steps does not yield trajectory-level coverage. An experimental condition is one policy–dataset pair.
Why Split Conformal Prediction Degenerates Here
Split conformal prediction assumes that calibration and test scores are exchangeable. However, exchangeability at the level of complete episodes does not generally entail exchangeability of the individual time steps obtained by pooling steps across episodes.
Within an episode, time steps are statistically dependent due to their shared action–observation history; episode lengths may differ; and actions can causally influence subsequent observations, further violating step-wise exchangeability. Moreover, marginal coverage guarantees for a single time step do not imply simultaneous coverage across all time steps within an episode.
Accordingly, the subsequent section defines a mapping from each episode to a single calibration score.
One Calibration Score per Episode
For calibration episode [the calibration episode] of length [the episode length], episode-normalized conformal prediction computes [one calibration score for the episode].
Every episode contributes one number, regardless of its length. Exchangeability across episodes is required, but no such assumption is made about steps within an episode.
For parameter-free episode-normalized conformal prediction, bounding the maximum bounds every step and gives simultaneous trajectory coverage (Theorem 1). The maximum is zero only when all step scores are zero. This condition makes a zero threshold less common than under step-pooled calibration (Proposition 1).
Experiments
The experiments report step coverage, the mean fraction of covered steps per episode. Set sizes include the argmax fallback, whereas coverage uses the set in the specified prediction-set definition; an empty raw set is uncovered.
Simulated Help-Seeking with Episode-Normalized Conformal Prediction
We test one use of episode-normalized conformal prediction at deployment: the agent acts when [the prediction set meets the action condition] and asks for help when [the prediction set meets the help-seeking condition]. A larger set therefore causes the agent to defer.
This experiment simulates help-seeking without human operators. When episode-normalized conformal prediction requests help because [the help-seeking condition is met], the agent executes the ground-truth action supplied by the simulator instead of its policy-selected action. The simulator has access to the goal and complete navigation graph and is assumed to make no errors.
This experiment does not select a deployment threshold. The threshold is swept after observing the validation-unseen split, and the same [threshold] produces different ask rates for policies with different set-size distributions.
The intervention also changes later observations, so the static episode-normalized conformal prediction coverage result does not certify the assisted trajectories.
Frequently Asked Questions
What problem does episode-normalized conformal prediction address? It addresses the failure of pooled step-wise calibration to provide trajectory-level coverage in vision-and-language navigation.
Why are steps within an episode not treated as exchangeable? They share action–observation histories, episode lengths may differ, and actions can causally influence later observations.
How does episode-normalized calibration summarize an episode? It assigns every calibration episode one calibration score, regardless of episode length.
How is the method used for simulated help-seeking? The agent acts or asks for help according to its prediction set, with the simulator supplying the ground-truth action when help is requested.