IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v34y2022i2p752-768.html
   My bibliography  Save this article

Practical Nonparametric Sampling Strategies for Quantile-Based Ordinal Optimization

Author

Listed:
  • 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)

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.

Suggested Citation

  • Dongwook Shin & Mark Broadie & Assaf Zeevi, 2022. "Practical Nonparametric Sampling Strategies for Quantile-Based Ordinal Optimization," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 752-768, March.
    • Handle: RePEc:inm:orijoc:v:34:y:2022:i:2:p:752-768
    DOI: 10.1287/ijoc.2021.1071
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2021.1071
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2021.1071?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Yijie Peng & Chun-Hung Chen & Michael C. Fu & Jian-Qiang Hu & Ilya O. Ryzhov, 2021. "Efficient Sampling Allocation Procedures for Optimal Quantile Selection," INFORMS Journal on Computing, INFORMS, vol. 33(1), pages 230-245, January.
    2. Batur, D. & Choobineh, F., 2010. "A quantile-based approach to system selection," European Journal of Operational Research, Elsevier, vol. 202(3), pages 764-772, May.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Zhongshun Shi & Yijie Peng & Leyuan Shi & Chun-Hung Chen & Michael C. Fu, 2022. "Dynamic Sampling Allocation Under Finite Simulation Budget for Feasibility Determination," INFORMS Journal on Computing, INFORMS, vol. 34(1), pages 557-568, January.
    2. Cheng, Zhenxia & Luo, Jun & Wu, Ruijing, 2023. "On the finite-sample statistical validity of adaptive fully sequential procedures," European Journal of Operational Research, Elsevier, vol. 307(1), pages 266-278.
    3. J P C Kleijnen & W C M van Beers, 2013. "Monotonicity-preserving bootstrapped Kriging metamodels for expensive simulations," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 64(5), pages 708-717, May.
    4. Chang, Kuo-Hao, 2015. "A direct search method for unconstrained quantile-based simulation optimization," European Journal of Operational Research, Elsevier, vol. 246(2), pages 487-495.
    5. Gabriella Dellino & Jack P. C. Kleijnen & Carlo Meloni, 2012. "Robust Optimization in Simulation: Taguchi and Krige Combined," INFORMS Journal on Computing, INFORMS, vol. 24(3), pages 471-484, August.
    6. Kleijnen, Jack P.C. & Pierreval, Henri & Zhang, Jin, 2011. "Methodology for determining the acceptability of system designs in uncertain environments," European Journal of Operational Research, Elsevier, vol. 209(2), pages 176-183, March.
    7. Meloni, Carlo & Pranzo, Marco & Samà, Marcella, 2022. "Evaluation of VaR and CVaR for the makespan in interval valued blocking job shops," International Journal of Production Economics, Elsevier, vol. 247(C).
    8. Tsai, Shing Chih & Chu, I-Hao, 2012. "Controlled multistage selection procedures for comparison with a standard," European Journal of Operational Research, Elsevier, vol. 223(3), pages 709-721.
    9. Saurabh Bansal & Genaro J. Gutierrez, 2020. "Estimating Uncertainties Using Judgmental Forecasts with Expert Heterogeneity," Operations Research, INFORMS, vol. 68(2), pages 363-380, March.
    10. Demet Batur & F. Fred Choobineh, 2021. "Selecting the Best Alternative Based on Its Quantile," INFORMS Journal on Computing, INFORMS, vol. 33(2), pages 657-671, May.
    11. Yijie Peng & Chun-Hung Chen & Michael C. Fu & Jian-Qiang Hu & Ilya O. Ryzhov, 2021. "Efficient Sampling Allocation Procedures for Optimal Quantile Selection," INFORMS Journal on Computing, INFORMS, vol. 33(1), pages 230-245, January.
    12. Batur, D. & Choobineh, F., 2012. "Stochastic dominance based comparison for system selection," European Journal of Operational Research, Elsevier, vol. 220(3), pages 661-672.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:orijoc:v:34:y:2022:i:2:p:752-768. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.