多智能体强化学习在信息不对称下实现接近单智能体的性能。
Decentralized Multi-Player Q-Learning in Episodic Markov Decision Processes with Information Asymmetry
- 设计了三种去中心化Q-learning算法，适应不同信息结构。
- 在小规模玩家或动作空间下达到近似最优的后悔率。
- 适用于无法通信但可预设协议的多智能体协同场景。
我们研究了在具有三种信息不对称情形下的去中心化多玩家强化学习：(A) 共享奖励下不可观测动作，(B) 可观测动作但独立奖励，(C) 不可观测动作且独立奖励。玩家学习期间无法通信，但可预先约定协议。针对问题A和B，提出 exttt{mQ-learning} 和 exttt{mQ-learning-intervals}，实现 $ ilde{O}( oot{4}{H^4 S A_{ ext{joint}} T})$ 的后悔界，其中 $H$ 为时长远，$S$ 为状态数，$T = KH$ 为总步数，$A_{ ext{joint}} = igprod_{i=1}^M |oldsymbol{ extcal{A}}_i|$ 为联合动作空间。对于问题C，给出 exttt{mEXC} 与 exttt{mEXC-Bellman} 两种两阶段探索-再利用算法，后悔率为 $ ilde{O}(H (S A_{ ext{joint}})^{1/3} T^{2/3})$。相较于集中式联合动作基准，去中心化学习在信息不对称下仍保持与单智能体Q-learning相近的收敛速率，仅含对数因子差异。由于 $A_{ ext{joint}}$ 随玩家数 $M$ 指数增长，该结果对小 $M$ 或每玩家动作集较小的情形最具意义。
原文摘要 · Abstract (English)
We study decentralized multi-player reinforcement learning in episodic tabular Markov decision processes (MDPs) under three forms of information asymmetry: (A) unobserved actions with common rewards, (B) observed actions with independent rewards, and (C) unobserved actions with independent rewards. Players cannot communicate during learning but may agree on a protocol a priori. For Problems A and B we propose \texttt{mQ-learning} and \texttt{mQ-learning-intervals}, achieving $\tilde{O}(\sqrt{H^4 S A_{\text{joint}}\, T})$ regret, where $H$ is the horizon, $S$ the state count, $T = KH$ the total steps, and $A_{\text{joint}} = \prod_{i=1}^M |\mathcal{A}_i|$ the joint action space across $M$ players. For Problem C we give \texttt{mEXC} and \texttt{mEXC-Bellman}, two-phase explore-then-commit algorithms with regret $\tilde{O}(H (S A_{\text{joint}})^{1/3} T^{2/3})$. Against the centralized joint-action benchmark, decentralized learning under information asymmetry matches the single-agent Q-learning rate of \cite{jin2018q} up to logarithmic factors. Because $A_{\text{joint}}$ grows exponentially in $M$, the bounds are most meaningful for small $M$ or small per-player action sets.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。