Communication-Efficient Decentralized Contextual X -Armed Bandit Learning in Multi-Agent Stochastic Networks

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 -