{"id":"ba6dfcaf-139a-4e94-9e76-af8a1ab8a46a","arxiv_id":"2608.12753","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"Decentralized players using pre-agreed deterministic tie-breaking can match centralized Q-learning regret when either actions or rewards are shared, but the fully asymmetric setting rests on an exploration argument that fails in stochastic MDPs.","lead":"This paper studies several multiplayer reinforcement learning settings where players cannot see each other's actions or rewards. It claims that in two settings, decentralized players can learn nearly as fast as one central player, and that the fully asymmetric setting needs a slower two-phase strategy.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 7's uniform coverage premise fails: least-visited-action exploration cannot guarantee K'/(S A_joint) visits to states with low reachability.","rationale":"The reader's rejection is supported. The coverage failure is load-bearing because Theorem 7 is the paper's main advertised contribution for Problem C, and its proof is only a sketch that explicitly relies on the false premise. Even the M=1 special case of the same algorithm would fail on a simple MDP with a rarely reached state, which shows the defect is not primarily about multi-player coordination but about the fundamental need to actively explore to reach states in an MDP. The Problem A reduction is likely sound, and Problem B's proof is at least plausible modulo the missing lower-confidence details, but the central claim of the paper includes Theorem 7. I therefore do not see a basis to move the verdict away from REJECT; the concrete test above would settle the coverage premise empirically. The coordination issue raised in Remark 9 is a second independent obstacle, but the coverage gap alone is sufficient.","tokens_in":12892,"tokens_out":7063,"duration_ms":75454,"concrete_test":"Simulate mEXC on an M=1, H=2, S=3 tabular MDP with layer-1 state s0; both actions at s0 transition to state A with probability 0.98 and to states B and C with probability 0.01 each. Set rewards so the optimal action at C differs from the suboptimal one. Run K=10^6 episodes with K' = ceil((S A_joint)^(1/3) K^(2/3)) and average the number of visits to (C,a) at step 2 over 100 seeds. If this count scales as ~0.01 K'/2 rather than ~K'/(S A_joint)=K'/6, and if the post-exploration value error at C does not shrink at the rate required by Theorem 7, the uniform-coverage premise is refuted.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 7 (Section IV.A) claims that after K' episodes of 'round-robin exploration,' every state-action pair has been visited at least floor(K'/(S A_joint)) times in expectation, and that this makes post-exploration Q-tables uniformly close to Q*. Algorithm 3 does not perform round-robin over state-action pairs: line 5 picks the least-visited action in the current state. The state sequence is generated by the unknown transition kernel, so a state x at layer h that is reachable only with probability p << 1/S will be reached at most about p K' times no matter how actions are balanced inside x. The visit count for (x,a) is then O(p K'/|A|), not Omega(K'/(S A_joint)). The resulting estimation error for Q*_h(x,a) is inflated by a factor ~1/sqrt(p), the stated value-error bound O(sqrt(H^4 S A_joint iota/K')) does not hold, and the balance K'=(S A_joint)^(1/3) K^(2/3) no longer controls commit-phase regret. Both mEXC and mEXC-Bellman inherit this gap; the argument would fail even for M=1, since uniform exploration over visited states cannot guarantee coverage of rarely reached states.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies decentralized multi-player reinforcement learning in episodic tabular MDPs under three information asymmetry models. For Problem A (unobserved actions, common rewards) it proposes mQ-learning and claims O~(sqrt(H^4 S A_joint T)) regret by reducing the protocol to centralized joint-action Q-learning with deterministic lexicographic tie-breaking. For Problem B (observed actions, independent rewards) it proposes mQ-learning-intervals, which maintains upper and lower confidence tables for action elimination, and claims the same regret rate. For Problem C (unobserved actions, independent rewards) it proposes mEXC and mEXC-Bellman, two-phase explore-then-commit algorithms, and claims O~(H (S A_joint)^{1/3} T^{2/3}) regret. The appendix contains lemmas on learning-rate weights, an optimism lemma, an interval-width lemma, and regret recursions that closely follow Jin et al. [1].","tokens_in":13206,"tokens_out":7348,"duration_ms":75566,"significance":"If the theorems were valid, the paper would establish that information asymmetry can be overcome at no cost beyond the joint-action space for Problems A and B, and would give the first sublinear regret bound for the fully asymmetric Problem C. The reduction for Problem A is a clean and sound observation, and the learning-rate lemmas are stated carefully. However, the central new contributions rest on two unsupported or false premises: the validity of the lower confidence table in Problem B, and the uniform coverage assumption in Problem C's exploration phase. Because these premises are load-bearing for the main theorems, the manuscript in its current form does not support its claims.","major_comments":[{"comment":"The claim that after K' episodes of least-visited exploration every (x,a) has been visited at least floor(K'/(S A_joint)) times in expectation is false. Algorithm 3 line 5 selects the least-visited action only within the current state; the sequence of states is governed by the unknown transition kernel. A state that is reachable with probability p << 1/S will be reached about p K' times, so a state-action pair involving it receives O(p K'/|A_i|) visits rather than Omega(K'/(S A_joint)). Consequently the stated post-exploration error bound O(sqrt(H^4 S A_joint iota/K')) and the balancing K' = (S A_joint)^{1/3} K^{2/3} do not follow. The same false premise invalidates the mEXC-Bellman variant, whose proof invokes a model-based concentration bound that also requires uniform coverage; the argument fails already for M=1.","section":"Section IV.A, Theorem 7 proof sketch"},{"comment":"No proof is given that the lower confidence table satisfies Q^low <= Q*. Lemma 12 proves optimism only for updates with the +b_t bonus. The lower-table update in Algorithm 2 line 12 uses -b_t but plugs in V_{h+1}, which is computed from the optimistic upper Q-values, so the future-value term can exceed V*_{h+1}; the backward induction that would establish Q^low <= Q* is therefore unavailable. The statement in Section III.B that 'Optimism ... guarantees each interval covers Q*' is unsupported. Since the action-elimination rule at lines 6-8 compares upper and lower tables, a false lower bound can remove the optimal action, which breaks the proof of Theorem 5.","section":"Section III.B, Lemma 12 and Algorithm 2"},{"comment":"The commit phase requires that, on the high-probability event, all players' Q-tables agree on the same lexicographic-smallest greedy joint action. This does not follow from uniform closeness to Q*. If two joint actions have values within the estimation error, independent reward samples can produce opposite orderings in different players' tables, so one player may choose a and another may choose b; because actions are unobserved in Problem C, the executed joint action is then not the intended one, and the per-episode suboptimality bound in the proof of Theorem 7 no longer applies.","section":"Section IV.A, Remark 9"},{"comment":"The proof of Theorem 7 for mEXC-Bellman says the argument is 'identical, using the standard model-based plug-in error bound ||hat P - P||_1 <= O(sqrt(S iota/N))'. This is not a proof: it does not specify how the empirical transition estimate is formed from the least-visited exploration data, nor how a per-state-action-pair concentration bound can be obtained without uniform coverage. A complete argument is needed, and in light of the first major comment no such argument can go through with the current exploration rule.","section":"Appendix C, mEXC-Bellman proof"}],"minor_comments":[{"comment":"The definition of V_h(x_h) uses 'Q^k_h(i,x_h,a')' without specifying whether Q^k_h is the upper or lower table; the two choices yield different updates, and the proof does not disambiguate them.","section":"Algorithm 2, line 13"},{"comment":"Lemma 12 is stated with iota = log(SAT/p), but Theorem 5 requires a union bound over M players; the M factor should appear inside the logarithm in the lemma statement as well, not only in the theorem.","section":"Lemma 12"},{"comment":"The sentence about an Omega(log T) lower bound 'for the multi-player problem as well' is not used anywhere in the regret analysis and distracts from the episodic-MDP lower bound quoted from [1]; it could be removed or clarified.","section":"Section II.C"},{"comment":"The notation A_joint = product_i |A_i| is used together with the shorthand A = A_joint; please make the notation consistent throughout.","section":"Abstract and Section II.A"},{"comment":"The numerical example states that per-episode suboptimality falls below 0.1 once K is roughly 10^5, but the constants in the theorems are not specified; this should be labeled as an illustrative order-of-magnitude estimate rather than a derived guarantee.","section":"Section VII.C"}],"recommendation":"reject","confidential_remarks":"The Problem A result is essentially a repackaging of the centralized Q-learning guarantee from Jin et al. [1] with a deterministic tie-breaking observation, as the paper itself concedes in Section VII.A. The actual novelty lies in Problems B and C, and in both cases the central proof steps are missing or false: the lower confidence bound for Problem B is not established, and the uniform coverage premise for Problem C is false in stochastic MDPs. These are not presentation issues; they affect the validity of the main theorems. A revision would require substantial algorithmic and proof changes, not just additional exposition."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nShort take: Problem A is a clean reduction and likely sound; Problem B is plausible but missing its lower-confidence proof; Problem C's main theorem is not supported because least-visited-action exploration cannot guarantee uniform coverage in a stochastic MDP. The paper overclaims the centerpiece result.\n\nWhat is actually new: the episodic MDP formulation of the three information-asymmetry models from [7], and the observation that deterministic tie-breaking gives implicit coordination for Problem A. That part works. The paper is honest that A_joint = prod |A_i| is exponential in M, so the bounds are meaningful only for small M. The reduction of Algorithm 1 to centralized joint-action Q-learning is clear and correct.\n\nSoft spots, in proportion. Theorem 7's proof sketch asserts that after K' episodes of 'round-robin exploration,' every (x,a) has been visited at least K'/(S A_joint) times in expectation. Algorithm 3 does not implement round-robin; it plays the least-visited action in the current state. How often a state is reached is governed by P_h, so a state reachable with probability p is visited about pK' times. The estimation error is inflated by ~1/sqrt(p), and the stated bound O~(H (S A_joint)^{1/3} T^{2/3}) does not follow. This invalidates the claim for Problem C as stated, and it fails even for M=1. The appended Remark 9 concedes that commit-phase coordination relies on concentrated Q-tables, but no argument shows players agree on the same greedy action when near-tied estimates put actions in opposite orders. Problem B has a separate gap: the proof of Theorem 5 never establishes that the lower confidence table is a valid lower bound on Q*. Lemma 12 provides optimism only for the upper table, and the elimination step depends on the missing lower bound. The appendix contains full proofs for Theorems 3 and 5 but not for Theorem 7, the advertised main contribution.\n\nNet: I would not accept this paper as is. The A result is correct but incremental. A revision that fixes C (or removes it), supplies the missing lower-bound argument for B, and provides complete proofs could change my view. I'd send it to a serious referee because the problem setting is worthwhile and the flaws are instructive, but I'd expect rejection unless C is fixed. I won't cite it in my next twelve months.\n\nBest","headline":"Problem A is a clean reduction, but the paper's centerpiece explore-then-commit bound for full asymmetry rests on a false uniform-coverage premise, and the proof is missing; the paper needs major revision.","tokens_in":13640,"tokens_out":6754,"would_cite":false,"duration_ms":70236,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Decentralized players who cannot communicate during learning can still match the centralized Q-learning regret rate in episodic MDPs, provided they pre-agree on deterministic tie-breaking.","keywords":["multi-player reinforcement learning","episodic MDP","Q-learning","regret bounds","information asymmetry","decentralized learning","explore-then-commit","implicit coordination"],"falsifier":"Run mEXC on a two-state MDP in which state 2 is reached with probability $10^{-3}$; after the $K'$ exploration episodes, count visits to each state-2 action pair. If any pair's visit count falls well below $K'/(S A_{\\text{joint}})$, the proof's coverage premise is violated and the stated regret bound need not hold; the same test can check whether near-tied joint actions are chosen consistently during the commit phase.","tokens_in":12696,"feed_emoji":"🤝","tokens_out":8664,"duration_ms":85290,"temperature":0.7,"pith_summary":"This paper asks whether cooperative multi-player reinforcement learning in episodic tabular MDPs (finite-horizon Markov decision processes with finitely many states and actions) loses efficiency when players cannot observe each other's actions or rewards while learning. It answers no for two of the three information-asymmetry models: with either common rewards or observed actions, a pre-agreed deterministic protocol achieves $\\tilde{O}(\\sqrt{H^4 S A_{\\text{joint}} T})$ regret, which matches the rate a single centralized agent would obtain on the joint-action MDP, up to logarithmic factors. For the fully asymmetric case, where players see neither the others' actions nor their rewards, the paper gives explore-then-commit algorithms with regret $\\tilde{O}(H (S A_{\\text{joint}})^{1/3} T^{2/3})$. The bounds are most meaningful when the joint action space $A_{\\text{joint}} = \\prod_{i=1}^{M} |\\mathcal{A}_i|$ is small, because it grows exponentially in the number of players; the contribution is that information asymmetry adds no extra factor beyond the centralized tabular rate.","feed_headline":"Decentralized Q-learning matches centralized regret without any chat","feed_subtitle":"Deterministic tie-breaking keeps players coordinated; full asymmetry costs a slower $T^{2/3}$ regret rate.","key_machinery":"Lexicographic ordering of joint actions (Definition 2): compare two $M$-tuples as multi-digit numbers and pick the smaller one. This is the load-bearing tie-break because it converts a set of tied Q-values into a unique joint action, so all players, running the same deterministic algorithm on the same shared statistics, arrive at the same choice without communication. In Problems A and B it directly selects the greedy joint action; in Problem C it defines both the least-visited exploration rule and the commit-phase greedy selection. The other workhorse is the weighted-learning-rate recursion (Lemma 11) with the identity $\\sum_{t \\ge i} \\alpha_t^i = 1 + 1/H$ (Lemma 10(c)), which lets the regret analysis charge a future-step value error back to all earlier episodes that visited the same state-action pair.","core_discovery":"The central claim is that pre-agreed deterministic rules can replace communication: the players need not observe each other's choices or rewards, because a shared lexicographic ordering plus identical update rules makes their private Q-tables select the same joint action at every step. In Problem A, identical rewards and transitions make all Q-tables exactly equal, so each player's play is identical to what a single centralized Q-learning agent would do on the joint MDP. In Problem B, observable actions allow a player's unilateral deviation to be read by everyone else as a one-bit signal, and upper/lower confidence intervals keep the players' estimates close enough to eliminate the same suboptimal actions. In Problem C, both signals are absent, so the paper uses a two-phase explore-then-commit schedule where shared visit counts coordinate exploration and lexicographic tie-breaking on learned Q-values coordinates the commit phase, giving the slower $T^{2/3}$ rate. The paper's overall thesis is that asymmetry is not free in absolute terms, because the joint action space is exponential in the number of players, but it adds no multiplicative regret penalty relative to a centralized learner on the same joint-action benchmark.","pith_inferences":["The uniform-coverage premise of the Problem C bound is questionable: in a stochastic MDP the transition kernel controls how often states are visited, so a least-visited joint-action exploration schedule does not guarantee roughly $K'/(S A_{\\text{joint}})$ visits to every state-action pair. A direct check is to count visits in a two-state chain with a rarely reached state and compare against the cl","The same deterministic tie-breaking idea should carry over to settings with limited or one-way communication, where a short pre-agreement plays the role of the missing coordination channel; the paper implicitly trades a priori coordination against online information.","The regret depends on $A_{\\text{joint}}$ only, so extending the framework to factored MDPs or linear function approximation is a natural next test; the tie-breaking mechanism itself does not rely on the joint-action structure except through the size of the action space."],"forward_implications":["For Problems A and B, decentralized learning with zero communication matches the regret of a centralized learner on the joint-action MDP, up to log factors.","Either shared rewards or observable actions supplies enough of a coordination channel to keep the $\\sqrt{T}$ regret rate; only when both are missing does the rate drop to $T^{2/3}$.","The bounds show that the multi-player curse is the exponential joint action space $A_{\\text{joint}}$, not the information asymmetry: if $A_{\\text{joint}}$ is held fixed, splitting one player's actions among more players does not change the regret.","For the fully asymmetric case the paper leaves open whether $\\sqrt{T}$ regret is achievable; its $T^{2/3}$ rate is the standard penalty of explore-then-commit when the suboptimality gap is unknown."],"supporting_citations":[{"why":"Supplies the single-agent optimistic Q-learning algorithm and bonus/learning-rate machinery that the paper extends to the multi-player setting; its regret rate is the centralized benchmark.","marker":"[1]"},{"why":"Introduces the information-asymmetry framework and the lexicographic ordering used for implicit coordination without communication.","marker":"[7]"},{"why":"Provides the interval-based action-elimination method for cooperative bandits with noisy rewards and no communication that underpins Problem B's algorithm.","marker":"[8]"}],"fun_headline_variants":["Zero-chat Q-learning: same regret as single agent","Multi-agent RL coordinates via tie-breaks, not talk","Information asymmetry costs nothing in Q-learning (up to logs)","For hidden actions, explore-then-commit gives slower regret","Deterministic tie-breaking replaces chat in multi-agent Q-learning"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"For the fully asymmetric Problem C, the proof assumes that the exploration phase visits every state-action pair about $K'/(S A_{\\text{joint}})$ times in expectation, but in a stochastic MDP the transition kernel governs how often states are reached, so rarely reachable states get far fewer visits and the uniform coverage floor does not follow.","fun_headline_variants_meta":{"raw":{"variants":["Zero-chat Q-learning: same regret as single agent","Multi-agent RL coordinates via tie-breaks, not talk","Information asymmetry costs nothing in Q-learning (up to logs)","For hidden actions, explore-then-commit gives slower regret","Deterministic tie-breaking replaces chat in multi-agent Q-learning"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001185,"raw_usage":{"total_tokens":4944,"prompt_tokens":1049,"completion_tokens":3895,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":665,"completion_tokens_details":{"reasoning_tokens":3812}},"tokens_in":665,"tokens_out":3895,"duration_ms":27836,"temperature":1.0,"reasoning_tokens":3812,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T00:00:30.353917+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run mEXC on a two-state MDP in which state 2 is reached with probability $10^{-3}$; after the $K'$ exploration episodes, count visits to each state-2 action pair. If any pair's visit count falls well below $K'/(S A_{\\text{joint}})$, the proof's coverage premise is violated and the stated regret bound need not hold; the same test can check whether near-tied joint actions are chosen consistently during the commit phase.","supporting_citations":[],"review_version":1}