IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2310.00786.html
   My bibliography  Save this paper

Semidiscrete optimal transport with unknown costs

Author

Listed:
  • Yinchu Zhu
  • Ilya O. Ryzhov

Abstract

Semidiscrete optimal transport is a challenging generalization of the classical transportation problem in linear programming. The goal is to design a joint distribution for two random variables (one continuous, one discrete) with fixed marginals, in a way that minimizes expected cost. We formulate a novel variant of this problem in which the cost functions are unknown, but can be learned through noisy observations; however, only one function can be sampled at a time. We develop a semi-myopic algorithm that couples online learning with stochastic approximation, and prove that it achieves optimal convergence rates, despite the non-smoothness of the stochastic gradient and the lack of strong concavity in the objective function.

Suggested Citation

  • Yinchu Zhu & Ilya O. Ryzhov, 2023. "Semidiscrete optimal transport with unknown costs," Papers 2310.00786, arXiv.org, revised Nov 2023.
    • Handle: RePEc:arx:papers:2310.00786
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/2310.00786
    File Function: Latest version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Bin Han & Ilya O. Ryzhov & Boris Defourny, 2016. "Optimal Learning in Linear Regression with Combinatorial Feature Selection," INFORMS Journal on Computing, INFORMS, vol. 28(4), pages 721-735, November.
    2. N. Bora Keskin & Assaf Zeevi, 2014. "Dynamic Pricing with an Unknown Demand Model: Asymptotically Optimal Semi-Myopic Policies," Operations Research, INFORMS, vol. 62(5), pages 1142-1167, October.
    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. Xiao, Baichun & Yang, Wei, 2021. "A Bayesian learning model for estimating unknown demand parameter in revenue management," European Journal of Operational Research, Elsevier, vol. 293(1), pages 248-262.
    2. Thomas Loots & Arnoud V. den Boer, 2023. "Data‐driven collusion and competition in a pricing duopoly with multinomial logit demand," Production and Operations Management, Production and Operations Management Society, vol. 32(4), pages 1169-1186, April.
    3. Boxiao Chen, 2021. "Data‐Driven Inventory Control with Shifting Demand," Production and Operations Management, Production and Operations Management Society, vol. 30(5), pages 1365-1385, May.
    4. Amir Ahmadi-Javid & Pooya Hoseinpour, 2022. "Convexification of Queueing Formulas by Mixed-Integer Second-Order Cone Programming: An Application to a Discrete Location Problem with Congestion," INFORMS Journal on Computing, INFORMS, vol. 34(5), pages 2621-2633, September.
    5. Huashuai Qu & Ilya O. Ryzhov & Michael C. Fu & Eric Bergerson & Megan Kurka & Ludek Kopacek, 2020. "Learning Demand Curves in B2B Pricing: A New Framework and Case Study," Production and Operations Management, Production and Operations Management Society, vol. 29(5), pages 1287-1306, May.
    6. Yuqing Zhang & Neil Walton, 2019. "Adaptive Pricing in Insurance: Generalized Linear Models and Gaussian Process Regression Approaches," Papers 1907.05381, arXiv.org.
    7. Gur, Yonatan & Macnamara, Gregory & Saban, Daniela, 2020. "On the Disclosure of Promotion Value in Platforms with Learning Sellers," Research Papers 3865, Stanford University, Graduate School of Business.
    8. den Boer, Arnoud V., 2015. "Tracking the market: Dynamic pricing and learning in a changing environment," European Journal of Operational Research, Elsevier, vol. 247(3), pages 914-927.
    9. Ruben Geer & Arnoud V. Boer & Christopher Bayliss & Christine S. M. Currie & Andria Ellina & Malte Esders & Alwin Haensel & Xiao Lei & Kyle D. S. Maclean & Antonio Martinez-Sykora & Asbjørn Nilsen Ris, 2019. "Dynamic pricing and learning with competition: insights from the dynamic pricing challenge at the 2017 INFORMS RM & pricing conference," Journal of Revenue and Pricing Management, Palgrave Macmillan, vol. 18(3), pages 185-203, June.
    10. Woonghee Tim Huh & Michael Jong Kim & Meichun Lin, 2022. "Bayesian dithering for learning: Asymptotically optimal policies in dynamic pricing," Production and Operations Management, Production and Operations Management Society, vol. 31(9), pages 3576-3593, September.
    11. Peter Seele & Claus Dierksmeier & Reto Hofstetter & Mario D. Schultz, 2021. "Mapping the Ethicality of Algorithmic Pricing: A Review of Dynamic and Personalized Pricing," Journal of Business Ethics, Springer, vol. 170(4), pages 697-719, May.
    12. Ying Zhong & L. Jeff Hong & Guangwu Liu, 2021. "Earning and Learning with Varying Cost," Production and Operations Management, Production and Operations Management Society, vol. 30(8), pages 2379-2394, August.
    13. Yiwei Chen & Cong Shi, 2023. "Network revenue management with online inverse batch gradient descent method," Production and Operations Management, Production and Operations Management Society, vol. 32(7), pages 2123-2137, July.
    14. Baris Ata & Alexandre Belloni & Ozan Candogan, 2018. "Latent Agents in Networks: Estimation and Targeting," Papers 1808.04878, arXiv.org, revised Jan 2022.
    15. Renato Matta & Timothy J. Lowe, 2023. "Product price alignment with seller service rating and consumer satisfaction," Annals of Operations Research, Springer, vol. 320(2), pages 695-725, January.
    16. Jianyu Xu & Yu-Xiang Wang, 2021. "Logarithmic Regret in Feature-based Dynamic Pricing," Papers 2102.10221, arXiv.org, revised Oct 2021.
    17. Jue Wang, 2021. "Optimal Bayesian Demand Learning over Short Horizons," Production and Operations Management, Production and Operations Management Society, vol. 30(4), pages 1154-1177, April.
    18. Yixiao Huang & Lei Zhao & Warren B. Powell & Yue Tong & Ilya O. Ryzhov, 2019. "Optimal Learning for Urban Delivery Fleet Allocation," Transportation Science, INFORMS, vol. 53(3), pages 623-641, May.
    19. Ruben van de Geer & Arnoud V. den Boer & Christopher Bayliss & Christine Currie & Andria Ellina & Malte Esders & Alwin Haensel & Xiao Lei & Kyle D. S. Maclean & Antonio Martinez-Sykora & Asbj{o}rn Nil, 2018. "Dynamic Pricing and Learning with Competition: Insights from the Dynamic Pricing Challenge at the 2017 INFORMS RM & Pricing Conference," Papers 1804.03219, arXiv.org.
    20. Joon Suk Huh & Ellen Vitercik & Kirthevasan Kandasamy, 2024. "Bandit Profit-maximization for Targeted Marketing," Papers 2403.01361, arXiv.org.

    More about this item

    Statistics

    Access and download statistics

    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:arx:papers:2310.00786. 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: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

    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.