REVIEW 3 major objections 5 minor 27 references
Indirect Query Bayesian Optimization with Integrated Feedback
T0 review · 3 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash
Pith's one-line read 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.
desk verdict New BO setting with a fixable proof gap; worth reviewing despite unfair baselines and missing tree-search theory. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (3)
- [Section 5.1, Theorem 5.6] 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 5.1, proof of Theorem 5.6] 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 5, preamble] 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.
minor comments (5)
- [Section 2, Assumption 2.4] 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.
- [Appendix D, Lemma D.2] 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.
- [Theorem 5.6, displayed definition of kappa_t] 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.
- [Appendix B] 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.
- [Appendix D, proof of Lemma 5.3] The proof writes "hat m_t" where the statement of Lemma 5.3 defines "hat l_t"; the notation should be made consistent.
Circularity Check
No load-bearing circularity: the CMES regret analysis applies known GPUCB/MES machinery to the CMP posterior, and the only author-overlap citation is non-load-bearing.
full rationale
The derivation chain is not circular. CMES is defined as an information-acquisition rule, not as a fitted estimator, and no constant in the regret bound is fitted to the data whose regret is reported. Lemma 5.1 explicitly reduces CMES to MES, EST, and GPUCB on the induced conditional-mean process g, and Theorem 5.6 then follows the standard information-theoretic proof technique of Srinivas et al. (2012) and Wang and Jegelka (2017). This is a transfer of known machinery to a new observation model, not a prediction that is equivalent to its own input by construction. Section 5.2 similarly applies the standard GP-UCB regret decomposition with a Taylor-expansion bias term. The only citation to prior work sharing authors is the Conditional Mean Process framework of Chau, Bouabid, and Sejdinovic (2021), used for posterior inference; that result is externally published, general-purpose, and does not encode the present regret claims or forbid alternative inference schemes, so it is not load-bearing. No fitted parameter is renamed as a prediction. Two correctness concerns outside the circularity remit should be flagged. Lemma 5.3 defines kappa_t as a minimum over a of (lhat_t - nu_{t-1}(a))/sqrt(q_{t-1}(a,a)), yet the proof's first line asserts nu_{t-1}(a_t) + kappa_t sqrt(q_{t-1}(a_t,a_t)) >= lhat_t; with a minimum the inequality is reversed, so the instant-regret bound of Theorem 5.6 is not established as written. Also, Assumption 2.4 is stated but never invoked in the CMES regret proof, so the condition that indirect queries can concentrate near x* is left unused. These are mathematical gaps, not circular steps.
Assumptions & free parameters
free parameters (2)
- GP hyperparameters (kernel lengthscales, noise variance sigma^2) =
not specified; presumably optimized or set by hand in experiments
- Cost function lambda(a) in Algorithm 2 =
lambda(a) = 0.5 * log2(1/d(a)) in experiments
assumptions (6)
- domain assumption f is a sample from a zero-mean Gaussian process with known covariance k (Assumption 2.3)
- domain assumption The conditional distribution p(x|a) is known for the regret analysis (Section 5, first sentence)
- domain assumption For any epsilon, zeta >= 0 there exists a query a with p(x in [x*-epsilon, x*+epsilon] | a) >= 1 - zeta (Assumption 2.4)
- domain assumption f has bounded second derivative Tr(grad^2 f) <= 2M, and sup_t E||eta_t/delta_t||^3 <= C (Theorem 5.7)
- standard math Concentration inequalities for GP posteriors (Lemma 5.2, Lemma D.2) hold, following Srinivas et al. 2012
- standard math CMP posterior inference formulas in Appendix A are correct (from Chau, Bouabid, and Sejdinovic 2021)
Cite this review
Pith. "Pith review of Indirect Query Bayesian Optimization with Integrated Feedback." pith.science (2026). https://pith.science/paper/5VGFBNS6
@misc{pith2026241213559,
author = {Pith},
title = {Pith review of: Indirect Query Bayesian Optimization with Integrated Feedback},
year = {2026},
howpublished = {\url{https://pith.science/paper/5VGFBNS6}},
note = {Machine review of arXiv:2412.13559}
}
abstract
We develop the framework of Indirect Query Bayesian Optimization (IQBO), a new class of Bayesian optimization problems where the integrated feedback is given via a conditional expectation of the unknown function $f$ to be optimized. The underlying conditional distribution can be unknown and learned from data. The goal is to find the global optimum of $f$ by adaptively querying and observing in the space transformed by the conditional distribution. This is motivated by real-world applications where one cannot access direct feedback due to privacy, hardware or computational constraints. We propose the Conditional Max-Value Entropy Search (CMES) acquisition function to address this novel setting, and propose a hierarchical search algorithm with multi-resolution feedback to improve computational efficiency. We show regret bounds for our proposed methods and demonstrate the effectiveness of our approaches on simulated optimization tasks.
Figures
Reference graph
Works this paper leans on
-
[1]
Multi-Step Budgeted Bayesian Optimization with Unknown Evaluation Costs
Raul Astudillo, Daniel R. Jiang, Maximilian Balandat, Eytan Bakshy, and Peter I. Frazier. Multi-step budgeted bayesian optimization with unknown evaluation costs, 2021. URL https://arxiv.org/abs/2111.06537
work page Pith review arXiv 2021
-
[2]
Stochastic bandits for multi-platform budget optimization in online advertising
Vashist Avadhanula, Riccardo Colini Baldeschi, Stefano Leonardi, Karthik Abinav Sankararaman, and Okke Schrijvers. Stochastic bandits for multi-platform budget optimization in online advertising. In Proceedings of the Web Conference 2021 , WWW '21, pages 2805--2817, 2021
work page 2021
-
[3]
On Multi-Armed Bandit Designs for Dose-Finding Trials
Maryam Aziz, Emilie Kaufmann, and Marie-Karelle Riviere. On Multi-Armed Bandit Designs for Dose-Finding Trials . Journal of Machine Learning Research, 22 0 (14): 0 1--38, 2021
work page 2021
-
[4]
Deconditional Downscaling with Gaussian Processes
Siu Lun Chau, Shahine Bouabid, and Dino Sejdinovic. Deconditional Downscaling with Gaussian Processes . In Advances in Neural Information Processing Systems , volume 34, pages 17813--17825, 2021
work page 2021
-
[5]
Active learning of conditional mean embeddings via bayesian optimisation
Sayak Ray Chowdhury, Rafael Oliveira, and Fabio Ramos. Active learning of conditional mean embeddings via bayesian optimisation. In Conference on Uncertainty in Artificial Intelligence, pages 1119--1128. PMLR, 2020
work page 2020
-
[6]
Sequential experimental design for transductive linear bandits, 2019
Tanner Fiez, Lalit Jain, Kevin Jamieson, and Lillian Ratliff. Sequential experimental design for transductive linear bandits, 2019. URL https://arxiv.org/abs/1906.08399
arXiv 2019
-
[7]
Robust Policy Search for Robot Navigation
Javier Garcia-Barcos and Ruben Martinez-Cantin. Robust policy search for robot navigation with stochastic meta-policies, 2020. URL https://arxiv.org/abs/2003.01000
work page Pith review arXiv 2020
-
[8]
Bayesian Optimization
Roman Garnett. Bayesian Optimization . Cambridge University Press, 2023
2023
Show all 27 references
-
[9]
Deep IV : A flexible approach for counterfactual prediction
Jason Hartford, Greg Lewis, Kevin Leyton-Brown, and Matt Taddy. Deep IV : A flexible approach for counterfactual prediction. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Lea...
2017
-
[10]
Entropy search for information-efficient global optimization
Philipp Hennig and Christian J Schuler. Entropy search for information-efficient global optimization. Journal of Machine Learning Research, 13 0 (6), 2012
2012
-
[11]
Predictive Entropy Search for Efficient Global Optimization of Black -box Functions
José Miguel Hernández-Lobato, Matthew W Hoffman, and Zoubin Ghahramani. Predictive Entropy Search for Efficient Global Optimization of Black -box Functions . In Advances in Neural Information Processing Systems , volume 27, 2014
2014
-
[12]
Gaussian process bandit optimisation with multi-fidelity evaluations
Kirthevasan Kandasamy, Gautam Dasarathy, Junier B Oliva, Jeff Schneider, and Barnab \'a s P \'o czos. Gaussian process bandit optimisation with multi-fidelity evaluations. Advances in neural information processing systems, 29, 2016
2016
-
[13]
Multi-fidelity bayesian optimisation with continuous approximations, 2017
Kirthevasan Kandasamy, Gautam Dasarathy, Jeff Schneider, and Barnabas Poczos. Multi-fidelity bayesian optimisation with continuous approximations, 2017. URL https://arxiv.org/abs/1703.06240
2017 arXiv
-
[14]
Linear partial monitoring for sequential decision-making: Algorithms, regret bounds and applications, 2023
Johannes Kirschner, Tor Lattimore, and Andreas Krause. Linear partial monitoring for sequential decision-making: Algorithms, regret bounds and applications, 2023. URL https://arxiv.org/abs/2302.03683
2023 arXiv
-
[15]
Variational Learning on Aggregate Outputs with Gaussian Processes
Ho Chung Law, Dino Sejdinovic, Ewan Cameron, Tim Lucas, Seth Flaxman, Katherine Battle, and Kenji Fukumizu. Variational Learning on Aggregate Outputs with Gaussian Processes . In Advances in Neural Information Processing Systems , volume 31, 2018
2018
-
[16]
Cost-aware bayesian optimization, 2020
Eric Hans Lee, Valerio Perrone, Cedric Archambeau, and Matthias Seeger. Cost-aware bayesian optimization, 2020. URL https://arxiv.org/abs/2003.10870
2020 arXiv
-
[17]
Experimental design for linear functionals in reproducing kernel hilbert spaces, 2023
Mojmír Mutný and Andreas Krause. Experimental design for linear functionals in reproducing kernel hilbert spaces, 2023. URL https://arxiv.org/abs/2205.13627
2023 arXiv
-
[18]
Bayesian optimisation under uncertain inputs, 2019
Rafael Oliveira, Lionel Ott, and Fabio Ramos. Bayesian optimisation under uncertain inputs, 2019. URL https://arxiv.org/abs/1902.07908
2019 arXiv
-
[19]
Multi-fidelity black-box optimization with hierarchical partitions
Rajat Sen, Kirthevasan Kandasamy, and Sanjay Shakkottai. Multi-fidelity black-box optimization with hierarchical partitions. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Le...
2018
-
[20]
Srinivas, A
N. Srinivas, A. Krause, S. M. Kakade, and M. W. Seeger. GPUCB : Information - Theoretic Regret Bounds for Gaussian Process Optimization in the Bandit Setting . IEEE Transactions on Information Theory, 58 0 (5): 0 3250--3265, May 2012
2012
-
[21]
Accelerating B ayesian optimization for biological sequence design with denoising autoencoders
Samuel Stanton, Wesley Maddox, Nate Gruver, Phillip Maffettone, Emily Delaney, Peyton Greenside, and Andrew Gordon Wilson. Accelerating B ayesian optimization for biological sequence design with denoising autoencoders. In International Conference on Machine Learning, pages 204...
2022
-
[22]
Multi-fidelity bayesian optimization with max-value entropy search and its parallelization
Shion Takeno, Hitoshi Fukuoka, Yuhki Tsukada, Toshiyuki Koyama, Motoki Shiga, Ichiro Takeuchi, and Masayuki Karasuyama. Multi-fidelity bayesian optimization with max-value entropy search and its parallelization. In International Conference on Machine Learning, pages 9334--9345, 2020
2020
-
[23]
Max-value entropy search for efficient bayesian optimization
Zi Wang and Stefanie Jegelka. Max-value entropy search for efficient bayesian optimization. In International Conference on Machine Learning, pages 3627--3635. PMLR, 2017
2017
-
[24]
Optimization as estimation with gaussian processes in bandit settings
Zi Wang, Bolei Zhou, and Stefanie Jegelka. Optimization as estimation with gaussian processes in bandit settings. In Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, pages 1022--1031, 2016
2016
-
[25]
Hyperparameter optimization for machine learning models based on bayesian optimization
Jia Wu, Xiu-Yun Chen, Hao Zhang, Li-Dong Xiong, Hang Lei, and Si-Hao Deng. Hyperparameter optimization for machine learning models based on bayesian optimization. Journal of Electronic Science and Technology, 17 0 (1): 0 26--40, 2019 a
2019
-
[26]
Frazier, and Andrew Gordon Wilson
Jian Wu, Saul Toscano-Palmerin, Peter I. Frazier, and Andrew Gordon Wilson. Practical multi-fidelity bayesian optimization for hyperparameter tuning, 2019 b . URL https://arxiv.org/abs/1903.04703
2019 arXiv
-
[27]
Gaussian process bandits with aggregated feedback
Mengyan Zhang, Russell Tsuchida, and Cheng Soon Ong. Gaussian process bandits with aggregated feedback. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 9074--9081, 2022
2022
Reviewed August 11, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.