We study regret minimization problems in a two-sided matching market where uniformly valued demand side agents (a.k.a. agents) continuously compete for getting matched with supply side agents (a.k.a. arms)with unknown and heterogeneous valuations. Such markets abstract online matching platforms ( for e.g. UpWork, TaskRabbit) and falls within the purview of matching bandit models introduced in Liu et al. \mbox{%DIFAUXCMD matching_bandits the demand side admits a unique stable matching equilibrium in the system . We design the first decentralized algorithm -%DIFDELCMD < \fullname%%% \; (%DIFDELCMD < \name%%%  ), for matching bandits under uniform valuation that does not require any knowledge of reward gaps or time horizon , and thus partially resolves an open question in \mbox{%DIFAUXCMD \cite{matching_bandits}\hspace{0pt}%DIFAUXCMD . }%DIFDELCMD < \name%%% \; works in phases of exponentially increasing length. In each phasei, an agent first deletes dominated arms\emph{ -- the arms preferred by agents ranked higher than itself. Deletion follows dynamic explore-exploit using UCB algorithm on the remaining arms for 2^i rounds. Finally, the preferred arm is broadcast in a decentralized fashion to other agents through {\em pure exploitation} in (N-1)K rounds with N agents and K arms. Comparing the obtained reward with respect to the unique stable matching, we show that%DIFDELCMD < \name%%% \; achieves O(\log(T)/\Delta^2) regret in T rounds, where \Delta is the minimum gap across all agents and arms. We provide a (orderwise) matching regret lower-bound .
Online learning in a two-sided matching market , with demand side agents continuously competing to be matched with supply side (arms), abstracts the complex interactions under partial information on matching platforms ( e.g. UpWork, TaskRabbit) . We study the decentralized serial dictatorship setting, a two-sided matching market where the demand side agents have unknown and heterogeneous valuation over the supply side (arms), while the arms have known uniform preference over the demand side (agents) . We design the first decentralized algorithm %DIFDELCMD < \fullname%%% %DIFDELCMD < \name%%% -- UCB with Decentralized Dominant-arm Deletion (UCB-D3 ), for the agents, that does not require any knowledge of reward gaps or time horizon }\hspace{0pt}%DIFAUXCMD . }%DIFDELCMD < \name%%% . UCB-D3 works in phases , where in each phase, agents delete\emph{dominated arms -- the arms preferred by higher ranked agents, and play only from the non-dominated arms according to the UCB. At the end of the phase, agents broadcast in a decentralized fashion , their estimated preferred arms through {\em pure exploitation} %DIFDELCMD < \name%%% . We prove both, a new regret lower bound for the decentralized serial dictatorship model, and that UCB-D3 is order optimal .
R
We study regret minimization problems
Online learning
R
where uniformly valued
, with
R
(a.k.a. agents) continuously compete for getting
continuously competing to be
R
agents (a.k.a. arms)with unknown and heterogeneous valuations. Such markets abstract online
(arms), abstracts the complex interactions under partial information on
D
for
R
and falls within the purview of matching bandit models introduced in Liu et al. \mbox{%DIFAUXCMD matching_bandits
. We study the decentralized serial dictatorship setting, a two-sided matching market where
R
admits a unique stable matching equilibrium in the system
agents have unknown and heterogeneous valuation over the supply side (arms), while the arms have known uniform preference over the demand side (agents)
D
-
D
\; (
A
-- UCB with Decentralized Dominant-arm Deletion (UCB-D3
R
matching bandits under uniform valuation
the agents,
D
, and thus partially resolves an open question in \mbox{%DIFAUXCMD \cite{matching_bandits
R
\;
. UCB-D3
R
of exponentially increasing length. In each phasei, an agent first deletes dominated arms
, where in each phase, agents delete
A
dominated arms
D
agents ranked higher than itself. Deletion follows dynamic explore-exploit using UCB algorithm on the remaining arms for 2^i rounds.
R
Finally, the preferred arm is
higher ranked agents, and play only from the non-dominated arms according to the UCB. At the end of the phase, agents
R
to other agents
, their estimated preferred arms
D
in (N-1)K rounds with N agents and K arms.
D
Comparing the obtained reward with respect to the unique stable matching, we show that
R
\; achieves O(\log(T)/\Delta^2) regret in T rounds, where \Delta is the minimum gap across all agents and arms. We provide a (orderwise) matching regret lower-bound
. We prove both, a new regret lower bound for the decentralized serial dictatorship model, and that UCB-D3 is order optimal