{"id":"7163ca64-08d9-44a0-a80a-6082edf4b294","arxiv_id":"2411.11451","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":2.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"This paper is a tutorial survey of robust MDPs, covering semantics, dynamic programming algorithms, model connections, applications, and open challenges.","lead":"This paper is a tutorial survey on robust Markov decision processes (RMDPs), models for decision-making when transition probabilities are not precisely known. It explains how to solve RMDPs by adapting value iteration and policy iteration, connects RMDPs to stochastic games and other models, and reviews applications in reinforcement learning and formal verification.","discovery_kind":"review","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The reach-reward tutorial only works under graph preservation, but Eqs. (3)-(5) in §3.2 are stated for convex (s,a)-rectangular RMDPs without this qualification; a simple interval uncertainty set with lower bound 0 invalidates the S∞ preprocessing.","rationale":"The reader's weakest assumption is graph preservation, and I agree; the concern is not merely scope. For a simple non-graph-preserving convex (s,a)-rectangular RMDP, the survey's stated precomputation plus Eq. (4) provably computes the wrong value. The S∞ classification in §2.2 is existential over policies and, in the RMDP setting, over transition functions; if p=0 is in the uncertainty set, s is classified as ∞, whereas the adversarial nature semantics in §4.2 assigns value 1. Thus the tutorial's central correctness claim overreaches. The paper does flag graph preservation in Remark 1 and again in the 'Other objectives' paragraph, so this is a scoping and emphasis issue rather than a fundamental technical error; the core content is correct under the intended assumptions. The reader's CONDITIONAL verdict remains appropriate: fix the citation error and prominently qualify Eqs. (3)-(5) with graph preservation, or present the counterexample as a motivation. Agreement: the reader identified the same load-bearing assumption; I add a concrete counterexample and note that compactness or positive lower bounds are also needed for the inner infimum to be well-behaved.","tokens_in":24724,"tokens_out":23886,"duration_ms":271571,"concrete_test":"Implement the one-state counterexample: states {s,t}; only enabled action a at s; R(s,a)=1 and R(t,a)=0; uncertainty p=P(s,a,t)∈[0,1] with self-loop mass 1-p. Compute the reach-reward value two ways: (i) using the survey's pipeline: apply §2.2 preprocessing to classify S∞ using the 'exists a policy that does not reach T almost surely' test, then run Eq. (4); (ii) using the explicit turn-based game of §4.2 where nature chooses p at the nature node to minimize expected total reward. Claim: (i) returns ∞ because p=0 puts s in S∞, while (ii) returns 1 (nature picks p=1). If this reproduces, the graph-preservation caveat is load-bearing and must be attached to every reach-reward statement.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Soft spot: §3.2's robust value iteration and policy iteration for reach-reward (Eqs. (3)-(5)) are presented as a direct adaptation for convex (s,a)-rectangular RMDPs, but the correctness of the reach-reward algorithm depends on graph preservation (Remark 1), and Remark 1 is not carried into the statement of the equations. The preprocessing into T, S∞, S? in §2.2 is graph-based; without a fixed support, the classification of S∞ is not uniform over P∈P. Concretely, let s be the only non-target state, with one action a, R(s,a)=1, P(s,a,t)=p, P(s,a,s)=1-p, p∈[0,1]. The set is convex and (s,a)-rectangular but not graph preserving at p=0. Applying the survey's preprocessing literally, p=0 means there is a policy (the only policy) that does not reach t a.s., so s∈S∞ and V(s)=∞. But in the game semantics of §4.2 nature minimizes reward and chooses p=1, yielding V(s)=1. Thus without graph preservation the tutorial's central algorithm gives the wrong value. The same issue affects L1-MDPs (§3.3), whose L1 balls around an empirical distribution generally have varying support, and the later caveat in 'Other objectives' comes only after Eqs. (3)-(5) have been asserted.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper is a survey and tutorial on robust Markov decision processes (RMDPs) intended to bridge the AI and formal-methods communities. After recalling MDPs and classical value iteration/policy iteration, it introduces RMDPs, classifies uncertainty sets by rectangularity, convexity, static/dynamic semantics, and graph preservation, and then presents robust dynamic programming for the (s,a)-rectangular case. It gives concrete inner-problem algorithms for interval MDPs and L1-MDPs, discusses instances such as multi-environment MDPs, and surveys connections to parametric MDPs, stochastic games, robust POMDPs, and distributional uncertainty. The final sections cover learning, abstraction, tool support, and future challenges.","tokens_in":24955,"tokens_out":13005,"duration_ms":133571,"significance":"The survey fills a genuine gap: there is little accessible tutorial material on RMDPs that speaks to both the AI and formal-methods communities. Its strengths are its clear progression from definitions to algorithms, the worked examples (notably Example 3 on last-action observability), the compact summary in Table 1, and the broad coverage of applications and tools. It is honest about several subtle semantic assumptions, for example by flagging graph preservation in Remark 1 and by pointing out that static/dynamic equivalence does not carry over to POMDPs. If the graph-preservation qualification is properly attached to the reach-reward equations, the tutorial will be a reliable entry point for researchers; with that fix, I would regard the survey as a solid contribution.","major_comments":[{"comment":"The reach-reward value-iteration and policy-iteration equations are displayed for convex (s,a)-rectangular RMDPs, but their correctness at the preprocessing level requires graph preservation (Remark 1), and this condition is not carried into the displayed statements. The S∞/S? preprocessing of §2.2 is defined via graph properties; without a fixed support, whether a state is in S∞ depends on which P∈P is considered. Concretely, take S={s,t}, T={t}, one action a, R(s,a)=1, and P(s,a,t)=p, P(s,a,s)=1-p with p∈[0,1]. This uncertainty set is convex and (s,a)-rectangular but not graph preserving. Applying the §2.2 preprocessing pointwise classifies s∈S∞ (the p=0 transition never reaches t), so Eq. (3) yields V(s)=∞. Under the game semantics described in §3.1 and §4.2, nature minimizes the agent's reward and chooses p=1, giving value V(s)=1. Thus the equations as stated are incorrect for this valid convex (s,a)-rectangular RMDP. The caveat in the 'Other objectives' paragraph later in §3.2 mentions graph preservation, but it appears after Eqs. (3)-(5) have already been asserted, and it is not linked to Definition 6 for L1-MDPs, whose L1 balls generally do not preserve support. I recommend explicitly restricting Eqs. (3)-(5) to graph-preserving convex (s,a)-rectangular RMDPs, or stating a separate robust definition of S∞/S? and showing that the equations remain correct without fixed support.","section":"§3.2, Eqs. (3)-(5), with Remark 1"}],"minor_comments":[{"comment":"In Algorithm 1, lines 5-11, when the while loop exhausts all successor states (e.g., two successors with lower bounds 0 and upper bounds 0.5), i becomes m+1 and line 10 indexes outside the sorted list; the algorithm as printed does not return a valid distribution in that boundary case. Add a guard or return the all-upper-bound distribution. The text also calls this a bisection algorithm, while the pseudocode is a water-filling greedy method; the description should be aligned with the code.","section":"§3.3, Algorithm 1"},{"comment":"Reference [95] lists arXiv identifier 2305.10546, which is the same as reference [40] (Fijalkow et al., 'Games on graphs'); the identifier for [95] appears to be a typo.","section":"References"},{"comment":"The symbol P is used for both the uncertain transition function (a set-valued object) and an element P∈P, which may confuse readers because Definition 1 uses P for a single transition function. Consider using a different script for the set.","section":"Definition 3"},{"comment":"Example 3 is correct and helpful, but the arithmetic behind the values 55 and 75 could be spelled out explicitly for both actions to make the last-action-observability point fully transparent.","section":"§3.1, Example 3"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things you should know up front. This is a genuinely useful tutorial survey of robust MDPs, and if you need to point a newcomer to one place, this is a good candidate. And there is a real scoping problem in Section 3.2: Equations (3)–(5) are presented as the reach-reward adaptation for convex (s,a)-rectangular RMDPs, but they are only correct under the graph-preservation assumption of Remark 1, and that qualifier is not carried into the equations. The stress-test example is valid. Take a single non-target state with one action, reward 1, transitions to target with probability p and self-loop with probability 1−p, p∈[0,1]. The set is convex and (s,a)-rectangular but not graph preserving at p=0. The paper's preprocessing classifies s as S∞ because there exists a P that never reaches the target, so the equations give V(s)=∞. The game semantics of Section 4.2 make nature minimize, and nature would choose p=1 to stop the reward, giving value 1. So the tutorial's central algorithm is wrong on this model if applied literally. The paper does flag Remark 1 and later says adaptation to reach-reward is straightforward 'provided the graph preservation property is met,' but that caveat appears after Equations (3)–(5) have been asserted as a direct adaptation. A one-sentence 'throughout this section we assume graph preservation' before Equation (3) would fix the issue. The same caution applies to L1-MDPs, whose balls can have varying support; the IMDP definition correctly enforces zero-lower-bound-iff-zero-upper-bound, so that class is safe. What the paper does well: clean definitions, worked examples that check out (I verified Example 3 on last-action observability), a good complexity table, and a useful map of connections to stochastic games, POMDPs, pMDPs, and RL. It fills a real gap, since the only other RMDP survey is oriented to recent results rather than fundamentals. Technical content is attributed to the right sources, and the self-citations are appropriate for a survey from active authors. There is no new theorem, but a tutorial does not need one. Minor issue: references [40] and [95] both cite arXiv:2305.10546, but they are different papers; one arXiv ID is wrong. Bottom line: this paper deserves a careful referee and a conditional accept after a minor revision that moves the graph-preservation caveat into the main algorithmic section. I would cite it as the entry-point tutorial.","headline":"Solid RMDP tutorial that deserves a serious referee, but Section 3.2 oversells its reach-reward algorithms by leaving the graph-preservation qualifier out of the main equations.","tokens_in":25559,"tokens_out":4605,"would_cite":true,"duration_ms":48764,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C40","68Q60","93E35"],"pacs":[],"model":"deepseek-v4-flash","headline":"Robust MDPs are presented as the unifying framework for decision-making under probability uncertainty across AI and formal methods, with a tutorial showing how to solve them by adding an inner worst-case step to value and policy iteration.","keywords":["robust Markov decision processes","uncertainty sets","rectangularity","value iteration","policy iteration","reach-reward objectives","interval MDPs","formal verification and reinforcement learning"],"falsifier":"Build a two-state RMDP where one transition has probability zero in one admissible transition function and positive probability in another, while the uncertainty set is still convex and (s,a)-rectangular. Running Equation (3) with the paper's preprocessing would classify that state inconsistently depending on which transition function is considered, making S∞ or S? ill-defined; observing that the value or the preprocessing changes discontinuously when the zero is changed to a small positive number shows the graph-preservation assumption is load-bearing and that the tutorial's claim is scoped to it.","tokens_in":24462,"feed_emoji":"🎲","tokens_out":5426,"duration_ms":50318,"temperature":0.7,"pith_summary":"This paper is a tutorial survey arguing that robust Markov decision processes (RMDPs) are the natural common framework when transition probabilities are not precisely known, which is the rule in both AI and formal verification. It develops RMDP semantics as a game between an agent and an adversarial nature that chooses from an uncertainty set, then shows that the familiar Bellman machinery survives: value iteration and policy iteration extend by replacing the expectation over a fixed transition function with an inner minimization over the uncertainty set at each state-action pair. The central tutorial claim is that for convex (s,a)-rectangular RMDPs this robust dynamic programming solves reach-reward objectives and that stationary deterministic optimal policies exist, using the same preprocessing as ordinary MDPs provided the uncertainty set is graph-preserving. A sympathetic reader comes away with a single recipe for turning any MDP solver into an RMDP solver, plus a map of where that recipe breaks down.","feed_headline":"Robust MDP solving reduces to adding an inner worst-case step","feed_subtitle":"A tutorial shows that convex rectangular uncertainty keeps value iteration and policy iteration, with stationary deterministic policies.","key_machinery":"The central object is the uncertain transition function P : U → (S×A ⇀ D(S)) with an uncertainty set U over transition variables, together with the notion of rectangularity that decides whether the adversary decomposes per state-action pair. The load-bearing identity is the robust Bellman equation $V^{{n+1}}$(s) = max_a { R(s,a) + inf_{P(s,a) ∈ P(s,a)} ∑_{s'} P(s,a,s') V^n(s') }, which reduces RMDP solving to ordinary value iteration with an extra inner optimization. For interval MDPs that inner problem is solved by a sorting and bisection algorithm; for L1-MDPs by a dual sorting algorithm; for general convex sets by convex optimization. Static versus dynamic uncertainty semantics and last-action observability are the two semantic knobs that, together with rectangularity and convexity, determine which policy class is sufficient.","core_discovery":"The survey's central claim is that RMDPs are a unifying model: they generalize bounded-parameter MDPs, L1-MDPs, multi-environment MDPs, and interval MDPs, and they carry over the standard solution methods. Robust value iteration replaces the sum over successor states by inf over the uncertainty set at each state-action pair, and under (s,a)-rectangularity the global adversary decomposes into local choices per state-action pair; if the uncertainty set is convex, the inner problem is efficiently solvable and stationary deterministic policies suffice. Robust policy iteration uses the same inner minimization in both policy evaluation and improvement. The paper is explicit that the reach-reward version requires graph preservation: every transition function in the uncertainty set must share the same zero-probability support, otherwise the standard S∞ and S? preprocessing is not well-defined.","pith_inferences":["Inference: the paper's dependence on graph preservation suggests that uncertainty sets built directly from sparse transition data, where some transitions are observed zero times in some states, fall outside the tutorial's algorithm; those sets would need a different preprocessing or a different inner problem.","Inference: the survey's comparison of robust value iteration and robust policy iteration points to a concrete open question the paper does not answer: whether policy iteration really is faster in practice because it solves fewer inner minimization problems.","Inference: the static/dynamic coincidence for (s,a)-rectangular RMDPs together with its failure in robust POMDPs suggests that partial observability is the real source of semantic fragility, so richer temporal-logic objectives for RMDPs may exhibit a similar sensitivity; the paper flags this as future work."],"forward_implications":["If the tutorial's recipe is correct, any MDP solver with value and policy iteration can be upgraded to handle convex (s,a)-rectangular RMDPs by plugging in an inner worst-case solver, and the resulting procedure inherits the same preprocessing and policy-extraction steps.","Reachability, discounted reward, and reach-reward objectives all fall out of the same framework by modifying the Bellman equation and preprocessing, so the recipe covers most objectives used in practice.","For s-rectangular, nonconvex, or non-rectangular uncertainty sets, the simple recipe stops working: optimal policies may need randomization and history, and policy evaluation becomes NP-hard, so these cases require specialised algorithms.","The same algorithms support optimistic variants, where the agent and nature cooperate, by replacing the inner infimum with a supremum, giving a dual view of the same uncertainty set."],"supporting_citations":[{"why":"Defines RMDPs with static and dynamic uncertainty semantics and robust dynamic programming, including the result that the two semantics coincide for (s,a)-rectangular reward maximization.","marker":"[64]"},{"why":"Introduces interval MDPs and time-stationary versus time-varying uncertainty, providing the other foundational source of the robust Bellman equation.","marker":"[93]"},{"why":"Provides the rectangularity taxonomy and the complexity and policy-class results that the survey reproduces in Table 1.","marker":"[118]"},{"why":"Defines bounded-parameter MDPs, the AI-side precursor that the survey argues RMDPs generalize.","marker":"[46]"},{"why":"Supplies fast Bellman updates for s-rectangular L1-robust MDPs, used in the survey's discussion of s-rectangular methods.","marker":"[58]"},{"why":"Introduces a policy iteration algorithm for L1-robust MDPs, which the survey cites as evidence that robust policy iteration is often the preferred method.","marker":"[59]"},{"why":"Gives the explicit sorting/bisection algorithm for solving the interval-MDP inner problem, which the survey presents as Algorithm 1.","marker":"[74]"},{"why":"Analyzes model-based interval estimation for MDPs and underlies the L1-MDP inner-problem algorithm the survey gives as Algorithm 2.","marker":"[109]"},{"why":"Defines multi-environment MDPs and their complexity results, used to illustrate discrete non-rectangular uncertainty.","marker":"[102]"}],"fun_headline_variants":["Robust MDPs add an inner worst-case step to standard solving","Tutorial: robust MDPs keep value iteration with an inf inside","RMDPs generalize interval MDPs and keep policy iteration","Robust MDP solving: replace sum over successors by inf over uncertainty","Robust MDPs: a unifying model with convex uncertainty and fixed algorithms"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The recipe assumes graph preservation: every transition function in the uncertainty set must put probability zero on exactly the same transitions, so the standard reach-reward preprocessing is well-defined; if that fails, the presented algorithms do not apply.","fun_headline_variants_meta":{"raw":{"variants":["Robust MDPs add an inner worst-case step to standard solving","Tutorial: robust MDPs keep value iteration with an inf inside","RMDPs generalize interval MDPs and keep policy iteration","Robust MDP solving: replace sum over successors by inf over uncertainty","Robust MDPs: a unifying model with convex uncertainty and fixed algorithms"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000775,"raw_usage":{"total_tokens":3381,"prompt_tokens":851,"completion_tokens":2530,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":467,"completion_tokens_details":{"reasoning_tokens":2435}},"tokens_in":467,"tokens_out":2530,"duration_ms":18195,"temperature":1.0,"reasoning_tokens":2435,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T18:30:43.585070+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Build a two-state RMDP where one transition has probability zero in one admissible transition function and positive probability in another, while the uncertainty set is still convex and (s,a)-rectangular. Running Equation (3) with the paper's preprocessing would classify that state inconsistently depending on which transition function is considered, making S∞ or S? ill-defined; observing that the value or the preprocessing changes discontinuously when the zero is changed to a small positive number shows the graph-preservation assumption is load-bearing and that the tutorial's claim is scoped to it.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines RMDPs with static and dynamic uncertainty semantics and robust dynamic programming, including the result that the two semantics coincide for (s,a)-rectangular reward maximization."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces interval MDPs and time-stationary versus time-varying uncertainty, providing the other foundational source of the robust Bellman equation."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the rectangularity taxonomy and the complexity and policy-class results that the survey reproduces in Table 1."},{"cited_title":"In: ICML","cited_arxiv_id":null,"evidence_quote":"Supplies fast Bellman updates for s-rectangular L1-robust MDPs, used in the survey's discussion of s-rectangular methods."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces a policy iteration algorithm for L1-robust MDPs, which the survey cites as evidence that robust policy iteration is often the preferred method."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the explicit sorting/bisection algorithm for solving the interval-MDP inner problem, which the survey presents as Algorithm 1."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Analyzes model-based interval estimation for MDPs and underlies the L1-MDP inner-problem algorithm the survey gives as Algorithm 2."},{"cited_title":"In: FSTTCS","cited_arxiv_id":null,"evidence_quote":"Defines multi-environment MDPs and their complexity results, used to illustrate discrete non-rectangular uncertainty."}],"review_version":1}