Study proves a tight lower bound for MNL-Bandit assortment selection problems.
problem Dynamic assortment planning under MNL bandit model with capacity constraints.
method Proved a tight lower bound on accumulated regret for all parameters.
result Tight lower bound matches existing upper bounds up to logarithmic factors.
New algorithms minimize risk in MNL bandits, achieving near-optimal performance.
problem Minimizing risk in multi-armed bandit problems.
method Designing algorithms for various risk criteria (e.g., CVaR, Sharpe ratio, entropy risk).
result Near-optimal regret for the designed algorithms.
Study MNL-Bandit in non-stationary settings with optimal regret bound.
problem Optimizing decisions in a non-stationary environment for multi-armed bandit problems.
method Develops an algorithm with worst-case expected regret bound and introduces new techniques to handle non-stationarity.
result Optimal regret bound proven for the MNL-Bandit problem in non-stationary environments.
The paper achieves nearly optimal regret bounds for contextual multinomial logit bandits.
problem The contextual multinomial logit (MNL) bandit problem with varying rewards.
method Established lower bounds and proposed OFU-MNL+ algorithm with matching upper bounds.
result Achieved minimax optimal regret bounds for both uniform and non-uniform reward settings.
Two algorithms optimize assortment selection for user choices in unknown MNL models.
problem Sequential assortment selection with unknown multinomial logit parameters.
method Upper confidence bound algorithms for MNL contextual bandits.
result Optimal regret bounds for assortment selection problems.
Improved online confidence bounds for multinomial logistic models in bandits.
problem Achieving optimal regret in multinomial logistic bandits with bounded parameters and outcomes.
method Deriving an improved online confidence bound and proposing OFU-MNL++ and OFU-MN 2 ^2 2 L algorithms. result Achieved variance-dependent optimal regret for MNL bandits.
New algorithm LUMB reduces regret for linear utility multinomial logit bandit.
problem Sequential subset selection with multinomial logit rewards.
method Proposes LUMB algorithm exploiting linear utility model.
result Achieves i l d e O ( d K T ) ilde{O}\big(dK\sqrt{T}\big) i l d e O ( d K T ) regret, independent of N N N . Optimal design for multinomial logit models improves assortment selection efficiency.
problem Optimal experimental design for multinomial logit models with feedback.
method Two complementary approaches: MILP reformulation and lifted design.
result Achieves statistical efficiency and scalability for MNL bandits.
New algorithm tackles non-linear utility in MNL bandits with i l d e O ( T ) ilde{O}(\sqrt{T}) i l d e O ( T ) regret.
problem Sequential assortment selection with intricate user-item interactions.
method Upper Confidence Bound principle for non-linear parametric utility functions, including neural networks.
result Achieves i l d e O ( T ) ilde{O}(\sqrt{T}) i l d e O ( T ) regret bound for neural network-based utilities. DMNL bandits optimize assortment choices balancing relevance and diversity.
problem Balancing relevance-driven choice with within-assortment diversity.
method Augments MNL choice probabilities with a submodular diversity function, proposing a white-box UCB-based algorithm.
result Achieves at least a ( 1 − 1 e + 1 ) (1-\frac{1}{e+1}) ( 1 − e + 1 1 ) -approximate regret bound of $ ilde{O}\left(d \sqrt{T/K}
ight)$ . Two algorithms achieve optimal regret with limited adaptivity in multinomial logistic bandits.
problem Achieving optimal regret with limited adaptivity in multinomial logistic bandits.
method Presented two algorithms, B-MNL-CB and RS-MNL, for batched and rarely-switching paradigms.
result Achieved i l d e O ( T ) ilde{O}(\sqrt{T}) i l d e O ( T ) regret with limited adaptivity. New algorithm for maximizing revenue in multinomial logistic bandits.
problem Maximizing revenue in scenarios with multiple outcomes.
method MNL-UCB algorithm based on upper confidence bounds.
result Achieves regret i l d e O ( d K T ) ilde{\mathcal{O}}(dK\sqrt{T}) i l d e O ( d K T ) with small dependency on constants. Improved regret bound for MNL MDPs with variance-aware approach.
problem Optimal reinforcement learning for MNL MDPs with structured variance.
method Introducing a problem-dependent constant measuring average variance, proposing an algorithm with improved regret bound.
result Minimax optimal regret bound of O ( d H 2 σ ˉ T T ) O(dH^2\barσ_T\sqrt{T}) O ( d H 2 σ ˉ T T ) for structured MDPs. Paper tackles combinatorial reinforcement learning with preference feedback.
problem Modeling long-term user engagement in scenarios like recommender systems and online advertising.
method Assumes a contextual MNL preference model with linear mean utilities and approximates item values. Proposes MNL-VQL algorithm.
result Achieves nearly minimax-optimal regret for linear MDPs with preference feedback.
New model optimizes assortment and pricing with dynamic customer arrivals.
problem Suboptimal decisions in classical models due to fixed arrival rates.
method Poisson-MNL model with UCB algorithm for dynamic decisions.
result Efficient algorithm achieves near optimal cumulative revenue.
Paper presents a privacy-preserving method for dynamic assortment selection.
problem Personalized assortment recommendations with data privacy concerns.
method Perturbed upper confidence bound method integrating calibrated noise.
result Policy satisfies Joint Differential Privacy (JDP) with near-optimal regret bound.
Optimal policy for dynamic assortment planning under MNL model with O ( T ) O(\sqrt{T}) O ( T ) regret.
problem Maximizing revenue in dynamic assortment planning under MNL model with unknown parameters.
method Trisection-based policy with adaptive confidence bounds.
result Achieves O ( T ) O(\sqrt{T}) O ( T ) regret bound, independent of the number of products. New algorithm reduces regret in dynamic assortment selection.
problem Dynamic assortment selection with consumer choice modeling.
method Optimistic algorithm with convex relaxation.
result Regret bound of O ( d T + κ ) O(\sqrt{dT} + κ) O ( d T + κ ) , improving over existing methods. The paper tackles learning mixtures of two multinomial logits, showing identifiability and presenting an algorithm.
problem Learning an arbitrary mixture of two multinomial logits.
method Reduction to solving a system of univariate quartic equations, followed by an algorithm using polynomial and linear samples.
result Identifiability of the mixture models may only fail on an algebraic variety of negligible measure.
New algorithms reduce regret in reinforcement learning with MNL approximations.
problem Efficient reinforcement learning with MNL function approximation for MDPs.
method Proposed randomized exploration algorithms with frequentist regret guarantees.
result Achieved improved regret bounds for MNL transition models.
New algorithms reduce matching regret by limiting frequent updates.
problem Minimizing regret in stochastic matching with rare optimization updates.
method Batched algorithms that limit matching updates to Θ(log log T) rounds.
result Achieve a regret bound of \(\widetilde{\mathcal{O}}(\sqrt{T})\) with reduced computational cost.
This paper refines the weighted strategy for non-stationary parametric bandits and MDPs, improving regret bounds.
problem Non-stationary environments with gradual drifting patterns.
method Refined analysis framework for the weighted strategy, leading to simpler and more efficient algorithms.
result Improved regret bounds for linear bandits, generalized linear bandits, and self-concordant bandits.
Flexible nonparametric model for discrete choice analysis.
problem Modeling heterogeneity in discrete choice data without fixed component limits.
method Dirichlet process mixture model with expectation maximisation algorithm.
result Proposed model outperforms latent class MNL and mixed MNL models in both fit and predictive ability.
New algorithms learn MNL weights efficiently for any slate size.
problem Efficiently learn weights for MNL models given query access.
method Two algorithms: adaptive and non-adaptive, with specific query complexities.
result Optimal query complexities for both adaptive and non-adaptive cases.
Motivated by generating personalized recommendations using ordinal (or preference) data, we study the question of learning a mixture of MultiNomial Logit (MNL) model, a parameterized class of distributions over permutations, from partial ordinal or preference data (e.g. pair-wise comparisons). Despite its long standing…
The geometric non-linear Schrodinger equation (GNLS) on the complex Grassmannian manifold M is the Hamiltonian equation for the energy functional on C(R,M) with respect to the symplectic form induced from the Kahler form on M. It has a Lax pair that is gauge equivalent to the Lax pair of the matrix non-linear Schroding…
Study optimal product assortment using historical data, proving item coverage suffices.
problem Offline assortment optimization under MNL model with limited historical data.
method Pessimistic Rank-Breaking (PRB) algorithm combining rank-breaking and pessimistic estimation.
result Optimal item coverage is both sufficient and necessary for efficient offline learning.
The paper models network formation using mixed logit models.
problem Modeling network formation in various fields.
method Mixed logit models, specifically the repeated-choice (RC) model.
result The RC model outperforms the multinomial logit (MNL) model in estimating network formation.
New algorithm reduces reinforcement learning regret by adapting to interaction variability.
problem Existing reinforcement learning methods lack adaptability to interaction variability.
method Developed a variance-adaptive optimal algorithm for MNL function approximation.
result Achieved instance-wise optimal regret bounds, validating efficiency in practice.
New model predicts airline passenger itinerary choices using Pointer Networks.
problem Modeling air passenger choices of flight itineraries.
method Pointer Networks combining Recurrent Neural Networks and Attention Mechanism.
result Pointer Networks model outperforms traditional MNL model on metrics.
When tracking user-specific online activities, each user's preference is revealed in the form of choices and comparisons. For example, a user's purchase history is a record of her choices, i.e. which item was chosen among a subset of offerings. A user's preferences can be observed either explicitly as in movie ratings …
Algorithm stabilizes queues in asymmetric systems with unknown service rates.
problem Stabilizing queues in multi-class multi-server systems with unknown service rates.
method Proposes UCB and Thompson Sampling algorithms to stabilize queues while learning service rates.
result Achieves system stability with an average queue length bound of \(O(\min\{N,K\}/ε)\) for large time horizon \(T\).
New models improve choice prediction accuracy.
problem Model misspecifications in discrete choice models lead to limited predictability and biased estimates.
method Proposes a new approach to estimate choice models by dividing the systematic part into knowledge-driven and data-driven components, which learns a new representation from available variables.
result The new models (L-MNL and L-NL) outperform traditional models in predictive performance and parameter estimation.
CRS model improves ranking data modeling with theoretical guarantees.
problem Lack of rich, multimodal models for ranking data.
method Contextual Repeated Selection (CRS) model for multimodal ranking data.
result CRS model significantly outperforms existing methods in various ranking contexts.
New algorithm tackles dynamic assortment optimization with knapsack constraints.
problem Optimizing retailer's assortment decisions under resource constraints with multi-nomial choice modeling.
method Epoch-based re-solving algorithm that transforms MNL's fractional structure into a linear program with slack variables.
result Regret scales logarithmically with time horizon and resource capacities.
Study dynamic assortment and positioning of products with varying display effects.
problem Dynamic assortment and positioning of products with varying display effects.
method Design round-based learning algorithms for both multiplicative and general position effects models, and develop efficient subroutines for optimization.
result First regret-optimal characterization for both models, with matching upper and lower bounds.
The paper studies ranking algorithms from pairwise and listwise comparisons, deriving lower bounds and optimal algorithms.
problem Designing efficient ranking algorithms from pairwise and listwise comparisons.
method Deriving lower bounds and proposing optimal algorithms for top-k and total ranking problems.
result The proposed algorithms match the derived lower bounds and are optimal up to a logarithmic factor.
New model improves website ranking by considering user choices as a whole.
problem Optimizing content ordering for user clicks in website design.
method Introduced multinomial logit (MNL) choice model to LTR framework, proposing UCB algorithms.
result Proved theoretical bounds on regret for UCB algorithms in both known and unknown position parameter settings.
Optimizes assortment decisions with a new OFU scheme for online choice problems.
problem Online assortment optimization under stochastic choice with revenue performance and inference quality considerations.
method Forced-exploration OFU scheme combining regularized estimators for decision making and inference.
result Explicit regret bound and error bounds for approximate optimistic actions, showing Pareto optimality.
This paper optimizes product assortment decisions with changing contextual information.
problem Optimizing product assortment decisions in a dynamic context.
method Developed an upper confidence bound (UCB) policy to learn and make decisions under a changing contextual MNL model.
result Established a regret bound of O ~ ( d T ) \widetilde O(d\sqrt{T}) O ( d T ) and a lower bound of Ω ( d T / K ) Ω(d\sqrt{T}/K) Ω ( d T / K ) for dynamic assortment optimization. The question of aggregating pair-wise comparisons to obtain a global ranking over a collection of objects has been of interest for a very long time: be it ranking of online gamers (e.g. MSR's TrueSkill system) and chess players, aggregating social opinions, or deciding which product to sell based on transactions. In mo…
As datasets capturing human choices grow in richness and scale -- particularly in online domains -- there is an increasing need for choice models that escape traditional choice-theoretic axioms such as regularity, stochastic transitivity, and Luce's choice axiom. In this work we introduce the Pairwise Choice Markov Cha…
New algorithms tackle RKHS bandits with reduced complexity and improved performance.
problem Adversarial and stochastic RKHS bandit problems with high computational complexity.
method Combining approximation theory with misspecified linear bandit methods.
result First general algorithm for adversarial RKHS bandit problem.
New research shows testing IIA in discrete choice is nearly impossible with current sample sizes.
problem Testing the Independence of Irrelevant Alternatives (IIA) in discrete choice models is challenging.
method Combinatorial analysis of Eulerian orientations of cycle decompositions of a bipartite graph.
result Any general test for IIA with low worst-case error requires an exponential number of samples in the number of alternatives.
Unified formulation bridges adversarial and nonstationary bandits.
problem Handling time-varying reward distributions in multi-armed bandit problems.
method Unified oracle that switches between adversarial and nonstationary bandit oracles based on window size.
result Optimal regret achieved with matching lower bound.
Paper studies attacks on bandit algorithms and shows how attackers can manipulate data to hijack behavior.
problem Potential attacks on bandit algorithms can cause catastrophic loss in real-world applications.
method Proposes a framework of offline and online attacks on bandit algorithms using convex optimization and adaptive strategies.
result Attackers can force bandit algorithms to pull target arms with high probability by manipulating data.
Paper solves stochastic contextual linear bandits using linear bandit algorithms.
problem Stochastic contextual linear bandits with unknown context distribution.
method Establishes a reduction framework to convert to linear bandit problems.
result Achieves nearly optimal regret bound of O ( d T log T ) O(d\sqrt{T\log T}) O ( d T log T ) . Paper tackles LDP bandits learning with improved results and sub-linear regret.
problem Contextual bandits learning with LDP privacy constraints.
method Simple black-box reduction frameworks for context-free bandits, extended to GLB.
result First result for BCO with multi-point feedback under LDP, sub-linear regret for GLB.