Decentralized Bandit Learning in Matching Markets

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2219 papers265 conceptsfrozen 2026-10-04

In a classic multi-armed bandit problem, a single agent tries to find the best resource by trial and error. But in the real world—from wireless devices competing for frequency channels to drivers searching for parking spots—we rarely act in a vacuum. We are usually part of a crowd of agents, all learning and competing for the same limited resources simultaneously.

The challenge in these decentralized environments is a phenomenon called a collision. If two agents attempt to use the same resource at the same time, they often interfere with each other, resulting in zero utility for everyone involved. To maximize efficiency, agents must not only learn which resources are high-quality but also learn how to "match" with them in a way that avoids others.

The Learning Coordination Dilemma

In centralized systems, a "god-eye" controller can simply assign agents to resources. However, in decentralized markets, agents often lack a central authority and cannot communicate directly. This creates a fundamental tension: to learn which resource is best, an agent must explore; but if every agent explores the same "best" resource, they will constantly collide, stalling their learning and wasting effort.

As Shuai Li and Zilong Wang note in A Survey on Bandit Learning in Matching Markets, this creates a unique form of "competitive regret." Agents aren't just losing out because they picked a bad arm; they are losing out because they failed to coordinate their choices with their peers.

Signaling Through Collisions

One of the most elegant solutions to this problem is to treat the collisions themselves as a form of communication. Since agents cannot send messages over a dedicated channel, they can use their actions to "signal" their intentions.

In An Optimal Algorithm in Multiplayer Multi-Armed Bandits, Alexandre Proutiere and Po-An Wang introduce the Decentralized Parsimonious Exploration (DPE) algorithm. DPE establishes a "leader-follower" dynamic. The agents use a specific protocol of intentional collisions to "vote" on assignments. By intentionally bumping into a specific arm at a specific time, an agent can signal its preference to the rest of the group. This allows the system to reach the same efficiency as a centralized controller using only a finite number of communication rounds.

Phased Exploration and Exploitation

Another way to bypass the collision problem is to structure when agents are allowed to learn. If agents explore at random times, the environment becomes "noisy" and unpredictable.

Dileep Kalathil and Rahul Jain proposed the $E^3$ (Exponentially-spaced Exploration and Exploitation) framework in On Regret-Optimal Learning in Decentralized Multiplayer Multiarmed Bandits. The intuition is to separate time into distinct phases. During exploration phases, agents try different arms to estimate their rewards. During exploitation phases, which grow exponentially longer over time, agents stick to their best-estimated "orthogonal" (non-conflicting) assignment. Because the exploitation phases grow so quickly, the cost of the occasional collision during exploration becomes negligible, allowing the group to achieve near-optimal "logarithmic regret."

Leveraging Market Structures

Sometimes, the structure of the market itself provides the coordination needed to avoid collisions. In Bandit Learning in Housing Markets, Shiyun Lin demonstrates that "initial endowments"—the resources agents already own—act as a natural anchor. Agents can use their starting resources as a safe home base, exploring other options only when they are sure they won't interfere with someone else's "property."

Similarly, Orly Avner and Shie Mannor framed the problem as a Stable Marriage task in Learning to coordinate without communication in multi-user multi-armed bandit problems. By applying Gale-Shapley-style logic to the bandit setting, they showed that agents can converge to a stable, collision-free configuration simply by observing whether their "proposal" to a resource was accepted or rejected.

From Theory to Physical Systems

These abstract mechanisms solve very concrete problems in distributed infrastructure:

  • Cognitive Radio: In Online Learning in Opportunistic Spectrum Access, Cem Tekin and Mingyan Liu show how wireless devices can learn to pick idle frequency channels without a central tower, even when those channels are "restless" and change state over time.
  • Urban Mobility: Niklas Alexander Strauß and colleagues demonstrate in Efficient Parking Search using Shared Fleet Data that even "selfish" agents can reduce collective search times by 84% if they share their intended destinations, effectively "reserving" resources to prevent others from even trying to compete for them.
  • Robotics and Satellites: Frameworks like REDA, developed by Joshua Holder, combine reinforcement learning with classical assignment solvers. By having agents learn the value of tasks but offloading the final selection to a conflict-resolution algorithm, these systems ensure that no two robots ever target the same objective simultaneously.

By treating coordination as a learning problem rather than just a communication problem, this research direction enables large-scale, autonomous systems to function efficiently in crowded, competitive environments.

Papers in this version

Showing 60 of 219 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 104 papers
  2. Version 1 · 2026-10-04 · 219 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_decentralized_resource_contention_dce2ba04,
  title = {decentralized resource contention},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/decentralized-resource-contention/rdr_dce2ba04cb2f43128a0214ed95307d9b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_decentralized_bandit_learning_in_matchin_dce2ba04_v1,
  title = {Decentralized Bandit Learning in Matching Markets},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/decentralized-bandit-learning-in-matching-markets/rdr_dce2ba04cb2f43128a0214ed95307d9b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}