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

2026-08-13 · Larissa Xu, King Bi, William Chang 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 \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.

📄 PDF Abstract BibTeX arXiv:2608.12753

Code (1)

arxivsub/arXivSub_daily_arxiv ★ 4

Tasks

Reinforcement Learning

Provably Efficient Multi-Task Reinforcement Learning with Model Transfer

2021-07-19 · NeurIPS 2021 12 · Chicheng Zhang, Zhi Wang

We study multi-task reinforcement learning (RL) in tabular episodic Markov decision processes (MDPs). We formulate a heterogeneous multi-player RL problem, in which a group of players concurrently face similar but not ne…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL

2021-10-27 · Chi Jin, Qinghua Liu, Yuanhao Wang, Tiancheng Yu

A major challenge of multiagent reinforcement learning (MARL) is the curse of multiagents, where the size of the joint action space scales exponentially with the number of agents. This remains to be a bottleneck for desi…

Medical Visual Question Answering Q-Learning

Provably Efficient Generalized Lagrangian Policy Optimization for Safe Multi-Agent Reinforcement Learning

2023-05-31 · Dongsheng Ding, Xiaohan Wei, Zhuoran Yang, Zhaoran Wang 외

We examine online safe multi-agent reinforcement learning using constrained Markov games in which agents compete by maximizing their expected total rewards under a constraint on expected total utilities. Our focus is con…

Multi-agent Reinforcement Learning reinforcement-learning Reinforcement Learning Safe Reinforcement Learning

Solving Hierarchical Information-Sharing Dec-POMDPs: An Extensive-Form Game Approach

2024-02-05 · Johan Peralez, Aurélien Delage, Olivier Buffet, Jilles S. Dibangoye

A recent theory shows that a multi-player decentralized partially observable Markov decision process can be transformed into an equivalent single-player game, enabling the application of \citeauthor{bellman}'s principle …

Form Management

Independent and Decentralized Learning in Markov Potential Games

2022-05-29 · Chinmay Maheshwari, Manxi Wu, Druv Pai, Shankar Sastry

We study a multi-agent reinforcement learning dynamics, and analyze its asymptotic behavior in infinite-horizon discounted Markov potential games. We focus on the independent and decentralized setting, where players do n…

Multi-agent Reinforcement Learning reinforcement-learning Reinforcement Learning