{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:27:09Z","timestamp":1750220829632,"version":"3.41.0"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2020,1,31]],"date-time":"2020-01-31T00:00:00Z","timestamp":1580428800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003141","name":"Consejo Nacional de Ciencia y Tecnolog\u00eda","doi-asserted-by":"crossref","award":["CONACYT-216011"],"award-info":[{"award-number":["CONACYT-216011"]}],"id":[{"id":"10.13039\/501100003141","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1521743"],"award-info":[{"award-number":["DMS-1521743"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Model. Comput. Simul."],"published-print":{"date-parts":[[2020,1,31]]},"abstract":"<jats:p>We consider numerical schemes for root finding of noisy responses through generalizing the Probabilistic Bisection Algorithm (PBA) to the more practical context where the sampling distribution is unknown and location dependent. As in standard PBA, we rely on a knowledge state for the approximate posterior of the root location. To implement the corresponding Bayesian updating, we also carry out inference of oracle accuracy, namely learning the probability of the correct response. 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 investigate both entropy-directed sampling and quantile sampling. Our numerical experiments show that these strategies perform quite differently; in particular, we demonstrate the efficiency of randomized quantile sampling, which is reminiscent of Thompson sampling. Our work is motivated by the root-finding subroutine in pricing of Bermudan financial derivatives, illustrated in the last section of the article.<\/jats:p>","DOI":"10.1145\/3355607","type":"journal-article","created":{"date-parts":[[2020,2,5]],"date-time":"2020-02-05T10:48:48Z","timestamp":1580899728000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Generalized Probabilistic Bisection for Stochastic Root Finding"],"prefix":"10.1145","volume":"30","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4126-8607","authenticated-orcid":false,"given":"Sergio","family":"Rodriguez","sequence":"first","affiliation":[{"name":"University of California, Santa Barbara, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Ludkovski","sequence":"additional","affiliation":[{"name":"University of California, Santa Barbara, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,2,5]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1137\/141000749"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1007\/s11222-011-9241-4"},{"volume-title":"Stochastic Approximation and Its Applications","author":"Chen Han-Fu","key":"e_1_2_1_3_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1080\/00401706.2013.860918"},{"volume-title":"Statistical Method in Biological Assay. Charles Griffin 8 Co","author":"Finney David John","key":"e_1_2_1_5_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1287\/moor.2018.0938"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1137\/140980089"},{"key":"e_1_2_1_8_1","article-title":"Entropy search for information-efficient global optimization","author":"Hennig Philipp","year":"2012","journal-title":"Journal of Machine Learning Research 13"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1239\/jap\/1331216837"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1080\/00224065.2002.11980168"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.21314\/JCF.2018.347"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1080\/00401706.1994.10485401"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1145\/1921598.1921603"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1198\/004017008000000541"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics","volume":"9","author":"Riihim\u00e4ki Jaakko","year":"2010"},{"volume-title":"Probabilistic bisection with spatial metamodels. arXiv preprint arXiv:1807.00095","year":"2018","author":"Rodriguez Sergio","key":"e_1_2_1_16_1"},{"key":"e_1_2_1_17_1","first-page":"1","article-title":"An information-theoretic analysis of Thompson sampling","volume":"17","author":"Russo Daniel","year":"2016","journal-title":"Journal of Machine Learning Research"},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.1007\/978-1-4757-1862-1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1137\/120861898"}],"container-title":["ACM Transactions on Modeling and Computer Simulation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3355607","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3355607","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3355607","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:13:29Z","timestamp":1750202009000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3355607"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,31]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,1,31]]}},"alternative-id":["10.1145\/3355607"],"URL":"https:\/\/doi.org\/10.1145\/3355607","relation":{},"ISSN":["1049-3301","1558-1195"],"issn-type":[{"type":"print","value":"1049-3301"},{"type":"electronic","value":"1558-1195"}],"subject":[],"published":{"date-parts":[[2020,1,31]]},"assertion":[{"value":"2017-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-02-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}