Decentralized Multi-Player Q-Learning in Episodic Markov Decision Processes with Information Asymmetry

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 © 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 $\mathtt{\text{mQ-learning}}$ and $\mathtt{\text{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\mathrm{\mid }{\mathcal{A}}_i\mathrm{\mid }$ the joint action space across $M$ players. For Problem C we give $\mathtt{\text{mEXC}}$ and $\mathtt{\text{mEXC-Bellman}}$, two-phase explore-then-commit algorithms with regret $\tilde{O}(H(S{A}_{\text{joint}}{)}^{1\mathrm{/}3}{T}^{2\mathrm{/}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.