The stable matching problem for multi-user spectrum access was first introduced in [1]} under the assumption that the expected rates are known, and a distributed opportunistic CSMA algorithm that solves the problem was proposed. The model with an unknown expected rate matrix and rested setting (i.e., the states of the Markovian process do not change if not observed by the user) was studied in [2]}, [3]}. A regret (with respect to the optimal allocation) of near-\(O(\log t)\)  was achieved. However, these algorithms require intensive communication between users in order to apply the auction algorithm [4]}. In [5]}, the authors reduced the communication burden, but without guarantees on the achievable regret. Recently, it was shown in [6]}, [7]} that achieving a sum-regret of near- \(O(\log t)\)  is possible without communication between users, but only for the case of i.i.d channels. In this paper we focus on the general case where the channel states may change whether or not they are being observed (i.e., the restless Markovian setting), and improve the regret scaling with the system parameters by a simple distributed implementation. The main contributions are summarized below.
