  We study the problem of online learning in two-sided non-stationary matching
markets, where the objective is to converge to a stable match. In particular,
we consider the setting where one side of the market, the arms, has fixed known
set of preferences over the other side, the players. While this problem has
been studied when the players have fixed but unknown preferences, in this work
we study the problem of how to learn when the preferences of the players are
time varying and unknown. Our contribution is a methodology that can handle any
type of preference structure and variation scenario. We show that, with the
proposed algorithm, each player receives a uniform sub-linear regret of
{$\widetilde{\mathcal{O}}(L^{1/2}_TT^{1/2})$} up to the number of changes in
the underlying preferences of the agents, $L_T$. Therefore, we show that the
optimal rates for single-agent learning can be achieved in spite of the
competition up to a difference of a constant factor. We also discuss extensions
of this algorithm to the case where the number of changes need not be known a
priori.
