多智能体协作学习中实现安全探索,性能接近最优。
Multi-Agent Stage-wise Conservative Linear Bandits
- 分阶段交替选择动作与共识协商,保障每轮收益不低于基线的1-α倍
- 理论证明在合理连通网络下,累积后悔项为O(d/√N √T log(NT)/√log(1/|λ₂|))
- 通信开销低,适合分布式推荐等需安全约束的系统
在推荐系统等真实场景中,多个学习智能体需在探索与利用间权衡,并满足阶段性的安全约束以避免灾难性失败。本文研究多智能体网络中的随机线性贝叶斯问题,要求每个回合的期望收益不低于基线策略的(1−α)倍。共有N个智能体,各自观测局部奖励(参数未知),但网络整体优化全局参数(局部参数平均值)。智能体仅与邻近节点通信,每次通信引入额外后悔。提出MA-SCLUCB算法,采用分周期的行动选择与共识构建交替机制。理论上证明该算法以高概率达到 ilde{O}ig(rac{d}{\\(sqrt{N}}\sqrt{T}\cdot\frac{\log(NT)}{\sqrt{\log(1/|λ_2|)}}\big)的后悔上界,其中d为维度,T为时间跨度,|λ₂|为网络第二大方阵特征值的绝对值。分析表明:(i) 即便局部通信,协作仍带来1/√N的性能提升;(ii) 对于连接良好的网络,通信开销仅对数增长;(iii) 阶段性安全约束仅引入低阶后悔。因此,在适度连通网络中,具备安全保证的分布式学习可实现近似最优性能。
原文摘要 · Abstract (English)
In many real-world applications such as recommendation systems, multiple learning agents must balance exploration and exploitation while maintaining safety guarantees to avoid catastrophic failures. We study the stochastic linear bandit problem in a multi-agent networked setting where agents must satisfy stage-wise conservative constraints. A network of $N$ agents collaboratively maximizes cumulative reward while ensuring that the expected reward at every round is no less than $(1-α)$ times that of a baseline policy. Each agent observes local rewards with unknown parameters, but the network optimizes for the global parameter (average of local parameters). Agents communicate only with immediate neighbors, and each communication round incurs additional regret. We propose MA-SCLUCB (Multi-Agent Stage-wise Conservative Linear UCB), an episodic algorithm alternating between action selection and consensus-building phases. We prove that MA-SCLUCB achieves regret $\tilde{O}\left(\frac{d}{\sqrt{N}}\sqrt{T}\cdot\frac{\log(NT)}{\sqrt{\log(1/|λ_2|)}}\right)$ with high probability, where $d$ is the dimension, $T$ is the horizon, and $|λ_2|$ is the network's second largest eigenvalue magnitude. Our analysis shows: (i) collaboration yields $\frac{1}{\sqrt{N}}$ improvement despite local communication, (ii) communication overhead grows only logarithmically for well-connected networks, and (iii) stage-wise safety adds only lower-order regret. Thus, distributed learning with safety guarantees achieves near-optimal performance in reasonably connected networks.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。