- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies offline learning for the external harness when safety-relevant damage is persistent, latent, and only selectively revealed in logged trajectories. They models the problem as a finite-horizon POMDP and proposes RA-PEVI, an offline RL method for tool-using agents facing problems above. It shares latent intervention dynamics across diagnostics, plans pessimistically in belief space, and achieves O(sqrt(1/N))sample guarantees.
Critical strengths
- The problem formulation is realistic and timely. They models offline harness learning with persistent hidden damage, selective reveals, and diagnose-then-intervene decisions, which is a sparkling and insightful safety setting for tool using agents.
- The proposed method is structure aware and principled with theory. They propose RA-PEVI to share latent intervention dynamics across diagnostic branches, and convert row-wise uncertainty into belied dependent pessimism. This strongly supports the approach’s validity.
Critical weaknesses
- The core assumptions may limit the method’s practical applicability. The main analysis assumes known diagnostic kernels, the full audit, and exactly shared transition dynamics. But in real application, diagnostics are often learned or misspecified, and exact audits may be unavailable. So maybe more independent calibration is needed.
- This problem is more important, that the empirical evaluation is limited and doesn’t stress the key assumptions. In this paper, experiments use a synthetic workflow and one AppWorld protocol with scripted logging policies. Moreover, the evaluation tasks is few and there’s no main-text empirical ablation on diagnostic misspecification and approximate transition sharing. These will make readers doubt about the practical effectiveness and robustness of RA-PEVI.
Questions for authors
- Can diagnostic and transition models be jointly estimated from offline logs, and how robust is RA-PEVI to misspecification or missing full audits?
- What is the computational complexity, and what guarantees exist for approximate belief-space planning at larger scale?
3 comments
Author Rebuttal (2/3)
Approximate transition sharing.
We relax the exact-sharing assumption in Appendix H. We allow the actual transition kernel $T^\star_{h,m,y,i}$ to differ from a common reference kernel $T^\star_{h,i}$, provided that their total variation distance is bounded:
$$ \mathrm{TV}(T^\star_{h,m,y,i},T^\star_{h,i}) \leq \zeta_h(d,x,m,y,i). $$
The bound $\zeta_h$ can be obtained from known system constraints or branch-specific validation data with trusted latent-state labels. Suppose the pooled estimator satisfies $\mathrm{TV}(T^\star_{h,i},\widehat{T}_{h,i})\leq\beta_h(d,x,i)$. Its deviation from the actual branch-specific kernel is bounded by $\beta_h+\zeta_h$, where $\beta_h$ captures statistical estimation error and $\zeta_h$ captures model misspecification.
We therefore add $\zeta_h$ to the original pessimism penalty. The proof follows the argument of Theorem 1, with the additional deviation accumulated along the comparator's trajectory. This yields Theorem 6, which guarantees performance relative to the optimal policy of the actual branch-dependent environment.
W2:Additional Empirical Evaluation
To further validate the theoretical extensions and address the concerns about empirical generality, we conducted three additional sets of experiments.
Joint estimation from the same logs and no-audit deployment.
We evaluate whether diagnostic and transition models can be jointly learned from the offline data, and whether full audits are needed during deployment. We conduct 60 independent repetitions using datasets of two sizes, with 100 and 200 offline trajectories, where each smaller dataset is a prefix of its corresponding larger dataset. At deployment, full audits are unavailable. Joint Plug-in estimates the same diagnostic and transition models from the shared labeled logs but does not use pessimistic uncertainty penalties.
| $N$ | Joint Plug-in | Joint RA-PEVI | Gap to Oracle |
|---|---|---|---|
| 100 | 5.8633 ± 3.6682 | 3.3303 ± 0.1771 | 6.02% |
| 200 | 4.1292 ± 2.3302 | 3.2881 ± 0.1048 | 4.68% |
Averaged across the two data sizes, our method reduces actual cost by 33.77% compared with Plug-in, with a small gap to Oracle. These results support joint estimation and show that effective harness learning does not require full audits during deployment.
Robustness to approximate transition sharing.
We evaluate the robustness correction in Appendix H using the original six-step synthetic workflow. We generate 20 independent offline datasets, each containing 5,000 trajectories collected under exact transition sharing. At deployment, we introduce branch-dependent deviations in the Execute transition kernels, shifting their distributions toward the catastrophic state. The deviation level is controlled by $\epsilon\in\{0,0.01,0.025,0.05,0.075,0.1\}$, with different magnitudes across diagnostic branches. We compare two methods. RA-PEVI is the original algorithm. Modified RA-PEVI additionally incorporates the known TV deviation upper bounds into its pessimism penalty. It does not know the actual deployment transition kernels or the direction of the deviations.
| Deviation $\epsilon$ | RA-PEVI | Modified RA-PEVI |
|---|---|---|
| 0 | 3.3038 | 3.3038 |
| 0.01 | 6.1138 | 6.0218 |
| 0.025 | 10.2260 | 9.3745 |
| 0.05 | 16.8105 | 13.5680 |
| 0.075 | 23.0656 | 16.9642 |
| 0.1 | 28.9999 | 20.2692 |
All entries report actual deployment costs. These results demonstrate that accounting for bounded deviations from shared transition dynamics can substantially improve robustness to adverse model misspecification.
Evaluation on a realistic tool-use benchmark.
We further evaluate RA-PEVI on 20 held-out tasks from the $\tau$-bench Retail domain [4]. Both the native tool-using agent and simulated user are powered by GLM-5.3-Flash. We retain the original Retail policies, tools, and multi-turn interaction protocol. The offline dataset contains 24 trajectories and 218 tool-level transitions. We compare RA-PEVI with a no-protection baseline, the Plug-in planner (without pessimism), and Branch PEVI (which estimates separate transition models for each diagnostic-output branch).
We report three metrics: Final DB success measures whether the final database state satisfies the task's target state and assertions; Residual damage measures whether the hidden damage remains in the protected customer profile at termination; and Cost is the total cost defined in our objective.
| Method | Final DB success ↑ | Residual damage ↓ | Cost ↓ |
|---|---|---|---|
| No protection | 55% | 45% | 11.250 |
| Plug-in Planner | 55% | 45% | 11.279 |
| Branch PEVI | 65% | 30% | 8.006 |
| RA-PEVI | 80% | 15% | 4.390 |
These results provide further evidence of the applicability of our framework beyond the original synthetic workflow and AppWorld setting.
Author Rebuttal (3/3)
Q2: Computational Complexity and Approximate Belief-Space Planning
Computational complexity.
RA-PEVI consists of three main computational stages: (i) counting selectively revealed transitions from offline logs, (ii) estimating categorical diagnostic and transition kernels and constructing their confidence radii, and (iii) planning over beliefs. The first two stages are computationally efficient: processing $N$ trajectories of horizon $H$ takes $O(NH)$ time, while model storage and confidence construction are linear in the size of the tabular model. Belief updates also require only polynomial-time operations (e.g., $O(|\mathcal D|^2)$ per update under dense transition kernels).
The main computational bottleneck is belief-space planning. Exact alpha-vector backups enumerate contingent plans across diagnostic and environment outcomes, and the number of alpha vectors can grow exponentially with the horizon and observation branching. This is inherent to general finite-horizon POMDP planning, which is PSPACE-complete in the worst case [1], rather than specific to RA-PEVI.
Approximate planning. Our pessimism penalty can be expressed as an additional latent-state stage cost (Appendix F, Proposition 3). Thus, the penalized problem retains the standard finite-horizon POMDP structure, allowing existing approximate POMDP solvers to be directly applied without changing the learning procedure. For example, point-based methods such as PBVI [2] restrict backups to representative reachable beliefs, while heuristic-search methods such as HSVI [3] focus computation on relevant belief regions and maintain bounds on solution quality.
Importantly, Theorem 1 already separates statistical uncertainty from planning approximation. If an approximate solver guarantees an optimization error of at most $\epsilon_{\mathrm{plan}}$ for the full pessimistically penalized objective, the resulting policy satisfies the same performance guarantee with an additive $\epsilon_{\mathrm{plan}}$ term. Thus, the statistical guarantees of RA-PEVI can be retained while using approximate POMDP planning, provided that the corresponding optimization error is controlled.
We will clarify the computational costs of each stage, identify planning as the main scalability bottleneck, and discuss these established approximation methods and their applicability in the revised paper.
We hope that our clarifications and additional theoretical and empirical results address your concerns. If so, we would be very grateful if you could consider revisiting your assessment of the paper. Thank you again for the constructive feedback and for your time.
References
[1] Papadimitriou, C. H., & Tsitsiklis, J. N. (1987). The complexity of Markov decision processes. Mathematics of operations research, 12(3), 441-450.
[2] Pineau, J., Gordon, G., & Thrun, S. (2003, August). Point-based value iteration: An anytime algorithm for POMDPs. In Ijcai (Vol. 3, pp. 1025-1032).
[3] Smith, T., & Simmons, R. (2012). Heuristic search value iteration for POMDPs. arXiv preprint arXiv:1207.4166.
[4] Yao, S., Shinn, N., Razavi, P., & Narasimhan, K. (2024). $\tau $-bench: A Benchmark for Tool-Agent-User Interaction in Real-World Domains. arXiv preprint arXiv:2406.12045.
Author Rebuttal (1/3)
Thank you for recognizing the realistic problem formulation and the structure-aware design of RA-PEVI. We appreciate your insightful comments and address them below.
W1 & Q1: Assumption Relaxations and Theoretical Extensions
Joint estimation of diagnostic and transition models
Our original Appendix G considers estimating unknown diagnostic kernels from an independent labeled calibration dataset. We further extend this result to estimate the diagnostic kernel $O$ and transition kernel $T$ from the same batch of offline trajectories.
The key is to extend the conditional representativeness principle in Assumption 2 to diagnostic-label selection. Specifically, let $R^O_{t,h}$ indicate whether a trusted current damage-state label is selected for estimating $O$. We additionally require:
$$ Y_{t,h} \perp R^O_{t,h} \mid \mathcal{F}_{t-1},\mathcal{H}^{-}_{t,h},d_{t,h},m_{t,h}. $$
This condition means that, given the information available before the diagnostic, the true damage state, and the selected diagnostic, whether a sample receives a trusted label cannot depend on its diagnostic output. Otherwise, the revealed samples may over-represent certain outputs, biasing the estimate of $O$.
Under these conditions, the same offline trajectories can contribute to all three estimators: samples with trusted current damage labels estimate $O$; source-labeled transitions estimate $Q$; and transitions with both source and destination labels estimate $K$. Each estimator retains its own concentration guarantee. These bounds hold simultaneously by a union bound. Importantly, this does not require independent estimators or sample splitting.
We then incorporate both uncertainties into planning at their respective decision stages: diagnostic uncertainty is penalized before observing the diagnostic output, while transition uncertainty is penalized when selecting the subsequent intervention. Applying the model-comparison argument of Theorem 1 gives:
$$ J_{O^\star,T^\star}(\widehat{\pi})-J_{O^\star,T^\star}(\pi_c) \leq 2B_O(\pi_c)+2B_T(\pi_c)+\epsilon_{\mathrm{plan}}. $$
Here, $O^\star$ and $T^\star$ are the true diagnostic and transition kernels, respectively; and $\pi_c$ is any admissible comparator policy. $J_{O^\star,T^\star}(\pi)$ denotes the expected cost of policy $\pi$ under the true environment. $B_O(\pi_c)$ and $B_T(\pi_c)$ are the cumulative diagnostic and transition uncertainty along the comparator's trajectories, respectively, and $\epsilon_{\mathrm{plan}}$ is the planning optimization error.
About Full-audit
Our framework requires a sufficient number of trusted latent-state labels in the offline logs. Full audits provide one possible source of such labels; they may also be obtained through periodic manual inspections, verification against authoritative system records, or post-incident investigations.
Importantly, full audits are needed as a source of supervision during learning, but not necessarily as an available action during deployment. Once the models are learned, RA-PEVI maintains a belief over latent states using available diagnostic outputs and makes decisions based on this belief. Our performance guarantee also holds when the deployment policy is restricted to never selecting full audits.
Identifiability boundary. Without trusted latent-state labels or additional structural assumptions, $O$ and $T$ are generally not jointly identifiable. To illustrate, consider a binary latent state $D\sim\mathrm{Bernoulli}(1/2)$ and binary diagnostic and transition outcomes $Y$ and $Z$, conditionally independent given $D$. Let $a$ and $b$ characterize their respective dependence on $D$:
$$ P(Y=1\mid D)=\frac{1+a(2D-1)}{2}, $$
$$ P(Z=1\mid D)=\frac{1+b(2D-1)}{2}. $$
After marginalizing out $D$, the observable distribution is
$$ P(Y=y,Z=z)=\frac{1}{4}[1+ab(2y-1)(2z-1)]. $$
It depends only on $ab$: for example, $(a,b)=(0.8,0.4)$ and $(0.4,0.8)$ generate exactly the same observable distribution but correspond to different diagnostic and transition kernels. Thus, even infinitely many unlabeled observations cannot uniquely identify $O$ and $T$. This simplified model illustrates why trusted latent-state labels or additional identifying assumptions are needed during learning.