{"id":"ec10e51f-4def-46c9-95d8-ff1d1ac12d54","arxiv_id":"2608.06545","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For average-reward MDPs with total-variation uncertainty, the minimax sample complexity is SA/epsilon^2 times min{H0,Hsigma}, with an extra SA sigma Hsigma^2/epsilon^2 term in the low-tolerance regime, and the paper provides matching algorithms.","lead":"Distributionally robust planning usually asks how many samples are needed when the environment's transition probabilities are imperfectly known. This paper gives the exact answer for average-reward Markov decision processes in terms of two span parameters, plus algorithms that achieve this rate, one of which needs no advance knowledge of those spans.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lower bound proves the robust-specific term only for ε ≤ 0.01σH0, so the claimed low-tolerance minimax rate is unproven in the intermediate regime.","rationale":"The reader identified Assumption 1 (unichain) as the weakest assumption, but that is an explicit structural restriction and not a hidden flaw. The load-bearing issue I find is in the proof of the central minimax claim: the lower bound's robustness-specific term is proven only for ε ≤ 0.01σH0, while the upper bounds and the abstract claim this term throughout the low-tolerance regime ε ≲ σH0. When H0 < Hσ and σHσ^2 is much larger than H0, the two rates differ by an unbounded constant factor in the region 0.01σH0 < ε < 7σH0. The lower bound in that region is only Ω(SA H0/ε^2), which does not match the upper bound's SA(H0 + σHσ^2)/ε^2. Proposition 1 guarantees the relevant span pair is realizable, and the Appendix C constructions appear consistent with the span bounds, so the gap is substantive. Because the paper's core contribution is a tight minimax characterization, this gap means the advertised claim is not fully proven; the upper bound may be loose in the intermediate regime. The appropriate resolution is to extend the lower-bound construction to larger ε or to explicitly restrict the low-tolerance claim to ε ≤ cσH0 for a sufficiently small constant c. This is a fixable but necessary correction, hence CONDITIONAL rather than ACCEPT.","tokens_in":74173,"tokens_out":33845,"duration_ms":285096,"concrete_test":"Re-run the lower-bound construction in Appendix C.2.3 with ε = c σH0 for c = 0.1 (and other constants), recomputing the testing gap condition (28) (Lemma 5) and the KL bound (46). If the weighted gaps and the KL bound still yield N ≤ C σHσ^2/ε^2 with an absolute constant C, the lower bound extends and the concern is resolved. If the inequalities force ε to remain below 0.01σH0, then Eq. (1) overstates the low-tolerance regime and the matching claim must be narrowed.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The formal lower bound, Theorem 1(b), establishes the robustness-specific term σHσ^2 only when ε ≤ 0.01σH0. The headline rate (1) and the upper-bound theorems (Theorems 2 and 3) assert this term in the low-tolerance regime ε ≲ σH0, with the upper bounds covering ε < 7σH0. For instances with H0 < Hσ and σHσ^2 ≫ H0, the two rate expressions differ by a non-constant factor in the intermediate regime 0.01σH0 < ε < 7σH0: the lower bound supplies only Ω(SA H0/ε^2), while the upper bound is O(SA(H0 + σHσ^2)/ε^2). Proposition 1 shows such span pairs are realizable, and the Appendix C hard instances respect the span bounds, so this is not an empty region. Consequently, the claimed matching minimax characterization in Eq. (1) is not established over the stated low-tolerance regime; the upper bound may be loose there. The paper needs either an extended lower bound covering all ε ≤ cσH0 for a constant c, or a reformulation stating that the robust-specific lower bound applies only when ε is sufficiently far below σH0.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies distributionally robust average-reward Markov decision processes under (s,a)-rectangular total-variation uncertainty sets, in a generative-model setting. It defines nominal and robust optimal bias spans H_0 and H_sigma, and claims that the minimax total sample complexity is, up to logarithms, (SA/epsilon^2) times min{H_0,H_sigma} in the high-tolerance regime epsilon ≳ sigma H_0, and min{H_0,H_sigma} + sigma H_sigma^2 in the low-tolerance regime epsilon ≲ sigma H_0. The main contributions are a lower bound (Theorem 1), a span-informed plug-in reduction with matching upper bound (Theorem 2), a span-agnostic adaptive procedure (Theorem 3), and simulations supporting the predicted rates. The paper also proves supporting results on robust Bellman equations, span comparison with prior robust span parameters, and a perturbation bound relating nominal and robust optimal rewards.","tokens_in":74337,"tokens_out":5989,"duration_ms":57040,"significance":"If the stated minimax characterization is correct, this is a substantial contribution: it gives the first tight sample-complexity characterization for robust average-reward MDPs and improves on prior quadratic-in-span upper bounds. The central rates are parameter-free up to universal constants, the lower-bound constructions instantiate prescribed span values, and the experimental section varies H_0, H_sigma, and sigma independently and checks the predicted slopes, which are all genuine strengths. The proof structure is extensive, with explicit verification lemmas, a discounted plug-in theorem with localized concentration, and a span-agnostic selection argument. The main reservation is a gap in the regime coverage of the lower bound, described below, which prevents the headline rate (1) from being fully established as stated.","major_comments":[{"comment":"The claimed minimax rate (1) is not established across the full low-tolerance regime. The robust-specific term sigma H_sigma^2 in the lower bound is proved only under the condition epsilon <= 0.01 sigma H_0, whereas the matching upper bound in Theorem 2(b) is asserted for the complementary condition 7 sigma H_0 > epsilon, i.e., epsilon < 7 sigma H_0. For instances with H_0 < H_sigma and sigma H_sigma^2 >> H_0, the lower bound supplies only Omega(SA H_0/epsilon^2) in the intermediate regime 0.01 sigma H_0 < epsilon < 7 sigma H_0, while the upper bound is O(SA(H_0 + sigma H_sigma^2)/epsilon^2); these differ by a nonconstant factor. Proposition 1 shows that such span pairs are realizable, and the Appendix C hard instances respect the span constraints, so this is not an empty region. Please either extend the lower bound to all epsilon <= c sigma H_0 for a universal constant c, or rescope Eq. (1) and Theorems 1–3 so that the robust-specific lower bound is stated only for epsilon sufficiently far below sigma H_0, with the intermediate regime explicitly left open.","section":"Theorem 1(b) vs Theorem 2(b), Eq. (1)"},{"comment":"The proof of Theorem 1 says it suffices to verify the min-span and robustness-specific components separately, but the combination is not complete for the regime in which both components must be active. The robustness-specific construction is run under epsilon <= 0.01 sigma min{H_0,H_sigma}, and the absorption argument in Eq. (26) covers only the case where this condition fails while H_sigma < H_0. The remaining case H_0 < H_sigma with 0.01 sigma H_0 < epsilon < 7 sigma H_0 is not addressed by either construction, so the lower bound does not support the rate displayed in Eq. (1) for that region. This is the same gap as the previous comment, but it is worth making explicit that the issue is in the proof's reduction to two separate sample-size components, not merely in the theorem statement.","section":"Section C.2, combination argument"}],"minor_comments":[{"comment":"The abstract's display for NSA appears to be missing a closing delimiter for the cases environment; the full-text Eq. (1) is correctly typeset, but the abstract version should be fixed for consistency.","section":"Abstract, display equation"},{"comment":"The caption refers to a dashed outline marking regimes where the robust reduction is used, but no dashed outline is visible in the table as rendered; please add the outline or revise the caption.","section":"Table 1 caption"},{"comment":"The experiments check the low-tolerance rate at isolated values of sigma and H_sigma, but they do not probe the intermediate regime 0.01 sigma H_0 < epsilon < 7 sigma H_0. If the lower-bound gap is closed, an experimental check in that regime would strengthen confidence in the claimed threshold behavior.","section":"Section 5.1, Figure 1"},{"comment":"The notation H0 and H_sigma is defined with max{1, ...}, but Proposition 1 is stated for any H_0,H_sigma >= 1; the proof uses values at least one, so this is consistent, but the proposition statement would be cleaner if it explicitly noted that the constructed spans are exactly the prescribed values after the max-with-one convention.","section":"Notation, Section 2.2"}],"recommendation":"major_revision","confidential_remarks":"The paper is well-executed and the central idea is strong, but the headline minimax claim has a real regime-coverage gap in the lower bound. The gap is local and fixable — either by extending the lower-bound construction or by carefully rescoping the theorem statement — so I see this as a major revision rather than a rejection. If the authors address the intermediate regime, I would support publication; the paper makes a significant contribution to the robust AMDP literature."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. This is the first minimax lower bound for robust average-reward MDPs, and it improves the prior quadratic span dependence to linear, with a sharp robustness-specific term. The span-agnostic reduction that calibrates both the discount factor and the nominal-vs-robust choice from data is genuinely clever and well executed. But the main rate (1) is not fully proven as stated. Theorem 1's lower bound proves the sigma-H-sigma-squared term only for epsilon <= 0.01 sigma H_0, while the upper bound in Theorem 2 uses it for all epsilon < 7 sigma H_0. The intermediate region is nonempty: Proposition 1 realizes instances with H_0 < H_sigma and sigma H_sigma^2 >> H_0, and there the lower bound supplies only Omega(SA H_0 / epsilon^2), while the upper bound claims O(SA (H_0 + sigma H_sigma^2)/epsilon^2). These differ by a non-constant factor, so the matching claim in Eq. (1) is not established over the full low-tolerance regime. This is a genuine gap in the paper, not a nitpick. The likely fix is a lower-bound construction covering all epsilon <= c sigma H_0 for a universal constant c, or a reformulation of Eq. (1) with two explicit thresholds.\n\nEverything else holds up. The reduction framework with nominal anchors, the localized concentration analysis, and the span-agnostic selection via lower-confidence bounds are the real content, and they look careful. The experiments match the predicted slopes. The unichain assumption is standard and stated clearly. I saw no fitting, no circular reasoning, and no invented parameters. The appendices are substantial enough that independent checking is feasible.\n\nBottom line: valuable paper, deserves a serious referee, but it is not ready in its current form. The central theorem's claimed equivalence must be repaired or narrowed. I would send it to review and expect a revision.","headline":"Strong theoretical package with a real gap: the claimed matching minimax rate is unproven in an intermediate tolerance regime.","tokens_in":74909,"tokens_out":2685,"would_cite":true,"duration_ms":24076,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that the minimax sample complexity of learning epsilon-optimal robust policies in average-reward MDPs with total-variation uncertainty sets is SA/epsilon^2 times min{H0,Hsigma}, plus an extra SA sigma Hsigma^2/epsilon^2…","keywords":["average-reward Markov decision processes","distributionally robust optimization","total-variation uncertainty sets","minimax sample complexity","generative model","bias span","discounted reduction","span-agnostic learning"],"falsifier":"Construct the hard instances of Appendix C with known $H_0,H_\\sigma,\\sigma$ and compute the minimax risk; if any algorithm succeeds with $NSA$ below the claimed bound by a large constant factor, the lower bound is wrong, and a concrete check is to run the span-agnostic algorithm on the two-state family of Proposition 1 and verify that the empirical per-state-action sample size $N_{95}$ bends at $\\varepsilon\\sim\\sigma H_0$ with slope $+1$ in $\\min\\{H_0,H_\\sigma\\}$ above the threshold and an additive dependence linear in $\\sigma$ and quadratic in $H_\\sigma$ below it.","tokens_in":73922,"feed_emoji":"🎯","tokens_out":9517,"duration_ms":74926,"temperature":0.7,"pith_summary":"This paper studies how many transition samples from a nominal model are needed to learn a policy that is $\\varepsilon$-optimal in worst-case average reward over total-variation uncertainty sets of radius at most $\\sigma$. The answer it establishes is the minimax total sample complexity $NSA \\asymp \\frac{SA}{\\varepsilon^2}\\min\\{H_0,H_\\sigma\\}$ when $\\varepsilon \\gtrsim \\sigma H_0$, and $\\frac{SA}{\\varepsilon^2}(\\min\\{H_0,H_\\sigma\\}+\\sigma H_\\sigma^2)$ when $\\varepsilon \\lesssim \\sigma H_0$, up to logarithmic factors; here $H_0$ and $H_\\sigma$ are the nominal and robust optimal bias spans. Matching lower and upper bounds are proved, with algorithms that work whether or not the spans are known. A sympathetic reader would care because this separates the statistical cost of robustness from the cost of ordinary average-reward learning: robustness is essentially free in the high-tolerance regime and costs a specific new term $\\sigma H_\\sigma^2$ only when the target tolerance is below the perturbation scale $\\sigma H_0$.","feed_headline":"Exact sample cost found for robust average-reward RL","feed_subtitle":"Matching bounds show the extra robustness cost enters only below the sigma*H0 threshold, as sigma times H_sigma squared.","key_machinery":"The carrying mechanism is the optimal bias span, defined as the minimum span seminorm among solutions of the average-reward Bellman optimality equations $\\rho^\\star\\mathbf{1}+h=T_0h$ and $\\rho^{\\star,\\sigma}\\mathbf{1}+h=T_\\sigma h$, giving $H_0$ and $H_\\sigma$. The argument is a reduction from robust average-reward to robust discounted MDPs: at $\\gamma=1-\\varepsilon/(3H_\\sigma)$, a policy that is $H_\\sigma$-suboptimal in discounted value is $\\varepsilon$-optimal in robust average reward (Corollary 1). The proof sharpens generic discounted plug-in bounds with a nominal-anchor comparison that isolates $\\min\\{H_0,H_\\sigma\\}$, span control of discounted values by $H_\\sigma$ (Lemma 3), and span-localized concentration in place of the worst-case horizon $(1-\\gamma)^{-1}$. For unknown spans, a first data batch certifies a nominal anchor and a dyadic discount grid with lower-confidence bounds selects the reduction and horizon.","core_discovery":"The paper's central claim is that the statistical price of distributional robustness in average-reward MDPs is exactly captured by the scale $\\sigma H_0$ and the robust bias span $H_\\sigma$. Over $(s,a)$-rectangular TV uncertainty sets of radius at most $\\sigma$, the minimax number of samples per state-action pair is, up to log factors, $N \\asymp \\varepsilon^{-2}\\min\\{H_0,H_\\sigma\\}$ when $\\varepsilon\\gtrsim\\sigma H_0$, and $N\\asymp \\varepsilon^{-2}(\\min\\{H_0,H_\\sigma\\}+\\sigma H_\\sigma^2)$ when $\\varepsilon\\lesssim\\sigma H_0$. The lower bound (Theorem 1) decomposes into the linear min-span term inherited from standard AMDPs and a robustness-specific $\\sigma H_\\sigma^2$ term active in low tolerance; the upper bounds (Theorems 2 and 3) attain both rates by reducing to discounted problems, choosing the nominal or robust reduction and a discount factor from known spans or adaptively from data. The paper also shows the two span parameters are independent (Proposition 1), so both must appear, and that a nominal optimal policy is $\\sigma H_0$-optimal for the robust problem (Proposition 2), which is why the threshold appears.","pith_inferences":["The authors do not pursue it, but the $\\sigma H_0$ threshold suggests a general design principle for other uncertainty geometries (e.g., $L_p$ or Wasserstein balls): robustness is free until the perturbation's value loss is comparable to the allowed suboptimality, with the bias span replaced by a suitable continuity modulus of the value function.","A testable practical consequence is that simulators should first estimate $H_0$ from a small pilot batch and only switch to robust planning when $\\varepsilon/\\sigma$ is on the order of $H_0$; this could save orders of magnitude in sample budget in high-tolerance settings.","The lower-bound construction, which encodes which of two actions has a larger perturbed transition probability, suggests that the $\\sigma H_\\sigma^2$ term is an action-identification cost; non-rectangular uncertainty sets, where perturbations can be coordinated across states, might yield a different robustness term rather than a simple additive one.","The lower-confidence-bound selection over a dyadic grid is a generic recipe: any average-reward reduction whose guarantee depends on an unknown horizon or span parameter can be made adaptive at a constant factor by maintaining candidate policies on a geometric grid and choosing by valid confidence penalties."],"forward_implications":["When the target tolerance is at least a constant times $\\sigma H_0$, robustness is statistically free: planning in the nominal MDP already achieves the minimax rate $SA\\min\\{H_0,H_\\sigma\\}/\\varepsilon^2$, with the robust reduction winning when $H_\\sigma\\leq H_0$.","When $\\varepsilon\\lesssim\\sigma H_0$, an extra $SA\\sigma H_\\sigma^2/\\varepsilon^2$ samples are necessary and sufficient; this is the first demonstration that the low-tolerance regime has a distinct robustness-specific cost.","If only the robust span $H_\\sigma$ is bounded and $H_0$ may be unbounded, the minimax rate collapses to $SA(H_\\sigma+\\sigma H_\\sigma^2)/\\varepsilon^2$, and a robust-only variant attains it without knowing the span.","The new bounds uniformly improve on earlier robust AMDP guarantees, replacing quadratic dependence on larger robust span parameters with $\\min\\{H_0,H_\\sigma\\}$ plus the $\\sigma H_\\sigma^2$ term.","The matching lower bound shows both terms in the rate are unavoidable, so any algorithm with sample complexity below this rate would contradict minimax optimality."],"supporting_citations":[{"why":"Supplies the nominal average-reward MDP sample-complexity bound $SA H_0\\varepsilon^{-2}$ that the robust rate extends.","marker":"Wang et al. 2022"},{"why":"Establishes the span-based minimax rate for standard AMDPs whose min-span term the robust bound inherits.","marker":"Zurek and Chen 2024"},{"why":"Provides the prior span-informed robust AMDP reduction with quadratic span dependence that this paper improves upon.","marker":"Roch et al. 2025"},{"why":"Provides the prior span-agnostic robust AMDP algorithm whose quadratic-span rate is improved by the new span-agnostic procedure.","marker":"Roch et al. 2026"},{"why":"Supplies the TV duality and robust discounted lower-bound machinery that the lower-bound construction adapts.","marker":"Shi et al. 2026"},{"why":"Derives the robust Bellman equations for average-reward MDPs used to define $H_\\sigma$ and verify policies.","marker":"Wang et al. 2023a"},{"why":"Establishes the generative-model discounted MDP sample complexity that motivates the reduction's discount-factor choice.","marker":"Li et al. 2024"}],"fun_headline_variants":["Robust RL sample cost: one threshold, two regimes","Robust MDP learning: threshold sigma H0 splits cost","Robust average-reward: extra sample cost only low tolerance","Matching bounds for robust average-reward MDPs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is the unichain condition (Assumption 1): for every stationary policy and every transition kernel in the uncertainty set, the induced Markov chain has exactly one recurrent class, so the robust average reward is a single number independent of the starting state; if this fails, the problem formulation itself becomes initial-state dependent and the reduction framework used for all upper and lower bounds no longer applies.","fun_headline_variants_meta":{"raw":{"variants":["Robust RL sample cost: one threshold, two regimes","Robust MDP learning: threshold sigma H0 splits cost","Robust average-reward: extra sample cost only low tolerance","Matching bounds for robust average-reward MDPs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000288,"raw_usage":{"total_tokens":1787,"prompt_tokens":1138,"completion_tokens":649,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":754,"completion_tokens_details":{"reasoning_tokens":580}},"tokens_in":754,"tokens_out":649,"duration_ms":6001,"temperature":1.0,"reasoning_tokens":580,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T14:31:18.446116+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct the hard instances of Appendix C with known $H_0,H_\\sigma,\\sigma$ and compute the minimax risk; if any algorithm succeeds with $NSA$ below the claimed bound by a large constant factor, the lower bound is wrong, and a concrete check is to run the span-agnostic algorithm on the two-state family of Proposition 1 and verify that the empirical per-state-action sample size $N_{95}$ bends at $\\varepsilon\\sim\\sigma H_0$ with slope $+1$ in $\\min\\{H_0,H_\\sigma\\}$ above the threshold and an additive dependence linear in $\\sigma$ and quadratic in $H_\\sigma$ below it.","supporting_citations":[],"review_version":2}