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

The paper investigates decentralized multi-player reinforcement learning in episodic tabular Markov Decision Processes (MDPs) where players cannot communicate during learning. The authors study how information asymmetry affects learning efficiency and regret across three distinct problem variants: (A) unobserved actions with common rewards, (B) observed actions with independent rewards, and (C) unobserved actions with independent rewards. To overcome the lack of communication, the framework leverages pre-agreed deterministic protocols and lexicographic ordering over joint actions. This enables players to implicitly coordinate their actions and maintain consistent decision-making without explicit signaling.

For Problem A, the authors propose mQ-learning, which uses a lexicographic tie-breaking rule so that all players independently maintain identical Q-values and select the same joint action, achieving a regret of tilde{O}(sqrt{H^4 S A_{joint} T}). For Problem B, mQ-learning-intervals maintains upper and lower confidence bounds alongside a desired set of optimal joint actions, allowing players to interpret unilateral deviations as implicit communication and eliminate suboptimal choices, yielding the same tilde{O}(sqrt{H^4 S A_{joint} T}) regret. For the fully asymmetric Problem C, the authors introduce two-phase explore-then-commit algorithms, mEXC and mEXC-Bellman, which achieve a regret of tilde{O}(H (SA_{joint})^{1/3} T^{2/3}).

These findings demonstrate that information asymmetry does not impose an additional asymptotic penalty beyond the centralized joint-action benchmark, provided players use deterministic coordination mechanisms. Although the regret bounds scale exponentially with the number of players due to the joint action space, the results establish that decentralized agents can navigate stateful environments and achieve sublinear regret matching single-agent lower bounds up to logarithmic factors.