TY - JOUR
T1 - Communication-Efficient Decentralized Contextual X -Armed Bandit Learning in Multi-Agent Stochastic Networks
AU - Li, Youqi
AU - Li, Fan
AU - Zhou, Pan
AU - Wang, Yu
N1 - Publisher Copyright:
© 2025 IEEE.
PY - 2026
Y1 - 2026
N2 - 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 contextual X-armed bandit, where N agents collaboratively solve the problem within time span T. The problem is nontrivial because the infinite arms challenge and statistical information consensus issue make our setting go beyond a simple combination of X-armed bandits and multi-agent bandits. We develop a decentralized arm selection algorithm, called MACXUCB, by elaborating the contextual covering tree technique with a novel gossip communication protocol, which allows each agent to communicate efficiently with her neighbors. We prove that MACXUCB achieves a sublinear regret upper bound (Formula present) given aggregation period D, and the covering dimensions dX and dY of arm and context spaces, which asymptomatically matches the lower bound (Formula present) up to a time-dependent factor. Moreover, MACXUCB enjoys a sublinear communication complexity Oe(NDT0.5/(1-X)) when tuning parameter X X (0, 12 ). Finally, we carry out experiments to verify the performance of our MACXUCB. The results show the effectiveness and efficiency of our MACXUCB.
AB - 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 contextual X-armed bandit, where N agents collaboratively solve the problem within time span T. The problem is nontrivial because the infinite arms challenge and statistical information consensus issue make our setting go beyond a simple combination of X-armed bandits and multi-agent bandits. We develop a decentralized arm selection algorithm, called MACXUCB, by elaborating the contextual covering tree technique with a novel gossip communication protocol, which allows each agent to communicate efficiently with her neighbors. We prove that MACXUCB achieves a sublinear regret upper bound (Formula present) given aggregation period D, and the covering dimensions dX and dY of arm and context spaces, which asymptomatically matches the lower bound (Formula present) up to a time-dependent factor. Moreover, MACXUCB enjoys a sublinear communication complexity Oe(NDT0.5/(1-X)) when tuning parameter X X (0, 12 ). Finally, we carry out experiments to verify the performance of our MACXUCB. The results show the effectiveness and efficiency of our MACXUCB.
KW - Contextual X
KW - RKHS
KW - armed bandit
KW - cooperation
KW - gossip communication
KW - multi-agent
UR - https://www.scopus.com/pages/publications/105032167189
U2 - 10.1109/TON.2026.3669909
DO - 10.1109/TON.2026.3669909
M3 - Article
AN - SCOPUS:105032167189
SN - 1063-6692
VL - 34
SP - 4042
EP - 4057
JO - IEEE/ACM Transactions on Networking
JF - IEEE/ACM Transactions on Networking
ER -