ENCP: Episode-Normalized Conformal Prediction for Vision-and-Language Navigation
Research summary
A navigation agent makes a sequence of dependent decisions. Calibrating each action separately does not establish that a prediction set will contain the correct action throughout a complete route. ENCP addresses that gap by rescaling each action's nonconformity score, which measures how poorly an action agrees with the policy's prediction, using the policy's residual confidence. It then calibrates the maximum score over each episode.
When calibration and evaluation episodes are exchangeable, ENCP's prediction sets cover the correct action at every step of a route with probability at least the chosen coverage level. The construction allows dependence between steps and variable route lengths. Across 4 navigation policies and 3 scores on R2R and REVERIE, it met the reported empirical step-coverage targets, including on seen-to-unseen evaluations. Those empirical results do not extend the formal guarantee to a new distribution of buildings. The prediction-set size can also indicate when the agent should request help; the paper evaluates that decision with an error-free simulated assistant.
From uncertainty to intervention
ENCP leaves the navigation policy fixed. Score normalization adjusts each action score to the current policy confidence; episode calibration then summarizes dependent steps with the maximum score for each episode. The parameter-free variant uses recorded policy probabilities, whereas the learning-based variant fits a weight before conformal calibration.
