{"id":"dbe4ba30-64c0-4f5f-83b6-44e43d4293e1","arxiv_id":"2507.22538","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"madupite is a distributed, customizable MDP solver based on inexact policy iteration that scales to millions of states on HPC clusters.","lead":"This paper describes the technical design and performance of madupite, a solver for large-scale discounted Markov decision processes (MDPs). It claims that madupite is the only solver that can compute exact solutions for MDPs with millions of states by distributing storage and computation across HPC clusters.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The 2-norm inner-loop stopping criterion in §III-B.3 is mischaracterized as 'more stringent' and voids the cited iPI convergence guarantees; the central exactness claim depends on it.","rationale":"The reader's weakest_assumption pinpoints exactly the condition that must hold for the solver to be both exact and efficient: the inner loop must solve policy-evaluation subproblems to the accuracy prescribed by the iPI theory. The paper asserts the opposite of the mathematical truth about norm ordering, so the most load-bearing assumption is indeed insecure. I agree with the reader's conditional assessment. I considered alternative concerns: the 'only solver' and 'unique customization' claims rest on a narrow comparison with pymdptoolbox and mdpsolver, and the memory figure for n=1000 appears inconsistent, but these affect marketing strength more than the core algorithmic validity. The 2-norm stopping issue is more fundamental because it undermines the theoretical justification for behaviour in the near-undiscounted, large-scale regime highlighted in the abstract. The paper's strengths—open-source code, reproducible benchmarks, and detailed engineering description—are real and mitigate the concern, but they do not replace a proof that the modified criterion preserves the convergence guarantees. The proposed test would settle whether the concern is merely theoretical or manifests in practice: if the infinity-norm variant produces the same results, the practical claim survives but the paper still needs correcting; if it produces different results, the central claim fails as stated. Therefore the reader's CONDITIONAL verdict should stand.","tokens_in":16757,"tokens_out":5136,"duration_ms":64881,"concrete_test":"Re-run the Section IV-A.2 benchmark MDPs (or the inverted pendulum case) with madupite's inner KSP convergence test set to the infinity norm (e.g., -ksp_norm_type INFINITY) while keeping α and tol identical, and compare outer iteration counts, runtime, and final Bellman residual with the default 2-norm variant. Also instrument the inner loop to record, at termination under the 2-norm criterion, the ratio ||r_final||_∞ / (α ||r_0||_∞). If this ratio exceeds 1 in any run, or if the infinity-norm runs yield materially different policies or iteration counts, the modified criterion is not 'more stringent' and the cited convergence guarantees do not apply.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Section III-B.3 the paper replaces the infinity-norm inner-loop stopping condition of Algorithm 1 with a 2-norm criterion and describes it as 'more stringent'. This is mathematically backwards: for any vector, ||x||_∞ ≤ ||x||_2, so requiring ||r_i||_2 ≤ α||r_0||_2 is weaker than requiring ||r_i||_∞ ≤ α||r_0||_∞ — the infinity-norm bound can be violated by up to a factor of sqrt(n) at the same 2-norm threshold. The convergence and suboptimality guarantees for inexact policy iteration cited from [18] are established for the infinity-norm relative residual; the paper gives no proof that they survive this change. The outer loop still checks ||r(V_k)||_∞ ≤ tol, so a returned solution is nominally within tolerance if the loop terminates, but the algorithm's ability to terminate efficiently in near-undiscounted regimes and its 'exact solution' claim rest on the inner solves being accurate enough for the greedy step to make guaranteed progress. If the 2-norm criterion lets the inner solver exit prematurely, policy evaluation can be too loose, causing slow or non-monotonic outer convergence and pushing the solver onto its iteration caps rather than its convergence theory. This is the weakest link in the central claim.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper presents madupite, an open-source distributed-memory solver for discounted infinite-horizon MDPs with finite state and action spaces. The solver is built on PETSc and implements inexact policy iteration, with a Python API and user-selectable inner linear solvers, preconditioners, and stopping parameters. The paper describes the algorithmic background (Algorithm 1), data layout and parallelization choices, and reports benchmarks: Amdahl speedup analysis (p≈0.95), discount-factor sensitivity with different inner solvers, scaling to MDPs beyond laptop memory, a comparison with pymdptoolbox and mdpsolver, and case studies in epidemiology (SIS), inverted pendulum control, and 2D maze navigation. The headline claims are that madupite is the only solver that can efficiently compute exact solutions at large scale and near-undiscounted settings and that it is unique in allowing users to customize the inner solution method.","tokens_in":17026,"tokens_out":7967,"duration_ms":90056,"significance":"If the performance and algorithmic claims are substantiated, madupite would be a practically valuable contribution: it is open source, builds on a mature HPC library, provides reproducible benchmarks with median runtimes over 10 runs, and demonstrates solving MDPs with millions of states on a cluster. The case studies are realistic and the comparisons, though narrow, are run on the same hardware. The paper does not provide machine-checked proofs, and the theoretical guarantees are inherited from the cited iPI theory [18]; the main value is engineering and empirical. The strength of the claims in the abstract is currently ahead of the evidence, and the modified inner stopping criterion introduces a correctness gap that must be resolved before the exactness claims can be accepted.","major_comments":[{"comment":"The statement that the 2-norm inner stopping criterion is 'more stringent' than the infinity-norm criterion is mathematically incorrect: for any vector x, ∥x∥∞ ≤ ∥x∥2, so the test ∥r_i∥2 < α∥r_0∥2 can be satisfied while ∥r_i∥∞ < α∥r_0∥∞ fails, potentially by a factor up to sqrt(n). Since the iPI convergence and suboptimality guarantees cited from [18] are formulated for the infinity-norm relative-residual stopping rule, the manuscript must either prove that the guarantees remain valid under the 2-norm replacement, revert to the infinity-norm rule, or provide empirical evidence (e.g., reported infinity-norm residuals of returned solutions across all benchmarks) that the modification does not change the convergence behavior. This is load-bearing because the abstract's 'exact solution' claim and the near-undiscounted scalability results in Section IV-C rely on inner solves being accurate enough for the greedy step to make guaranteed progress.","section":"III-B.3, Algorithm 1 step 8"},{"comment":"The uniqueness claims—'only solver capable of efficiently computing exact solutions...' and Section IV-A.2's 'only existing MDP solver that enables users to customize'—are supported by comparison with only two open-source Python toolkits (pymdptoolbox and mdpsolver). The evidence establishes superiority on one benchmark instance against these two comparators, not uniqueness in the field. Please broaden the survey/comparison or qualify the claims to the compared toolkits, and report the configuration of mdpsolver's parallel mode (number of threads/cores) and the variance of the runtimes in Table 3.","section":"Abstract; Section IV-A.4"},{"comment":"Algorithm 1 returns V_k after breaking on the outer or inner iteration caps (N_o, N_i), without any residual certificate. The evaluation sections do not state whether any benchmark run terminated by reaching a cap rather than by satisfying the tolerance; given the weakened inner stopping criterion, this is a real possibility. The paper should report cap activity for all experiments and, when a cap is hit, either continue to convergence or clearly label the output as not certified. Without this, the reported runtimes cannot be interpreted as times to an exact (tolerance-certified) solution.","section":"Algorithm 1 lines 11-12, 15-16; Section IV"}],"minor_comments":[{"comment":"There are several typos and word-choice issues, e.g., 'benchmakrs' in Section IV-A.1, 'loosing' in Section III-C, and 'without requiring the minimal change' in Section III-B.1 (should be 'without requiring any change').","section":"Throughout"},{"comment":"The text says the blue dotted line plots median runtime as a function of the number of ranks, while the caption says it plots median speedup; the axis and caption should be made consistent.","section":"Figure 1 and Section IV-A.1"},{"comment":"Please report the mdpsolver parallel configuration (number of threads or cores) and provide standard deviations or confidence intervals; a single benchmark instance with means over 10 runs gives limited evidence for the speedup claims.","section":"Section IV-A.4 and Table 3"},{"comment":"MINRES and CG are listed as supported inner solvers, but I−γPπ is generally nonsymmetric; clarify whether these are intended only for MDPs with special structure or are provided as user options without a convergence guarantee.","section":"Section III-B.3"},{"comment":"The word 'exact' is used for solutions computed to a finite tolerance (e.g., tol=1e-8); the paper should state explicitly that 'exact' means 'within the user-specified residual tolerance' to avoid overclaiming.","section":"Abstract and Section IV"}],"recommendation":"major_revision","confidential_remarks":"The 2-norm stopping-criterion issue is the main technical reason for major revision: it is a concrete correctness gap in a load-bearing part of the exactness claim. The uniqueness claims in the abstract also need to be tempered or substantially better supported. Apart from these, the paper is a solid software and performance report, and the public code and benchmark setup are strengths. The editor may also wish to consider whether the engineering focus is a good fit for the journal given the JOSS companion."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Matilde and co-authors have built a real distributed MDP solver, and the paper gives a level of implementation detail you rarely see in this area. The matrix layout decisions, the matrix-free policy evaluation, and the PETSc integration are explained carefully, and the benchmarks—median over 10 runs, open code, realistic SIS and inverted pendulum problems—support the basic claim that madupite solves million-state, high-discount MDPs on a cluster that would not fit on a laptop. The core iPI algorithm is not new; it is the authors' own prior work [18], and the paper is honest about that. The contribution here is engineering, and the engineering looks solid.\n\nThe main soft spot is the inner-loop stopping criterion in Section III-B.3. The text says the 2-norm of the linear residual is a 'more stringent criterion' than the infinity-norm condition in Algorithm 1. That is backwards: for any vector, the infinity-norm is bounded by the 2-norm, so a 2-norm relative-residual threshold is weaker, by up to a factor of sqrt(n). The convergence guarantees for inexact policy iteration in the cited [18] are established for the infinity-norm inner test; the paper provides no proof they survive this change. In practice the outer loop still checks the infinity-norm of the full residual, so if the algorithm terminates, the returned value is within tolerance. But the efficiency and the 'exact solution' claim rest on inner solves being accurate enough for the greedy step to make steady progress, and the 2-norm condition could let the inner solver exit too early. This is a genuine flaw in the argument, not a nitpick. The fix is straightforward: prove the guarantee under the 2-norm, go back to the infinity-norm, or present the 2-norm as a heuristic with supporting experiments. The authors should be asked to address this.\n\nThe 'only solver' and 'unique' claims are also overbroad. The comparison is against two toolboxes, pymdptoolbox and mdpsolver. That is enough to say madupite is competitive and scalable, but not enough for 'only solver capable.' Same with the customization claim—unique among the compared set, not unique in the world. The Amdahl p=0.95 estimate comes from one benchmark, so the ~20x speedup ceiling is a fitted number, not a general law. That is a minor caveat, not a fatal one.\n\nWho is this for? Anyone working on exact dynamic programming for large MDPs, or on HPC numerical software. It deserves a serious referee. I would recommend sending it to peer review with a request to fix the stopping-criterion issue and tone down the uniqueness claims.","headline":"Real engineering value in a distributed MDP solver, but a mischaracterized 2-norm stopping condition and overbroad uniqueness claims need to be fixed.","tokens_in":17535,"tokens_out":3153,"would_cite":true,"duration_ms":34861,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C40","65F10"],"pacs":[],"model":"deepseek-v4-flash","headline":"Madupite is a distributed solver for finite-state Markov decision processes that, the authors argue, is the only one able to compute exact solutions for problems too large to fit in a laptop's memory, even at discount factors close to one.","keywords":["Markov decision processes","inexact policy iteration","distributed memory parallelism","exact dynamic programming","discounted infinite-horizon MDPs","Krylov subspace methods","high-performance computing","large-scale MDPs"],"falsifier":"Solve a collection of small MDPs with known optimal value functions using the 2-norm inner stopping rule, and compare the infinity-norm Bellman residual at termination with the user-specified tolerance; if the residual exceeds the tolerance for any instance, the exactness claim as stated is false for that configuration.","tokens_in":16560,"feed_emoji":"⚙️","tokens_out":8182,"duration_ms":91593,"temperature":0.7,"pith_summary":"The paper introduces madupite, a solver for discounted infinite-horizon Markov decision processes with finite state and action spaces, and argues that it is the only solver able to compute exact solutions at a scale that exceeds the memory of a modern laptop, including settings with discount factors close to one. The central bet is that inexact policy iteration, in which each policy evaluation is only approximately solved by an iterative linear solver, can be combined with distributed-memory parallelism to make exact dynamic programming competitive at scale. If the bet holds, practitioners facing large real-world MDPs no longer have to choose between quantifiable optimality guarantees and tractability. The paper backs the claim with benchmarks on epidemic control, inverted pendulum stabilization, and maze navigation, reporting exact solutions for state spaces in the millions.","feed_headline":"Distributed solver claims exact answers for MDPs beyond laptop memory","feed_subtitle":"Combines inexact policy iteration with cluster computing to solve high-discount problems exactly.","key_machinery":"The load-bearing object is the solver madupite itself: a distributed implementation of inexact policy iteration built on a portable scientific-computing toolkit that supplies sparse distributed matrices, vectors, and a library of iterative linear solvers. Inexact policy iteration alternates a greedy-policy extraction step with an approximate policy evaluation step, where the inner loop runs an iterative linear solver on (I - gamma P^pi) V = g^pi until a residual-based stopping condition is met; the algorithm's outer tolerance and inner-accuracy parameter $\\alpha$ regulate the trade-off. Two implementation details carry the scalability: the transition probability tensor is flattened into an n m by n row-stacked sparse matrix and partitioned so that all rows belonging to the same state live on the same process, and the coefficient matrix is applied matrix-free through a shell operator, avoiding explicit assembly unless a preconditioner such as SOR needs it. The inner stopping condition is computed from the 2-norm of the linear residual, which the solver already produces internally, rather than the infinity norm used in the theoretical description.","core_discovery":"On its own terms, the paper's claim is that madupite establishes a new baseline for exact MDP solving: by storing the transition tensor in a row-block layout distributed over parallel processes and forming the operator I - gamma P^pi matrix-free, it can evaluate policies and extract greedy policies without ever assembling the full system on one machine. The outer loop is an inexact policy iteration whose inner loop solves the policy-evaluation linear system with a user-selected Krylov solver (GMRES, BiCGStab, TFQMR, Richardson, and others), and the stopping rule uses the 2-norm of the linear residual instead of the infinity norm to cut per-iteration overhead. Benchmarks show the solver solving SIS epidemic models of one million states in under ten seconds, an inverted pendulum discretization of about ten million states in about seventeen minutes, and a maze of one million states in under two minutes, while a 95 percent parallelizable workload gives a theoretical maximum speedup near twenty. The paper also demonstrates speedups of roughly two to three times over existing single-machine MDP toolkits, and emphasizes that customizing the inner solver is what unlocks fast convergence in high-discount regimes.","pith_inferences":["The switch from infinity-norm to 2-norm inner residuals is described as a performance optimization; an obvious next step is a worst-case analysis showing whether the theoretical convergence guarantee survives, since the 2-norm can hide a large single-component error.","A portable sanity check for the 'exact solution' claim is to run the solver on small MDPs with analytically known value functions and verify the infinity-norm Bellman residual on exit, which the paper does not report.","Because the outer loop is generic, the same distributed machinery is plausibly reusable for risk-averse MDPs or stochastic shortest-path problems, as the paper hints for the risk-averse case.","Amdahl's 95 percent parallelizable estimate implies a speedup ceiling near 20 for the current implementation, so reaching hundreds of cores would likely demand reducing synchronization or overlapping communication with computation."],"forward_implications":["If the central claim holds, medium-to-large MDPs can be solved exactly on clusters, giving practitioners certified near-optimal policies instead of function approximations of unknown quality.","The high-discount-factor regime, historically the slowest for dynamic programming, becomes tractable when the inner solver is chosen to exploit problem structure.","Distributed storage rather than laptop RAM becomes the practical limit on problem size, so the solver can absorb sparse or dense MDPs that previously had to be simplified or aggregated.","The ability to recover classical algorithms (value iteration, policy iteration, optimistic policy iteration) through parameter settings makes madupite a single testbed for comparing DP variants at scale.","The reported speedups over existing single-machine toolkits suggest that simply upgrading the solution algorithm, not just the hardware, carries much of the benefit."],"supporting_citations":[{"why":"Provides the inexact policy iteration convergence results that underwrite the exactness and near-undiscounted performance claims.","marker":"[18]"},{"why":"Supplies the distributed sparse matrices, vectors, and iterative linear solvers that the implementation builds on.","marker":"[3]"},{"why":"Introduces the GMRES-based policy iteration variant whose high-discount behavior the benchmarks exploit.","marker":"[14]"},{"why":"Is the standard reference for dynamic programming and policy iteration used to frame the problem and the classical baselines.","marker":"[7]"},{"why":"Is the shared-memory MDP toolbox used as the baseline that motivates the distributed design.","marker":"[10]"},{"why":"Is the multi-core-capable MDP solver used as the parallel baseline in the comparison benchmarks.","marker":"[2]"}],"fun_headline_variants":["Distributed MDP solver cracks million-state problems exactly","Exact MDP solving goes cluster-scale with madupite","Madupite: exact large-scale MDPs without approximation","MDP solver scales to millions of states, exactly","Cluster-powered MDP solver beats laptop memory limits"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The paper assumes the modified inner-loop stopping rule is at least as demanding as the theoretical one, even though the rule it actually implements can stop earlier, so if that assumption fails, the returned policy may not be as accurate as claimed.","fun_headline_variants_meta":{"raw":{"variants":["Distributed MDP solver cracks million-state problems exactly","Exact MDP solving goes cluster-scale with madupite","Madupite: exact large-scale MDPs without approximation","MDP solver scales to millions of states, exactly","Cluster-powered MDP solver beats laptop memory limits"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000185,"raw_usage":{"total_tokens":1356,"prompt_tokens":1015,"completion_tokens":341,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":631,"completion_tokens_details":{"reasoning_tokens":262}},"tokens_in":631,"tokens_out":341,"duration_ms":4283,"temperature":1.0,"reasoning_tokens":262,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T11:32:46.874342+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Solve a collection of small MDPs with known optimal value functions using the 2-norm inner stopping rule, and compare the infinity-norm Bellman residual at termination with the user-specified tolerance; if the residual exceeds the tolerance for any instance, the exactness claim as stated is false for that configuration.","supporting_citations":[{"cited_title":"Inexact Policy Iteration Methods for Large-Scale Markov Decision Processes","cited_arxiv_id":"2404.06136","evidence_quote":"Provides the inexact policy iteration convergence results that underwrite the exactness and near-undiscounted performance claims."},{"cited_title":"Balay, S","cited_arxiv_id":null,"evidence_quote":"Supplies the distributed sparse matrices, vectors, and iterative linear solvers that the implementation builds on."},{"cited_title":"Gargiani, D","cited_arxiv_id":null,"evidence_quote":"Introduces the GMRES-based policy iteration variant whose high-discount behavior the benchmarks exploit."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Is the standard reference for dynamic programming and policy iteration used to frame the problem and the classical baselines."},{"cited_title":"Chad `es, G","cited_arxiv_id":null,"evidence_quote":"Is the shared-memory MDP toolbox used as the baseline that motivates the distributed design."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Is the multi-core-capable MDP solver used as the parallel baseline in the comparison benchmarks."}],"review_version":1}