Research map / Bandits and online learning / Online convex optimization and games
Online Learning of Delayed Choices
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes DEMBA and PA-DEMBA, optimism-based (UCB) algorithms for online assortment selection under the MNL choice model with delayed and optionally threshold-censored feedback, with ~O(√(NT)) regret and a matching lower bound up to logs.
Problem
Online assortment optimization under an unknown multinomial logit (MNL) choice model where customer choice feedback arrives with random delays, possibly censored by a business-imposed threshold.
Approach
Epoch-based optimistic (UCB) estimation of MNL attraction parameters built on biased delayed observations, with confidence radii adjusted for thresholding (censoring bias scaled by psi_mu) or for expected delay in the non-thresholded (patient) case, and assortments chosen to maximize the optimistic revenue.
Key results
- DEMBA achieves regret bound of order O~(sqrt(NT)) in the thresholded setting, with a matching Omega(sqrt(NT)) lower bound up to logarithmic factors (Theorems 5.1, 5.2).
- PA-DEMBA achieves O~(sqrt(NT)) regret in the non-thresholded setting (Theorem 6.2), with bounds depending on expected delay E[d_s] instead of psi_mu.
- In simulations over 100 independent runs, DEMBA outperforms explore-then-exploit benchmarks across geometric and uniform delay settings, while MNL-Bandit degrades as delay increases.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use DEMBA instead of the explore-then-exploit benchmarks | Thresholded delayed-choice assortment learning · Geometric and uniform delays; three threshold/delay settings | cumulative regret | Helped |
| increase the thresholded feedback fraction ψµ | DEMBA · Thresholded delays | cumulative regret | Helped |
| use uniform rather than geometric delays | DEMBA · Thresholded delays | cumulative regret | Hurt |
| increase product contrast ϵ | DEMBA · Geometric delays, varying contrast | cumulative regret | Mixed |
| use PA-DEMBA rather than the EXP benchmarks | Non-thresholded delayed-choice assortment learning · Non-thresholded geometric delays | cumulative regret | Helped |
| apply a delay-unaware MNL-Bandit algorithm as delay increases | MNL-Bandit · No delay, E[ds] = 50, and E[ds] = 100 | cumulative regret | Hurt |
| use DEMBA rather than MNL-Bandit when there is no delay | Delayed-choice assortment learning · No delay | cumulative regret | No clear effect |
Surprising findings
- The paper conjectures the upper bound is not tight with respect to the threshold mu, since the lower bound decreases with larger psi_mu while the upper bound increases with mu.
Limitations
- Analysis uses only the expected delay and the threshold; tighter bounds based on delay skewness or variance are left open.
- Assumes no-purchase (browse-without-purchase) decisions are observable, distinct from delayed purchases.
- Experiments are limited to simulated synthetic instances with N=10, K=4.
Experimental setup
Benchmarks: simulated MNL assortment instances (N=10, K=4)
Metrics: cumulative regret
Baselines: explore-then-exploit (EXP) MNL-Bandit
Builds on: MNL-Bandit (Agrawal et al. 2019) Upper confidence bound (Auer et al. 2002) Thresholded linear bandits with delays (Vernade et al. 2020)
Closest papers by meaning
- Combinatorial Reinforcement Learning with Preference Feedback (ICML 2025 · similarity 0.87)
- Nearly Minimax Optimal Regret for Multinomial Logistic Bandit (NeurIPS 2024 · similarity 0.87)
- Dynamic Assortment Selection and Pricing with Censored Preference Feedback (ICLR 2025 · similarity 0.87)
- Contextual Multinomial Logit Bandits with General Value Functions (NeurIPS 2024 · similarity 0.87)
- Improved Online Confidence Bounds for Multinomial Logistic Bandits (ICML 2025 · similarity 0.86)
- Tractable Multinomial Logit Contextual Bandits with Non-Linear Utilities (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.