提出两种自适应网络共享的上下文线性强化学习算法,降低通信开销并提升学习效率。
Decentralized Contextual Bandits with Network Adaptivity
- 基于动态网络权重实现全局与局部信息的分层共享
- 在 $N$ 个节点网络中将学习复杂度从 $O(N)$ 降至 $O(\ oot{2}{N})$
- 适用于多地点协同决策,尤其适合噪声低或高维场景
我们研究网络上的上下文线性马尔可夫决策问题,即多个位置同时学习,奖励分布具有结构性相似性但存在局部差异。传统方法要么完全集中,要么完全孤立,而网络环境中部分信息共享仍待探索。本文提出两种网络感知的上置信界(UCB)算法:NetLinUCB 和 Net-SGD-UCB,通过动态更新的网络权重实现自适应信息共享。方法将学习分解为全局与局部成分,使代理在无需全同步的情况下受益于共享结构。相比完全集中式设置,通信成本更低,仅需共享关于同质特征的计算摘要。理论分析表明,共享结构带来的学习复杂度由 $O(N)$ 降低至子线性 $O(\sqrt{N})$,其中 $N$ 为网络规模。两种算法各具优势:NetLinUCB 在低噪声、细粒度异质性下表现更优;Net-SGD-UCB 对高维、高方差上下文更具鲁棒性。在模拟定价场景中,相比标准基准,本方法显著提升性能。
原文摘要 · Abstract (English)
We consider contextual linear bandits over networks, a class of sequential decision-making problems where learning occurs simultaneously across multiple locations and the reward distributions share structural similarities while also exhibiting local differences. While classical contextual bandits assume either fully centralized data or entirely isolated learners, much remains unexplored in networked environments when information is partially shared. In this paper, we address this gap by developing two network-aware Upper Confidence Bound (UCB) algorithms, NetLinUCB and Net-SGD-UCB, which enable adaptive information sharing guided by dynamically updated network weights. Our approach decompose learning into global and local components and as a result allow agents to benefit from shared structure without full synchronization. Both algorithms incur lighter communication costs compared to a fully centralized setting as agents only share computed summaries regarding the homogeneous features. We establish regret bounds showing that our methods reduce the learning complexity associated with the shared structure from $O(N)$ to sublinear $O(\sqrt{N})$, where $N$ is the size of the network. The two algorithms reveal complementary strengths: NetLinUCB excels in low-noise regimes with fine-grained heterogeneity, while Net-SGD-UCB is robust to high-dimensional, high-variance contexts. We further demonstrate the effectiveness of our methods across simulated pricing environments compared to standard benchmarks.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。