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

This paper studies 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.

The paper considers a multiplayer episodic tabular MDP with M players, state space S with S = S, and each player Pi having actions Ai, with the joint action space A = A1 × · · · × AM having size Ajoint = ∏M i=1 Ai, which scales as AM max in the worst case—exponential in M. The horizon is H, T = KH is the total number of steps, and the reward r depends on the joint action. The learning objective is to minimize per-player expected regret: RT = ΣK k=1 [V1*(xk1) − V1πk(xk1)], where K is the number of episodes.

For Problem A (unobserved actions, common rewards), the paper proposes mQ-learning, which uses a lexicographic ordering of joint actions to coordinate implicitly and achieves Õ(√(H4SAjointT)) regret (Theorem 3). The key insight is that "all players receive the same reward and observe the same state transitions. Therefore, if all players run the same deterministic algorithm with the same tie-breaking rule, they will independently maintain identical Q-value estimates and select the same joint action at every step—without needing to observe each other's actions. The algorithm uses a lexicographic ordering from prior work to break ties deterministically, and the paper proves that the invariant is preserved across all KH steps; no probabilistic argument is required" for synchronization under repeated tie-breaking.

For Problem B (observed actions, independent rewards), the paper proposes mQ-learning-intervals, which maintains upper and lower confidence bounds at each state-action pair to coordinate action elimination across players, with the same Õ(√(H4SAjointT)) regret (Theorem 5). Since players receive independent rewards, they cannot maintain identical Q-value estimates, so the algorithm maintains both upper and lower confidence bounds. The key idea is that "players maintain a 'desired set' of plausible optimal joint actions at each state. An action is eliminated from the desired set when some player's confidence interval shows it is definitively suboptimal. Since players can observe each other's actions, a unilateral deviation from the agreed-upon action serves as an implicit communication signal. The regret analysis includes an additional slack" term bounded using the interval width from Lemma 13, which decays as O(√(H3ι/t)) with the number of visits.

For Problem C (unobserved actions, independent rewards), the paper gives mEXC and mEXC-Bellman, two-phase explore-then-commit algorithms with regret Õ(H(SAjoint) 1/3T 2/3) (Theorem 7). With K′ ≍ (SAjoint) 1/3K 2/3, the exploration phase plays the least-visited joint action (with lexicographic tie-breaking), and the commit phase acts greedily with respect to learned Q-values. The exploration phase incurs regret at most Rexplore ≤ K′H, and the commit phase regret depends on the quality of Q-value estimates after exploration. The mEXC-Bellman variant uses the plug-in empirical Bellman equation with P̂h(x′x,a) = Nh(x,a,x′)/Nh(x,a) which can yield tighter estimates when exploration is long, at the cost of storing transition counts. The paper notes that "The T 2/3 rate is worse than the √T rate achieved for Problems A and B, which is the standard penalty paid by explore-then-commit when the suboptimality gap is unknown. Whether the optimal rate for Problem C is √T or T 2/3 is left open."

The paper proves auxiliary lemmas on weighted learning rates and interval widths. For the learning rate αt = (H+1)/(H+t), Lemma 10 establishes weight properties: (a) 1/√t ≤ Σi αti/√i ≤ 2/√t, (b) maxi∈[t] αti ≤ 2H/t and Σ∞ i=1(αti)2 ≤ 2H/t, and (c) Σ∞ t=i αti = 1 + 1/H. Lemma 11 provides a recursion decomposing the estimation error Qkh − Qh into initialization bias, propagated estimation error from future steps, and transition estimation error plus exploration bonus. Lemma 12 establishes optimism: with probability ≥ 1−p, 0 ≤ (Qkh − Qh)(x,a,m) ≤ αt0H + Σt i=1 αti φk h+1 + βt, where βt = 2Σt i=1 αti bi ≤ 4c√(H3ι/t). Lemma 13 shows the interval width for Problem B satisfies Qup(x,a;t) − Qlow(x,a;t) = 2Σt i=1 αti bi, which decays at the same rate as the bonus bt.

The paper shows that Algorithm 1 is operationally equivalent to centralized joint-action Q-learning—the agreement is achieved implicitly through deterministic tie-breaking rather than through observation. Specifically, "a single agent running UCB-Q-learning on the joint MDP (S, A1 × · · · × AM, H, P, r) produces a Q-table identical to that of any one player in Algorithm 1, since Problem A players see the same reward, same next state, and same update with the same tie-breaking."

The bounds depend on M only through Ajoint: There is no separate polynomial factor in M: doubling M while keeping Ajoint fixed—e.g. splitting one player with A = 4 into two players with Ai = 2—does not change the regret. The exponential dependence on M through Ajoint is a property of the tabular setting, not of the asymmetry: any worst-case bound against arbitrary joint policies must pay at least √Ajoint.

The paper discusses practical implications: "With M = 2, Ai = 3, S = 10, H = 20, our Problem A bound puts the per-episode suboptimality below 0.1 once K ≳ 105, comparable to centralized Q-learning on the same joint MDP. With M = 4 and Ai = 3 (Ajoint = 81), the same threshold needs K ≳ 106."

The paper concludes: "For Problems A and B we obtain Õ(√(H4SAjointT)) regret, matching the single-agent rate of [1] against the joint-action benchmark up to logarithmic factors. For Problem C we obtain Õ(H(SAjoint) 1/3T 2/3) via explore-then-commit. All bounds depend on Ajoint = ∏M i=1 Ai, which grows exponentially in M: asymmetry imposes no multiplicative penalty relative to a centralized learner over the same joint action space, but the tabular curse of dimensionality remains. Open directions include sharper bounds for Problem C, extensions to function approximation (linear MDPs), matching lower bounds under each asymmetry model, and regret–communication tradeoffs."

Improvements to AI Systems:

1. Decentralized Multi-Agent Coordination Without Communication: Build multi-agent RL systems where agents coordinate implicitly via shared deterministic tie-breaking rules (lexicographic ordering) and identical update logic, eliminating the need for inter-agent communication during learning. This enables scalable coordination in bandwidth-constrained or latency-sensitive environments (e.g., drone swarms, autonomous vehicle fleets) while achieving regret matching centralized learning.

2. Robust Coordination Under Heterogeneous Rewards: Implement interval-based confidence bounds (upper/lower) for agents with independent reward signals, enabling coordinated action elimination and implicit signaling through unilateral deviations. This allows AI systems to maintain coordination even when agents have divergent objectives, useful in competitive or mixed-motive settings (e.g., multi-robot task allocation with individual performance metrics).

3. Efficient Exploration in Unknown Joint Action Spaces: Use explore-then-commit strategies with least-visited joint action sampling for settings where agents cannot observe each other’s actions and have independent rewards. This provides a principled trade-off between exploration cost and regret, applicable to systems with privacy constraints or partial observability (e.g., federated learning with non-communicating clients).

4. Regret-Optimal Learning with Exponential Action Spaces: Adopt algorithms whose regret scales with the joint action space size (Ajoint) rather than the number of agents M, enabling AI systems to handle many agents with small action sets as efficiently as few agents with large action sets. This improves scalability for systems like smart grids or sensor networks with numerous low-complexity nodes.

5. Implicit Synchronization for Shared-State Systems: Leverage the proof that identical deterministic algorithms on shared state-reward observations produce synchronized Q-tables without communication. This enables AI systems to run parallel, fault-tolerant learning processes that automatically stay aligned, useful for distributed control systems or redundant AI pipelines.

6. Adaptive Confidence-Based Action Elimination: Apply the interval-width decay property to dynamically prune suboptimal joint actions across agents, reducing computational overhead in large action spaces. This improves efficiency in real-time decision systems (e.g., resource allocation, portfolio optimization) where action pruning accelerates convergence.

7. Theoretical Guarantees for Multi-Agent Exploration: Use the derived regret bounds to set exploration budgets (K′ ≍ (SAjoint) 1/3K 2/3) in systems with unknown suboptimality gaps, ensuring predictable performance degradation (T 2/3 instead of √T) when full observability is impossible. This informs design choices for AI systems operating under strict exploration constraints.

8. Transferable Learning Rate and Bonus Schedules: Apply the weighted learning rate properties (Lemma 10) and optimism-based bonus decay (Lemma 12) to design hyperparameter schedules that guarantee sublinear regret in multi-agent settings, improving sample efficiency in reinforcement learning systems without requiring per-agent tuning.