Near-optimal policies for dynamic multinomial logit assortment selection models

Yining Wang, Xi Chen, Yuan Zhou

Research output: Contribution to journalConference article

Abstract

In this paper we consider the dynamic assortment selection problem under an uncapacitated multinomial-logit (MNL) model. By carefully analyzing a revenue potential function, we show that a trisection based algorithm achieves an item-independent regret bound of O(√T log log T), which matches information theoretical lower bounds up to iterated logarithmic terms. Our proof technique draws tools from the unimodal/convex bandit literature as well as adaptive confidence parameters in minimax multi-armed bandit problems.

Original languageEnglish (US)
Pages (from-to)3101-3110
Number of pages10
JournalAdvances in Neural Information Processing Systems
Volume2018-December
StatePublished - Jan 1 2018
Event32nd Conference on Neural Information Processing Systems, NeurIPS 2018 - Montreal, Canada
Duration: Dec 2 2018Dec 8 2018

Keywords

  • Dynamic assortment planning
  • Multinomial logit choice model
  • Regret analysis
  • Trisection algorithm

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Information Systems
  • Signal Processing

Cite this

Near-optimal policies for dynamic multinomial logit assortment selection models. / Wang, Yining; Chen, Xi; Zhou, Yuan.

In: Advances in Neural Information Processing Systems, Vol. 2018-December, 01.01.2018, p. 3101-3110.

Research output: Contribution to journalConference article

@article{c3a3f502f7b54d0a826a49b2b97f9ea5,
title = "Near-optimal policies for dynamic multinomial logit assortment selection models",
abstract = "In this paper we consider the dynamic assortment selection problem under an uncapacitated multinomial-logit (MNL) model. By carefully analyzing a revenue potential function, we show that a trisection based algorithm achieves an item-independent regret bound of O(√T log log T), which matches information theoretical lower bounds up to iterated logarithmic terms. Our proof technique draws tools from the unimodal/convex bandit literature as well as adaptive confidence parameters in minimax multi-armed bandit problems.",
keywords = "Dynamic assortment planning, Multinomial logit choice model, Regret analysis, Trisection algorithm",
author = "Yining Wang and Xi Chen and Yuan Zhou",
year = "2018",
month = "1",
day = "1",
language = "English (US)",
volume = "2018-December",
pages = "3101--3110",
journal = "Advances in Neural Information Processing Systems",
issn = "1049-5258",

}

TY - JOUR

T1 - Near-optimal policies for dynamic multinomial logit assortment selection models

AU - Wang, Yining

AU - Chen, Xi

AU - Zhou, Yuan

PY - 2018/1/1

Y1 - 2018/1/1

N2 - In this paper we consider the dynamic assortment selection problem under an uncapacitated multinomial-logit (MNL) model. By carefully analyzing a revenue potential function, we show that a trisection based algorithm achieves an item-independent regret bound of O(√T log log T), which matches information theoretical lower bounds up to iterated logarithmic terms. Our proof technique draws tools from the unimodal/convex bandit literature as well as adaptive confidence parameters in minimax multi-armed bandit problems.

AB - In this paper we consider the dynamic assortment selection problem under an uncapacitated multinomial-logit (MNL) model. By carefully analyzing a revenue potential function, we show that a trisection based algorithm achieves an item-independent regret bound of O(√T log log T), which matches information theoretical lower bounds up to iterated logarithmic terms. Our proof technique draws tools from the unimodal/convex bandit literature as well as adaptive confidence parameters in minimax multi-armed bandit problems.

KW - Dynamic assortment planning

KW - Multinomial logit choice model

KW - Regret analysis

KW - Trisection algorithm

UR - http://www.scopus.com/inward/record.url?scp=85064841749&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85064841749&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:85064841749

VL - 2018-December

SP - 3101

EP - 3110

JO - Advances in Neural Information Processing Systems

JF - Advances in Neural Information Processing Systems

SN - 1049-5258

ER -