Improved regret bounds for logistic bandits via novel confidence set construction.
problem Dependencies in parameter space for logistic bandits, especially when S ≥ d S \geq d S ≥ d . method Regret-to-confidence-set conversion (R2CS) to construct convex confidence sets.
result Strict improvement in regret bound w.r.t. S S S in logistic bandits. 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. Improved regret bound for multinomial logistic bandits with non-linearity.
problem Maximizing rewards in multinomial logistic bandits with non-linear feedback.
method Extended the definition of κ ∗ κ_* κ ∗ to multinomial setting and proposed an efficient algorithm. result Minimax-optimal regret bound of O ~ ( R d K T / κ ∗ ) \smash{\widetilde{\mathcal{O}}( R d \sqrt{ {KT}/{κ_*}} ) } O ( R d K T / κ ∗ ) , improving over existing guarantees. 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. A new algorithm reduces the time and space complexity for multinomial logistic bandits.
problem High-dimensional feedback in multinomial logistic bandits makes existing algorithms inefficient.
method Integrates frequent directions matrix sketching into OFUL-MLogB to reduce time and space complexity.
result Achieves a regret bound of i l d e O ( Δ T ( K d ln Δ T + m ) T ) ilde{\mathcal{O}}(Δ_T(Kd\lnΔ_T+m)\sqrt{T}) i l d e O ( Δ T ( K d ln Δ T + m ) T ) . 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.
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. 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.
PIANO speeds up multinomial logistic regression solving.
problem Handling large datasets and many classes in logistic regression.
method Parallel iterative algorithm based on Majorization Minimization.
result PIANO converges to a stationary point of Multinomial and Sparse Multinomial Logistic Regression.
The paper proves asymptotic normality for multinomial logistic regression on null covariates.
problem Classical asymptotic normality results fail in high-dimensional multinomial logistic models.
method Developed asymptotic normality and chi-square results for multinomial logistic MLE on null covariates.
result Validated new methodology to test feature significance in high-dimensional classification problems.
Sparse multinomial logistic regression for multiclass classification with feature selection.
problem High-dimensional multiclass classification with a focus on sparse models.
method Penalized maximum likelihood with complexity penalty, feature selection using group Lasso and Slope classifiers.
result Achievement of minimax order in both small and large number of classes regimes.
Efficient RL algorithm for multinomial logistic MDPs with provable guarantees.
problem Model-based RL for episodic MDPs with unknown transition probabilities.
method Upper confidence bound-based algorithm for exploration-exploitation balance.
result Achieves i l d e O ( d H 3 T ) ilde{O}(d \sqrt{H^3 T}) i l d e O ( d H 3 T ) regret bound for multinomial logistic models. New algorithm reduces switching costs in multinomial logit bandit problems.
problem Minimizing switching costs in multinomial logit bandit problems.
method Proposed AT-DUCB and FH-DUCB algorithms with low assortment switching costs.
result AT-DUCB and FH-DUCB algorithms achieve almost optimal minimax regret with low switching costs.
We improve MoE models for classification with rigorous guarantees and practical methods.
problem Limited guarantees for stable maximum-likelihood training and model selection in softmax-gated MoE models.
method Derived a batch MM algorithm with closed-form updates, proved finite-sample rates, and developed a dendrogram selector.
result Achieved near-parametric optimal rates for parameter recovery and improved accuracy over baselines.
We propose a penalized likelihood method that simultaneously fits the multinomial logistic regression model and combines subsets of the response categories. The penalty is non differentiable when pairs of columns in the optimization variable are equal. This encourages pairwise equality of these columns in the estimator…
Proposes a method to use external machine-learning predictions in multinomial logistic regression.
problem Improving statistical inference using summary-level external machine-learning predictions.
method Empirical-likelihood framework incorporating moment constraints from external nonparametric machine-learning predictions.
result Fused estimator achieves strict efficiency gain over primary-only estimator under mild conditions.
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.
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.
Develops first optimal algorithm for logistic bandits.
problem Pure exploration in logistic bandits.
method Logistic track-and-stop (Log-TS) algorithm.
result Asymptotically matches lower bound for expected sample complexity.
We develop an approximate formula for evaluating a cross-validation estimator of predictive likelihood for multinomial logistic regression regularized by an ℓ 1 \ell_1 ℓ 1 -norm. This allows us to avoid repeated optimizations required for literally conducting cross-validation; hence, the computational time can be significantl…
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)$ . Scaling multinomial logistic regression to datasets with very large number of data points and classes is challenging. This is primarily because one needs to compute the log-partition function on every data point. This makes distributing the computation hard. In this paper, we present a distributed stochastic gradient d…
The paper establishes convergence rates for MoE models in classification problems.
problem Understanding the behavior of MoE models in classification settings.
method Established convergence rates for density and parameter estimation in softmax gating multinomial logistic MoE models.
result Parameter estimation rates are significantly improved with a novel modified softmax gating function.
New algorithm reduces regret for logistic bandits without κ κ κ dependency.
problem Logistic bandits have poor frequentist regret guarantees due to large κ κ κ . method Optimistic algorithm based on self-normalized martingale tail-inequality.
result Achieves i l d e O ( T ) ilde{\mathcal{O}}(\sqrt{T}) i l d e O ( T ) regret with no κ κ κ dependency. For the problem of multi-class linear classification and feature selection, we propose approximate message passing approaches to sparse multinomial logistic regression (MLR). First, we propose two algorithms based on the Hybrid Generalized Approximate Message Passing (HyGAMP) framework: one finds the maximum a posterio…
This work improves regret minimization for logistic bandits by reducing dependence on a large constant.
problem Minimizing regret in logistic bandits with reduced dependence on a large constant.
method Experimental design procedure and warmup sampling algorithm.
result Achieves a minimax regret of \(O(\sqrt{d \dotμT\log(|\mathcal{X}|)})\) in the fixed arm setting.
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.
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. Many practical modeling problems involve discrete data that are best represented as draws from multinomial or categorical distributions. For example, nucleotides in a DNA sequence, children's names in a given state and year, and text documents are all commonly modeled with multinomial distributions. In all of these cas…
Paper uses subjective logic to estimate uncertainty in multi-armed bandit problems.
problem Estimating uncertainty in multi-armed bandit problems.
method Formalism of subjective logic applied to multi-armed bandits, proposing new algorithms.
result Subjective logic quantities enable useful assessment of uncertainty.
Improved confidence bounds for linear logistic model with applications to bandits.
problem Improving confidence bounds for linear logistic model.
method Self-concordant analysis of the logistic loss to avoid dependence on worst-case variance.
result Significant improvement in confidence bounds, avoiding dependence on 1 / κ 1/κ 1/ κ . We present ADMM-Softmax, an alternating direction method of multipliers (ADMM) for solving multinomial logistic regression (MLR) problems. Our method is geared toward supervised classification tasks with many examples and features. It decouples the nonlinear optimization problem in MLR into three steps that can be solv…
The logistic normal distribution has recently been adapted via the transformation of multivariate Gaus- sian variables to model the topical distribution of documents in the presence of correlations among topics. In this paper, we propose a probit normal alternative approach to modelling correlated topical structures. O…
FisherSFT selects informative examples to fine-tune LLMs efficiently.
problem Adapting large language models to new domains efficiently.
method Selects examples maximizing information gain using Hessian of log-likelihood.
result Empirically demonstrates improved performance with reduced computational cost.
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.
Approximates large Random Forest models to save space.
problem Large model size limits deployment on small devices.
method Approximate each tree using multinomial logistic regression.
result Reduced model size without significant loss of accuracy.
Researchers show mixtures of ranking models are generally identifiable.
problem Understanding when and how parameters of mixtures of ranking models can be uniquely determined.
method Algebraic geometry framework applied to verify the number of solutions in polynomial systems.
result Popular mixtures of ranking models with two components are generically identifiable.
We address the problem of regret minimization in logistic contextual bandits, where a learner decides among sequential actions or arms given their respective contexts to maximize binary rewards. Using a fast inference procedure with Polya-Gamma distributed augmentation variables, we propose an improved version of Thomp…
New algorithms reduce regret in neural logistic bandits.
problem Learning unknown reward functions in neural networks.
method Introduced a Bernstein-type inequality for self-normalized vector-valued martingales.
result Regret bounds improved to O ~ ( d ~ κ T ) \widetilde{O}(\widetilde{d}\sqrt{κT}) O ( d κ T ) and O ~ ( d ~ T / κ ) \widetilde{O}(\widetilde{d}\sqrt{T/κ}) O ( d T / κ ) . Improved algorithm for logistic bandits with better regret bounds.
problem Understanding the impact of non-linearity in logistic bandits.
method Introducing a new algorithm and providing refined analysis.
result Improved regret bounds scaling as O ~ ( d T / κ ) \tilde{\mathcal{O}}(d\sqrt{T/κ}) O ~ ( d T / κ ) in most favorable cases. Improved Thompson Sampling for logistic bandits with information-theoretic analysis.
problem Optimizing binary reward probabilities in logistic bandit problems.
method Information-theoretic framework, focusing on the information ratio and minimax measure.
result Bound on Bayesian expected regret of O ( d / α T log ( β T / d ) ) O(d/α\sqrt{T \log(βT/d)}) O ( d / α T log ( β T / d ) ) for logistic bandits. 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.
Improved logistic MoE with sigmoid gate shows better sample efficiency.
problem Improving sample efficiency in logistic MoE models.
method Comprehensive analysis of multinomial logistic MoE with modified sigmoid gate, incorporating temperature parameter and using Euclidean score.
result The sigmoid gate leads to lower sample complexity than softmax gate for both parameter and expert estimation.
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.
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.
Model predicts individual insurance claim reserves using activation patterns.
problem Accurately predicting individual claim reserves in insurance contracts.
method Multinomial logistic regression to model claim activation and development.
result The model generates accurate predictions of total and per coverage reserves.
Bandits with Knapsacks (BwK) is a general model for multi-armed bandits under supply/budget constraints. While worst-case regret bounds for BwK are well-understood, we present three results that go beyond the worst-case perspective. First, we provide upper and lower bounds which amount to a full characterization for lo…
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.