{"id":"61bc2e35-2cac-400e-be4b-3aaf08a950fe","arxiv_id":"2505.06319","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"DQN and PPO policies, trained with a graph-aware action mask called an action-displacement adjacency matrix, beat random and greedy baselines on multi-step Colonel Blotto games on small graphs.","lead":"The authors apply deep reinforcement learning (DQN and PPO) to a multi-step Colonel Blotto game played on a graph. The learned policies beat random and greedy opponents on small graphs and exploit structural advantages in asymmetric networks.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The state s = d1 - d2 is not a sufficient MDP state, so the claimed MDP formulation of the MCBG is invalid; valid actions and next states depend on the full distributions.","rationale":"The reader's weakest assumption correctly identifies the state-sufficiency issue, and this is the single most load-bearing concern because the paper's central theoretical claim is that the multi-step Colonel Blotto game on graphs can be modeled as an MDP with state s = d1 - d2. That claim fails: the legal actions and the next state depend on the absolute distributions, not just their difference. The paper itself concedes in Section II-B that P(s'|s,a) cannot be explicitly expressed, but the problem is stronger: the transition is not a well-defined function of s at all. This means the Q-values and policies learned by DQN and PPO are heuristic reactive policies for a partially observable process, not solutions to the stated MDP. The action-displacement adjacency matrix construction itself is a useful and likely correct contribution, so the paper can be repaired by using the full state (d1,d2) or by providing evidence that the difference compression is sufficient. The verdict remains CONDITIONAL: the authors should fix the state representation, correct the sign error in Theorem 1's proof, and rerun the experiments with the revised state. I agree with the reader that this is the weakest assumption and that the requested revisions would resolve it.","tokens_in":17415,"tokens_out":10053,"duration_ms":107790,"concrete_test":"Enumerate all states of a small GRAG instance (e.g., G0 with M=3) and compute, for every reachable difference vector s, the set of valid joint actions (a1,a2). If there exist two configurations (d1,d2) and (d1',d2') with d1-d2 = d1'-d2' = s but different legal action products, then s is not a sufficient statistic and the MDP in Section III-A is invalid. This is a purely combinatorial check requiring no training. As a complementary empirical check, train DQN on the same games with observation s and with observation (d1,d2) under identical hyperparameters and report both win rates; if the full-state agent outperforms the difference-state agent, the information loss has practical consequence.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The weakest assumption is the state compression S := {s = d1 - d2} in Section III-A. The valid action set for each player is generated from that player's full distribution via the action-displacement adjacency matrix (Section III-B, Eq. 3 and Theorem 1), and the next state is s' = T(d1,a1) - T(d2,a2). Neither T(d1,·) nor the opponent's legal moves are recoverable from s alone. Concretely, with N=2, M=3, the vector s=(1,-1) is consistent with d1=(2,1), d2=(1,2) and with d1=(1,2), d2=(0,3); in the first case Player 1 has two units on node 0 and one on node 1, in the second one unit on node 0 and two on node 1, so the legal action sets differ. Since the legal moves and the transition depend on the absolute distributions, P(s'|s,a) in Section III-A is not well-defined and the Bellman target max_{a'}Q(s',a') is not a function of s'. Thus the claimed MDP does not exist for this observation function; DQN and PPO are solving a partially observable problem with an insufficient statistic. This undermines the theoretical status of the learned policies and the 'converge to 50%' claim, which is only meaningful for a well-defined symmetric game. The proof of Theorem 1 also contains a sign error (Eq. 4 defines P_{ij}=1 for j=i-1, which gives a right shift, not the left shift claimed by e_kP=e_{k+1}), but the state-sufficiency issue is independent and more fundamental.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a reinforcement learning framework for a multi-step Colonel Blotto game on graphs (GRAG). The authors formulate the game as an MDP with state s = d1 - d2 (the difference of the two players' resource distributions), introduce an action-displacement adjacency matrix that generates the set of valid graph-constrained actions at each step, and train DQN and PPO agents against random, greedy, and self-play opponents on small symmetric and asymmetric graphs. They report win rates on five graphs and conclude that both algorithms outperform baselines, exploit structural asymmetries, and converge to a balanced 50% win rate in self-play.","tokens_in":17707,"tokens_out":11119,"duration_ms":119100,"significance":"If the MDP formulation were sound, the paper would offer a useful engineering contribution: a concrete action-masking mechanism for graph-constrained Blotto games and an empirical comparison of two standard RL algorithms in that setting. The action-displacement adjacency matrix construction in Section III-B is concrete, and the linear-algebraic characterization in Theorems 1 and 2 is a helpful formalization. A strength is that the reported win rates are obtained against external baselines (random and greedy opponents) rather than fitted targets, so there is no circular fitting of the headline numbers. However, the central state-compression claim is not justified: the state s = d1 - d2 is not a sufficient statistic for the players' decision problem, which undermines the claim that the game is modeled as an MDP and the theoretical status of the learned policies. The experiments are on very small graphs and are reported without error bars or seed information, so the broad generalization claims should be tempered.","major_comments":[{"comment":"The state s = d1 - d2 is not a sufficient statistic for the MDP. The valid action set in Eq. (3) is generated from the player's own full distribution d_t, and the next state s' = T(d1,a1) - T(d2,a2) depends on the absolute distributions through the resource locations. Two different underlying states can give the same s but different legal moves and different transitions. For example, with N=2, M=3 and an adjacency matrix H = [[1,1],[1,0]], s=(1,-1) is consistent with d1=(2,1), d2=(1,2) and also with d1=(1,2), d2=(0,3); in the first case Player 1 has two resources on node 0 and one on node 1, while in the second case the counts are reversed, so the valid action sets differ. Consequently P(s'|s,a) is not well-defined as a function of s alone, and the Bellman target max_{a'}Q(s',a') is not a function of s'. This invalidates the claim in Section II-A that the game satisfies the Markov property for the chosen state representation. In the implementation, the agent additionally conditions on its own distribution through the action mask, so the learned object is not actually a policy π(a|s) as described. To make the MDP formulation valid, the state must include the full distributions (d1,d2) or a sufficient statistic; otherwise the learning problem is a POMDP with an insufficient observation and the convergence claims do not follow.","section":"Section III-A, definition of S; Section III-B, Eq. (3)"},{"comment":"The permutation matrix P defined by P_{ij}=1 iff j ≡ i-1 (mod N) satisfies e_k P = e_{k-1}, not e_{k+1} as claimed in the text; it implements a right shift, not a left shift. The same sign error propagates into Theorem 2, where e_{n_j} P^{a_j} would move a resource to node n_j - a_j rather than the intended n_j + a_j. The intended left-shift construction requires P_{ij}=1 iff j ≡ i+1 (mod N), or equivalently the use of P^T. The final formulas in Eq. (7) and Eq. (8) are correct under the intended convention, so the theorem statements are likely correct, but the proofs as written are internally inconsistent and need correction.","section":"Section III-B, Theorem 1 proof, Eq. (4)-(6); Theorem 2, Eq. (8)"},{"comment":"The abstract claims that both DQN and PPO 'consistently outperform baseline strategies,' but several PPO test results are at or below chance against a random policy. For example, Table II (C3, Greedy π1, Random column) reports 43%, and Table IV (C4, Greedy π1, Random column) reports 43%; the RL-vs-RL rows in Tables II and IV also contain values such as 37%, 44%, and 40%. These entries contradict the unqualified 'consistently' claim. The performance statement should be qualified to distinguish training performance from generalization performance and to acknowledge that PPO often fails to beat a random opponent after training against a fixed greedy policy.","section":"Abstract and Tables I-IV"}],"minor_comments":[{"comment":"The acronym 'CRAG' appears in the first paragraph; it should be 'GRAG'.","section":"Section III-A"},{"comment":"The definition of J'_1 for virtual resources is unclear. Virtual resources should be constrained to action 0, so the corresponding rows should have a single 1 in the first column, but the notation '1T_{M-M1,0}' is ambiguous and appears to suggest an all-ones block. Please clarify the construction.","section":"Section III-C, Eq. (9)"},{"comment":"The caption refers to graphs G1 and G3, while the text describes the episodes as being on G2 and G4. These references should be made consistent.","section":"Figure 7 caption"},{"comment":"The text states that PPO achieves a 71% win rate on G3, but Table V reports 72%. The numbers should be reconciled.","section":"Section IV-E and Table V"},{"comment":"The header 'Train/Test' and the notation '100%∼50%' are not defined. Please clarify which entries are training win rates and which are test win rates against random and greedy opponents, and define the '∼' notation.","section":"Tables I-IV"},{"comment":"No number of random seeds, standard deviations, or hyperparameter settings are reported for the win rates in Tables I-V. Adding this information is necessary to assess the reliability of the empirical claims.","section":"Section IV"}],"recommendation":"major_revision","confidential_remarks":"The state-sufficiency problem in Section III-A is fundamental: the MDP claim is the basis for the entire learning pipeline. If the authors can revise the formulation to use a sufficient state (e.g., the joint distribution) or explicitly reframe the method as a POMDP heuristic, the paper may become viable after re-running the experiments. The sign error in the P matrix in Theorem 1 and Theorem 2 also suggests that the proofs need careful independent checking. The novelty claim of being the 'first RL framework' for GRAG should be verified against the related work cited in [17] and other recent literature."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the action-displacement adjacency matrix is a nice piece of engineering, and the asymmetric-graph experiments show RL can exploit topology. But the paper's central formal claim — that the game is an MDP with state s = d1 − d2 — does not hold. Legal moves for each player depend on their own distribution d, and s does not determine d. So the transition kernel P(s'|s,a) is not well-defined, and the Bellman target max_{a'} Q(s',a') is not a function of s' alone. The paper even uses d1 and d2 to generate action masks in Figure 2, so the actual observation is richer than s. This is not a minor notational slip; it invalidates the \"we formulate MCBG as an MDP\" claim in Section III-A. The learned policies are heuristics for a partially observable problem, which is fine if presented that way, but the paper oversells the theory.\n\nWhat is genuinely new: applying DQN/PPO to the multi-step Blotto game on graphs, with a graph-derived action mask. The J-matrix construction in Section III-B is a compact way to encode adjacency and resource counts into per-resource valid actions; Theorems 1 and 2 are simple linear algebra and the intended statements are correct. Theorem 1's proof, however, has a sign error: Eq. (4) defines P_{ij}=1 when j ≡ i−1 (mod N), which is a right shift, not the left shift claimed by e_kP = e_{k+1}. The statement is still true if you flip the convention, but as written it is internally inconsistent. Eq. (10) also looks misindexed in the unequal-resource case.\n\nEmpirically, the scope is small — 4–5 nodes, 7–8 resources — and the tables lack error bars, seeds, and hyperparameters. The greedy baseline is built from a pretrained DQN, which is unusual but not circular. The 50% self-play claim is plausible but not surprising: in a symmetric game with identical state representations, near-50% win rates are what you expect. The experiments on asymmetric graphs (G2–G4) are the most interesting: the RL agent learns to hold an isolated node or exploit forced moves. Those results are worth reporting as heuristics.\n\nBottom line: this is a solid workshop/short-paper candidate once the state-sufficiency issue is addressed head-on. The authors can either expand the state to (d1, d2) or (d1, s), which fixes the math but changes their dimensionality argument, or explicitly reframe as a POMDP and drop claims of optimality. They also need to release code and seeds, fix the notational errors, and temper the 'MDP' language. The action-mask construction is citable; the MDP claim is not. I would send it to peer review, but the referee should insist on these revisions.","headline":"The action-mask construction and asymmetric-graph experiments earn a look, but the MDP formulation is broken: the state s=d1-d2 discards the information needed to define legal actions, so the theoretical claim does not hold as written.","tokens_in":18329,"tokens_out":4889,"would_cite":false,"duration_ms":50983,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Standard deep reinforcement learning, with graph-constrained action masking, learns winning strategies in multi-step Colonel Blotto games on graphs.","keywords":["game-theoretic resource allocation","multi-step Colonel Blotto game","Markov decision process","action-displacement adjacency matrix","deep Q-network","proximal policy optimization","asymmetric graphs","graph-constrained action masking"],"falsifier":"Compare two positions that give the same state $s$ but different distributions: on a two-node path with $M=3$, $d_1=(3,0), d_2=(2,1)$ and $d_1'=(2,1), d_2'=(1,2)$ both give $s=(1,-1)$, yet the first player's legal moves from $d_1$ differ from those from $d_1'$. If a DQN trained on $s$ alone assigns a different Q-value to the same $(s,a)$ pair depending on which hidden distribution produced it, or if replacing $s$ by the full pair $(d_1,d_2)$ changes the reported win rates, the MDP formulation's sufficiency claim fails.","tokens_in":17127,"feed_emoji":"🎲","tokens_out":8200,"duration_ms":79007,"temperature":0.7,"pith_summary":"The paper tries to establish that the multi-step Colonel Blotto game on a graph, where two players move indistinguishable resource units along edges over multiple turns to control a majority of nodes, can be treated as a Markov decision process and solved by off-the-shelf deep reinforcement learning. The authors introduce the action-displacement adjacency matrix, which derives the set of legal moves from the current resource distribution and the graph's adjacency matrix, so a fixed neural-network output layer can be masked to respect graph constraints. Experiments on five small graphs with DQN and PPO show win rates above random and greedy baselines, convergence to a balanced 50% win rate when the two sides use the same learned policy, and exploitation of asymmetric structures, including by the structurally disadvantaged player.","feed_headline":"Deep RL wins graph-constrained Colonel Blotto games","feed_subtitle":"A difference-state MDP and an action-displacement matrix let standard RL agents exploit graph asymmetries.","key_machinery":"The action-displacement adjacency matrix $J$ is the load-bearing object. For a distribution $d$ with $M$ units, the paper assigns each resource a one-hot row for its node, forms $J = \\hat{d} H'$, where $H'$ is the adjacency matrix $H$ with row $i$ cyclically left-shifted by $i$ positions, and reads $J_{j,k}=1$ as \"resource $j$ may move $k$ steps clockwise.\" This matrix converts the graph constraint into a mask over a fixed $M$-by-$N$ action table, so DQN's Q-values and PPO's policy logits can be filtered to legal actions; Theorem 1 proves the mask is exactly the set of legal moves, and Theorem 2 gives the deterministic update $d' = \\sum_j \\hat{d}_{j,:} P^{a_j}$ for the next distribution. Together they turn a moving-boundary action space into a fixed-size, distribution-dependent mask.","core_discovery":"On the paper's own terms, the central discovery is that an MDP formulation with state $s = d_1 - d_2$, reward $+1/0/-1$ by node majority, and the action-displacement matrix $J$ (built by cyclically shifting each row of the graph adjacency matrix by the node index and lifting the resource distribution to one-hot rows) makes the graph-constrained multi-step Blotto game learnable by DQN and PPO. Theorem 1 states that for a resource at node $n_j$, a displacement $k$ is legal exactly when $J_{j,k}=1$, i.e. $H_{n_j,(n_j+k) \\bmod N}=1$. Empirically the trained policies beat random and greedy opponents, approach 50-50 play against another learned policy, and on asymmetric graphs exploit permanent-control and forced-movement structures enough to raise win rates far above random-policy baselines (DQN and PPO reach 100% on $G_2$, and the disadvantaged side's win rate improves from 20% to 25-33%).","pith_inferences":["The state $s = d_1 - d_2$ may be information-deficient: two positions with the same difference can have different legal action sets, so an $s$-only MDP has transitions that are not well-defined; a testable fix is to include each player's own distribution (or a factored encoding) and check whether win rates against adaptive opponents improve.","Because $J$ is built from cyclic shifts of the adjacency matrix, the masking operation is differentiable and batched, so the same construction should extend to larger graphs and to graph neural network policies, not just MLP DQN and PPO.","The asymmetric-graph results suggest learned policies discover structural 'fortresses' (e.g., holding an isolated node with one unit); formalizing this as a graph-theoretic condition on winning regions could predict when RL will succeed before running experiments.","Self-play convergence near 50% on symmetric graphs is consistent with either a mixed equilibrium or policy cycling; distinguishing the two by tracking the policies' entropy or by evaluating the final policy against a best-response oracle would clarify what the agents actually learned."],"forward_implications":["On the five tested graphs, both DQN and PPO beat random and greedy opponents, so graph-constrained Blotto does not require bespoke game solvers; standard RL with legal-action masking suffices for the studied sizes.","When both players are trained RL agents, win rates settle near 50%, meaning mutual learning reaches a balanced outcome under symmetric initialization on $G_0$ and $G_1$.","Asymmetric graph structure is exploitable: DQN and PPO reach 100% win rate on $G_2$ where one node is unreachable, and the disadvantaged player still improves from 20% to 25-33% win rate by learning.","Randomness in initial distributions trades off against generalization: agents trained on fixed deterministic initializations beat the trained opponent 100% but drop to about 50% against a random opponent, while random initialization improves robustness.","With unequal resources (7 vs 8), RL raises the weaker player's win rate from 17% under random play to 23-24%, showing the learned policy partially compensates for numeric disadvantage."],"supporting_citations":[{"why":"Supplies the original Colonel Blotto game that the paper extends to graphs and multiple steps.","marker":"[14]"},{"why":"Extends Blotto to a dynamic defender-attacker setting and grounds the on-graph multi-step formulation.","marker":"[16]"},{"why":"Introduces the graph-constrained robot allocation variant whose structure the multi-step Blotto game inherits.","marker":"[17]"},{"why":"Demonstrates RL agents in a conventional three-node Blotto game and provides the closest RL baseline the paper builds on.","marker":"[28]"},{"why":"Provides the deep Q-network algorithm used as the value-based learner.","marker":"[29]"},{"why":"Provides the proximal policy optimization algorithm used as the policy-gradient learner.","marker":"[30]"},{"why":"Supplies the multi-agent environment interface used to implement the game.","marker":"[32]"},{"why":"Supplies the deep RL training library used for DQN and PPO experiments.","marker":"[33]"}],"fun_headline_variants":["DQN and PPO master graph-constrained Blotto games","Action-displacement matrix unlocks RL for graph Blotto","RL learns to exploit graph structure in Colonel Blotto","Deep RL wins asymmetric graph Blotto with smart MDP","Graph Blotto: Standard RL beats baselines via MDP"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the difference state $s = d_1 - d_2$ contains enough information to choose an optimal action, although the legal moves at each step depend on each player's full distribution and two different distributions can yield the same difference.","fun_headline_variants_meta":{"raw":{"variants":["DQN and PPO master graph-constrained Blotto games","Action-displacement matrix unlocks RL for graph Blotto","RL learns to exploit graph structure in Colonel Blotto","Deep RL wins asymmetric graph Blotto with smart MDP","Graph Blotto: Standard RL beats baselines via MDP"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000199,"raw_usage":{"total_tokens":1377,"prompt_tokens":954,"completion_tokens":423,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":570,"completion_tokens_details":{"reasoning_tokens":342}},"tokens_in":570,"tokens_out":423,"duration_ms":4620,"temperature":1.0,"reasoning_tokens":342,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T23:01:16.945138+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compare two positions that give the same state $s$ but different distributions: on a two-node path with $M=3$, $d_1=(3,0), d_2=(2,1)$ and $d_1'=(2,1), d_2'=(1,2)$ both give $s=(1,-1)$, yet the first player's legal moves from $d_1$ differ from those from $d_1'$. If a DQN trained on $s$ alone assigns a different Q-value to the same $(s,a)$ pair depending on which hidden distribution produced it, or if replacing $s$ by the full pair $(d_1,d_2)$ changes the reported win rates, the MDP formulation's sufficiency claim fails.","supporting_citations":[{"cited_title":"La th ´eorie du jeu et les ´equations int ´egralesa noyau sym´etrique,","cited_arxiv_id":null,"evidence_quote":"Supplies the original Colonel Blotto game that the paper extends to graphs and multiple steps."},{"cited_title":"Dynamic defender- attacker blotto game,","cited_arxiv_id":null,"evidence_quote":"Extends Blotto to a dynamic defender-attacker setting and grounds the on-graph multi-step formulation."},{"cited_title":"Double oracle algorithm for game-theoretic robot allocation on graphs,","cited_arxiv_id":null,"evidence_quote":"Introduces the graph-constrained robot allocation variant whose structure the multi-step Blotto game inherits."},{"cited_title":"Tianshou: A highly modularized deep reinforcement learning library,","cited_arxiv_id":null,"evidence_quote":"Supplies the deep RL training library used for DQN and PPO experiments."}],"review_version":1}