Research map / Reinforcement learning / Visual and representation RL
Online Matching with Stochastic Rewards: Provable Better Bound via Adversarial Reinforcement Learning
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.
Adversarial RL (cross-entropy-trained adversary vs. algorithm agent) explores hard instances for online matching with stochastic rewards, yielding structural properties that tighten the known upper bound from 0.621 to 0.597.
Problem
Online matching with stochastic rewards (OMSR) has an unknown optimal competitive ratio, with a best known hardness upper bound of 0.621 and best algorithmic lower bound of 0.572-0.576; it is unclear whether RL can help understand problem hardness.
Approach
Train an adversary RL agent to generate worst-case OMSR instances against an algorithm agent, iteratively with an algorithm agent trained on those instances; distill consistency and exclusivity structural properties from learned instance patterns to reduce the action space and prove an improved hardness bound.
Key results
- Proves no algorithm for OMSR exceeds competitive ratio 0.597 (improving the 0.621 hardness bound from FOCS 2012), with the bound attained at n=7 in the learned instance family.
- Learned algorithm's average CR converges to 0.635 for equal probabilities (Balance: 0.615) and 0.614 for unequal probabilities (Balance: 0.594) on worst-case distributions with n=6.
- Learned adversarial instances are harder than Thick-z, Triangular, and MP12 instances for the learned algorithm.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use adversarial RL-learned graph patterns to construct hard instances | OMSR hardness analysis · OMSR | competitive ratio upper bound: 0.621 -> 0.597 | Helped |
| Train the algorithm agent adversarially against hard instances | OMSR algorithm design · OMSR, equal probabilities, worst-case distributions (n=6) | average competitive ratio: 0.615 -> 0.635 | Helped |
| Train the algorithm agent adversarially against hard instances | OMSR algorithm design · OMSR, unequal probabilities, worst-case distributions (n=6) | average competitive ratio: 0.594 -> 0.614 | Helped |
Surprising findings
- Learned algorithm and Balance perform almost identically when success probability is vanishingly small (p=1/40), suggesting Balance may be optimal in that regime.
Limitations
- Theoretical proof uses a weaker bound of 0.61 on G3 in the main text; the 0.597 result relies on the learned family G_n with n=7 and the restricted infinitesimal-probability setting.
- Hard to summarize what the learned algorithm does, so the algorithmic lower bound is not improved theoretically.
Experimental setup
Benchmarks: OMSR hard instances G_n Thick-z graphs Triangular graphs
Metrics: competitive ratio
Baselines: Balance Thick-z graph Triangular graph MP12 worst-case instance
Builds on: Pinto et al. 2017 robust adversarial RL Balance algorithm (Huang & Zhang 2020) Kong et al. 2019 RL for online algorithms Alomrani et al. 2021
Closest papers by meaning
- DiMa: Understanding the Hardness of Online Matching Problems via Diffusion Models (ICML 2025 · similarity 0.90)
- Learning for Edge-Weighted Online Bipartite Matching with Robustness Guarantees (ICML 2023 · similarity 0.90)
- Bandit Learning in Matching Markets Robust to Adversarial Corruptions (ICLR 2026 · similarity 0.89)
- Online Reinforcement Learning in Stochastic Games (NeurIPS 2017 · similarity 0.88)
- Online bipartite matching with imperfect advice (ICML 2024 · similarity 0.88)
- Improved Bandits in Many-to-One Matching Markets with Incentive Compatibility (AAAI 2024 · similarity 0.86)
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.