- 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
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 , 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 , the smallest tested online budget at which our method achieves mean simple regret at most .
Quantity of offline observations. First, we vary the number of offline observations from to . When the observations are highly informative (), increasing from to reduces from to , a reduction in the required online budget. In contrast, when , offline observations can distinguish only coarse groups of reward functions, leaving uncertainty within each group unresolved. Consequently, decreases from to with a small number of offline observations, but does not improve further even with observations.
Relevance of offline observations. We then vary , which controls how strongly offline observations distinguish reward functions that differ in their optimal target actions. For , increasing from to and reduces from to and , 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 -observation source cycles, the evidence scales as , 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 . With and , increases from at to at and at . 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 achieving mean simple regret at most for Proposed, with offline noise standard deviation . Lower is better.
| 0 | 32 | 32 | 32 | 32 |
| 8 | 24 | 24 | 24 | 24 |
| 16 | 24 | 24 | 24 | 24 |
| 32 | 24 | 24 | 24 | 16 |
| 64 | 24 | 24 | 16 | 12 |
| 128 | 24 | 24 | 16 | 12 |
| 256 | 24 | 24 | 12 | 12 |
| 512 | 24 | 24 | 12 | 8 |
| 1024 | 24 | 24 | 8 | 8 |
Table 6. Effect of offline observation noise on online sample efficiency. Entries give for Proposed with known offline noise, , and . Lower is better.
| 12 | |
| 12 | |
| 16 | |
| 24 |
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 -member Ridge function class , we augment it with either the archived true mean-reward function or a perturbed approximation , where has independent standard Gaussian entries. The scale specifies the perturbation standard deviation before clipping.
As shown in Table 7, adding reduces mean simple regret from to . Adding an approximate reward function with reduces regret to . Regret increases to and as grows to and , respectively. These results show that our method benefits from a reward-function class containing accurate approximations of . 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 . Lower is better.
| Reward-function class | Simple regret |
|---|---|
| Original class | |
| Original class | |
| Original class , | |
| Original class , | |
| Original class , |
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.
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.01 of the optimal mean reward. Along Proposed's trajectories, from rounds 1–8 to 129–256, coverage increases from 0.040 to 0.141 for Qwen3.5-0.8B and from 0.475 to 0.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,256. Model greedy is lowest at T=16 and Uniform at T=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
Qwen3.5-27B generator
Table. Empirical near-optimal proposal coverage on LCBench.