betaFeedback

WorksComputer Science

Learn then Bet: Learning Interpretable Rules for Reliable Agent Intervention

Abstract

Autonomous agents now run for hundreds of steps with little or no human supervision. In practice, practitioners use runtime monitors such as turn limits and keyword filters to decide when a run should be stopped, upgraded, or assisted. However, these heuristics may stop runs that would otherwise succeed or allow failing runs to continue. To address this limitation, we introduce LeBet (Learn then Bet), a statistical learning framework that derives its learning objective from sufficient conditions for valid and powerful intervention. In particular, LeBet learns an interpretable OR-of-AND monitor and accumulates evidence through a fixed betting statistic, intervening when the evidence reaches a prescribed threshold. Under finite within-class exchangeability and leave-one-out stability, we derive finite-sample guarantees for false-positive control (validity) and detection power conditional on the training data, using the same trajectories for learning and calibration without assuming independent and identically distributed trajectories. To address the intractable combinatorial optimization problem in our learning formulation, we use stochastic local search that leverages the monitor's Boolean structure to propose rule edits aimed at improving empirical separation. On SWE-bench Lite with Ministral 3 8B, the learned monitor saves 34.46%34.46\% of input-plus-output tokens and increases output precision from 18.33%18.33\% to 21.59%21.59\%. The empirical false-positive rate is 13.64%13.64\%. Our results show how to formalize the learning problem over interpretable rule sets with statistical conditions and establish training-conditional guarantees for reliable intervention based on partial histories.

Introduction

Large language model (LLM) agents are increasingly used to solve complex tasks through multi-step reasoning, tool use, and interaction with external environments. Early agent systems such as ReAct (Yao et al., 2023) interleave reasoning and actions, while later work introduces explicit workflow states, memory management, and search over alternative decisions to improve long-horizon execution (Wu et al., 2024; Zhang et al., 2026; Wei et al., 2026). Recent work also studies how to allocate models, tools, and computation across agent pipelines, reflecting the growing cost and complexity of long-running agents (Hua et al., 2026a; Gao and Peng, 2025). As agents operate for longer horizons with less human supervision, failures may arise at intermediate steps and propagate through the remaining trajectory. It is therefore important to have a monitoring system that observes the evolving trajectory and decides when intervention is needed (Gao and Peng, 2025; Rabanser et al., 2026; Mittapalli et al., 2026; Modgil, 2026).

Existing work on runtime monitoring follows two main directions. One line takes a verifier or monitoring output as given and converts it into an online decision rule with statistical guarantees [13] (Sadhuka et al. 2026; Schirmer et al. 2026; Prinster et al. 2026). These guarantees specify conditions under which the supplied signal can support valid intervention and control false alarm risk. Some of these methods use calibration procedures similar to conformal methods [2] to provide finite-sample risk control conditional on the calibration set. Another line learns a monitor or a model of agent behavior from trajectory data and uses it to predict failures during execution (Wang et al., 2026b,a; Xiang et al., 2025; Chen et al., 2025). The training objective shapes the signal supplied to the decision rule, including its behavior on trajectories where intervention is unnecessary or needed, and the resulting signal can then be calibrated on a separate calibration set to control the false-positive probability. Together, these directions suggest incorporating the requirements for false-alarm control and detection power into the monitor’s learning objective, motivating the following question: Can the statistical requirements of reliable intervention guide the learning process?

In this paper, we answer this question through LeBet (Learn then Bet). We formulate agent intervention as a statistical learning problem over complete trajectories while requiring the learned monitor to operate only on the evolving trajectory prefix. Our contributions are as follows:

  1. Learning formulation and algorithm design (Algorithm 1). Rather than first training a general verifier and then calibrating it, we use testing by betting (Ramdas and Wang, 2025) as an online decision framework to identify statistical conditions sufficient for reliable intervention. We formulate the search for a rule set satisfying these conditions as a learning problem. For interpretability, we restrict the learning class to OR-of-AND rule sets (Xin et al., 2022; Perreault et al., 2026). Due to the intractable combinatorial optimization problem for learning rule sets (Malioutov and Varshney, 2013), we adapt FastSRS (Molero-Río et al., 2026) to optimize the empirical separation underlying our intervention guarantees. The key insight is that Boolean identities and monotonicity guide the choice of rule modifications (Yang et al., 2021).

  1. Training-conditional guarantees (Theorem 5). Standard sample-splitting approaches use separate training and calibration sets (Vovk, 2013). Following the approach of Liang and Barber (2025), we extend their stability argument to calibration within intervention classes, replacing independent and identically distributed (i.i.d.) sampling with a finite within-class exchangeable extension and leave-one-out stability averaged over training-sample exchanges. We prove finite-sample bounds of a Probably Approximately Correct (PAC) form for the conditional false-positive and missed-detection probabilities, using the same trajectories for learning and calibration. These bounds quantify the intuitive tradeoff between separation, instability, and the evidence required for detection. In particular, betting allows us to introduce an error budget that controls the trade-off between false intervention and detection. The underlying argument may be of independent interest for training-conditional inference under finite exchangeability.

  1. Empirical illustration (§ 0.9). On SWE-bench Lite (Jimenez et al., 2024) with a Ministral 3 8B (Liu et al., 2026) coding agent, the learned monitor saves 34.46% of input-plus-output tokens and increases output precision from 18.33% to 21.59% with the false-positive rate 13.64%.

4. Lean 4 verification (Supplement). The formal proofs are machine-checked by Lean 4 (de Moura and Ullrich, 2021; de Moura et al., 2015). We encode the paper’s definitions and theorem statements as Challenges and use Comparator (Lean FRO) to check that Solutions do not weaken the claims or introduce additional assumptions.

Preliminaries

Throughout, N:={0,1,…}\mathbb{N} := \{0,1,\ldots\}, [n]:={1,…,n}[n] := \{1,\ldots,n\}, and [a]+:=max⁡{a,0}[a]_{+} := \max\{a,0\}. We write ∣A∣|A| for the cardinality of a finite set AA, and ⌊a⌋\lfloor a\rfloor and ⌈a⌉\lceil a\rceil for the floor and ceiling of aa. We use standard probabilistic notation (Chung, [15]). The symbol =d\overset{d}{=} denotes equality in distribution. Let (Ω,F∞,P)(\Omega,\mathcal{F}_{\infty},\mathbb{P}) be a probability space. We write σ(Z)\sigma(Z) for the σ\sigma-algebra generated by ZZ. A filtration F:=(Ft)t∈N\mathcal{F} := (\mathcal{F}_{t})_{t\in\mathbb{N}} is an increasing sequence of sub-σ\sigma-algebras of F∞\mathcal{F}_{\infty}. We write EP\mathbb{E}^{\mathbb{P}} and EP[⋅∣Ft]\mathbb{E}^{\mathbb{P}}[\cdot\mid\mathcal{F}_{t}] for expectation and conditional expectation under P\mathbb{P}, respectively. A process (Xt)t∈N(X_t)_{t\in\mathbb{N}} is adapted if XtX_t is Ft\mathcal{F}_t-measurable for every tt. When XtX_t is binary, EP[Xt∣Ft−1]=P(Xt=1∣Ft−1)\mathbb{E}^{\mathbb{P}}[X_t \mid\mathcal{F}_{t-1}] = \mathbb{P}(X_t = 1 \mid\mathcal{F}_{t-1}) for t≥1t \ge1. A random variable τ\tau taking values in N∪{∞}\mathbb{N} \cup\{\infty\} is a stopping time if {τ≤t}∈Ft\{\tau\le t\} \in\mathcal{F}_t for every tt. For p∈[0,1]p \in[0,1], Ber⁡(p)\operatorname{Ber}(p) denotes the Bernoulli distribution with mean pp. For p,q∈(0,1)p,q \in(0,1), its Kullback–Leibler divergence is DKL(Ber⁡(p)∥Ber⁡(q)):=plog⁡(p/q)+(1−p)log⁡((1−p)/(1−q))D_{\mathrm{KL}}(\operatorname{Ber}(p)\Vert\operatorname{Ber}(q)) := p\log(p/q) + (1-p)\log((1-p)/(1-q)). We write ∨\lor and ∧\land for logical OR and AND, respectively. An empty disjunction equals zero. We write 1{A}\mathbf{1}\{A\} for the indicator of an event AA and use the convention inf⁡∅=∞\inf\varnothing= \infty. All logarithms are natural. We use the endpoint conventions 0log⁡(0/q)=00\log(0/q) = 0, plog⁡(p/0)=+∞p\log(p/0) = +\infty for p>0p > 0, and e−∞=0e^{-\infty} = 0. For a finite family (vi)i∈I(v_i)_{i\in\mathcal{I}} of real values and k∈[∣I∣]k \in[|\mathcal{I}|], v(k:I)v_{(k:\mathcal{I})} denotes the kkth smallest value, counting repetitions. We write vectors in bold. For a vector V=(v1,…,vN)\mathbf{V} = (v_1,\ldots,v_N) and an index vector I=(i1,…,ir)\mathbf{I} = (i_1,\ldots,i_r) with distinct entries in [N][N], write VI:=(vi1,…,vir)\mathbf{V}_{\mathbf{I}} := (v_{i_1},\ldots,v_{i_r}) for the subvector ordered by I\mathbf{I}. We use I:={i1,…,ir}\mathcal{I} := \{i_1,\ldots,i_r\} for the corresponding index set, ignoring order. We summarize additional notation in Appendix A. Appendix G collects auxiliary lemmas used in the proofs.

Problem Statement: Statistical Modeling of LLM Agents

An LLM agent is specified by a system prompt and a tool set (where skills, MCP servers, and other capabilities are special cases of tools) and interacts with an environment through a ReAct loop (Yao et al., 2023). Formally, let Zt\mathcal{Z}_t denote the space of interaction histories of length tt, and let Z:=⋃t≥0Zt\mathcal{Z} := \bigcup_{t\ge0}\mathcal{Z}_t denote the space of all finite interaction histories, Rtrace\mathcal{R}_{\mathrm{trace}} the space of reasoning traces, Atool_call\mathcal{A}_{\mathrm{tool\_call}} the space of tool-call actions, and O\mathcal{O} the space of observations. The agent policy may be viewed as a map f:Z→Rtrace×Atool_callf:\mathcal{Z}\to\mathcal{R}_{\mathrm{trace}}\times\mathcal{A}_{\mathrm{tool\_call}}, and executing an action produces an outcome in O\mathcal{O}. Both the agent policy ff and environment outputs may be deterministic. However, determinism of the underlying mechanism does not preclude statistical modeling. This perspective is standard in deterministic computer experiments ([7] (Sacks et al. 1989; Vaart 1998)), where repeated evaluation at the same input produces the same output, but the unknown response function is nevertheless modeled statistically for prediction and uncertainty quantification. We take the same view of agent–environment interactions. In particular, let (Ω,F∞)(\Omega,\mathcal{F}_{\infty}) be a measurable sample space whose elements specify single agent–environment interactions. For ω∈Ω\omega\in\Omega, let O0(ω)O_0(\omega) denote the initial request. At each step t≥1t\ge1, the agent produces (Rt(ω),At(ω))=f(Zt−1(ω))(R_t(\omega),A_t(\omega))=f(Z_{t-1}(\omega)), and executing At(ω)A_t(\omega) in the environment produces the observation Ot(ω)O_t(\omega). The resulting trajectory is

Zt(ω)=(O0(ω),R1(ω),A1(ω),O1(ω),…,Rt(ω),At(ω),Ot(ω)).Z_t(\omega) = (O_0(\omega), R_1(\omega), A_1(\omega), O_1(\omega), \ldots, R_t(\omega), A_t(\omega), O_t(\omega)).

For a fixed ω\omega, the entire agent–environment interaction is fully deterministic. Since ZtZ_t contains the history up to time tt, the trajectory process (Zt)t∈N(Z_t)_{t\in\mathbb{N}} is adapted to its natural filtration (σ(Zt))t∈N(\sigma(Z_t))_{t\in\mathbb{N}}. Let Z∞(ω)Z_\infty(\omega) denote the complete agent–environment trajectory in the absence of intervention. In hindsight, one can assess whether intervention was necessary for the agent to achieve an acceptable outcome. We encode this application-dependent judgment by the binary label Y:Ω→{0,1}Y:\Omega\to\{0,1\}, determined by Z∞(ω)Z_\infty(\omega), with Y(ω)=1Y(\omega)=1 indicating that intervention was needed and Y(ω)=0Y(\omega)=0 indicating that the agent could have proceeded without intervention. All trajectory and label maps are assumed measurable.

References

  1. [1]Anastasios N. Angelopoulos, Stephen Bates, Emmanuel J. Candès, Michael I. Jordan, and Lihua Lei. Learn then test: Calibrating predictive algorithms to achieve risk control. The Annals of Applied Statistics, 19(2):1641 – 1662, 2025. doi: 10.1214/24-AOAS1998. URL https://doi.org/10.1214/24-AOAS1998.
  2. [2]Anastasios N. Angelopoulos, Rina Foygel Barber, and Stephen Bates. Theoretical Foundations of Conformal Prediction. Cambridge University Press, 2027.
  3. [3]Maria-Florina Balcan and Nicholas J. A. Harvey. Submodular Functions: Learnability, Structure, and Optimization. SIAM Journal on Computing, 47(3):703–754, 2018. doi: 10.1137/120888909. URL https://doi.org/10.1137/120888909.
  4. [4]Rémi Bardenet and Odalric-Ambrym Maillard. Concentration inequalities for sampling without replacement. Bernoulli, 21(3):1361 – 1385, 2015. doi: 10.3150/14-BEJ605. URL https://doi.org/10.3150/14-BEJ605.
  5. [5]Sebastian Becker, Patrick Cheridito, and Arnulf Jentzen. Deep Optimal Stopping. Journal of Machine Learning Research, 20(74):1–25, 2019. URL http://jmlr.org/papers/v20/18-232.html.arxiv.org/abs/1804.05394
  6. [6]Michael Bian and Rina Foygel Barber. Training-conditional coverage for distribution-free predictive inference. Electronic Journal of Statistics, 17(2):2044–2066, 2023. doi: 10.1214/23-EJS2140. URL https://doi.org/10.1214/23-EJS2140.
  7. [7]David Blackwell. Comparison of Experiments. In Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability, volume 2, pages 93–103. University of California Press, January 1951. URL https://projecteuclid.org/ebooks/berkeley-symposium-on-mathematical-statistics-and-probability/Proceedings-of-the-Second-Berkeley-Symposium-on-Mathematical-Statistics-and/ chapter/Comparison-of-Experiments/bsms/1200500222.DOI
  8. [8]Akash Bonagiri, Devang Borkar, Gerard Janno Anderias, Setareh Rafatirad, and Houman Homayoun. CausalFlow: Causal Attribution and Counterfactual Repair for LLM Agent Failures, May 2026. URL http://arxiv.org/abs/2605.25338. arXiv:2605.25338 [cs.LG].
  9. [9]Olivier Bousquet and André Elisseeff. Stability and Generalization. Journal of Machine Learning Research, 2(Mar):499–526, 2002. ISSN ISSN 1533-7928. URL https://www.jmlr.org/papers/v2/bousquet02a.html.
  10. [10]Ting-En Chao, Yu Huang, Hao Dai, Gary G. Yen, and Vincent S. Tseng. Early Time Series Anomaly Prediction With Multi-Objective Optimization. IEEE Transactions on Emerging Topics in Computational Intelligence, 9(1):972–987, 2025. doi: 10.1109/TETCI.2024.3423472.
  11. [11]Wenjing Chen and Victoria Crawford. Bicriteria Approximation Algorithms for the Submodular Cover Problem. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 72705–72716. Curran Associates, Inc., 2023. doi: 10.52202/075280-3178. URL https://proceedings.neurips.cc/paper_files/paper/2023/file/e5eaf67f3405be58cd12848a89cd8ace-Paper-Conference.pdf.DOI
  12. [13]Young Hyun Cho and Will Wei Sun. When Should an AI Workflow Release? Always-Valid Inference for Black-Box Generate-Verify Systems, May 2026. URL http://arxiv.org/abs/2605.12947. arXiv:2605.12947 [stat.ML].
  13. [14]Yuan Shih Chow and Henry Teicher. Probability Theory: Independence, Interchangeability, Martingales. Springer Texts in Statistics. Springer, New York, NY, 1997. ISBN 978-0-387-40607-7 978-1-4612-1950-7. doi: 10.1007/978-1-4612-1950-7. URL http://link.springer.com/10.1007/978-1-4612-1950-7.DOI
  14. [15]Kai Lai Chung. A course in probability theory. Elsevier, 2000.
  15. [16]Sanjeeb Dash, Oktay Gunluk, and Dennis Wei. Boolean Decision Rules via Column Generation. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.arxiv.org/abs/1805.09901

Paper details

vlnc:W_xrs5hyan
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 7

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

AI agents, AI

View statement
Looking for related papers…
Contents