Beyond log(T) regret for decentralized bandits in matching markets

Soumya Basu, Karthik Abinav Sankararaman, Abishek Sankararaman

Introduction

Decentralized matching markets—such as gig economy platforms like TaskRabbit or UpWork—rely on agents learning their preferences through trial and error. This paper breaks new ground by introducing two novel algorithms that significantly reduce "regret" (the cost of learning) in these environments. By effectively solving the "deadlocks" that previously stalled decentralized learning, the authors achieve near-optimal performance even when agents cannot communicate and possess heterogeneous preferences.

The Challenge of Decentralized Matching

In a classic two-sided matching market, agents (e.g., workers) and arms (e.g., tasks) have preferences for one another. The gold standard is a "stable matching," where no pair would rather deviate to be with each other over their current partners. While the classic Gale-Shapley model assumes everyone knows their preferences upfront, real-world scenarios often require learning these preferences through interaction—a multi-armed bandit setting.

The primary challenge here is decentralization. In a fully decentralized market, agents lack a central coordinator and cannot observe the actions of others. They only receive limited bandit feedback: either the reward from a successful match, or a "collision" indicator if they were rejected because the arm preferred someone else. Prior decentralized approaches either required a central arbiter, assumed homogeneous preferences across all agents (serial dictatorship), or suffered from high regret bounds of $O(\log^2(T))$. This paper aims to push regret down toward the theoretical limit of $O(\log(T))$ for a broader class of markets.

Algorithmic Innovations

The authors propose two primary algorithmic frameworks to tackle these challenges:

1. Phased Explore-Then-Commit (Phased ETC)

Designed for general markets, this algorithm operates in exponentially growing phases. At the start of each phase, agents follow a collision-free exploration protocol to estimate rewards. They then use these estimates to run a decentralized version of the Gale-Shapley algorithm, allowing them to "commit" to a stable matching for the remainder of the phase.

2. UCB-D4 (UCB Decentralized Dominate-Delete with Local Deletions)

Tailored for markets satisfying "Uniqueness Consistency" (where the stable match remains robust even if some participants leave), UCB-D4 is the standout contribution of the paper. It introduces a pivotal Local Deletion step. If an agent collides with a specific arm too frequently—above a calculated threshold—they locally delete that arm from their preference list. This mechanism effectively breaks "deadlocks" where agents block each other indefinitely due to rank heterogeneity.

Key Insights and Theoretical Guarantees

  • Breaking Deadlocks: Local deletion is a crucial insight. In decentralized settings with heterogeneous preferences, agents can get stuck in infinite loops, repeatedly trying for arms they will never secure. By aggressively pruning arms that cause frequent collisions, agents "clear the way" for one another, enabling exploration of better, available options.
  • The $\alpha$-Condition: The authors utilize the $\alpha$-condition, a combinatorial property ensuring a unique stable matching. They demonstrate that this condition creates a "dual induction" structure—a specific order for agents and arms—that guides the decentralized system to converge step-by-step.
  • Agent-Optimal Matching: Unlike previous decentralized algorithms that often settled for "agent-pessimal" outcomes (the worst stable match for the agents), this work specifically targets and achieves the agent-optimal stable matching.
  • Regret Bounds: For general markets, Phased ETC achieves $O(\log^{1+\epsilon}(T))$ regret for any $\epsilon > 0$, a strict improvement over the prior $O(\log^2(T))$ state-of-the-art. For Uniqueness Consistency markets, UCB-D4 achieves the optimal $O(\log(T))$ regret.

Empirical Validation

The paper relies on synthetic simulations to evaluate the algorithms, generating random market instances with 5 agents and 6 arms across various market conditions. In general settings, Phased ETC outperformed existing decentralized algorithms like CA-UCB. In markets with unique stable matchings, UCB-D4 performed nearly as well as centralized algorithms that have access to vastly more information. Furthermore, unlike some previous methods that scaled exponentially with the number of agents, UCB-D4’s regret scales polynomially, making it highly practical for larger markets.

Limitations and Future Directions

While the theoretical guarantees are strong, the paper identifies a few open challenges. The Phased ETC algorithm suffers from a "cold-start" problem, requiring a very long time horizon ($T$) to become effective due to an exponential dependence on the minimum reward gap ($\Delta$). This limits its immediate applicability in short-lived markets. Additionally, while UCB-D4 is optimal for uniqueness-consistent markets, achieving $O(\log(T))$ regret for entirely general decentralized markets without an exponential penalty remains a key direction for future research.

Summary updated

Abstract

We design decentralized algorithms for regret minimization in the two sided matching market with one-sided bandit feedback that significantly improves upon the prior works (Liu et al.\,2020a, Sankararaman et al.\,2020, Liu et al.\,2020b). First, for general markets, for any $\varepsilon > 0$, we design an algorithm that achieves a $O(\log^{1+\varepsilon}(T))$ regret to the agent-optimal stable matching, with unknown time horizon $T$, improving upon the $O(\log^{2}(T))$ regret achieved in (Liu et al.\,2020b). Second, we provide the optimal $\Theta(\log(T))$ agent-optimal regret for markets satisfying {\em uniqueness consistency} – markets where leaving participants don’t alter the original stable matching. Previously, $\Theta(\log(T))$ regret was achievable (Sankararaman et al.\,2020, Liu et al.\,2020b) in the much restricted {\em serial dictatorship} setting, when all arms have the same preference over the agents. We propose a phase based algorithm, where in each phase, besides deleting the globally communicated dominated arms the agents locally delete arms with which they collide often. This \emph{local deletion} is pivotal in breaking deadlocks arising from rank heterogeneity of agents across arms. We further demonstrate superiority of our algorithm over existing works through simulations.
BibTeX
@inproceedings{basu2021beyond,
  author = {Soumya Basu and Karthik Abinav Sankararaman and Abishek Sankararaman},
  title = {{Beyond log(T) regret for decentralized bandits in matching markets}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=C42sGQIXwo},
}
Figure