acceptodds
Under review as a conference paper at ICLR 2027

Offline Learning to Diagnose and Intervene in Tool-Using Agents

Abstract

Tool-using agents act on stateful environments, where erroneous tool actions, such as API calls or file operations, can leave persistent effects that are not directly visible in later interactions. This creates a sequential safety problem: an external harness must track possible hidden damage, decide when costly diagnosis is worthwhile, and choose how to intervene while accounting for intervention cost. We study how to learn such a harness from fixed interaction logs in which damage labels are revealed only selectively. We propose Revealing-Action Pessimistic Value Iteration (RA-PEVI), which learns intervention dynamics shared across diagnostic branches from selectively revealed latent states and performs pessimistic planning in the belief space. We establish a finite-sample performance guarantee, derive the corresponding rate, and prove matching lower bounds and identifiability limits. Experiments on synthetic data and AppWorld support our theoretical results and show that RA-PEVI achieves better performance than standard baselines.

Primary area:
reinforcement learning
Keywords:
Offline reinforcement learning, Tool-using agents, Pessimistic planning

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_rMxzOpenReview ↗
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
  1. 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.
  2. 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
  1. 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.
  2. 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
  1. Can diagnostic and transition models be jointly estimated from offline logs, and how robust is RA-PEVI to misspecification or missing full audits?
  2. What is the computational complexity, and what guarantees exist for approximate belief-space planning at larger scale?
3 comments
AuthorsOpenReview ↗

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.

AuthorsOpenReview ↗

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-inJoint RA-PEVIGap to Oracle
1005.8633 ± 3.66823.3303 ± 0.17716.02%
2004.1292 ± 2.33023.2881 ± 0.10484.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-PEVIModified RA-PEVI
03.30383.3038
0.016.11386.0218
0.02510.22609.3745
0.0516.810513.5680
0.07523.065616.9642
0.128.999920.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.

MethodFinal DB success ↑Residual damage ↓Cost ↓
No protection55%45%11.250
Plug-in Planner55%45%11.279
Branch PEVI65%30%8.006
RA-PEVI80%15%4.390

These results provide further evidence of the applicability of our framework beyond the original synthetic workflow and AppWorld setting.

AuthorsOpenReview ↗

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.

Reviewer_qKrLOpenReview ↗
Rating
2
Confidence
1
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper proposed RA-PEVI, a method that models agentic tool use as a POMDP and solved for an optimal harness via an offline RL formulation. The authors then derived theoretical bounds on state estimation accuracy and harness policy optimality. Finally, the authors validated

Critical strengths
  • An interesting application of tabular offline RL and POMDP.
  • Cool optimality theorems.
  • The paper is coherent and the claims are supported by the provided evidences.
Critical weaknesses

I must first confess that I am not an expert in this field, and thus refer the AC to other reviews. That said, I personally found the paper hard to follow. While my unfamiliarity with this topic is likely a big factor, some ambiguous notations didn't help. For example, dcleand_{\textrm{clean}} in line 124 and Ymh\mathcal{Y}_{m_h} in line 131 are not clearly defined. Also, while the theorems are pretty cool after I understand their implications, I wish there were more explanations about their significance to help the readers construct a full picture about this paper.

Questions for authors
  • Would you consider the "plug-in planner" used in the experiment as one of your innovations, or an existing method? To me, the most interesting experiment is how RA-PEVI outperforms plug-in in the low-data regime, so I would appreciate some explanations about their relationship.
  • The settings considered in the experiments could be too simple and thus far from reality. In the AppWorld experiment, we assume the agent to be a sequence of actions, and actions like blocking some command receive a fixed penalty. However, real-world agents generally work to achieve some goal, so if one command is blocked, they try to fix the wrong command or use a workaround, rather than continuing their originally planned sequence. In this case, the penalty could be additional tool call turns and slower task completion. The provided experiments don't quite shed light on how RA-PEVI might perform on these more realistic scenarios.
3 comments
AuthorsOpenReview ↗

Author Rebuttal (1/2)

Thank you for recognizing the interesting application of offline RL and POMDPs, as well as the value of our theoretical results. We appreciate the helpful comments and address them below.

W1: Presentation and Significance of Theoretical Results

Notation and readability. We agree that some notation and theoretical implications need clearer explanations. In particular, $d_{clean}$ denotes the clean (undamaged) latent state, and $\mathcal{Y}_m$ denotes the set of possible outputs of diagnostic $m$. We will conduct a thorough revision of the entire paper to ensure that every notation is clearly defined and the presentation is easier to follow. We will also add intuitive explanations before technical results and improve the overall organization of Sections 3–5.

Significance of the theoretical results. We would like to further clarify why our theoretical guarantees are meaningful.

First, Corollary 1 establishes a suboptimality bound of $\widetilde{O}(\sqrt{C_{\mathrm{lat}}(\pi^\star_{\mathrm{cov}})/N})+\epsilon_{\mathrm{plan}}$, where $N$ is the number of offline trajectories and $C_{\mathrm{lat}}$ measures coverage of the latent transitions relevant to an optimal policy. Here, $\epsilon_{\mathrm{plan}}$ denotes the optimization error incurred by approximate planning, and is zero under exact alpha-vector planning. This implies that the statistical component of suboptimality decreases at an $N^{-1/2}$ rate as more offline data become available. In particular, for finite latent coverage and exact planning ($\epsilon_{\mathrm{plan}}=0$), the bound vanishes as $N\to\infty$, establishing the statistical consistency of RA-PEVI: its learned policy approaches the optimal policy in value.

Second, Theorem 2 establishes a matching information-theoretic lower bound of $\Omega(\sqrt{C_{\mathrm{lat}}/N})$ for any offline learner in our problem class. Thus, our upper bound matches the fundamental lower bound in its dependence on both sample size and latent coverage, up to logarithmic factors. This establishes minimax-rate optimality in these two key quantities. In particular, no offline learning algorithm can achieve a uniformly faster rate in terms of sample size and latent coverage over our problem class, showing that RA-PEVI extracts information from the offline data at the statistically optimal rate. We emphasize that such matching upper and lower bounds are a central goal in theoretical offline RL, as illustrated by prior works [1–3]. We will add more explanations of these results and clarify their significance in Sections 4 and 5.

Beyond the main results, our appendices further extend the framework to approximate transition sharing, independently calibrated diagnostic models, cross-branch identification without direct branch support, and hard resource budgets (Appendices E–I). These extensions broaden the applicability of our theoretical framework.

Q1: Relationship Between RA-PEVI and the Plug-in Planner

The Plug-in planner is a baseline that we design specifically for our problem. The only difference from RA-PEVI is that it directly plans using the estimated transition model without the pessimism term. This provides a comparison to isolate the contribution of pessimism.

The key idea of pessimism is to account for estimation uncertainty in decision making, instead of treating estimated transitions as ground truth. This is particularly important with limited data: an intervention may appear safe simply because insufficient samples have been collected to reveal its potential risks. The Plug-in planner directly trusts this potentially unreliable estimate, whereas RA-PEVI incorporates a confidence-based penalty into planning, making decisions more cautious when the underlying transition estimates are uncertain.

As more offline data become available, estimation uncertainty decreases, and the pessimism penalty becomes smaller. Therefore, pessimism is particularly beneficial in the low-data regime, while the two methods are expected to become closer with sufficient data. This is consistent with Fig. 1(a). We will clarify the role of the Plug-in planner and this comparison in Section 6.

AuthorsOpenReview ↗

Author Rebuttal (2/2)

Q2: Evaluation in More Realistic Agent Environments

To address this concern, we conducted additional experiments on the Retail domain of τ-bench [4], a benchmark featuring multi-turn interactions between LLM agents and simulated users, with native APIs and persistent database states.

We use the native τ-bench Retail llm_agent, powered by GLM-5.3-Flash, together with a GLM-5.3-Flash user simulator. We retain the original Retail policies, tool schemas, and multi-turn interaction protocol, without fine-tuning the LLM. Our harness intercepts tool requests and decides whether to execute, block, or repair them, while the agent continues to generate its responses and subsequent actions through the original orchestrator.

We evaluate on 20 held-out tasks selected from the official Retail test split, covering identity verification, order and product queries, cancellations, returns, exchanges, and modifications of orders and customer information. For offline learning, we collect 24 trajectories containing 218 tool-level transitions, including 178 source-state labels and 127 paired source–destination labels. All learned methods use the same frozen offline dataset and are evaluated on the same 20 tasks.

Importantly, the agent can replan after interventions. A blocked tool call receives a rejection, while a repair restores the protected address but does not execute the original request. The feedback is returned to the ongoing conversation, allowing the LLM to generate new actions, retry operations, or choose alternative tools. Thus, the resulting trajectories reflect the agent's actual adaptive behavior. We compare RA-PEVI with a no-protection baseline, the Plug-in planner (without pessimism), and the Branch PEVI (which estimates separate transition models for each diagnostic-output branch).

The results are:

MethodDB success ↑Residual damage ↓Cost ↓
No protection55%45%11.250
Plug-in planner55%45%11.279
Branch PEVI65%30%8.006
RA-PEVI80%15%4.390

The cost follows our defined objective, including diagnostic and intervention costs and terminal task and damage penalties.

Interaction overhead. We also measure the actual system overhead:

MethodAgent LLM requests / taskBackend calls / taskTime (s) / task
Plug-in planner11.757.5070.26
RA-PEVI12.3011.8070.41

Our objective focuses on costs directly controlled by the harness and their task and safety consequences. Since the base LLM is fixed and its inference is not a decision variable of the harness, we report LLM inference overhead separately instead of including it in the learning objective. Nevertheless, RA-PEVI requires only 0.55 additional agent LLM requests per task, while average execution time remains nearly unchanged. Most additional backend calls come from explicit diagnostics and repairs.

These results show that RA-PEVI improves task success and reduces persistent damage even when interventions trigger adaptive agent behavior, providing evidence of its applicability beyond our original controlled workflows.

We hope that our clarifications and additional 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] Jin, Y., Yang, Z., & Wang, Z. (2021, July). Is pessimism provably efficient for offline rl?. In International conference on machine learning (pp. 5084-5096). PMLR.

[2] Yin, M., & Wang, Y. X. (2021). Towards instance-optimal offline reinforcement learning with pessimism. Advances in neural information processing systems, 34, 4065-4078.

[3] Li, G., Shi, L., Chen, Y., Chi, Y., & Wei, Y. (2024). Settling the sample complexity of model-based offline reinforcement learning. The Annals of Statistics, 52(1), 233-260.

[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.

Reviewer_qKrLOpenReview ↗

Thank you for the response.

I appreciate the authors' response and acknowledge that I have read it. Some of my questions have been answered (e.g., the implications of the provided theory), but several other concerns remain open. For example, I could not find the promised edits in the latest PDF. The added GLM experiment also has two insufficiencies. First, the database damage is modeled as a 15% backend error injection independent of the agent’s tool call contents, which seems different from the paper's main motivation that agents make mistakes. Second, with only 24 offline trajectories and 20 evaluation tasks, the experiment scale may be too small, and no confidence intervals are provided.

Reviewer_nTmzOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Tool using agents can potentially cause hidden damages that persist in subsequent interactions. This paper formulates learning cost sensitive diagnostic and intervention policies as an offline RL problem, reducing hidden damages and the costs of diagnosis and intervention, while maintaining high terminal task performance. The paper proposes a new offline RL algorithm Revealing Action Pessimistic Value Iteration (RA-PEVI) which learns from fixed logs with selectively revealed damage labels and plans over beliefs about hidden damage. It can more effectively learn the damage dynamics compared to ordinary offline RL algorithm by leveraging the fact that the same intervention may share similar diagnoses. Experiments on synthetic workflows and a controlled AppWorld protocol show lower overall costs and less unresolved damage than several baselines.

Critical strengths
  1. The paper identifies an interesting, practical problem of learning hidden damages that occur frequently in tool using agents. By considering not only the terminal task performance but also the hidden damages during agent execution, the paper provides a different perspective on agent safety and motivates jointly learning diagnostics and intervention policies.

  2. The paper also makes an interesting observation that conditional on the underlying state, one can exploit the structure of the problem that intervention may be shared across different diagnostics. This inspired RA-PEVI, which uses this structure to pool selectively labeled evidence and improve data efficiency in offline learning. The paper further shows the sample complexity guarantee for the proposed algorithm.

Critical weaknesses
  1. The algorithm and theoretical results need clearer exposition and interpretation. Sections 4 and 5 are notation-heavy, making the main ideas difficult to follow. For example, Section 4.1 would benefit from an intuitive explanation of the decomposition in Equation (3), particularly what Q and K represent and why estimating them separately helps exploit selectively revealed damage labels. Similarly, Section 4.3 introduces alpha-vector dynamic programming without sufficient background for readers unfamiliar with POMDP planning. Section 5 should better explain the significance of the finite-sample guarantees, including how coverage, label availability, and problem dimensions affect sample complexity. A comparison with an approach that does not exploit shared transition structure would help clarify the theoretical benefit of the proposed method.

  2. The empirical evaluation is too narrow to establish broad practical relevance. Given the paper’s motivation in real-world tool-using agents, the experiments provide limited evidence of generality. They cover one synthetic workflow and a controlled AppWorld protocol involving simple file-system operations. These settings help isolate the proposed mechanisms but leave open whether the approach remains effective across diverse tasks, richer damage dynamics, and realistic diagnostic and intervention procedures. Evaluation on additional environments and more varied agent workflows would substantially strengthen the practical claims.

Questions for authors
  1. Can the authors compare sample complexity with a similar algorithm that estimates separate transitions for each diagnostic branch? How does RA-PEVI improve dependence on other aspects of the algorithm, e.g., the number of diagnostics?

  2. How well do the empirical gains from the existing experiments generalize?

3 comments
AuthorsOpenReview ↗

Author Rebuttal (1/2)

Thank you for recognizing the practical importance and algorithmic design of our work. We address your comments below.

W1 & Q1: Algorithm and Theoretical Clarifications

Why decompose the transition into Q and K Let $u_h=(x_{h+1},e_h,z_h)$ denote the observable outcome after an intervention. We decompose the joint transition into

$T^\star_{h,i}(d',u\mid d,x)=Q^\star_{h,i}(u\mid d,x)K^\star_{h,i}(d'\mid d,x,u)$.

This follows from the conditional probability chain rule. $Q$ models the observable intervention outcome and requires only the source damage label, $ K$ models the next damage state conditioned on the outcome and requires both source and destination damage labels. Estimating $Q$ and $K$ separately allows us to use all source-labeled transitions for $Q$ and the subset with paired labels for $K$. In contrast, directly estimating the joint transition requires both labels for every sample, discarding transitions with missing destination labels. Thus, decomposition makes more effective use of the offline data.

About transition sharing The diagnostics in our model are read-only. Given the same underlying damage state, context, and intervention, the transition is identical across diagnostic branches. Thus, transitions observed under different diagnostic branches provide samples from the same underlying dynamics and can be pooled for more efficient estimation. A non-sharing method estimates separate transition models for each diagnostic-output branch. This will decrease the effective sample size for each transition estimate. We can show that the suboptimality bounds scale as follows under balanced coverage across $B$ relevant diagnostic-output branches:

  • RA-PEVI (sharing): $\widetilde{O}(\sqrt{C_{\mathrm{lat}}/N})+\epsilon_{\mathrm{plan}}$.
  • Non-sharing: $\widetilde{O}(\sqrt{B C_{\mathrm{lat}}/N})+\epsilon_{\mathrm{plan}}$.

Thus, sharing improves the statistical error term by a factor of $\sqrt{B}$. We will include the formal comparison and complete proof in the revised paper. Sharing also enables cross-branch identification. Proposition 1 in Appendix E shows that a branch without direct samples can still be identified if its underlying latent transitions are covered under other branches.

About the finite-sample guarantee Our existing guarantee scales as $\widetilde{O}(\sqrt{C_{\mathrm{lat}}/N})+\epsilon_{\mathrm{plan}}$. Its main implications are:

  • Coverage: The guarantee depends on whether the offline data cover the transitions needed by an optimal policy. $C_Q$ measures coverage of source-labeled transitions, while $C_K$ measures coverage of transitions with paired source-destination labels. Insufficient coverage of either type can weaken the guarantee.
  • Label availability: Q only requires source labels, whereas K requires paired labels. Therefore, even with many logged trajectories, insufficient paired labels can become the main bottleneck.
  • Problem dimensions and diagnostics: The number of shared transition rows is $H|\mathcal{D}||\mathcal{X}||\mathcal{I}|$. Importantly, it does not multiply by the number of diagnostic-output branches, since the same transition model is shared across them. Larger state, intervention, and outcome spaces still increase estimation complexity, while additional diagnostics may affect label coverage and planning complexity.

We will explain these dependencies more clearly in Section 5, including the dimension-explicit bound in Appendix D.3.

About alpha-vector dynamic programming Alpha-vector is a classical planning method for finite-horizon POMDPs, where the true state is hidden and decisions rely on partial observations [1,2]. In our problem, the harness maintains a belief $b$ over possible damage states and chooses diagnostics and interventions based on this belief and future observations. The key idea of alpha-vector planning is to represent each contingent plan (i.e., a strategy that specifies actions according to future observations) by a vector $\alpha$, whose entries give the expected total cost under each possible damage state. Its expected cost under belief $b$ is simply $b^\top\alpha$, and the planner selects the plan with the lowest expected cost.

Since the horizon and all action and observation spaces are finite, there are finitely many such plans. Thus, the value function is the minimum of finitely many linear functions of the belief, yielding the standard piecewise-linear and concave representation. Importantly, our pessimism penalty is an additional cost depending on the latent state and intervention, so it can be incorporated into the alpha vectors without changing this representation. This allows exact planning over the continuous belief space without discretization, as established in Appendix F (Proposition 3). We will add this explanation to Section 4, and improve the overall readability of the paper.

AuthorsOpenReview ↗

Author Rebuttal (2/2)

W2 & Q2: Evaluation on More Diverse Tool-Using Tasks

While our primary contribution is the learning framework and its theoretical guarantees, we agree that broader empirical evaluation is important. Following this suggestion, we conducted additional experiments on τ-bench.

τ-bench [3] evaluates agents through multi-turn interactions with simulated users. Agents must follow domain-specific policies, call APIs, and complete tasks whose outcomes are evaluated against target database states. We use the Retail domain, which covers diverse customer-service tasks, including identity verification, order and product queries, cancellations, returns, exchanges, and modifications of orders and customer information.

Both the base agent and user simulator use fixed GLM-5.3-Flash models, with the original Retail policies and tools. To instantiate persistent hidden damage, we introduce a controlled perturbation: after a successful tool execution, the customer's protected profile address is modified in the background with a probability of 15%. The harness maintains a belief over the resulting damage states and chooses among three diagnostics (skip, partial ZIP-code check, and full audit) and three interventions (execute, block, and repair). We collect 24 offline trajectories containing 218 tool-level transitions. All learned methods use the same frozen dataset and are evaluated on the same 20 held-out tasks, covering identity verification, order and product queries, cancellations, returns, exchanges, and modifications of orders and customer information. We compare RA-PEVI with a no-protection baseline, the Plug-in planner (without pessimism), and the Branch PEVI (which estimates separate transition models for each diagnostic-output branch).

MethodFinal DB success ↑Residual damage ↓Cost ↓
No protection11/20 (55%)9/20 (45%)11.250
Plug-in planner11/20 (55%)9/20 (45%)11.279
Branch PEVI13/20 (65%)6/20 (30%)8.006
RA-PEVI16/20 (80%)3/20 (15%)4.390

The cost is computed using the objective defined in our paper. These results show that the base agent is insufficient to handle persistent hidden damage, while RA-PEVI substantially improves task success and reduces residual damage. They also provide evidence of its applicability beyond the original synthetic and AppWorld settings. We will incorporate these results and clarify the applicability conditions in the revised paper.

Finally, we emphasize that RA-PEVI applies to a broad class of stateful tool-use environments where hidden states affect future outcomes, diagnostic information is available, and intervention dynamics are exactly or approximately shared across diagnostic branches. Our extensions accommodate approximate transition sharing, independently calibrated diagnostic models, diagnostic branches without direct samples (when their underlying latent transitions are covered elsewhere), and hard resource budgets (Appendices E–I). These relaxations can further enhance the generality of our algorithm.

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] Smallwood, R. D., & Sondik, E. J. (1973). The optimal control of partially observable Markov processes over a finite horizon. Operations research, 21(5), 1071-1088.
[2] Kaelbling, L. P., Littman, M. L., & Cassandra, A. R. (1998). Planning and acting in partially observable stochastic domains. Artificial intelligence, 101(1-2), 99-134.
[3] 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.

Reviewer_nTmzOpenReview ↗

Follow-up on Authors' Response

I thank the authors for the detailed clarification and additional experiments. The explanations of the transition decomposition, alpha-vector planning, and coverage dependence substantially address my questions about the intended formulation. The comparison with non-sharing methods is helpful. The revised draft should explain when the improvement is substantial, for example, in settings with many diagnostic-output branches, and how it reduces the amount of data needed to achieve comparable performance. The draft should also distinguish more clearly the technical novelty of the analysis from the use of established POMDP planning and concentration techniques.

I appreciate the additional τ-bench experiment, which extends the evaluation beyond the original settings and provides encouraging results. But the scale seems rather limited, which leaves uncertainty about robustness and applicability to more diverse agent induced damage.

The response helps clarify the authors’ intentions, but substantial revisions are still needed to better explain the theoretical contribution and strengthen the empirical evidence. I therefore maintain my recommendation that the paper undergo a major revision before publication.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.