UC Santa Barbara

This thesis studies the stochastic root-finding problem, which consists of estimating the point x∗ that solves the equation h(x∗) = 0, where the function h : (0,1) → R is learned via a stochastic simulator (oracle). Instead of focusing on modeling h(·), we develop statistical methodologies that directly infer x∗ following a fully Bayesian approach. To do so, we investigate procedures that generalize the Probabilistic Bisection Algorithm (PBA) first introduced in Horstein (1963). The PBA is a one-dimensional stochastic root-finding routine which builds an explicit Bayesian representation (i.e., a posterior density) for x∗ based on the history of noisy function evaluations and sampling locations. The PBA starts by assuming that x∗ is the realized value of an absolutely continuous random variable, X∗ ∼ g0, with prior density g0. Then, it recursively updates a posterior, gn, leveraging the information provided by the signs (positive/negative) of the noisy function evaluations — which inform the direction where x∗ is located with respect to a given location, x—. Due to observational noise, the oracle responses are correct only with probability p(x). Waeber et al. (2013) showed that sampling at the median of gn is an optimal sampling strategy and established exponential convergence of the posterior gn to a Dirac mass at the true x∗ under the very restrictive assumption that the probability of correct response p(x) is known and constant for all x; however, in the most general and practical settings the latter condition no longer holds and the only way to implement the PBA is to estimate p(·).

In the first part of this thesis, we state the Generalized PBA (G-PBA), where the above assumption is relaxed to the case where the sampling distribution of the oracle is unknown and location-dependent. Namely, as in standard PBA, we rely on a knowledge state to approximate the posterior of the root location. To implement the corresponding Bayesian updating, we also carry out inference of p(·). To this end we utilize batched querying in combination with a variety of frequentist and Bayesian estimators based on majority vote, as well as the underlying functional responses, if available. For guiding sampling selection we propose two families of sampling policies: batched Information Di- rected Sampling and Randomized Quantile Sampling, which is a reminiscent of Thompson Sampling and a generalization of the median sampling as in classical PBA. The latter leads to the first main conclusion: the G-PBA is able to efficiently learn p(·) and X∗ simultaneously.

In the second part of this thesis, we propose to leverage the spatial structure of a typical oracle by constructing a non-parametric statistical surrogate for p(·) based on binomial regression. The latter leads to the second main conclusion: surrogate modeling allows to determine the batch size for querying the oracle adaptively as a function of the estimated predictive uncertainty of p(·).

In the last part of this thesis, we present extensive numerical experiments in order to evaluate our sampling strategies (information-based or randomized). In particular we demonstrate the efficiency of randomized quantile sampling for balancing the ex- ploration/exploitation component; moreover, we show that spatial surrogate modeling results in significant gains relative to the local estimators, as quantified by the improved quality of the resulting root estimates (namely lower absolute residuals, narrower credible intervals and dramatically higher probability coverage). Our work is motivated by the root-finding sub-routine in pricing of Bermudan financial derivatives, illustrated in the last section of this thesis.