{"id":"e3343e5b-5db7-4a74-83a0-75ff7cf78598","arxiv_id":"2605.01339","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Parametric MDPs enable PAC uncertainty models for MDPs by projecting empirical frequencies onto parameter space with polytopic outer approximations, yielding tighter estimates than independent interval methods.","lead":"This paper proposes using parametric MDPs to project data uncertainty onto shared parameters, creating PAC uncertainty sets that respect transition dependencies instead of treating them independently. A smart generalist might read it to learn how to design less conservative robust policies for verifying systems like robots when only limited data is available.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.3","headline":"Central claim requires a pre-specified parametric structure expressing all transition probabilities as functions of shared parameters.","rationale":"The reader's weakest_assumption correctly isolates the prerequisite that makes the entire construction work. Because the full text was not supplied in the query, it is impossible to check whether later sections supply a structure-learning procedure or merely assume the structure is given; the abstract alone leaves the claim conditional on that assumption holding.","tokens_in":1697,"tokens_out":327,"duration_ms":18676,"concrete_test":"Construct a small MDP whose transitions obey a dependency (e.g., p(s'|s,a) = θ·f(s,a) for unknown θ) but supply the learner with a different parametric form (e.g., independent parameters per transition); draw N samples, compute the projected confidence set, and measure the empirical frequency that the true θ lies outside it. If this frequency exceeds the nominal PAC δ, the projection step fails to preserve the guarantee under structural mismatch.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The PAC guarantee and the claim of respecting algebraic dependencies both rest on the mapping from parameters to transition probabilities being known and correctly specified in advance. Projection of empirical frequency uncertainty onto parameter space only yields a valid confidence set for the true MDP if every transition is exactly the stated algebraic expression of those parameters; any misspecification means the projected set may exclude the true parameter vector with probability larger than the PAC failure probability. The abstract provides no mechanism for discovering or validating this structure from data, so the method applies only when the structure is given by the user.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The paper proposes learning uncertain MDPs via parametric MDPs (pMDPs), where transition probabilities are algebraic expressions over a shared parameter vector. Empirical transition frequencies are projected onto the parameter space to obtain a PAC-bounded confidence set that respects algebraic dependencies among transitions. Because the resulting pMDPs are hard to solve, the authors develop a hierarchy of sound polytopic outer approximations of the induced confidence set. Experiments are claimed to produce substantially tighter uncertainty estimates than classical interval-based uncertain-MDP methods.","tokens_in":1815,"tokens_out":497,"duration_ms":32083,"significance":"If the parametric structure is correctly specified in advance and the projection preserves the PAC guarantee, the method would yield less conservative robust policies by exploiting known algebraic dependencies. The polytopic outer-approximation hierarchy is a practical algorithmic contribution that makes the models tractable. The approach is limited by its reliance on a user-provided parametric form; without a mechanism to discover or validate that form, the PAC claim holds only conditionally on correct specification.","major_comments":[{"comment":"Abstract and §3 (projection step): the claim that projecting empirical frequencies onto the pMDP parameter space yields a PAC uncertainty model is load-bearing, yet no explicit theorem or derivation shows how the original PAC failure probability is preserved under the (generally nonlinear) projection; without this reduction the central guarantee does not follow from standard PAC-MDP results.","section":"Abstract and §3"},{"comment":"Evaluation section: the reported tighter uncertainty estimates presuppose that a suitable pMDP structure expressing all transitions as functions of shared parameters is already known; the manuscript gives no description of how this structure was obtained or validated for the benchmark domains, so it is impossible to assess whether the improvement is due to the projection technique or to favorable a-priori structure selection.","section":"Evaluation section"}],"minor_comments":[{"comment":"The notation distinguishing the parameter vector, the mapping to transition probabilities, and the induced confidence set could be introduced with a small concrete example in the preliminaries to improve readability.","section":"Preliminaries"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is a reasonable fit for a learning-for-verification venue, but the authors should be asked to clarify the scope of the PAC guarantee with respect to misspecification of the parametric form."},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for the detailed and constructive review. Below we address each major comment point by point and indicate the revisions we will incorporate.","responses":[{"response":"We agree that an explicit derivation is needed for rigor. The confidence set in parameter space is constructed as the preimage, under the parametric mapping P(θ), of the standard PAC confidence set over transition probabilities. Because the true parameter θ∗ induces the true transition probabilities, and the empirical frequencies lie inside the PAC set around those true probabilities with probability at least 1−δ, the true θ∗ necessarily belongs to the preimage set with the same probability. The PAC guarantee is therefore preserved by construction, independent of the nonlinearity of the mapping. We will add a formal theorem in §3 that states this reduction explicitly and derives the PAC bound for the parameter-space set directly from classical PAC-MDP results.","revision_made":"yes","referee_comment":"[Abstract and §3] Abstract and §3 (projection step): the claim that projecting empirical frequencies onto the pMDP parameter space yields a PAC uncertainty model is load-bearing, yet no explicit theorem or derivation shows how the original PAC failure probability is preserved under the (generally nonlinear) projection; without this reduction the central guarantee does not follow from standard PAC-MDP results."},{"response":"The referee is correct that the method presupposes a user-supplied parametric structure; the PAC claim holds conditionally on correct specification of the algebraic dependencies. For the reported benchmarks the structures were obtained from standard domain knowledge (shared parameters for slip/wind effects in grid-worlds, factored action effects in other environments). We will revise the evaluation section to include an explicit description of each parametric form together with a short justification based on the underlying MDP semantics. We will also add a clarifying sentence that structure discovery and validation are orthogonal to the present contribution and are left for future work, consistent with the limitations already noted in the manuscript.","revision_made":"yes","referee_comment":"[Evaluation section] Evaluation section: the reported tighter uncertainty estimates presuppose that a suitable pMDP structure expressing all transitions as functions of shared parameters is already known; the manuscript gives no description of how this structure was obtained or validated for the benchmark domains, so it is impossible to assess whether the improvement is due to the projection technique or to favorable a-priori structure selection."}],"tokens_in":1324,"tokens_out":510,"duration_ms":30864,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The paper shows how to get tighter uncertainty sets for MDPs learned from data by projecting empirical frequencies onto a parametric model that encodes dependencies between transitions. This gives PAC guarantees that respect the algebraic structure, unlike standard interval methods that bound each probability separately. What stands out is the use of pMDPs where transitions are functions of parameters, and then mapping the confidence intervals from data to a set in parameter space. They follow this with a series of polytopic outer approximations to make robust policy synthesis feasible, since the exact set is hard to handle. The experiments back this up by showing substantially tighter bounds than classical approaches. That's the practical payoff for applications like safety-critical systems where loose bounds hurt performance. The main limitation is the need for a suitable parametric structure upfront. The method works only if the transition probabilities can be expressed as the right functions of shared parameters, and the paper doesn't provide ways to discover or check that structure from the data. If the parametrization doesn't match the true MDP, the PAC property could fail. The approximations are conservative by design as outer bounds, which is fine but means some tightness is lost. Overall, this is aimed at people in MDP verification and robust control who already have some model structure in mind. It builds on existing PAC learning for MDPs but adds the dependency respect in a clean way. The math looks solid on the projection and approximation parts, assuming the structure is correct. I'd say send it to peer review. The core claim holds up and the evaluation supports it.","headline":"Projecting empirical uncertainty onto a pre-specified parametric MDP structure gives tighter PAC sets than independent intervals, but the whole thing rests on having the right parametrization upfront.","tokens_in":2287,"tokens_out":377,"would_cite":false,"duration_ms":28933,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"Projecting empirical uncertainty onto shared parameters in parametric MDPs produces PAC confidence sets that respect transition dependencies and are tighter than independent intervals.","keywords":["uncertain MDPs","parametric MDPs","PAC learning","robust synthesis","Markov decision processes","polytopic approximations","parameter learning"],"falsifier":"Sample trajectories from a known ground-truth MDP, apply the method to obtain an approximated uncertainty set, synthesize a robust policy, and check whether that policy fails to satisfy its specification for some transition function inside the true PAC set with probability higher than claimed.","tokens_in":2598,"feed_emoji":"📉","tokens_out":626,"duration_ms":20261,"temperature":0.7,"pith_summary":"The paper proposes learning uncertain models for unknown Markov decision processes by representing transition probabilities as expressions over a shared set of parameters. Statistical uncertainty from observed frequencies is then projected onto this parameter space rather than treated separately for each probability. The result is a probably approximately correct uncertainty model that preserves algebraic dependencies between transitions. Because the resulting models are difficult to solve directly, the authors develop a hierarchy of sound polytopic outer approximations of the induced confidence set. This yields substantially tighter uncertainty estimates than classical interval-based techniques while still supporting robust policy synthesis.","feed_headline":"Projecting uncertainty to shared parameters tightens MDP bounds","feed_subtitle":"The approach respects algebraic dependencies ignored by interval methods and supports more precise robust policy synthesis.","key_machinery":"The projection of statistical uncertainty from empirical transition frequencies onto the parameter space of a parametric MDP (pMDP), together with a hierarchy of polytopic outer approximations of the resulting confidence set.","core_discovery":"The paper establishes that uncertainty from empirical transition counts can be projected onto the parameter space of a pMDP to form a PAC-bounded uncertainty set for the underlying MDP that respects algebraic dependencies between transitions, and that this set admits a hierarchy of polytopic outer approximations that remain sound for robust verification and synthesis.","pith_inferences":["The same projection technique could be applied to other models such as POMDPs whenever transitions share latent parameters.","If parametric forms can be inferred from data instead of assumed, the method might scale to settings where the structure is not known beforehand.","Empirical comparisons on standard benchmarks would quantify how much less conservative the resulting policies are relative to interval-based uncertain MDPs."],"forward_implications":["Robust policies synthesized on the approximated models remain valid for the true underlying MDP with the stated PAC guarantees.","The resulting uncertainty sets are strictly contained in those obtained from independent confidence intervals on each transition probability.","The algebraic dependencies between transitions are automatically respected in the confidence set.","Computation of robust policies stays feasible through the hierarchy of outer approximations."],"fun_headline_variants":["Projecting uncertainty to pMDP parameters tightens bounds","Parameter projection respects MDP transition dependencies","Uncertainty projection onto shared pMDP params tightens bounds","pMDP learning projects empirical uncertainty onto parameters"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"A suitable parametric structure expressing the transition probabilities as functions of a shared parameter set must be known or provided in advance.","fun_headline_variants_meta":{"raw":{"variants":["Projecting uncertainty to pMDP parameters tightens bounds","Parameter projection respects MDP transition dependencies","Uncertainty projection onto shared pMDP params tightens bounds","pMDP learning projects empirical uncertainty onto parameters"]},"model":"grok-4.3","cost_usd":0.009659,"raw_usage":{"total_tokens":4179,"prompt_tokens":577,"num_sources_used":0,"completion_tokens":59,"cost_in_usd_ticks":96590500,"prompt_tokens_details":{"text_tokens":577,"audio_tokens":0,"image_tokens":0,"cached_tokens":64},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":3543,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":577,"tokens_out":59,"duration_ms":32556,"temperature":1.0,"reasoning_tokens":3543,"cache_read_input_tokens":64,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-05-09T14:25:26.574766+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"Sample trajectories from a known ground-truth MDP, apply the method to obtain an approximated uncertainty set, synthesize a robust policy, and check whether that policy fails to satisfy its specification for some transition function inside the true PAC set with probability higher than claimed.","supporting_citations":[],"review_version":1}