Paper deep dive
In-Context Learning for Pure Exploration in Continuous Spaces
Alessio Russo, Yin-Ching Lee, Ryan Welch, Aldo Pacchiano
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 89%
Last extracted: 7/20/2026, 11:02:44 PM
Summary
The paper introduces Continuous In-Context Pure Exploration (C-ICPE-TS), an algorithm that meta-trains deep neural policies to solve pure exploration problems in continuous hypothesis spaces. Unlike traditional methods requiring explicit information models, C-ICPE-TS maps observation histories to continuous query actions and predicted hypotheses, enabling transferable sequential testing strategies. The approach is validated on benchmarks including continuous best-arm identification, region localization, and function minimizer identification, demonstrating the ability to identify optimal actions with few queries in noisy, continuous environments.
Entities (7)
Relation Signals (5)
C-ICPE-TS → solves → Pure Exploration
confidence 95% · In this work, we study pure exploration in such continuous spaces and introduce Continuous In-Context Pure Exploration for this regime.
C-ICPE-TS → uses → In-Context Learning
confidence 92% · We introduce C-ICPE-TS, an algorithm that meta-trains deep neural policies... learning transferable sequential testing strategies directly from data.
C-ICPE-TS → validateson → Ackley function
confidence 88% · We validate C-ICPE-TS across a range of benchmarks... C-ICPE-TS is able to identify the global maxima... of the noisy Ackley function
Chernoff → studied → Pure Exploration
confidence 85% · This problem, originally studied by Chernoff in 1959
Russo et al. → proposed → In-Context Pure Exploration
confidence 80% · Recently, Russo et al. (2025b) proposed In-Context Pure Exploration (ICPE)
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:In active sequential testing, also termed pure exploration, a learner is tasked with the goal to adaptively acquire information so as to identify an unknown ground-truth hypothesis with as few queries as possible. This problem, originally studied by Chernoff in 1959, has several applications: classical formulations include Best-Arm Identification (BAI) in bandits, where actions index hypotheses, and generalized search problems, where strategically chosen queries reveal partial information about a hidden label. In many modern settings, however, the hypothesis space is continuous and naturally coincides with the query/action space: for example, identifying an optimal action in a continuous-armed bandit, localizing an $\epsilon$-ball contained in a target region, or estimating the minimizer of an unknown function from a sequence of observations. In this work, we study pure exploration in such continuous spaces and introduce Continuous In-Context Pure Exploration for this regime. We introduce C-ICPE-TS, an algorithm that meta-trains deep neural policies to map observation histories to (i) the next continuous query action and (ii) a predicted hypothesis, thereby learning transferable sequential testing strategies directly from data. At inference time, C-ICPE-TS actively gathers evidence on previously unseen tasks and infers the true hypothesis without parameter updates or explicit hand-crafted information models. We validate C-ICPE-TS across a range of benchmarks, spanning continuous best-arm identification, region localization, and function minimizer identification.
Tags
Links
- Source: https://arxiv.org/abs/2602.17976v1
- Canonical: https://arxiv.org/abs/2602.17976v1
Trouble viewing inline? Open PDF directly →
Full Text
114,110 characters extracted from source content.
Expand or collapse full text
In-Context Learning for Pure Exploration in Continuous Spaces Alessio Russo Boston University arusso2@bu.edu &Yin-Ching Lee11footnotemark: 1 Boston University leewill@bu.edu &Ryan Welch Stanford University rcwelch@stanford.edu &Aldo Pacchiano Boston University Broad Institute of MIT and Harvard apacchian@bu.edu Equal contribution. Abstract In active sequential testing, also termed pure exploration, a learner is tasked with the goal to adaptively acquire information so as to identify an unknown ground-truth hypothesis with as few queries as possible. This problem, originally studied by Chernoff in 1959, has several applications: classical formulations include Best-Arm Identification (BAI) in bandits, where actions index hypotheses, and generalized search problems, where strategically chosen queries reveal partial information about a hidden label. In many modern settings, however, the hypothesis space is continuous and naturally coincides with the query/action space: for example, identifying an optimal action in a continuous-armed bandit, localizing an ϵε-ball contained in a target region, or estimating the minimizer of an unknown function from a sequence of observations. In this work, we study pure exploration in such continuous spaces and introduce Continuous In-Context Pure Exploration for this regime. We introduce C-ICPE-TS, an algorithm that meta-trains deep neural policies to map observation histories to (i) the next continuous query action and (i) a predicted hypothesis, thereby learning transferable sequential testing strategies directly from data. At inference time, C-ICPE-TS actively gathers evidence on previously unseen tasks and infers the true hypothesis without parameter updates or explicit hand-crafted information models. We validate C-ICPE-TS across a range of benchmarks, spanning continuous best-arm identification, region localization, and function minimizer identification. Keywords Active Regression ⋅· Pure Exploration ⋅· Experimental Design ⋅· In-Context Learning ⋅· Best Arm Identification 1 Introduction Several learning problems are interactive or sequential, and revolve around the problem of identifying some underlying hypothesis. Consider a scientist investigating a phenomenon: sequentially, the scientist selects an intervention (or an “action”), observes noisy evidence whose distribution depends on that intervention, and decides whether to stop once the accumulated evidence supports a reliable conclusion. Chernoff (1959) studied this controlled-sensing perspective early on, asking how to choose interventions as to guarantee small decision error while using as few observations as possible. In these settings, where the observed data depends on the chosen intervention, the learner must adaptively select queries that discriminate between hypotheses under scarce and noisy data. Over the last decades, this objective has been formalized under closely related lenses, including active sequential hypothesis testing (ASHT) (Naghshvar and Javidi, 2013) (also known as Pure Exploration (Audibert and Bubeck, 2010; Degenne et al., 2019)) and Bayesian experimental design Rainforth et al. (2024). While both study adaptive intervention choice, they typically optimize different criteria: Bayesian design often selects a fixed budget of interventions to maximize an expected utility (commonly information gain). In contrast, an important regime for ASHT is the fixed-confidence one, where the learner sequentially selects experiments and stops only once it can return a decision/estimate with error probability at most δ. This regime is well understood in canonical settings such as best-arm identification in stochastic multi-armed bandit models (Garivier and Kaufmann, 2016) and best-policy identification in Markov Decision Processes (MDPs) (Puterman, 2014). In these settings the learner chooses queries (e.g., arms) and outputs an object of interest, often a best action/policy, and the theoretical guarantees have been studied in a range of settings (Degenne et al., 2019; Poiani et al., 2025b; Al Marjani et al., 2021; Russo et al., 2025a). Figure 1: C-ICPE-TS is able to identify the global maxima (with ϵε-accuracy and 1−δ1-δ confidence) of the noisy Ackley function (with random parameters and observation noise), while trying to use the least number of data-points. Our focus in this work is Pure Exploration in the fixed-confidence regime when the hypothesis space is continuous, and where the goal is to estimate a latent hypothesis about an action (e.g., identify an action that is approximately optimal). This viewpoint encompasses a range of continuous pure-exploration tasks, including ε -best arm identification with a continuous action space, the problem of finding (approximately) the minimizer of an unknown function, and continuous analogues of binary search. In this setting, the task resembles adaptive localization: the learner must probe the environment to identify a hypothesis (e.g., an ϵε-optimal action) with 1−δ1-δ confidence. This is challenging because nearby hypotheses can induce highly overlapping observations, and noise can make it difficult to reliably separate parameters at fine resolution (Garivier and Kaufmann, 2021; Russo and Pacchiano, 2025). Common techniques for finite hypothesis classes do not typically work in a continuous hypothesis space, and separating ϵε-close hypotheses may require sample sizes that depend sharply on the local information geometry. Consequently, deriving statistically sound stopping rules and exploration strategies is a non-trivial task. Recently, Russo et al. (2025b) proposed In-Context Pure Exploration (ICPE), a method for training sequential neural architecture for solving active testing problems with finite hypothesis/action settings, thereby bypassing explicit hand-crafted information models at inference time. Concretely, ICPE learns a policy that maps interaction histories to the next query, enabling adaptive acquisition without explicit hand-designed confidence bounds or likelihood models. Yet, extending this paradigm to continuous hypotheses raises nontrivial questions: what is a correct reward formulation for continuous hypotheses, and how do we design a practical stopping rule? In this work we take a step forward, and introduce C-ICPE-TS, a continuous analogue of ICPE that learns transferable fixed-confidence-style identification strategies directly from interaction data in continuous spaces. We empirically validate C-ICPE-TS on a suite of continuous pure-exploration benchmarks, covering both deterministic and stochastic observation models. Our experiments span (i) continuous-armed ε -best arm identification, (i) region localization tasks where the learner must identify an ε -ball contained in a target set, and (i) gradient-free function minimizer identification from sequential noisy evaluations. Figure 1 illustrates that our method can reliably localize a global optimum of a noisy, multimodal landscape (Ackley function) with few evaluations. We believe that this type of (ϵ,δ)(ε,δ)-PAC exploration is broadly aligned with similar optimization problems encountered in scientific settings, such as materials discovery and other experimental sciences (Liu et al., 2017), where each experiment is costly and observations are noisy. Across these settings, we study how well C-ICPE-TS transfers across tasks, and how its learned querying and stopping behavior compares to other baselines. 2 Problem Setting In the active sequential testing problem the learner acts sequentially in an environment M: starting with an initial observation Y1Y_1, in each round t=1,2,…t=1,2,… the learner chooses an action AtA_t (i.e., an experiment) and observes an outcome Yt+1Y_t+1. The goal of the learner is to collect a sequence of data (history) Ht≔(Y1,A1,Y2,…,At−1,Yt)H_t (Y_1,A_1,Y_2,…,A_t-1,Y_t) that is sufficiently informative to output a high-quality decision. In our formulation, decision quality is captured by an environment-dependent loss function Lθ:→[0,∞)L_θ:X→[0,∞) (defined below): at stopping, the learner recommends x^∈ x and we require x x to be ϵε-optimal, i.e. Lθ(x^)≤ϵL_θ( x)≤ε, with high probability. In this work, we focus on identification problems where the learner’s final recommendation is an action or a decision directly tied to the action space, e.g., an approximately optimal arm, an approximate minimizer of an unknown function, or an ε -accurate localization of a target region. Accordingly, we view the target as an environment-specific ground-truth hypothesis x⋆x and aim to output an ε -accurate hypothesis x x with high probability. Notation. We use uppercase letters for random variables (e.g., At,YtA_t,Y_t) and lowercase letters for their realizations (e.g., at,yta_t,y_t). We write Ht≔(Y1,A1,Y2,…,At−1,Yt)H_t (Y_1,A_1,Y_2,…,A_t-1,Y_t) for the random history and hth_t for a realized history (an element of its range). Finally, X denotes the hypothesis (decision) space and x∈x denotes a generic hypothesis. In this setup, we focus on the fixed confidence setting: we want to minimize the number of queries while returning a recommendation that is correct with high probability. Concretely, the learner must (i) choose queries AtA_t based on the history hth_t, and (i) decide when to stop and output a final recommendation x x. Relative to Russo et al. (2025b), which focuses on finite spaces, we study continuous spaces and require (ϵ,δ)(ε,δ)-PAC guarantees: with probability at least 1−δ1-δ, the returned hypothesis is ϵε-optimal. We now introduce the notation and assumptions of the model, and then define the (ϵ,δ)(ε,δ)-identification problem. Model, Hypotheses and Risk Function. Let Θ⊂ℝd ^d be a compact parameter space. We consider environments MθM_θ indexed by θ∈Θθ∈ . Each environment has a compact action space ⊂ℝmA ^m and a compact observation space ⊂ℝnY ^n, an initial observation distribution ρθ∈Δ() _θ∈ (Y), and (possibly history-dependent) observation kernels Pθ=(Pθ,t)t≥1P_θ=(P_θ,t)_t≥ 1 such that Yt+1∼Pθ,t(⋅|ht,at)Y_t+1 P_θ,t(·|h_t,a_t). A hypothesis x∈x is any object the learner may recommend. We assume X is compact; in the continuous pure-exploration problems we study, we take the hypothesis space to coincide with the action/decision space. For each θ∈Θθ∈ , the environment induces a risk function Lθ:→[0,∞)L_θ:X→[0,∞) that evaluates the quality of each hypothesis. In many examples we can also define an (possibly set-valued) optimal decision ⋆(θ)X (θ) (e.g. global minimizers, best arms, or a target point); however, throughout the paper ϵε-optimality is defined solely via LθL_θ. In our running examples, Lθ(x)L_θ(x) measures (i) distance in action space to the set of global minimizers, or (i) suboptimality gap relative to the best action. We assume (w.l.o.g.) that infx∈Lθ(x)=0 _x L_θ(x)=0. Therefore, we say that x is ϵε-optimal in MθM_θ if Lθ(x)≤ϵL_θ(x)≤ε. The corresponding ϵε-optimal set of hypotheses is ϵ(θ)≔x∈:Lθ(x)≤ϵ.X_ε(θ) \x :L_θ(x)≤ε\. Lastly, we place a prior ν on Θ and write θ∼νθ ν; we let M≔MθM M_θ denote the corresponding (random) environment. Example 2.1. To fix the ideas, consider the following examples: 1. (Function minimization) Consider the problem of minimizing a parametrized function fθf_θ. Let =X=A be the decision space, and let fθ:→ℝf_θ:X be the objective function encoded by θ. Let ⋆(θ)≔argminx∈fθ(x)X (θ) _x f_θ(x) be the (possibly non-unique) set of global minimizers. We set the loss to be distance-to-optimal-set, Lθ(x)≔infx⋆∈⋆(θ)‖x−x⋆‖2, so that ϵ(θ)=x∈:infx⋆∈⋆(θ)‖x−x⋆‖2≤ϵL_θ(x) _x (θ)\|x-x \|_2,\; so that \;X_ε(θ)= \x : _x (θ)\|x-x \|_2≤ε \ is the set of points that are ϵε-close (in decision space) to a global minimizer. 2. (ϵε-Best-Arm Identification) Consider best-arm identification in linear bandits. Let =m−1A=S^m-1 be the set of arms on the unit sphere, and let =X=A. For linear bandits, the mean reward of arm x∈x is μθ(x)=θ⊤x _θ(x)=θ x. Let x⋆(θ)∈argmaxx∈θ⊤x (θ)∈ _x θ x and μ⋆(θ)≔θ⊤x⋆(θ)μ (θ) θ x (θ). Define the gap-based loss Lθ(x)≔θ⊤(x⋆(θ)−x)L_θ(x) θ (x (θ)-x). Then the set of ϵε-optimal arms is: ϵ(θ)=x∈:θ⊤(x⋆(θ)−x)≤ϵ.X_ε(θ)= \x :θ (x (θ)-x)≤ε \. 3. (Noisy binary search in a continuum) Let =[0,1]mA=[0,1]^m and let =X=A. The environment is specified by an unknown target point x⋆∈x . When the learner queries x∈x , it observes a noisy sign vector Y∈−1,+1mY∈\-1,+1\^m defined coordinate-wise as follows: for each dimension j∈1,…,mj∈\1,…,m\ the observtion is given by Yj=ξjsign(xj−xj⋆),Y_j= _j\,sign(x_j-x _j), where (ξj)j=1m( _j)_j=1^m are i.i.d. Rademacher noise variables with ℙ(ξj=−1)=pP( _j=-1)=p (i.i.d. across dimensions and across rounds). A natural choice of loss is distance to the target, Lθ(x)≔‖x−x⋆‖2,L_θ(x) \|x-x \|_2, so that ϵ(θ)X_ε(θ) is the set of points within Euclidean distance ϵε of x⋆x . Problem Setting. We work in the fixed-confidence ((ϵ,δ)(ε,δ)-PAC) regime. A learner is defined by the triplet (π,I,τ)(π,I,τ): a sampling policy π=(πt)t≥1π=( _t)_t≥ 1 such that At=πt(Ht)A_t= _t(H_t); a stopping time τ with respect to ℱt=σ(Ht)F_t=σ(H_t), defining when to stop the data acquisition process; an inference rule I=(It)t≥1I=(I_t)_t≥ 1 such that x^τ=Iτ(Hτ) x_τ=I_τ(H_τ). The goal of the learner is to adaptively choose queries A1,A2,…A_1,A_2,… and a stopping time τ, so that the returned x^τ x_τ is ϵε-optimal, i.e. x^τ∈ϵ(θ) x_τ _ε(θ), with high probability. Hence, for a given pair ϵ>0,δ∈(0,1/2)ε>0,δ∈(0,1/2), we seek to minimize the (expected) number of queries while ensuring δ-correctness: formally, we solve infτ,π,Iθ∼νπ[τ]s.t.ℙθ∼νπ(x^τ∈ϵ(θ))≥ 1−δ,θ∼νπ[τ]<∞. _τ,π,I\ E_θ ν^π [τ ] .t. _θ ν^π ( x_τ _ε(θ) )≥\ 1-δ, _θ ν^π[τ]<∞. (1) In our setting, ν represents a distribution over environments (tasks) used for training and evaluation: each episode samples θ∼νθ ν and generates an interaction trajectory under (π,I,τ)(π,I,τ). We therefore optimize (1) in an average-case sense over tasks, aiming for policies and stopping rules that transfer across environments drawn from the same family. Practically, we parameterize π and I by neural networks and train them from simulated interaction data; the stopping rule τ is implemented as a learned halting mechanism that trades off additional queries against confidence in the current recommendation. 3 Theoretical Background In this section we extend the technical results in (Russo et al., 2025b) to the continuous case. These results serve as a basis for the algorithm design, and motivate some practical choices. As for ICPE, we show that learning an optimal inference rule I amounts to computing a posterior distribution of ϵ(θ) X_ε(θ). Secondly, the policy π can be learned using RL with an appropriate reward function that naturally emerges from the problem formulation. Optimal inference and the posterior success function. In the fixed-confidence setting with a continuous decision set X, the relevant posterior object is not the point-mass ℙ(x⋆=x|Ht)P(x =x|H_t) (which is ill-suited to continuous X), but the posterior success probability. For a candidate recommendation x∈x , define the posterior success probability qt(h,x)≔ℙ(Lθ(x)≤ϵ|Ht=h),rt(h)≔maxx∈qt(h,x).q_t(h,x) (L_θ(x)≤ε |H_t=h ), r_t(h) _x q_t(h,x). Intuitively, qt(h,x)q_t(h,x) is the posterior probability that x is ϵε-optimal under the unknown task parameter θ, and rt(h)r_t(h) is the best such probability achievable from history h. Under mild regularity (continuity of x↦Lθ(x)x L_θ(x) on compact X), the maximum in rt(h)r_t(h) is attained. Moreover, Proposition A.4 shows that an optimal inference rule at time t is simply It(h)∈argmaxx∈qt(h,x),(ties broken by a fixed convention)I_t(h)∈ _x q_t(h,x), (ties broken by a fixed convention) i.e., recommend the action with the largest posterior chance of being ϵε-optimal. Dual formulation, stopping and optimality. We study the fixed-confidence problem in Equation 1 through its Lagrangian dual, following the ASHT literature (Naghshvar and Javidi, 2013) and (Russo et al., 2025b). Concretely, introducing a multiplier λ≥0λ≥ 0 for the correctness constraint yields the dual objective Vλ(π,I,τ)≔−θ∼νπ[τ]+λ(ℙθ∼νπ(Iτ(Hτ)∈ϵ(θ))−1+δ),infλ≥0supπ,I,τVλ(π,I,τ),V_λ(π,I,τ) -E_θ ν^π[τ]+λ (P_θ ν^π (I_τ(H_τ) _ε(θ) )-1+δ ), _λ≥ 0\ _π,I,τV_λ(π,I,τ), (2) where the supremum is over admissible policies π, measurable inference rules I, and stopping times τ that are finite in expectation. This formulation makes explicit that the learner must jointly optimize what to sample (π), when to stop (τ), and what to recommend at stopping (I). To solve the problem, we make a few observations. First, for a fixed policy and stopping rule, maximizing over the inference rule I at time τ yields supIℙθ∼νπ(Iτ(Hτ)∈ϵ(θ))=θ∼νπ[rτ(Hτ)],rt(h)≔maxx∈qt(h,x), _IP_θ ν^π (I_τ(H_τ) _ε(θ) )=E_θ ν^π [r_τ(H_τ) ], r_t(h) _x q_t(h,x), so the inner maximization in Equation 2 is equivalent to maximizing −π[τ]+λπ[rτ(Hτ)−1+δ]-E^π[τ]+ ^π [r_τ(H_τ)-1+δ ] (this follows directly from Proposition A.4). Secondly, a key simplification is that any admissible stopping time can be represented by introducing an explicit absorbing action astopa_ stop: the policy continues with actions in A until it selects astopa_ stop, at which point it stops and outputs an inference rule (see Lemma A.7 and Section A.3). Thus, without loss of generality, we work on the augmented action space and write τ¯=inft≥1:At=astop τ= \t≥ 1:A_t=a_ stop\, dropping τ from the optimization variables. With these two key simplifications, the Lagrangian dual in Equation 2 becomes an optimal-stopping control problem: each continuation step incurs unit cost, while stopping at history h yields a terminal reward proportional to rτ¯(h)r_ τ(h). Therefore, formally, for t≥1t≥ 1 and λ≥0λ≥ 0, we can convert the problem into a reward-to-collect formulation. Define the optimal value from a history h∈ℋth _t as Vt⋆(h;λ)≔supπ¯θ∼νπ¯[λrτ¯(Hτ¯)−(τ¯−t)|Ht=h].V_t (h;λ) _ π\ E_θ ν π [λ\,r_ τ(H_ τ)-( τ-t)\ |\ H_t=h ]. (3) Define the associated optimal Q-functions Qt,stop⋆(h;λ)≔λrt(h),Qt,cont⋆(h,a;λ)≔−1+[Vt+1⋆(Ht+1;λ)|Ht=h,At=a],Q_t, stop (h;λ) λ r_t(h), Q_t, cont (h,a;λ) -1+E [V_t+1 (H_t+1;λ)|H_t=h,A_t=a ], where the expectation is taken under the predictive posterior P¯t(⋅|h,a) P_t(·|h,a) induced by the Bayesian model. Then the optimal value satisfies the stop/continue Bellman equation Vt⋆(h;λ)=maxQt,stop⋆(h;λ),supa∈Qt,cont⋆(h,a;λ).V_t (h;λ)= \Q_t, stop (h;λ),\ _a Q_t, cont (h,a;λ) \. (4) Concretely, for a fixed multiplier λ≥0λ≥ 0, the inner maximization in the dual can be viewed as maximizing expected return with reward rt,λ(Ht,a)=− 1a≠astop+λ 1a=astoprt(Ht).r_t,λ(H_t,a)=-\,1\a≠ a_ stop\+λ\,1\a=a_ stop\\,r_t(H_t). This motivates learning the sampling policy via RL with a cost for continuation and terminal reward proportional to rt(Ht)r_t(H_t) at stopping: the policy learns to trade off sample efficiency (penalized by a cost per step) against confidence at stopping (rewarded by λrt(Ht)λ r_t(H_t)). In terms of technical novelty, this result resembles the approach in (Russo et al., 2025b). However, in contrast to their finite setting, we require some additional care in the continuous case. In fact, it is not immediately clear that the supremum over the actions in Equation 4 can be attained: the term Qt,cont⋆Q_t, cont estimates the future confidence at the stopping τ, and thus depends on the optimal future stopping decision. Therefore, we need a particular continuity argument that ensures Qt,cont⋆Q_t, cont is upper semicontinuous (hence attains its supremum on a compact action set). Our technical analysis (see Lemma A.10) shows that, under suitable assumptions111We require that for all θ the mapping a↦Pθ,t(⋅|ht,a)a P_θ,t(·|h_t,a) is weakly continuous in the action a, see also Appendix A in the appendix., such property is satisfied, and therefore the decomposition in Equation 17 is valid (see Proposition A.11). For all technical details we also refer the reader to Section A.3. 4 Deep Learning and Thompson Sampling for Exploration in Continuous Space This section describes a simple instantiation of Thompson Sampling (Thompson, 1933) for continuous problems where the hypothesis/decision space coincides with the action space. The key design choice is to avoid learning a separate actor: we maintain an explicit parametric posterior over a true hypothesis and use it directly for Thompson-style exploration. A critic is learned only to decide when to stop. Training protocol. Our method uses meta-training to train the models. In brief, meta-training iterates over tasks θ∼νθ ν, collects trajectories using Thompson sampling , stores transitions (and task labels for inference) in a replay buffer, and performs off-policy updates: (i) a likelihood update of the posterior parameters (inference), and (i) a DQN-like update of the critic. At test time, the policy samples actions from the learned posterior, and stops whenever the Q-value of stopping is larger than the value of continuing. We now explain the training procedure and the models. Posterior distribution, recommendation and exploration. Our method models a posterior over an optimal decision x⋆(θ)x (θ) and is trained via an NLL loss that requires a per-task target. Accordingly, we assume access (in simulation or via an oracle) to a point x⋆(θ)x (θ) satisfying Lθ(x⋆(θ))=0L_θ(x (θ))=0 and B(x⋆(θ),ρ)⊆ϵ(θ)B(x (θ),ρ) _ε(θ) for some ρ 222Formally, we assume that near x⋆(θ)x (θ) the loss is controlled by Euclidean distance: there exists a nondecreasing function g:ℝ+→ℝ+g:R_+ _+ with g(0)=0g(0)=0 such that Lθ(x)≤g(‖x−x⋆(θ)‖2)∀x∈L_θ(x)\ ≤\ g(\|x-x (θ)\|_2)\;∀ x . In particular, if g(r)=rg(r)=r then B(x⋆(θ),ϵ)⊆ϵ(θ)B(x (θ),ε) _ε(θ), and more generally, if g(r)=κrg(r)=κ r then B(x⋆(θ),ϵ/κ)⊆ϵ(θ)B(x (θ),ε/κ) _ε(θ).. In the previous examples one can simply take ρ=ϵρ=ε, and if x:Lθ(x)=0\x:L_θ(x)=0\ contains multiple minimizers, any choice x⋆(θ)∈x:Lθ(x)=0x (θ)∈\x:L_θ(x)=0\ is valid, since B(x⋆(θ),ϵ)⊆ϵ(θ)B(x (θ),ε) _ε(θ). Based on that, we approximate the posterior by a diagonal Gaussian pϕ(x⋆(θ)|Ht=h)≡(μϕ(h),diag(σϕ2(h))),(μt,Σt)=Iϕ(h),p_φ(x (θ)|H_t=h) \! ( _φ(h),\ diag( _φ^2(h)) ), ( _t, _t)=I_φ(h), where IϕI_φ is the inference network. During data collection we use this posterior directly: At∼(μt,Σt)(Thompson-style exploration in ).A_t ( _t, _t) (Thompson-style exploration in A). At stopping time, inference returns the posterior mean, x^=It(h)=μϕ(h), x=I_t(h)= _φ(h), which is a natural point estimate for Euclidean losses and avoids introducing an additional decision head. Finally, we update ϕφ via a negative log-likelihood objective ℒinf(B;ϕ)=^B[−logpϕ(x⋆(θ)|Ht)],L_ inf(B;φ)= E_B [- p_φ (x (θ)|H_t ) ], (5) where E is the empirical average computed on replayed histories from a batch B. We also mantain a target network ϕ¯ φ that is updated via Polyak averaging with parameter ηI _I. Algorithm 1 C-ICPE-TS (Thompson Sampling) 1:Input: Tasks distribution P; confidence δ; risk ϵε; initial λ and hyperparameters ηI,ηQ _I, _Q. 2:// Training phase 3:Initialize buffer ℬ B, networks Qθ,IϕQ_θ,I_φ and set θ¯←θ,ϕ¯←ϕ θ←θ, φ←φ. 4:while Training is not over do 5: Sample environment Mθ∼νM_θ ν and hypothesis x⋆(θ)x (θ); observe Y1∼ρY_1 ρ and set t←1t← 1. 6: repeat 7: Execute action At∼(μt,Σt)A_t N( _t, _t), where (μt,Σt)=Iϕ(Ht)( _t, _t)=I_φ(H_t), and observe Yt+1Y_t+1. 8: Add partial trajectory (Ht,At,Yt+1,x⋆(θ))(H_t,A_t,Y_t+1,x (θ)) to ℬ B and set t←t+1t← t+1. 9: until Qθ(Ht,astop)≥Qθ(Ht,At)Q_θ(H_t,a_ stop)≥ Q_θ(H_t,A_t). 10: In the fixed confidence, update c according to Equation 7. 11: Sample batch B∼ℬB B and update θ,ϕθ,φ using ℒinf(B;ϕ) L_ inf(B;φ) (Equation 5) and train critic using ℒcritic(B;θ) L_ critic(B;θ) (Equation 6). 12: Set ϕ¯←(1−ηI)ϕ¯+ηIϕ φ←(1- _I) φ+ _Iφ and θ¯←(1−ηQ)θ¯+ηQθ θ←(1- _Q) θ+ _Qθ. 13:end while 14: 15:// Inference phase 16:Sample unknown environment M∼M . 17:Collect a trajectory HτH_τ selecting At∼Iϕ(Ht)A_t I_φ(H_t) (until Qθ(Ht,At)≤Qθ(Ht,astop)Q_θ(H_t,A_t)≤ Q_θ(H_t,a_ stop)). 18:Return x^τ=μϕ(Hτ) x_τ= _φ(H_τ) (recommendation). Critic learning and stopping rule. We learn a critic that evaluates two quantities from the same history: (i) the value of stopping, and (i) the value of continuing with the realized (Thompson-sampled) action. Concretely, we parameterize Qθ(h,astop)andQθ(h,a) for a∈.Q_θ(h,a_ stop) Q_θ(h,a)\ for a . Rollouts use the learned posterior to sample AtA_t, and decide to stop when stopping is preferred: stop at t⟺Qθ(Ht,astop)≥Qθ(Ht,At).stop at t Q_θ(H_t,a_ stop)\ ≥\ Q_θ(H_t,A_t). Dentoting by dtd_t the binary variable indicating when a trajectory has stopped, the critic is trained from a replay buffer of transitions (Ht,At,Ht+1,dt)(H_t,A_t,H_t+1,d_t) using a target network θ¯ θ and Polyak averaging with parameter ηQ _Q. Importantly, since A is continuous and we do not learn an actor, we do not maximize Qθ(Ht+1,a)Q_θ(H_t+1,a) over a. Instead, the continuation branch bootstraps using as target value μϕ¯(Ht+1) _ φ(H_t+1). Since the critic is not used to update the sampling procedure, but only to decide when to stop, it is not in general needed to learn an exact critic value, as long as the accuracy signal is unbiased. Furthermore, since exact evaluation of qt(h,x)q_t(h,x) is generally intractable even under a Gaussian posterior, we use the Markov-style lower qt(h,x)≥1−[Lθ(x)|h]ϵq_t(h,x)≥ 1- E[L_θ(x)|h]ε and use the reward r¯(Ht)=1−Lθ(μϕ¯(Ht))ϵ r(H_t)=1- L_θ( _ φ(H_t))ε. Define then the bootstrap value at the next history as Vtarg(Ht+1)≔maxQθ¯(Ht+1,astop),Qθ¯(Ht+1,μϕ¯(Ht+1)),V_ targ(H_t+1) \Q_ θ(H_t+1,a_ stop),\ Q_ θ(H_t+1, _ φ(H_t+1)) \, and the stop/continue targets ytcont≔−c+(1−dt)Vtarg(ht+1),ytstop≔r~(ht),y_t cont -c+(1-d_t)\,V_ targ(h_t+1), y_t stop r(h_t), where c≥0c≥ 0 is a cost representing the dual variable 333For fixed λ>0λ>0, the inner objective in (2) is (up to an additive constant) −[τ]+λ[rτ(Hτ)]-E[τ]+λ\,E[r_τ(H_τ)]. Rescaling by 1/λ1/λ yields the equivalent form [rτ(Hτ)]−c[τ]E[r_τ(H_τ)]-c\,E[τ] with c≔1/λc 1/λ. (we implement the fixed-confidence tradeoff by tuning a nonnegative per-step cost c). The critic is trained to regress the value of continuing with the realized action ata_t and the value of stopping: ℒcritic(B;θ)=12^B[(Qθ(Ht,At)−ytcont)2+(Qθ(Ht,astop)−ytstop)2]. L_ critic(B;θ)= 12\, E_B [ (Q_θ(H_t,A_t)-y_t cont )^2+ (Q_θ(H_t,a_ stop)-y_t stop )^2 ]. (6) Cost update. In the fixed-confidence regime we tune the per-step cost c to target success probability 1−δ1-δ. During training, we estimate the stopping success rate p^=1B∑i=1Bμϕ(Hτ(i))∈ϵ(θ) p= 1B _i=1^B1\ _φ(H_τ^(i)) _ε(θ)\ computed over a minibatch of recent episodes (or an exponential moving average). We then update c←Π[0,1](c−ηc((1−δ)−p^)),c← _[0,1] (c- _c ((1-δ)- p ) ), (7) so that if the empirical confidence falls below 1−δ1-δ we decrease c (allowing longer trajectories), and if it exceeds 1−δ1-δ we increase c (encouraging earlier stopping). 4.1 Model Architecture and Time Pooling Layer Both the inference network IϕI_φ and critic QθQ_θ share a history encoder (see Figure 2). Each interaction step is embedded as a token via a linear map; concretely we form a per-step vector from the continuous action and observation, e.g. ut=[At;Yt+1]u_t=[A_t;Y_t+1] (and optionally time/flag features), and compute et=Linear(ut)∈ℝde_t=Linear(u_t) ^d. The token sequence (e1,…,et)(e_1,…,e_t) is processed by a sequential backbone (either an LSTM, or blocks of attention++feed-forward nets), producing hidden states h1,…,ht∈ℝdh_1,…,h_t ^d. We then apply a time pooling readout that (i) selects informative timesteps and (i) gates feature dimensions. The pooling weights are computed as α=softmax(1d[⟨qin,Wkh1⟩,…,⟨qin,Wkht⟩]),v=∑i=1tαiWvhi,α=softmax ( 1 d [ q_ in,W_kh_1 ,…, q_ in,W_kh_t ] ), v= _i=1^t _i\,W_vh_i, followed by a feature-wise gate z=Gate(v,qout)≔v⊙silu(Wmqout)z=Gate(v,q_ out) v (W_mq_ out). The key difference between inference and critic is how the query qinq_ in is chosen. For the critic, qinq_ in is action-conditioned: we embed the candidate action a through a linear layer and use it as the pooling query, so that the readout performs cross-attention from a into the history. This yields an action-dependent summary z(h,a)z(h,a) used to evaluate Qθ(h,a)Q_θ(h,a) (including a=astopa=a_ stop via a dedicated embedding). For the inference model IϕI_φ, we use an action-independent query (a learned parameter), producing a summary z(h)z(h) that parameterizes the Gaussian posterior head (μt,logσt)( _t, _t). In both cases, the vector qoutq_ out provides a lightweight channel gate on the pooled summary before the output heads. The pooled representation feeds (a) an inference head producing (μt,logσt)( _t, _t) and (b) critic heads producing Qθ(Ht,astop)Q_θ(H_t,a_ stop) and Qθ(Ht,At)Q_θ(H_t,A_t). Figure 2: Shared history encoder and time-pooling readout used by the inference network IϕI_φ and critic QθQ_θ. 5 Empirical Evaluation We evaluate C-ICPE-TS on a range of tasks: continuous binary search problem (target localization), ϵε-best-arm identification problem, and minimization of the Ackley function. For all of the problems, we restrict the query space to =[−1,1]DA=[-1,1]^D, where D∈ℕD is the number of dimensions. In each experiment, we set the tmax=100t_max=100 and conduct the training with 22 seeds. We report 95%95\% confidence intervals (CI) using hierarchical bootstrap with bias-correction and acceleration. 5.1 Baselines In this section, we compare C-ICPE-TS against several baselines. Our first baseline is C-ICPE-Uniform, which still trains an inference network for predicting x⋆x but uses uniform sampling for querying actions during exploration. This comparison isolates the contribution of the meta-learned exploration policy in efficiently gathering information about the hypothesis space X to predict x⋆x . Both methods are trained in the fixed-confidence setting with δ=0.1δ=0.1. Beyond C-ICPE-Uniform, we compare C-ICPE-TS with Bayesian Optimization methods: Tree-structured Parzen Estimator (TPE) (Bergstra et al., 2011), Gaussian Process (GP) (Ament et al., 2023), and an evolutionary algorithm: Covariance Matrix Adaptation Evolution Strategy (CMA-ES) (Hansen, 2016), all implemented via Optuna (Akiba et al., 2019). TPE models the objective by building two density estimators over good and bad observations and selects candidates that maximize this ratio. GP fits a probabilistic model with a Matérn kernel by maximizing the marginal log-likelihood, Optuna uses log Expected Improvement as its acquisition function. CMA-ES samples a population of candidates and iteratively updates a multivariate Gaussian distribution by adapting its covariance matrix based on successful candidates. For fair comparison, all these baselines are given a fixed horizon equal to [τ]E[τ] of C-ICPE-TS. We also try horizons equal to [τ]+kστE[τ]+k _τ, where k∈1,2,3k∈\1,2,3\ and στ _τ is the standard deviation of τ, to account for the variance in τ. We evaluate each method across different dimensions and values of ϵε to investigate C-ICPE’s scalability and ability to solve problems of varying difficulty. 5.2 Binary Search Problem Problem Description. Figure 3: Binary search problem in =[−1,1]2X=[-1,1]^2: a query AtA_t yields YtY_t; the goal is to predict x x within ε of x⋆x . In traditional binary search problem, the goal is to find a target value efficiently within sorted arrays. In our experiment, we extend the problem to the D-dimensional hypercube =[−1,1]DX=[-1,1]^D with D∈ℕD , where we seek to find a uniformly sampled true hypothesis x⋆∈x as visualized in Figure 3. The observation space is Y=−1,1DY=\-1,1\^D: the observation is a sign function that indicates whether the action is below or above x⋆x in each dimension i=1,…,Di=1,…,D: Yt,i=1if At,i≤xi⋆−1if At,i>xi⋆Y_t,i= cases1&if A_t,i≤ x _i\\ -1&if A_t,i>x _i cases (8) ϵ=0.1ε=0.1 ϵ=0.2ε=0.2 6D 8D 10D 6D 8D 10D Correctness C-ICPE-TS 0.9040.904 [.861,.945] 0.9210.921 [.906,.935] 0.9360.936 [.902,.970] 0.9450.945 [.911,.974] 0.9090.909 [.891,.926] 0.9410.941 [.898,.981] C-ICPE-Uniform 0.9570.957 [.945,.968] 0.9150.915 [.889,.938] 0.8990.899 [.880,.917] 0.8920.892 [.855,.927] 0.8850.885 [.825,.941] 0.9230.923 [.911,.934] Stopping Time (τ) C-ICPE-TS 7.497.49 [7.21,7.77] 7.977.97 [7.83,8.11] 8.608.60 [8.23,8.95] 5.965.96 [5.79,6.14] 6.166.16 [6.13,6.20] 6.756.75 [6.44,7.08] C-ICPE-Uniform 53.3253.32 [50.98,55.76] 60.0160.01 [54.41,65.90] 65.5765.57 [63.22,67.86] 19.0719.07 [18.06,20.09] 23.4123.41 [20.74,26.25] 28.7828.78 [28.18,29.38] Table 1: Performance on Binary Search Problem: correctness (accuracy with 95% bootstrap CI) and stopping time (τ, mean with 95% bootstrap CI) across dimensions and ϵε values. ϵ=0.1ε=0.1 ϵ=0.2ε=0.2 6D 8D 10D 6D 8D 10D Correctness C-ICPE-TS 0.9040.904 [.866,.941] 0.9170.917 [.902,.933] 0.9150.915 [.905,.925] 0.9140.914 [.899,.927] 0.9150.915 [.890,.938] 0.9050.905 [.885,.925] C-ICPE-Uniform 0.9530.953 [.912,.990] 0.9880.988 [.983,.992] 0.8990.899 [.886,.910] 0.9620.962 [.944,.977] 0.9290.929 [.906,.951] 0.9010.901 [.880,.920] TPE (k=3k=3) 0.0110.011 [.004,.017] 0.0040.004 [.000,.007] 0.0010.001 [.000,.002] 0.0040.004 [.000,.007] 0.0030.003 [.000,.005] 0.0010.001 [.000,.002] GP (k=3k=3) 0.1590.159 [.136,.180] 0.0380.038 [.025,.049] 0.0100.010 [.003,.015] 0.2750.275 [.246,.302] 0.1710.171 [.147,.194] 0.1400.140 [.117,.160] CMA-ES (k=3k=3) 0.0020.002 [.000,.004] 0.0000.000 [.000,.000] 0.0010.001 [.000,.002] 0.0040.004 [.000,.007] 0.0010.001 [.000,.002] 0.0010.001 [.000,.002] Stopping Time (τ) C-ICPE-TS 24.7924.79 [22.41,27.19] 48.6448.64 [47.41,49.85] 83.9083.90 [78.62,88.95] 10.4710.47 [10.04,10.89] 17.4017.40 [16.44,18.36] 25.4425.44 [25.21,25.68] C-ICPE-Uniform 56.3856.38 [36.19,76.86] 93.3393.33 [93.12,93.57] 90.7490.74 [90.62,90.86] 17.4717.47 [15.43,19.58] 23.7723.77 [22.46,25.08] 31.9231.92 [30.84,33.00] Table 2: Performance on ϵε-Best-Arm Problem: correctness (accuracy with 95% bootstrap CI) and stopping time (τ, mean with 95% bootstrap CI) across dimensions and ϵε values. TPE, GP, and CMA-ES use a fixed horizon equal to [τ]+kστE[τ]+k _τ, where k=3k=3 and τ is the stopping time of C-ICPE-TS. ϵ=0.1ε=0.1 ϵ=0.2ε=0.2 3D 4D 5D 3D 4D 5D Correctness C-ICPE-TS 0.9060.906 [.849,.958] 0.8950.895 [.859,.929] 0.9020.902 [.886,.915] 0.9240.924 [.914,.934] 0.9210.921 [.900,.936] 0.8730.873 [.857,.888] C-ICPE-Uniform 0.9120.912 [.901,.924] 0.7420.742 [.601,.884] 0.5700.570 [.533,.607] 0.9050.905 [.875,.932] 0.9060.906 [.889,.922] 0.8320.832 [.748,.913] TPE (k=3k=3) 0.2590.259 [.231,.285] 0.1210.121 [.100,.140] 0.0320.032 [.020,.042] 0.5400.540 [.507,.569] 0.4010.401 [.370,.431] 0.2360.236 [.209,.261] GP (k=3k=3) 0.4370.437 [.405,.467] 0.1720.172 [.148,.194] 0.0480.048 [.035,.061] 0.6970.697 [.668,.725] 0.4550.455 [.423,.484] 0.2210.221 [.195,.246] CMA-ES (k=3k=3) 0.1640.164 [.141,.187] 0.0960.096 [.078,.113] 0.0300.030 [.018,.040] 0.3680.368 [.336,.397] 0.2840.284 [.255,.312] 0.1570.157 [.133,.178] Stopping Time (τ) C-ICPE-TS 19.5119.51 [18.01,20.96] 31.8631.86 [29.13,34.81] 50.3650.36 [48.99,51.87] 15.7715.77 [14.77,16.76] 26.0026.00 [24.91,27.17] 34.3034.30 [32.97,35.56] C-ICPE-Uniform 62.1962.19 [58.22,66.40] 92.0692.06 [87.37,96.81] 93.5993.59 [91.91,95.23] 34.4934.49 [28.65,40.33] 67.9567.95 [60.99,74.96] 89.9089.90 [84.70,95.15] Table 3: Performance on Ackley Function: correctness (accuracy with 95% bootstrap CI) and stopping time (τ, mean with 95% bootstrap CI) across dimensions and ϵε values. TPE, GP, and CMA-ES use a fixed horizon equal to [τ]+kστE[τ]+k _τ, where k=3k=3 and τ is the stopping time of C-ICPE-TS. Accuracy and Sample Complexity Table 1 reports the expected accuracy [[∥x^−x⋆∥2<ϵE[1[\| x-x \|_2<ε]] and the expected stopping time [τ]E[τ] across all problems, dimensions, and ϵε values. On the binary search problem, both C-ICPE-TS and C-ICPE-Uniform achieve the target (1−δ)(1-δ)-accuracy, but C-ICPE-TS requires significantly fewer samples by leveraging the learned posterior. This gap widens at ϵ=0.1ε=0.1, where C-ICPE-Uniform requires 66-8×8× more steps than C-ICPE-TS, demonstrating that Thompson sampling with the learned posterior are more sample-efficient than uniform sampling. Figure 7(a) in the Appendix provides additional insight into the learned stopping behavior. We can see from the survival function that C-ICPE-TS learns to stop early when uncertainty reaches a low convergence value, as Figure 7(b) in the Appendix shows that the standard deviation converges when the critic network predicts to stop the exploration. In contrast, C-ICPE-Uniform shows a rather heavier tail distribution of τ. This suggests that the learned critic network in C-ICPE-TS effectively recognizes when sufficient samples has been queries to make a good prediction of x x and enable early stopping. Robustness to Prior Misspecification C-ICPE is a meta-learning algorithm, meaning it can generalize across a wide range of priors rather than optimizing for a single problem setting. We investigate C-ICPE-TS’s performance when the prior distribution at test time differs from training. During training, the true hypothesis x⋆x is sampled uniformly; at evaluation, we instead sample from Beta(α,β)Beta(α,β) distributions with varying parameters. Note that α=β=1α=β=1 recovers the uniform distribution used during training. Table 4 in the Appendix reports the expected accuracy and the expected stopping time under different (α,β)(α,β) settings, sorted by DKL(Beta∥Uniform)D_KL(Beta\|Uniform). Interestingly, despite KL divergences as large as 2.392.39, the performance remains largely unchanged, demonstrating C-ICPE-TS’s robustness to prior misspecification. 5.3 ϵε-Best-Arm Identification Problem Figure 4: ϵε-best-arm problem in =[−1,1]2X=[-1,1]^2: C-ICPE queries AtA_t yields YtY_t; the goal is to predict x x within ε of x⋆x . Problem Description Best-arm identification (BAI) in multi-armed bandits focuses on identifying the arm with the highest mean reward. We extend this problem to continuous spaces where the hypothesis space is the surface of a unit sphere, =x⋆∈[−1,1]D∣‖x⋆‖2=1X=\x ∈[-1,1]^D \|x \|_2=1\, with D∈ℕD , exemplified in Figure 4. The observation is Yt=At⊤x⋆+ηY_t=A_t x +η, where η∼(0,0.052)η (0,0.05^2).444In practice we use Yt=‖x⋆−At‖2+ηY_t=\|x -A_t\|_2+η, which is equivalent on the unit sphere since ‖x⋆−At‖22=2−2At⊤x⋆\|x -A_t\|_2^2=2-2A_t x when ‖x⋆‖2=1\|x \|_2=1. Similarly, C-ICPE-TS and C-ICPE-Uniform are both trained in the fixed-confidence setting (with δ=0.1δ=0.1) and evaluated across different dimensions and values of ϵε. Accuracy and Sample Complexity In Table 2, we can see that both C-ICPE-TS and C-ICPE-Uniform achieve the target accuracy (with δ=0.1δ=0.1) across all dimensions and ϵε values. While having similar expected accuracies, the expected stopping time of C-ICPE-TS is consistently lower. When ϵ=0.1ε=0.1, C-ICPE-TS requires approximately half as many queries as C-ICPE-Uniform in the 6D and 8D scenarios. For 10D, C-ICPE-TS’s [τ]E[τ] could be further reduced with additional training, while C-ICPE-Uniform has already converged to [τ]≈90E[τ]≈ 90. These results demonstrate that the meta-learned posterior distribution with Thompson sampling substantially improves the sample efficiency over uniform exploration while maintaining the target accuracy. For the Bayesian optimization methods and evolutionary algorithm, the expected accuracy is substantially lower despite having more queries with k=3k=3. GP obtains the highest expected accuracy among the three baselines, but even in the easier ϵ=0.2ε=0.2 case, it achieves only one-third of C-ICPE-TS’s accuracy in 3D. As dimensionality increases, the accuracy gap widens further. Results for other k values can be found in Table 7 in the Appendix. Survival function and uncertainty convergence show consistent patterns with Section 5.2; full results are provided in Figure 8 in the Appendix. Robustness to Prior Misspecification Similar to Section 5.2, we investigate C-ICPE-TS’s robustness to prior misspecification using the same protocol. Table 5 shows that even as KL divergence increases, the expected accuracy and stopping time remain nearly constant, demonstrating that C-ICPE-TS is robust to prior misspecification for the ϵε-best-arm problem as well. 5.4 Ackley Function Problem Description The Ackley function (Figure 1) is a non-convex function that is widely used benchmark for optimization methods since it has multiple local minima surrounding the global optimum (Naser et al., 2025). Its mixture of outer flat regions, many local minima, and highly curved surfaces captures the complexity of real-world optimization tasks, making it popular for testing an algorithm’s ability to avoid premature convergence and escape local traps. The Ackley function is defined as: f(At;φ)=−aexp(−b1D∑i=1DAi,t2)−exp(1D∑i=1Dcos(cAi,t))+a+ef(A_t; )=-a (-b 1D _i=1^DA_i,t^2 )- ( 1D _i=1^D (cA_i,t) )+a+e (9) Figure 5: Effect of parameters b and c on the Ackley function landscape. where φ=(a,b,c) =(a,b,c) are the function parameters that control the function’s characteristics, and D is the dimensionality. Specifically, a determines the amplitude of the function; b controls the steepness of the basin leading towards the global optimum; and c dictates the frequency of the local minima. The parameters’ effect on the ackley function landscape can be visualized in Figure 5. In our experiments, we fix a=10a=10 since it primarily affects the function’s output range, while uniformly sampling b∼[0.1,0.5]b [0.1,0.5] and c∼[π,4π]c [π,4π] as the priors. The goal of the problem is to predict the location of the global optimum. The original Ackley function is a minimization problem with the global optimum always at the origin. We modify the function in two ways: first, we shift the global optimum uniformly within [−1,1]D[-1,1]^D and use it as x⋆x ; second, we invert the function output to become a maximization problem, where the observation Yt=−f(At;φ)+ηY_t=-f(A_t; )+η, where η∼(0,0.052)η (0,0.05^2). Despite we fix the value of a, the output range still depends on the sampled priors, and the influence from the noise could vary. Based on the ranges of the priors, query space, and dimensions used in this experiment, we derive a normalization constant empirically: Znorm=π−0.21⋅D+9.68⋅b+0.04⋅cZ_norm=π-0.21· D+9.68· b+0.04· c. Accuracy and Sample Complexity As shown in Table 3, both C-ICPE-TS and C-ICPE-Uniform achieve (1−δ)(1-δ)-correctness across all three dimensions when ϵ=0.2ε=0.2. However, the table also shows that the expected stopping time of C-ICPE-TS is less than half that of C-ICPE-Uniform. The gap widens at ϵ=0.1ε=0.1: C-ICPE-Uniform still attains the target accuracy in the 3D setting, although with a relatively large [τ]E[τ], but as dimensionality increases, it fails to reach the target accuracy even at the near maximum horizon. By contrast, C-ICPE-TS achieves the target accuracy across all three dimensions with comparatively small [τ]E[τ], demonstrating that the learned policy efficiently gather information and effectively find x⋆x . Additionally, the other three baselines struggle under the given horizon length. GP consistently achieves the highest accuracy among the three baselines across all dimensions and ϵε values, yet still fails to reach the target accuracy (δ=0.1δ=0.1) even with k=3k=3. When ϵ=0.2ε=0.2, the expected accuracy declines to 0.221 in the 5D scenario; the performance degrades further under ϵ=0.1ε=0.1, where the expected accuracy drops below 0.05 in 5D. This gap in expected accuracy between C-ICPE-TS and GP highlights C-ICPE’s ability to learn a policy that accurately predicts x x within ϵε of x⋆x using far fewer queries. Results for other k values can be found in Table 7 in the Appendix. Survival function and uncertainty convergence show consistent patterns with Section 5.2; full results are provided in Figure 9 in the Appendix. Robustness to Prior Misspecification Unlike Section 5.2 and Section 5.3, the Ackley function has additional priors beyond x⋆x , namely b and c. We investigate C-ICPE-TS’s robustness to prior misspecification on the Ackley function using the same approach: we sample all priors from Beta(α,β)Beta(α,β) distributions with varying parameters at evaluation. Interestingly, Table 6 in the Appendix shows that despite KL divergences as large as 2.39 and the increased number of priors to sample, the expected accuracy and expected stopping time remain largely unchanged. This demonstrates C-ICPE-TS’s ability to meta-learn and generalize its policy across ranges of prior values, maintaining robustness to prior misspecification even with more complex prior distributions. 6 Discussion, Related Work and Conclusions Active sequential hypothesis testing (ASHT) provides the broad conceptual umbrella for this paper. In ASHT, a learner adaptively selects experiments and decides when to stop and declare a hypothesis, with the objective of minimizing expected sample size subject to a correctness constraint (Chernoff, 1959; Wald and Wolfowitz, 1948; Ghosh, 1991; Naghshvar and Javidi, 2013; Naghshvar et al., 2012). A key methodological theme in this literature is that fixed-confidence constraints can be handled via Lagrangian duality. Closely related line of works include Bayesian experimental design and Bayesian active learning, which study adaptive data acquisition when the unknown is drawn from a known prior, typically optimizing expected utility or information gain (Lindley, 1956; Golovin and Krause, 2011; Rainforth et al., 2024), and active learning, which emphasizes selecting informative queries/labels to reduce uncertainty efficiently (Cohn et al., 1996). Despite the shared emphasis on adaptive measurement and sequential stopping, most classical ASHT results assume substantial knowledge of the observation model: one typically has access to likelihoods (or at least to a parametric family) for every experiment under every hypothesis, enabling explicit likelihood-ratio statistics and model-based allocation (Naghshvar and Javidi, 2013). While there are efforts toward relaxing this assumption to partial model knowledge (Cecchi and Hegde, 2017), the need for explicit likelihood structure remains a limiting factor for modern continuous environments with complex, history-dependent feedback. In many practical settings, the learner must instead infer both (i) which latent environment/task it is facing and (i) which actions are informative, using only interaction data and function approximation. This motivates data-driven approaches that preserve the ASHT objective while reducing dependence on fully specified likelihoods. A prominent special case of ASHT is fixed-confidence pure exploration in bandits and reinforcement learning, where the hypothesis is typically the identity of an optimal action/policy rather than an arbitrary latent state of nature. In finite-armed bandits (Lattimore and Szepesvári, 2020), best-arm identification (BAI) at ϵ=0ε=0 is characterized by a mature theory: instance-dependent lower bounds quantify the intrinsic complexity of identifying the best arm (Garivier and Kaufmann, 2016; Degenne et al., 2019; Wang et al., 2020; Jedra and Proutiere, 2020; Kocák and Garivier, 2021; Russo and Proutiere, 2023b; Poiani et al., 2025b; Russo et al., 2025a), and a family of algorithms achieves near-optimal sample complexity by coupling adaptive allocation with statistically valid stopping rules (Audibert and Bubeck, 2010; Russo, 2016; Garivier and Kaufmann, 2016; Wang et al., 2021; Jourdan et al., 2022). These results provide both sharp guidance and strong baselines, but they rely on a finite decision set and model-specific likelihood constructions. Even under well-specified models, moving from ϵ=0ε=0 BAI to (ϵ,δ)(ε,δ)-PAC identification in continuous decision spaces can be technically and computationally demanding; recent works study continuous pure exploration, but typically at the cost of heavier machinery(Garivier and Kaufmann, 2021; Poiani et al., 2025a). Our work targets exactly this regime: continuous decisions with fixed-confidence guarantees. Pure exploration also extends naturally to Markov decision processes (MDPs) (Puterman, 2014) through best-policy identification and related PAC objectives: the learner aims to identify an optimal policy with probability at least 1−δ1-δ (Al Marjani et al., 2021; Taupin et al., 2023; Al Marjani et al., 2023; Russo and Proutiere, 2023a; Russo and Vannella, 2024). This literature yields sharp insights into exploration complexity in sequential decision processes. However, much of it is developed for finite state-action structure and focuses on identifying a policy, whereas our primary object is a continuous decision. Only recently has work begun to treat (ϵ,δ)(ε,δ)-PAC objectives in finite MDP settings for best policy identification (Tirinzoni et al., 2022) and optimal data-collection for policy evaluation (Russo and Pacchiano, 2025). Our contribution complements this direction by emphasizing continuous decision spaces and a practical design. Bayesian viewpoints connect these settings by treating tasks as random draws from a prior, and optimizing average-case performance over this prior. In bandits, posterior sampling and top-two style methods provide principled exploration heuristics driven by posterior uncertainty, with analyses based on posterior concentration and allocation (Russo and Van Roy, 2014; Russo, 2016). In continuous domains, related ideas appear in Bayesian optimization (BO) (Garnett, 2023), where a posterior over an unknown objective is updated from noisy evaluations and an acquisition rule selects the next query point (often via expected improvement or information-based criteria) (Hernández-Lobato et al., 2014; Hennig and Schuler, 2012). BO is conceptually aligned with identifying an optimizer, but it is most commonly posed as fixed-budget optimization or simple regret minimization, and it typically relies on function-space posteriors (e.g., Gaussian processes) whose inference and optimization can become challenging in high dimensions. Moreover, BO pipelines do not usually produce a fixed-confidence stopping mechanism derived from a correctness constraint. This gap motivates our design choices, and propose a model that autonomously learn when to stop with a given confidence guarantee. Taken together, prior work establishes (i) a principled fixed-confidence objective and duality-based stopping perspective (ASHT), (i) sharp sample-complexity theory and strong baselines in finite bandits and finite MDPs, and (i) Bayesian and information-gain criteria for adaptive experimentation and continuous optimization. The remaining challenge is a method that retains the fixed-confidence semantics while scaling to continuous decisions and complex observation models without requiring known likelihoods, explicit confidence sequences, or continuous-action maximization. Our approach addresses this by combining a posterior-driven exploration rule with a stopping critic trained off-policy from replay. Limitations and future directions. This paper inherits several limitations of the broader ICPE algorithm, while also introducing new ones specific to continuous spaces. First, unimodal parametric posteriors (e.g., diagonal Gaussians) may be too restrictive when the set of minimizers is multi-modal or when the posterior over optima is intrinsically non-Gaussian. Second, the approach is most natural when actions and decisions coincide; extending to settings where the hypothesis space differs from the query space requires an explicit actor model. Third, while duality motivates the stop/continue structure, turning the dual variable into a robust, well-calibrated cost schedule remains an important practical detail (and a point where miscalibration can hurt stopping behavior). Promising directions include richer posterior families (mixtures/flows), explicit treatment of multiple minimizers, offline or batch training protocols. Overall, this work extends the ICPE viewpoint to continuous decision spaces by (i) replacing discrete posteriors with posterior success probabilities, (i) using Lagrangian duality to recover an optimal-stopping Bellman structure in the continuous case, and (i) proposing a practical Thompson-style exploration strategy that avoids learning an actor and pairs naturally with a stop/continue critic. We view this as a step toward general-purpose, learned sequential testing procedures in continuous domains where hand-designed algorithms are unavailable or costly to engineer. References T. Akiba, S. Sano, T. Yanase, T. Ohta, and M. Koyama (2019) Optuna: a next-generation hyperparameter optimization framework. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, p. 2623–2631. Cited by: §5.1. A. Al Marjani, A. Garivier, and A. Proutiere (2021) Navigating to the best policy in markov decision processes. In Advances in neural information processing systems, Vol. 34, p. 25852–25864. Cited by: §1, §6. A. Al Marjani, T. Kocak, and A. Garivier (2023) On the Complexity of All ϵε-Best Arms Identification. In Machine Learning and Knowledge Discovery in Databases, M. Amini, S. Canu, A. Fischer, T. Guns, P. Kralj Novak, and G. Tsoumakas (Eds.), Vol. 13716, Cham, p. 317–332 (en). Note: Series Title: Lecture Notes in Computer Science External Links: ISBN 978-3-031-26411-5 978-3-031-26412-2, Link, Document Cited by: §6. S. Ament, S. Daulton, D. Eriksson, M. Balandat, and E. Bakshy (2023) Unexpected improvements to expected improvement for bayesian optimization. Advances in neural information processing systems 36, p. 20577–20612. Cited by: §5.1. J. Audibert and S. Bubeck (2010) Best arm identification in multi-armed bandits. In COLT-23th Conference on learning theory-2010, p. 13–p. Cited by: §1, §6. J. Bergstra, R. Bardenet, Y. Bengio, and B. Kégl (2011) Algorithms for hyper-parameter optimization. Advances in neural information processing systems 24. Cited by: §5.1. F. Cecchi and N. Hegde (2017) Adaptive active hypothesis testing under limited information. Advances in Neural Information Processing Systems 30. Cited by: §6. H. Chernoff (1959) Sequential design of experiments. The Annals of Mathematical Statistics 30 (3), p. 755 – 770. Note: Publisher: Institute of Mathematical Statistics External Links: Link, Document Cited by: §1, §6. D. A. Cohn, Z. Ghahramani, and M. I. Jordan (1996) Active learning with statistical models. Journal of artificial intelligence research 4, p. 129–145. Cited by: §6. R. Degenne, W. M. Koolen, and P. Ménard (2019) Non-asymptotic pure exploration by solving games. In Advances in neural information processing systems, H. Wallach, H. Larochelle, A. Beygelzimer, F. dAlché-Buc, E. Fox, and R. Garnett (Eds.), Vol. 32. External Links: Link Cited by: §1, §6. A. Garivier and E. Kaufmann (2016) Optimal best arm identification with fixed confidence. Proceedings of the 29th Conference on Learning Theory 49, p. 998–1027. Cited by: §1, §6. A. Garivier and E. Kaufmann (2021) Nonasymptotic sequential tests for overlapping hypotheses applied to near-optimal arm identification in bandit models. Sequential Analysis 40 (1), p. 61–96. Note: Publisher: Taylor & Francis Cited by: §1, §6. R. Garnett (2023) Bayesian Optimization. Cambridge University Press. Cited by: §6. B. K. Ghosh (1991) A brief history of sequential analysis. Handbook of sequential analysis 1. Cited by: §6. D. Golovin and A. Krause (2011) Adaptive submodularity: Theory and applications in active learning and stochastic optimization. Journal of Artificial Intelligence Research 42, p. 427–486. Cited by: §6. N. Hansen (2016) The cma evolution strategy: a tutorial. arXiv preprint arXiv:1604.00772. Cited by: §5.1. P. Hennig and C. J. Schuler (2012) Entropy Search for Information-Efficient Global Optimization. Journal of Machine Learning Research 13 (57), p. 1809–1837. External Links: ISSN 1533-7928 Cited by: §6. J. M. Hernández-Lobato, M. W. Hoffman, and Z. Ghahramani (2014) Predictive Entropy Search for Efficient Global Optimization of Black-box Functions. In Advances in Neural Information Processing Systems, Vol. 27. External Links: Link Cited by: §6. Y. Jedra and A. Proutiere (2020) Optimal best-arm identification in linear bandits. In Advances in neural information processing systems, Vol. 33, p. 10007–10017. Cited by: §6. M. Jourdan, R. Degenne, D. Baudry, R. de Heide, and E. Kaufmann (2022) Top Two Algorithms Revisited. In Advances in Neural Information Processing Systems, Vol. 35, p. 26791–26803 (en). External Links: Link Cited by: §6. T. Kocák and A. Garivier (2021) Best arm identification in spectral bandits. In Proceedings of the twenty-ninth international joint conference on artificial intelligence, IJCAI’20, Yokohama, Yokohama, Japan. Note: Number of pages: 7 tex.articleno: 307 External Links: ISBN 978-0-9992411-6-5 Cited by: §6. T. Lattimore and C. Szepesvári (2020) Bandit algorithms. Cambridge University Press. Cited by: §6. D. V. Lindley (1956) On a measure of the information provided by an experiment. The Annals of Mathematical Statistics 27 (4), p. 986–1005. Cited by: §6. Y. Liu, T. Zhao, W. Ju, and S. Shi (2017) Materials discovery and design using machine learning. Journal of Materiomics 3 (3), p. 159–177. Cited by: §1. M. Naghshvar, T. Javidi, and K. Chaudhuri (2012) Noisy bayesian active learning. In 2012 50th annual allerton conference on communication, control, and computing (allerton), p. 1626–1633. Cited by: §6. M. Naghshvar and T. Javidi (2013) Active Sequential Hypothesis Testing. The Annals of Statistics 41 (6), p. 2703–2738. External Links: 23566746, ISSN 0090-5364 Cited by: §1, §3, §6, §6. M. Naser, M. K. Al-Bashiti, A. T. G. Tapeh, A. Naser, V. Kodur, R. Hawileh, J. Abdalla, N. Khodadadi, A. H. Gandomi, and A. D. Eslamlou (2025) A review of benchmark and test functions for global optimization algorithms and metaheuristics. Wiley Interdisciplinary Reviews: Computational Statistics 17 (2), p. e70028. Cited by: §5.4. R. Poiani, M. Bernasconi, and A. Celli (2025a) Pure Exploration with Infinite Answers. arXiv. External Links: 2505.22473, Document Cited by: §6. R. Poiani, M. Jourdan, E. Kaufmann, and R. Degenne (2025b) Best-Arm Identification in Unimodal Bandits. In Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, p. 2233–2241 (en). Note: ISSN: 2640-3498 External Links: Link Cited by: §1, §6. M. L. Puterman (2014) Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons. Cited by: §1, §6. T. Rainforth, A. Foster, D. R. Ivanova, and F. Bickford Smith (2024) Modern Bayesian experimental design. Statistical Science 39 (1), p. 100–114. Note: Publisher: Institute of Mathematical Statistics Cited by: §1, §6. A. Russo and A. Pacchiano (2025) Adaptive exploration for multi-reward multi-policy evaluation. In Proceedings of the 42nd international conference on machine learning, A. Singh, M. Fazel, D. Hsu, S. Lacoste-Julien, F. Berkenkamp, T. Maharaj, K. Wagstaff, and J. Zhu (Eds.), Proceedings of machine learning research, Vol. 267, p. 52382–52421. External Links: Link Cited by: §1, §6. A. Russo and A. Proutiere (2023a) Model-free active exploration in reinforcement learning. In Advances in neural information processing systems, Vol. 36, p. 54740–54753. Cited by: §6. A. Russo and A. Proutiere (2023b) On the sample complexity of representation learning in multi-task bandits with global and local structure. In Proceedings of the AAAI conference on artificial intelligence, Vol. 37, p. 9658–9667. Cited by: §6. A. Russo, Y. Song, and A. Pacchiano (2025a) Pure exploration with feedback graphs. In Proceedings of the 28th international conference on artificial intelligence and statistics, Proceedings of machine learning research, Vol. 258, p. 1810–1818. Cited by: §1, §6. A. Russo and F. Vannella (2024) Multi-reward best policy identification. In Advances in neural information processing systems, Vol. 37, p. 105583–105662. Cited by: §6. A. Russo, R. Welch, and A. Pacchiano (2025b) Learning to Explore: An In-Context Learning Approach for Pure Exploration. arXiv (en). Note: arXiv:2506.01876 [cs] External Links: Link, Document Cited by: §A.3, §A.3, §1, §2, §3, §3, §3. D. Russo and B. Van Roy (2014) Learning to optimize via posterior sampling. Mathematics of Operations Research 39 (4), p. 1221–1243. Cited by: §6. D. Russo (2016) Simple Bayesian Algorithms for Best Arm Identification. In Conference on Learning Theory, p. 1417–1418 (en). External Links: ISSN 1938-7228, Link Cited by: §6, §6. J. Taupin, Y. Jedra, and A. Proutiere (2023) Best policy identification in discounted linear MDPs. In Sixteenth european workshop on reinforcement learning, Cited by: §6. W. R. Thompson (1933) On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika 25 (3-4), p. 285–294. Cited by: §4. A. Tirinzoni, A. Al Marjani, and E. Kaufmann (2022) Near instance-optimal pac reinforcement learning for deterministic mdps. In Advances in neural information processing systems, Vol. 35, p. 8785–8798. Cited by: §6. A. Wald and J. Wolfowitz (1948) Optimum character of the sequential probability ratio test. The Annals of Mathematical Statistics 19 (3), p. 326 – 339. External Links: Link, Document Cited by: §6. P. Wang, A. Proutiere, K. Ariu, Y. Jedra, and A. Russo (2020) Optimal algorithms for multiplayer multi-armed bandits. In Proceedings of the twenty third international conference on artificial intelligence and statistics, S. Chiappa and R. Calandra (Eds.), Proceedings of machine learning research, Vol. 108, p. 4120–4129. External Links: Link Cited by: §6. P. Wang, R. Tzeng, and A. Proutiere (2021) Fast Pure Exploration via Frank-Wolfe. In Advances in Neural Information Processing Systems, Vol. 34, p. 5810–5821. Cited by: §6. Contents 1 Introduction 2 Problem Setting 3 Theoretical Background 4 Deep Learning and Thompson Sampling for Exploration in Continuous Space 4.1 Model Architecture and Time Pooling Layer 5 Empirical Evaluation 5.1 Baselines 5.2 Binary Search Problem 5.3 ϵε-Best-Arm Identification Problem 5.4 Ackley Function 6 Discussion, Related Work and Conclusions A Appendix: Theoretical Results A.1 Problem Modeling A.2 Posterior distribution over the true hypothesis and inference rule optimality A.3 Fixed-confidence setting: dual formulation B Appendix: Numerical Results Appendix A Appendix: Theoretical Results A.1 Problem Modeling We specialize to the fixed-confidence ((ϵ,δ)(ε,δ)-PAC) setting introduced in Section 2, and provide a self-contained definition of the induced probability measures. We now provide a formal definition of the underlying probability measures of the problem we consider. To that aim, it is important to formally define what a model M is, as well as the definition of policy π and inference rule I (infernece rules are also known as recommendation rules). Spaces and histories. Let Θ⊂ℝd ^d be compact. Let ⊂ℝmA ^m be a compact action (query) space and ⊂ℝnY ^n a compact observation space, each endowed with the Borel σ-algebra. Let X be a compact hypothesis/decision space (in our experiments =X=A). For t∈ℕt , define the history space ℋt≔(×)t−1×,ht=(y1,a1,…,at−1,yt),H_t (Y×A)^t-1×Y, h_t=(y_1,a_1,…,a_t-1,y_t), with its product Borel σ-algebra. We also write ℋ∞≔×(×)ℕH_∞ ×(A×Y)^N for infinite histories. Since ,A,Y are compact metric spaces, ℋtH_t and ℋ∞H_∞ are standard Borel spaces. Environment (observation model). An environment is indexed by θ∈Θθ∈ and specified by an initial observation law ρθ∈Δ() _θ∈ (Y) and a sequence of (possibly history-dependent) observation kernels Pθ,t(⋅|ht,at)∈Δ(),t≥1,P_θ,t(·|h_t,a_t)∈ (Y), t≥ 1, such that for every Borel C⊂C the map (ht,a)↦Pθ,t(C|ht,a)(h_t,a) P_θ,t(C|h_t,a) is measurable. Optionally, one may assume weak continuity in θ. However, we do assume weak continuity in a, as this is later used to prove optimality. Assumption A.1 (Weak continuity of the transition). For all θ∈Θθ∈ we assume a↦Pθ,t(⋅|ht,a)a P_θ,t(·|h_t,a) to be weakly continuous.555That is, for all continuous bounded functions f we have that a↦∫f(y)Pθ,t(dy|ht,a)a _ Yf(y)P_θ,t( dy|h_t,a) is continuous. Learner: policy, stopping time, inference rule. A (possibly randomized) sampling policy is a sequence of probability kernels πt(⋅|ht)∈Δ(),t≥1, _t(·|h_t)∈ (A), t≥ 1, measurable as maps ℋt→Δ()H_t→ (A). Let Ht=(Y1,A1,…,At−1,Yt)H_t=(Y_1,A_1,…,A_t-1,Y_t) be the random history and ℱt=σ(Ht)F_t=σ(H_t). A stopping time τ is defined w.r.t. (ℱt)t≥1(F_t)_t≥ 1. An inference rule is a sequence of measurable maps It:ℋt→I_t:H_t , and the learner outputs x^τ≔Iτ(Hτ). x_τ I_τ(H_τ). Loss and ϵε-optimal set. For each θ∈Θθ∈ , the environment induces a loss function Lθ:→[0,∞)L_θ:X→[0,∞) with infx∈Lθ(x)=0 _x L_θ(x)=0. Define the ϵε-optimal set ϵ(θ)≔x∈:Lθ(x)≤ϵ.X_ε(θ) \x :\ L_θ(x)≤ε\. Path measures (Ionescu–Tulcea). Fix θ∈Θθ∈ and a policy π. By the Ionescu–Tulcea theorem, there exists a unique probability measure ℙθ,tπP_θ,t^π on (ℋt,ℬ(ℋt))(H_t,B(H_t)) such that for all cylinder sets C=C1×B1×⋯×Bt−1×CtC=C_1× B_1×·s× B_t-1× C_t (with Ci∈ℬ()C_i (Y) and Bi∈ℬ()B_i (A)), ℙθ,tπ(C) _θ,t^π(C) =∫C1ρθ(dy1)∏s=1t−1[∫Bsπs(das|hs)∫Cs+1Pθ,s(dys+1|hs,as)]. = _C_1 _θ(dy_1) _s=1^t-1 [ _B_s _s( da_s|h_s)\, _C_s+1P_θ,s( dy_s+1|h_s,a_s) ]. Analogously, one obtains a unique path measure ℙθπP_θ^π on (ℋ∞,ℬ(ℋ∞))(H_∞,B(H_∞)). Mixture law over tasks. Given a prior ν on Θ , define the joint law on Θ×ℋt ×H_t by tπ(dθ,dht)≔ν(dθ)ℙθ,tπ(dht),P_t^π( dθ, dh_t) ν( dθ)\,P_θ,t^π( dh_t), and the trajectory marginal ℙtπ(⋅)=∫ℙθ,tπ(⋅)ν(dθ)P_t^π(·)= _θ,t^π(·)\,ν( dθ). We use θ∼νπ[⋅]E_θ ν^π[·] and ℙθ∼νπ(⋅)P_θ ν^π(·) for expectations/probabilities under this mixture. Fixed-confidence objective. The learner is (ϵ,δ)(ε,δ)-correct (under ν) if ℙθ∼νπ(x^τ∈ϵ(θ))≥1−δ.P_θ ν^π\! ( x_τ _ε(θ) )≥ 1-δ. In the fixed-confidence regime, we seek to minimize the expected number of queries subject to (ϵ,δ)(ε,δ)-correctness: infπ,I,τθ∼νπ[τ]s.t.ℙθ∼νπ(x^τ∈ϵ(θ))≥1−δ. _π,I,τ\ E_θ ν^π[τ] .t. _θ ν^π\! ( x_τ _ε(θ) )≥ 1-δ. A.2 Posterior distribution over the true hypothesis and inference rule optimality We first record a domination assumption that allows us to express likelihoods w.r.t. fixed reference measures. Assumption A.2 (Domination). There exist probability measures λ0,λ _0,λ on (,ℬ())(Y,B(Y)) such that, for all θ∈Θθ∈ , all t≥1t≥ 1, and all (ht,a)∈ℋt×(h_t,a) _t×A, ρθ(⋅)≪λ0(⋅)andPθ,t(⋅|ht,a)≪λ(⋅). _θ(·) _0(·) P_θ,t(·|h_t,a) λ(·). Let pθ,0(y)≔dρθdλ0(y)p_θ,0(y) d _θ d _0(y) and pθ,t(y′|ht,a)≔dPθ,t(⋅|ht,a)dλ(y′)p_θ,t(y |h_t,a) dP_θ,t(·|h_t,a) dλ(y ) be versions of the corresponding densities, chosen jointly measurable in their arguments. Remark. The assumption holds, for instance, when all ρθ _θ and Pθ,t(⋅|ht,a)P_θ,t(·|h_t,a) admit densities w.r.t. a common reference measure (e.g., Lebesgue on ⊂ℝnY ^n or counting measure when Y is finite). Under A.2, define the (policy-independent) likelihood of a realized history ht=(y1,a1,…,at−1,yt)∈ℋth_t=(y_1,a_1,…,a_t-1,y_t) _t under parameter θ: ℓt(θ,ht)≔pθ,0(y1)∏s=1t−1pθ,s(ys+1|hs,as),hs=(y1,a1,…,as−1,ys). _t(θ,h_t) p_θ,0(y_1) _s=1^t-1p_θ,s(y_s+1|h_s,a_s), h_s=(y_1,a_1,…,a_s-1,y_s). We now give a posterior kernel representation that is independent of π. Lemma A.3 (Posterior kernel over Θ ). For each t∈ℕt there exists a probability kernel Rt:ℋt×ℬ(Θ)→[0,1]R_t:H_t×B( )→[0,1], independent of π, such that for every policy π, all A∈ℬ(Θ)A ( ) and Z∈ℬ(ℋt)Z (H_t), tπ(θ∈A,Ht∈Z)=∫ZRt(A|h)ℙtπ(dh),P_t^π(θ∈ A,H_t∈ Z)= _ZR_t(A|h)P_t^π( dh), where tπ(dθ,dh)=ν(dθ)ℙθ,tπ(dh)P_t^π( dθ, dh)=ν( dθ)\,P_θ,t^π( dh) and ℙtπP_t^π is its ℋtH_t-marginal. Moreover, for ℙtπP_t^π-a.e. h∈ℋth _t, Rt(A|h)=∫Aℓt(θ,h)ν(dθ)∫Θℓt(θ,h)ν(dθ).R_t(A|h)= _A _t(θ,h)ν( dθ) _ _t(θ,h)ν( dθ). Consequently, for any measurable map g:Θ→g: into a standard Borel space S and any B∈ℬ()B (S), ℙ(g(θ)∈B|Ht=h)=Rt(θ:g(θ)∈B|h)for ℙtπ-a.e. h.P(g(θ)∈ B|H_t=h)=R_t(\θ:\ g(θ)∈ B\|h) P_t^π-a.e.\ h. Proof. Fix π and t. Define the reference measure on ℋtH_t (depending on π) νtπ(dht)≔λ0(dy1)∏s=1t−1[πs(das|hs)λ(dys+1)]. _t^π( dh_t) _0( dy_1) _s=1^t-1 [ _s( da_s|h_s)\,λ( dy_s+1) ]. By construction and A.2, ℙθ,tπ≪νtπP_θ,t^π _t^π for every θ, with Radon–Nikodym density dℙθ,tπdνtπ(ht)=ℓt(θ,ht), dP_θ,t^π d _t^π(h_t)= _t(θ,h_t), which does not depend on π. Therefore, for A∈ℬ(Θ)A ( ) and Z∈ℬ(ℋt)Z (H_t), tπ(θ∈A,Ht∈Z)=∫A∫Zℓt(θ,h)νtπ(dh)ν(dθ),P_t^π(θ∈ A,H_t∈ Z)= _A _Z _t(θ,h)\, _t^π( dh)ν( dθ), and ℙtπ(Z)=∫Z∫Θℓt(θ,h)ν(dθ)νtπ(dh).P_t^π(Z)= _Z _ _t(θ,h)\,ν( dθ)\, _t^π( dh). Hence tπ(θ∈A,⋅)≪ℙtπ(⋅)P_t^π(θ∈ A,·) _t^π(·) and the Radon–Nikodym derivative is the displayed Bayes ratio, which defines the kernel Rt(A|h)R_t(A|h). Measurability and the fact that Rt(⋅|h)R_t(·|h) is a probability measure follow from standard properties of Radon–Nikodym derivatives. Independence of π is immediate from the explicit formula. ∎ Optimal inference rule. Fix ϵ>0ε>0 and t∈ℕt . Recall that, for each θ∈Θθ∈ , the ϵε-optimal set is ϵ(θ)=x∈:Lθ(x)≤ϵX_ε(θ)=\x :L_θ(x)≤ε\. Given a realized history h∈ℋth _t, define the posterior success probability of recommending x∈x as qt(h,x)≔ℙθ∼νπ(x∈ϵ(θ)|Ht=h)=Rt(θ∈Θ:Lθ(x)≤ϵ|h),q_t(h,x) _θ ν^π (x _ε(θ)|H_t=h )=R_t (\θ∈ :L_θ(x)≤ε\|h ), (10) where Rt(⋅|h)R_t(·|h) is the posterior kernel from Lemma A.3. We also define rt(h)≔supx∈qt(h,x).r_t(h) _x q_t(h,x). (11) If, for every θ, the map x↦Lθ(x)x L_θ(x) is continuous on the compact set X, then ϵ(θ)X_ε(θ) is closed and x↦x∈ϵ(θ)x 1\x _ε(θ)\ is upper semicontinuous. Consequently, x↦qt(h,x)x q_t(h,x) is upper semicontinuous ℙtπP_t^π-a.s.. To see this, let (xn)n(x_n)_n be a sequence in X such that xn→x⋆x_n→ x . Define yn=xn∈ϵ(θ)y_n=1\x_n _ε(θ)\. By Fatou’s reverse lemma we have lim supnt[yn|Ht=h]≤t[lim supnyn|Ht=z]≤ℙt(x∈ϵ(θ)|Ht=h). _nE_t[y_n|H_t=h] _t[ _ny_n|H_t=z]≤P_t(x _ε(θ)|H_t=h). where the last inequality follows from the fact that lim supnyn≤x∈ϵ(θ) _ny_n≤1\x _ε(θ)\ from the upper semicontinuity. Thus the posterior is upper semicontinuous on ℙtπP_t^π-a.s. Since X is compact, by the Extreme Value theorem we have that the supremum in (11) is attained (so one may replace sup by max ). Proposition A.4 (Optimal inference). Consider a fixed policy π and a fixed time t∈ℕt . Among measurable inference rules It:ℋt→I_t:H_t , the maximal value of ℙθ∼νπ(It(Ht)∈ϵ(θ))P_θ ν^π (I_t(H_t) _ε(θ) ) is achieved by any rule satisfying, for ℙtπP_t^π-a.e. h∈ℋth _t, It(h)∈argmaxx∈qt(h,x),I_t(h)∈ _x q_t(h,x), with ties broken by a fixed convention. Proof. Fix π and t, and let x^t≔It(Ht) x_t I_t(H_t). Using the posterior kernel, ℙθ∼νπ(x^t∈ϵ(θ)) _θ ν^π ( x_t _ε(θ) ) =∫x^t∈ϵ(θ)tπ(dθ,dh) = 1\ x_t _ε(θ)\\,P_t^π( dθ, dh) =∫ℋt[∫ΘIt(h)∈ϵ(θ)Rt(dθ|h)]ℙtπ(dh) = _H_t [ _ 1\I_t(h) _ε(θ)\\,R_t( dθ|h) ]P_t^π( dh) =∫ℋtqt(h,It(h))ℙtπ(dh) = _H_tq_t (h,I_t(h) )\,P_t^π( dh) ≤∫ℋtsupx∈qt(h,x)ℙtπ(dh)=∫ℋtrt(h)ℙtπ(dh). ≤ _H_t _x q_t(h,x)\,P_t^π( dh)= _H_tr_t(h)\,P_t^π( dh). If It(h)∈argmaxx∈qt(h,x)I_t(h)∈ _x q_t(h,x) for ℙtπP_t^π-a.e. h, then the inequality holds with equality, yielding the optimal value. A measurable selection can be obtained by tie-breaking. ∎ We also note the following lower bound on the posterior qtq_t. Lemma A.5 (Markov lower bound on posterior success). Fix ϵ>0ε>0, t∈ℕt , and a realized history h∈ℋth _t. For any decision x∈x , define the posterior success probability qt(h,x)≔ℙθ∼νπ(Lθ(x)≤ϵ|Ht=h),q_t(h,x) _θ ν^π (L_θ(x)≤ε|H_t=h ), and the posterior mean loss L¯t(h,x)≔θ∼νπ[Lθ(x)|Ht=h]. L_t(h,x) _θ ν^π [L_θ(x)|H_t=h ]. Then qt(h,x)≥1−L¯t(h,x)ϵ.q_t(h,x)≥ 1- L_t(h,x)ε. Equivalently, with the (clipped) shaped reward rϵ(θ,x)≔[1−Lθ(x)/ϵ]+r_ε(θ,x) [1-L_θ(x)/ε ]_+, qt(h,x)≥θ∼νπ[rϵ(θ,x)|Ht=h].q_t(h,x) _θ ν^π [r_ε(θ,x)|H_t=h ]. Proof. Since Lθ(x)≥0L_θ(x)≥ 0, Markov’s inequality yields ℙθ∼νπ(Lθ(x)>ϵ|Ht=h)≤L¯t(h,x)ϵ.P_θ ν^π (L_θ(x)>ε|H_t=h )≤ L_t(h,x)ε. Taking complements gives the first claim. For the second, note that Lθ(x)≤ϵ≥[1−Lθ(x)/ϵ]+1\L_θ(x)≤ε\≥[1-L_θ(x)/ε]_+ pointwise, and take conditional expectations. ∎ A.3 Fixed-confidence setting: dual formulation We consider the fixed-confidence problem from Section 2 in its Bayesian (task-averaged) form. A learner is a triplet (π,I,τ)(π,I,τ) with sampling policy π, inference rule I=(It)t≥1I=(I_t)_t≥ 1, and stopping time τ. The objective is infπ,I,τθ∼νπ[τ]s.t.ℙθ∼νπ(Iτ(Hτ)∈ϵ(θ))≥ 1−δ,θ∼νπ[τ]<∞. _π,I,τ\ E^π_θ ν[τ] .t. ^π_θ ν\! (I_τ(H_τ) _ε(θ) )\ ≥\ 1-δ, ^π_θ ν[τ]<∞. (12) Throughout this section, Ht=(Y1,A1,…,At−1,Yt)H_t=(Y_1,A_1,…,A_t-1,Y_t) is the history, x^τ=Iτ(Hτ) x_τ=I_τ(H_τ) and ℱt=σ(Ht)F_t=σ(H_t). Posterior success. For each t and realized history h∈ℋth _t, define the posterior success probability of recommending x∈x as qt(h,x)≔ℙθ∼νπ(x∈ϵ(θ)|Ht=h),q_t(h,x)\ \ P^π_θ ν (x _ε(θ)|H_t=h ), and recall rt(h)≔supx∈qt(h,x)r_t(h) _x q_t(h,x). We have the following lemma that relates the success probability to the expected posterior success. Lemma A.6 (Stopped success as expected posterior success). For any policy π, stopping time τ, and inference rule I, ℙθ∼νπ(x^τ∈ϵ(θ))=π[qτ(Hτ,x^τ)].P_θ ν^π ( x_τ _ε(θ) )=E^π [q_τ (H_τ, x_τ ) ]. Proof. By the tower rule and x^τ x_τ being σ(Hτ)σ(H_τ)-measurable, ℙθ∼νπ(x^τ∈ϵ(θ))=π[π[x^τ∈ϵ(θ)∣Hτ]]=π[qτ(Hτ,x^τ)].P_θ ν^π( x_τ _ε(θ))=E^π [E^π\! [1\ x_τ _ε(θ)\ H_τ ] ]=E^π [q_τ(H_τ, x_τ) ]. ∎ Therefore, we have that ℙθ∼νπ(Iτ(Hτ)∈ϵ(θ))=π[qτ(Hτ,Iτ(Hτ))]P^π_θ ν (I_τ(H_τ) _ε(θ) )=E^π [q_τ (H_τ,I_τ(H_τ) ) ]. Lagrangian dual. Define, for λ≥0λ≥ 0, the Lagrangian value Vλ(π,I,τ)≔θ∼νπ[τ]+λ((1−δ)−ℙθ∼νπ(Iτ(Hτ)∈ϵ(θ))).V_λ(π,I,τ) ^π_θ ν[τ]\ +λ ((1-δ)-P^π_θ ν (I_τ(H_τ) _ε(θ) ) ). Using Lemma A.6, this can be written as Vλ(π,I,τ)=λ(1−δ)+π[τ−λqτ(Hτ,Iτ(Hτ))].V_λ(π,I,τ)=λ(1-δ)+E^π [τ-λ q_τ (H_τ,I_τ(H_τ) ) ]. (13) The Lagrangian dual of (12) is then supλ≥0infπ,I,τVλ(π,I,τ). _λ≥ 0\ _π,I,τ\ V_λ(π,I,τ). (14) Optimal inference rule. Fix π,λπ,λ and t. Among all measurable inference rules It:ℋt→I_t:H_t , the maximal probability of ϵε-success at time t is achieved by any It(h)∈argmaxx∈qt(h,x),I_t(h)∈ _x q_t(h,x), with ties broken by a fixed convention; equivalently, qt(h,It(h))=rt(h)q_t(h,I_t(h))=r_t(h) for ℙtπP_t^π-a.e. h. (see Proposition A.4.) Since τ is adapted, plugging the optimal inference rule into Equation 13 yields the simplified dual objective supλ≥0infπ,τλ(1−δ)+π[τ−λrτ(Hτ)]. _λ≥ 0 _π,τλ(1-δ)+E^π [τ-λ r_τ(H_τ) ]. (15) Stopping as an action (equivalence). The additional optimization over stopping rules can be avoided by introducing an additional stopping aciton astopa_ stop. Introduce an augmented action space ¯≔∪astop A ∪\a_ stop\, where choosing astopa_ stop terminates interaction (no new observation is collected). Let τ¯≔inft≥1:At=astop τ \t≥ 1:A_t=a_ stop\. Lemma A.7 (Embedding stopping times as a stop action). For every triplet (π,I,τ)(π,I,τ) with τ<∞τ<∞ a.s., there exists a policy π¯ π on ¯ A such that, under π¯ π, (i) τ¯=τ τ=τ a.s., and (i) the stopped history Hτ¯H_ τ has the same distribution as HτH_τ under π. In particular, for every λ≥0λ≥ 0, Vλ(π,I,τ)=Vλ(π¯,I,τ¯)V_λ(π,I,τ)=V_λ( π,I, τ). Proof. Since τ is a stopping time w.r.t. ℱt=σ(Ht)F_t=σ(H_t), the event τ=t\τ=t\ belongs to ℱtF_t; hence there exists a measurable set St⊂ℋtS_t _t such that τ=t=Ht∈St\τ=t\=\H_t∈ S_t\. Define π¯ π as follows: at time t, given history h∈ℋth _t, π¯t(astop|h)=h∈St,π¯t(⋅|h)=πt(⋅|h) on when h∉St. π_t(a_ stop|h)=1\h∈ S_t\, π_t(·|h)= _t(·|h)\ on A\ when h∉ S_t. Then At=astop=Ht∈St=τ=t\A_t=a_ stop\=\H_t∈ S_t\=\τ=t\, so τ¯=τ τ=τ a.s. Moreover, on the event τ>t\τ>t\ the action distribution and observation kernel coincide with those under π, so the induced law of (Ht)t≤τ(H_t)_t≤τ is the same; in particular Hτ¯H_ τ under π¯ π has the same distribution as HτH_τ under π. Hence, one can easily show that the equality Vλ(π,I,τ)=Vλ(π¯,I,τ¯)V_λ(π,I,τ)=V_λ( π,I, τ) follows. ∎ Optimal Policy. Lemma A.7 shows that (for fixed λ) the inner problem in Equation 15 can be viewed as an optimal-stopping control problem on the augmented action space: each continuation step incurs unit cost, while stopping at history h∈ℋth _t incurs terminal cost −λrt(h)-λ\,r_t(h). Define the optimal cost-to-go (for fixed λ) from a history h∈ℋth _t as Vt⋆(h;λ)≔infπ¯=(π¯i)i≥tθ∼νπ¯[∑s=tτ¯−11−λrτ¯(Hτ¯)|Ht=h],V_t (h;λ) _ π=( π_i)_i≥ t\ E_θ ν π [ _s=t τ-11-λ r_ τ(H_ τ) |\ H_t=h ], (16) where the infimum is over policies on ¯ A and τ¯ τ is the first time astopa_ stop is chosen. Similarly to [Russo et al., 2025b], we can define the following optimal Q-functions Qt,stop⋆(h;λ)≔−λrt(h),Qt,cont⋆(h,a;λ)≔1+[Vt⋆(Ht+1;λ)|Ht=h,At=a].Q_t, stop (h;λ) -λ r_t(h), Q_t, cont (h,a;λ) 1+E [V_t (H_t+1;λ)|H_t=h,A_t=a ]. where the latter expectation is over the posterior mixture, defined as P¯t(y′∈Y|Ht=h,At=a)=∫Pθ,t(y′∈Y|Ht,At=a)Rt(dθ|Ht=h),∀Y∈ℬ(). P_t(y ∈ Y|H_t=h,A_t=a)= P_θ,t(y ∈ Y|H_t,A_t=a)R_t( dθ|H_t=h), ∀ Y∈ B( Y). Furthermore, similarly to [Russo et al., 2025b], a standard decomposition yields the Bellman optimality relation Vt⋆(h;λ)=minQt,stop⋆(h;λ),infa∈Qt,cont⋆(h,a;λ).V_t (h;λ)= \Q_t, stop (h;λ), _a Q_t, cont (h,a;λ) \. (17) However, in order to guarantee that the infimum ,infa∈Qt,cont⋆(h,a;λ), _a Q_t, cont (h,a;λ) is attained, since A is compact, we need to guarantee that the Q-value is lower semicontinuous. We begin by showing that Vt⋆V_t is lower semicontinuous. To that aim, we need some results first. We begin by showing that the mixture posterior is weakly continuous. Lemma A.8 (Weak continuity of the mixture posterior). Fix t and h∈ℋth _t. Let Rt(⋅|h)R_t(·|h) be the posterior on Θ and define the posterior predictive kernel P¯t(⋅|h,a)≔∫ΘPθ,t(⋅|h,a)Rt(dθ|h). P_t(·|h,a) _ P_θ,t(·|h,a)\,R_t( dθ|h). Under A.1, a↦P¯t(⋅|h,a)a P_t(·|h,a) is weakly continuous. Proof. Fix f∈Cb()f∈ C_b(Y) (continuous and bounded) and a sequence (an)n(a_n)_n such that an→a_n→ a. For each θ, by A.1, ∫f(y)Pθ,t(dy|h,an)→∫f(y)Pθ,t(dy|h,a). f(y)\,P_θ,t( dy|h,a_n)→ f(y)\,P_θ,t( dy|h,a). Moreover, |∫f(y)dPθ,t(dy|h,an)|≤∥f∥∞<∞ | f(y)\, dP_θ,t( dy|h,a_n) |≤\|f\|_∞<∞ for all θ,nθ,n. By dominated convergence, ∫f(y)P¯t(dy|h,an)=∫Θ(∫f(y)dPθ,t(dy|h,an))Rt(dθ∣h) f(y)\, P_t( dy|h,a_n)= _ ( f(y)\, dP_θ,t( dy|h,a_n) )R_t( dθ h) →∫Θ(∫f(y)Pθ,t(dy|h,a))Rt(dθ∣h), → _ ( f(y)\,P_θ,t( dy|h,a) )R_t( dθ h), =∫f(y)P¯t(dy|h,a). = f(y) P_t( dy|h,a). ∎ Now, consider the truncated problem where one is forced to stop at time T, and let VtT(⋅;λ)V_t^T(·;λ) be its optimal value. Baed on this value, we also define the Q-value of continuing in this problem QtT(h,a;λ)=1+[Vt+1T(Ht+1;λ)|Ht=h,At=a].Q_t^T(h,a;λ)=1+E [V_t+1^T(H_t+1;λ)|H_t=h,A_t=a ]. For this truncated version of the problem, we have that the infimum over actions is attained. Lemma A.9 (Finite-horizon l.s.c. and attainment). Fix λ≥0λ≥ 0 and an horizon T≥tT≥ t. Consider the truncated problem where one is forced to stop at time T, and let VtT(⋅;λ)V_t^T(·;λ) be its optimal value. Under A.1, for every h∈ℋth _t the map a↦QtT(h,a;λ)a Q_t^T(h,a;λ) is lower semicontinuous on A and infa∈QtT(h,a;λ) _a Q_t^T(h,a;λ) is attained. Proof. Boundedness: for any admissible policy, ∑s=tτ−11−λrτ(Hτ)≥−λ _s=t^τ-11-λ r_τ(H_τ)≥-λ a.s., hence VtT(⋅;λ)≥−λV_t^T(·;λ)≥-λ. We prove (i) by backward induction on t. The terminal value is VTT(h;λ)=−λrT(h)V_T^T(h;λ)=-λ r_T(h), which is lower semicontinuous since rt(h)=supxqt(h,x)r_t(h)= _xq_t(h,x) and q is upper semicontinuous. Fix t<Tt<T and assume Vt+1T(⋅;λ)V_t+1^T(·;λ) is lower semicontinuous and bounded below by −λ-λ. For fixed h∈ℋth _t, define QtT(h,a;λ)=1+∫Vt+1T((h,a,y);λ)P¯t(dy|h,a),Q_t^T(h,a;λ)=1+ _YV_t+1^T ((h,a,y);λ ) P_t( dy|h,a), where P¯t P_t is the mixture posterior. Let an→a_n→ a and denote μn=P¯t(⋅∣h,an) _n= P_t(· h,a_n), μ=P¯t(⋅∣h,a)μ= P_t(· h,a). By Lemma A.8 we have μn _n converges weakly to μ. Since y↦Vt+1T((h,a,y);λ)y V_t+1^T((h,a,y);λ) is lower semicontinuous and bounded below, the Portmanteau theorem yields lim infn→∞∫Vt+1T((h,a,y);λ)μn(dy)≥∫Vt+1T((h,a,y);λ)μ(dy). _n→∞ _YV_t+1^T ((h,a,y);λ ) _n( dy)≥ _YV_t+1^T ((h,a,y);λ )μ( dy). Hence a↦QtT(h,a;λ)a Q_t^T(h,a;λ) is lower semicontinuous. Finally, since A is compact, we have that infa∈QtT(h,a;λ) _a Q_t^T(h,a;λ) is attained. ∎ Finally, we extend the previous result by taking the infimum over T. Lemma A.10 (Infinite-horizon value as a limit). Under A.1, for every t and h∈ℋth _t, Vt⋆(h;λ)=infT≥tVtT(h;λ).V_t (h;λ)= _T≥ tV_t^T(h;λ). Moreover, for every fixed h, the map a↦Qt,cont⋆(h,a;λ)a Q_t, cont (h,a;λ) is lower semicontinuous on A, hence the infimum over a∈a is attained. Proof. For any T≥tT≥ t, forcing termination at T restricts the policy class, hence Vt⋆(h;λ)≤VtT(h;λ)V_t (h;λ)≤ V_t^T(h;λ) and so Vt⋆(h;λ)≤infT≥tVtT(h;λ)V_t (h;λ)≤ _T≥ tV_t^T(h;λ). Now, for any admissible pair (π¯,τ¯)( π, τ)666Such pair always exists as long as the admissible set of pairs (π,τ)(π,τ) is non-empty.let us define Jt(h;π¯,τ¯)=π¯[∑s=tτ¯1−λrτ¯(Hτ¯)|Ht=h].J_t(h; π, τ)=E π [ _s=t τ1-λ r_ τ(H_ τ) |H_t=h ]. For the reverse inequality, fix ε>0 >0 and choose an ε -optimal admissible pair (π¯,τ¯)( π, τ) for Vt⋆(h;λ)V_t (h;λ), so that Jt(h;π¯,τ¯)=π¯[∑s=tτ¯−11−λrτ¯(Hτ¯)|Ht=h]≤Vt⋆(h;λ)+ε.J_t(h; π, τ)=E π [ _s=t τ-11-λ r_ τ(H_ τ) |H_t=h ]≤ V_t (h;λ)+ . Define τ¯T=min(τ¯,T) τ_T= ( τ,T) and use the same policy π¯ π until τ¯T τ_T. Clearly, on τ¯≤T\ τ≤ T\ the costs coincide; on τ¯>T\ τ>T\ we have 0≤(∑s=tτ¯−11−λrτ¯(Hτ¯))−(∑s=tτ¯T−11−λrτ¯T(Hτ¯T))≤(τ¯−T)+2λ.0≤ ( _s=t τ-11-λ r_ τ(H_ τ) )- ( _s=t τ_T-11-λ r_ τ_T(H_ τ_T) )≤( τ-T)+2λ. Therefore 0≤|Jt(h;π¯,τ¯)−Jt(h;π¯,τ¯T)|≤π¯[(τ¯−T)+|Ht=h]+2λℙπ¯(τ¯>T|Ht=h).0≤ |J_t(h; π, τ)-J_t(h; π, τ_T) | π[( τ-T)^+|H_t=h]+2 π( τ>T|H_t=h). Since τ¯ τ is admissible, we have that [τ¯]<∞E[ τ]<∞, implying that π¯[(τ¯−T)+|Ht=h]+2λℙπ¯(τ¯>T|Ht=h)→0 as T→∞.E π[( τ-T)^+|H_t=h]+2 π( τ>T|H_t=h)→ 0 as T→∞. and thus Jt(h;π¯,τ¯T)→Jt(h;π¯,τ¯T)J_t(h; π, τ_T)→ J_t(h; π, τ_T) as T→∞T→∞. In particular, for δ>0δ>0 there exists TδT_δ such that for T≥TδT≥ T_δ we have Jt(h;π¯,τ¯T)≤Jt(h;π¯,τ¯)+δ.J_t(h; π, τ_T)≤ J_t(h; π, τ)+δ. Since (π¯,τ¯)( π, τ) is ϵε-optimal, we also have that Jt(h;π¯,τ¯T)≤Vt⋆(h;λ)+ϵ+δ.J_t(h; π, τ_T)≤ V_t (h;λ)+ε+δ. Taking δ=ϵδ=ε, with T≥TϵT≥ T_ε, yields Jt(h;π¯,τ¯T)≤Vt⋆(h;λ)+2ϵ.J_t(h; π, τ_T)≤ V_t (h;λ)+2ε. Since (π¯,τ¯T)( π, τ_T) is feasible for the forced-stop problem at horizon T, we have VtT(h;λ)≤Jt(h;π¯,τ¯T)≤Vt⋆(h;λ)+2ϵV_t^T(h;λ)≤ J_t(h; π, τ_T)≤ V_t (h;λ)+2ε. Taking infimum over T on the l.h.s., and letting ϵ↓0ε 0 yields infT≥tVtT(h;λ)≤Vt⋆(h;λ) _T≥ tV_t^T(h;λ)≤ V_t (h;λ), proving the equality. Finally, Lemma A.9 yields that for fixed h, a↦Qt,contT(h,a;λ)a Q_t, cont^T(h,a;λ) is lower semicontinuous: taking infT _T preserves this property, hence a↦Qt,cont⋆(h,a;λ)a Q_t, cont (h,a;λ) is l.s.c. Compactness of A gives attainment. ∎ Hence, we conclude with the following result Proposition A.11 (Actor over A and stopping action). Assume A.1 and let a⋆(h)∈argmina∈Qt,cont⋆(h,a)a (h)∈ _a Q_t, cont (h,a). Then an optimal policy can be implemented by: (i) selecting a⋆(h)a (h) as the continuation action, and (i) stopping iff Qt,stop⋆(h)≤Qt,cont⋆(h,a⋆(h))Q_t, stop (h)≤ Q_t, cont (h,a (h)). Proof. By (17), at each history h the optimal action is whichever attains the minimum between Qt,stop⋆(h)Q_t, stop (h) and infa∈Qt,cont⋆(h,a) _a Q_t, cont (h,a). If a⋆(h)a (h) attains the infimum over A, then the comparison Qt,stop⋆(h)≤Qt,cont⋆(h,a⋆(h))Q_t, stop (h)≤ Q_t, cont (h,a (h)) is equivalent to Qt,stop⋆(h)≤infaQt,cont⋆(h,a)Q_t, stop (h)≤ _aQ_t, cont (h,a), i.e., stopping is optimal. Otherwise continuing with a⋆(h)a (h) is optimal. ∎ This last result shows that an algorithm can act in the augmented space ¯ A while never explicitly parameterizing a “stop action” in the actor. Hence an optimal policy can be implemented by: 1. choose a continuation action a⋆(h)∈argmina∈Qt,cont⋆(h,a)a (h)∈ _a Q_t, cont (h,a) (this is the actor over A only); 2. stop if Qt,stop⋆(h)≤Qt,cont⋆(h,a⋆(h))Q_t, stop (h)≤ Q_t, cont (h,a (h)), otherwise continue with a⋆(h)a (h). This is mathematically equivalent to having a single policy over ¯ A that selects argminQt,stop⋆(h),minaQt,cont⋆(h,a) \Q_t, stop (h), _aQ_t, cont (h,a)\, but it decomposes the decision into (i) a continuous control over A and (i) an optimal-stopping comparison against a scalar stop value. Therefore, one can learn a Q-value for the stop decision and comparing it to the Q-value of the actor-chosen action: this is consistent with the optimal control structure of (17), provided the actor approximates the minimizer of Qt,cont⋆(h,⋅)Q_t, cont (h,·) and the critic estimates are calibrated. Appendix B Appendix: Numerical Results (a) (b) Figure 6: Effect of Ackley function’s parameters on output range across multiple dimensions: (a) range vs b; (b) range vs c. Ackley Function Output Normalization The Ackley function’s global minimum is always at the origin with a value of 0, but the maximum value within our defined hypothesis space X depends on the function parameters and dimensionality. Figures 6(a) and 6(b) show how the values of b and c affect the function output ranges. Larger b values consistently increase the range, while c has less significant effect on the output ranges. From the figures, we also see that the ranges depend on dimensionality, where lower dimensions tend to have larger ranges. The issue with varying output ranges is that the influence of noise can vary across different priors sampled, and we want the noise effect to be on the same scale. Additionally, without normalization, C-ICPE must not only learn the relative patterns from HtH_t but also account for the scale differences across different HtH_t. For these reasons, we derive a normalization constant empirically from multiple samples across different b, c values and dimensionalities: Znorm=π−0.21⋅D+9.68⋅b+0.04⋅cZ_norm=π-0.21· D+9.68· b+0.04· c. (a) (b) Figure 7: Results for Binary Search Problem with fixed confidence δ=0.1δ=0.1 and N=100N=100 across different dimensions and ϵε: (a) survival function of τ; (b) inference uncertainty convergence. (a) (b) Figure 8: Results for ϵε-Best-Arm Identification Problem with fixed confidence δ=0.1δ=0.1 and N=100N=100 across different dimensions and ϵε: (a) survival function of τ; (b) inference uncertainty convergence. (a) (b) Figure 9: Results for Ackley function with fixed confidence δ=0.1δ=0.1 and N=100N=100 across different dimensions and ϵε: (a) survival function of τ; (b) inference uncertainty convergence. Survival Function and Uncertainty Convergence In all three problems, we compare the performance of C-ICPE-TS and C-ICPE-Uniform. Specifically, we evaluate whether they can achieve the target accuracy (with δ=0.1δ=0.1) and, if so, whether they minimize the expected stopping time. In most problems, ϵε values, and dimensions, both methods achieve the target accuracy (except for C-ICPE-Uniform with 4D, 5D and ϵ=0.1ε=0.1 in the Ackley function). We consistently observe that C-ICPE-TS has lower expected stopping time than C-ICPE-Uniform. To further understand the stopping behaviors, we show the survival functions and inference uncertainty convergence across the horizon for all methods, ϵε values, and dimensionalities in Figures 7 and 9. Across all settings, we see that the standard deviation of C-ICPE-TS converges quickly before the critic network predicts to stop querying, matching how P(τ>t)P(τ>t) drops quickly. In contrast, C-ICPE-Uniform shows a heavier tail distribution of τ. This combined result of survival function and uncertainty convergence demonstrates C-ICPE-TS’s critic network’s effectiveness in identifying when sufficient information has been gathered for making a good estimate of x⋆x . 6D 8D 10D (α,β)(α,β) DKLD_KL τ Acc. τ Acc. τ Acc. (1,1)(1,1) 0.000.00 5.965.96 0.9450.945 6.166.16 0.9090.909 6.756.75 0.9410.941 (0.5,0.5)(0.5,0.5) 0.140.14 5.465.46 0.8650.865 5.755.75 0.8510.851 6.836.83 0.9570.957 (3,3)(3,3) 0.600.60 6.146.14 0.9300.930 6.516.51 0.9330.933 7.507.50 0.9840.984 (5,5)(5,5) 1.551.55 6.176.17 0.9140.914 6.456.45 0.9170.917 7.497.49 0.9700.970 (1,5)(1,5) 2.392.39 5.655.65 0.9320.932 5.595.59 0.8480.848 6.536.53 0.9610.961 (5,1)(5,1) 2.392.39 5.285.28 0.8460.846 5.905.90 0.9100.910 7.047.04 0.9820.982 Table 4: Robustness to misspecification on binary search problem (ϵ=0.2ε=0.2). Trained with Uniform(1,1)Uniform(1,1), evaluated under Beta(α,β)Beta(α,β). Sorted by DKL(Beta∥Uniform)D_KL(Beta\|Uniform). 6D 8D 10D (α,β)(α,β) DKLD_KL τ Acc. τ Acc. τ Acc. (1,1)(1,1) 0.000.00 10.4010.40 0.9080.908 17.3617.36 0.9110.911 25.5525.55 0.9060.906 (0.5,0.5)(0.5,0.5) 0.140.14 10.2910.29 0.9230.923 17.0817.08 0.9210.921 24.8924.89 0.9090.909 (3,3)(3,3) 0.600.60 10.6410.64 0.9100.910 17.8617.86 0.8980.898 26.6926.69 0.8870.887 (5,5)(5,5) 1.551.55 10.6610.66 0.9020.902 18.0918.09 0.8920.892 26.7726.77 0.8820.882 (1,5)(1,5) 2.392.39 10.2710.27 0.9230.923 16.6316.63 0.9110.911 23.4523.45 0.9080.908 (5,1)(5,1) 2.392.39 10.1910.19 0.9140.914 16.9116.91 0.9290.929 24.0424.04 0.9220.922 Table 5: Robustness to misspecification on ϵε-best-arm identification problem (ϵ=0.2ε=0.2). Trained with Uniform(1,1)Uniform(1,1), evaluated under Beta(α,β)Beta(α,β). Sorted by DKL(Beta∥Uniform)D_KL(Beta\|Uniform). 3D 4D 5D (α,β)(α,β) DKLD_KL τ Acc. τ Acc. τ Acc. (1,1)(1,1) 0.000.00 15.7715.77 0.9240.924 26.0026.00 0.9210.921 34.3034.30 0.8730.873 (0.5,0.5)(0.5,0.5) 0.140.14 15.7515.75 0.8580.858 27.2527.25 0.8520.852 35.9435.94 0.8210.821 (3,3)(3,3) 0.600.60 14.3214.32 0.9610.961 23.5223.52 0.9690.969 32.1032.10 0.9600.960 (5,5)(5,5) 1.551.55 14.2314.23 0.9670.967 21.7021.70 0.9810.981 31.5831.58 0.9730.973 (1,5)(1,5) 2.392.39 13.5813.58 0.9550.955 20.3620.36 0.9070.907 30.3530.35 0.8670.867 (5,1)(5,1) 2.392.39 13.9213.92 0.9180.918 26.0026.00 0.96330.9633 32.0332.03 0.9850.985 Table 6: Robustness to misspecification on the Ackley function (ϵ=0.2ε=0.2). Trained with Uniform(1,1)Uniform(1,1), evaluated under Beta(α,β)Beta(α,β). Sorted by DKL(Beta∥Uniform)D_KL(Beta\|Uniform). Robustness to Prior Misspecification When training C-ICPE, we sample the prior uniformly, resulting in a meta-learning setting. When evaluating under the same distribution as during training, we consistently observe that C-ICPE-TS achieves good performance. We investigate whether C-ICPE-TS can achieve similar performance when evaluated under a different distribution for sampling priors. Tables 4, 5 and 6 show the expected accuracy and expected stopping time when sampling priors from Beta(α,β)Beta(α,β) distributions with varying parameters at ϵ=0.2ε=0.2 across different dimensionalities, sorted by DKL(Beta∥Uniform)D_KL(Beta\|Uniform). From these tables, we observe that the performance generally remains consistent even as KL divergences increase, even when the Ackley function has more priors to sample. This result demonstrates how C-ICPE generalizes well across priors and maintains robustness to prior misspecification. ϵ=0.1ε=0.1 ϵ=0.2ε=0.2 Binary Search 6D 8D 10D 6D 8D 10D C-ICPE-TS 0.9040.904 [.861,.945] 0.9210.921 [.906,.935] 0.9360.936 [.902,.970] 0.9450.945 [.911,.974] 0.9090.909 [.891,.926] 0.9410.941 [.898,.981] C-ICPE-Uniform 0.9570.957 [.945,.968] 0.9150.915 [.889,.938] 0.8990.899 [.880,.917] 0.8920.892 [.855,.927] 0.8850.885 [.825,.941] 0.9230.923 [.911,.934] ϵε-Best-Arm 6D 8D 10D 6D 8D 10D C-ICPE-TS 0.9040.904 [.866,.941] 0.9170.917 [.902,.933] 0.9150.915 [.905,.925] 0.9140.914 [.899,.927] 0.9150.915 [.890,.938] 0.9050.905 [.885,.925] C-ICPE-Uniform 0.9530.953 [.912,.990] 0.9880.988 [.983,.992] 0.8990.899 [.886,.910] 0.9620.962 [.944,.977] 0.9290.929 [.906,.951] 0.9010.901 [.880,.920] TPE (k=0k=0) 0.0000.000 [.000,.000] 0.0000.000 [.000,.000] 0.0000.000 [.000,.000] 0.0030.003 [.000,.005] 0.0000.000 [.000,.000] 0.0000.000 [.000,.000] TPE (k=1k=1) 0.0030.003 [.000,.005] 0.0000.000 [.000,.000] 0.0010.001 [.000,.002] 0.0030.003 [.000,.005] 0.0000.000 [.000,.000] 0.0010.001 [.000,.002] TPE (k=2k=2) 0.0050.005 [.000,.008] 0.0020.002 [.000,.004] 0.0010.001 [.000,.002] 0.0040.004 [.000,.007] 0.0010.001 [.000,.002] 0.0010.001 [.000,.002] TPE (k=3k=3) 0.0110.011 [.004,.017] 0.0040.004 [.000,.007] 0.0010.001 [.000,.002] 0.0040.004 [.000,.007] 0.0030.003 [.000,.005] 0.0010.001 [.000,.002] GP (k=0k=0) 0.0570.057 [.042,.070] 0.0160.016 [.007,.023] 0.0070.007 [.001,.011] 0.0520.052 [.038,.065] 0.0470.047 [.033,.059] 0.0440.044 [.031,.056] GP (k=1k=1) 0.0980.098 [.079,.116] 0.0300.030 [.019,.040] 0.0090.009 [.003,.014] 0.0920.092 [.073,.109] 0.0930.093 [.075,.110] 0.0750.075 [.058,.091] GP (k=2k=2) 0.1340.134 [.112,.154] 0.0320.032 [.020,.042] 0.0100.010 [.003,.015] 0.1850.185 [.160,.208] 0.1360.136 [.114,.156] 0.1060.106 [.086,.124] GP (k=3k=3) 0.1590.159 [.136,.180] 0.0380.038 [.025,.049] 0.0100.010 [.003,.015] 0.2750.275 [.246,.302] 0.1710.171 [.147,.194] 0.1400.140 [.117,.160] CMA-ES (k=0k=0) 0.0000.000 [.000,.000] 0.0000.000 [.000,.000] 0.0000.000 [.000,.000] 0.0010.001 [.000,.002] 0.0000.000 [.000,.000] 0.0000.000 [.000,.000] CMA-ES (k=1k=1) 0.0020.002 [.000,.004] 0.0000.000 [.000,.000] 0.0000.000 [.000,.000] 0.0020.002 [.000,.004] 0.0000.000 [.000,.000] 0.0000.000 [.000,.000] CMA-ES (k=2k=2) 0.0020.002 [.000,.004] 0.0000.000 [.000,.000] 0.0010.001 [.000,.002] 0.0020.002 [.000,.004] 0.0010.001 [.000,.002] 0.0010.001 [.000,.002] CMA-ES (k=3k=3) 0.0020.002 [.000,.004] 0.0000.000 [.000,.000] 0.0010.001 [.000,.002] 0.0040.004 [.000,.007] 0.0010.001 [.000,.002] 0.0010.001 [.000,.002] Ackley Function 3D 4D 5D 3D 4D 5D C-ICPE-TS 0.9060.906 [.849,.958] 0.8950.895 [.859,.929] 0.9020.902 [.886,.915] 0.9240.924 [.914,.934] 0.9210.921 [.900,.936] 0.8730.873 [.857,.888] C-ICPE-Uniform 0.9120.912 [.901,.924] 0.7420.742 [.601,.884] 0.5700.570 [.533,.607] 0.9050.905 [.875,.932] 0.9060.906 [.889,.922] 0.8320.832 [.748,.913] TPE (k=0k=0) 0.0270.027 [.016,.036] 0.0050.005 [.000,.008] 0.0020.002 [.000,.004] 0.1270.127 [.105,.146] 0.0730.073 [.056,.088] 0.0220.022 [.012,.030] TPE (k=1k=1) 0.0850.085 [.066,.101] 0.0220.022 [.012,.030] 0.0110.011 [.004,.017] 0.2770.277 [.248,.304] 0.1510.151 [.129,.173] 0.0400.040 [.027,.051] TPE (k=2k=2) 0.1580.158 [.135,.180] 0.0550.055 [.040,.068] 0.0210.021 [.011,.029] 0.4220.422 [.391,.452] 0.2770.277 [.249,.304] 0.1070.107 [.087,.125] TPE (k=3k=3) 0.2590.259 [.231,.285] 0.1210.121 [.100,.140] 0.0320.032 [.020,.042] 0.5400.540 [.507,.569] 0.4010.401 [.370,.431] 0.2360.236 [.209,.261] GP (k=0k=0) 0.1830.183 [.158,.206] 0.0580.058 [.043,.071] 0.0310.031 [.019,.041] 0.3570.357 [.326,.385] 0.2270.227 [.200,.251] 0.1060.106 [.086,.124] GP (k=1k=1) 0.2980.298 [.269,.325] 0.1050.105 [.085,.124] 0.0410.041 [.028,.052] 0.5190.519 [.487,.549] 0.3270.327 [.297,.355] 0.1540.154 [.130,.175] GP (k=2k=2) 0.3800.380 [.349,.410] 0.1490.149 [.127,.170] 0.0490.049 [.035,.061] 0.6280.628 [.596,.657] 0.3970.397 [.366,.427] 0.1850.185 [.160,.208] GP (k=3k=3) 0.4370.437 [.405,.467] 0.1720.172 [.148,.194] 0.0480.048 [.035,.061] 0.6970.697 [.668,.725] 0.4550.455 [.423,.484] 0.2210.221 [.195,.246] CMA-ES (k=0k=0) 0.0160.016 [.008,.023] 0.0060.006 [.001,.010] 0.0010.001 [.000,.002] 0.0950.095 [.076,.112] 0.0530.053 [.038,.066] 0.0090.009 [.003,.014] CMA-ES (k=1k=1) 0.0410.041 [.028,.052] 0.0140.014 [.006,.020] 0.0040.004 [.000,.007] 0.1930.193 [.167,.217] 0.1060.106 [.086,.124] 0.0280.028 [.017,.037] CMA-ES (k=2k=2) 0.0880.088 [.070,.105] 0.0440.044 [.030,.056] 0.0200.020 [.011,.028] 0.2770.277 [.249,.304] 0.1800.180 [.156,.203] 0.0770.077 [.059,.092] CMA-ES (k=3k=3) 0.1640.164 [.141,.187] 0.0960.096 [.078,.113] 0.0300.030 [.018,.040] 0.3680.368 [.336,.397] 0.2840.284 [.255,.312] 0.1570.157 [.133,.178] Table 7: Correctness comparison across all problems, dimensions, and ϵε values. We report accuracy with 95% bootstrap confidence intervals.