Research map / Bandits and online learning / Multi-armed bandits

Stochastic Matching Bandits with Rare Optimization Updates

NeurIPS 2026 · Bandits and online learning › Multi-armed bandits · approach: Optimal stochastic bandit algorithms

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 batched elimination-based algorithms (B-SMB and B-SMB+) for stochastic matching bandits under an MNL arm-side choice model, achieving Õ(√T) regret while invoking combinatorial optimization only Θ(log log T) times.

Problem

Regret minimization for revenue-maximizing stochastic matching between agents and arms with MNL arm-side choice, where per-round assortment optimization is NP-hard.

Approach

Batched elimination with rare update epochs (doubly-logarithmic number of updates) combined with a localized Hessian-based confidence bound and G/D-optimal exploration design, so that combinatorial optimization is run only on a vanishing fraction of rounds.

Key results

• B-SMB and B-SMB+ use far fewer combinatorial optimization updates than OFU-MNL+, UCB-QMB, and TS-QMB, whose update counts grow linearly with time.
• Regret of the proposed algorithms is comparable to OFU-MNL+ and lower than UCB-QMB and TS-QMB on synthetic instances.
• Theoretical regret is Õ((1/κ) K^{3/2} sqrt(rT)) with known κ and Õ(r K^{3/2} sqrt(T)) without κ, using Θ(log log T) batch updates.

Limitations

• Regret with known κ scales with 1/κ, which can be as large as O(L^2) in the worst case.
• K^{3/2} dependence is worse than the Ω(K√T) lower bound by a factor of √K.
• Experiments are limited to small synthetic instances (N≤7, K≤4).

Experimental setup

Datasets: synthetic (uniform random features and preferences)

Benchmarks: synthetic stochastic matching bandit instances (N=3,K=2 and N=7,K=4, T=5000)

Metrics: cumulative regret cumulative number of combinatorial optimization updates runtime

Baselines: OFU-MNL+ UCB-QMB TS-QMB

Builds on: MNL bandits (OFU-MNL+) batched bandit elimination G-optimal design stable matching bandits

Closest papers by meaning

• Pure Exploration and Regret Minimization in Matching Bandits (ICML 2021 · similarity 0.91)
• Improved Analysis for Bandit Learning in Matching Markets (NeurIPS 2024 · similarity 0.90)
• Combinatorial Stochastic-Greedy Bandit (AAAI 2024 · similarity 0.90)
• Nearly Minimax Optimal Regret for Multinomial Logistic Bandit (NeurIPS 2024 · similarity 0.89)
• Competing Bandits in Matching Markets via Super Stability (ICML 2025 · similarity 0.89)
• Improved Bandits in Many-to-One Matching Markets with Incentive Compatibility (AAAI 2024 · similarity 0.88)