Pith. sign in

REVIEW 2 major objections 5 minor 118 references

Partial preference rankings let a matching platform stop early and still return the optimal stable matching with high probability under two-sided uncertainty.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-11 12:55 UTC pith:TMFOLMPM

load-bearing objection Solid two-sided pure-exploration result that cleanly imports pervasive stable matching into elimination algorithms and gives the first Δ_min-free regret bound for the optimal stable matching. the 2 major comments →

arxiv 2607.04824 v1 pith:TMFOLMPM submitted 2026-07-06 cs.LG stat.ML

Probably Correct Optimal Stable Matching under Two-Sided Uncertainty

Andreas Athanasopoulos , Anne-Marie George , Christos Dimitrakakis This is my paper
classification cs.LG stat.ML
keywords stable matchingtwo-sided uncertaintypure explorationpervasive stable matchingpartial preferenceselimination algorithmssemi-bandit feedbackregret minimization
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

In two-sided markets such as ride-hailing or online labor platforms, both sides start with unknown preferences and the platform can only learn them by repeatedly proposing matches and observing noisy rewards. The usual goal is either to minimize cumulative regret or to recover every agent’s complete ranking. This paper shows that neither is necessary. Once the platform has learned enough pairwise comparisons to certify a single matching that remains optimal no matter how the remaining unknown comparisons are resolved, it can stop. That matching is called a pervasive stable matching. Elimination algorithms that sample only the still-uncertain pairs and stop at the first pervasive stable matching achieve sample-complexity and regret bounds that depend on the easiest valid partial ranking rather than on the hardest pairwise gap. The same idea yields the first regret guarantee for the optimal stable matching under two-sided uncertainty that does not blow up when some irrelevant gaps become arbitrarily small.

Core claim

An elimination algorithm that maintains confidence intervals, builds partial rankings, and stops when those rankings admit a pervasive stable matching is δ-correct and uses a number of matchings bounded by a sum of inverse-squared gaps taken only over the easiest valid partial preference profile, not over the full ranking. The identical bound, used inside an explore-then-commit wrapper, produces a regret guarantee free of the global minimum gap Δ_min.

What carries the argument

Pervasive stable matching (PSM): a matching that is the unique proposer-optimal stable matching for every possible completion of the currently known partial rankings. The POSM procedure returns it (or NONE) in polynomial time and thereby supplies a sound early-stopping rule.

Load-bearing premise

Every agent-partner reward is 1-sub-Gaussian and all true utilities are distinct, so concentration radii shrink at the claimed rate and preferences remain strict total orders.

What would settle it

On a family of markets whose admissible gap Δ_F stays fixed while the global minimum gap Δ_min tends to zero, measure whether the number of samples used by E-PSM stays bounded by the Δ_F-dependent expression or grows like 1/Δ_min^{2}.

Watch this falsifier — get emailed when new claim-graph text bears on it.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper studies pure exploration for the optimal (P-optimal) stable matching in a centralized two-sided market under semi-bandit feedback when both sides have unknown preferences. It introduces the admissible gap Δ_F (the largest minimum gap over valid partial preference profiles that admit a pervasive stable matching) and shows that learning such a partial profile is sufficient. Uniform strategies and an elimination algorithm (E-PSM) that stops when a pervasive stable matching is found are analyzed; the sample-complexity bound of Theorem 5.1 replaces the usual Δ_min dependence by terms involving max(Δ_F, Δ^min_a,i). The same high-probability event yields an Explore-Then-Commit regret bound free of Δ_min (Theorem 5.2). An extended elimination rule that further prunes after a super-stable matching is identified, a non-explicit lower bound via change of measure, and simulations are also provided.

Significance. The work cleanly extends one-sided pure-exploration results to two-sided uncertainty and is the first to give a regret guarantee for the optimal stable matching under two-sided uncertainty that avoids Δ_min. The use of pervasive stable matching (rather than super-stability alone) is the right conceptual tool for the optimality objective, and the edge-coloring argument that converts per-pair elimination times into a matching-sample bound is a useful technical refinement. The analysis is standard and carefully written (concentration, elimination times, validity of the constructed partial profile, change-of-measure lower bound). Code is released and the experiments isolate the contributions of elimination versus the PSM stopping rule. These strengths make the paper a solid contribution to the bandit-matching literature.

major comments (2)
  1. The sample-complexity claim of Theorem 5.1 is stated as an unconditional O(·) bound on the number of sampled matchings, yet the proof (Appendix C) only shows that the bound holds with probability at least 1-δ under the good event E. Either the theorem statement should be rephrased as a high-probability bound, or an expectation argument (integrating the tail of the stopping time) should be added so that the claim matches the proof.
  2. Section 5.3 and Proposition 5.3 establish that the extended elimination rule after a super-stable matching still leaves a valid profile, but the authors correctly note that the Δ_F-based bound of Theorem 5.1 no longer applies. Because EE-PSM is presented as a contribution and is evaluated experimentally, a (possibly weaker) sample-complexity guarantee, or an explicit statement that none is claimed, is needed for completeness.
minor comments (5)
  1. In the proof of Theorem 4.1 the final display reads Pr(m_τ = m*) < 1-δ; it should be ≥ 1-δ.
  2. Notation for the set of agents is overloaded (A for both the full set and one side); a short clarifying sentence early in Section 2 would help.
  3. Figure 1 caption and the surrounding text refer to “Theorem 1 and Theorem 2”; they should cite Theorems 4.1 and 4.2.
  4. The lower-bound optimization problem (Theorem 6.1) is left non-explicit; a short remark on computational hardness or a pointer to approximation schemes would strengthen the discussion.
  5. A few typos remain (e.g., “Leaning in matching markets”, “umber of agents”, “witch concludes”). A careful proof-reading pass is recommended.

Circularity Check

0 steps flagged

No significant circularity; sample-complexity and regret claims rest on standard sub-Gaussian concentration plus an external polynomial-time oracle for pervasive stable matchings, with self-citations only to prior one-sided work that is not load-bearing.

full rationale

The central claims (Theorems 5.1–5.2) derive high-probability correctness and an instance-dependent sample-complexity bound expressed in the admissible gap Δ_F from three ingredients that are independently established inside the paper: (i) a union-bound concentration event E that every true mean stays inside its UCB/LCB forever (Lemma C.1, using only the 1-sub-Gaussian assumption), (ii) the elementary elimination-time conversion of a gap Δ into O(log(1/(δΔ))/Δ²) samples (Lemma C.2), and (iii) the existence of at least one valid partial profile whose minimum gap equals Δ_F (Definition 3.3 and Eq. (1)). The algorithm itself never requires knowledge of Δ_F; the quantity appears only in the analysis. The stopping rule invokes the external POSM procedure of Rastegari et al. (2014), which is polynomial-time and independent of the present authors. Self-citations to Athanasopoulos et al. (2025) concern only the one-sided special case and are not used to justify any step of the two-sided proofs. No parameter is fitted to evaluation data, no uniqueness theorem is imported from the authors’ own prior work, and no known empirical pattern is merely renamed. The derivation is therefore self-contained against the paper’s stated assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 4 axioms · 1 invented entities

The central claims rest on standard sub-Gaussian concentration, the classical Gale-Shapley lattice, and the polynomial-time POSM procedure of Rastegari et al. (2014). No free parameters are fitted; the only modeling choices are the 1-sub-Gaussian tail and the strict-preference assumption. Pervasive stable matching is imported, not invented.

axioms (4)
  • domain assumption Every reward distribution ν_a,i is 1-sub-Gaussian (Assumption 1).
    Used for all concentration radii (Eq. 2) and elimination-time bounds (Lemma C.2); without it the stated O(log(1/δ)/Δ^{2}) expressions fail.
  • domain assumption Utilities of each agent are distinct, inducing a strict total order (Section 2).
    Guarantees a unique optimal stable matching and that partial rankings refine to a total order; ties would require super-stability arguments that the main theorems avoid.
  • standard math A partial preference profile admits a pervasive stable matching if and only if POSM returns a matching (Rastegari et al. 2014).
    The stopping rule of Algorithms 2 and 3 invokes POSM as a black-box polynomial-time oracle; correctness of the algorithms inherits correctness of that oracle.
  • standard math The set of stable matchings is non-empty and forms a lattice (Gale-Shapley 1962).
    Background fact used to define the P-optimal matching that the algorithms target.
invented entities (1)
  • admissible gap Δ_F independent evidence
    purpose: Largest minimum pairwise gap over all valid partial preference profiles; replaces the classical Δ_min in sample-complexity and regret bounds.
    Defined in Eq. (1) purely from the instance; not a free parameter, but a new complexity measure introduced by the paper.

pith-pipeline@v1.1.0-grok45 · 33178 in / 2706 out tokens · 25665 ms · 2026-07-11T12:55:17.056354+00:00 · methodology

0 comments
read the original abstract

We study a sequential learning problem for stable matchings in two-sided markets where preferences on both sides are initially unknown. We focus on a centralized setting where an algorithm matches agents at each time step and receives noisy rewards that reflect the preferences of the matched agents, following a semi-bandit feedback structure. We adopt a pure exploration perspective, aiming to efficiently identify the optimal stable matching with high probability. Our work extends prior results by handling \emph{two-sided uncertainty} and by exploiting \emph{partial preference} information. A central ingredient is the notion of \textbf{pervasive stable matching}, which enables the identification of optimal stable matchings under partial preferences. We propose elimination-based algorithms whose stopping criteria exploit the structure of the learned partial preferences, and provide a refined sample-complexity analysis. Beyond pure exploration, we extend our approach to regret minimization and establish regret bounds with respect to the \emph{optimal} stable matching that avoid dependence on the minimum reward gap $\Delta_{\min}$.

Figures

Figures reproduced from arXiv: 2607.04824 by Andreas Athanasopoulos, Anne-Marie George, Christos Dimitrakakis.

Figure 1
Figure 1. Figure 1: Sample complexity bounds from Theorem 4.1 and [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Sample complexity as a function of market size [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Cumulative regret numbers of agents on each side, further demonstrating the effectiveness of our approach. 7.2 REGRET MINIMIZATION We further provide an ablation study for regret minimization. We measure regret using the cumulative market instability defined in Section 5.2, Eq. 7, which counts the number of rounds in which the selected matching differs from the optimal stable matching [Das and Kamenica, 20… view at source ↗
Figure 4
Figure 4. Figure 4: Illustration of the bipartite graph G [PITH_FULL_IMAGE:figures/full_fig_p017_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: illustrates the case of three agents on each side. a1 > a2 > a3 p1 a1 > a2 > a3 p2 a1 > a2 > a3 p3 a1 p1 > p2 > p3 a2 p1 > p2 > p3 a3 p1 > p2 > p3 [PITH_FULL_IMAGE:figures/full_fig_p024_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Illustration of the bipartite graph G. Lower bound on the number of matchings Eν[τ ] Finally, we lower bound the number of matchings τ by analyzing the associated bipartite multigraph G with edge multiplici￾ties ti,j , as illustrated in [PITH_FULL_IMAGE:figures/full_fig_p026_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Sample complexity as a function of the number of players [PITH_FULL_IMAGE:figures/full_fig_p028_7.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

118 extracted references · 1 canonical work pages

  1. [1]

    Complex & Intelligent Systems , volume=

    Towards fairness-aware multi-objective optimization , author=. Complex & Intelligent Systems , volume=. 2025 , publisher=

    2025

  2. [2]

    Games and Economic Behavior , volume=

    Social games: Matching and the play of finitely repeated games , author=. Games and Economic Behavior , volume=. 2010 , publisher=

    2010

  3. [3]

    Economics Bulletin , volume=

    Equilibrium existence in bipartite social games: A generalization of stable matchings , author=. Economics Bulletin , volume=. 2008 , publisher=

    2008

  4. [4]

    and Sotomayor, Marilda A

    Roth, Alvin E. and Sotomayor, Marilda A. Oliveira , year=. Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis , publisher=

  5. [5]

    Journal of political Economy , volume=

    The evolution of the labor market for medical interns and residents: a case study in game theory , author=. Journal of political Economy , volume=. 1984 , publisher=

    1984

  6. [6]

    Gale and L

    D. Gale and L. S. Shapley , journal =. College Admissions and the Stability of Marriage , urldate =

  7. [7]

    Decentralized Job Matching , volume =

    Haeringer, Guillaume and Wooders, Myrna , year =. Decentralized Job Matching , volume =. International Journal of Game Theory , doi =

  8. [8]

    Advances in Neural Information Processing Systems , volume=

    Learning equilibria in matching markets from bandit feedback , author=. Advances in Neural Information Processing Systems , volume=

  9. [10]

    The Foundations of Price Theory Vol 4 , pages=

    Non-cooperative games , author=. The Foundations of Price Theory Vol 4 , pages=. 2024 , publisher=

    2024

  10. [11]

    Mathematische annalen , volume=

    Zur theorie der gesellschaftsspiele , author=. Mathematische annalen , volume=. 1928 , publisher=

    1928

  11. [12]

    Theory of games and economic behavior , volume=

    Morgenstern, 0 , author=. Theory of games and economic behavior , volume=. 1944 , publisher=

    1944

  12. [13]

    Uncertainty in Artificial Intelligence , pages=

    Matrix games with bandit feedback , author=. Uncertainty in Artificial Intelligence , pages=. 2021 , organization=

    2021

  13. [14]

    Games and Economic Behavior , volume=

    Adaptive game playing using multiplicative weights , author=. Games and Economic Behavior , volume=. 1999 , publisher=

    1999

  14. [15]

    Artificial intelligence , volume=

    Multiagent learning using a variable learning rate , author=. Artificial intelligence , volume=. 2002 , publisher=

    2002

  15. [16]

    Reinforcement learning: State-of-the-art , pages=

    Game theory and multi-agent reinforcement learning , author=. Reinforcement learning: State-of-the-art , pages=. 2012 , publisher=

    2012

  16. [17]

    arXiv preprint arXiv:2312.00886 , volume=

    Nash learning from human feedback , author=. arXiv preprint arXiv:2312.00886 , volume=

    Pith/arXiv arXiv

  17. [18]

    nature , volume=

    Mastering the game of Go with deep neural networks and tree search , author=. nature , volume=. 2016 , publisher=

    2016

  18. [19]

    arXiv preprint arXiv:2307.12966 , year=

    Aligning large language models with human: A survey , author=. arXiv preprint arXiv:2307.12966 , year=

    Pith/arXiv arXiv

  19. [20]

    , title =

    Nisan, Noam and Roughgarden, Tim and Tardos, Eva and Vazirani, Vijay V. , title =. 2007 , isbn =

    2007

  20. [21]

    Prediction, Learning, and Games , publisher=

    Cesa-Bianchi, Nicolo and Lugosi, Gabor , year=. Prediction, Learning, and Games , publisher=

  21. [22]

    Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms , pages=

    Near-optimal no-regret algorithms for zero-sum games , author=. Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms , pages=. 2011 , organization=

    2011

  22. [23]

    Advances in Neural Information Processing Systems , volume=

    Optimization, learning, and games with predictable sequences , author=. Advances in Neural Information Processing Systems , volume=

  23. [24]

    Advances in Neural Information Processing Systems , volume=

    Near-optimal no-regret learning in general games , author=. Advances in Neural Information Processing Systems , volume=

  24. [25]

    Conference On Learning Theory , pages=

    More adaptive algorithms for adversarial bandits , author=. Conference On Learning Theory , pages=. 2018 , organization=

    2018

  25. [26]

    International Conference on Artificial Intelligence and Statistics , pages=

    Instance-dependent sample complexity bounds for zero-sum matrix games , author=. International Conference on Artificial Intelligence and Statistics , pages=. 2023 , organization=

    2023

  26. [27]

    arXiv preprint arXiv:2502.17625 , year=

    Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback , author=. arXiv preprint arXiv:2502.17625 , year=

    Pith/arXiv arXiv

  27. [28]

    Proceedings of IEEE 36th annual foundations of computer science , pages=

    Gambling in a rigged casino: The adversarial multi-armed bandit problem , author=. Proceedings of IEEE 36th annual foundations of computer science , pages=. 1995 , organization=

    1995

  28. [29]

    2019 , volume =

    Foundations and Trends® in Machine Learning , title =. 2019 , volume =. doi:10.1561/2200000068 , issn =

    doi:10.1561/2200000068 2019

  29. [30]

    Competing Against

    Cardoso, Adrian Rivera and Abernethy, Jacob and Wang, He and Xu, Huan , booktitle =. Competing Against. 2019 , editor =

    2019

  30. [31]

    Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems , pages =

    Athanasopoulos, Andreas and George, Anne-Marie and Dimitrakakis, Christos , title =. Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems , pages =. 2025 , isbn =

    2025

  31. [32]

    Neural Information Processing Systems , year=

    Non-Asymptotic Pure Exploration by Solving Games , author=. Neural Information Processing Systems , year=

  32. [33]

    Putting Gale &amp; Shapley to Work: Guaranteeing Stability Through Learning , volume =

    Hosseini, Hadi and Roy, Sanjukta and Zhang, Duohan , booktitle =. Putting Gale &amp; Shapley to Work: Guaranteeing Stability Through Learning , volume =

  33. [34]

    Proceedings of The 5th Annual Learning for Dynamics and Control Conference , pages =

    Competing Bandits in Time Varying Matching Markets , author =. Proceedings of The 5th Annual Learning for Dynamics and Control Conference , pages =. 2023 , editor =

    2023

  34. [35]

    Proceedings of the 19th International Joint Conference on Artificial Intelligence , pages =

    Das, Sanmay and Kamenica, Emir , title =. Proceedings of the 19th International Joint Conference on Artificial Intelligence , pages =. 2005 , publisher =

    2005

  35. [36]

    Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics , pages =

    Competing Bandits in Matching Markets , author =. Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics , pages =. 2020 , editor =

    2020

  36. [37]

    Journal of Machine Learning Research , volume=

    Bandit learning in decentralized matching markets , author=. Journal of Machine Learning Research , volume=

  37. [39]

    Proceedings of The 24th International Conference on Artificial Intelligence and Statistics , pages =

    Dominate or Delete: Decentralized Competing Bandits in Serial Dictatorship , author =. Proceedings of The 24th International Conference on Artificial Intelligence and Statistics , pages =. 2021 , editor =

    2021

  38. [40]

    Proceedings of the 38th International Conference on Machine Learning , pages =

    Beyond log^2(T) regret for decentralized bandits in matching markets , author =. Proceedings of the 38th International Conference on Machine Learning , pages =. 2021 , editor =

    2021

  39. [41]

    Proceedings of The 25th International Conference on Artificial Intelligence and Statistics , pages =

    Regret, stability & fairness in matching markets with bandit learners , author =. Proceedings of The 25th International Conference on Artificial Intelligence and Statistics , pages =. 2022 , editor =

    2022

  40. [42]

    Contributions to the Theory of Games , volume=

    Approximation to Bayes risk in repeated play , author=. Contributions to the Theory of Games , volume=

  41. [43]

    Information and computation , volume=

    The weighted majority algorithm , author=. Information and computation , volume=. 1994 , publisher=

    1994

  42. [44]

    Biometrika , volume=

    Asymptotic calibration , author=. Biometrika , volume=. 1998 , publisher=

    1998

  43. [45]

    Econometrica , volume=

    A simple adaptive procedure leading to correlated equilibrium , author=. Econometrica , volume=. 2000 , publisher=

    2000

  44. [46]

    Advances in Neural Information Processing Systems , volume=

    Fast convergence of regularized learning in games , author=. Advances in Neural Information Processing Systems , volume=

  45. [47]

    Advances in Neural Information Processing Systems , volume=

    Hedging in games: Faster convergence of external and swap regrets , author=. Advances in Neural Information Processing Systems , volume=

  46. [48]

    Advances in Neural Information Processing Systems , volume=

    Near-optimal no-regret learning dynamics for general convex games , author=. Advances in Neural Information Processing Systems , volume=

  47. [49]

    Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages=

    Near-optimal no-regret learning for correlated equilibria in multi-player general-sum games , author=. Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages=

  48. [50]

    Uncoupled Learning Dynamics with O( log T) Swap Regret in Multiplayer Games , volume =

    Anagnostides, Ioannis and Farina, Gabriele and Kroer, Christian and Lee, Chung-Wei and Luo, Haipeng and Sandholm, Tuomas , booktitle =. Uncoupled Learning Dynamics with O( log T) Swap Regret in Multiplayer Games , volume =

  49. [51]

    Bandit Algorithms , url =

    Lattimore, Tor and Szepesvari, Csaba , biburl =. Bandit Algorithms , url =

  50. [52]

    An Iterative Method of Solving a Game , urldate =

    Julia Robinson , journal =. An Iterative Method of Solving a Game , urldate =

  51. [53]

    Mathematics of Operations Research , volume=

    Zero-sum polymatrix games: A generalization of minmax , author=. Mathematics of Operations Research , volume=. 2016 , publisher=

    2016

  52. [54]

    Algorithmic Game Theory: Second International Symposium, SAGT 2009, Paphos, Cyprus, October 18-20, 2009

    The cost of stability in coalitional games , author=. Algorithmic Game Theory: Second International Symposium, SAGT 2009, Paphos, Cyprus, October 18-20, 2009. Proceedings 2 , pages=. 2009 , organization=

    2009

  53. [55]

    Econometrica: Journal of the Econometric Society , pages=

    Quasi-cores in a monetary economy with nonconvex preferences , author=. Econometrica: Journal of the Econometric Society , pages=. 1966 , publisher=

    1966

  54. [56]

    Journal of machine learning research , volume=

    Using confidence bounds for exploitation-exploration trade-offs , author=. Journal of machine learning research , volume=

  55. [57]

    Forty-second International Conference on Machine Learning , year=

    Competing Bandits in Matching Markets via Super Stability , author=. Forty-second International Conference on Machine Learning , year=

  56. [58]

    Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Player-optimal stable regret for bandit learning in matching markets , author=. Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2023 , organization=

    2023

  57. [59]

    Proceedings of the 2024 International Conference on Information Technology for Social Good , pages=

    Altruistic bandit learning for one-to-many matching markets , author=. Proceedings of the 2024 International Conference on Information Technology for Social Good , pages=

    2024

  58. [60]

    Proceedings of the 31st ACM International Conference on Information & Knowledge Management , pages=

    Bandit learning in many-to-one matching markets , author=. Proceedings of the 31st ACM International Conference on Information & Knowledge Management , pages=

  59. [61]

    Proceedings of the AAAI Conference on Artificial Intelligence , pages=

    Improved bandits in many-to-one matching markets with incentive compatibility , author=. Proceedings of the AAAI Conference on Artificial Intelligence , pages=

  60. [62]

    Bandit Algorithms , publisher=

    Lattimore, Tor and Szepesvári, Csaba , year=. Bandit Algorithms , publisher=

  61. [63]

    Even-Dar, Eyal and Mannor, Shie and Mansour, Yishay , title =. J. Mach. Learn. Res. , month =. 2006 , issue_date =

    2006

  62. [65]

    Proceedings of the fifteenth ACM conference on Economics and computation , pages=

    Reasoning about optimal stable matchings under partial information , author=. Proceedings of the fifteenth ACM conference on Economics and computation , pages=

  63. [66]

    Proceedings of the fourteenth ACM conference on Electronic Commerce , pages=

    Two-sided matching with partial information , author=. Proceedings of the fourteenth ACM conference on Electronic Commerce , pages=

  64. [67]

    The Journal of Machine Learning Research , volume=

    On the complexity of best-arm identification in multi-armed bandit models , author=. The Journal of Machine Learning Research , volume=. 2016 , publisher=

    2016

  65. [68]

    Conference on Learning Theory , pages=

    Optimal best arm identification with fixed confidence , author=. Conference on Learning Theory , pages=. 2016 , organization=

    2016

  66. [69]

    2020 , publisher=

    Bandit algorithms , author=. 2020 , publisher=

    2020

  67. [70]

    Proceedings of the 15th Annual Conference on Computational Learning Theory , pages =

    Even-Dar, Eyal and Mannor, Shie and Mansour, Yishay , title =. Proceedings of the 15th Annual Conference on Computational Learning Theory , pages =. 2002 , isbn =

    2002

  68. [71]

    Biometrika , volume=

    On the likelihood that one unknown probability exceeds another in view of the evidence of two samples , author=. Biometrika , volume=. 1933 , publisher=

    1933

  69. [72]

    Journal of Machine Learning Research , volume=

    The sample complexity of exploration in the multi-armed bandit problem , author=. Journal of Machine Learning Research , volume=

  70. [73]

    2013 , doi =

    Manlove, David F , title =. 2013 , doi =

    2013

  71. [74]

    Proceedings of the 2019 ACM Conference on Economics and Computation , pages=

    Stable fractional matchings , author=. Proceedings of the 2019 ACM Conference on Economics and Computation , pages=

    2019

  72. [75]

    2024 IEEE International Symposium on Information Theory (ISIT) , pages=

    Explore-then-commit algorithms for decentralized two-sided matching markets , author=. 2024 IEEE International Symposium on Information Theory (ISIT) , pages=. 2024 , organization=

    2024

  73. [76]

    Proceedings of The 27th Conference on Learning Theory , pages =

    lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits , author =. Proceedings of The 27th Conference on Learning Theory , pages =. 2014 , editor =

    2014

  74. [77]

    Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence , pages =

    Decentralized Two-Sided Bandit Learning in Matching Market , author =. Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence , pages =. 2024 , editor =

    2024

  75. [79]

    Discrete applied mathematics , volume=

    The set of super-stable marriages forms a distributive lattice , author=. Discrete applied mathematics , volume=. 1995 , publisher=

    1995

  76. [80]

    Algorithmic Learning Theory , pages=

    Efficient pure exploration for combinatorial bandits with semi-bandit feedback , author=. Algorithmic Learning Theory , pages=. 2021 , organization=

    2021

  77. [81]

    1989 , publisher=

    The stable marriage problem: structure and algorithms , author=. 1989 , publisher=

    1989

  78. [82]

    Probably correct optimal stable matching for two-sided market under uncertainty

    Andreas Athanasopoulos, Anne-Marie George, and Christos Dimitrakakis. Probably correct optimal stable matching for two-sided market under uncertainty. In Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems, AAMAS '25, page 152–160, Richland, SC, 2025. International Foundation for Autonomous Agents and Multiagent Sy...

    2025

  79. [83]

    Competing bandits in matching markets via super stability

    Soumya Basu. Competing bandits in matching markets via super stability. In Forty-second International Conference on Machine Learning, 2025. URL https://openreview.net/forum?id=mNxjoMiFFf

    2025

  80. [84]

    Beyond log^2(t) regret for decentralized bandits in matching markets

    Soumya Basu, Karthik Abinav Sankararaman, and Abishek Sankararaman. Beyond log^2(t) regret for decentralized bandits in matching markets. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 705--715, Virtual, 18--24 Jul 2021. PMLR. URL ...

    2021

Showing first 80 references.