Information directed sampling for Stochastic Root Finding
S. Rodriguez, Michael Ludkovski · 2015
The Stochastic Root-Finding Problem (SRFP) consists of finding the root χ* of a noisy function. To discover χ*, an agent sequentially queries an oracle whether the root lies rightward or leftward of a given measurement location χ. The oracle answers truthfully with probability p(χ). The Probabilistic Bisection Algorithm (PBA) pinpoints the root by incorporating the knowledge acquired in oracle replies via Bayesian updating. A common sampling strategy is to myopically maximize the mutual information criterion, known as Information Directed Sampling (IDS). We investigate versions of IDS in the setting of a non-parametric p(χ), as well as when p(·) is not known and must be learned in parallel. An application of our approach to optimal stopping problems, where the goal is to find the root of a timing-value function, is also presented.