acceptodds
Under review as a conference paper at ICLR 2027

Counterfactual Regret for Reflective Agents with Lean-Verified Guarantees

Abstract

Reflective language agents reuse feedback and memory to adapt across tasks without updating model weights. However, existing guarantees for policy selection and action generation do not by themselves establish when local reflection yields longterm performance guarantees for the complete agent under resource constraints. In this paper, we address this gap by deriving sufficient conditions for sublinear counterfactual regret from local generation and deployment guarantees, while retaining the native controller. Specifically, we establish a resource-sensitive transfer that bounds full-state deployment discrepancies along actual execution paths and preserves the own-history laws of both learner and comparator. Besides, local generation reliability yields a cumulative generation opportunity bound, linking policy acquisition to long-term performance through an explicit quality, coverage, and hard-budget tradeoff. To verify these guarantees, we formalize the conditional proof chain for all thirteen numbered theoretical results in Lean, including a native instance with repeated policy growth and imperfect validation. Proof sources, declaration mappings, and reproduction instructions are provided in the anonymous supplementary material, with a result-by-result guide in Appendix H.

Primary area:
learning theory
Keywords:
Reflective Agents, Counterfactual Regret, Lean Verification

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_kw9POpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies long-term performance guarantees for reflective language agents that adapt through feedback, memory, and reusable policy generation without updating model parameters. The authors formulate counterfactual regret against resource-feasible alternative procedures operating on their own interaction histories. They introduce a growing-library exponential-weights reference algorithm and derive conditional regret bounds by accounting for policy selection, generation reliability, representation errors, and deployment discrepancies. The analysis incorporates hard resource constraints and provides sufficient conditions for sublinear counterfactual regret. The authors further formalise thirteen theoretical results in Lean and present constructed examples involving verified policy generation, repeated library growth, and imperfect validation. A separate sparse-feedback benchmark establishes near-matching upper and lower regret bounds in a restricted theoretical setting.

Critical strengths
  1. The paper addresses the challenging question of how local reflection, policy generation, and memory-based adaptation can contribute to long-term performance guarantees. The paper separates errors arising from policy generation, selection, representation, alignment, and deployment. This modular treatment helps clarify which conditions are required for transferring local guarantees to the complete agent.

  2. A strong theoretical framework is provided in the paper. The comparison against complete alternative procedures operating on their own histories is well motivated. It accounts for the fact that different actions can lead to different future observations, memories, and available policies. The paper explicitly considers full-state transition discrepancies and their accumulated effect along actual execution paths. Incorporating hard resource budgets into this analysis is a useful technical aspect.

Critical weaknesses
  1. The paper does not provide empirical comparisons against existing reflective-agent methods such as Reflexion or Self-Refine. Although theoretical comparisons with simplified procedures are included, they do not establish how the proposed framework relates to existing methods in practical settings.

  2. Actual computational costs, such as generation and validation time, memory usage, or inference overhead, are not reported in the paper.

  3. The theoretical framework allows for history-dependent environments, but the examples are limited to relatively simple settings. It is unclear how well the guarantees would hold in more challenging nonstationary environments, where policy performance, generation success, or validation accuracy may change over time.

  4. Although the authors establish near-matching bounds for a restricted sparse-feedback benchmark, they do not establish whether the combined generation, representation, and deployment error terms in the main native-agent regret bound are necessary or tight.

  5. Horizon-dependent guarantees are not provided. The concrete no-regret constructions rely on parameters chosen as functions of the task horizon. It is unclear whether similar guarantees can be achieved by an anytime reflective agent that does not know the total number of future tasks in advance.

  6. The paper provides theoretical bounds on deployment errors; these are demonstrated only through constructed mathematical examples. It remains unclear how the deployment assumptions and guarantees would hold for actual reflective language agents operating in practical environments.

  7. The paper is motivated by reflective language agents, but the guarantees rely on several specific assumptions and are demonstrated mainly through constructed mathematical examples. The authors should more clearly distinguish what is proved for these models from what can be expected for general LLM-based reflective agents.

Questions for authors

see the weakness section

5 comments
AuthorsOpenReview ↗

Response to Reviewer kw9P [1/2]

Thank you for recognizing the theoretical framework. Following your suggestions, we added an empirical SQL comparison, an executable theorem instance, joint attainability and an anytime construction. We address W1–W3 here and W4–W7 in Part 2.

W1.

The paper does not provide empirical comparisons against existing reflective-agent methods such as Reflexion or Self-Refine. Although theoretical comparisons with simplified procedures are included, they do not establish how the proposed framework relates to existing methods in practical settings.

A1 (Response to W1).

Following your suggestion, we added a Qwen comparison on repeated SQL reports of overdue balances and received payments. Appendix U uses the same model and business-rule scorer across three request streams, with 24 tasks per method, to examine both task loss and resource use.

The Reflexion-style adaptation keeps verbal memory from external feedback and retries, whereas Self-Refine-style uses draft, critique and revision without intermediate external feedback. The native method first executes a saved query or fallback, then tests a proposal and retains it for later requests only if it passes complete validation.

MethodFinal lossAPI callsTotal tokens
Pure Qwen212423,220
Reflexion-style072106,123
Self-Refine-style87283,010
Native SQL cards10109,646

Reflexion-style had the smallest loss, while native cards used fewer calls and tokens. The logs locate the native controller's 10 losses on the 10 tasks that began without a card of the requested type, with zero loss on the 14 tasks starting with one. This links its performance to acquiring and reusing queries.

All methods had per-task caps of three model calls, 24 domain-validation cases and one intermediate point evaluation, but used different actual feedback and resources. Native cards performed 204 domain-validation cases and registered six cards, while Reflexion-style used 24 external point evaluations. The pilot therefore describes loss–resource tradeoffs under different realized feedback use.

Our theory gives a conditional guarantee for complete procedures evolving on their own histories. Appendix T separately instantiates it using enforced exploration and a fixed preparation schedule, whereas this comparison uses plain Qwen and later card reuse.

W2.

Actual computational costs, such as generation and validation time, memory usage, or inference overhead, are not reported in the paper.

A2 (Response to W2).

We added token, timing and client-memory measurements in Appendix U. Summed API wall times were 67.701 s for Pure Qwen, 155.176 s for Reflexion-style, 198.288 s for Self-Refine-style and 22.270 s for native cards. These are end-to-end client waiting times, including network and provider latency. With at most two concurrent streams, the whole run took 289.797 s and peak whole-client working set was 59.4 MiB.

Generation and validation times are not fully separated, and server inference time and model/GPU memory were unobserved. These measurements describe client-side costs, while the finite instance of the worked example separately caps declared operation credits on every prefix. Request, response and cost records accompany the logs.

W3.

The theoretical framework allows for history-dependent environments, but the examples are limited to relatively simple settings. It is unclear how well the guarantees would hold in more challenging nonstationary environments, where policy performance, generation success, or validation accuracy may change over time.

A3 (Response to W3).

The bound covers changing conditions when the stated contracts hold and all cumulative allowances are sublinear. Following your suggestion, Appendix P.4 states explicit sufficient conditions. In episode ee, ρe\rho_e lower-bounds conditional success after every still-unsuccessful history, and δe\delta_e measures retained-policy quality on that episode's domain. The generation contribution is sublinear when

\sum_en_e(1-\rho_e)^{k_e}=o(T).$$ Appendix P.4 also gives a budget-constrained design rule. If $\sum_e n_e\le T$ and trial quotas can satisfy $k_e\rho_e\ge\lambda_T\to\infty$ within the same hard budget, the failure contribution is at most $Te^{-\lambda_T}=o(T)$. Changes in the deployment domain can raise retained-policy quality error, while longer fault propagation may increase the deployment contribution. Together with sublinear delay, quality and the remaining selection, representation and deployment terms, the failure bound yields a vanishing upper bound on average expected excess loss. Appendix N changes public task types but keeps within-phase sampling and validation fixed.
AuthorsOpenReview ↗

Response to Reviewer kw9P [2/2]

W4.

Although the authors establish near-matching bounds for a restricted sparse-feedback benchmark, they do not establish whether the combined generation, representation, and deployment error terms in the main native-agent regret bound are necessary or tight.

A4 (Response to W4).

For a fixed native controller and lossy representation map, the added Appendix S places all three terms on the same suffix and gives k+G+Enf+EA/4≤RT≤k+G+Enf+EA.k+G+E_{\rm nf}+E_A/4\le R_T\le k+G+E_{\rm nf}+E_A. The generation and representation gaps are exact, while the deployment contribution is attained within a factor four. All can be nonzero together without charging acquisition failure again as a runtime fault. This establishes joint attainability for the fixed interfaces, complementing the benchmark lower bound in Section 4.

W5.

Horizon-dependent guarantees are not provided. The concrete no-regret constructions rely on parameters chosen as functions of the task horizon. It is unclear whether similar guarantees can be achieved by an anytime reflective agent that does not know the total number of future tasks in advance.

A5 (Response to W5).

We added Appendix R, which constructs one causal controller that attempts reflection after tasks 1,4,9,…1,4,9,\ldots until success and retains the repair, using the original fair-template generator and complete validator. It needs no TT input or memory restart. For every T≥1T\ge1, RT≤min⁡T,25/4,B(t)=2⌊t⌋+4.R_T\le\min\\{T,25/4\\},\qquad B(t)=2\lfloor\sqrt t\rfloor+4. The proof covers consistent observable laws and all operation prefixes, including failed or unfinished attempts, for learner and own-history comparators. This establishes an anytime existence guarantee within the verified-template model.

W6.

The paper provides theoretical bounds on deployment errors; these are demonstrated only through constructed mathematical examples. It remains unclear how the deployment assumptions and guarantees would hold for actual reflective language agents operating in practical environments.

A6 (Response to W6).

Appendix T makes the deployment comparison concrete through a paid output check in the worked example's Qwen/SQLite implementation. With probability 1/41/4, it replaces the first post-preparation report by a broken fallback. Because later prompts, registrations and choices ignore that output, a fault can add at most one unit of task loss, giving the expected allowance EA≤1/4E_A\le1/4. Paired replays inspect this isolation on recorded proposal histories by fixing proposals and evolving both states. If later reflection reads a faulty report, a propagation bound is needed, as discussed in Appendix P.2.

To connect the remaining mechanisms to the model, complete validation and immutable retention establish quality on twelve legal contexts from three snapshots and four parameter settings. A fresh fair mixture of model proposals and uniform exploration over 64 queries containing an audited correct template enforces conditional success at least 1/1281/128 after every unsuccessful history. Each of 32 attempts prepays thirteen operation credits, giving a 418-credit prefix cap with registration and the check. Normal and guided modes are legal to both procedures, while the specified native rule uses normal mode.

At k=32,N=1024k=32,N=1024, three 1,056-task runs had losses 32, 32 and 33 with 418 credits each, while guided own-history comparators spent 14 each with zero loss. Using the conservative enforced ρ=1/128\rho=1/128 floor, this finite instance has a conditional expected-regret certificate of about 883.14<1056883.14<1056, dominated by N(127/128)k≈796.71N(127/128)^k\approx796.71.

W7.

The paper is motivated by reflective language agents, but the guarantees rely on several specific assumptions and are demonstrated mainly through constructed mathematical examples. The authors should more clearly distinguish what is proved for these models from what can be expected for general LLM-based reflective agents.

A7 (Response to W7).

The proved claims are conditional mathematical guarantees, with eighteen results checked in Lean. The finite instance of the worked example supplies mechanisms for specific premises, while the comparison study measures outputs and costs of the adapted methods. The revised abstract and introduction clarify scope, while Appendix P maps premises to the worked example.

To apply the bound to a new agent, its feedback, comparator representation, generation, deployment effects and resources must satisfy the stated conditions. Fresh randomness, normalized causal responses, scorer correctness and code-to-model correspondence remain premises. The Lean proofs cover the mathematical model, with Python, SQLite, the operating system and model server outside their verification. New inputs and feedback paths therefore require renewed quality, coverage and propagation arguments.

Thanks for the rebuttal; most of the concerns have resolved. However, I still have a few follow-up questions:

  1. When the environment, feedback, and agent memory change over time, how can the assumptions used in the Lean-verified results be established in real LLM-based systems?
  2. I appreciate for the additional experiemtns by the authors, but I have doubt about whether the assumptions required for the theoretical regret guarantees are satisfied in these experiments. Have the authors verified these assumptions, and to what extent do the theoretical guarantees apply to the reported experimental results?
Reviewer_UgB4OpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2(+1)
Soundness
2
Read review
Paper summary

Summary: This paper provides a method to bound the counter-factual regret for reflective agents by carefully considering the effect the local changes on the feedback it receives, it's own behaviours, and how these effects aggregate across time. The authors provide a repository where these lean proofs can be verified and built on to understand other systems.

Critical strengths

Understanding the compounding behavior of reflective agents when building software systems is quite complex, and it is impressive to find an approach which can analyse these effects to move towards practical bounds. If this sort of verification can scale, and the bounds can be made tight enough to apply effectively to scalable implementations, then there could be a lot of value in providing these assurances to actual systems.

Critical weaknesses

My main concern with this work is the clarity of it's exposition. On my first read of the abstract and introduction it was difficult to parse or follow because it was not clear the paper was seeking to provide formal checkable guarantees about actual systems as opposed to the common use of "guarantees" in more theoretical works which apply only under several assumptions. Taking a few sentences early to outline the problem, and the concrete real-world use case, precisely enough to leave no room for confusion would help the reader understand the problem this paper is aimed at solving.

My concern with the clarity is not limited to the introduction, as the rest of the work also is much more technical than most readers will be prepared for, and introduces several layers of abstraction which were difficult for me to keep straight. As far as I can tell, this complexity is a reflection of the complexity in the dozens of lean files which are necessary to prove these results. I expect that a good degree of this complexity is not necessary to understand the main statement of the results if one does not need to follow the proof themselves, and that having an explanation at a higher level of abstraction would make the work more accessible. As is often the case with Lean proofs, the main constraint to accepting their validity is accepting the premises and definitions that are used in the statement of the result. Do to the complexity of this statement it is difficult to validate how it would map to a real system.

Relatedly, in order to for a broader audience to be able to effectively engage with this work, I believe it would be effective to have a single worked example where it is clear how each aspect of the formalism maps to it, and how that system would be deployed in the real world. I understand appendix I is aiming to be this concrete, but it still is phrased in terms of the abstractions introduced in this work like records and program identities I find hard to map down to a concrete deployment instance. I find it difficult to ground my understanding of the rest of the work without having a strong grounding in the meaning of these terms.

Questions for authors

Could you describe for me the simplest concrete instance of this problem in a real-world system and help me map the terminology you use to that system?

4 comments
AuthorsOpenReview ↗

Response to Reviewer UgB4 [1/2]

Thank you for pointing out where the exposition obscured the problem and its connection to a system. Following your suggestions, we clarified the scope in the abstract and introduction, placed the worked example and terminology map before the formal model, and added a high-level interpretation in Section 3. We organize the response into four topics, C1–C4, covering the scope, the result, the terminology and the checks needed for application.

C1. Problem and scope.

On my first read of the abstract and introduction it was difficult to parse or follow because it was not clear the paper was seeking to provide formal checkable guarantees about actual systems as opposed to the common use of "guarantees" in more theoretical works which apply only under several assumptions. Taking a few sentences early to outline the problem, and the concrete real-world use case, precisely enough to leave no room for confusion would help the reader understand the problem this paper is aimed at solving.

A1 (Response to C1).

The result is a conditional guarantee for the complete execution of an agent, with Lean checking the mathematical implication from explicit model and interface assumptions to a regret bound. Our practical aim is to make those assumptions inspectable in a concrete workflow, so that a reader can identify what must be established before applying the theorem.

For example, a service repeatedly answers requests for overdue customer balances from invoice and payment records. A controller can obtain candidate SQL repairs from a language model and retain a validated query for later requests. Because a saved query affects many subsequent reports, the question is how the benefits and errors of these local repairs accumulate under a resource budget. Following your suggestion, the abstract now briefly identifies the implemented SQL reporting example and states that we evaluate its cumulative task loss and resource use. The Introduction develops the same example and maps its terminology before the formal model.

C2. Understanding the result without following the proof.

I expect that a good degree of this complexity is not necessary to understand the main statement of the results if one does not need to follow the proof themselves, and that having an explanation at a higher level of abstraction would make the work more accessible.

A2 (Response to C2).

The theorem limits how much more expected task loss our controller can accumulate than the best expected loss within a chosen class of feasible alternatives. Each alternative follows its own history and pays for its own operations, so the comparison concerns complete procedures with their respective feedback and memory.

In the worked example, preparation incurs early errors, failure to acquire a repair can leave many later requests wrong, and a delivery fault can add further loss. The bound controls these effects together with the allowances needed to make the comparison valid, while reflection and validation costs are enforced through separate hard budgets. If the cumulative bound is sublinear uniformly over the comparator class and both sides meet those budgets, the upper bound on average expected excess loss tends to zero. This concerns expected performance across tasks. We added this interpretation before the transfer formulas in Section 3.

AuthorsOpenReview ↗

Response to Reviewer UgB4 [2/2]

C3. A worked system and its terminology.

Could you describe for me the simplest concrete instance of this problem in a real-world system and help me map the terminology you use to that system?

A3 (Response to C3).

Consider a read-only service asked to list overdue balances by customer. A request supplies an invoice/payment snapshot and date parameters. In the recorded execution, the initial SQL returned an undefined-column error. Qwen then proposed a replacement, the validator checked its reports against the business rule on every admitted context, and the first passing query was registered. Under the chosen schedule it was saved during preparation and invoked on subsequent requests after that phase. The following terms describe parts of this same sequence.

TermObject in this workflow
ContextThe database snapshot and requested date, grace period and balance threshold
Execution cardThe immutable SQL together with its fixed interpreter version
IdentityThe registered executable version, whose printed fingerprint is a display name
Task recordThe request, called identity, returned rows or error, score and charges
Behavior stateThe registry, retained-query pointer, proposal/validation memory and resource counters
Native controllerThe program deciding when to propose, validate and invoke registered queries
Guided comparatorA separate procedure obtaining, validating and registering its own approved query before its tasks
Reference processAn auxiliary mathematical selector supplying a bound in the proof

Appendix T records this sequence using actual Qwen proposals and SQLite outputs. The worked example and terminology paragraph at the end of the Introduction connect these objects to the formal model, with further premise mappings in Appendices P and T.

C4. Checking premises in the implemented workflow.

As is often the case with Lean proofs, the main constraint to accepting their validity is accepting the premises and definitions that are used in the statement of the result. Do to the complexity of this statement it is difficult to validate how it would map to a real system.

A4 (Response to C4).

To assess whether the premises fit this workflow, we identify the concrete mechanism supporting each condition. We added this connection explicitly in Appendices P and T. For the finite instance of the worked example, the main obligations map as follows.

PremiseMechanism supporting it in this instance
Retained-policy qualityValidation covers all twelve legal contexts using the same guarded interpreter and business-rule score as deployment. Immutable retention gives δe=0\delta_e=0 within that domain.
Conditional generation coverageThe fixed native rule uses normal mode, where a fresh fair branch mixes Qwen with uniform exploration over 64 queries containing an audited correct template. This mechanism gives ρe≥1/128\rho_e\ge1/128 after every unsuccessful history, independently of observed Qwen success. Both procedures may use guided mode, which returns the approved template.
Hard resource feasibilityFor k=32k=32 trials, each attempt prepays thirteen credits, including failures. At most one registration and one check add one each, so 13k+2=41813k+2=418 bounds every operation prefix. These credits count the declared reflection and validation operations.
Deployment discrepancyWith probability 1/41/4, the paid check replaces the first post-preparation report by a broken fallback. Later control ignores that error, giving EA≤1/4E_A\le1/4.
Reference and score correspondenceThe reference uses the common task score and is attached after preparation through a normalized law preserving the native trajectory distribution. Comparators retain their own registries, feedback and costs.

Execution logs and paired replays let readers inspect proposals, validation outcomes, operation charges and the isolation of the specified delivery fault on recorded histories. These execution checks complement the mechanism arguments in the table.

The conditional proof still assumes fresh randomness, normalized causal model responses, correctness of the business-rule implementation and code-to-model correspondence. Lean checks all eighteen conditional mathematical results, while Python, SQLite, the operating system and model server remain outside that verification. A new deployment domain therefore needs renewed quality and interface arguments.

Reviewer_UgB4OpenReview ↗

Response to Rebuttal

I thank the authors for their clarifications and adjustments to the the papers. The worked examples and grounding it in the context of a real problem helps substantially in interpreting the rest of the formal results. I will be increasing my score accordingly.

AuthorsOpenReview ↗

Response to Reviewer UgB4

We appreciate your recognition of our work. It's very motivating.

Reviewer_s8EeOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper models a reflective agent as an integrated process encompassing policy generation, validation and retention, policy selection and execution, and feedback-driven memory updates. It evaluates long-term performance through counterfactual regret, comparing the agent’s cumulative loss with that of resource-feasible alternative procedures, each evolving under its own interaction history. Its central contribution is a theoretical connection between local mechanisms and end-to-end performance: under explicit conditions on generation reliability, policy quality, deployment stability, and the remaining selection and execution interfaces, the agent achieves sublinear regret, so that its average excess loss relative to the best procedure in the comparator class vanishes asymptotically. The paper also provides concrete mathematical instances satisfying these conditions and reports Lean formalizations of the conditional proof chains for all thirteen numbered theoretical results.

Critical strengths
  • The analysis connects generation, selection, and deployment through explicitly specified interface conditions, making it clear which proof obligations must be re-established when individual components are modified. This modular structure facilitates both scrutiny and reuse. The Lean formalization further supports the verification of consistency across probability laws, task timing, and resource accounting throughout the composed argument.

  • The paper recognizes that a single validation error can cause an incorrect policy to remain active across many subsequent tasks. By analyzing full-state transitions and their downstream effects, the framework accounts for the cumulative consequences of such errors rather than restricting attention to their immediate cost. This treatment strengthens the analysis of reflective agents, whose current decisions shape future memory, policy availability, and execution.

Critical weaknesses
  1. Verifiability of the assumptions. The guarantee still requires a bound on the performance gap between the native controller and the reference algorithm. Could the authors explain how this condition can be derived from concrete properties of the controller?

  2. Value of the full framework. In Appendix N, direct calculation yields a tighter bound than the general transfer framework. Could the authors provide a more natural example demonstrating the framework’s advantage over direct analysis?

  3. Clarification of technical novelty. The selection analysis builds on established techniques, including Fixed Share and growing-expert tracking. Could the authors clarify which new mathematical obstacle arises when extending these techniques to complete reflective executions, and how their analysis resolves it?

Questions for authors

See weaknesses.

2 comments
AuthorsOpenReview ↗

Response to Reviewer s8Ee [1/2]

Thank you for the questions on verifiability, composition and novelty. Following your suggestions, we added the native-to-reference derivation in Appendix P.1, an executable instance of the worked example in T and the runtime replacement in Q, and clarified the own-history obstacle in Sections 1 and 3. We address W1 here and W2–W3 in Part 2.

W1.

Verifiability of the assumptions. The guarantee still requires a bound on the performance gap between the native controller and the reference algorithm. Could the authors explain how this condition can be derived from concrete properties of the controller?

A1 (Response to W1).

The native-to-reference comparison follows from the controller's validation, retention and calling rules in the worked example of Appendix T. The controller uses a broken query with unit loss for kk preparation tasks and makes one trial after each task. The next NN tasks call the retained query or the broken fallback. A paid output check can corrupt the first suffix report. The clean execution removes that delivery fault while keeping the charge. Source code and complete execution logs are available in the anonymous repository.

Fix a completed preparation history hh, and let ξ(h)=1\xi(h)=1 if no passing query was retained and 00 otherwise. Validation checks every legal future context, so every passing query has zero loss throughout this domain. The first passing query is retained immutably and called throughout the suffix if one exists. Otherwise the broken fallback is used. Thus the clean suffix loss is Nξ(h)N\xi(h), and adding the kk preparation losses gives the clean total k+Nξ(h)k+N\xi(h).

After this history is complete, the two reference arms have per-task losses 11 and ξ(h)\xi(h). Let Jsel(h)J_{\rm sel}(h) denote the reference's expected suffix loss conditional on hh. Every reference choice loses at least ξ(h)\xi(h) per task, giving Nξ(h)≤Jsel(h)N\xi(h)\le J_{\rm sel}(h) and hence k+Nξ(h)−Jsel(h)≤k.k+N\xi(h)-J_{\rm sel}(h)\le k. Averaging over hh gives JAref−Jsel≤kJ_A^{\rm ref}-J^{\rm sel}\le k, where these endpoints are the expected clean total and expected reference suffix loss. This is the learner-reference comparison in Eq. (13), with F=kF=k charging displaced preparation tasks once. The clean-prefix boundary allowance Pb\mathcal P_b and score-calibration allowance DAD_A vanish because slots contain one task, the response scale is zero and scores agree.

The check's faulty-output branch contributes a separate deployment term. For fixed hh, it replaces only the first suffix report with probability 1/41/4, adding expected loss 14(1−ξ(h))\frac14(1-\xi(h)). It leaves future control state unchanged, and later calls never read that result, so the error cannot propagate. Averaging over hh gives EA=14Pr⁡(ξ=0)≤14E_A=\frac14\Pr(\xi=0)\le\frac14. If later reflection reads the faulty report, its downstream effects need their own bound.

To connect these calculations to the procedures' own-law objectives, Appendix T appends a normalized reference law only after preparation. Summing it out preserves the complete native trajectory law, including the check outcome. Each comparator keeps its own registry, feedback and costs, and the construction establishes common scoring and task-clock correspondences. Thus the comparisons apply to complete executions under their respective laws.

The generation and resource interfaces are checked separately. A fresh fair choice between a model proposal and a uniform draw from 64 queries containing an audited correct query gives a conditional probability of validation and retention at least 1/1281/128 after every unsuccessful history. Each attempt prepays thirteen operation credits, including failures, while at most one registration and one check add one credit each, giving the hard prefix cap 13k+213k+2 declared operation credits. The native-to-reference inequality above does not use this probability floor or resource cap.

Appendix N gives a different example with imperfect validation. An incorrect acceptance can overwrite a correct pointer and remain active throughout the suffix. The resulting expected deployment excess is at most NβmN\beta_m per phase, separately from acquisition failure, where βm=2−m\beta_m=2^{-m}.

AuthorsOpenReview ↗

Response to Reviewer s8Ee [2/2]

W2.

Value of the full framework. In Appendix N, direct calculation yields a tighter bound than the general transfer framework. Could the authors provide a more natural example demonstrating the framework’s advantage over direct analysis?

A2 (Response to W2).

We agree that the direct recurrence in Appendix N is tighter. The framework’s advantage here is proof reuse when an implementation changes, because a local contract can cover a family of runtime laws while the unaffected generation and reference arguments remain valid. Following your suggestion, Section 5 explains this proof reuse, and Appendix Q instantiates it by replacing only the paid runtime check of the verified-template instance in Appendix I. A delivery fault can then persist for up to HH scored tasks before reset.

ObjectRetained or rebuilt obligation
Generation, validation, retention and callingRetain the native rules and generation certificate
Comparator class, reference and resourcesRetain reference recursion, observation moments, path code and prefix-cost proof
Runtime moduleRebuild the local deployment edge
Complete execution lawRebuild the normalized coupling with the changed native marginal

For each fixed completed history hh, the registry and selected program are fixed. The entry-bit law satisfies TV⁡(ph,δ0)≤ε\operatorname{TV}(p_h,\delta_0)\le\varepsilon, and the continuation-value span over that bit is at most HH. The range–TV calculation therefore gives a conditional charge at most HεH\varepsilon, and averaging over hh yields EA≤HεE_A\le H\varepsilon. This span is conditional on hh, allowing successful and unsuccessful preparation histories to have different baseline losses.

Appendix P.2 gives the corresponding reset condition for a service. For every remaining horizon, expected losses beyond the next HH tasks must agree over all compared complete next states, including relevant memory, pending operations and external side effects.

Thus each admissible history-dependent php_h can use the same retained proof components and the new local deployment certificate. For η>0\eta>0, the transfer gives RT≤k+N2−k+log⁡2η+ηN+Hε.R_T\le k+N2^{-k}+\frac{\log2}{\eta}+\eta N+H\varepsilon. As a check, Bernoulli entry noise with k=2,N=4,H=2,ε=1/4k=2,N=4,H=2,\varepsilon=1/4 gives exact expected loss 27/827/8 and deployment excess 3/83/8 under the same six-credit cap. These values verify a nonzero persistent effect in the replacement instance.

W3.

Clarification of technical novelty. The selection analysis builds on established techniques, including Fixed Share and growing-expert tracking. Could the authors clarify which new mathematical obstacle arises when extending these techniques to complete reflective executions, and how their analysis resolves it?

A3 (Response to W3).

Fixed Share supplies the standard reference selection component. The additional obstacle is that a reflective comparator changes the history on which its future cards, feedback and decisions depend. A card acquired on that history may be unavailable to the learner. Allowing the learner to use it violates availability, while evaluating the comparator on the learner’s history changes the own-history comparison. We clarified this obstacle in Sections 1 and 3.

To address availability, the analysis constructs a causal available substitute and charges its generation gap under explicit coverage and quality conditions. For comparator μ\mu, episode delay τe\tau_e, suffix length nen_e, quality error δe\delta_e, conditional success floor ρe\rho_e and kek_e attempts, Theorem 11 gives gTgen(μ)≤∑eτe+ne[δe+(1−ρe)ke].g_T^{\rm gen}(\mu)\le\sum_e\\{\tau_e+n_e[\delta_e+(1-\rho_e)^{k_e}]\\}. The floor must hold after every still-unsuccessful history, so repeated conditioning yields the failure term without independent-attempt assumptions. Success includes validation, retention and causal access to a sufficiently good card.

To preserve own-history comparisons, the joint experiment must reproduce the procedures’ complete trajectory laws, (r_A)_{\\#}\Gamma=\mathbb{P}_A and (r_{\mu})_{\\#}\Gamma=\mathbb{P}_{\mu}, and respect task and scoring correspondences. In Q, this is achieved by attaching a normalized conditional reference law to the actual preparation and replacement-runtime laws, so summing out the reference restores the changed native law and the comparator keeps its own law. Full-state stability then bounds downstream runtime effects along actual paths, with paid updates and hard resources controlling accumulation. The transfer combines these comparisons with the reference selection bound while retaining the native controller’s execution rules.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.