Seeing through Uncertainty: Robust Task-Oriented Optimization in Visual Navigation

We sincerely thank you for the detailed and expert feedback. We are encouraged that you found our work innovative and our mathematical derivations solid. We hope that the following clarifications can address the noted weaknesses (W1, W2, W3, W4, W5, W6), further solidifying the contributions of our work.

---

W1: Computational Cost Analysis

We address this crucial point by analyzing memory footprint and runtime performance, which proves NeuRO’s efficiency for real-world deployment.

1. Memory Consumption: NeuRO is lightweight. Its checkpoint size (20.24MB) is smaller than other SoTA methods due to its parameter-free optimization component.
2. Runtime Performance: We demonstrate with the following points:

• 2.1 Absolute Time: The values in Table 3 are normalized for comparison (relative to $E=3, \tau=4$; see line 523-524 in Appendix). The absolute solving times are presented in Appendix F (Table 5) and are modest (e.g., 1.084s for a large $E=20, \tau=12$ setting). We will incorporate this clarification from the Appendix into the main paper.
• 2.2 Runtime Performance: We attribute the primary computational cost to the gradient computation of the optimization model but not the solving process, because modern linear program solvers are already highly efficient for solving. To validate this analysis, we measured the runtime cost at test stage, where the agent only needs to solve the forward pass. This result confirms that NeuRO is fully capable of real-time performance. We will add this crucial table and clarification to the revised version.

  Memory Footprint	Test Runtime (SMON$_{m=2}$; per step (ms))
  Lyon	22.18MB
  HTP-GCN	25.63MB
  NeuRO	20.24MB

• 2.3 Local Grid Scope: The optimization time is manageable since our framework does not require a large optimization grid. This is because our optimization grid models the agent's local egocentric view, NOT the global map (Evidence: e.g., The grid is re-formulated at every time step based on the current egocentric observation). This keeps the optimization problem small and tractable. In MultiON, the ego-map spans 5m with ~30 cells (0.8m × 0.8m resolution). Our generation process of the optimization grid can be understood as overlaying a goal position distribution onto this local map. Therefore, a grid size of $E=5$ ($V=25$ cells) is sufficient. In summary, our optimization grid simulates a local field of view, so the problem size $E$ remains bounded regardless of the overall environment scale.
• 2.4. Scalability: To reduce the $O(E^2\tau)$ complexity (the source of the optimization problem’s computational complexity) analyzed in Appendix F, we introduce a basis function expansion that enables the network to predict $\alpha$ and $\beta$ directly, reducing the complexity to $O(K\tau)$ with a predefined constant K ≪ E². Empirical results confirm its effectiveness.

---

W2: Lack of Failure Case Analysis

We agree this is an important analysis, and we have now systematically studied our method's robustness from two perspectives:

1. Target Geometries (Appendix H.1): We analyzed performance on targets with less distinct geometries (e.g., short cylinders, ambiguous spheres). The results show that while all methods' performance degrades, NEURO's performance drops far more gracefully, demonstrating superior robustness to perceptually challenging objects.
2. Visually Similar Distractors: We analyzed failure cases in S-MON (m=3) and found 62% were due to perceptual ambiguity (e.g., confusing a target sphere with a pan). This issue is fundamental, as the failure rate for this reason is comparable across methods (Baseline: ~66%; Lyon: ~60%). Notably, our core framework improves resilience to such distractors over the baseline, even without the specialized perception modules used by methods like Lyon.

---

W3: Limited Comparison

We thank you for suggesting recent baselines. As few works report MultiON results and official implementations are often unavailable, we reproduced several methods based on their original papers (* indicates such methods). A subset of results is shown below due to space limits. As shown, NeuRO continues to outperform even this strong, transformer-based baseline. We will add this comparison to Table 1 in the revised manuscript.

---

W4: Sensitivity to Inaccurate Belief Estimation

We demonstrate NEURO's resilience to inaccurate belief estimation through both its core mechanism and a new experiment.

1. Robust Calibration Mechanism: Our framework is fundamentally designed to handle estimation inaccuracies. The conformal calibration procedure (Proposition 1) ensures that the generated uncertainty set $\Omega(x)$ covers the true object dynamics with a prespecified probability. As shown in Table 2, this calibrated, conservative belief representation can filter out noise and make accurate predictions (about object location) under uncertainties. This mechanism is our framework's primary defense against the inevitable inaccuracies of belief estimation.
2. Robustness to Noisy Inputs: To further validate this resilience, we conducted a new ablation study. We injected Dropout noise into the agent's RGB input to interfere belief estimation. The results show that NeuRO's performance degrades far more gracefully than the baseline: |SMON$_{m=2}$: Success||| |-|-|-| | |No Noise|Dropout Noise| |OracleEgoMap|63.40 (±4.82)|56.27 (±7.33)| |NeuRO|81.14 (±3.86)|78.25 (±5.24)|

---

W5: Convexity Assumption

To address this question, while the navigation task is inherently non-convex and complex, we conducted the following experiment in response to quantify the practical impact. We extracted a subset of SMON$_{m=2}$ where both objects are of the same category (e.g., two cylinders), and measured the navigation performance & prediction accuracy (following the method in Section 4.3) under two settings:

1. The 2 objects are placed in separate rooms, where each’s location belief distribution is approximately a convex uncertainty;
2. Both objects are in the same room, resulting in a mutually interfering, non-convex posterior.

While the first task is harder due to room traversal, NeuRO narrows the performance gap as it is specifically designed for convex problems. Also, while its prediction accuracy slightly declines in the second, non-convex task, NeuRO still outperforms SoTA baselines, indicating that non-convexity does not compromise its effectiveness and demonstrating its robustness.

Moreover, we would like to clarify a technical point discussed in our original manuscript:

In our appendix, we present a basis function expansion method that not only addresses scalability but also, as we found, provides a principled path for tackling non-convex problems. We would first like to first clarify that non-convex problems (e.g., visual navigation) are generally intractable. Our proposed method in Appendix F serves as a way to alleviate this issue. Specifically, we replaces the belief representation layer of the optimization model with basis functions, leveraging their flexibility to approximate non-convex belief variables ($\alpha$ and $\beta$). Our experimental results validate this substitution, showing a moderate improvement in the agent's performance in vision-based navigation, an environment rich with non-convex inputs. To this end, we can also treat matrix $M$ as a given constraint, avoiding PICNN-based convex calibration by leveraging its relation with alpha-beta in Eq. (2b) or using general black-box networks (e.g., predicting uncertainty bounds as in our experiments).

In summary, we provides two approaches: (i) the PICNN-based convex approximation; and (ii) the basis function expansion to fit more complex variables. While the (ii) can be extended to non-convex scenarios, it incurs extra training costs, and solutions to non-convex problems generally lack theoretical guarantees. Thus, approach (i) is more suitable for the data-scarce environments central to our paper's theme.

---

W6: i.i.d. Assumption

We sincerely apologize for the lack of clarity that led to this misunderstanding. We want to clarify that the i.i.d. assumption applies to data sampled for a given time step t, not across temporally correlated steps within an episode, with following two reasons:

Firstly, this is supported by our formulation and is not violated by the nature of embodied navigation. First, there is a minor typo on Line 162-163; we intended to state that we omit the time index $t$ for conciseness, not the object index $i$. This is consistent with Eq. (5), where index $t$ is omitted.

Secondly, because the optimization grid is re-formulated at every time step $t$, the conformal quantile q must also be determined based on data relevant to that specific time step. This means the calibration procedure relies on i.i.d. samples drawn for the same, given time $t$

---

[1] N. Gireesh, et al., Sequence-Agnostic Multi-Object Navigation, ArXiv, 2023

[2] KH. Zheng, et al., PoliFormer: Scaling On-Policy RL with Transformers Results in Masterful Navigators, CORL, 2024

[3] P. Marza, et al., Multi-Object Navigation with dynamically learned neural implicit representations, ICCV, 2023

We sincerely thank you for the thoughtful and encouraging feedback. We hope that the following clarifications will fully address the noted weaknesses (W1, W2, W3, W4) and questions (Q1, Q2), further solidifying the contributions of our work.

---

W1: Convex Approximation

To address this question, while the overall navigation task is inherently non-convex and complex, we conducted the following experiment to quantify this. We first extracted a subset of SMON$_{m=2}$ task (both objects belong to the same category, e.g., “two cylinder”), and measured the navigation performance & prediction accuracy (following the method in Section 4.3 “Conformal Coverage Level") under two settings:

1. The 2 target objects are placed in separate rooms, which means the location belief distribution of each room’s object is approximately a convex uncertainty;
2. Both similar objects are in the same room, resulting in a mutually interfering, non-convex posterior. ||Two Room| |Single Room| | |-|-|-|-|-| | |Avg. Sucess|Pred. Acc.|Avg. Sucess|Pred. Acc.| |Lyon|72.80|-|79.42|-| |NeuRO (α=0.05)|77.84|0.88 (±0.019)|82.25|0.83 (±0.022)|

We observe the navigation performance in the first setting is lower, since finding objects in separate rooms is harder. However, NeuRO narrows this gap as it is specifically designed for convex problems. Also, while its prediction accuracy slightly declines in the second, non-convex task, NeuRO still outperforms SoTA baselines, indicating that non-convexity does not compromise its effectiveness and demonstrating its robustness.

Moreover, we would like to clarify a technical point discussed in our original manuscript:

In our appendix, we present a basis function expansion method that not only addresses scalability but also, as we found, provides a principled path for tackling non-convex problems. We would first like to first clarify that non-convex problems (e.g., visual navigation), being NP-hard, are generally intractable and lack theoretical guarantees for their solutions. Our proposed method in Appendix F serves as a way to alleviate this issue. Specifically, we replaces the belief representation layer of the optimization model with basis functions, leveraging their power and flexibility to approximate non-convex belief variables ($\alpha$ and $\beta$). Our experimental results validate this substitution, showing a moderate improvement in the agent's performance in vision-based navigation, an environment rich with non-convex inputs. This, of course, introduces additional training costs and data requirements from the extra network module. Furthermore, to this end, we can treat matrix $M$ as a given constraint, avoiding PICNN-based convex calibration by leveraging its relation with alpha-beta in Eq. (2b) or using general black-box networks (e.g., predicting uncertainty bounds as in our experiments).

In summary, we provides two complementary approaches: (i) the PICNN-based convex approximation; and (ii) the basis function expansion to fit more complex variables. While the second approach can be extended to non-convex scenarios, it incurs extra training costs, and solutions to non-convex problems generally lack theoretical guarantees. Given these considerations, we believe the first approach is more suitable for the data-scarce environments central to our paper's theme. Therefore, we chose to feature method (i) in the main text.

---

W2 & Q1: Real-World Scalability

To address the concern about "visual distractors" and "sensor noise," we would like to first clarify that our experiments are conducted in the Habitat simulator, which features rich, photorealistic textures and varied lighting conditions, providing a strong baseline for real-world visual complexity. Furthermore, we conducted a new ablation study. We injected Dropout noise into the agent's RGB input during testing to simulate real-world sensor imperfections. The results show that NeuRO's performance degrades far more gracefully than the baseline.

Beyond robustness to visual noise, we highlight three key aspects of our framework that support its real-robot feasibility:

1. Memory Efficiency: NeuRO's memory consumption (20.24MB, largely consisting of the perception module) is less than other SoTA methods due to its parameter-free component of optimization model, thus not introducing prohibitive memory overhead (see the table in W3).
2. Runtime Performance: See W3.
3. Non-convex Adaptability: See W1. Collectively, these points demonstrate that our framework is not only effective but also practical and extensible for real-world applications.

---

W3: Inference Time

We thank the reviewer for this crucial clarifying question. To comprehensively address the reviewer’s concern, we offer the following clarifications:

1. Absolute Time: The values in Table 3 are normalized for comparison (relative to $E=3, \tau=4$; see line 523-524 in Appendix). The absolute solving times are presented in Appendix F (Table 5) and are modest (e.g., 1.084s for a large $E=20, \tau=12$ setting). We will incorporate this clarification from the Appendix into the main paper.
2. Runtime Performance: We attribute the primary computational cost to the gradient computation of the optimization model but not the solving process, because modern linear program (LP) solvers are already highly efficient for solving. To validate this analysis, we measured the runtime cost at test stage, where the agent only needs to solve the forward pass of the optimization problem to get the action offset without any gradient computation. This result confirms that NeuRO is fully capable of real-time performance. We will add this crucial table and clarification to the revised version.

   	Memory Consumption	Test Runtime (SMON$_{m=2}$; per step (ms))
   Lyon	22.18MB	12.9
   HTP-GCN	25.63MB	15.3
   NeuRO	20.24MB	11.6

3. Local Grid Scope: The optimization time is manageable since our framework does not require a large optimization grid. This is because our optimization grid models the agent's local egocentric view, NOT the global map (Evidence: 1. The grid is re-formulated at every time step based on the current egocentric observation; 2. We always initialize agent position to the center of the optimization grid). This keeps the optimization problem small and tractable. In the MultiON task, the input ego-map spans a 5m view and each cell in the map represents a 0.8m*0.8m area, which means there are about 30 cells. Our generation process of the optimization grid can be understood as overlaying a goal position distribution onto this local map. Therefore, a grid size of $E=5$ ($V=25$ cells) is sufficient. In summary, our optimization grid simulates a local field of view, so the problem size E remains bounded regardless of the overall environment scale.
4. Scalability: Furthermore, we have analyzed the source of the optimization problem’s computational complexity in Appendix F, which scales with $O(E^2\tau)$. To address this, we introduce a basis function expansion method in Appendix F to let network predict α and β. It effectively reduces this complexity to $O(K\tau)$, where $K \ll E^2$ is a constant. We empirically validate this approach, demonstrating its effectiveness in accelerating the optimization. However, for the sake of clarity and to maintain focus on the “network+optimization” framework itself in the main paper, we have detailed this extension in the appendix.

---

W4: Writing Clarity

We sincerely appreciate this feedback. We acknowledge that the manuscript currently assumes a level of prior familiarity, and we will make the necessary adjustments. For example,

1. Add Justifications for Key Design Choices: We will provide clear, intuitive explanations for our core modeling choices (E.g., we will explicitly clarify why we use a discrete grid for the uncertainty set (to avoid intractable semi-infinite programs)).
2. Provide Essential Background: We will introduce a concise background section covering prerequisite knowledge, such as the core ideas behind Conformal Prediction.
3. Refine Notation and Symbols: We will thoroughly revise our notation and add a comprehensive notation table to the appendix for easy reference.

---

Q2: PICNN Design

We have conducted new experiments on PICNN capacity, alongside with our existing ablation on the coverage level in Section 4.3, to provide a comprehensive sensitivity analysis. We analyze the sensitivity of our framework to the two primary design factors of the PICNN module—the conformal coverage level and network capacity—by measuring their impact on both prediction accuracy and final task performance. The results show that a larger PICNN improves both grid prediction accuracy and task performance, but with diminishing returns. We attribute this to the challenges of training a high-capacity model in a data-scarce regime.

1. Coverage Level $(1-\alpha)$: As shown in Section 4.3 (Table 2), task performance is directly and intuitively linked to calibration quality. A higher coverage level leads to more conservative but reliable uncertainty sets, improving performance, which aligns perfectly with our design motivation.
2. Network Capacity: We have now conducted a new experiment to analyze the impact of PICNN capacity (dimension of hidden layers). |SMON$_{m=2}$|||| |-|-|-|-| |Hidden Dim.|Avg. Success|Avg. SPL|Prediction Accuracy| |128|77.3|62.1|0.84 (±0.021)| |256|80.1|66.5|0.90 (±0.015)| |512|82.4|67.1|0.88 (±0.013)|

We sincerely thank you for the constructive and detailed feedback. We are encouraged that you found our work novel, well-written, and outperforming SoTA baselines. We address the specific weaknesses (W1, W2, W3) and questions (Q1, Q2, Q3) below.

---

W1: Experimental Rigor

We have now conducted experiments with 8 different random seeds and will update Table 1 with mean and standard deviation in the final version. (due to space limitations, we are currently able to include only a subset of the results.)

We observed that Progress and PPL provide inherently more robust counterparts to Success and SPL, respectively. Also, the new results show that NeuRO not only achieves a higher mean success rate but also exhibits significantly lower variance, further reinforcing our central claim regarding the model’s robustness and generalization capabilities.

---

W2: Potential Limited Use

Thank you for raising this point. We address it from three perspectives. Collectively, our analysis and experiments demonstrate that NeuRO is computationally efficient and effectively accounts for complex visual information in realistic environments, facilitating its applicability to real-time scenarios.

1. Optimization under Continuous Uncertainty: See Q3
2. Incorporation of Sight Information: See Q1.
3. Inference Efficiency: See Q2.

---

W3: Experimental Clarity

We thank you for pointing this out. Due to page limitations, we condensed the setup description. We will elaborate on these details in the revised version to improve clarity Specifically, we will:

1. Include a glossary and symbol table in the appendix, along with a description of the basic setup (e.g., action FORWARD (0.25m), TURN-LEFT/RIGHT (30°)) for the MultiON task.
2. Introduce prerequisite concepts such as conformal prediction at the beginning of the Method section.
3. Add more intuitive explanations to clarify key modeling choices (e.g., using a discrete grid for efficient optimization while maintaining continuous decision variables for differentiability).

---

Q1 & W2: Detection Factor & Sight Information

We appreciate the question and you are correct that $d(p_t)_v$ itself is a simplification. As for the line-of-sight information, we do explicitly incorporate it during the generation process of the uncertain transition matrix, where networks takes the raw depth image and BEV ego-map as inputs. We believe this incorporation contributes to our model’s strong performance even with a simple distance-based factor.

To validate this hypothesis, we conducted a new experiment to make this geometric reasoning more explicit within the optimization process itself, inspired by your suggestion. We modified our PICNN to also predict an obstacle map (just like the current goal map) and merged two map to construct a optimization grid with both object location belief and obstacles. Then, we redefined $d(p_t)_v$ based on the geodesic distance (calculated via Breadth-First Search) instead original Manhattan one to consider the predicted obstacles. The results (Progress metric) are shown below:

As observed, this leads to a moderate but consistent improvement in navigation performance. We hypothesize this is because our perception module already captures parts of the occlusion information from the input depth data, so the contribution of the new explicit factor partially overlaps with what the network has already implicitly learned. This experiment affirms your intuition and further reinforces the physical grounding of our framework. We will include this insightful analysis in the revised version.

---

Q2 & W2: Inference Time

We thank you for this crucial clarifying question. The "Inference time" reported in Table 3 refers to the training-time process of solving the optimization problem and computing the policy gradients via Eq. 7(b), NOT the actual runtime deployment.

1. Absolute Time: The values in Table 3 are normalized for comparison (relative to $E=3, \tau=4$; see line 523-524 in Appendix). The absolute solving times are presented in Appendix F (Table 5) and are modest (e.g., 1.084s for a large $E=20, \tau=12$ setting). We will incorporate this clarification from the Appendix into the main paper.
2. Runtime Performance: We attribute the primary computational cost to the gradient computation of the optimization model but not the solving process, because modern linear program (LP) solvers are already highly efficient for solving. To validate this analysis, we measured the runtime cost at test stage, where the agent only needs to solve the forward pass of the optimization problem to get the action offset without any gradient computation. This result confirms that NeuRO is fully capable of real-time performance. We will add this crucial table and clarification to the revised version.

   	Memory Consumption	Test Runtime (SMON$_{m=2}$; per step (ms))
   Lyon	22.18MB	12.9
   HTP-GCN	25.63MB	15.3
   NeuRO	20.24MB	11.6

3. Local Grid Scope: The optimization time is manageable since our framework does not require a large optimization grid. This is because our optimization grid models the agent's local egocentric view, NOT the global map (Evidence: 1. The grid is re-formulated at every time step based on the current egocentric observation; 2. We always initialize agent position to the center of the optimization grid). This keeps the optimization problem small and tractable. In the MultiON task, the input ego-map spans a 5m view and each cell in the map represents a 0.8m*0.8m area, which means there are about 30 cells. Our generation process of the optimization grid can be understood as overlaying a goal position distribution onto this local map. Therefore, a grid size of $E=5$ ($V=25$ cells) is sufficient. In summary, our optimization grid simulates a local field of view, so the problem size remains bounded regardless of the overall environment scale.
4. Scalability: Furthermore, we have analyzed the source of the optimization problem’s computational complexity in Appendix F, which scales with $O(E^2\tau)$. To address this, we introduce a basis function expansion method in Appendix F to let network predict α and β. It effectively reduces this complexity to $O(K\tau)$, where $K \ll E^2$ is a constant. We empirically validate this approach, demonstrating its effectiveness in accelerating the optimization. However, for the sake of clarity and to maintain focus on the “network+optimization” framework itself in the main paper, we have detailed this extension in the appendix.

---

Q3 & W2: Continuous Space

This is a very insightful question that touches upon a fundamental challenge in robust optimization, but modifying the optimization grid (the uncertainty part in our robust optimization problem) to a continuous space would transform our problem into a semi-infinite program (SIP). In general, solving SIPs to optimality is NP-hard and computationally intractable, especially within the tight time constraints of an agent's decision loop. While relaxations can be used to approximate SIPs, they often alter the optimization landscape and sacrifice the guarantee of finding the true robust optimum.

Therefore, we intentionally adopt a discretized grid as a principled and pragmatic design choice to ensure the downstream robust optimization problem remains a tractable Linear Program. This guarantees that we can find the global optimum of the subproblem efficiently and, more importantly, that we can differentiate efficiently through it for end-to-end training. Also, from a practical standpoint, one could even view the real world map as a very fine-grained discrete grid, making our approach a practical approximation. We will add this discussion to the appendix to provide a richer context for our design choices.

We sincerely thank you for the detailed feedback and for recognizing the novelty of our work. We sincerely hope the following clarifications and new experimental results will address the outlined weaknesses (W1, W2, W3) and questions (Q1, Q2).

---

W1 & Q1: Statistical Significance

We have conducted new experiments with 8 random seeds to ensure statistical significance. The new results show our method is not only superior in mean performance but also exhibits lower variance. We will update all experimental results in all the tables in the final version. (due to space limitations, we are currently able to include only a subset of the results)

The new results confirm that NeuRO achieves a higher mean success rate and also exhibits significantly lower variance. This finding is critical, as it indicates that our framework produces more stable and reliable policies, which directly supports our central claim of enhanced robustness and generalization.

---

W2: Recent Baselines

We thank the reviewer for suggesting recent baselines. To provide a more comprehensive comparison in the evolving landscape of MultiON, where few works report results, we have made our best effort to reproduce other methods for the MultiON task, as some official implementations for this benchmark are not available (* denotes our implementation following the methodology outlined in the corresponding paper; due to space limitations, we are currently able to include only a subset of the results). As shown, NeuRO continues to outperform even this strong, transformer-based baseline. We will add this comparison to Table 1 in the revised manuscript.

---

W3: Single-Object Navigation

We greatly appreciate this insightful suggestion. We have included our results on single-object navigation in Appendix H. We have now incorporated a broader range of navigation agents into the single-object navigation task in MultiON settings (# denotes the agent specialized for single-object tasks). The results are shown below. (due to space limitations, we only show some of the results). These results suggest that agents trained for multi-object navigation can effectively generalize to standard single-goal scenarios, highlighting NeuRO’s strong generalization. Further results about this point are included in Appendix Table 8.

---

Q2: HTP-GCN Results

We apologize for this omission. The results were not included initially as the official code was unavailable. We tried reproduce it based on the official paper and now completed HTP-GCN’s results (See W2).

---

[1] N. Gireesh, et al., Sequence-Agnostic Multi-Object Navigation, ArXiv, 2023

[2] KH. Zheng, et al., PoliFormer: Scaling On-Policy RL with Transformers Results in Masterful Navigators, CORL, 2024

[3] P. Marza, et al., Multi-Object Navigation with dynamically learned neural implicit representations, ICCV, 2023

[4] D. An, et al., BEVBert: Multimodal Map Pre-training for Language-guided Navigation, ICCV, 2023