Communication-Efficient Decentralized Contextual $\mathcal{X}$ -Armed Bandit Learning in Multi-Agent Stochastic Networks

Bandit with infinitely many arms (i.e.,X-armed bandit) is an important variant of multi-armed stochastic bandits, which is useful to model different networking problems under both wired and wireless settings, e.g., online caching, dynamic channel/power allocation, rate adaption. However, the problem becomes challenging when the characteristic of the networking setting is affected by the side information (i.e., context) and distributed behavior. In this paper, we identify and study a novel problem, decentralized contextualX-armed bandit, whereNagents collaboratively solve the problem within time spanT. The problem is nontrivial because the infinite arms challenge and statistical information consensus issue make our setting go beyond a simple combination ofX-armed bandits and multi-agent bandits. We develop a decentralized arm selection algorithm, called MACXUCB, by elaborating the contextual covering tree technique with a novelgossip communication protocol, which allows each agent to communicate efficiently with her neighbors. We prove that MACXUCB achieves a sublinear regret upper bound Õ(D1/2dX+2dY+4NdX+dY+1.5/dX+dY+2TdX+dY+1/dX+dY+2) given aggregation periodD, and the covering dimensionsdXanddYof arm and context spaces, which asymptomatically matches the lower bound Ω((DN)1/dX+dY+2TdX+dY+1/dX+dY+2) up to a time-dependent factor. Moreover, MACXUCB enjoys a sublinear communication complexity Õ(NDT0.5/(1–p)) when tuning parameterp∈ (0, 1/2). Finally, we carry out experiments to verify the performance of our MACXUCB. The results show the effectiveness and efficiency of our MACXUCB.