Research map / Bandits and online learning / Online convex optimization and games
Improved Analysis for Bandit Learning in Matching Markets
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 AETGS with elimination, an adaptive explore-then-Gale-Shapley bandit algorithm for matching markets achieving O(N^2 log T/Δ^2 + K log T/Δ) player-optimal stable regret, and refines the centralized UCB analysis under the α-condition to O(N log T/Δ^2 + K log T/Δ).
Problem
Bandit learning in two-sided one-to-one matching markets where players must learn unknown preferences over arms and converge to the player-optimal stable matching while minimizing stable regret; prior bounds scale with K in the main term.
Approach
Integrates the learning process into the Gale-Shapley steps: players adaptively explore, eliminate sub-optimal arms in real time (keeping N arms), and exploit once their most preferred available arm is identified, rather than explicitly separating exploration from exploitation. Also refines the centralized UCB analysis under the α-condition via inductive analysis over players.
Key results
- AETGS with elimination achieves player-optimal stable regret O(N^2 log T/Δ^2 + K log T/Δ), removing the K dependence from the main term versus prior O(K log T/Δ^2).
- Under the α-condition, centralized UCB achieves an improved O(N log T/Δ^2 + K log T/Δ) regret bound.
- In simulations with N=3, K=10 over 50 runs and T=100k, AETGS-E attains the lowest cumulative regret and player-optimal unstability among compared baselines.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use AETGS with elimination instead of the prior ETC-style methods | Decentralized matching markets · Decentralized one-to-one markets (N = 3, K = 10) | maximum cumulative player-optimal stable regret | Helped |
| Use AETGS with elimination instead of the prior ETC-style methods | Decentralized matching markets · Decentralized one-to-one markets (N = 3, K = 10) | cumulative player-optimal instability | Helped |
| Replace full preference-ranking exploration with adaptive exploration integrated into Gale–Shapley and prompt arm elimination | Player-optimal stable regret in general matching markets · General matching markets | regret upper bound: O(K log T/∆2) -> O(N 2 log T/∆2 + K log T/∆) | Helped |
| Refine the centralized UCB analysis for markets satisfying α-condition | Centralized UCB · Markets satisfying α-condition | stable regret upper bound: O(NK log T/∆2) -> O(N log T/∆2 + K log T/∆) | Helped |
Limitations
- Lower bound for general markets remains open, so optimality is not established for the general case.
- Experiments are limited to a single small synthetic setting (N=3, K=10).
- Decentralized extension relies on phased communication and a regret overhead of up to a factor of two.
Experimental setup
Benchmarks: simulated one-to-one decentralized matching market (N=3, K=10)
Metrics: maximum cumulative player-optimal stable regret cumulative player-optimal unstability
Baselines: ETGS ML-ETC Phased ETC centralized UCB
Builds on: Gale-Shapley algorithm explore-then-commit (ETGS) UCB centralized UCB (Liu et al. 2020) AETDA (Kong and Li 2021)
Closest papers by meaning
- Improved Bandits in Many-to-One Matching Markets with Incentive Compatibility (AAAI 2024 · similarity 0.93)
- Competing Bandits in Matching Markets via Super Stability (ICML 2025 · similarity 0.93)
- Stable Matching with Ties: Approximation Ratios and Learning (NeurIPS 2025 · similarity 0.90)
- Stochastic Matching Bandits with Rare Optimization Updates (NeurIPS 2026 · similarity 0.90)
- Two-sided Competing Matching Recommendation Markets With Quota and Complementary Preferences Constraints (ICML 2024 · similarity 0.90)
- Decentralized and Uncoordinated Learning of Stable Matchings: A Game-Theoretic Approach (AAAI 2025 · similarity 0.89)
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.