{"id":"0c40e273-625a-45e4-97c4-6f1ce9a33619","arxiv_id":"2412.13559","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":2,"one_line_summary":"A framework, acquisition function (CMES), and tree-search variant for Bayesian optimization with conditional-expectation feedback, with claimed regret bounds.","lead":"This paper introduces a Bayesian optimization variant where queries return an average of the function under a hidden condition, not the function value itself. It proposes the CMES policy and reports regret bounds and synthetic experiments.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 5.3's sign error in the definition of κt invalidates the instant-regret bound of Theorem 5.6; the central CMES guarantee is unsupported.","rationale":"I read the paper's main theoretical contribution as Theorem 5.6: a sublinear instant-regret guarantee for the CMES policy under conditional-expectation feedback. For that theorem to hold, Lemma 5.3 must provide a valid upper bound on f* - g(a_t). The proof of Lemma 5.3 uses κt as the minimum of the standardized gap; taking a minimum gives a lower envelope, so the claimed lower bound on ν+κ√q is exactly backwards. This is not a matter of disagreement with standard results; it is an internal algebraic error in the submitted proof. The reader's stated weakest assumption (Assumption 2.4) is related: the proof needs some mechanism ensuring f* is not unattainable through indirect queries, but even before reaching that issue, the sign error blocks the regret bound. Theorem 5.7 also has a separate gap (the information-gain bound γ_T is for direct queries, not for the integrated observations actually used), but the Lemma 5.3 issue alone is sufficient to invalidate the central CMES guarantee. The empirical comparisons may still show promise, and a corrected proof could make a revised version viable, but as written the central claim is unsupported. The verdict should remain REJECT; my concern reinforces the reader's rejection rather than changing it.","tokens_in":17172,"tokens_out":10102,"duration_ms":84053,"concrete_test":"Verify Lemma 5.3 algebraically on a two-point query space: set ν(a1)=0, ν(a2)=0.9, q(a1,a1)=q(a2,a2)=1, and lhat_t=1. Compute κt = min{(1-0)/1, (1-0.9)/1} = 0.1 and then ν(a1)+κt√q(a1,a1) = 0.1. Compare this with lhat_t=1: the claimed inequality ν(a1)+κt√q ≥ lhat_t is false. This single arithmetic check determines whether Lemma 5.3's proof step is a harmless typo (if equality/≥ held) or a structural flaw (as written), and therefore whether Theorem 5.6 has a valid proof.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim that CMES achieves sublinear instant regret (Theorem 5.6) rests on Lemma 5.3, and Lemma 5.3's proof contains a direction error. Lemma 5.3 defines κt := min_{a∈A} (lhat_t - ν_{t-1}(a))/√q_{t-1}(a,a), where lhat_t ≥ max f. The proof then asserts ν_{t-1}(a_t) + κt√q_{t-1}(a_t,a_t) ≥ lhat_t. But because κt is a minimum, for every a, (lhat_t - ν_{t-1}(a))/√q_{t-1}(a,a) ≥ κt, so ν_{t-1}(a) + κt√q_{t-1}(a,a) ≤ lhat_t. The inequality is reversed. A two-point query space with ν(a1)=0, ν(a2)=0.9, q=1, lhat=1 gives κt=0.1 and ν(a1)+κt√q=0.1<1, contradicting the proof's first line. Consequently the bound f(x*) - g(a_t) ≤ (κt+ζt)√q_{t-1}(a_t,a_t) is not established, and Theorem 5.6 inherits the gap. The paper states Assumption 2.4 (queryable distributions can concentrate near x*) but never invokes it in this proof; that assumption is precisely what would be needed to ensure f* can be approached by sup over queries, and its absence highlights that the current proof cannot deliver the advertised sublinear regret.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces Indirect Query Bayesian Optimization (IQBO), in which the learner chooses an indirect query a and observes a noisy conditional expectation g(a) = E[f(X) | A = a] rather than a direct value of f. It proposes the Conditional Max-value Entropy Search (CMES) acquisition, a hierarchical multi-resolution variant (CMETS), regret bounds for both settings, and experiments on a Branin benchmark with linear and nonlinear transformations. The abstract also states that the conditional distribution may be unknown and learned from offline data. The central theoretical claim is an instant-regret bound for CMES in Theorem 5.6 and a multi-resolution regret bound in Theorem 5.7.","tokens_in":17523,"tokens_out":21369,"duration_ms":198849,"significance":"The IQBO problem formulation is genuinely useful and covers settings such as aggregated feedback and multi-resolution queries, and the use of Conditional Mean Processes for posterior inference is a natural fit. If the regret analysis were complete, Theorem 5.6 would be a first regret guarantee for BO with conditional-expectation feedback, and the cost-aware analysis in Theorem 5.7 is an interesting extension. The empirical results are suggestive but limited to a single synthetic function and two hand-designed transformations. The significance is currently contingent because the main CMES regret theorem is not established as written: the bound contains an uncontrolled random quantity, and the identifiability assumption that would make the problem solvable is never used in the proof.","major_comments":[{"comment":"The regret bound in Theorem 5.6 depends on kappa_{t*}, where kappa_t is defined as a minimum over a of (f^t_* - nu_{t-1}(a))/sqrt(q_{t-1}(a,a)). This is a data-dependent random quantity, and no upper bound on kappa_{t*} is proved. To claim a sublinear regret guarantee, the authors must show that kappa_{t*} is, with high probability, O(1) or at least o(sqrt(T/rho_T)); otherwise the right-hand side may fail to vanish. The standard GP-UCB/MES proof technique uses a deterministic confidence parameter, whereas here the analogous parameter is random and could be large. In particular, if the query family cannot concentrate near x*, i.e., if sup_a g(a) < f(x*), then the instant regret cannot converge to zero for any policy, so some quantitative version of Assumption 2.4 must enter the argument; currently Assumption 2.4 is stated but never invoked in the proof of Theorem 5.6.","section":"Section 5.1, Theorem 5.6"},{"comment":"The proof bounds the sum over the T selected iterations by a multiple of rho_T, the maximum information gain for T observations, but the algorithm actually runs T' = sum_i k_i iterations. The relevant information gain is I(z_{T'}; f), which is bounded by rho_{T'}, not rho_T. Since rho is nondecreasing in the number of observations, rho_T is generally smaller than rho_{T'}, so the displayed bound is not justified as written. If rho_T is intended to denote the maximum information gain for the full horizon, the notation and the subsequent rate involving T in the denominator need to be reconciled with the fact that T' is the total number of queries.","section":"Section 5.1, proof of Theorem 5.6"},{"comment":"The theoretical analysis begins by assuming that the conditional distribution p(x|a) is known, but the abstract and Algorithm 1 advertise that the conditional distribution can be unknown and learned from offline data. No regret bound or convergence statement is provided for the estimated-CMP setting. This is a mismatch between the stated contribution and the analysis: either the claims should be narrowed to the known-p case, or the analysis should be extended to account for estimation error in the conditional distribution.","section":"Section 5, preamble"}],"minor_comments":[{"comment":"Assumption 2.4 quantifies over \"any epsilon >= 0 and zeta >= 0\"; when epsilon = 0 and zeta < 1, it requires a point mass at x*, which is impossible for continuous conditional distributions. The assumption should be formulated for epsilon > 0 and zeta > 0, or as a limiting statement.","section":"Section 2, Assumption 2.4"},{"comment":"Lemma D.2 states a concentration inequality over all x in X with beta_t = 2 log(|X| pi_t / delta), but X is a continuous compact set and |X| is not finite. A standard discretization argument is needed for the bound to be meaningful.","section":"Appendix D, Lemma D.2"},{"comment":"The definition \"kappa_t = min_{x in A, f^{t*}>f*} gamma_{f^{t*}}(a)\" uses x in A where the variable should be a in A; this should be corrected.","section":"Theorem 5.6, displayed definition of kappa_t"},{"comment":"The displayed formula for the alternative CMES objective contains an apparent typesetting artifact: \"1/2 log[2 pi e (q + sigma^2)]]\" has a stray closing bracket, and the final expression is not fully specified.","section":"Appendix B"},{"comment":"The proof writes \"hat m_t\" where the statement of Lemma 5.3 defines \"hat l_t\"; the notation should be made consistent.","section":"Appendix D, proof of Lemma 5.3"}],"recommendation":"major_revision","confidential_remarks":"The sign-error concern raised in an earlier review of Lemma 5.3 does not actually land: because CMES selects a_t = argmin_a gamma(a), kappa_t equals the ratio at the selected action, making the first inequality in the proof an equality. The real problem is the uncontrolled random kappa_{t*} and the unused Assumption 2.4. If the authors can supply a quantitative bound on kappa_{t*} and properly incorporate an identifiability condition, the central regret claim may be repairable. The empirical evaluation on a single Branin benchmark is thin and should be strengthened if the theoretical gap is closed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the paper introduces a genuinely new BO setting and a sensible acquisition function, but the main regret proof contains a step that is wrong as written. The good news is that the step is fixable: a_t is the minimizer of γ, so the inequality in Lemma 5.3 is actually an equality for the selected query. The stress-test note's counterexample uses the wrong point. That said, the proof needs to say this explicitly, and other weaknesses remain.\n\nThe IQBO formulation — optimizing f from conditional-expectation feedback in a mismatched query space — is real and worth attention. CMES is a clean adaptation of MES to the conditional-mean process, and Lemma 5.1's equivalence to MES/GPUCB on g is useful. The multi-resolution instant-regret bound (Thm 5.7) is separate from CMES and appears to go through; it's basically GP-UCB on f with a bias term δ^4.\n\nSoft spots: the proof of Lemma 5.3 as written claims that for the chosen a_t, ν(a_t)+κ_t√q ≥ lhat follows from the definition of κ_t as a minimum. It doesn't; it follows because a_t is the argmin of γ. Without that sentence, the proof is misleading and a careful reader can find a counterexample if they plug in a non-selected query. This is a minor fix, but it's load-bearing and the current text doesn't have it. Second, Theorem 5.7 doesn't analyze the actual tree-search algorithm (Algorithm 2); it analyzes a simpler deterministic schedule with GP-UCB on f. The tree search with adaptive splitting and cost-weighted acquisition is unproven. Third, the experiments compare against MES, UCB, and EI applied to g, i.e., optimizing the wrong objective; the comparison is not apples-to-apples. A fair baseline would be MES on g with f* samples, which Lemma 5.1 suggests should behave like CMES.\n\nOverall: the paper is worth a serious referee. The setting is novel, the algorithm is sensible, and the main regret proof is salvageable. The tree-search theory and experimental comparison need real work. I would not reject on the sign error alone.\n\nRecommendation: accept for review with major revision. Bring to reading group if someone is working on aggregate feedback BO.","headline":"New BO setting with a fixable proof gap; worth reviewing despite unfair baselines and missing tree-search theory.","tokens_in":18088,"tokens_out":7185,"would_cite":false,"duration_ms":63495,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Bayesian optimization still works when queries are indirect and feedback is only an average: the paper's CMES policy carries a sublinear instant-regret bound.","keywords":["indirect query Bayesian optimization","conditional mean process","max-value entropy search","Gaussian process","multi-resolution queries","regret bounds","integrated feedback","hierarchical search"],"falsifier":"Fix a query family that violates Assumption 2.4, for instance all conditional distributions are Gaussians with variance at least $\\delta^2$ and means restricted to a compact set whose distance from $x^*$ is positive, so $\\max_a g(a) < f(x^*)$ by construction. Then compute $\\max_a g(a)$ by quadrature or closed form for a known $f$ and run CMES: the empirical instant regret cannot go below $f(x^*) - \\max_a g(a) > 0$ for any number of iterations, showing that the sublinear-regret conclusion depends exactly on that assumption. The paper's Fig. 2 with $\\delta=0.5$ is the same phenomenon.","tokens_in":16964,"feed_emoji":"🎯","tokens_out":11718,"duration_ms":107211,"temperature":0.7,"pith_summary":"The paper introduces Indirect Query Bayesian Optimization (IQBO), a setting in which the optimizer never evaluates the unknown function $f$ directly, but only observes noisy conditional averages $g(a)=\\mathbb{E}[f(X)\\mid A=a]$ chosen through a query $a$ in a different space. It proposes the Conditional Max-Value Entropy Search (CMES) acquisition, which selects the query whose integrated observation carries the most mutual information about the value $f^*=f(x^*)$ at the true optimum. The central claim is that CMES has sublinear instant regret (Theorem 5.6), and that a hierarchical tree version with cost-weighted multi-resolution queries keeps a matching regret bound while saving budget (Theorem 5.7). If the claim is right, Bayesian optimization can be applied to aggregated, privacy-restricted, or hardware-limited feedback, and the mismatch between where we query and where we want to optimize does not have to be a barrier.","feed_headline":"Indirect queries can still find the optimum with a proven regret bound","feed_subtitle":"The CMES policy proves sublinear regret when feedback is only a conditional average of the target function.","key_machinery":"The central object is the Conditional Max-Value Entropy Search acquisition function, whose one-sample approximation is $$I(z; f^* \\mid a, D_t) \\approx \\frac{1}{|\\mathcal{F}_t^*|}\\sum_{f_t^*\\in\\mathcal{F}_t^*} h\\!\\left(\\frac{f_t^* - \\nu_{t-1}(a)}{\\sqrt{q_{t-1}(a,a)}}\\right),$$ where $h(\\alpha)=\\alpha\\phi(\\alpha)/(2\\Phi(\\alpha))-\\log\\Phi(\\alpha)$, $\\nu_{t-1}$ and $q_{t-1}$ are the posterior mean and covariance of the conditional-mean process $g$, and $\\mathcal{F}_t^*$ is a set of samples of the optimal value $f^*=f(x^*)$ drawn from the posterior of $f$. Maximizing this quantity selects the query whose observation most reduces entropy about the optimum of the true target function, using the posterior of $g$ for the query decision and the posterior of $f$ for the objective. The multi-resolution tree search modifies the same rule to $\\arg\\max_{a\\in\\mathcal{A}_t} I(z;f^*\\mid a,D_{t-1})/\\lambda_{l(a)}$, i.e., information gain per unit resolution cost, with the space partitioned by a $K$-ary tree.","core_discovery":"The paper's central claim is that the query-space/target-space mismatch can be overcome by simultaneously maintaining a Gaussian process posterior for $f$ on $\\mathcal{X}$ and a conditional-mean-process posterior for $g(a)$ on $\\mathcal{A}$. CMES then chooses $a_t$ maximizing approximate mutual information $I(z; f^* \\mid a, D_{t-1})$, with $f^*$ samples drawn from the posterior of $f$; Lemma 5.1 shows that with a single $f^*$ sample this policy coincides with Max-Value Entropy Search, entropy search with threshold $f^*$, and GP-UCB applied to $g$, which lets the proof follow established GP-UCB concentration arguments. Theorem 5.6 bounds the instant regret $f(x^*) - \\max_{t\\le T'} g(a_t)$ by $\\sqrt{C\\rho_T/T}\\,(\\kappa_{t^*}+\\zeta_T)$ with high probability, where $\\rho_T$ is the maximum mutual information between $T$ indirect observations and $f$. Theorem 5.7 addresses the budgeted multi-resolution case: with a deterministic decreasing resolution schedule and GP-UCB location selection, instant regret is $O\\big(\\sqrt{(\\beta_T\\gamma_T + \\sum_{t=1}^T \\delta_t^4)/T}\\big)$, matching the rate of direct queries when $\\delta_t^2 = O(t^{-1/2}(\\log t)^{d/2})$ for a Gaussian kernel; the proof splits the regret into a direct-query term and a Taylor-expansion smoothing error $O(\\delta_t^2)$. This gives regret guarantees for a Bayesian optimization setting that previously had none.","pith_inferences":["Beyond the paper: because the instant regret is measured against the best integrated value $\\max_t g(a_t)$, not against the best direct value $f(x^*)$, the practical conclusion is conditional on Assumption 2.4; if every available query averages over a region that misses $x^*$, a floor $f(x^*) - \\max_a g(a) > 0$ remains no matter how good the policy is.","The paper's theoretical analysis assumes $p(x\\mid a)$ is known even though the framework allows learning it; an immediate testable extension is to add a kernel-embedding estimation-error term and derive regret for the learned-conditional case.","The information-per-unit-cost criterion used in CMETS is a general principle: any surrogate model that can output predictive means and variances could be substituted for the Gaussian process, so the same tree schedule might carry over to neural or ensemble surrogates.","The multi-resolution theorem implies a concrete practical recipe, start coarse, refine on a proven schedule, and pay far less than the direct-query cost, that could be validated on real aggregated data such as satellite imagery or disease-incidence mapping, two applications the paper names."],"forward_implications":["With known conditional distributions, CMES drives instant regret $f(x^*) - \\max_t g(a_t)$ toward zero as the query budget grows, so an agent can effectively optimize $f$ while only ever observing averages over $\\mathcal{X}$.","When $p(x\\mid a)$ is unknown, the conditional-mean-process posterior update consumes offline paired samples, so CMES remains implementable; the paper's regret theorems assume $p$ is known, leaving the estimated case as an open extension.","In the multi-resolution setting, query windows can shrink slowly while the instant regret stays at the direct-query rate, translating resolution into cost savings that grow with dimension.","In the reported Branin experiments, CMES outperforms MES, UCB, and EI on both simple and instant regret, and the hierarchical CMETS outperforms flat and multi-fidelity baselines under a fixed cost budget.","Simple regret in the target space is not covered by the main bound; the paper notes in Remark 5.4 that bounding $f(x^*)-f(x_t)$ would require additional assumptions linking recommended points to queries."],"supporting_citations":[{"why":"It supplies the Conditional Mean Process framework used to update the posterior of $f$ from conditional-mean observations, which is the core inference step of the paper's algorithms.","marker":"Chau, Bouabid, and Sejdinovic 2021"},{"why":"It defines Max-Value Entropy Search and the equivalence to GP-UCB that Lemma 5.1 and Theorem 5.6 reuse for the CMES policy.","marker":"Wang and Jegelka 2017"},{"why":"It provides the Gaussian-process concentration inequality and the maximal-information-gain quantities $\\rho_T$ and $\\gamma_T$ on which both regret theorems rely.","marker":"Srinivas et al. 2012"},{"why":"It supplies the proof route that turns entropy-search-style policies into GP-UCB-style regret bounds through sampled optimal values $f^*$.","marker":"Wang, Zhou, and Jegelka 2016"},{"why":"It introduces the multi-fidelity max-value entropy search that motivates the hierarchical tree algorithm and serves as a baseline in the budgeted experiments.","marker":"Takeno et al. 2020"},{"why":"It is the closest prior setting with aggregated feedback in Gaussian-process bandits, against which IQBO defines its new conditional-expectation feedback.","marker":"Zhang, Tsuchida, and Ong 2022"}],"fun_headline_variants":["Bayesian optimization with indirect queries gets first regret bound","CMES: proven regret when feedback is a conditional average","Indirect feedback no longer blocks provable Bayesian optimization","Sublinear regret guaranteed for conditional-expectation feedback","Optimizing via indirect queries now comes with a regret guarantee"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The results need some indirect query whose conditional distribution can be made to concentrate almost all of its mass arbitrarily close to the true optimum $x^*$, because otherwise averaged feedback never reveals where $f$ is best and the regret cannot vanish.","fun_headline_variants_meta":{"raw":{"variants":["Bayesian optimization with indirect queries gets first regret bound","CMES: proven regret when feedback is a conditional average","Indirect feedback no longer blocks provable Bayesian optimization","Sublinear regret guaranteed for conditional-expectation feedback","Optimizing via indirect queries now comes with a regret guarantee"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000148,"raw_usage":{"total_tokens":1225,"prompt_tokens":1016,"completion_tokens":209,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":632,"completion_tokens_details":{"reasoning_tokens":131}},"tokens_in":632,"tokens_out":209,"duration_ms":3037,"temperature":1.0,"reasoning_tokens":131,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T13:02:30.034237+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Fix a query family that violates Assumption 2.4, for instance all conditional distributions are Gaussians with variance at least $\\delta^2$ and means restricted to a compact set whose distance from $x^*$ is positive, so $\\max_a g(a) < f(x^*)$ by construction. Then compute $\\max_a g(a)$ by quadrature or closed form for a known $f$ and run CMES: the empirical instant regret cannot go below $f(x^*) - \\max_a g(a) > 0$ for any number of iterations, showing that the sublinear-regret conclusion depends exactly on that assumption. The paper's Fig. 2 with $\\delta=0.5$ is the same phenomenon.","supporting_citations":[{"cited_title":"Deconditional Downscaling with Gaussian Processes","cited_arxiv_id":null,"evidence_quote":"It supplies the Conditional Mean Process framework used to update the posterior of $f$ from conditional-mean observations, which is the core inference step of the paper's algorithms."},{"cited_title":"Max-value entropy search for efficient bayesian optimization","cited_arxiv_id":null,"evidence_quote":"It defines Max-Value Entropy Search and the equivalence to GP-UCB that Lemma 5.1 and Theorem 5.6 reuse for the CMES policy."},{"cited_title":"Optimization as estimation with gaussian processes in bandit settings","cited_arxiv_id":null,"evidence_quote":"It supplies the proof route that turns entropy-search-style policies into GP-UCB-style regret bounds through sampled optimal values $f^*$."},{"cited_title":"Multi-fidelity bayesian optimization with max-value entropy search and its parallelization","cited_arxiv_id":null,"evidence_quote":"It introduces the multi-fidelity max-value entropy search that motivates the hierarchical tree algorithm and serves as a baseline in the budgeted experiments."},{"cited_title":"Gaussian process bandits with aggregated feedback","cited_arxiv_id":null,"evidence_quote":"It is the closest prior setting with aggregated feedback in Gaussian-process bandits, against which IQBO defines its new conditional-expectation feedback."}],"review_version":1}