Online Learning of Delayed Choices
Abstract
Choice models are essential for understanding decision-making processes in domains like online advertising, product recommendations, and assortment optimization. The Multinomial Logit (MNL) model is particularly versatile in selecting products or advertisements for display. However, challenges arise with unknown MNL parameters and delayed feedback, requiring sellers to learn customers' choice behavior and make dynamic decisions with biased knowledge due to delays. We address these challenges by developing an algorithm that handles delayed feedback, balancing exploration and exploitation using confidence bounds and optimism. We first consider a censored setting where a threshold for considering feedback is imposed by business requirements. Our algorithm demonstrates a Õ( √ N T ) regret, with a matching lower bound up to a logarithmic term. Furthermore, we extend our analysis to environments with non-thresholded delays, achieving a Õ( √ N T ) regret. To validate our approach, we conduct experiments that confirm the effectiveness of our algorithm.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Lineage
Builds on8
- Linear bandits with Stochastic Delayed FeedbackClaire Vernade, Alexandra Carpentier, Tor Lattimore, Giovanni Zappella et al.ICML 2020 · 74 citations
- Stochastic bandits with arm-dependent delaysAnne Gael Manegueu, Claire Vernade, Alexandra Carpentier, Michal ValkoICML 2020 · 49 citations
- Stochastic Multi-Armed Bandits with Unrestricted Delay DistributionsTal Lancewicki, Shahar Segal, Tomer Koren, Yishay MansourICML 2021 · 45 citations
- Online Learning with Optimism and DelayGenevieve Flaspohler, Francesco Orabona, Judah Cohen, Soukayna Mouatadid et al.ICML 2021 · 40 citations
- Dynamic pricing and assortment under a contextual MNL demandNoémie Périvier, Vineet GoyalNeurIPS 2022 · 29 citations
Related papers
- Multinomial Logit Contextual Bandits: Provable Optimality and PracticalityMin-hwan Oh, Garud IyengarAAAI 2021 · 29 citations
- Dynamic Assortment Selection and Pricing with Censored Preference FeedbackJung-hun Kim, Min-hwan OhICLR 2025
- Combinatorial Reinforcement Learning with Preference FeedbackJoongkyu Lee, Min-hwan OhICML 2025
- Improved Confidence Regions and Optimal Algorithms for Online and Offline Linear MNL BanditsYuxuan Han, José H. Blanchet, Zhengyuan ZhouNeurIPS 2025 · 1 citation
- Nearly Minimax Optimal Regret for Multinomial Logistic BanditJoongkyu Lee, Min-hwan OhNeurIPS 2024 · 20 citations
