mlsanityData to 14 Oct 2026

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

arXiv 2608.12753 ↗First posted 13 Aug 2026cs.LGcited by 0

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

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 textttmQ-learning and textttmQ-learning-intervals, achieving tildeO(√H4 S Ajoint, T) regret, where H is the horizon, S the state count, T = KH the total steps, and Ajoint = prodi=1M |Ai| the joint action space across M players. For Problem C we give textttmEXC and textttmEXC-Bellman, two-phase explore-then-commit algorithms with regret tildeO(H (S Ajoint)1/3 T2/3). Against the centralized joint-action benchmark, decentralized learning under information asymmetry matches the single-agent Q-learning rate of citejin2018q up to logarithmic factors. Because Ajoint grows exponentially in M, the bounds are most meaningful for small M or small per-player action sets.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 3 of its 10 references that are in the map. First posted on arXiv 13 Aug 2026.

Builds on

3 of 10 references.

References · 3

  1. 2018Is Q-learning Provably Efficient?cited by 487
  2. 2021Online Learning for Cooperative Multi-Player Multi-Armed Banditscited by 12
  3. 2023Optimal Cooperative Multiplayer Learning Bandits with Noisy Rewards and No Communicationcited by 8

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026High-Probability Nash Regret for Decentralized Learning in Markov α-Potential Games: Episodic and Fully Online Asynchronous Algorithms with Applications to Markov Congestion Games
  2. 2026Provably Efficient Reinforcement Learning in Continuous-Time Episodic MDPs with Poisson Decision Epochs
  3. 2023Achieving Fairness in Multi-Agent Markov Decision Processes Using Reinforcement Learning
  4. 2026Bayesian Learning in Episodic Zero-Sum Games
  5. 2024Federated Q-Learning with Reference-Advantage Decomposition: Almost Optimal Regret and Logarithmic Communication Cost
  6. 2026Learning Markov Decision Processes under Fully Bandit Feedback
  7. 2024widetildeO(T-1) Convergence to (Coarse) Correlated Equilibria in Full-Information General-Sum Markov Games
  8. 2025Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games