mlsanityData to 14 Oct 2026

Learn to Match with No Regret: Reinforcement Learning in Markov Matching Markets

arXiv 2203.03684 ↗First posted 7 Mar 2022cs.LG cs.AI cs.GTcited by 16

Not on the map. Why?

Abstract (arXiv)

We study a Markov matching market involving a planner and a set of strategic agents on the two sides of the market. At each step, the agents are presented with a dynamical context, where the contexts determine the utilities. The planner controls the transition of the contexts to maximize the cumulative social welfare, while the agents aim to find a myopic stable matching at each step. Such a setting captures a range of applications including ridesharing platforms. We formalize the problem by proposing a reinforcement learning framework that integrates optimistic value iteration with maximum weight matching. The proposed algorithm addresses the coupled challenges of sequential exploration, matching stability, and function approximation. We prove that the algorithm achieves sublinear regret.

Key facts. Cited by 16 papers in the map (data through 14 Oct 2026). Builds on 31 of its 93 references that are in the map. First posted on arXiv 7 Mar 2022.

Builds on

31 of 93 references.

References · 31

  1. 2017Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networkscited by 4,897
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  3. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  4. 2018Is Q-learning Provably Efficient?cited by 487
  5. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
  6. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 223
  7. 2019Provably Efficient Exploration in Policy Optimizationcited by 205
  8. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
  9. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 181
  10. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 178
  11. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 176
  12. 2013Risk-sensitive Reinforcement Learningcited by 130
19 more
  1. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  2. 2014Generalization and Exploration via Randomized Value Functionscited by 112
  3. 2019Provably Efficient Q-Learning with Low Switching Costcited by 78
  4. 2020Risk-Sensitive Reinforcement Learning: Near-Optimal Risk-Sample Tradeoff in Regretcited by 58
  5. 2019Competing Bandits in Matching Marketscited by 56
  6. 2020Bandit Learning in Decentralized Matching Marketscited by 46
  7. 2021Exponential Bellman Equation and Improved Regret Bounds for Risk-Sensitive Reinforcement Learningcited by 43
  8. 2021A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Costcited by 40
  9. 2021Variance-Aware Off-Policy Evaluation with Linear Function Approximationcited by 34
  10. 2021Learning Equilibria in Matching Markets from Bandit Feedbackcited by 34
  11. 2021Beyond log2(T) Regret for Decentralized Bandits in Matching Marketscited by 30
  12. 2021Learning Stochastic Shortest Path with Linear Function Approximationcited by 23
  13. 2021Regret, stability & fairness in matching markets with bandit learnerscited by 20
  14. 2018On the Landscape of Synchronization Networks: A Perspective from Nonconvex Optimizationcited by 11
  15. 2020Meta Learning in the Continuous Time Limitcited by 10
  16. 2018Dynamic Type Matchingcited by 8
  17. 2021Data Sharing Marketscited by 5
  18. 2014Dynamic Matching Market Designcited by 2
  19. 2020Stability in Repeated Matching Marketscited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 2; 2023: 5; 2024: 4; 2025: 4; 2026: 1.

16 papers.

Sort:

By area:

  1. 2022Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processescited by 26
  2. 2023Player-optimal Stable Regret for Bandit Learning in Matching Marketscited by 17
  3. 2023Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximationcited by 9
  4. 2024Putting Gale & Shapley to Work: Guaranteeing Stability Through Learningcited by 7
  5. 2023Two-sided Competing Matching Recommendation Markets With Quota and Complementary Preferences Constraintscited by 5
  6. 2023Fairness in Matching under Uncertaintycited by 5
  7. 2023Finding Regularized Competitive Equilibria of Heterogeneous Agent Macroeconomic Models with Reinforcement Learningcited by 4
  8. 2022Competing Bandits in Time Varying Matching Marketscited by 3
  9. 2024Competing Bandits in Decentralized Contextual Matching Marketscited by 1
  10. 2025Optimal Analysis for Bandit Learning in Matching Markets with Serial Dictatorshipcited by 1
  11. 2024Taming Equilibrium Bias in Risk-Sensitive Multi-Agent Reinforcement Learningcited by 0
  12. 2024Centralized Selection with Preferences in the Presence of Biasescited by 0
4 more
  1. 2025Hierarchical Reinforcement Learning for Optimal Agent Grouping in Cooperative Systemscited by 0
  2. 2025Linear Bandits beyond Inner Product Spaces, the case of Bandit Optimal Transportcited by 0
  3. 2025EMERGENT: Efficient and Manipulation-resistant Matching using GFlowNetscited by 0
  4. 2026Learn to Match: Two-Sided Matching with Temporally Extended Feedbackcited by 0