acceptodds
Under review as a conference paper at ICLR 2027

Fixed-Budget Agentic Pure Exploration with Judges

Abstract

Pure exploration typically assumes that the learner can directly choose which actions to evaluate. However, agentic systems often differ from this classical interaction model because the actions available for evaluation are generated contextually by an agent from a large implicit space rather than directly selected by the learner, as in reasoning-and-acting (ReAct) systems and automated scientific discovery. We initiate the study of fixed-budget agentic pure exploration with judges, where a black-box action generator repeatedly proposes a small candidate set from a potentially large or infinite action space, and a separate judge decides which candidate to execute. The learner is additionally given offline reward data from different context–action pairs, together with a function class that captures shared reward structure across these pairs. The goal is to identify a near-optimal action for a target context (e.g., task) after a fixed budget of online interactions, even though the learner can only evaluate actions exposed by the generator. The offline data narrow the set of plausible reward functions, while online feedback progressively resolves the remaining uncertainty at the target context. We develop a simple judge that uses this evolving uncertainty through function class refinement, optimistic exploration, and pessimistic final selection. We establish a fixed-budget success guarantee whose error decays exponentially with the online budget, together with a nearly matching information-theoretic lower bound. The results show that the additional penalty induced by imperfect action generation is unavoidable in the worst case, while retaining the standard dependence on the remaining statistical parameters. Finally, we empirically evaluate the proposed framework and show improvements over corresponding baselines.

Primary area:
reinforcement learning
Keywords:
Agentic pure exploration, Judge, Fixed-budget

Reviews

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

This work considers a pure exploration problem where the goal is to maximize the probability of returning a near-optimal action after a fixed number of online interactions with additional offline reward observations from related contexts. At each round, an action generator proposes a finite set of candidates from a potentially large action space and a separate judge selects one action to execute and observes its reward. The authors propose an algorithm that uses offline and online reward observations to progressively refine a class of plausible reward functions. More specifically, the judge selects actions optimistically by the highest predicted reward among the remaining functions and the final recommendation is selected pessimistically from previously executed actions. The authors derive an exponentially decreasing error bound and a similar information-theoretic lower bound that characterizes the dependence on reward-function complexity and the generator's probability of proposing near-optimal actions. The method is evaluated on a synthetic problem and on LCBench hyperparameter optimization with noisy reward observations.

Critical strengths
  • This is an interesting problem formulation that extends fixed-budget pure exploration to settings where the actions are proposed by a separate, potentially history-dependent generator rather than selected freely by the learner. The theoretical analysis is rigorous and the upper and lower bounds illustrate the effects of imperfect generator coverage and reward-function complexity.
  • Combining offline reward information with online function class refinement, optimistic action selection, and pessimistic final recommendations gives a principled approach for identifying good actions. And the synthetic experiments demonstrate the effectiveness of the method and provide evidence that both exploration and final decoding are important.
Critical weaknesses
  • The guarantees rely on a realizable reward-function class and a positive probability that the generator proposes near-optimal actions. The experiments do not use an actual history-dependent LLM generator and the LCBench reward-function class is not guaranteed to be realizable. It therefore remains unclear how well the theoretical findings characterize practical agentic exploration and the LCBench improvements are relatively modest.
  • Although the offline data from related contexts is important to the method, the empirical investigation on this is limited. There is one ablation demonstrating the benefit of offline observations but their quantity, informativeness, and similarity to the target context should also affect online sample efficiency. The LCBench experiments do not isolate this contribution, making it difficult to determine how much of the improvement comes specifically from offline information transfer.
Questions for authors
  • Could the authors evaluate the method with a history-dependent LLM generator and monitor how its probability of proposing near-optimal actions changes during exploration?
  • How does the quality, quantity, and relevance of offline observations affect the remaining reward uncertainty and online sample efficiency?
  • How sensitive is the method to a misspecified the reward-function class, particularly when the true reward function is not represented by any candidate model?
4 comments

Thank you for your review. We address your concerns and questions below.


Q1: Could the authors evaluate the method with a history-dependent LLM generator and monitor how its probability of proposing near-optimal actions changes during exploration?

A: We conduct additional LCBench experiments using Qwen3.5-0.8B and Qwen3.5-27B as history-dependent LLM action generators. Each generator has access to 128 offline observations throughout exploration and conditions on the history of previously executed actions, their observed rewards, and visit counts. At each round, it proposes eight candidate actions, from which our method selects one to execute. We have added these experiments to Section 5.3 and Table 2 of the revised manuscript, with implementation details in Appendix F.4.

We monitor empirical near-optimal proposal coverage (see Table below), defined as the fraction of rounds in which at least one candidate is within 0.010.01 of the optimal mean reward. Along Proposed's trajectories, from rounds 11–88 to 129129–256256, coverage increases from 0.0400.040 to 0.1410.141 for Qwen3.5-0.8B and from 0.4750.475 to 0.5650.565 for Qwen3.5-27B. These results illustrate the time-varying coverage behavior accommodated by our theoretical framework, including its extension to history-dependent generators with time-varying coverage in Appendix A.3. Table 2 reports the corresponding simple regret. Our method achieves the lowest mean regret at all five budgets with Qwen3.5-0.8B and at three of five budgets with Qwen3.5-27B, namely T∈32,64,256T\in\\{32,64,256\\}. Model greedy is lowest at T=16T=16 and Uniform at T=128T=128. All four Qwen3.5-27B methods use the independent rerun. Overall, the experiments support the applicability of our framework to real history-dependent LLM generators.

Table 2. Simple regret with history-dependent Qwen3.5 generators on LCBench. Entries report the mean and sample standard deviation across five target-context means, each averaged over ten seeds. Bold marks the lowest mean within each generator and budget. Lower is better.

Qwen3.5-0.8B generator

MethodT=16T=16T=32T=32T=64T=64T=128T=128T=256T=256
Proposed.0435±.0209\mathbf{.0435} \pm .0209.0420±.0208\mathbf{.0420} \pm .0208.0359±.0180\mathbf{.0359} \pm .0180.0387±.0173\mathbf{.0387} \pm .0173.0370±.0163\mathbf{.0370} \pm .0163
Model greedy.0536±.0265.0536 \pm .0265.0599±.0247.0599 \pm .0247.0555±.0299.0555 \pm .0299.0628±.0296.0628 \pm .0296.0540±.0285.0540 \pm .0285
Mean greedy.0689±.0245.0689 \pm .0245.0655±.0260.0655 \pm .0260.0478±.0223.0478 \pm .0223.0504±.0217.0504 \pm .0217.0494±.0217.0494 \pm .0217
Uniform.0649±.0247.0649 \pm .0247.0631±.0269.0631 \pm .0269.0568±.0287.0568 \pm .0287.0654±.0319.0654 \pm .0319.0516±.0239.0516 \pm .0239

Qwen3.5-27B generator

MethodT=16T=16T=32T=32T=64T=64T=128T=128T=256T=256
Proposed.0316±.0162.0316 \pm .0162.0304±.0173\mathbf{.0304} \pm .0173.0331±.0251\mathbf{.0331} \pm .0251.0328±.0240.0328 \pm .0240.0257±.0155\mathbf{.0257} \pm .0155
Model greedy.0315±.0130\mathbf{.0315} \pm .0130.0374±.0230.0374 \pm .0230.0350±.0223.0350 \pm .0223.0334±.0156.0334 \pm .0156.0288±.0162.0288 \pm .0162
Mean greedy.0361±.0134.0361 \pm .0134.0336±.0176.0336 \pm .0176.0385±.0206.0385 \pm .0206.0376±.0188.0376 \pm .0188.0312±.0131.0312 \pm .0131
Uniform.0325±.0175.0325 \pm .0175.0358±.0162.0358 \pm .0162.0353±.0207.0353 \pm .0207.0235±.0109\mathbf{.0235} \pm .0109.0321±.0156.0321 \pm .0156

Table. Empirical near-optimal proposal coverage on LCBench.

Generator1–89–1617–3233–6465–128129–256
Qwen3.5-0.8B.040.060.065.074.108.141
Qwen3.5-27B.475.390.396.434.499.565

Q2: How does the quality, quantity, and relevance of offline observations affect the remaining reward uncertainty and online sample efficiency?

A: We extend the synthetic experiments in Section 5.1 by systematically varying the quantity, relevance, and quality of offline observations in the M=8M=8, β=0.5\beta=0.5 setting. The main findings appear in Section 5.1, with the configuration and results in Appendix F.2 and Tables 5–6. We measure online sample efficiency by T∗(0.01)T^*(0.01), the smallest tested online budget at which our method achieves mean simple regret at most 0.010.01.

Quantity of offline observations. First, we vary the number of offline observations n0n_0 from 00 to 10241024. When the observations are highly informative (γ=10\gamma=10), increasing n0n_0 from 00 to 512512 reduces T∗(0.01)T^*(0.01) from 3232 to 88, a 75%75\% reduction in the required online budget. In contrast, when γ=0\gamma=0, offline observations can distinguish only coarse groups of reward functions, leaving uncertainty within each group unresolved. Consequently, T∗(0.01)T^*(0.01) decreases from 3232 to 2424 with a small number of offline observations, but does not improve further even with 10241024 observations.

Relevance of offline observations. We then vary γ\gamma, which controls how strongly offline observations distinguish reward functions that differ in their optimal target actions. For n0=64n_0=64, increasing γ\gamma from 00 to 55 and 1010 reduces T∗(0.01)T^*(0.01) from 2424 to 1616 and 1212, respectively. These results demonstrate that offline observations are particularly useful when they resolve target-relevant reward uncertainty. For a fixed pair of within-group reward functions over complete 1616-observation source cycles, the evidence scales as n0γ2/σ02n_0\gamma^2/\sigma_0^2, illustrating how quantity and relevance jointly determine the information available for refinement.

Quality of offline observations. We investigate the effect of known offline observation noise by varying its standard deviation σ0∈0.125,0.25,0.5,1\sigma_0\in\\{0.125,0.25,0.5,1\\}. With n0=64n_0=64 and γ=10\gamma=10, T∗(0.01)T^*(0.01) increases from 1212 at σ0=0.25\sigma_0=0.25 to 1616 at σ0=0.5\sigma_0=0.5 and 2424 at σ0=1\sigma_0=1. Thus, noisier offline observations provide less information for resolving reward uncertainty and require more online exploration.

Overall, these experiments show that more informative and reliable offline observations reduce the remaining uncertainty in the plausible function class and improve online sample efficiency.

Table 5. Effects of offline quantity and relevance on online sample efficiency. Entries give the smallest tested budget T∗(0.01)T^*(0.01) achieving mean simple regret at most 0.010.01 for Proposed, with offline noise standard deviation σ0=0.25\sigma_0=0.25. Lower is better.

n0n_0γ=0\gamma=0γ=1\gamma=1γ=5\gamma=5γ=10\gamma=10
032323232
824242424
1624242424
3224242416
6424241612
12824241612
25624241212
5122424128
1024242488

Table 6. Effect of offline observation noise on online sample efficiency. Entries give T∗(0.01)T^*(0.01) for Proposed with known offline noise, n0=64n_0=64, and γ=10\gamma=10. Lower is better.

σ0\sigma_0T∗(0.01)T^*(0.01)
.125.12512
.25.2512
.5.516
1124

Q3: How sensitive is the method to a misspecified the reward-function class, particularly when the true reward function is not represented by any candidate model?

A: We conduct additional oracle diagnostics on LCBench to examine the sensitivity of our method to reward-function class misspecification. We have added the main findings to Section 5.4, with the setup and Table 7 in Appendix F.5. Starting from the original 1616-member Ridge function class F\mathcal F, we augment it with either the archived true mean-reward function f∗f^* or a perturbed approximation fδ=clip(f∗+δz,0,1)f_\delta=\mathrm{clip}(f^*+\delta z,0,1), where zz has independent standard Gaussian entries. The scale δ\delta specifies the perturbation standard deviation before clipping.

As shown in Table 7, adding f∗f^* reduces mean simple regret from 0.028180.02818 to 0.015930.01593. Adding an approximate reward function with δ=0.02\delta=0.02 reduces regret to 0.018970.01897. Regret increases to 0.026140.02614 and 0.031280.03128 as δ\delta grows to 0.050.05 and 0.100.10, respectively. These results show that our method benefits from a reward-function class containing accurate approximations of f∗f^*. The benefit weakens as the approximation becomes less accurate, highlighting the role of reward-function class quality in online performance.

Table 7. Sensitivity to reward-function class misspecification on LCBench through oracle class augmentation. Entries give the mean and sample standard deviation across five target-context means, each averaged over ten seeds and budgets T∈16,32,64,128,256T\in\\{16,32,64,128,256\\}. Lower is better.

Reward-function classSimple regret
Original class F\mathcal F.02818±.0221.02818 \pm .0221
Original class +f∗+f^*.01593±.0109.01593 \pm .0109
Original class +fδ+f_\delta, δ=.02\delta=.02.01897±.0096.01897 \pm .0096
Original class +fδ+f_\delta, δ=.05\delta=.05.02614±.0140.02614 \pm .0140
Original class +fδ+f_\delta, δ=.10\delta=.10.03128±.0195.03128 \pm .0195
Reviewer_56F2OpenReview ↗

Response to Rebuttal

Thank you for the detailed responses and additional experiments. The evaluation with history dependent LLM generators and the analysis of offline data quantity, quality and relevance address my questions well, although the empirical evidence seems to remain limited to a relatively narrow set of settings. The misspecification experiments are also useful but relying on oracle reward information and artificially perturbed functions does not fully establish robustness when the true reward lies outside the assumed function class. Overall, the rebuttal strengthens the paper and addresses most of my concerns, although some questions about practical robustness remain. Therefore, I will maintain my already positive recommendation.

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

This paper studies fixed budget exploration and presents an exploration algorithm to maximize success under these constraints. They use a fixed generator to create candidates and a trained reward models to assess candidate quality and run LCBench. The paper is thorough theory-wise. However, the proposed study is rather simplistic and hard to see how it can extrapolate to practice. Moreover, they did not study agentic generators/judges which seem to be prevalent today.

Critical strengths
  • In-depth theoretical analysis of their judge setup
  • Studies a useful question that does come up in practice
Critical weaknesses
  • Simplistic benchmark with weak baselines. The baseline judge is a very small LLM (that doesn't fit to the provided source contexts), there is no agentic baseline. My main concern with this paper is the lack of baselines and toy-ish sized LLMs used in study and the lack of insight/extension into the agentic systems used today.
Questions for authors

see weakness

1 comment

Thank you for your review. We address your concerns and questions below.


Q: My main concern with this paper is the lack of baselines and toy-ish sized LLMs used in study and the lack of insight/extension into the agentic systems used today.

A: To address these concerns, we have substantially expanded our LCBench experiments, as reported in the revised manuscript (Sections 5.2–5.3, Tables 1–2, and Appendices F.3–F.4).

Stronger LLM baselines. We evaluate standalone LLM judges of different scales, including Qwen3.5-0.8B, 9B, and 27B, GPT-5.6, and Claude Opus 5. Each judge receives 128128 offline observations and source data used to construct our function class. The Qwen judges receive 2,7002{,}700 construction rows, and GPT-5.6 and Claude Opus 5 receive all 10,24010{,}240 rows, as detailed in Appendix F.3. Our original method, Proposed + Ridge, achieves lower mean simple regret than all standalone Qwen judges across all tested budgets T∈16,32,64,128,256T\in\\{16,32,64,128,256\\}, considering both empirical and direct decoding. It also outperforms standalone GPT-5.6 and Claude Opus 5 at T∈32,64,256T\in\\{32,64,256\\}.

LLM-based function classes. Our original implementation uses a function class of 16 ridge reward predictors built on frozen Qwen3.5-0.8B representations. We further instantiate our algorithm with function classes consisting of 16 LLM-based reward predictors constructed using GPT-5.6 or Claude Opus 5. With Claude Opus 5, our method achieves lower mean simple regret than the standalone Claude Opus 5 at every tested budget. For example, at T=128T=128, our method achieves a regret of 0.01490.0149, compared with 0.02960.0296 for the original method and 0.02950.0295 for standalone Claude Opus 5. The GPT-5.6 function class also improves over the original method at T∈32,64,128,256T\in\\{32,64,128,256\\} with the reported reward-function class. Both GPT-5.6 and Claude Opus 5 use high reasoning effort for judging and reward prediction. These results demonstrate that our framework can incorporate and coordinate multiple powerful LLM-based reward predictors. These comparisons appear in Section 5.2 and Table 1, with construction details in Appendix F.3.

LLM action generators. We added experiments replacing the original statistical action generator with history-dependent LLM action generators and track their near-optimal action coverage throughout exploration. From rounds 11–88 to 129129–256256, coverage increases from 0.0400.040 to 0.1410.141 for Qwen3.5-0.8B and from 0.4750.475 to 0.5650.565 for Qwen3.5-27B. Section 5.3 and Table 2 report these experiments, with the setup in Appendix F.4.

Table 1. LCBench simple regret. Entries are the mean and sample standard deviation across five target-context means, each averaged over ten seeds. Emp and Direct denote empirical-mean and direct LLM terminal decoding. Bold marks the lowest mean at each budget. Lower is better.

MethodT=16T=16T=32T=32T=64T=64T=128T=128T=256T=256
Proposed + Ridge.0291±.0234.0291 \pm .0234.0271±.0227.0271 \pm .0227.0264±.0215.0264 \pm .0215.0296±.0231.0296 \pm .0231.0287±.0219.0287 \pm .0219
Proposed + Claude Opus 5.0255±.0186.0255 \pm .0186.0221±.0192\mathbf{.0221 \pm .0192}.0183±.0144\mathbf{.0183 \pm .0144}.0149±.0087\mathbf{.0149 \pm .0087}.0226±.0177\mathbf{.0226 \pm .0177}
Proposed + GPT-5.6.0320±.0235.0320 \pm .0235.0245±.0187.0245 \pm .0187.0197±.0137.0197 \pm .0137.0203±.0168.0203 \pm .0168.0254±.0283.0254 \pm .0283
Model greedy.0370±.0187.0370 \pm .0187.0319±.0125.0319 \pm .0125.0330±.0124.0330 \pm .0124.0363±.0148.0363 \pm .0148.0358±.0174.0358 \pm .0174
Mean greedy.0409±.0242.0409 \pm .0242.0382±.0216.0382 \pm .0216.0366±.0171.0366 \pm .0171.0370±.0172.0370 \pm .0172.0300±.0118.0300 \pm .0118
Uniform.0485±.0287.0485 \pm .0287.0415±.0224.0415 \pm .0224.0398±.0156.0398 \pm .0156.0448±.0179.0448 \pm .0179.0394±.0154.0394 \pm .0154
Qwen3.5-0.8B + Emp.0456±.0230.0456 \pm .0230.0360±.0164.0360 \pm .0164.0403±.0163.0403 \pm .0163.0418±.0199.0418 \pm .0199.0383±.0178.0383 \pm .0178
Qwen3.5-0.8B + Direct.0669±.0371.0669 \pm .0371.0788±.0333.0788 \pm .0333.0710±.0338.0710 \pm .0338.0834±.0320.0834 \pm .0320.0623±.0209.0623 \pm .0209
Qwen3.5-9B + Emp.0408±.0209.0408 \pm .0209.0404±.0189.0404 \pm .0189.0435±.0207.0435 \pm .0207.0388±.0151.0388 \pm .0151.0396±.0179.0396 \pm .0179
Qwen3.5-9B + Direct.0501±.0246.0501 \pm .0246.0362±.0179.0362 \pm .0179.0401±.0239.0401 \pm .0239.0379±.0182.0379 \pm .0182.0331±.0173.0331 \pm .0173
Qwen3.5-27B + Emp.0433±.0231.0433 \pm .0231.0397±.0200.0397 \pm .0200.0412±.0220.0412 \pm .0220.0355±.0157.0355 \pm .0157.0344±.0152.0344 \pm .0152
Qwen3.5-27B + Direct.0370±.0198.0370 \pm .0198.0404±.0197.0404 \pm .0197.0333±.0167.0333 \pm .0167.0322±.0207.0322 \pm .0207.0407±.0190.0407 \pm .0190
GPT-5.6 + Emp.0246±.0113\mathbf{.0246 \pm .0113}.0279±.0148.0279 \pm .0148.0316±.0127.0316 \pm .0127.0296±.0109.0296 \pm .0109.0351±.0145.0351 \pm .0145
Claude Opus 5 + Emp.0265±.0113.0265 \pm .0113.0378±.0185.0378 \pm .0185.0356±.0167.0356 \pm .0167.0295±.0121.0295 \pm .0121.0392±.0197.0392 \pm .0197
Reviewer_bT3vOpenReview ↗
Rating
4(+2)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper considers an agent-based decision making problem and algorithm. Given past history data from different contexts, and also given a new context and finite number of exploratory actions, the algorithm aims to find the best action in the given new context. Agents are used in proposing some promising actions, and the main algorithm revolves around select which of these promising actions to try out. The main contribution of the paper is the theoretical analysis of the algorithm, how far from optimality and with what probability given the number of interactions.

Critical strengths

The paper provides a theoretical analysis for the given algorithm, as well as a theoretic worst case bound about how well any algorithm can perform in this problem. I found these interesting contributions to the broad multi-armed bandit area.

Critical weaknesses

I have some questions about the problem formulation, which I will point out as questions to the authors below. Overall, my judgment is that these formulations make the scope of the problem formulation limited.

The experimental data are relatively limited. I acknowledge that the paper is primarily theoretical, but I find that the experimental data do not show how useful the algorithm is, how broadly it can be applied in different settings/contexts, and how well it achieves on some task that is practically useful and challenging.

Questions for authors

The context set X. Is this a finite set? It consists of past contexts and the new target one. Then all the theoretical results depend on the specific new target. I would have expected a result like, now matter what is the new context, the probability of optimal action is etc. Or alternatively, depending on how similar is the target context to the previous ones, you get better answers.

The action generator provides as output action recommendations that are independent among themselves or no? or just a random tuple? Does this matter?

Even though the action generator is assumed a black box, Assumption 2.2. is a strong assumption in my eyes. It is also something that would be hard to verify. In the numerical results, in the synthetic data, if I understand correctly, it was enforced by design, but was this assumption verified in the other case study?

Also, the action generator could take a longer history, and one could model that in that case it gives better candidate actions?

This assumption also depends on the specific context set X or does it hold for any set of contexts? If X is fixed throughout the paper, then things shouldn't depend on it?

Overall, I would have expected a discussion about the combinatorial aspects. For example equation (2) is the sum over all functions g. Equation (5) is over all actions and all functions f. Aren't these of a very high combinatorial complexity for large scale problems - the kind of problems you would try LLM agents? Could you also please discuss this in the numerical results, how large these numbers were?

Theorem 4.1 says that there is a specific function class and specific generator that make this worst case. Can some intuition be provided as to whether this class and generator are likely to be encountered or are some very strange corner cases?

5 comments

Thank you for your review. We address your concerns and questions below.


W: Insufficient experiments.

A: We have substantially expanded the experimental evaluation in the revised manuscript. The added results appear in Sections 5.1–5.4 and Appendices F.2–F.5, covering offline-data sensitivity, stronger LLM judges and reward-function classes, history-dependent LLM action generators, and reward-class misspecification.


Q1: Is context set X\mathcal{X} finite? It consists of past contexts and the new target one. Then all the theoretical results depend on the specific new target. I would have expected a result like, now matter what is the new context, the probability of optimal action is etc. Or alternatively, depending on how similar is the target context to the previous ones, you get better answers.

A: In our paper, X=Xoff∪x0\mathcal X=\mathcal X^{\mathrm{off}}\cup\\{x_0\\} is finite, since Xoff\mathcal X^{\mathrm{off}} consists of the finitely many contexts appearing in the offline dataset. To address this question, we have added Theorem B.3 in Appendix B.3 of the revised manuscript, extending our guarantee to a possibly infinite target context space Xtarget\mathcal X^{\mathrm{target}} without changing the proposed algorithm. The newly added theorem establishes a common success bound for every queried x∈Xtargetx\in\mathcal X^{\mathrm{target}}, using TT online rounds per target. It uses the residual dimension sup⁡x∈XtargetdV0(x,ϵ/2)\sup_{x\in\mathcal X^{\mathrm{target}}}d_{\mathcal V_0}(x,\epsilon/2) the common coverage lower bound p=inf⁡x∈Xtarget(1−β(ϵ/2,x))>0p=\inf_{x\in\mathcal X^{\mathrm{target}}}(1-\beta(\epsilon/2,x))>0. In particular, the guarantee does not depend on the cardinality of Xtarget\mathcal X^{\mathrm{target}}.

Our existing analysis also captures how the relevance of offline contexts to the target affects the success probability. Specifically, Theorem 3.1 (Eq. (6)) provides a data-dependent guarantee in terms of the residual eluder dimension dV0(ϵ/2)d_{\mathcal V_0}(\epsilon/2), where V0\mathcal V_0 is the function class remaining after offline refinement. When offline observations distinguish reward functions that make different predictions at the target context, this dimension can decrease, leading to a stronger success guarantee for the same online budget. We also examine this effect in the added offline-data experiments in Section 5.1 and Appendix F.2.


Q2: The action generator provides as output action recommendations that are independent among themselves or no? or just a random tuple? Does this matter?

A: We do not assume independence among the generated actions. As defined in Section 2, the generator samples an entire candidate tuple from an arbitrary joint distribution M(⋅∣x0,Ht−1)\mathcal M(\cdot \mid x_0, \mathcal H_{t-1}), allowing arbitrary correlations among candidates and history-dependent generation across rounds. Our theoretical guarantees apply to this joint-generation model.


Q3: Even though the action generator is assumed a black box, Assumption 2.2. is a strong assumption in my eyes. It is also something that would be hard to verify. In the numerical results, in the synthetic data, if I understand correctly, it was enforced by design, but was this assumption verified in the other case study?

A: In real-world agentic systems, action generators such as LLMs are often complex, history-dependent, and opaque, making their output distributions difficult to characterize explicitly. This motivates Assumption 2.2, which characterizes generator quality through a general, typically unknown function β\beta that upper-bounds the conditional probability of failing to propose any near-optimal action. This function can be arbitrarily complex, allowing our framework to accommodate diverse black-box generators without restrictions on their generation mechanisms. Importantly, we do not assume high-quality generation. A poor generator may frequently miss near-optimal actions, as captured by β\beta close to one. Our guarantees explicitly quantify the resulting impact on success probability, while the proposed algorithm does not require knowledge of β\beta.

Q4: The action generator could take a longer history, and one could model that in that case it gives better candidate actions?

A: Our framework already allows the generator to use the entire interaction history Ht−1\mathcal H_{t-1}, including previously generated candidates, executed actions, and observed rewards, to improve its recommendations. Moreover, Appendix A.3 explicitly accommodates such improvements through time-varying coverage βt(r,x0)\beta_t(r,x_0). Better coverage leads to a stronger success guarantee, with effective coverage ∑t=1T(1−βt(r,x0))\sum_{t=1}^T (1-\beta_t(r,x_0)) replacing T(1−β(r,x0))T(1-\beta(r,x_0)), without any modification to our proposed judge. We have added history-dependent Qwen3.5 action generators in Section 5.3.

To examine this behavior empirically, we added LCBench experiments with history-dependent LLM action generators. We measure empirical coverage as the fraction of rounds containing a candidate within 0.010.01 of the optimal mean reward. Along Proposed's trajectories, this coverage increases from 0.0400.040 to 0.1410.141 for Qwen3.5-0.8B and from 0.4750.475 to 0.5650.565 for Qwen3.5-27B between rounds 11–88 and 129129–256256. With these history-dependent proposals, our method achieves the lowest mean simple regret among the four selectors at all five budgets with Qwen3.5-0.8B and three of five with Qwen3.5-27B. These results appear in Section 5.3 and Table 2, with details in Appendix F.4.


Q5: Assumption 2.2 also depends on the specific context set X\mathcal{X} or does it hold for any set of contexts? If X\mathcal{X} is fixed throughout the paper, then things shouldn't depend on it?

A: Thank you for pointing this out. Since our setting considers a fixed target context x0x_0, Assumption 2.2 only requires coverage at x0x_0, rather than over the entire context set X\mathcal X. Thus, β(⋅,x0)\beta(\cdot,x_0) can equivalently be viewed as a function on [0,1][0,1], with x0x_0 implicitly fixed. Accordingly, our success guarantee depends on β(ϵ/2,x0)\beta(\epsilon/2,x_0), which characterizes the generator's coverage at the target context. We have clarified this notation in Assumption 2.2 of Section 2 in the revised manuscript. Moreover, Appendix B.3 extends our analysis to a possibly infinite target context space.


Q6: Overall, I would have expected a discussion about the combinatorial aspects. For example equation (2) is the sum over all functions g. Equation (5) is over all actions and all functions f. Aren't these of a very high combinatorial complexity for large scale problems - the kind of problems you would try LLM agents? Could you also please discuss this in the numerical results, how large these numbers were?

A: We have already discussed the per-round computational cost in Appendix E, which is O(MN+M2)O(MN+M^2), where M=∣F∣M=|\mathcal F| is the number of reward models and NN is the number of generated candidate actions. Importantly, our algorithm never enumerates the entire action space, which may be infinite. In practical agentic systems, F\mathcal F is naturally kept relatively small, since its members may be distinct LLM-based or other neural network reward models that are costly to train and evaluate. Thus, the quadratic dependence on MM is manageable in our intended setting. We have also reported the function-class sizes in our experiments, with M∈4,8,16M\in\\{4,8,16\\} in the synthetic setting and M=16M=16 in LCBench.


Q7: Theorem 4.1 says that there is a specific function class and specific generator that make this worst case. Can some intuition be provided as to whether this class and generator are likely to be encountered or are some very strange corner cases?

A: Our lower-bound construction captures two natural challenges in agentic systems. Offline observations do not necessarily provide useful information for distinguishing reward models that favor different actions at a new target context, while the generator may not always propose useful candidates. Specifically, we construct a function class whose members make identical predictions on all offline observations but favor different optimal actions at the target context. The generator independently proposes all informative actions with probability 1−β1-\beta and otherwise provides only uninformative candidates, satisfying the coverage requirement of Assumption 2.2 with equality. Thus, the lower bound captures these fundamental statistical challenges even with a simple, history-independent generator, without relying on adversarial or sophisticated generation mechanisms.

Thank you, I really think that checking the quality of the action generator in practice is important. Like something you would do before you start using them in your system. I strongly encourage the authors to add a numerical experiment of this, maybe this means estimating beta experimentally or something similar

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.