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

# Decentralized Multi-Player Q-Learning in Episodic Markov Decision Processes with Information Asymmetry
Source: [https://arxiv.org/html/2608.12753](https://arxiv.org/html/2608.12753)
1stLarissa Xu\*Affiliation:Department of Mathematics University of California, Los Angeles Los Angeles, USA xuzhiyun004119@g\.ucla\.edu2ndKing BiAffiliation:Department of Computer Science University of California, Los Angeles Los Angeles, USA king0508@g\.ucla\.edu3rdWilliam ChangAffiliation:Department of Mathematics University of California, Los Angeles Los Angeles, USA chang314@g\.ucla\.edu

###### Abstract

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 proposemQ\-learningandmQ\-learning\-intervals, achievingO~​\(H4​S​Ajoint​T\)\\tilde\{O\}\(\\sqrt\{H^\{4\}SA\_\{\\text\{joint\}\}\\,T\}\)regret, whereHHis the horizon,SSthe state count,T=K​HT=KHthe total steps, andAjoint=∏i=1M\|𝒜i\|A\_\{\\text\{joint\}\}=\\prod\_\{i=1\}^\{M\}\|\\mathcal\{A\}\_\{i\}\|the joint action space acrossMMplayers\. For Problem C we givemEXCandmEXC\-Bellman, two\-phase explore\-then\-commit algorithms with regretO~​\(H​\(S​Ajoint\)1/3​T2/3\)\\tilde\{O\}\(H\(SA\_\{\\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\[[7](https://arxiv.org/html/2608.12753#bib.bib7)\]up to logarithmic factors\. BecauseAjointA\_\{\\text\{joint\}\}grows exponentially inMM, the bounds are most meaningful for smallMMor small per\-player action sets\.

###### Index Terms:

multi\-player reinforcement learning, Markov decision processes, Q\-learning, information asymmetry, regret bounds, decentralized learning

## IIntroduction

Multi\-agent reinforcement learning \(MARL\) arises in cooperative systems such as communication networks\[[1](https://arxiv.org/html/2608.12753#bib.bib3)\], multi\-robot coordination, and distributed resource allocation\[[9](https://arxiv.org/html/2608.12753#bib.bib2)\], where agents must coordinate without centralized control or explicit communication during learning\.

The multi\-armed bandit \(MAB\) framework is well understood in the single\-player setting\[[8](https://arxiv.org/html/2608.12753#bib.bib1),[2](https://arxiv.org/html/2608.12753#bib.bib4)\]\. Extensions to the multi\-player setting\[[3](https://arxiv.org/html/2608.12753#bib.bib9)\]reveal that information asymmetry between players introduces substantial coordination challenges\. Prior work on cooperative multi\-player bandits has studied several asymmetry models\[[4](https://arxiv.org/html/2608.12753#bib.bib6),[5](https://arxiv.org/html/2608.12753#bib.bib8)\], but these results are limited to the stateless bandit setting, whereas many applications have state structure that agents must learn to navigate\.

In the single\-agent episodic MDP setting, Jin et al\.\[[7](https://arxiv.org/html/2608.12753#bib.bib7)\]showed that a model\-free Q\-learning algorithm with upper confidence bounds achievesO~​\(H4​S​A​T\)\\tilde\{O\}\(\\sqrt\{H^\{4\}SAT\}\)regret, near\-optimal up to polynomial factors inHH\. A natural question is whether similar guarantees hold for the multi\-player setting with information asymmetry, or whether asymmetry imposes an additional cost beyond the centralized joint\-action rate\.

The key insight, first observed in the bandit setting\[[4](https://arxiv.org/html/2608.12753#bib.bib6)\], is that players can use a*pre\-agreed deterministic protocol*to implicitly coordinate without communication: if all players follow the same deterministic algorithm with access to the same information, they independently reach the same decisions\. We extend this to episodic MDPs, where coordination must also account for state transitions and multi\-step planning\.

#### Our Contributions

- •For Problem A \(unobserved actions, common rewards\),mQ\-learninguses a lexicographic ordering of joint actions to coordinate implicitly and achievesO~​\(H4​S​Ajoint​T\)\\tilde\{O\}\(\\sqrt\{H^\{4\}SA\_\{\\text\{joint\}\}\\,T\}\)regret \(Theorem[3](https://arxiv.org/html/2608.12753#Thmtheorem3)\), whereAjoint=∏i=1M\|𝒜i\|A\_\{\\text\{joint\}\}=\\prod\_\{i=1\}^\{M\}\|\\mathcal\{A\}\_\{i\}\|\.
- •For Problem B \(observed actions, independent rewards\),mQ\-learning\-intervalsmaintains upper and lower confidence bounds at each state\-action pair to coordinate action elimination across players, with the sameO~​\(H4​S​Ajoint​T\)\\tilde\{O\}\(\\sqrt\{H^\{4\}SA\_\{\\text\{joint\}\}\\,T\}\)regret \(Theorem[5](https://arxiv.org/html/2608.12753#Thmtheorem5)\)\.
- •For Problem C \(unobserved actions, independent rewards\),mEXCandmEXC\-Bellmanare explore\-then\-commit algorithms\. WithK′≍\(S​Ajoint\)1/3​K2/3K^\{\\prime\}\\asymp\(SA\_\{\\text\{joint\}\}\)^\{1/3\}K^\{2/3\}, we obtainO~​\(H​\(S​Ajoint\)1/3​T2/3\)\\tilde\{O\}\(H\(SA\_\{\\text\{joint\}\}\)^\{1/3\}T^\{2/3\}\)regret \(Theorem[7](https://arxiv.org/html/2608.12753#Thmtheorem7)\)\.
- •We prove auxiliary lemmas on weighted learning rates and interval widths that may be of independent interest, and show that Algorithm[1](https://arxiv.org/html/2608.12753#alg1)is operationally equivalent to centralized joint\-action Q\-learning—the agreement is achieved*implicitly*through deterministic tie\-breaking rather than through observation\.

#### Role ofMM\.

Our bounds match the single\-agent rate*relative to the joint\-action benchmark*, but grow exponentially inMMthroughAjointA\_\{\\text\{joint\}\}\. This is unavoidable in tabular MARL: even a centralized learner hasΩ⁡\(S​Ajoint​T\)\\Omega\(\\sqrt\{SA\_\{\\text\{joint\}\}T\}\)regret\[[7](https://arxiv.org/html/2608.12753#bib.bib7)\]\. The contribution is therefore that asymmetry imposes no*additional*factor beyond the centralized rate, not that asymmetry is free in absolute terms\.

#### Organization\.

Section[II](https://arxiv.org/html/2608.12753#S2)sets up the model\. Section[III](https://arxiv.org/html/2608.12753#S3)treats Problems A and B; Section[IV](https://arxiv.org/html/2608.12753#S4)treats Problem C\. Section[VIII](https://arxiv.org/html/2608.12753#S8)discusses related work; proofs are in the Appendix\.

## IIPreliminaries

### II\-AMulti\-Player Episodic MDP Model

We consider a multiplayer episodic tabular MDP\(𝒫,𝒮,𝒜,H,ℙ,r\)\(\\mathcal\{P\},\\mathcal\{S\},\\mathcal\{A\},H,\\mathbb\{P\},r\)\. Here𝒫=\{P1,…,PM\}\\mathcal\{P\}=\\\{P\_\{1\},\\ldots,P\_\{M\}\\\}is the set ofMMplayers and𝒮\\mathcal\{S\}is the state space with\|𝒮\|=S\|\\mathcal\{S\}\|=S\. Each playerPiP\_\{i\}has actions𝒜i\\mathcal\{A\}\_\{i\}, and the joint action space is𝒜=𝒜1×⋯×𝒜M\\mathcal\{A\}=\\mathcal\{A\}\_\{1\}\\times\\cdots\\times\\mathcal\{A\}\_\{M\}with\|𝒜\|=Ajoint=∏i=1M\|𝒜i\|\|\\mathcal\{A\}\|=A\_\{\\text\{joint\}\}=\\prod\_\{i=1\}^\{M\}\|\\mathcal\{A\}\_\{i\}\|, which scales asAmaxMA\_\{\\max\}^\{M\}in the worst case—exponential inMM\. We useAAandAjointA\_\{\\text\{joint\}\}interchangeably in regret bounds\.ℙh\\mathbb\{P\}\_\{h\}is the set of unknown transition kernels at stephh, one for each joint action𝒂∈𝒜\\bm\{a\}\\in\\mathcal\{A\}; entry\(ℙh\)i​j​\(𝒂\)\(\\mathbb\{P\}\_\{h\}\)\_\{ij\}\(\\bm\{a\}\)is the probability of moving fromxix\_\{i\}toxjx\_\{j\}under𝒂\\bm\{a\}\. The horizon isHH, and the rewardrrdepends on the joint action\. Without loss of generality, states are layered: the initial state iss0s\_\{0\}and the final state issHs\_\{H\}\.

At each time step, each player observes the current state and picks an arm from their set\. TheMM\-tuple of arms is denoted𝒂=\(a1,…,aM\)\\bm\{a\}=\(a\_\{1\},\\ldots,a\_\{M\}\)\. Throughout this paper, vectors and tuples are denoted in boldface\. This generates a random rewardX𝒂∈\[0,1\]X\_\{\\bm\{a\}\}\\in\[0,1\]from a11\-subgaussian distributionF𝒂F\_\{\\bm\{a\}\}with meanμ𝒂\\mu\_\{\\bm\{a\}\}\. After performing the joint action, the players transition to a new state according to the unknown transition kernelℙh\\mathbb\{P\}\_\{h\}\.

### II\-BValue Functions and Bellman Equation

A*policy*π\\pispecifies, for each stephhand statexx, a joint action𝒂\\bm\{a\}\. The*value function*of a policyπ\\piat stephhand statexxis defined as

Vhπ​\(x\)=𝔼π​\[∑h′=hHrh′​\(xh′,𝒂h′\)\|xh=x\]V\_\{h\}^\{\\pi\}\(x\)=\\mathbb\{E\}\_\{\\pi\}\\left\[\\sum\_\{h^\{\\prime\}=h\}^\{H\}r\_\{h^\{\\prime\}\}\(x\_\{h^\{\\prime\}\},\\bm\{a\}\_\{h^\{\\prime\}\}\)\\;\\middle\|\\;x\_\{h\}=x\\right\]\(1\)and the corresponding*action\-value function*\(Q\-function\) is

Qhπ\(x,𝒂\)=rh\(x,𝒂\)\+𝔼x′∼ℙh\(⋅\|x,𝒂\)\[Vh\+1π\(x′\)\]\.Q\_\{h\}^\{\\pi\}\(x,\\bm\{a\}\)=r\_\{h\}\(x,\\bm\{a\}\)\+\\mathbb\{E\}\_\{x^\{\\prime\}\\sim\\mathbb\{P\}\_\{h\}\(\\cdot\|x,\\bm\{a\}\)\}\[V\_\{h\+1\}^\{\\pi\}\(x^\{\\prime\}\)\]\.\(2\)
The optimal value function satisfies the*Bellman optimality equation*:

Qh∗​\(x,𝒂\)=rh​\(x,𝒂\)\+\[ℙh​Vh\+1∗\]​\(x,𝒂\),Q\_\{h\}^\{\*\}\(x,\\bm\{a\}\)=r\_\{h\}\(x,\\bm\{a\}\)\+\[\\mathbb\{P\}\_\{h\}V\_\{h\+1\}^\{\*\}\]\(x,\\bm\{a\}\),\(3\)whereVh∗​\(x\)=max𝒂⁡Qh∗​\(x,𝒂\)V\_\{h\}^\{\*\}\(x\)=\\max\_\{\\bm\{a\}\}Q\_\{h\}^\{\*\}\(x,\\bm\{a\}\)and\[ℙhf\]\(x,𝒂\)=𝔼x′∼ℙh\(⋅\|x,𝒂\)\[f\(x′\)\]\[\\mathbb\{P\}\_\{h\}f\]\(x,\\bm\{a\}\)=\\mathbb\{E\}\_\{x^\{\\prime\}\\sim\\mathbb\{P\}\_\{h\}\(\\cdot\|x,\\bm\{a\}\)\}\[f\(x^\{\\prime\}\)\]\.

### II\-CRegret and Learning Objective

The players want to collectively identify the best policy, i\.e\., one that returns the highest rewards in expectation\. This takes into account both the true reward means and the probability transition matrices\. However, the players know neither the meansμ𝒂\\mu\_\{\\bm\{a\}\}nor the transition functionsℙh\\mathbb\{P\}\_\{h\}\. They must learn by playing and exploring\. We capture learning efficiency via the per\-playerexpected regret:

RT=∑k=1K\[V1∗​\(x1k\)−V1πk​\(x1k\)\]R\_\{T\}=\\sum\_\{k=1\}^\{K\}\\left\[V\_\{1\}^\{\*\}\(x\_\{1\}^\{k\}\)\-V\_\{1\}^\{\\pi\_\{k\}\}\(x\_\{1\}^\{k\}\)\\right\]\(4\)whereKKis the number of episodes,T=K​HT=KHis the total number of steps, andπk\\pi\_\{k\}is the policy used in episodekk\. Our goal is to design decentralized algorithms with sublinear regret\. Fundamental results for single\-player MAB problems\[[8](https://arxiv.org/html/2608.12753#bib.bib1)\]suggest anΩ⁡\(log⁡T\)\\Omega\(\\log T\)lower bound for the multi\-player problem as well\. In the episodic MDP setting,Ω~​\(H2​S​A​T\)\\tilde\{\\Omega\}\(\\sqrt\{H^\{2\}SAT\}\)is a known lower bound\[[7](https://arxiv.org/html/2608.12753#bib.bib7)\]\. We specifically exclude any explicit communication between players during learning, though they may coordinatea priori\.

### II\-DInformation Asymmetry Models

We consider three types of information asymmetry, following\[[4](https://arxiv.org/html/2608.12753#bib.bib6)\]\.

#### Problem A: Action Asymmetry with Common Rewards

Consider a set ofMMplayersP1,…,PMP\_\{1\},\\ldots,P\_\{M\}, where playerPiP\_\{i\}has a set𝒦i\\mathcal\{K\}\_\{i\}ofKiK\_\{i\}arms\. At each time instant, each player picks an arm from their set with theMM\-tuple denoted by𝒂=\(a1,…,aM\)\\bm\{a\}=\(a\_\{1\},\\ldots,a\_\{M\}\)\. The reward to*all*players equalsX𝒂⁡\(t\)​\(t\)X\_\{\\bm\{a\}\(t\)\}\(t\), i\.e\., the reward is common, depends on the joint action𝒂⁡\(t\)\\bm\{a\}\(t\), and is independent across time\. Crucially, no player can observe the actions of the other players\. Formally, the information available to playeriiat timettis:\{xhk,rhk:k≤t,h∈\[H\]\}\\\{x\_\{h\}^\{k\},r\_\{h\}^\{k\}:k\\leq t,h\\in\[H\]\\\}together with their own action history\{aih,k:k≤t,h∈\[H\]\}\\\{a\_\{i\}^\{h,k\}:k\\leq t,h\\in\[H\]\\\}\.

#### Problem B: Reward Asymmetry with Observed Actions

Each agent can observe the actions of all other agents, but the rewards are independent\. If the arms pulled at timettare𝒂⁡\(t\)\\bm\{a\}\(t\), each player gets an i\.i\.d\. copy of the reward: playeriireceivesX𝒂⁡\(t\)i​\(t\)X^\{i\}\_\{\\bm\{a\}\(t\)\}\(t\)drawn independently fromF𝒂⁡\(t\)F\_\{\\bm\{a\}\(t\)\}\. Since rewards are i\.i\.d\., the expected regret is the same for all players\. The information available to playeriiis:\{xhk,𝒂hk,rhi,k:k≤t,h∈\[H\]\}\\\{x\_\{h\}^\{k\},\\bm\{a\}\_\{h\}^\{k\},r\_\{h\}^\{i,k\}:k\\leq t,h\\in\[H\]\\\}, i\.e\., full action information but only their own rewards\.

#### Problem C: Full Asymmetry

No player can observe the actions of the others, and rewards are independent from the same distribution\. This combines the challenges of both Problems A and B\. The information available to playeriiis only:\{xhk,aih,k,rhi,k:k≤t,h∈\[H\]\}\\\{x\_\{h\}^\{k\},a\_\{i\}^\{h,k\},r\_\{h\}^\{i,k\}:k\\leq t,h\\in\[H\]\\\}\.

## IIIMain Results

### III\-AProblem A: Asymmetry in Actions

The key difficulty in Problem A is that players cannot observe each other’s actions and must therefore coordinate implicitly\. We use a lexicographic ordering from\[[4](https://arxiv.org/html/2608.12753#bib.bib6)\]to break ties deterministically\.

###### Definition 2\(Lexicographic Order\)

For twoMM\-tuples𝐱=\(x1,…,xM\)\\bm\{x\}=\(x\_\{1\},\\ldots,x\_\{M\}\)and𝐲=\(y1,…,yM\)\\bm\{y\}=\(y\_\{1\},\\ldots,y\_\{M\}\), we say𝐱<𝐲\\bm\{x\}<\\bm\{y\}if and only if there exists annnsuch that∀i<n\\forall i<n,xi=yix\_\{i\}=y\_\{i\}, andxn<ynx\_\{n\}<y\_\{n\}\.

Intuitively,𝒙<𝒚\\bm\{x\}<\\bm\{y\}if𝒙\\bm\{x\}is smaller than𝒚\\bm\{y\}when viewed as anMM\-digit number\. When each player has the same number of actionsAA, we can view𝒂∈𝒜\\bm\{a\}\\in\\mathcal\{A\}as a number in baseAA\. This definition remains applicable even when players have different numbers of actions\.

The key observation is that in Problem A, 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\.

Algorithm 1mQ\-learning\(for each playerPiP\_\{i\}\)1:Initialize

Qhk​\(i,x,𝒂\)←HQ^\{k\}\_\{h\}\(i,x,\\bm\{a\}\)\\leftarrow H,

Nh​\(i,x,𝒂\)←0N\_\{h\}\(i,x,\\bm\{a\}\)\\leftarrow 0for all

\(x,𝒂,h\)∈𝒮×𝒜×\[H\]\(x,\\bm\{a\},h\)\\in\\mathcal\{S\}\\times\\mathcal\{A\}\\times\[H\]\.

2:forepisode

k=1,…,Kk=1,\\ldots,Kdo

3:Receive initial state

x1x\_\{1\}\.

4:forstep

h=1,…,Hh=1,\\ldots,Hdo

5:Pick

𝒂h\\bm\{a\}\_\{h\}as the*smallest*action \(via Definition[2](https://arxiv.org/html/2608.12753#Thmtheorem2)\) in

arg⁡max𝒂′​Qhk​\(i,xh,𝒂′\)\\arg\\max\_\{\\bm\{a\}^\{\\prime\}\}Q^\{k\}\_\{h\}\(i,x\_\{h\},\\bm\{a\}^\{\\prime\}\)\.

6:Observe common reward

rhr\_\{h\}and next state

xh\+1x\_\{h\+1\}\.

7:

t=Nh​\(i,xh,𝒂h\)←Nh​\(i,xh,𝒂h\)\+1t=N\_\{h\}\(i,x\_\{h\},\\bm\{a\}\_\{h\}\)\\leftarrow N\_\{h\}\(i,x\_\{h\},\\bm\{a\}\_\{h\}\)\+1\.

8:

bt←c​H3​ι/tb\_\{t\}\\leftarrow c\\sqrt\{H^\{3\}\\iota/t\}\.

9:

Qhk​\(i,xh,𝒂h\)←\(1−αt\)​Qhk−1​\(i,xh,𝒂h\)Q\_\{h\}^\{k\}\(i,x\_\{h\},\\bm\{a\}\_\{h\}\)\\leftarrow\(1\-\\alpha\_\{t\}\)Q\_\{h\}^\{k\-1\}\(i,x\_\{h\},\\bm\{a\}\_\{h\}\)\+αt​\[rh\+Vh\+1k−1​\(xh\+1\)\+bt\]\\quad\+\\alpha\_\{t\}\[r\_\{h\}\+V\_\{h\+1\}^\{k\-1\}\(x\_\{h\+1\}\)\+b\_\{t\}\]\.

10:

Vhk​\(xh\)←min⁡\{H,max𝒂′⁡Qhk​\(i,xh,𝒂′\)\}V\_\{h\}^\{k\}\(x\_\{h\}\)\\leftarrow\\min\\\{H,\\max\_\{\\bm\{a\}^\{\\prime\}\}Q^\{k\}\_\{h\}\(i,x\_\{h\},\\bm\{a\}^\{\\prime\}\)\\\}\.

11:endfor

12:endfor

The learning rate isαt=\(H\+1\)/\(H\+t\)\\alpha\_\{t\}=\(H\+1\)/\(H\+t\)andι=log⁡\(S​Ajoint​T/p\)\\iota=\\log\(SA\_\{\\text\{joint\}\}T/p\)\. The algorithm is essentially the UCB\-based Q\-learning of\[[7](https://arxiv.org/html/2608.12753#bib.bib7)\]applied to the joint action space, with the deterministic tie\-breaking of Definition[2](https://arxiv.org/html/2608.12753#Thmtheorem2)ensuring implicit coordination\. Operationally, Algorithm[1](https://arxiv.org/html/2608.12753#alg1)matches centralized joint\-action Q\-learning: no player observes the others’ actions, but because rewards and transitions are common and tie\-breaking is deterministic, every player’s Q\-table evolves identically and they select the same joint action at every step\.

#### Synchronization under repeated tie\-breaking\.

Stability of implicit coordination follows from a one\-line invariant\. All players initializeQh1≡HQ^\{1\}\_\{h\}\\equiv H, so thearg⁡max\\arg\\maxset is identical and the lexicographic\-smallest element is uniquely determined\. IfQhkQ^\{k\}\_\{h\}is identical across players at the start of episodekk, then in Problem A the update on line 8 depends only on quantities common to all players \(same rewardrhr\_\{h\}, same next statexh\+1x\_\{h\+1\}, same visit counttt\), soQhk\+1Q^\{k\+1\}\_\{h\}remains identical\. The invariant is preserved across allK​HKHsteps; no probabilistic argument is required\.

###### Theorem 3

Consider Problem A withMMplayers and joint action space sizeAjoint=∏i=1M\|𝒜i\|A\_\{\\text\{joint\}\}=\\prod\_\{i=1\}^\{M\}\|\\mathcal\{A\}\_\{i\}\|\. There existsc\>0c\>0such that for anyp∈\(0,1\)p\\in\(0,1\), withbt=c​H3​ι/tb\_\{t\}=c\\sqrt\{H^\{3\}\\iota/t\}andαt=\(H\+1\)/\(H\+t\)\\alpha\_\{t\}=\(H\+1\)/\(H\+t\), with probability at least1−p1\-pthe total regret ofmQ\-learningfor any player isO⁡\(H4​S​Ajoint​T​ι\)O\(\\sqrt\{H^\{4\}SA\_\{\\text\{joint\}\}\\,T\\,\\iota\}\), whereι=log⁡\(S​Ajoint​T/p\)\\iota=\\log\(SA\_\{\\text\{joint\}\}T/p\)\.

### III\-BProblem B: Asymmetry in Rewards

When players receive independent rewards, they cannot maintain identical Q\-value estimates\. Even though they observe the same actions, their different reward realizations lead to different confidence intervals for each state\-action pair\. We address this by maintaining both upper and lower confidence bounds, inspired by the approach of\[[5](https://arxiv.org/html/2608.12753#bib.bib8)\]in the bandit setting\.

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*: it tells all players that the deviating player has determined the proposed action is suboptimal\.

Algorithm 2mQ\-learning\-intervals\(for each playerPiP\_\{i\}\)1:Initialize

Qhk,up​\(i,x,𝒂\)←HQ^\{k,\\text\{up\}\}\_\{h\}\(i,x,\\bm\{a\}\)\\leftarrow H,

Qhk,low​\(i,x,𝒂\)←0Q^\{k,\\text\{low\}\}\_\{h\}\(i,x,\\bm\{a\}\)\\leftarrow 0,

Nh​\(i,x,𝒂\)←0N\_\{h\}\(i,x,\\bm\{a\}\)\\leftarrow 0for all

\(x,𝒂,h\)∈𝒮×𝒜×\[H\]\(x,\\bm\{a\},h\)\\in\\mathcal\{S\}\\times\\mathcal\{A\}\\times\[H\]\.

2:forepisode

k=1,…,Kk=1,\\ldots,Kdo

3:Receive initial state

x1x\_\{1\}\.

4:forstep

h=1,…,Hh=1,\\ldots,Hdo

5:In state

xhx\_\{h\}, consider the action in the desired set pulled the fewest times\. Break ties via Definition[2](https://arxiv.org/html/2608.12753#Thmtheorem2)\. Call this

𝒂\\bm\{a\}\.

6:If

∃𝒂′\\exists\\,\\bm\{a\}^\{\\prime\}such that for some player

ii:

Qhk,up​\(i,𝒂,xhk\)<Qhk,low​\(i,𝒂′,xhk\)Q\_\{h\}^\{k,\\text\{up\}\}\(i,\\bm\{a\},x\_\{h\}^\{k\}\)<Q\_\{h\}^\{k,\\text\{low\}\}\(i,\\bm\{a\}^\{\\prime\},x\_\{h\}^\{k\}\), then player

iiintentionally deviates from

𝒂\\bm\{a\}\.

7:Call the realized joint action

𝒂h\\bm\{a\}\_\{h\}\. All players observe

𝒂h\\bm\{a\}\_\{h\}\.

8:If

𝒂h≠𝒂\\bm\{a\}\_\{h\}\\neq\\bm\{a\}, all players eliminate

𝒂\\bm\{a\}from the desired set for state

xhx\_\{h\}\.

9:Each player observes own reward

rhir\_\{h\}^\{i\}and state

xh\+1x\_\{h\+1\}\.

10:

t=Nh​\(i,xh,𝒂h\)←Nh​\(i,xh,𝒂h\)\+1t=N\_\{h\}\(i,x\_\{h\},\\bm\{a\}\_\{h\}\)\\leftarrow N\_\{h\}\(i,x\_\{h\},\\bm\{a\}\_\{h\}\)\+1;

bt←c​H3​ι/tb\_\{t\}\\leftarrow c\\sqrt\{H^\{3\}\\iota/t\}\.

11:

Qhk,up​\(i,xh,𝒂h\)←\(1−αt\)​Qhk,up​\(i,xh,𝒂h\)Q\_\{h\}^\{k,\\text\{up\}\}\(i,x\_\{h\},\\bm\{a\}\_\{h\}\)\\leftarrow\(1\-\\alpha\_\{t\}\)Q\_\{h\}^\{k,\\text\{up\}\}\(i,x\_\{h\},\\bm\{a\}\_\{h\}\)\+αt​\[rhi\+Vh\+1​\(xh\+1\)\+bt\]\\quad\+\\alpha\_\{t\}\[r\_\{h\}^\{i\}\+V\_\{h\+1\}\(x\_\{h\+1\}\)\+b\_\{t\}\]\.

12:

Qhk,low​\(i,xh,𝒂h\)←\(1−αt\)​Qhk,low​\(i,xh,𝒂h\)Q\_\{h\}^\{k,\\text\{low\}\}\(i,x\_\{h\},\\bm\{a\}\_\{h\}\)\\leftarrow\(1\-\\alpha\_\{t\}\)Q\_\{h\}^\{k,\\text\{low\}\}\(i,x\_\{h\},\\bm\{a\}\_\{h\}\)\+αt​\[rhi\+Vh\+1​\(xh\+1\)−bt\]\\quad\+\\alpha\_\{t\}\[r\_\{h\}^\{i\}\+V\_\{h\+1\}\(x\_\{h\+1\}\)\-b\_\{t\}\]\.

13:

Vh​\(xh\)←min⁡\{H,max𝒂′⁡Qhk​\(i,xh,𝒂′\)\}V\_\{h\}\(x\_\{h\}\)\\leftarrow\\min\\\{H,\\max\_\{\\bm\{a\}^\{\\prime\}\}Q^\{k\}\_\{h\}\(i,x\_\{h\},\\bm\{a\}^\{\\prime\}\)\\\}\.

14:endfor

15:endfor

The learning rate is againαt=\(H\+1\)/\(H\+t\)\\alpha\_\{t\}=\(H\+1\)/\(H\+t\)\. The width of the confidence intervalQup−QlowQ^\{\\text\{up\}\}\-Q^\{\\text\{low\}\}controls the regret incurred when a suboptimal action from the desired set is played; Lemma[13](https://arxiv.org/html/2608.12753#Thmtheorem13)characterizes how it shrinks with visits\.

#### Confidence stability across players\.

Although each player’s reward stream is independent, all players use the same bonus schedulebtb\_\{t\}and the same visit countsNh​\(⋅,⋅\)N\_\{h\}\(\\cdot,\\cdot\)\(since actions are observable\)\. By Lemma[13](https://arxiv.org/html/2608.12753#Thmtheorem13), the interval width at\(x,𝒂\)\(x,\\bm\{a\}\)afterttvisits is exactly2​∑iαti​bi2\\sum\_\{i\}\\alpha\_\{t\}^\{i\}b\_\{i\}, a deterministic function ofttidentical across players\. The intervals are merely shifted between players by independent reward noise\. Optimism \(Lemma[12](https://arxiv.org/html/2608.12753#Thmtheorem12), union\-bounded overMMplayers, contributing the\(1−p\)M\(1\-p\)^\{M\}factor\) guarantees each interval coversQh∗​\(x,𝒂\)Q^\{\*\}\_\{h\}\(x,\\bm\{a\}\)w\.h\.p\., so playerii’s deviation truthfully signals dominance: the desired set shrinks monotonically and never excludes the optimal action\.

###### Theorem 5

Consider Problem B \(asymmetry in rewards\) withMMplayers and joint action space sizeAjoint=∏i=1M\|𝒜i\|A\_\{\\text\{joint\}\}=\\prod\_\{i=1\}^\{M\}\|\\mathcal\{A\}\_\{i\}\|\. There exists a constantc\>0c\>0such that for anyp∈\(0,1\)p\\in\(0,1\), withbt=c​H3​ι/tb\_\{t\}=c\\sqrt\{H^\{3\}\\iota/t\}, with probability at least1−p1\-pthe total regret ofmQ\-learning\-intervalsfor any player is at mostO⁡\(H4​S​Ajoint​T​ι\)O\(\\sqrt\{H^\{4\}SA\_\{\\text\{joint\}\}\\,T\\,\\iota\}\), whereι=log⁡\(M​S​Ajoint​T/p\)\\iota=\\log\(MSA\_\{\\text\{joint\}\}T/p\)\.

## IVProblem C: Full Information Asymmetry

When both action and reward information are asymmetric, the challenges of Problems A and B combine\. Players cannot observe each other’s actions \(so they cannot use deviations as signals\) and receive different rewards \(so they cannot maintain identical estimates\)\. We adopt a two\-phase explore\-then\-commit strategy\.

### IV\-AAlgorithm:mEXC

During the exploration phase \(episodes1,…,K′1,\\ldots,K^\{\\prime\}\), players follow a deterministic exploration protocol: at each state, they play the least\-visited joint action \(with lexicographic tie\-breaking\)\. Since this rule depends only on the visit counts—which are identical across players because they visit the same state\-action pairs—all players agree on the exploration action without communication\.

During the commit phase \(episodesK′\+1,…,KK^\{\\prime\}\+1,\\ldots,K\), each player acts greedily with respect to their learned Q\-values, using lexicographic tie\-breaking to ensure agreement\.

Algorithm 3mEXC\(for each playerPiP\_\{i\}\)1:Initialize

Qhk​\(i,x,𝒂\)←HQ^\{k\}\_\{h\}\(i,x,\\bm\{a\}\)\\leftarrow H,

Nh​\(i,x,𝒂\)←0N\_\{h\}\(i,x,\\bm\{a\}\)\\leftarrow 0for all

\(x,𝒂,h\)∈𝒮×𝒜×\[H\]\(x,\\bm\{a\},h\)\\in\\mathcal\{S\}\\times\\mathcal\{A\}\\times\[H\]\.

2:forepisode

k=1,…,K′k=1,\\ldots,K^\{\\prime\}\(Exploration Phase\)do

3:Receive

x1x\_\{1\}\.

4:forstep

h=1,…,Hh=1,\\ldots,Hdo

5:Pick the least\-visited action in the desired set; break ties via Definition[2](https://arxiv.org/html/2608.12753#Thmtheorem2)\. Call this

𝒂h\\bm\{a\}\_\{h\}\.

6:All players take

𝒂h\\bm\{a\}\_\{h\}, observe reward

rhr\_\{h\}and state

xh\+1x\_\{h\+1\}\.

7:

t=Nh​\(i,xh,𝒂h\)←Nh​\(i,xh,𝒂h\)\+1t=N\_\{h\}\(i,x\_\{h\},\\bm\{a\}\_\{h\}\)\\leftarrow N\_\{h\}\(i,x\_\{h\},\\bm\{a\}\_\{h\}\)\+1;

bt←c​H3​ι/tb\_\{t\}\\leftarrow c\\sqrt\{H^\{3\}\\iota/t\}\.

8:

Qhk​\(i,xh,𝒂h\)←\(1−αt\)​Qhk​\(i,xh,𝒂h\)Q\_\{h\}^\{k\}\(i,x\_\{h\},\\bm\{a\}\_\{h\}\)\\leftarrow\(1\-\\alpha\_\{t\}\)Q\_\{h\}^\{k\}\(i,x\_\{h\},\\bm\{a\}\_\{h\}\)\+αt​\[rh\+Vh\+1​\(xh\+1\)\+bt\]\\quad\+\\alpha\_\{t\}\[r\_\{h\}\+V\_\{h\+1\}\(x\_\{h\+1\}\)\+b\_\{t\}\]\.

9:

Vh​\(xh\)←min⁡\{H,max𝒂′⁡Qhk​\(i,xh,𝒂′\)\}V\_\{h\}\(x\_\{h\}\)\\leftarrow\\min\\\{H,\\max\_\{\\bm\{a\}^\{\\prime\}\}Q^\{k\}\_\{h\}\(i,x\_\{h\},\\bm\{a\}^\{\\prime\}\)\\\}\.

10:endfor

11:endfor

12:forepisode

k=K′\+1,…,Kk=K^\{\\prime\}\+1,\\ldots,K\(Commit Phase\)do

13:Receive

x1x\_\{1\}\.

14:forstep

h=1,…,Hh=1,\\ldots,Hdo

15:Pick

𝒂h\\bm\{a\}\_\{h\}as the smallest action in

arg⁡max𝒂′​QhK′​\(i,xh,𝒂′\)\\arg\\max\_\{\\bm\{a\}^\{\\prime\}\}Q^\{K^\{\\prime\}\}\_\{h\}\(i,x\_\{h\},\\bm\{a\}^\{\\prime\}\)\.

16:endfor

17:endfor

The exploration phase incurs regret at mostRexplore≤K′​HR\_\{\\text\{explore\}\}\\leq K^\{\\prime\}Hsince rewards are bounded in\[0,1\]\[0,1\]\. The commit phase regret depends on the quality of the Q\-value estimates after exploration\.

### IV\-BAlgorithm:mEXC\-Bellman

An alternative approach uses the empirical Bellman equation rather than the incremental Q\-learning update during the exploration phase\.

Algorithm 4mEXC\-Bellman\(for each playerPiP\_\{i\}\)1:Initialize

Qhk​\(i,x,𝒂\)←HQ^\{k\}\_\{h\}\(i,x,\\bm\{a\}\)\\leftarrow H,

Nh​\(i,x,𝒂\)←0N\_\{h\}\(i,x,\\bm\{a\}\)\\leftarrow 0for all

\(x,𝒂,h\)∈𝒮×𝒜×\[H\]\(x,\\bm\{a\},h\)\\in\\mathcal\{S\}\\times\\mathcal\{A\}\\times\[H\]\.

2:forepisode

k=1,…,K′k=1,\\ldots,K^\{\\prime\}\(Exploration Phase\)do

3:Receive

x1x\_\{1\}\.

4:forstep

h=1,…,Hh=1,\\ldots,Hdo

5:Pick the least\-visited action; break ties via Definition[2](https://arxiv.org/html/2608.12753#Thmtheorem2)\. Call this

𝒂h\\bm\{a\}\_\{h\}\.

6:All players take

𝒂h\\bm\{a\}\_\{h\}, observe reward

rhr\_\{h\}and state

xh\+1x\_\{h\+1\}\.

7:

t=Nh​\(i,xh,𝒂h\)←Nh​\(i,xh,𝒂h\)\+1t=N\_\{h\}\(i,x\_\{h\},\\bm\{a\}\_\{h\}\)\\leftarrow N\_\{h\}\(i,x\_\{h\},\\bm\{a\}\_\{h\}\)\+1\.

8:Update empirical reward

r^​\(xh,𝒂h\)\\hat\{r\}\(x\_\{h\},\\bm\{a\}\_\{h\}\)and empirical transition

ℙ^h\(⋅∣xh,𝒂h\)\\hat\{\\mathbb\{P\}\}\_\{h\}\(\\cdot\\mid x\_\{h\},\\bm\{a\}\_\{h\}\)using the latest sample\.

9:

Qhk​\(i,xh,𝒂h\)←r^​\(xh,𝒂h\)\+∑x′∈𝒮ℙ^h​\(x′∣xh,𝒂h\)​Vh\+1​\(x′\)Q\_\{h\}^\{k\}\(i,x\_\{h\},\\bm\{a\}\_\{h\}\)\\leftarrow\\hat\{r\}\(x\_\{h\},\\bm\{a\}\_\{h\}\)\+\\sum\_\{x^\{\\prime\}\\in\\mathcal\{S\}\}\\hat\{\\mathbb\{P\}\}\_\{h\}\(x^\{\\prime\}\\mid x\_\{h\},\\bm\{a\}\_\{h\}\)\\,V\_\{h\+1\}\(x^\{\\prime\}\)\.

10:

Vh​\(xh\)←min⁡\{H,max𝒂′⁡Qhk​\(i,xh,𝒂′\)\}V\_\{h\}\(x\_\{h\}\)\\leftarrow\\min\\\{H,\\max\_\{\\bm\{a\}^\{\\prime\}\}Q^\{k\}\_\{h\}\(i,x\_\{h\},\\bm\{a\}^\{\\prime\}\)\\\}\.

11:endfor

12:endfor

13:forepisode

k=K′\+1,…,Kk=K^\{\\prime\}\+1,\\ldots,K\(Commit Phase\)do

14:Receive

x1x\_\{1\}\.

15:forstep

h=1,…,Hh=1,\\ldots,Hdo

16:Pick

𝒂h\\bm\{a\}\_\{h\}as the smallest action in

arg⁡max𝒂′​QhK′​\(i,xh,𝒂′\)\\arg\\max\_\{\\bm\{a\}^\{\\prime\}\}Q^\{K^\{\\prime\}\}\_\{h\}\(i,x\_\{h\},\\bm\{a\}^\{\\prime\}\)\.

17:endfor

18:endfor

ThemEXC\-Bellmanvariant uses the plug\-in empirical Bellman equation withℙ^h​\(x′∣x,𝒂\)=Nh​\(x,𝒂,x′\)/Nh​\(x,𝒂\)\\hat\{\\mathbb\{P\}\}\_\{h\}\(x^\{\\prime\}\\mid x,\\bm\{a\}\)=N\_\{h\}\(x,\\bm\{a\},x^\{\\prime\}\)/N\_\{h\}\(x,\\bm\{a\}\)\(the standard model\-based update; cf\.\[[7](https://arxiv.org/html/2608.12753#bib.bib7)\]\)\. It can yield tighter estimates when exploration is long, at the cost of storing transition counts\.

#### Exploration–commit transition\.

Both algorithms use a hard switch at the predetermined episodeK′K^\{\\prime\}, which depends only onKK,SS,AjointA\_\{\\text\{joint\}\},HH\(all common knowledge\), so the switch is communication\-free\. Visit counts are common to all players \(since exploration is joint\), so all players commit simultaneously\. A hard switch is used rather thanϵ\\epsilon\-greedy because the latter would require shared randomness when actions are unobserved\.

###### Theorem 7

Consider Problem C \(full information asymmetry\) withMMplayers and joint action space sizeAjoint=∏i=1M\|𝒜i\|A\_\{\\text\{joint\}\}=\\prod\_\{i=1\}^\{M\}\|\\mathcal\{A\}\_\{i\}\|\. Choose the exploration horizonK′=⌈\(S​Ajoint\)1/3​K2/3⌉K^\{\\prime\}=\\lceil\(SA\_\{\\text\{joint\}\}\)^\{1/3\}K^\{2/3\}\\rceil\. There exists a constantc\>0c\>0such that for anyp∈\(0,1\)p\\in\(0,1\), withbt=c​H3​ι/tb\_\{t\}=c\\sqrt\{H^\{3\}\\iota/t\}andι=log⁡\(M​S​Ajoint​T/p\)\\iota=\\log\(MSA\_\{\\text\{joint\}\}T/p\), with probability at least1−p1\-pthe total regret ofmEXC\(and ofmEXC\-Bellman\) for any player is at most

O⁡\(H​\(S​Ajoint\)1/3​T2/3​ι1/3\)\.O\\\!\\left\(H\\,\(SA\_\{\\text\{joint\}\}\)^\{1/3\}\\,T^\{2/3\}\\,\\iota^\{1/3\}\\right\)\.

###### Proof:

\(Sketch\.\)Total regret decomposes asRT=Rexplore\+RcommitR\_\{T\}=R\_\{\\text\{explore\}\}\+R\_\{\\text\{commit\}\}\. The exploration phase plays an arbitrary policy forK′K^\{\\prime\}episodes, soRexplore≤K′​HR\_\{\\text\{explore\}\}\\leq K^\{\\prime\}H\. AfterK′K^\{\\prime\}episodes of round\-robin exploration, every\(x,𝒂\)\(x,\\bm\{a\}\)has been visited at least⌊K′/\(S​Ajoint\)⌋\\lfloor K^\{\\prime\}/\(SA\_\{\\text\{joint\}\}\)\\rfloortimes in expectation, so by Lemma[12](https://arxiv.org/html/2608.12753#Thmtheorem12)applied to each player’s Q\-table together with a union bound over theMMplayers, with probability≥1−p\\geq 1\-pthe post\-exploration estimates satisfy

\|V1K′​\(x1\)−V1∗​\(x1\)\|≤O⁡\(H4​S​Ajoint​ι/K′\)\|V\_\{1\}^\{K^\{\\prime\}\}\(x\_\{1\}\)\-V\_\{1\}^\{\*\}\(x\_\{1\}\)\|\\leq O\\\!\\Big\(\\\!\\sqrt\{H^\{4\}SA\_\{\\text\{joint\}\}\\iota/K^\{\\prime\}\}\\,\\Big\)for every player\. Since each player commits to the \(lexicographic\-smallest\) greedy policy under their own table, and on the high\-probability event allMMtables agree on the same greedy joint action \(the optimism plus deterministic tie\-breaking argument from Theorem[3](https://arxiv.org/html/2608.12753#Thmtheorem3)extends to Q\-tables that are uniformly close toQ∗Q^\{\*\}\), the commit phase incurs per\-episode suboptimality bounded by the above value\-function error\. Summing,

Rcommit≤\(K−K′\)⋅O⁡\(H4​S​Ajoint​ι/K′\)\.R\_\{\\text\{commit\}\}\\leq\(K\-K^\{\\prime\}\)\\cdot O\\\!\\Big\(\\\!\\sqrt\{H^\{4\}SA\_\{\\text\{joint\}\}\\iota/K^\{\\prime\}\}\\Big\)\.BalancingRexplore=K′​HR\_\{\\text\{explore\}\}=K^\{\\prime\}HandRcommit=O⁡\(K​H4​S​Ajoint​ι/K′\)R\_\{\\text\{commit\}\}=O\(K\\sqrt\{H^\{4\}SA\_\{\\text\{joint\}\}\\iota/K^\{\\prime\}\}\)by settingK′≍\(S​Ajoint\)1/3​K2/3K^\{\\prime\}\\asymp\(SA\_\{\\text\{joint\}\}\)^\{1/3\}K^\{2/3\}yields the claimedO~​\(H​\(S​Ajoint\)1/3​T2/3\)\\tilde\{O\}\(H\(SA\_\{\\text\{joint\}\}\)^\{1/3\}T^\{2/3\}\)regret\. The argument formEXC\-Bellmanis identical, using the standard model\-based plug\-in error bound‖ℙ^−ℙ‖1≤O⁡\(S​ι/N\)\\\|\\hat\{\\mathbb\{P\}\}\-\\mathbb\{P\}\\\|\_\{1\}\\leq O\(\\sqrt\{S\\iota/N\}\)in place of the model\-free concentration step\. ∎

## VAuxiliary Results and Proof Sketches

We present the key technical lemmas that underlie our main results\. Full proofs are deferred to the Appendix\.

### V\-ALearning Rate Properties

For the learning rateαt=\(H\+1\)/\(H\+t\)\\alpha\_\{t\}=\(H\+1\)/\(H\+t\), we define the weights:

αt0=∏j=1t\(1−αj\),αti=αi​∏j=i\+1t\(1−αj\)\.\\alpha\_\{t\}^\{0\}=\\prod\_\{j=1\}^\{t\}\(1\-\\alpha\_\{j\}\),\\quad\\alpha\_\{t\}^\{i\}=\\alpha\_\{i\}\\prod\_\{j=i\+1\}^\{t\}\(1\-\\alpha\_\{j\}\)\.\(5\)
These weights arise naturally when unrolling the recursive Q\-learning update\. The quantityαti\\alpha\_\{t\}^\{i\}represents the effective weight of theii\-th observation aftertttotal observations\.

###### Lemma 10\(Weight Properties\)

The following properties hold for the weights defined in \([5](https://arxiv.org/html/2608.12753#S5.E5)\):

1. \(a\)1t≤∑i=1tαtii≤2t\\frac\{1\}\{\\sqrt\{t\}\}\\leq\\sum\_\{i=1\}^\{t\}\\frac\{\\alpha\_\{t\}^\{i\}\}\{\\sqrt\{i\}\}\\leq\\frac\{2\}\{\\sqrt\{t\}\}\.
2. \(b\)maxi∈\[t\]⁡αti≤2​Ht\\max\_\{i\\in\[t\]\}\\alpha\_\{t\}^\{i\}\\leq\\frac\{2H\}\{t\}and∑i=1t\(αti\)2≤2​Ht\\sum\_\{i=1\}^\{t\}\(\\alpha\_\{t\}^\{i\}\)^\{2\}\\leq\\frac\{2H\}\{t\}\.
3. \(c\)∑t=i∞αti=1\+1H\\sum\_\{t=i\}^\{\\infty\}\\alpha\_\{t\}^\{i\}=1\+\\frac\{1\}\{H\}\.

Property \(c\) is crucial for the regret analysis: it controls how much a single observation’s “influence” accumulates across all future episodes where the same state\-action pair is visited\.

### V\-BRecursion and Optimism

###### Lemma 11\(Recursion\)

For any\(x,𝐚,h\)∈𝒮×𝒜×\[H\]\(x,\\bm\{a\},h\)\\in\\mathcal\{S\}\\times\\mathcal\{A\}\\times\[H\]and episodek∈\[K\]k\\in\[K\], lett=Nhk​\(x,𝐚\)t=N\_\{h\}^\{k\}\(x,\\bm\{a\}\)and suppose\(x,𝐚\)\(x,\\bm\{a\}\)was taken at stephhof episodesk1,…,kt<kk\_\{1\},\\ldots,k\_\{t\}<k\. Then for any playermm:

\(Qhk−Qh∗\)​\(x,𝒂,m\)=αt0​\(H−Qh∗​\(x,𝒂,m\)\)\\displaystyle\(Q\_\{h\}^\{k\}\-Q\_\{h\}^\{\*\}\)\(x,\\bm\{a\},m\)=\\alpha\_\{t\}^\{0\}\(H\-Q\_\{h\}^\{\*\}\(x,\\bm\{a\},m\)\)\+∑i=1tαti\[\(Vh\+1ki−Vh\+1∗\)\(xh\+1ki,m\)\\displaystyle\+\\sum\_\{i=1\}^\{t\}\\alpha\_\{t\}^\{i\}\\Big\[\(V\_\{h\+1\}^\{k\_\{i\}\}\-V\_\{h\+1\}^\{\*\}\)\(x\_\{h\+1\}^\{k\_\{i\}\},m\)\+\[\(P^hki−Ph\)Vh\+1∗\]\(x,𝒂,m\)\+bi\]\.\\displaystyle\\quad\+\[\(\\hat\{P\}\_\{h\}^\{k\_\{i\}\}\-P\_\{h\}\)V\_\{h\+1\}^\{\*\}\]\(x,\\bm\{a\},m\)\+b\_\{i\}\\Big\]\.\(6\)

This recursion decomposes the estimation errorQhk−Qh∗Q\_\{h\}^\{k\}\-Q\_\{h\}^\{\*\}into three components: \(i\) the initialization bias \(decaying viaαt0\\alpha\_\{t\}^\{0\}\), \(ii\) the propagated estimation error from future steps, and \(iii\) the transition estimation error plus the exploration bonus\.

###### Lemma 12\(Optimism\)

There existsc\>0c\>0such that for anyp∈\(0,1\)p\\in\(0,1\), lettingbt=c​H3​ι/tb\_\{t\}=c\\sqrt\{H^\{3\}\\iota/t\}withι=log⁡\(S​A​T/p\)\\iota=\\log\(SAT/p\), with probability≥1−p\\geq 1\-p, for all\(x,𝐚,h,k\)\(x,\\bm\{a\},h,k\):

0≤\(Qhk−Qh∗\)​\(x,𝒂,m\)≤αt0​H\+∑i=1tαti​ϕh\+1ki\+βt0\\leq\(Q\_\{h\}^\{k\}\-Q\_\{h\}^\{\*\}\)\(x,\\bm\{a\},m\)\\leq\\alpha\_\{t\}^\{0\}H\+\\sum\_\{i=1\}^\{t\}\\alpha\_\{t\}^\{i\}\\phi\_\{h\+1\}^\{k\_\{i\}\}\+\\beta\_\{t\}\(7\)whereϕhk=\(Vhk−Vh∗\)​\(xhk\)\\phi\_\{h\}^\{k\}=\(V\_\{h\}^\{k\}\-V\_\{h\}^\{\*\}\)\(x\_\{h\}^\{k\}\)andβt=2​∑i=1tαti​bi≤4​c​H3​ι/t\\beta\_\{t\}=2\\sum\_\{i=1\}^\{t\}\\alpha\_\{t\}^\{i\}b\_\{i\}\\leq 4c\\sqrt\{H^\{3\}\\iota/t\}\.

The lower boundQhk≥Qh∗Q\_\{h\}^\{k\}\\geq Q\_\{h\}^\{\*\}\(optimism\) is essential: it ensures that the algorithm does not prematurely discard optimal actions\. The upper bound controls the overestimation error that drives the regret\.

### V\-CInterval Width for Problem B

###### Lemma 13\(Interval Width\)

After state\-action pair\(x,𝐚\)\(x,\\bm\{a\}\)has been visitedtttimes:

Qup​\(x,𝒂,t\)−Qlow​\(x,𝒂,t\)=2​∑i=1tαti​bi\.Q^\{\\text\{up\}\}\(x,\\bm\{a\};t\)\-Q^\{\\text\{low\}\}\(x,\\bm\{a\};t\)=2\\sum\_\{i=1\}^\{t\}\\alpha\_\{t\}^\{i\}b\_\{i\}\.\(8\)

###### Proof:

For the base case,Qup​\(x,𝒂,1\)−Qlow​\(x,𝒂,1\)=2​α1​b1Q^\{\\text\{up\}\}\(x,\\bm\{a\};1\)\-Q^\{\\text\{low\}\}\(x,\\bm\{a\};1\)=2\\alpha\_\{1\}b\_\{1\}, which satisfies the lemma\. For the inductive step, letn=n⁡\(x,𝒂\)n=n\(x,\\bm\{a\}\):

Qup​\(x,𝒂,n\+1\)−Qlow​\(x,𝒂,n\+1\)\\displaystyle Q^\{\\text\{up\}\}\(x,\\bm\{a\};n\{\+\}1\)\-Q^\{\\text\{low\}\}\(x,\\bm\{a\};n\{\+\}1\)=\(1−αn\+1\)​\(Qup​\(x,𝒂,n\)−Qlow​\(x,𝒂,n\)\)\+2​αn\+1​bn\+1\\displaystyle=\(1\-\\alpha\_\{n\+1\}\)\\big\(Q^\{\\text\{up\}\}\(x,\\bm\{a\};n\)\-Q^\{\\text\{low\}\}\(x,\\bm\{a\};n\)\\big\)\+2\\alpha\_\{n\+1\}b\_\{n\+1\}=\(1−αn\+1\)⋅2∑i=1nαnibi\+2αn\+1bn\+1\\displaystyle=\(1\-\\alpha\_\{n\+1\}\)\\cdot 2\\sum\_\{i=1\}^\{n\}\\alpha\_\{n\}^\{i\}b\_\{i\}\+2\\alpha\_\{n\+1\}b\_\{n\+1\}=2​∑i=1n\+1αn\+1i​bi,\\displaystyle=2\\sum\_\{i=1\}^\{n\+1\}\\alpha\_\{n\+1\}^\{i\}b\_\{i\},\(9\)where the last step usesαn\+1i=αi​∏j=i\+1n\+1\(1−αj\)\\alpha\_\{n\+1\}^\{i\}=\\alpha\_\{i\}\\prod\_\{j=i\+1\}^\{n\+1\}\(1\-\\alpha\_\{j\}\), completing the induction\. ∎

Using Lemma[10](https://arxiv.org/html/2608.12753#Thmtheorem10)\(a\), the interval width satisfiesQup−Qlow≤O⁡\(H3​ι/t\)Q^\{\\text\{up\}\}\-Q^\{\\text\{low\}\}\\leq O\(\\sqrt\{H^\{3\}\\iota/t\}\), which decays at the same rate as the bonusbtb\_\{t\}\.

### V\-DConcentration via Azuma\-Hoeffding

The proofs also rely on the Azuma\-Hoeffding inequality to control the martingale difference terms that arise from transition estimation errors\. Define the martingale differenceξh\+1k:=\[\(ℙh−ℙ^hk\)​\(Vh\+1∗−Vh\+1k\)\]​\(xhk,ahk\)\\xi\_\{h\+1\}^\{k\}:=\[\(\\mathbb\{P\}\_\{h\}\-\\hat\{\\mathbb\{P\}\}\_\{h\}^\{k\}\)\(V\_\{h\+1\}^\{\*\}\-V\_\{h\+1\}^\{k\}\)\]\(x\_\{h\}^\{k\},a\_\{h\}^\{k\}\)\. Since\|\[\(ℙ^hki−ℙh\)​Vh\+1∗\]​\(x,a\)\|≤H\|\[\(\\hat\{\\mathbb\{P\}\}\_\{h\}^\{k\_\{i\}\}\-\\mathbb\{P\}\_\{h\}\)V\_\{h\+1\}^\{\*\}\]\(x,a\)\|\\leq H, Azuma\-Hoeffding gives:

Pr⁡\(\|∑h=1H∑k=1Kξh\+1k\|≥ϵ\)≤2​exp⁡\(−ϵ22​K​H3\)\.\\Pr\\\!\\left\(\\left\|\\sum\_\{h=1\}^\{H\}\\sum\_\{k=1\}^\{K\}\\xi\_\{h\+1\}^\{k\}\\right\|\\geq\\epsilon\\right\)\\leq 2\\exp\\\!\\left\(\\frac\{\-\\epsilon^\{2\}\}\{2KH^\{3\}\}\\right\)\.\(10\)Setting the right\-hand side equal toppand solving forϵ\\epsilonyields the claimed concentration bound\.

### V\-EProof Sketch for Theorem[3](https://arxiv.org/html/2608.12753#Thmtheorem3)

Defineδhk:=\(Vhk−Vhπk\)​\(xhk\)\\delta\_\{h\}^\{k\}:=\(V\_\{h\}^\{k\}\-V\_\{h\}^\{\\pi\_\{k\}\}\)\(x\_\{h\}^\{k\}\)andϕhk:=\(Vhk−Vh∗\)​\(xhk\)\\phi\_\{h\}^\{k\}:=\(V\_\{h\}^\{k\}\-V\_\{h\}^\{\*\}\)\(x\_\{h\}^\{k\}\)\. By optimism \(Lemma[12](https://arxiv.org/html/2608.12753#Thmtheorem12)\),RT≤∑k=1Kδ1kR\_\{T\}\\leq\\sum\_\{k=1\}^\{K\}\\delta\_\{1\}^\{k\}\. Decomposingδhk\\delta\_\{h\}^\{k\}via the Bellman equation and Lemma[12](https://arxiv.org/html/2608.12753#Thmtheorem12)yields a recursive relation:

∑k=1Kδhk≤S​A​H\+\(1\+1H\)​∑k=1Kδh\+1k\+∑k=1K\(βnhk\+ξh\+1k\)\.\\sum\_\{k=1\}^\{K\}\\delta\_\{h\}^\{k\}\\leq SAH\+\\left\(1\+\\frac\{1\}\{H\}\\right\)\\sum\_\{k=1\}^\{K\}\\delta\_\{h\+1\}^\{k\}\+\\sum\_\{k=1\}^\{K\}\(\\beta\_\{n\_\{h\}^\{k\}\}\+\\xi\_\{h\+1\}^\{k\}\)\.\(11\)
Recursing overhhand bounding the bonus terms via pigeonhole and Azuma\-Hoeffding gives the result\. See Appendix[D](https://arxiv.org/html/2608.12753#A4)for the complete proof\.

## VIComparison of Approaches

The three problem settings share a common skeleton—joint\-action Q\-learning with deterministic tie\-breaking—but differ in how players reach agreement\. In Problem A, common rewards and common transitions make all players’ Q\-tables identical at every step, so lexicographic tie\-breaking on thearg⁡max\\arg\\maxset picks the same joint action without any communication\. In Problem B, independent rewards prevent identical Q\-tables, but observable actions let each player use a*unilateral deviation*as an implicit dominance signal: when one player deviates from the candidate action, the others infer that player has found a strictly better alternative and eliminate the candidate from the desired set\. In Problem C, neither mechanism is available, so we fall back to explore\-then\-commit with a deterministic schedule shared a priori\.

The regret rates reflect this hierarchy\. Problems A and B both achieveO~​\(H4​S​Ajoint​T\)\\tilde\{O\}\(\\sqrt\{H^\{4\}SA\_\{\\text\{joint\}\}\\,T\}\)\(Theorems[3](https://arxiv.org/html/2608.12753#Thmtheorem3)and[5](https://arxiv.org/html/2608.12753#Thmtheorem5)\), matching centralized single\-agent learning\[[7](https://arxiv.org/html/2608.12753#bib.bib7)\]against the joint\-action benchmark\. Problem C achievesO~​\(H​\(S​Ajoint\)1/3​T2/3\)\\tilde\{O\}\(H\(SA\_\{\\text\{joint\}\}\)^\{1/3\}T^\{2/3\}\)\(Theorem[7](https://arxiv.org/html/2608.12753#Thmtheorem7)\), the standard penalty of explore\-then\-commit when the suboptimality gap is unknown\. TheT2/3T^\{2/3\}rate is worse thanT\\sqrt\{T\}but still sublinear; whether it can be improved toT\\sqrt\{T\}for Problem C remains open\.

A useful way to think about the gap from Problems A/B to Problem C is that observability of*either*actions or rewards is enough to encode a low\-bandwidth signal between players, and that signal suffices to recover theT\\sqrt\{T\}rate\. Problem C removes both channels, and the only remaining shared information—visit counts of jointly\-played actions—is too coarse to drive UCB\-style adaptive exploration; hence the retreat to a non\-adaptive schedule\.

## VIIDiscussion

### VII\-AReduction to Centralized Joint\-Action Q\-Learning

The relationship between Algorithm[1](https://arxiv.org/html/2608.12753#alg1)and a centralized learner is direct: a single agent running UCB\-Q\-learning\[[7](https://arxiv.org/html/2608.12753#bib.bib7)\]on the joint MDP\(𝒮,𝒜1×⋯×𝒜M,H,ℙ,r\)\(\\mathcal\{S\},\\mathcal\{A\}\_\{1\}\\times\\cdots\\times\\mathcal\{A\}\_\{M\},H,\\mathbb\{P\},r\)produces a Q\-table identical to that of any one player in Algorithm[1](https://arxiv.org/html/2608.12753#alg1), since Problem A players see the same reward, same next state, and same update with the same tie\-breaking\. The decentralized algorithm inherits the centralized regret bound\. Problem B adds a one\-bit\-per\-step deviation signal that carries exactly the information the centralized learner uses internally to eliminate dominated actions\.

### VII\-BDependence on the Number of Players

The bounds depend onMMonly throughAjointA\_\{\\text\{joint\}\}\. There is no separate polynomial factor inMM: doublingMMwhile keepingAjointA\_\{\\text\{joint\}\}fixed—e\.g\. splitting one player with\|𝒜\|=4\|\\mathcal\{A\}\|=4into two players with\|𝒜i\|=2\|\\mathcal\{A\}\_\{i\}\|=2—does not change the regret\. From the joint\-action viewpoint, the partition into per\-player components is irrelevant\. The exponential dependence onMMthroughAjointA\_\{\\text\{joint\}\}is therefore a property of the*tabular*setting, not of the asymmetry: any worst\-case bound against arbitrary joint policies must pay at leastAjoint\\sqrt\{A\_\{\\text\{joint\}\}\}\. Removing this requires structural assumptions on the joint Q\-function \(factored MDPs, mean\-field couplings, linear function approximation\), each a natural next direction\.

### VII\-CWhen the Bounds Are Practical

WithM=2M=2,\|𝒜i\|=3\|\\mathcal\{A\}\_\{i\}\|=3,S=10S=10,H=20H=20, our Problem A bound puts the per\-episode suboptimality below0\.10\.1onceK≳105K\\gtrsim 10^\{5\}, comparable to centralized Q\-learning on the same joint MDP\. WithM=4M=4and\|𝒜i\|=3\|\\mathcal\{A\}\_\{i\}\|=3\(Ajoint=81A\_\{\\text\{joint\}\}=81\), the same threshold needsK≳106K\\gtrsim 10^\{6\}\. Beyond that, structural assumptions are needed\.

## VIIIRelated Work

#### Multi\-Player Bandits\.

The multi\-player MAB problem has been studied under various information structures\. The collision model\[[3](https://arxiv.org/html/2608.12753#bib.bib9)\]forbids two players from choosing the same arm\. In the cooperative setting without collisions, Chang et al\.\[[4](https://arxiv.org/html/2608.12753#bib.bib6)\]introduced the information\-asymmetry framework that we extend, and\[[5](https://arxiv.org/html/2608.12753#bib.bib8)\]achieved optimal regret without communication in the bandit case\.

#### Episodic MDPs\.

For single\-agent episodic MDPs, Jin et al\.\[[7](https://arxiv.org/html/2608.12753#bib.bib7)\]proved that optimistic Q\-learning achievesO~​\(H4​S​A​T\)\\tilde\{O\}\(\\sqrt\{H^\{4\}SAT\}\)regret model\-free\. Our work extends this to the multi\-player setting under information asymmetry\.

#### Game\-Theoretic Learning\.

The literature on uncoupled dynamics\[[6](https://arxiv.org/html/2608.12753#bib.bib5)\]studies whether players reach equilibria without knowing each other’s payoffs;\[[6](https://arxiv.org/html/2608.12753#bib.bib5)\]shows uncoupled dynamics cannot generally reach Nash equilibrium, suggesting fundamental limits to communication\-free learning\. Our cooperative setting is distinct from the competitive game\-theoretic framework but shares the no\-communication constraint\.

## IXConclusion

We studied multi\-player decentralized reinforcement learning in episodic MDPs under three information\-asymmetry models\. For Problems A and B we obtainO~​\(H4​S​Ajoint​T\)\\tilde\{O\}\(\\sqrt\{H^\{4\}SA\_\{\\text\{joint\}\}\\,T\}\)regret, matching the single\-agent rate of\[[7](https://arxiv.org/html/2608.12753#bib.bib7)\]against the joint\-action benchmark up to logarithmic factors\. For Problem C we obtainO~​\(H​\(S​Ajoint\)1/3​T2/3\)\\tilde\{O\}\(H\(SA\_\{\\text\{joint\}\}\)^\{1/3\}T^\{2/3\}\)via explore\-then\-commit\. All bounds depend onAjoint=∏i=1M\|𝒜i\|A\_\{\\text\{joint\}\}=\\prod\_\{i=1\}^\{M\}\|\\mathcal\{A\}\_\{i\}\|, which grows exponentially inMM: 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\.

## Acknowledgment

The authors thank colleagues at UCLA for helpful discussions\.

## Appendix AProof of Lemma[10](https://arxiv.org/html/2608.12753#Thmtheorem10)\(Weight Properties\)

###### Proof:

A direct computation givesαti=H\+1H\+i​∏j=i\+1tj−1H\+j\\alpha\_\{t\}^\{i\}=\\frac\{H\+1\}\{H\+i\}\\prod\_\{j=i\+1\}^\{t\}\\frac\{j\-1\}\{H\+j\}fori≥1i\\geq 1\.

\(a\)Standard Beta\-function identities \(cf\.\[[7](https://arxiv.org/html/2608.12753#bib.bib7), Lemma 4\.1\]\) yield∑iαti=1\\sum\_\{i\}\\alpha\_\{t\}^\{i\}=1fort≥1t\\geq 1, and∑iαti/i\\sum\_\{i\}\\alpha\_\{t\}^\{i\}/\\sqrt\{i\}lies between1/t1/\\sqrt\{t\}and2/t2/\\sqrt\{t\}\.

\(b\)The ratioαti/αti\+1\\alpha\_\{t\}^\{i\}/\\alpha\_\{t\}^\{i\+1\}shows the sequence is maximized ati=ti=t, givingmaxi⁡αti=αt=\(H\+1\)/\(H\+t\)≤2​H/t\\max\_\{i\}\\alpha\_\{t\}^\{i\}=\\alpha\_\{t\}=\(H\+1\)/\(H\+t\)\\leq 2H/t\. Hence∑i\(αti\)2≤maxi⁡αti⋅∑iαti≤2​H/t\\sum\_\{i\}\(\\alpha\_\{t\}^\{i\}\)^\{2\}\\leq\\max\_\{i\}\\alpha\_\{t\}^\{i\}\\cdot\\sum\_\{i\}\\alpha\_\{t\}^\{i\}\\leq 2H/t\.

\(c\)Telescoping the product representation gives∑t≥iαti=\(H\+1\)/H=1\+1/H\\sum\_\{t\\geq i\}\\alpha\_\{t\}^\{i\}=\(H\+1\)/H=1\+1/H\. ∎

## Appendix BProof of Lemma[11](https://arxiv.org/html/2608.12753#Thmtheorem11)\(Recursion\)

###### Proof:

By induction ont=Nhk​\(x,𝒂\)t=N\_\{h\}^\{k\}\(x,\\bm\{a\}\)\. Att=0t=0,Qhk​\(x,𝒂\)=HQ\_\{h\}^\{k\}\(x,\\bm\{a\}\)=H, matchingα00​\(H−Qh∗\)\\alpha\_\{0\}^\{0\}\(H\-Q\_\{h\}^\{\*\}\)\. For the inductive step, letktk\_\{t\}be the episode of thett\-th visit\. The update on line 8 of Algorithm[1](https://arxiv.org/html/2608.12753#alg1), minusQh∗=rh\+ℙh​Vh\+1∗Q\_\{h\}^\{\*\}=r\_\{h\}\+\\mathbb\{P\}\_\{h\}V\_\{h\+1\}^\{\*\}, gives

Qhkt−Qh∗\\displaystyle Q\_\{h\}^\{k\_\{t\}\}\-Q\_\{h\}^\{\*\}=\(1−αt\)​\(Qhkt,pre−Qh∗\)\\displaystyle=\(1\-\\alpha\_\{t\}\)\(Q\_\{h\}^\{k\_\{t\},\\text\{pre\}\}\-Q\_\{h\}^\{\*\}\)\+αt\[\(Vh\+1kt−Vh\+1∗\)\(xh\+1kt\)\\displaystyle\\quad\+\\alpha\_\{t\}\\big\[\(V\_\{h\+1\}^\{k\_\{t\}\}\-V\_\{h\+1\}^\{\*\}\)\(x\_\{h\+1\}^\{k\_\{t\}\}\)\+\[\(ℙ^hkt−ℙh\)Vh\+1∗\]\(x,𝒂\)\+bt\],\\displaystyle\\quad\\quad\+\[\(\\hat\{\\mathbb\{P\}\}\_\{h\}^\{k\_\{t\}\}\-\\mathbb\{P\}\_\{h\}\)V\_\{h\+1\}^\{\*\}\]\(x,\\bm\{a\}\)\+b\_\{t\}\\big\],whereℙ^hkt\\hat\{\\mathbb\{P\}\}\_\{h\}^\{k\_\{t\}\}is the one\-sample empirical kernel\. Using the identity\(1−αt\)​αt−1i=αti\(1\-\\alpha\_\{t\}\)\\alpha\_\{t\-1\}^\{i\}=\\alpha\_\{t\}^\{i\}fori<ti<tandαtt=αt\\alpha\_\{t\}^\{t\}=\\alpha\_\{t\}, the inductive hypothesis unrolls to \([6](https://arxiv.org/html/2608.12753#S5.E6)\)\. ∎

## Appendix CProof of Lemma[12](https://arxiv.org/html/2608.12753#Thmtheorem12)\(Optimism\)

###### Proof:

We proveQhk≥Qh∗Q\_\{h\}^\{k\}\\geq Q\_\{h\}^\{\*\}by induction backward onhh\(the caseh=H\+1h=H\+1is trivial\)\. By Lemma[11](https://arxiv.org/html/2608.12753#Thmtheorem11),

Qhk−Qh∗=αt0​\(H−Qh∗\)\+∑i=1tαti​\[\(Vh\+1ki−Vh\+1∗\)\+ζi\+bi\],Q\_\{h\}^\{k\}\-Q\_\{h\}^\{\*\}=\\alpha\_\{t\}^\{0\}\(H\-Q\_\{h\}^\{\*\}\)\+\\sum\_\{i=1\}^\{t\}\\alpha\_\{t\}^\{i\}\\big\[\(V\_\{h\+1\}^\{k\_\{i\}\}\-V\_\{h\+1\}^\{\*\}\)\+\\zeta\_\{i\}\+b\_\{i\}\\big\],whereζi:=\[\(ℙ^hki−ℙh\)​Vh\+1∗\]​\(x,𝒂\)\\zeta\_\{i\}:=\[\(\\hat\{\\mathbb\{P\}\}\_\{h\}^\{k\_\{i\}\}\-\\mathbb\{P\}\_\{h\}\)V\_\{h\+1\}^\{\*\}\]\(x,\\bm\{a\}\)is a bounded martingale difference \(\|ζi\|≤H\|\\zeta\_\{i\}\|\\leq H\)\. The first two terms are non\-negative by induction\. By Azuma–Hoeffding and Lemma[10](https://arxiv.org/html/2608.12753#Thmtheorem10)\(b\), with probability≥1−p/\(S​A​H​K\)\\geq 1\-p/\(SAHK\),

\|∑iαti​ζi\|≤H​2​ι​∑i\(αti\)2≤c​H3​ι/t,\\Big\|\\sum\_\{i\}\\alpha\_\{t\}^\{i\}\\zeta\_\{i\}\\Big\|\\leq H\\sqrt\{2\\iota\\sum\_\{i\}\(\\alpha\_\{t\}^\{i\}\)^\{2\}\}\\leq c\\sqrt\{H^\{3\}\\iota/t\},which is dominated by∑iαti​bi\\sum\_\{i\}\\alpha\_\{t\}^\{i\}b\_\{i\}for our choicebi=c​H3​ι/ib\_\{i\}=c\\sqrt\{H^\{3\}\\iota/i\}\. HenceQhk≥Qh∗Q\_\{h\}^\{k\}\\geq Q\_\{h\}^\{\*\}\. Union\-bounding over\(x,𝒂,h,k\)\(x,\\bm\{a\},h,k\)absorbs anS​A​H​K≤S​A​TSAHK\\leq SATfactor intoι\\iota\. The upper bound \([7](https://arxiv.org/html/2608.12753#S5.E7)\) follows from the same decomposition, with the factor22inβt=2​∑iαti​bi\\beta\_\{t\}=2\\sum\_\{i\}\\alpha\_\{t\}^\{i\}b\_\{i\}absorbing the \(positive\) contribution ofζi\\zeta\_\{i\}; Lemma[10](https://arxiv.org/html/2608.12753#Thmtheorem10)\(a\) givesβt≤4​c​H3​ι/t\\beta\_\{t\}\\leq 4c\\sqrt\{H^\{3\}\\iota/t\}\. ∎

## Appendix DProof of Theorem[3](https://arxiv.org/html/2608.12753#Thmtheorem3)

###### Proof:

Denoteδhk:=\(Vhk−Vhπk\)​\(xhk\)\\delta\_\{h\}^\{k\}:=\(V\_\{h\}^\{k\}\-V\_\{h\}^\{\\pi\_\{k\}\}\)\(x\_\{h\}^\{k\}\)andϕhk:=\(Vhk−Vh∗\)​\(xhk\)\\phi\_\{h\}^\{k\}:=\(V\_\{h\}^\{k\}\-V\_\{h\}^\{\*\}\)\(x\_\{h\}^\{k\}\)\.

By Lemma[12](https://arxiv.org/html/2608.12753#Thmtheorem12), with probability1−p1\-p,Qhk≥Qh∗Q\_\{h\}^\{k\}\\geq Q\_\{h\}^\{\*\}and thusVhk≥Vh∗V\_\{h\}^\{k\}\\geq V\_\{h\}^\{\*\}\. The total regret is bounded:

RT=∑k=1K\(V1∗−V1πk\)​\(x1k\)≤∑k=1Kδ1k\.R\_\{T\}=\\sum\_\{k=1\}^\{K\}\(V\_\{1\}^\{\*\}\-V\_\{1\}^\{\\pi\_\{k\}\}\)\(x\_\{1\}^\{k\}\)\\leq\\sum\_\{k=1\}^\{K\}\\delta\_\{1\}^\{k\}\.\(12\)
For any fixed\(k,h\)\(k,h\), lett=Nhk​\(xhk,ahk\)t=N\_\{h\}^\{k\}\(x\_\{h\}^\{k\},a\_\{h\}^\{k\}\), and suppose\(xhk,ahk\)\(x\_\{h\}^\{k\},a\_\{h\}^\{k\}\)was taken at stephhof episodesk1,…,kt<kk\_\{1\},\\ldots,k\_\{t\}<k\. Then:

δhk\\displaystyle\\delta\_\{h\}^\{k\}=\(Vhk−Vhπk\)​\(xhk\)≤\(Qhk−Qhπk\)​\(xhk,ahk\)\\displaystyle=\(V\_\{h\}^\{k\}\-V\_\{h\}^\{\\pi\_\{k\}\}\)\(x\_\{h\}^\{k\}\)\\leq\(Q\_\{h\}^\{k\}\-Q\_\{h\}^\{\\pi\_\{k\}\}\)\(x\_\{h\}^\{k\},a\_\{h\}^\{k\}\)\(13\)=\(Qhk−Qh∗\)​\(xhk,ahk\)\+\(Qh∗−Qhπk\)​\(xhk,ahk\)\\displaystyle=\(Q\_\{h\}^\{k\}\-Q\_\{h\}^\{\*\}\)\(x\_\{h\}^\{k\},a\_\{h\}^\{k\}\)\+\(Q\_\{h\}^\{\*\}\-Q\_\{h\}^\{\\pi\_\{k\}\}\)\(x\_\{h\}^\{k\},a\_\{h\}^\{k\}\)≤αt0​H\+∑i=1tαti​ϕh\+1ki\+βt\\displaystyle\\leq\\alpha\_\{t\}^\{0\}H\+\\sum\_\{i=1\}^\{t\}\\alpha\_\{t\}^\{i\}\\phi\_\{h\+1\}^\{k\_\{i\}\}\+\\beta\_\{t\}\+\[ℙh​\(Vh\+1∗−Vh\+1πk\)\]​\(xhk,ahk\)\\displaystyle\\quad\+\[\\mathbb\{P\}\_\{h\}\(V\_\{h\+1\}^\{\*\}\-V\_\{h\+1\}^\{\\pi\_\{k\}\}\)\]\(x\_\{h\}^\{k\},a\_\{h\}^\{k\}\)\(14\)=αt0​H\+∑i=1tαti​ϕh\+1ki\+βt−ϕh\+1k\+δh\+1k\+ξh\+1k\\displaystyle=\\alpha\_\{t\}^\{0\}H\+\\sum\_\{i=1\}^\{t\}\\alpha\_\{t\}^\{i\}\\phi\_\{h\+1\}^\{k\_\{i\}\}\+\\beta\_\{t\}\-\\phi\_\{h\+1\}^\{k\}\+\\delta\_\{h\+1\}^\{k\}\+\\xi\_\{h\+1\}^\{k\}\(15\)whereβt=2​∑αti​bi≤O⁡\(1\)​H3​ι/t\\beta\_\{t\}=2\\sum\\alpha\_\{t\}^\{i\}b\_\{i\}\\leq O\(1\)\\sqrt\{H^\{3\}\\iota/t\}andξh\+1k:=\[\(ℙh−ℙ^hk\)​\(Vh\+1∗−Vh\+1k\)\]​\(xhk,ahk\)\\xi\_\{h\+1\}^\{k\}:=\[\(\\mathbb\{P\}\_\{h\}\-\\hat\{\\mathbb\{P\}\}\_\{h\}^\{k\}\)\(V\_\{h\+1\}^\{\*\}\-V\_\{h\+1\}^\{k\}\)\]\(x\_\{h\}^\{k\},a\_\{h\}^\{k\}\)is a martingale difference sequence\. Inequality \([13](https://arxiv.org/html/2608.12753#A4.E13)\) holds becauseVhk​\(xhk\)≤Qhk​\(xhk,ahk\)V\_\{h\}^\{k\}\(x\_\{h\}^\{k\}\)\\leq Q\_\{h\}^\{k\}\(x\_\{h\}^\{k\},a\_\{h\}^\{k\}\), and inequality \([14](https://arxiv.org/html/2608.12753#A4.E14)\) holds by Lemma[12](https://arxiv.org/html/2608.12753#Thmtheorem12)and the Bellman equation \([3](https://arxiv.org/html/2608.12753#S2.E3)\)\. Equality \([15](https://arxiv.org/html/2608.12753#A4.E15)\) follows fromδh\+1k−ϕh\+1k=\(Vh\+1∗−Vh\+1πk\)​\(xh\+1k\)\\delta\_\{h\+1\}^\{k\}\-\\phi\_\{h\+1\}^\{k\}=\(V\_\{h\+1\}^\{\*\}\-V\_\{h\+1\}^\{\\pi\_\{k\}\}\)\(x\_\{h\+1\}^\{k\}\)\.

Computing∑k=1Kδhk\\sum\_\{k=1\}^\{K\}\\delta\_\{h\}^\{k\}, the initialization term gives:

∑k=1Kαnhk0H=∑k=1KH⋅𝕀\[nhk=0\]≤SAH\.\\sum\_\{k=1\}^\{K\}\\alpha\_\{n\_\{h\}^\{k\}\}^\{0\}H=\\sum\_\{k=1\}^\{K\}H\\cdot\\mathbb\{I\}\[n\_\{h\}^\{k\}=0\]\\leq SAH\.\(16\)
For the weighted sum term, we regroup: for everyk′∈\[K\]k^\{\\prime\}\\in\[K\], the termϕh\+1k′\\phi\_\{h\+1\}^\{k^\{\\prime\}\}appears in the summand withk\>k′k\>k^\{\\prime\}whenever\(xhk,ahk\)=\(xhk′,ahk′\)\(x\_\{h\}^\{k\},a\_\{h\}^\{k\}\)=\(x\_\{h\}^\{k^\{\\prime\}\},a\_\{h\}^\{k^\{\\prime\}\}\)\. Therefore:

∑k=1K∑i=1nhkαnhki​ϕh\+1ki≤\(1\+1H\)​∑k=1Kϕh\+1k\\sum\_\{k=1\}^\{K\}\\sum\_\{i=1\}^\{n\_\{h\}^\{k\}\}\\alpha\_\{n\_\{h\}^\{k\}\}^\{i\}\\phi\_\{h\+1\}^\{k\_\{i\}\}\\leq\\left\(1\+\\frac\{1\}\{H\}\\right\)\\sum\_\{k=1\}^\{K\}\\phi\_\{h\+1\}^\{k\}\(17\)using∑t=i∞αti=1\+1/H\\sum\_\{t=i\}^\{\\infty\}\\alpha\_\{t\}^\{i\}=1\+1/Hfrom Lemma[10](https://arxiv.org/html/2608.12753#Thmtheorem10)\(c\)\. Sinceϕh\+1k≤δh\+1k\\phi\_\{h\+1\}^\{k\}\\leq\\delta\_\{h\+1\}^\{k\}\(becauseV∗≥VπkV^\{\*\}\\geq V^\{\\pi\_\{k\}\}\):

∑k=1Kδhk\\displaystyle\\sum\_\{k=1\}^\{K\}\\delta\_\{h\}^\{k\}≤S​A​H\+\(1\+1H\)​∑k=1Kδh\+1k\\displaystyle\\leq SAH\+\\left\(1\+\\frac\{1\}\{H\}\\right\)\\sum\_\{k=1\}^\{K\}\\delta\_\{h\+1\}^\{k\}\+∑k=1K\(βnhk\+ξh\+1k\)\.\\displaystyle\\quad\+\\sum\_\{k=1\}^\{K\}\(\\beta\_\{n\_\{h\}^\{k\}\}\+\\xi\_\{h\+1\}^\{k\}\)\.\(18\)
Recursing forh=1,…,Hh=1,\\ldots,Hand usingδH\+1k≡0\\delta\_\{H\+1\}^\{k\}\\equiv 0:

∑k=1Kδ1k≤O⁡\(H2​S​A\+∑h=1H∑k=1K\(βnhk\+ξh\+1k\)\)\.\\sum\_\{k=1\}^\{K\}\\delta\_\{1\}^\{k\}\\leq O\\\!\\left\(H^\{2\}SA\+\\sum\_\{h=1\}^\{H\}\\sum\_\{k=1\}^\{K\}\(\\beta\_\{n\_\{h\}^\{k\}\}\+\\xi\_\{h\+1\}^\{k\}\)\\right\)\.\(19\)
By the pigeonhole principle, for anyh∈\[H\]h\\in\[H\]:

∑k=1Kβnhk\\displaystyle\\sum\_\{k=1\}^\{K\}\\beta\_\{n\_\{h\}^\{k\}\}≤O⁡\(1\)​∑x,a∑n=1NhK​\(x,a\)H3​ιn≤O⁡\(H2​S​A​T​ι\)\\displaystyle\\leq O\(1\)\\sum\_\{x,a\}\\sum\_\{n=1\}^\{N\_\{h\}^\{K\}\(x,a\)\}\\sqrt\{\\frac\{H^\{3\}\\iota\}\{n\}\}\\leq O\(\\sqrt\{H^\{2\}SAT\\iota\}\)\(20\)where the last inequality uses∑x,aNhK​\(x,a\)=K\\sum\_\{x,a\}N\_\{h\}^\{K\}\(x,a\)=Kand is maximized whenNhK​\(x,a\)=K/\(S​A\)N\_\{h\}^\{K\}\(x,a\)=K/\(SA\)for allx,ax,a\. By Azuma\-Hoeffding, with probability1−p1\-p:

\|∑h=1H∑k=1Kξh\+1k\|≤c​H​T​ι\.\\left\|\\sum\_\{h=1\}^\{H\}\\sum\_\{k=1\}^\{K\}\\xi\_\{h\+1\}^\{k\}\\right\|\\leq cH\\sqrt\{T\\iota\}\.\(21\)
Combining,∑k=1Kδ1k≤O⁡\(H2​S​A\+H4​S​A​T​ι\)\\sum\_\{k=1\}^\{K\}\\delta\_\{1\}^\{k\}\\leq O\(H^\{2\}SA\+\\sqrt\{H^\{4\}SAT\\iota\}\)\. WhenT≥H2​S​AT\\geq H^\{2\}SA, the second term dominates\. WhenT<H2​S​AT<H^\{2\}SA, the trivial bound∑k=1Kδ1k≤H​K=T≤H4​S​A​T​ι\\sum\_\{k=1\}^\{K\}\\delta\_\{1\}^\{k\}\\leq HK=T\\leq\\sqrt\{H^\{4\}SAT\\iota\}applies\. ThereforeRT≤O⁡\(H4​S​A​T​ι\)R\_\{T\}\\leq O\(\\sqrt\{H^\{4\}SAT\\iota\}\)with probability≥1−2​p\\geq 1\-2p\. Rescalingpptop/2p/2completes the proof\. ∎

## Appendix EProof of Theorem[5](https://arxiv.org/html/2608.12753#Thmtheorem5)

###### Proof:

By Lemma[12](https://arxiv.org/html/2608.12753#Thmtheorem12)applied to each player, with probability\(1−p\)M\(1\-p\)^\{M\},Qhk≥Qh∗Q\_\{h\}^\{k\}\\geq Q\_\{h\}^\{\*\}for all players\. Since regret is evaluated with respect to expectations and all players receive i\.i\.d\. rewards, we omit the player index for the remainder\.

Defineδhk\\delta\_\{h\}^\{k\}andϕhk\\phi\_\{h\}^\{k\}as in Appendix[D](https://arxiv.org/html/2608.12753#A4)\. The decomposition forδhk\\delta\_\{h\}^\{k\}is:

δhk\\displaystyle\\delta\_\{h\}^\{k\}=Vhk​\(xhk\)−Vhπk​\(xhk\)\\displaystyle=V^\{k\}\_\{h\}\(x\_\{h\}^\{k\}\)\-V^\{\\pi\_\{k\}\}\_\{h\}\(x\_\{h\}^\{k\}\)\(22\)≤max𝒂⁡Qhk​\(xhk,𝒂\)−Qhπk​\(xhk,𝒂hk\)\\displaystyle\\leq\\max\_\{\\bm\{a\}\}Q\_\{h\}^\{k\}\(x\_\{h\}^\{k\},\\bm\{a\}\)\-Q\_\{h\}^\{\\pi\_\{k\}\}\(x\_\{h\}^\{k\},\\bm\{a\}\_\{h\}^\{k\}\)\(23\)=max𝒂⁡Qhk​\(xhk,𝒂\)−Qhk​\(xhk,𝒂hk\)⏟A\\displaystyle=\\underbrace\{\\max\_\{\\bm\{a\}\}Q\_\{h\}^\{k\}\(x\_\{h\}^\{k\},\\bm\{a\}\)\-Q\_\{h\}^\{k\}\(x\_\{h\}^\{k\},\\bm\{a\}\_\{h\}^\{k\}\)\}\_\{A\}\+\(Qhk−Qh∗\)​\(xhk,𝒂hk\)\+\(Qh∗−Qhπk\)​\(xhk,𝒂hk\)\.\\displaystyle\\quad\+\(Q\_\{h\}^\{k\}\-Q\_\{h\}^\{\*\}\)\(x\_\{h\}^\{k\},\\bm\{a\}\_\{h\}^\{k\}\)\+\(Q\_\{h\}^\{\*\}\-Q\_\{h\}^\{\\pi\_\{k\}\}\)\(x\_\{h\}^\{k\},\\bm\{a\}\_\{h\}^\{k\}\)\.\(24\)
TermAAaccounts for the fact that the action𝒂hk\\bm\{a\}\_\{h\}^\{k\}played \(from the desired set\) may not be the greedy action\. Since actions in the desired set have upper Q\-values within the interval width of the best action, by Lemma[13](https://arxiv.org/html/2608.12753#Thmtheorem13):

A≤Qup​\(xhk,𝒂hk,t\)−Qlow​\(xhk,𝒂hk,t\)=2​∑i=1tαti​bi\.A\\leq Q^\{\\text\{up\}\}\(x\_\{h\}^\{k\},\\bm\{a\}\_\{h\}^\{k\};t\)\-Q^\{\\text\{low\}\}\(x\_\{h\}^\{k\},\\bm\{a\}\_\{h\}^\{k\};t\)=2\\sum\_\{i=1\}^\{t\}\\alpha\_\{t\}^\{i\}b\_\{i\}\.\(25\)
Applying Lemma[12](https://arxiv.org/html/2608.12753#Thmtheorem12)and the Bellman equation for the remaining terms:

δhk\\displaystyle\\delta\_\{h\}^\{k\}≤2​∑i=1tαti​bi\+αt0​H\+∑i=1tαti​ϕh\+1ki\+βt\\displaystyle\\leq 2\\sum\_\{i=1\}^\{t\}\\alpha\_\{t\}^\{i\}b\_\{i\}\+\\alpha\_\{t\}^\{0\}H\+\\sum\_\{i=1\}^\{t\}\\alpha\_\{t\}^\{i\}\\phi\_\{h\+1\}^\{k\_\{i\}\}\+\\beta\_\{t\}−ϕh\+1k\+δh\+1k\+ξh\+1k\.\\displaystyle\\quad\-\\phi\_\{h\+1\}^\{k\}\+\\delta\_\{h\+1\}^\{k\}\+\\xi\_\{h\+1\}^\{k\}\.\(26\)
Therefore, the recursive bound becomes:

∑k=1Kδhk\\displaystyle\\sum\_\{k=1\}^\{K\}\\delta\_\{h\}^\{k\}≤∑k=1K2​∑i=1tαti​bi\+S​A​H\\displaystyle\\leq\\sum\_\{k=1\}^\{K\}2\\sum\_\{i=1\}^\{t\}\\alpha\_\{t\}^\{i\}b\_\{i\}\+SAH\+\(1\+1H\)∑k=1Kδh\+1k\+∑k=1K\(βnhk\+ξh\+1k\)\.\\displaystyle\\quad\+\\left\(1\+\\frac\{1\}\{H\}\\right\)\\sum\_\{k=1\}^\{K\}\\delta\_\{h\+1\}^\{k\}\+\\sum\_\{k=1\}^\{K\}\(\\beta\_\{n\_\{h\}^\{k\}\}\+\\xi\_\{h\+1\}^\{k\}\)\.\(27\)
This is identical to the bound in Theorem[3](https://arxiv.org/html/2608.12753#Thmtheorem3)with an additional∑k=1K2​∑i=1tαti​bi\\sum\_\{k=1\}^\{K\}2\\sum\_\{i=1\}^\{t\}\\alpha\_\{t\}^\{i\}b\_\{i\}term\. By Lemma[10](https://arxiv.org/html/2608.12753#Thmtheorem10)\(a\),2​∑i=1tαti​bi≤2​c​H3​ι⋅2t=O⁡\(H3​ι/t\)2\\sum\_\{i=1\}^\{t\}\\alpha\_\{t\}^\{i\}b\_\{i\}\\leq 2c\\sqrt\{H^\{3\}\\iota\}\\cdot\\frac\{2\}\{\\sqrt\{t\}\}=O\(\\sqrt\{H^\{3\}\\iota/t\}\), which is of the same order asβt\\beta\_\{t\}\. Following the same recursion and pigeonhole arguments as in Appendix[D](https://arxiv.org/html/2608.12753#A4), we obtain the stated regret bound ofO⁡\(H4​S​A​T​ι\)O\(\\sqrt\{H^\{4\}SAT\\iota\}\)\. ∎

## References

- \[1\]\(2011\)Distributed algorithms for learning and cognitive medium access with logarithmic regret\.IEEE Journal on Selected Areas in Communications29\(4\),pp\. 731–745\.Cited by:[§I](https://arxiv.org/html/2608.12753#S1.p1.1)\.
- \[2\]P\. Auer, N\. Cesa\-Bianchi, and P\. Fischer\(2002\)Finite\-time analysis of the multiarmed bandit problem\.Machine learning47\(2\),pp\. 235–256\.Cited by:[§I](https://arxiv.org/html/2608.12753#S1.p2.1)\.
- \[3\]I\. Bistritz and A\. Leshem\(2018\)Distributed multi\-player bandits\-a game of thrones approach\.Advances in Neural Information Processing Systems31\.Cited by:[§I](https://arxiv.org/html/2608.12753#S1.p2.1),[§VIII](https://arxiv.org/html/2608.12753#S8.SS0.SSS0.Px1.p1.1)\.
- \[4\]W\. Chang, M\. Jafarnia\-Jahromi, and R\. Jain\(2021\)Online learning for cooperative multi\-player multi\-armed bandits\.arXiv preprint arXiv:2109\.03818\.Cited by:[§I](https://arxiv.org/html/2608.12753#S1.p2.1),[§I](https://arxiv.org/html/2608.12753#S1.p4.1),[§II\-D](https://arxiv.org/html/2608.12753#S2.SS4.p1.1),[§III\-A](https://arxiv.org/html/2608.12753#S3.SS1.p1.1),[§VIII](https://arxiv.org/html/2608.12753#S8.SS0.SSS0.Px1.p1.1)\.
- \[5\]W\. Chang and Y\. Lu\(2023\)Optimal cooperative multiplayer learning bandits with noisy rewards and no communication\.arXiv preprint arXiv:2311\.06210\.Cited by:[§I](https://arxiv.org/html/2608.12753#S1.p2.1),[§III\-B](https://arxiv.org/html/2608.12753#S3.SS2.p1.1),[§VIII](https://arxiv.org/html/2608.12753#S8.SS0.SSS0.Px1.p1.1)\.
- \[6\]S\. Hart and A\. Mas\-Colell\(2003\)Uncoupled dynamics do not lead to nash equilibrium\.American Economic Review93\(5\),pp\. 1830–1836\.Cited by:[§VIII](https://arxiv.org/html/2608.12753#S8.SS0.SSS0.Px3.p1.1)\.
- \[7\]C\. Jin, Z\. Allen\-Zhu, S\. Bubeck, and M\. I\. Jordan\(2018\)Is q\-learning provably efficient?\.Advances in neural information processing systems31\.Cited by:[Appendix A](https://arxiv.org/html/2608.12753#A1.p2.1.1.1),[§I](https://arxiv.org/html/2608.12753#S1.SS0.SSS0.Px2.p1.1),[§I](https://arxiv.org/html/2608.12753#S1.p3.1),[§II\-C](https://arxiv.org/html/2608.12753#S2.SS3.p1.2),[§III\-A](https://arxiv.org/html/2608.12753#S3.SS1.p4.1),[§IV\-B](https://arxiv.org/html/2608.12753#S4.SS2.p2.1),[§VI](https://arxiv.org/html/2608.12753#S6.p2.1),[§VII\-A](https://arxiv.org/html/2608.12753#S7.SS1.p1.1),[§VIII](https://arxiv.org/html/2608.12753#S8.SS0.SSS0.Px2.p1.1),[§IX](https://arxiv.org/html/2608.12753#S9.p1.1),[Remark 4](https://arxiv.org/html/2608.12753#Thmtheorem4.p1.1.1),[Abstract](https://arxiv.org/html/2608.12753#abstract1.1)\.
- \[8\]T\. L\. Lai and H\. Robbins\(1985\)Asymptotically efficient adaptive allocation rules\.Advances in applied mathematics6\(1\),pp\. 4–22\.Cited by:[§I](https://arxiv.org/html/2608.12753#S1.p2.1),[§II\-C](https://arxiv.org/html/2608.12753#S2.SS3.p1.2)\.
- \[9\]R\. S\. Sutton and A\. G\. Barto\(2018\)Reinforcement learning: an introduction\.MIT press\.Cited by:[§I](https://arxiv.org/html/2608.12753#S1.p1.1)\.