Fixed-Budget Agentic Pure Exploration with Judges

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.