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

arXiv: https://arxiv.org/abs/2608.12753 · HTML: https://mlsanity.com/paper/2608.12753/

## 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.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 3 of 3)

- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Online Learning for Cooperative Multi-Player Multi-Armed Bandits](https://mlsanity.com/paper/2109.03818/) (2021)
- [Optimal Cooperative Multiplayer Learning Bandits with Noisy Rewards and No Communication](https://mlsanity.com/paper/2311.06210/) (2023)

## 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.