Practical Nonparametric Sampling Strategies for Quantile-Based Ordinal Optimization

Dongwook Shin (), Mark Broadie () and Assaf Zeevi ()
Additional contact information
Dongwook Shin: School of Business and Management, Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong
Mark Broadie: Graduate School of Business, Columbia University, New York, New York 10025
Assaf Zeevi: Graduate School of Business, Columbia University, New York, New York 10025

INFORMS Journal on Computing, 2022, vol. 34, issue 2, 752-768

Abstract: Given a finite number of stochastic systems, the goal of our problem is to dynamically allocate a finite sampling budget to maximize the probability of selecting the “best” system. Systems are encoded with the probability distributions that govern sample observations, which are unknown and only assumed to belong to a broad family of distributions that need not admit any parametric representation. The best system is defined as the one with the highest quantile value. The objective of maximizing the probability of selecting this best system is not analytically tractable. In lieu of that, we use the rate function for the probability of error relying on large deviations theory. Our point of departure is an algorithm that naively combines sequential estimation and myopic optimization. This algorithm is shown to be asymptotically optimal; however, it exhibits poor finite-time performance and does not lead itself to implementation in settings with a large number of systems. To address this, we propose practically implementable variants that retain the asymptotic performance of the former while dramatically improving its finite-time performance.

Keywords: quantile; ordinal optimization; tractable procedures; large deviations theory (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2021.1071 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:34:y:2022:i:2:p:752-768

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().