Search papers, labs, and topics across Lattice.
This paper investigates decentralized multi-player reinforcement learning in episodic tabular Markov decision processes (MDPs) under various forms of information asymmetry, proposing novel algorithms such as mQ-learning and mEXC. The authors achieve regret bounds of $\tilde{O}(\sqrt{H^4 S A_{\text{joint}}\, T})$ for certain scenarios, demonstrating that decentralized learning can match the performance of centralized benchmarks, albeit with logarithmic factors. The findings highlight the potential for effective decentralized strategies in multi-agent settings, particularly when the number of players or action sets is limited.
Decentralized learning can achieve regret rates comparable to centralized benchmarks, even in the presence of 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 (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.
