ENCP: Episode-Normalized Conformal Prediction for Vision-and-Language Navigation

Technical Summary: Episode-Normalized Conformal Prediction (ENCP) for Vision-and-Language Navigation

1. Problem Statement

Vision-and-Language Navigation (VLN) enables embodied agents to navigate physical environments using natural language instructions. A critical challenge in deploying these agents safely is uncertainty estimation. Sequential navigation is prone to compounding errors; a single incorrect action alters the agent's state and subsequent observations, potentially leading to task failure or physical collisions.

While modern VLN policies achieve high success rates, standard confidence metrics (e.g., softmax probabilities) are often uncalibrated and overconfident, particularly when deployment environments differ from training data. Existing self-monitoring mechanisms rely on empirical heuristics rather than formal guarantees.

Conformal Prediction (CP) offers a statistical framework to generate prediction sets with guaranteed coverage (i.e., the set contains the ground-truth action with probability $1-\alpha$). However, standard CP assumes exchangeable data points. In VLN, this assumption fails because:

1. Step Dependence: Actions within a single episode are statistically dependent due to shared history and causal influence on future observations.
2. Variable Length: Episodes have different lengths.
3. Failure of Step-Pooled Calibration: Applying standard CP to individual steps (pooled across episodes) fails to provide a guarantee that the correct action is included at every step of a route. It often undercovers, meaning the actual error rate exceeds the target risk level $\alpha$.

2. Methodology: Episode-Normalized Conformal Prediction (ENCP)

The authors propose ENCP, a post-training framework that leaves the underlying navigation policy unchanged. ENCP addresses the dependence and variable-length issues by shifting the calibration unit from individual steps to complete episodes.

Core Mechanisms:

1. Episode-Level Calibration: Instead of calibrating on a pool of individual steps, ENCP aggregates the nonconformity scores of all steps within a single episode into a single scalar value. Specifically, it computes the maximum normalized nonconformity score across the entire episode. This single value represents the "worst-case" deviation for that trajectory.
2. Confidence-Adjusted Score Normalization: To handle varying policy confidence across steps, ENCP rescales the base nonconformity score ($s_{base}$) by the policy's residual confidence.
   • Parameter-free variant: Uses a fixed weight $w(x_t) = 1 - p_{max}(x_t)$, where $p_{max}$ is the highest probability assigned by the policy. The normalized score is:
     $$s_{norm}(x_t, a) = \frac{s_{base}(x_t, a)}{1 + (1 - p_{max}(x_t))} = \frac{s_{base}(x_t, a)}{2 - p_{max}(x_t)}$$
   • Learning-based variant: Uses a neural network to predict weights based on features like entropy, probability gaps, and step index, trained to identify steps where the policy is confident but incorrect.
3. Prediction Set Generation:
   • A conformal threshold $\hat{q}(\alpha)$ is calculated from the distribution of the episode-level maximum scores on a calibration set.
   • At test time, for each step $t$, the prediction set $C_\alpha(x_t)$ includes all actions $a$ where $s_{norm}(x_t, a) \le \hat{q}(\alpha)$.
   • Act-or-Ask Rule: If the size of the prediction set $|C_\alpha(x_t)|$ exceeds a user-defined budget $\tau$, the agent requests human assistance (or defers to a simulator). Otherwise, it proceeds autonomously.

Theoretical Guarantee:
Under the assumption that calibration and test episodes are exchangeable (e.g., drawn from the same distribution), ENCP guarantees that the ground-truth action is included in the prediction set at every step of a test episode with probability at least $1-\alpha$. This provides simultaneous trajectory coverage, a stronger guarantee than step-wise coverage.

3. Key Contributions

1. Identification of Standard CP Failure: The paper demonstrates that standard step-pooled Conformal Prediction fails to satisfy coverage guarantees in VLN due to intra-episode dependencies, often resulting in severe undercoverage.
2. Development of ENCP: The authors introduce an episode-level calibration method that rescales scores by policy confidence and aggregates them via a maximum operator. This construction ensures simultaneous coverage over the entire trajectory.
3. Empirical Validation: The method is evaluated on four VLN policies (DUET, HAMT, R-prev, R-osc) across two datasets (R2R and REVERIE). The study includes:
   • Verification of step-coverage targets on seen-to-unseen splits.
   • Comparison between parameter-free and learning-based weighting schemes.
   • A simulated help-seeking experiment demonstrating how prediction set size can trigger human intervention to improve success rates.

4. Results

• Coverage Targets: Across all tested policies and nonconformity scores (THR, APS, RAPS) on the R2R and REVERIE val-unseen splits, ENCP successfully met the empirical step-coverage targets (e.g., achieving $\ge 90\%$ coverage for $\alpha=0.10$) under exchangeable splits. In contrast, standard split CP consistently undercovered.
• Distribution Shift: The paper explicitly notes that while ENCP meets targets under exchangeable splits, coverage drops in the "seen-to-unseen" setting (where calibration occurs on seen buildings and testing on unseen buildings). In this scenario, episode exchangeability is not assumed, and the formal coverage guarantee does not strictly hold, though ENCP still outperforms standard CP.
• Weighting Variants: The parameter-free weighting scheme (using $1-p_{max}$) achieved comparable coverage to the learning-based variant but resulted in smaller prediction sets and required no additional model fitting.
• Help-Seeking Utility: In a simulation where the agent defers to a ground-truth "oracle" when the prediction set size exceeds a threshold $\tau$, the success rate improved significantly. For example, on the DUET model, lowering the threshold to trigger more queries increased the success rate from 71.2% (no help) to 98.8% (querying on every non-singleton set), albeit at a higher "ask rate."

5. Significance and Claims

The paper claims that ENCP provides a model-agnostic method for uncertainty quantification in VLN that offers formal, finite-sample coverage guarantees over dependent, variable-length trajectories.

• Safety and Reliability: By providing a statistically valid prediction set, ENCP allows agents to identify unreliable steps and defer to human assistance before errors compound, addressing a critical safety gap in autonomous navigation.
• Practical Deployment: The size of the prediction set serves as a practical signal for intervention. The authors argue that this allows for a tunable trade-off between autonomy and safety, enabling agents to "know when they don't know."
• Limitations: The authors modestly note that the closed-loop evaluation relies on a simulated oracle rather than human operators. Furthermore, the method assumes a finite action space, and the coverage guarantee is marginal over the episode distribution, meaning it may not hold perfectly under significant distribution shifts (e.g., unseen buildings) without recalibration, as evidenced by the observed drop in coverage in the seen-to-unseen setting.

In summary, ENCP bridges the gap between theoretical uncertainty guarantees and the practical, sequential nature of VLN, offering a robust mechanism for safe agent deployment.