Paper deep dive
Adaptive Policy Portfolios for Robust Markov Decision Processes
Kasper Engelen, Sebastian Junges, Guillermo A. Pérez, Marnix Suilen
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%
Last extracted: 8/22/2026, 1:46:13 AM
Summary
This paper introduces adaptive policy portfolios for Robust Markov Decision Processes (RMDPs) to address the conservatism of single-policy robust optimization. It defines robust regret as a quality metric and analyzes the computational complexity of certifying and synthesizing these portfolios. The study proves that certifying a portfolio is ∀ℝ-complete and synthesizing one is ∃∀ℝ-complete, highlighting hardness sources like shared uncertain transitions and cycles. Finally, it proposes an offline construction method using discretization and clustering, paired with an online UCB selector.
Entities (6)
Relation Signals (5)
Portfolio Certification → hascomplexity → ∀ℝ-complete
confidence 95% · Certifying a given portfolio is ∀ℝ-complete already for deterministic portfolios in acyclic (s,a)-rectangular RMDPs.
Portfolio Synthesis → hascomplexity → ∀ℝ-complete
confidence 95% · Synthesizing a portfolio of unary-bounded size is ∃∀ℝ-complete for general rational polytopes.
Adaptive Policy Portfolio → uses → Robust Regret
confidence 95% · Robust regret is a natural measure of portfolio quality... We study adaptive policy portfolios... Synthesized by minimizing robust regret.
Ghavamzadeh et al. → studied → Robust Regret
confidence 90% · Related regret objectives were studied by Ghavamzadeh et al. (2016) with an emphasis on approximations and relaxations for safe policy improvement.
UCB → usedfor → Online Selection
confidence 90% · At runtime, UCB (8) selects among the portfolio members as observations accumulate.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Robust Markov decision processes optimize one policy against a set of plausible transition functions. This can be conservative when the unknown dynamics are fixed and become partially identifiable after deployment. We study adaptive policy portfolios: finite sets of memoryless randomized policies synthesized offline and paired with a lightweight online selector. Robust regret is a natural measure of portfolio quality: for each plausible environment, it measures the loss of the best portfolio member relative to the policy that would have been optimal had that environment been known. Related regret objectives were studied by Ghavamzadeh et al. (2016) with an emphasis on approximations and relaxations for safe policy improvement. We give a complexity-theoretic account of portfolio certification and synthesis. Certifying a given portfolio is $\forall\mathbb{R}$-complete already for deterministic portfolios in acyclic (s,a)-rectangular RMDPs. Synthesizing a portfolio of unary-bounded size is $\exists\forall\mathbb{R}$-complete for general rational polytopes, even with fixed discount and acyclic dynamics. The single-policy case is already hard, both combinatorially and algebraically. Finally, we present an offline portfolio construction that is amenable to runtime specialization.
Tags
Links
- Source: https://arxiv.org/abs/2608.17929v1
- Canonical: https://arxiv.org/abs/2608.17929v1
Trouble viewing inline? Open PDF directly →
Full Text
237,763 characters extracted from source content.
Expand or collapse full text
Adaptive Policy Portfolios for Robust Markov Decision Processes Kasper Engelen Sebastian Junges Guillermo A. Pérez Marnix Suilen Abstract Robust Markov decision processes optimize one policy against a set of plausible transition functions. This can be conservative when the unknown dynamics are fixed and become partially identifiable after deployment. We study adaptive policy portfolios: finite sets of memoryless randomized policies synthesized offline and paired with a lightweight online selector. Robust regret is a natural measure of portfolio quality: for each plausible environment, it measures the loss of the best portfolio member relative to the policy that would have been optimal had that environment been known. Related regret objectives were studied by Ghavamzadeh et al. (2016) with an emphasis on approximations and relaxations for safe policy improvement. We give a complexity-theoretic account of portfolio certification and synthesis. Certifying a given portfolio is ∀ℝ -complete already for deterministic portfolios in acyclic (s,a)(s,a)-rectangular RMDPs. Synthesizing a portfolio of unary-bounded size is ∃∀ℝ∃ -complete for general rational polytopes, even with fixed discount and acyclic dynamics. The single-policy case is already hard, both combinatorially and algebraically. Finally, we present an offline portfolio construction that is amenable to runtime specialization. 1 Introduction Markov decision processes (MDPs) are the standard formalism for sequential decision-making under uncertainty, but they require precise knowledge of transition probabilities. Robust MDPs (RMDPs, for short) (23) relax this requirement by optimizing against an uncertainty set of possible transition functions. A robust policy is optimized against the worst transition dynamics in that set. Consequently, robust policies can be overly conservative because their behavior is dominated by the hardest environments, even when those environments are unlikely or quickly ruled out by observation. Robust regret (2; 18) offers an alternative. Instead of maximizing value under the worst transition function, it minimizes the largest value shortfall relative to the policy that would have been optimal had the true transition function been known. This yields a policy with uniformly small relative loss. It still commits, however, to one policy for every possible transition function and cannot exploit evidence gathered online about which model governs the environment. We propose adaptive policy portfolios. Offline, we compute a set of policies tailored to different regions of the uncertainty set. Online, accumulated evidence is used to select among these already validated policies. The portfolio is synthesized by minimizing robust regret. We focus on portfolios of memoryless policies, the simplest practically interesting policies for sequential decision making. Figure 1: Portfolio regret in the actuator example. As a motivating example, consider an actuator whose true slip level is an unknown parameter p∈[0,1]p∈[0,1]. Viewed as a single-state RMDP, each action is a calibration c∈C=0,1/8,…,1c∈ C=\0, 18,…,1\, and the unknown p sets the success probability 1−(p−c)21-(p-c)^2 of reaching an absorbing success state. The regret of a calibration is its excess squared distance to p over the closest calibration in C. A single robust-regret policy chooses c=1/2c= 12 and has worst-case regret 1/4 14. The portfolio 0,1/2,1\0, 12,1\ reduces this to 1/16 116, while 0,1/4,1/2,3/4,1\0, 14, 12, 34,1\ reduces it to 1/64 164. Increasing the portfolio size provides a controlled form of adaptation while online selection remains over a finite set. Figure 1 plots these regret curves. Task Nonrect. uncertainty (s,a)(s,a)-rectangular uncertainty Hardness already holds for Certify one given policy ∀ℝ -complete coNP-hard and coSQRS-hard; in ∀ℝ deterministic policies; acyclic models whose uncertain choices are two-Dirac, for coNP Certify a given portfolio ∀ℝ -complete ∀ℝ -complete deterministic portfolios with acyclic graphs and two-successor choices Synthesize one randomized policy ∀ℝ -hard and in ∃∀ℝ∃ NP-hard, coNP-hard, and ± SQRS_±-hard; in ∃∀ℝ∃ two-Dirac models for the Boolean bounds Synthesize at most k policies ∃∀ℝ∃ -complete hard already for k=1k=1; exact complexity open regret threshold 22, fixed discount, acyclic dynamics, two-successor uncertain choices Table 1: Complexity of regret certification and synthesis. Certification is established by Theorems 1, 2, 4 and 3. Synthesis is established by Theorems 5, 6, 7, 8 and 9. In this work, we study the computational complexity of synthesizing minimal-regret policy portfolios and the certification and comparison subproblems that arise along the way. Table 1 summarizes our main results: the robust-regret problems are hard for different levels of the hierarchy of the theory of the reals (19). The coNP lower bound was stated by 11 under a policy restriction removed here. Our square-root-sum and theory-of-the-reals bounds are new, and neither the Boolean nor the square-root-sum bound is known to be comparable with the theory-of-the-reals bounds. This rules out efficient general-purpose algorithms under standard complexity assumptions. These worst-case bounds still leave room for the practical offline construction developed later. The lower bounds persist even under structural assumptions that usually simplify RMDPs. Rectangularity is the independence assumption that transition uncertainty at one state-action pair does not constrain uncertainty at another, and it commonly lowers complexity and underlies much of the RMDP literature (13; 23; 20). Here it does not rescue portfolio certification: although rectangularity removes the real quantifier alternation from comparison between two acyclic policies, the pointwise maximum over portfolio members restores it (Theorem 3). Consequently, checking a given portfolio is ∀ℝ -complete already for deterministic portfolios in acyclic (s,a)(s,a)-rectangular RMDPs. Choosing a portfolio under a unary size budget adds one existential real block and is ∃∀ℝ∃ -complete for general rational polytopic uncertainty. The reduction couples choices, so it does not establish ∃∀ℝ∃ -completeness under rectangular uncertainty (Theorem 9). Despite these worst-case lower bounds, we give a practical construction that discretizes the uncertainty into cells, computes a candidate policy for each cell, and evaluates every candidate against all cells. It then clusters the resulting regret profiles to the desired portfolio budget. At runtime, UCB (8) selects among the portfolio members as observations accumulate. Contributions. Our contributions are as follows. 1. We introduce adaptive policy portfolios as a finite and certifiable form of adaptation for RMDPs. 2. We prove the two exact portfolio classifications summarized in Table 1: given-portfolio certification is ∀ℝ -complete and bounded-portfolio synthesis is ∃∀ℝ∃ -complete (Theorems 3 and 9). 3. We identify the structural sources of hardness: uncertain transitions used by both policies yield Boolean hardness, their recurrence on cycles yields hardness from sums of square roots, and choosing a policy adds further Boolean and signed-square-root-sum hardness. 4. We present an offline portfolio construction that is amenable to runtime specialization. The main text gives the principal arguments. Complete proofs and supporting comparison results appear in the appendix. Related Work Several approaches reduce the conservativeness of worst-case robust policies by optimizing over less conservative uncertainty sets (23; 6). When multiple optimal robust policies exist, best-effort approaches can select among them without sacrificing worst-case value (1). A more adaptive response to fixed but initially unknown transition dynamics is provided by Bayes-adaptive MDPs (12), hidden-model MDPs (9), and hidden-parameter MDPs (10). These models plan over a belief on the unknown dynamics and update it as evidence accumulates. This formulation is expressive, but planning becomes intractable outside narrow special cases. Its belief representation can be continuous or high-dimensional, and online belief-space planning can itself be expensive. Adaptive policy portfolios occupy an intermediate position. Their expensive computation is performed offline, while online adaptation reduces to selecting among a fixed set of policies. Regret is natural in this setting because the portfolio should contain a policy that performs near-optimally for whichever environment turns out to be true (cf. 11). 2 Problem Statement For a finite set X, we write |X||X| for its cardinality, and (X)D(X) for the set of discrete probability distributions over X, i.e., functions μ:X→[0,1]μ X→[0,1] with ∑x∈Xμ(x)=1 _x∈ Xμ(x)=1. Vectors and matrices are boldface. For ∈ℝn x ^n, (i) x(i) denotes its i-th entry. Throughout, S and A denote finite sets of states and actions of a decision process, and we call a pair (s,a)∈S×A(s,a)∈ S× A a choice. We fix an arbitrary ordering of the triples (s,a,s′)∈S×A×S(s,a,s )∈ S× A× S, so that a vector ∈ℝS×A×S u ^S× A× S assigns a value (s,a,s′) u(s,a,s ) to each triple. We call u a transition vector if (s,a,⋅)∈(S) u(s,a,·) (S) for every choice (s,a)(s,a). Definition 1 (RMDP). A robust Markov decision process (RMDP) is a tuple (S,A,,R,sι,γ)(S,A,U,R,s_ ,γ), where R:S×A→ℝR S× A is the reward function, sι∈Ss_ ∈ S is the initial state, γ∈(0,1)γ∈(0,1) is a discount factor, and =∈ℝS×A×S∣≤U=\ u ^S× A× S F u≤ g\ is a convex polytope of transition vectors, for ∈ℝm×n F ^m× n, ∈ℝm g ^m (n=|S‖A‖S|n=|S||A||S|). The inequalities ≤ F u≤ g include the constraints defining a transition vector, so every ∈ u is a valid transition function. A policy maps paths to distributions over actions, π:(SA)∗S→(A)π (SA)^*S (A). A memoryless randomized policy π:S→(A)π S (A) depends only on the current state. The set of such policies is ΠMR ^MR. A memoryless deterministic policy π:S→Aπ S→ A further selects a single action per state. The set of such policies is ΠMD⊆ΠMR ^MD ^MR. Unless stated otherwise, candidate policies range over ΠMR ^MR. Each ∈ u induces a classical MDP M=(S,A,P,R,sι,γ)M_ u=(S,A,P_ u,R,s_ ,γ) with P(s,a)(s′)=(s,a,s′)P_ u(s,a)(s )= u(s,a,s ). For a policy π, its value Vπ:S→ℝV^π_ u S in M_ u is the expected discounted cumulative reward, Vπ(s)=π[∑t=0∞γtR(st,at)|s0=s],V^π_ u(s)=E_π [ _t=0^∞γ^tR(s_t,a_t) |s_0=s ], and V∗(s)=supπVπ(s)V^*_ u(s)= _πV^π_ u(s) is the optimal value. This supremum is attained by a policy in ΠMD ^MD and V∗V^*_ u is computable in polynomial time for fixed u (17). Types of uncertainty. By default, U places no further structure on how uncertainty interacts across choices. We call this the general (non-rectangular, convex-polytopic) case. The special case where U decomposes into independent per-choice uncertainty sets is (s,a)(s,a)-rectangular: =×(s,a)∈S×A(s,a),(s,a)⊆ℝs×a×S.U= _(s,a)∈ S× AU_(s,a), _(s,a) ^\s\×\a\× S. We call (s,a)U_(s,a) the uncertainty set of choice (s,a)(s,a), and the choice uncertain if (s,a)U_(s,a) is not a singleton. Intuitively, (s,a)(s,a)-rectangularity is an independence assumption across choices. The general case allows U to couple choices, whereas (s,a)(s,a)-rectangularity prohibits this. Subclasses of RMDPs. An uncertain choice is two-successor if every distribution in its uncertainty set is supported on the same two states, and two-Dirac if that set is the line segment between two Dirac distributions. An RMDP has either property when all its uncertain choices do. An RMDP is acyclic when its possible-transition graph has no directed cycle except self-loops at absorbing final states. A policy graph is acyclic under the analogous restriction to choices used by that policy. Constructions that describe only their intended choices are completed on every other state-action pair by the ruinous-sink convention of Section A.1. Robust Value & Regret. For a policy π, its robust value is Vπ,rob(s)=inf∈Vπ(s),V^π,rob(s)= _ u V_ u^π(s), the worst-case value π can guarantee against any realization in U. The robust optimal value is Vrob(s)=supπVπ,rob(s)V^rob(s)= _πV^π,rob(s), and a policy attaining it is robust optimal. Robust value compares policies in absolute terms, but it does not distinguish a policy performing poorly from a realization that is simply hard for every policy: even the best policy for a fixed u may attain a low value there. We therefore turn to a comparative notion, measuring a policy’s shortfall against the best policy for each particular realization, rather than its raw worst-case value. That is, for π∈ΠMRπ∈ ^MR, its robust regret (at sιs_ ) is Rreg(π)=sup∈(V∗(sι)−Vπ(sι)),Rreg(π)= _ u (V_ u^*(s_ )-V_ u^π(s_ ) ), the largest shortfall of π from the policy optimal at u, over every realization of the uncertainty. We call the choice of realization u nature’s move. Definition 2 (Adaptive policy portfolio). An adaptive policy portfolio is a finite set Π⊆ΠMR ^MR of candidate policies synthesized offline and paired with a runtime mechanism that selects among its members as evidence accumulates. Robust regret lifts to portfolios by comparing against the best member for that realization: Rreg(Π)=sup∈(V∗(sι)−maxπ∈ΠVπ(sι)).Rreg( )= _ u (V_ u^*(s_ )- _π∈ V_ u^π(s_ ) ). (1) This is an offline coverage guarantee: it idealizes away the cost of identifying the best member and assumes that member is selected. The online identification cost is evaluated separately in Section 4. This quantity cannot in general be recovered from the single-policy regret values Rreg(π):π∈Π\Rreg(π):π∈ \. Portfolio regret evaluates all members under the same realization before taking the worst case, whereas each singleton regret has already taken its own supremum. Note that the bound Rreg(Π)≤minπ∈ΠRreg(π)Rreg( )≤ _π∈ Rreg(π) follows. We seek the best guarantee achievable by a portfolio of bounded size k≥1k≥ 1: ρk=infΠ⊆ΠMR:|Π|≤kRreg(Π). _k= _ ^MR:| |≤ kRreg( ). Note ρ1=infπ∈ΠMRRreg(π) _1= _π∈ ^MRRreg(π): minimal single-policy regret is the k=1k=1 case of minimal portfolio regret. 3 Computational Complexity We first recall the required classes, then turn to the certification and synthesis of portfolios. We note that the results yield a rich landscape, but all studied problems lie in PSPACE. 3.1 Complexity Preliminaries We assume basic familiarity with standard complexity classes such as NP, coNP, and PSPACE (16; 4). Input conventions. The rewards, γ, threshold t, polytope data , F, g, and policy matrices in ℚS×AQ^S× A are binary-encoded rationals. The portfolio budget k is encoded in unary. Theory of the reals. We use the first-order theory of the reals over (ℝ,0,1,+,⋅,<)(R,0,1,+,·,<). In this logic, we can ask whether a system of polynomial equations and inequalities has a real solution, or holds for every real assignment. We consider three fragments, given a quantifier-free formula φ : • existential sentences ∃x1,…,xnφ(x1,…,xn)∃ x_1,…,x_n\ (x_1,…,x_n); • universal sentences ∀x1,…,xnφ(x1,…,xn)∀ x_1,…,x_n\ (x_1,…,x_n); • existential-universal sentences ∃x1,…,xn∀y1,…,ymφ(x1,…,xn,y1,…,ym)∃ x_1,…,x_n\ ∀ y_1,…,y_m\ (x_1,…,x_n,y_1,…,y_m). The truth problem of each fragment defines a complexity class, denoted ∃ℝ , ∀ℝ , and ∃∀ℝ∃ respectively (19). These classes sit between NP and PSPACE (7; 5), and ∀ℝ=∃ℝ = co and ∃ℝ=∀ℝ = co . Square-root-sum. We also consider variants of the well-known square-root-sum ( SQRS) decision problem and their associated complexity classes. For the variants below, assume finite lists of positive integers a1,…,ama_1,…,a_m and b1,…,bnb_1,…,b_n, and an integer k, all encoded in binary. • SQRS. Decide whether ∑i=1mai≤k _i=1^m a_i≤ k. coSQRS is the complement class. • ± SQRS_±. Given an operator ⋈∈≤,≥ ∈\≤,≥\, decide whether ∑i=1mai⋈∑j=1nbj _i=1^m a_i _j=1^n b_j. Both SQRS and coSQRS reduce to ± SQRS_±: SQRS uses =(k2) b=(k^2); for coSQRS, test equality in polynomial time (∑iai∈ℚ _i a_i iff every aia_i is a perfect square), then use ≥. Polynomial hierarchy and common upper bound. The polynomial hierarchy PH is the union of the classes obtained by alternating polynomially bounded existential and universal Boolean quantifiers in front of a polynomial-time predicate. In particular, Σ2p _2^p begins with an existential block followed by a universal block (16; 4). Every level of PH, every fixed level of the real hierarchy considered above, and ± SQRS_± lie in PSPACE (7; 3). Thus all classes used in this paper share a PSPACE upper bound. 3.2 Policy and Portfolio Comparison Policy comparison. We call the following problem policy comparison: given two policies π1,π2∈ΠMR _1, _2∈ ^MR and a threshold t, decide whether Δ(π1,π2)=sup∈(Vπ1(sι)−Vπ2(sι))≤t. _U( _1, _2)= _ u (V_ u _1(s_ )-V_ u _2(s_ ) )≤ t. Policy comparison is tractable when π1 _1 and π2 _2 share no uncertain choice (Section B.1): in this case the robust value of each policy can be evaluated individually and this is known to be feasible in polynomial time (13; 21). Otherwise, it is coNP-hard11 1 This was stated by 11 but proved only under a restrictive constraint imposed on the policies. We give an unconditional proof of the fact in Section B.2. already in acyclic (s,a)(s,a)-rectangular RMDPs, and coNP-complete when no uncertain choice used by both policies lies on a cycle of either policy graph (Sections B.2 and B.3). In this cycle-free regime the supremum defining Δ _U is attained at a rational vertex of the uncertainty polytope, so a witness realization can be written down exactly. Sketch of coNP-hardness. Reduce from UNSATUNSAT. For a 3-CNF formula φ , the RMDP keeps two local bits per literal occurrence, one certifying each value for the bits, and lets nature fix them independently through separate two-Dirac choices. Both policies read the same copies but ask different questions of them. The clause policy πC _C accepts when every clause has a locally true literal. The consistency policy πK _K uniformly selects a variable and accepts when all its copies agree with one global value. Thus πC _C contributes either 00 or 11 to Δ _U, while πK _K contributes the fraction of variables whose audits pass. Nature attains 22 exactly when φ is satisfiable; otherwise the difference is at most 2−1/n2-1/n. ∎ Even in the rectangular case, optimality at the vertices no longer holds once a shared choice lies on a cycle: the supremum can then be attained in the interior, at an irrational value, a sum of square roots, which is exactly the phenomenon coSQRS-hardness captures (see Section B.4 and the example below). Membership in ∀ℝ follows from a known adaptation of the Bellman equations for the value functions to the parametric setting (14). Example 1. Consider this RMDP with discount γ=1/2γ=1/2.sιs_ ccggaaxx1−x1-xπ1(c) _1(c)π2(c) _2(c)R=1R=1 Fix the realization ∈ u corresponding to x. The value of g is 22. Under π1 _1, reaching c gives one zero-reward step back to sιs_ . Hence Vπ1(sι)=12(x12Vπ1(sι)+(1−x)2),V_ u _1(s_ )= 12 (x 12V_ u _1(s_ )+(1-x)2 ), hence Vπ1(sι)=1−x1−x/4.V_ u _1(s_ )= 1-x1-x/4. Under π2 _2, the state c has value zero, so Vπ2(sι)=1−x.V_ u _2(s_ )=1-x. Thus Vπ1(sι)−Vπ2(sι)=x(1−x)4−x.V_ u _1(s_ )-V_ u _2(s_ )= x(1-x)4-x. This difference is zero at x=0x=0 and x=1x=1, but positive between them. Its maximum over [0,1][0,1] is attained at x∗=4−23.x^*=4-2 3. Substitution gives Δ(π1,π2)=7−43. _U( _1, _2)=7-4 3. The square root appears because π1 _1 can revisit the same uncertain choice, so its value is a rational function of x whose maximum lies inside the interval. Nonrectangularity makes things harder. Without rectangularity, coupling lets one parameter recur at different choices. Then comparison is even ∀ℝ -complete (Section B.5). To obtain hardness, we encode polynomial nonpositivity and build an RMDP whose value at each realization equals a given polynomial. A monomial pi1⋯pidp_i_1·s p_i_d becomes a chain of d uncertain choices that survives with probability equal to the monomial. A certain splitter is a state whose sole action draws among these monomial branches with fixed rational probabilities. On each branch, a terminal payoff cancels its certain splitter probability and discount, so the branch contributes its signed monomial. Comparing this polynomial evaluator with a policy that goes to a zero-reward sink decides whether a given polynomial f is nonpositive at every point in the uncertainty domain (Section B.5). Portfolio comparison. Portfolio comparison remains ∀ℝ -complete even under (s,a)(s,a)-rectangular uncertainty. The pointwise maximum maxπ∈ΠVπ _π∈ V_ u^π over the explicit portfolio, rather than parameter reuse or recurrence, supplies the real quantifier alternation (Section B.6). 3.3 Regret Certification Certification asks whether a given policy or portfolio meets a target regret value. Problem 1 (Robust-regret certification). Given an RMDP, a policy π∈ΠMRπ∈ ^MR, and a threshold t∈ℚt , decide whether Rreg(π)≤tRreg(π)≤ t. Problem 2 (Portfolio-regret certification). Given an RMDP, a portfolio Π⊆ΠMR ^MR, and a threshold t∈ℚt , decide whether Rreg(Π)≤tRreg( )≤ t. We show ∀ℝ -membership for both problems: Theorem 1 (Membership). Regret certification is in ∀ℝ . The idea is to universally quantify the realization, an optimal policy at that realization, and one Bellman system per portfolio member, comparing the optimal value against the best of them. See Appendix C. From comparison to regret. The obstacle to transferring comparison lower bounds is that it fixes both policies. Regret measures a candidate against the best policy at the fixed realization. For a policy π and portfolio Π , write Δ(π,Π)=sup∈(Vπ(sι)−maxπ′∈ΠVπ′(sι)). _U(π, )= _ u (V^π_ u(s_ )- _π ∈ V^π _ u(s_ ) ). For a source RMDP N and reference policy π0 _0, N^=Lift(N,π0) N=Lift(N, _0) makes π0 _0 optimal at every realization (Appendix D). Each source choice becomes a tag state that selects an action and a selector state that carries its transition uncertainty. For a source portfolio Π , let Π be its image under LiftLift. Certification in N N then becomes comparison against π0 _0, up to a known constant Λ : Rreg(Π^)=Λ+Δ(π0,Π).Rreg( )= + _U( _0, ). Lower bounds. The following lower bounds combine comparison hardness with the lift construction. Theorem 2. Given-policy robust regret is coNP-hard and coSQRS-hard under (s,a)(s,a)-rectangular uncertainty. coNP-hardness already holds when every uncertain choice is two-Dirac and the only other stochastic rows are certain uniform splitters. Proof sketch. Apply LiftLift to Cmp(φ)Cmp( ) and to the shared-cycle square-root-sum construction, respectively. The transformation converts each comparison threshold by one known additive constant. See Section E.1. ∎ The pointwise maximum over members makes portfolio comparison ∀ℝ -hard even when rectangularity removes the corresponding alternation for one acyclic policy pair. The transformation LiftLift transfers this hardness to certification: Theorem 3. Portfolio-regret certification is ∀ℝ -hard, already for deterministic portfolios and acyclic (s,a)(s,a)-rectangular RMDPs with two-successor uncertain choices. Proof sketch. Apply LiftLift to the portfolio-comparison construction in Section 3.2. See Section E.2. ∎ Theorem 4. Given-policy robust regret is ∀ℝ -complete under general rational polytopic uncertainty, even for deterministic policies. Proof sketch. Membership is the singleton-portfolio case of Theorem 1. For hardness, reduce from the ∀ℝ -complete problem of deciding whether a polynomial is nonpositive throughout a bounded domain, introduced in Section 3.2. At each realization, we first force the given policy to take a zero-valued branch, while an optimal policy at that realization may choose either that branch or one evaluating a polynomial function. Up to the fixed initial discount, the regret is therefore the positive part of the polynomial’s value. Consequently, the policy has regret at most zero exactly when the polynomial is nonpositive. See Section E.3. ∎ 3.4 Minimal Robust Regret & Bounded Synthesis Certification fixes the candidate set whereas in the minimization and synthesis problems we need to choose it. Problem 3 (Minimal robust regret). Given an RMDP and a threshold t∈ℚt , decide whether infπ∈ΠMRRreg(π)≤t _π∈ ^MRRreg(π)≤ t. Problem 4 (Bounded portfolio synthesis). Given an RMDP, a budget k encoded in unary, and a threshold t∈ℚt , decide whether ρk≤t _k≤ t. Portfolio regret is monotone under inclusion, and Rreg(π)=Rreg(π)Rreg(\π\)=Rreg(π). Thus minimal robust regret is the special case of bounded portfolio synthesis with k=1k=1. Theorem 5 (Membership). Minimal robust regret and bounded portfolio synthesis belong to ∃∀ℝ∃ . For single-policy minimization, we existentially quantify the candidate policy table. For bounded synthesis, we quantify the k portfolio tables. We then universally quantify the realization, an optimal policy at that realization, and the corresponding Bellman systems. Since k is encoded in unary, both formulas have polynomial size. See Appendix C. Restricting the synthesized policy. Synthesis chooses its candidate, so a reduction must keep the synthesized policy in the role assigned by its encoding, either naming a valuation or following the consistency policy, rather than letting it escape to an unintended lower-regret policy. The policy-restriction transformation RestrictRestrict makes disallowed actions so costly that minimizing over all policies comes within any rational ε>0 >0 of minimizing over the allowed policies (Appendix F). Combinatorial hardness under rectangular uncertainty. Theorem 6. Minimal robust regret is NP-hard and coNP-hard on (s,a)(s,a)-rectangular RMDPs in which every uncertain choice is two-Dirac and the only other stochastic rows are certain uniform splitters. Proof sketch. For coNP-hardness, lift Cmp(φ)Cmp( ) with the clause policy as reference and restrict the synthesized policy to the lifted consistency policy. The resulting threshold separates satisfiable from unsatisfiable formulas. For NP-hardness, the fixed reference finds a falsified clause and the synthesized policy names a valuation whose local copies nature can audit. The most probable randomized choices still name a valuation with probability at least 2−n2^-n, which supplies the required gap. The transformations LiftLift and RestrictRestrict preserve both gaps. Both reductions retain independent two-Dirac choices. See Appendix F. ∎ Square-root-sum hardness under rectangular uncertainty. Beyond the combinatorial hardness, irrational regret values let us encode problems with signed sums of roots. Theorem 7. Minimal robust regret is ± SQRS_±-hard under (s,a)(s,a)-rectangular uncertainty. Proof sketch. The reduction uses local RMDPs in which the policy chooses a mixing probability x between two actions. For suitable rational A,B,q>0A,B,q>0, its regret is maxA(1−x)1−(1−q)x,Bxq+(1−q)x. \ A(1-x)1-(1-q)x, Bxq+(1-q)x \. As x increases the first term decreases while the second increases, so their maximum is minimized at an interior balance point, producing a square root. Reward signs realize the two forms Db−bD_b- b and b−Cb b-C_b. A certain uniform splitter adds the local minima, which realizes a signed sum. See Appendix H. ∎ Hardness under general polytopic uncertainty. Under general rational polytopic uncertainty, policy comparison reduces to single-policy regret minimization. Theorem 8. Single-policy minimal robust regret is ∀ℝ -hard for arbitrary rational polytopic uncertainty. Proof sketch. Reduce from the ∀ℝ -complete general-polytope comparison problem described in Section 3.2. The construction leaves the synthesized policy one decision: a mixing probability x between forced copies of the two source policies. Two absorbing states of values ±Z± Z anchor the branches so that only this mixing probability matters. They make its regret max(1−x)D,xE \(1-x)D,xE\, where E is a fixed positive rational and D is an affine, strictly increasing function of the source comparison value Δ . The minimizing policy balances the two terms, giving DE/(D+E)DE/(D+E), again strictly increasing in Δ , so the comparison threshold transfers by a rational transformation. See Appendix I. ∎ Together with the upper bound above, this places single-policy minimal robust regret between ∀ℝ -hardness and ∃∀ℝ∃ -membership under general rational polytopic uncertainty. The current bounds do not establish completeness. Restricting the search to memoryless deterministic policies on acyclic (s,a)(s,a)-rectangular RMDPs makes minimal robust regret Σ2p _2^p-complete (Appendix G). This is a different problem from 3, which minimizes over ΠMR ^MR, and neither classification implies the other. In particular, the Σ2p _2^p-hardness construction leaves the synthesized policy a free choice at every existential variable state, so a randomized policy may mix there and undercut every deterministic candidate. The NP-hardness of Theorem 6 thus rests on a separate construction, whose 2−n2^-n gap randomization cannot close. Bounded portfolio synthesis. For bounded portfolios, the general upper bound is tight. Theorem 9. Bounded portfolio synthesis is ∃∀ℝ∃ -complete under general rational polytopic uncertainty, with k encoded in unary. Hardness holds already for regret threshold two, the fixed discount γ=12γ= 12, RMDPs acyclic apart from absorbing final states, and uncertain choices with two successors. Proof sketch. Membership is the encoding above. For hardness, normalize ∃x∀y:F(x,y)≥0∃ x\,∀ y:F(x,y)≥ 0 into tests gi(x,η)g_i(x,η) affine in x, and use one portfolio member per test. A case distribution lets nature audit roles, witness agreement, and tests through fixed-reward polynomial evaluators. The regret threshold is met exactly when some x passes every test for every η. See Appendix J. ∎ The equality ties couple choices at different state-action pairs, so the reduction does not settle the rectangular case. Under rectangular uncertainty, bounded synthesis is hard already for the fixed budget k=1k=1. 4 Portfolio Construction and Evaluation We show that even a simple offline pipeline yields portfolios with substantially lower empirical regret, despite the intractability of portfolio construction. To this end, we implemented the three-phase prototype summarized in Algorithm 1. Two research questions guide the experiments: whether portfolios reduce empirical robust regret as the budget grows (RQ1), and whether the best member can be identified online in a fixed but unknown environment (RQ2). All details on the benchmarks, experiment protocol, and results can be found in Appendix K. Input: RMDP M, parameter box D, portfolio size K, and evaluation seeds Construct: split D into cells and compute an optimal midpoint policy for each cell; Robustly evaluate every candidate on every cell, giving one regret profile per policy; Cluster the profiles and select the policy nearest each of the K centers; Evaluate: for 3 seeded samples of D, estimate min regret in portfolio, maximized over samples; Deploy: treat members as bandit arms and run UCB in each fixed sampled environment; Algorithm 1 Experimental pipeline Benchmarks. We introduce two new benchmarks: datacenter climate control and UAV control. The datacenter benchmark contains two uncertain parameters, cooling effectiveness and ambient pressure, both ranging over a box domain. The rewards combine a per-action energy cost with penalties activating near the temperature, humidity, and queue ceilings, giving Vmax=2080V_max=2080. The UAV benchmark is a planning problem through a three-dimensional grid under uncertain wind intensity p and actuator-drop probability q, again over a box domain. Reaching the goal is the only rewarded event; thus, the value is the discounted landing probability, and Vmax=100V_max=100. We consider three different instances of this benchmark, uav-small, uav-medium, and uav-large. Every grid position offers seven actions, so even uav-small admits 7957^95 memoryless deterministic policies, ruling out exhaustive search. Portfolio construction. The benchmarks are nonrectangular RMDPs whose transition probabilities are affine in a parameter vector ranging over a box D. Hence, every valuation θ∈Dθ∈ D induces a realization ∈ u . Discretizing each parameter into 1010 bins gives a set C of 100100 cells c for our two-parameter benchmarks, and the optimal policy at each cell midpoint mid(c)mid(c) becomes a candidate π∈Π()π∈ (C) in the candidate set. Robust policy evaluation then assigns each candidate π a midpoint-based approximate regret vector LπL_π with one entry per cell: Lπ,c=Vmid(c)∗(sι)−infθ∈cVθπ(sι).L_π,c=V^*_mid(c)(s_ )- _θ∈ cV^π_θ(s_ ). We then use K-means over these vectors to select the policy nearest each center, resulting in a set ΠK⊆Π() _K (C) of policies. Clustering is a computationally cheap approximation for obtaining portfolios of deterministic policies. Portfolio evaluation. A uniform parameter sample D^⊂D D⊂ D with |D^|=1000 D =1000 is drawn to estimate portfolio regret by Rreg^D^(Π)=maxθ∈D^(Vθ∗(sι)−maxπ∈ΠVθπ(sι)), Rreg_ D( )= _θ∈ D (V^*_θ(s_ )- _π∈ V^π_θ(s_ ) ), which measures coverage without charging for online identification and under-approximates the true regret, since it maximizes over finitely many samples (cf. Equation 1). For deployment, UCB (8) treats portfolio members as bandit arms whose returns come from fixed-length trajectories in a fixed but unknown environment. We use it with error ε=0.001 =0.001 (as a fraction of the return bound), confidence δ=0.1δ=0.1, and empirical-Bernstein bounds (15) to speed up convergence. For the UCB-based deployment, we uniformly draw 3030 valuations and run UCB once per valuation with a trajectory of length H=100H=100 sampled on each iteration. We plot, per iteration, the fraction of UCB runs where the final recommended arm is the best portfolio member and the difference between the best and recommended policy, normalized between 00 (best) and 11 (worst). Setup. The Python prototype uses Stormvogel (22), robust value iteration (13), and scikit-learn K-means. Experiments were run on a 2022 MacBook Pro M1 under macOS Tahoe 26.5.2, using 6 threads for robust policy evaluation, regret approximation, and UCB evaluation. All experiments are done for three different seeds. For the plots in Figure 2, we merged all 9090 samples across the three seeds. K UAV-S (98) UAV-M (358) UAV-L (1813) datacenter (330) 1 0.053 0.091 0.126 14.28 2 0.032 0.019 0.017 3.86 3 0.018 0.010 0.016 2.82 5 0.002 0.003 0.015 2.79 7 0.002 0.003 0.008 1.79 10 0.002 0.003 0.003 0.80 Construction time 43.8s 384.1s 2357.8s 2732.7s Table 2: Empirical robust regret, averaged over three seeds. Parentheses give the number of states. Bottom row indicates wall-clock time. RQ1: Portfolios reduce robust regret. Table 2 shows empirical robust regret decreasing with K on every benchmark, with the largest single drop at K=2K=2, and further gains as K increases. The K=1K=1 row is a singleton rather than an adaptive portfolio. Seed-level values and K-means inertia appear in Table 5 in Appendix K. For reference, the mini-max regret minπ∈Π()maxc∈Lπ,c _π∈ (C) _c L_π,c is 0.0390.039, 0.1180.118, 0.1460.146, and 41.50241.502 by column. Policy portfolios beat it for all K on the three largest benchmarks. (a) Runs with the correct arm recommended. (b) Regret of recommended arm. Figure 2: Reported UCB deployment results on the datacenter across all tested values of K. RQ2: Portfolio members can be identified online. At each iteration of the UCB algorithm, we measure which arm was pulled (maximal UCB) and which arm was recommended (maximal LCB). Figure 2(a) gives the fraction of UCB runs recommending the best portfolio policy at each iteration. Identification slows as the portfolio grows: after 10410^4 iterations, about half the runs recover the best member at K=10K=10. Since this ignores how well the remaining members perform, Figure 2(b) instead reports the regret of the recommended policy relative to the best portfolio policy, and there the value difference after 10410^4 iterations is minimal. 5 Conclusion Adaptive policy portfolios sit between committing to a single robust policy and planning over a full belief state, offering finite and certifiable adaptation. Certification is ∀ℝ -complete and bounded synthesis ∃∀ℝ∃ -complete under rational polytopic uncertainty; certification stays hard under rectangularity, since the pointwise maximum over members reintroduces the quantifier alternation that rectangularity eliminates. Our prototype empirically shows portfolios whose regret falls sharply with the first few members, at an identification cost that grows with K. Bounded synthesis under rectangular uncertainty, and the gap between ∀ℝ -hardness and ∃∀ℝ∃ -membership for single-policy minimal robust regret, remain open. References Abate et al. (2026) A. Abate, T. Badings, G. D. Giacomo, and F. Fabiano Best-effort policies for robust markov decision processes. In AAAI, p. 36120–36128. Cited by: §1. Ahmed et al. (2013) A. Ahmed, P. Varakantham, Y. Adulyasak, and P. Jaillet Regret based robust solutions for uncertain markov decision processes. In NIPS, p. 881–889. Cited by: §1. Allender et al. (2009) E. Allender, P. Bürgisser, J. Kjeldgaard-Pedersen, and P. B. Miltersen On the complexity of numerical analysis. SIAM J. Comput. 38 (5), p. 1987–2006. Cited by: §3.1. Arora and Barak (2009) S. Arora and B. Barak Computational complexity - A modern approach. Cambridge University Press. Cited by: §3.1, §3.1. Basu et al. (2006) S. Basu, R. Pollack, and M. Roy Algorithms in real algebraic geometry. Springer. Cited by: §3.1. Benyamine et al. (2026) A. Benyamine, J. Grand-Clément, M. Petrik, M. I. Jordan, and A. Durmus Dynamic programming for epistemic uncertainty in markov decision processes. CoRR abs/2602.03381. Cited by: §1. Canny (1988) J. F. Canny Some algebraic and geometric computations in PSPACE. In STOC, p. 460–467. Cited by: §3.1, §3.1. Cesa-Bianchi and Lugosi (2006) N. Cesa-Bianchi and G. Lugosi Prediction, learning, and games. Cambridge University Press. External Links: Link, Document, ISBN 978-0-521-84108-5 Cited by: §K.4, §1, §4. Chades et al. (2012) I. Chades, J. Carwardine, T. G. Martin, S. Nicol, R. Sabbadin, and O. Buffet MOMDPs: A solution for modelling adaptive management problems. In AAAI, p. 267–273. Cited by: §1. Doshi-Velez and Konidaris (2016) F. Doshi-Velez and G. D. Konidaris Hidden parameter markov decision processes: A semiparametric regression approach for discovering latent task parametrizations. In IJCAI, p. 1432–1440. Cited by: §1. Ghavamzadeh et al. (2016) M. Ghavamzadeh, M. Petrik, and Y. Chow Safe policy improvement by minimizing robust baseline regret. In NIPS, p. 2298–2306. Cited by: §1, §1, footnote 1. Guez et al. (2012) A. Guez, D. Silver, and P. Dayan Efficient bayes-adaptive reinforcement learning using sample-based search. In NIPS, p. 1034–1042. Cited by: §1. Iyengar (2005) G. N. Iyengar Robust dynamic programming. Math. Oper. Res. 30 (2), p. 257–280. Cited by: §K.1, §B.1, §1, §3.2, §4. Junges et al. (2021) S. Junges, J. Katoen, G. A. Pérez, and T. Winkler The complexity of reachability in parametric markov decision processes. J. Comput. Syst. Sci. 119, p. 183–210. Cited by: §3.2. Mnih et al. (2008) V. Mnih, C. Szepesvári, and J. Audibert Empirical bernstein stopping. In Proceedings of the 25th International Conference on Machine Learning, ICML ’08, New York, NY, USA, p. 672–679. External Links: ISBN 9781605582054, Link, Document Cited by: §K.4, §4. Papadimitriou (1994) C. H. Papadimitriou Computational complexity. Addison-Wesley. Cited by: §G.2, §3.1, §3.1. Puterman (1994) M. L. Puterman Markov decision processes: discrete stochastic dynamic programming. Wiley Series in Probability and Statistics, Wiley. Cited by: §2. Rigter et al. (2021) M. Rigter, B. Lacerda, and N. Hawes Minimax regret optimisation for robust planning in uncertain markov decision processes. In AAAI, p. 11930–11938. Cited by: §1. Schaefer and Stefankovic (2024) M. Schaefer and D. Stefankovic Beyond the existential theory of the reals. Theory Comput. Syst. 68 (2), p. 195–226. Cited by: §A.2, §B.5, §B.6, §1, §3.1. Suilen et al. (2024) M. Suilen, T. Badings, E. M. Bovy, D. Parker, and N. Jansen Robust markov decision processes: A place where AI and formal methods meet. In Principles of Verification (3), Lecture Notes in Computer Science, Vol. 15262, p. 126–154. Cited by: §1. Suilen and Pérez (2026) M. Suilen and G. A. Pérez On the complexity of robust markov decision processes and bisimulation metrics. In CONCUR, Note: To appear; arXiv:2604.26748 Cited by: §B.1, §3.2. Volk et al. (2026) M. Volk, L. Heck, S. Junges, J. Katoen, and T. Quatmann Probabilistic model checking taken by Storm: a tutorial on the probabilistic model checker Storm. In FM, Lecture Notes in Computer Science, Vol. 16557, p. 524–549. External Links: Document Cited by: §K.2, §4. Wiesemann et al. (2013) W. Wiesemann, D. Kuhn, and B. Rustem Robust Markov decision processes. Math. Oper. Res. 38 (1), p. 153–183. Cited by: §1, §1, §1. Appendix Contents 1 Introduction 2 Problem Statement 3 Computational Complexity 4 Portfolio Construction and Evaluation 5 Conclusion References A Conventions and primitives B On Policy and Portfolio Comparison C Proofs of and : Membership for Certification and Synthesis D Exact Transfer from Policy Comparison to Robust Regret E Proofs of , and : Transferring Comparison Bounds to Certification F Proof of : Combinatorial Minimal-Regret Hardness G Deterministic Minimal-Regret Complexity H Proof of : Signed Square-Root-Sum Hardness I Proof of : General-Polytope Minimal-Regret Hardness J Proof of : Bounded Portfolio Synthesis K Experimental setup L Experimental data Appendix A Conventions and primitives This appendix collects the conventions and building blocks that the later reductions share. Three groups follow. First, two numerical conventions: a discount γ0 _0 chosen so that the comparison-to-regret lift composes exactly, and one inequality about it that the normalized square-root gadget needs. Second, reduction primitives: how a state is given a prescribed value, how uncertainty enters a single choice, the two-Dirac gadgets by which nature encodes a Boolean assignment and a verifier reads it back, and ruinous-sink completion, which makes every choice we did not describe so costly that no policy gains by taking it. Third, encodings: a degree-four normal form that turns a polynomial constraint into small residuals, and the Bellman formulas behind the membership proofs. A reader may skip ahead and return here when a later construction cites one of these by name. We first fix two conventions used throughout the appendix. Set β=1920,γ0=β2=361400.β= 1920, _0=β^2= 361400. The identity β2=γ0β^2= _0 is needed by the exact comparison-to-regret lift, while (1+γ0+γ021+γ0)2>2 ( 1+ _0+ _0^21+ _0 )^2>2 is the numerical inequality used by the normalized square-root gadget. All appendix constructions use γ0 _0 unless stated otherwise. The bounded-synthesis reduction uses γ=12γ= 12 because it does not invoke the lift and hence does not require β2=γ0β^2= _0. A.1 Reduction primitives A state is an absorbing final when every described action has a Dirac self-loop. A terminal with payoff c is an absorbing final whose described action has reward (1−γ)c(1-γ)c, so its value is exactly c. Every action not separately described at such a terminal is assigned the same reward and Dirac self-loop. Reaching such a terminal after d transitions with probability w contributes wγdcwγ^dc to the value at the initial state. For a choice (s,a)(s,a), call the distribution (s,a,⋅) u(s,a,·) its row; the choice is uncertain exactly when its row is not fixed. A selector is a state whose described action has a row carrying one uncertainty coordinate. A splitter is a state whose described action has a fixed row, independent of both the realization and the policy; such a row is certain. A splitter is uniform when its row is uniform over its successors. We reserve ⊥ for an absorbing zero-reward sink, that is, the terminal with payoff zero, and ⊥r _ r for a ruinous sink. Definition 3 (Local-bit verifier primitives). For an occurrence o and Boolean value c, a local-bit selector qo,cq_o,c has outcomes qo,c0,qo,c1q_o,c^0,q_o,c^1 and row (1−p)δqo,c0+pδqo,c1:p∈[0,1].\(1-p) _q_o,c^0+p _q_o,c^1:p∈[0,1]\. (2) Its vertices encode the bit bo,c=p∈0,1b_o,c=p∈\0,1\. A pair test for an occurrence with designated satisfying value val(o)val(o) reads qo,val(o)q_o,val(o) and then qo,1−val(o)q_o,1-val(o). Outcomes (1,0)(1,0) certify local truth and (0,1)(0,1) certify local falsity. An audit committed to value c visits qo,cq_o,c for the relevant occurrences in a fixed order, advancing on outcome one and rejecting on outcome zero. Lemma 10 (Acceptance-difference verifier). Suppose reference and candidate verifier paths are padded to depth H, all nonaccepting payoffs are zero, and their accepting terminals have payoffs γ−Hγ^-H and −γ−H-γ^-H. Then their value difference is the sum of their acceptance probabilities. Proof. Every accepting run contributes γHγ−H=1γ^Hγ^-H=1 to the corresponding signed value, while every rejecting run contributes zero. ∎ A construction’s ruinous-sink completion adds a fresh absorbing state ⊥r _ r and a rational Z>0Z>0. Every action at ⊥r _ r has reward −(1−γ)Z-(1-γ)Z and the singleton row δ⊥r\ _ _ r\, so V(⊥r)=−ZV( _ r)=-Z. Every otherwise undescribed choice at a nonterminal state has reward zero and the singleton row δ⊥r\ _ _ r\. Write Vbd=maxs,a|R(s,a)|/(1−γ)V bd= _s,a|R(s,a)|/(1-γ) for the standard bound on values, the maximum ranging over the choices described before completion. Unless stated otherwise, Z is fixed after those rewards, has polynomial encoding length, and satisfies γZ>Vbd+1γ Z>V bd+1. We invoke this convention by saying that the remaining choices use ruinous-sink completion. The added state is an absorbing final and all added rows are singletons, so the completion preserves acyclicity, rectangularity, and every two-successor or two-Dirac restriction on uncertain choices. Call a choice ruinous when its row is δ⊥r\ _ _ r\ and its reward is zero, whether the completion supplied it or a later transformation described it explicitly. Call a policy compliant when it plays a nonruinous action at every state, and write π¯ π for the policy obtained from π by conditioning on the nonruinous actions at every state, using an arbitrary nonruinous action where that conditioning has zero mass. Lemma 11 (Ruinous dominance). Suppose |Vuρ¯(s)|≤M|V_u ρ(s)|≤ M for every compliant policy ρ¯ ρ, every state s other than ⊥r _ r, and every realization u, and suppose γZ>M+1γ Z>M+1. Then Vuπ(s)≤Vuπ¯(s)V_u^π(s)≤ V_u π(s) for every stationary randomized policy π, every state, and every realization. Proof. Both policies have value −Z-Z at ⊥r _ r, so fix any other state s. The action value of a nonruinous choice (s,a)(s,a) under Vuπ¯V_u π is the value at s of the compliant policy that plays a once and follows π¯ π afterwards, hence at least −M-M. A ruinous choice has action value γV(⊥r)=−γZ<−M−1γ V( _ r)=-γ Z<-M-1, strictly smaller. Writing TπT_π for the Bellman operator of π at u, evaluating both policies at Vuπ¯V_u π therefore gives TπVuπ¯≤Tπ¯Vuπ¯=Vuπ¯T_πV_u π≤ T_ πV_u π=V_u π, since π¯ π redistributes π’s ruinous mass onto strictly larger action values. Monotonicity and contraction of TπT_π give Vuπ≤Vuπ¯V_u^π≤ V_u π. ∎ Under the default rule, M=VbdM=V bd by the standard bound on discounted values, so the hypothesis holds. A construction that fixes its own constant instead, such as ZrZ_ r in Definition 19, exhibits a bound on its own compliant values and checks the inequality against that. Definition 12 is the exception: it chooses ZεZ_ to meet a quantitative requirement of its own and establishes dominance directly in the proof of Lemma 32. Value identities below are stated for compliant policies and hold as upper bounds in general by Lemma 11. We use function-like notation for the four transformations that recur below. For a 3-CNF formula φ on n variables, Cmp(φ)Cmp( ) denotes the Boolean comparison RMDP of Definition 6, together with its clause and consistency policies and threshold 2−12n2- 12n. For a source RMDP N and reference policy π0 _0, Lift(N,π0)Lift(N, _0) denotes the exact regret lift of Definition 10, with its allowed-action family specified by context. Restrict(N,Aallow,ε)Restrict(N,A_allow, ) denotes the policy-restriction transformation of Definition 12. Finally, Ruin(N,Z)Ruin(N,Z) denotes ruinous-sink completion of N with constant Z. All constructions below run in polynomial time, and all the rational constants above have polynomial encoding length. Ruinous-sink completion adds one state and O(|S||A|)O(|S||A|) singleton rows, so it preserves polynomial size. We mention size bounds only where they are not immediate from the construction. A.2 Degree-Four Residual Normal Form The bounded-domain equivalence of 19 and the degree-four normal form quoted in their proof of Lemma 2.8 allow bounded real sentences to use an explicitly represented rational polynomial of degree at most four over [0,1]N[0,1]^N. Write such a polynomial as F(w)=∑ν=1Nmoncν∏j=1dνwν,j,dν≤4,B=max1,∑ν=1Nmon|cν|.F(w)= _ν=1^N_ monc_ν _j=1^d_νw_ν,j, d_ν≤ 4, B= \1, _ν=1^N_ mon|c_ν| \. Thus |F|≤B|F|≤ B on the box, and B has polynomial encoding length. Definition 4 (Degree-four residual normal form). For every occurrence wν,jw_ν,j, introduce a copy zν,j∈[0,1]z_ν,j∈[0,1] and residual hν,jcp=zν,j−wν,jh cp_ν,j=z_ν,j-w_ν,j. Compute each monomial with auxiliary coordinates in [0,1][0,1]: • for dν=0d_ν=0, set pν=1p_ν=1, and for dν=1d_ν=1, set pν=zν,1p_ν=z_ν,1; • for dν=2d_ν=2, use hν=pν−zν,1zν,2h_ν=p_ν-z_ν,1z_ν,2; • for dν=3d_ν=3, use tν−zν,1zν,2t_ν-z_ν,1z_ν,2 and pν−tνzν,3p_ν-t_νz_ν,3; • for dν=4d_ν=4, use tν,12−zν,1zν,2t_ν,12-z_ν,1z_ν,2, tν,34−zν,3zν,4t_ν,34-z_ν,3z_ν,4, and pν−tν,12tν,34p_ν-t_ν,12t_ν,34. These copy and product residuals lie in [−1,1][-1,1], are affine or affine plus one product of distinct variables, and have a common zero exactly at correct copies and products. The decoded polynomial is F^=∑νcνpν F= _νc_νp_ν. When an explicit output is needed, introduce o¯∈[0,1] o∈[0,1], put o=B(2o¯−1)o=B(2 o-1), and append hout=(o−F^)/(2B)h out=(o- F)/(2B); this residual also lies in [−1,1][-1,1]. Lemma 12 (Degree-four residual error). For any assignment to the inputs and auxiliary coordinates, let δ be the largest absolute copy or product residual. Then |pν−∏jwν,j|≤7δand|F^−F|≤7Bδ.|p_ν- _jw_ν,j|≤ 7δ | F-F|≤ 7Bδ. If the output residual is present and δ′δ also includes |hout||h out|, then |o−F|≤9Bδ′|o-F|≤ 9Bδ . Proof. For a,b,a′,b′∈[0,1]a,b,a ,b ∈[0,1], |ab−a′b′|≤|a−a′|+|b−b′||ab-a b |≤|a-a |+|b-b |, because ab−a′b′=b(a−a′)+a′(b−b′)ab-a b =b(a-a )+a (b-b ). The errors in degrees zero and one are zero and at most δ. For degree two the error is at most δ+δ+δ=3δ+δ+δ=3δ. For degree three it is at most δ+3δ+δ=5δ+3δ+δ=5δ, and for degree four it is at most δ+3δ+3δ=7δ+3δ+3δ=7δ. Therefore |F^−F|≤7δ∑ν|cν|≤7Bδ| F-F|≤ 7δ _ν|c_ν|≤ 7Bδ. With the output residual, |o−F^|=2B|hout|≤2Bδ′|o- F|=2B|h out|≤ 2Bδ , and the triangle inequality gives the last claim. ∎ A.3 Encoding primitives For an uncertainty vector u, policy table σ, values vsv_s, and action values qs,aq_s,a, define Bell(σ,u,v,q)=⋀s(vs=∑aσs,aqs,a)∧⋀s,a(qs,a=R(s,a)+γ∑s′u(s,a,s′)vs′).Bell(σ,u,v,q)= _s (v_s= _a _s,aq_s,a ) _s,a (q_s,a=R(s,a)+γ _s u(s,a,s )v_s ). Let Φ(u) _U(u) be the rational linear description of the uncertainty polytope, including nonnegativity and normalization, and let Policy(σ)=⋀s(∑aσs,a=1)∧⋀s,aσs,a≥0.Policy(σ)= _s ( _a _s,a=1 ) _s,a _s,a≥ 0. Lemma 13 (Universal Bellman encoding). For an explicit family Π=π1,…,πr =\ _1,…, _r\ and a universally quantified policy τ, the assertion Vuτ(sι)−maxi≤rVuπi(sι)≤tfor every u∈V_u^τ(s_ )- _i≤ rV_u _i(s_ )≤ t every u has a polynomial-size universal formula over the reals. The policy τ may instead be fixed, and prefixing an existential block for r valid policy tables gives an existential-universal formula when r is unary-bounded. Proof. Use the universal implication ∀τ,u,vτ,qτ,(vi,qi)i=1r:(Policy(τ)∧Φ(u)∧Bell(τ,u,vτ,qτ)∧⋀i=1rBell(πi,u,vi,qi))⟹⋁i=1r(vsιτ−vsιi≤t). split∀\,τ,u,v^τ,q^τ,(v^i,q^i)_i=1^r: & (Policy(τ) _U(u) (τ,u,v^τ,q^τ) _i=1^rBell( _i,u,v^i,q^i) ) _i=1^r (v^τ_s_ -v^i_s_ ≤ t ). split Discounting makes each valid Bellman system unique. Invalid policy, realization, or Bellman assignments falsify the antecedent. Fixing τ removes its policy variables, while existentially quantified family members require their simplex constraints outside the universal implication. Compactness of the policy simplexes and uncertainty polytope ensures that the relevant extrema are attained. ∎ Appendix B On Policy and Portfolio Comparison We collect the comparison problems and constructions used by the regret lower bounds. B.1 Comparison Preliminaries Problem 5 (Robust policy comparison). Given an RMDP M, policies π1,π2∈ΠMR _1, _2∈ ^MR, and a rational threshold t, decide whether Δ(π1,π2)=sup∈(Vπ1(sι)−Vπ2(sι))≤t. _U( _1, _2)= _ u (V_ u _1(s_ )-V_ u _2(s_ ) )≤ t. A choice (s,a)(s,a) is used by π if s is reachable with positive probability under some realization and π(s,a)>0π(s,a)>0. It is shared by π1 _1 and π2 _2 if both use it. The set of shared choices is denoted Sh(π1,π2)Sh( _1, _2). Call s absorbing under π when every choice used by π at s has row δs\ _s\. Let GπG_π contain s→s′s→ s when a choice used by π at s can reach s′s under some realization, except that the self-loop at a state absorbing under π is omitted. This exception matches the convention for RMDP acyclicity, which likewise permits self-loops only at absorbing final states. Self-loops at other states remain one-edge cycles. A used choice (s,a)(s,a) is cycle-free under π if s lies on no directed cycle of GπG_π. We write CF(π)CF(π) for these choices. Definition 5 (Cycle-free on shared choices). The pair (π1,π2)( _1, _2) is cycle-free on shared choices if Sh(π1,π2)⊆CF(π1)∩CF(π2)Sh( _1, _2) ( _1) ( _2). For π1,π2 _1, _2 and ∈ u , write Dπ1,π2():=Vπ1(sι)−Vπ2(sι)D_ _1, _2( u):=V_ u _1(s_ )-V_ u _2(s_ ), so that Δ(π1,π2)=sup∈Dπ1,π2() _U( _1, _2)= _ u D_ _1, _2( u). For a polytope P, write vert(P)vert(P) for its set of vertices. For (s,a)(s,a)-rectangular U, write Vert():=∏s,avert(s,a)Vert(U):= _s,avert(U_s,a) for the set of vertex tuples. Separated choices. If π1 _1 and π2 _2 share no uncertain choice, rectangularity lets nature optimize their used rows independently, so Δ(π1,π2)=supu1Vu1π1(sι)−infu2Vu2π2(sι). _U( _1, _2)= _u_1V _1_u_1(s_ )- _u_2V _2_u_2(s_ ). This is a direct consequence of the standard optimistic and robust fixed-policy linear programs and is computable in polynomial time (13; 21). B.2 Combinatorial Hardness of Robust Policy Comparison The reduction makes one local copy of every variable in every clause. One policy scans the clauses, and the other audits a uniformly selected variable against one valuation. Theorem 14 (Shared-choice Boolean hardness). Robust policy comparison is coNP-hard even for deterministic policies in acyclic (s,a)(s,a)-rectangular RMDPs in which every uncertain choice is a two-Dirac segment and the only other stochastic row is a certain uniform splitter. Fix a 3-CNF formula φ=⋀i=1mCi = _i=1^mC_i over variables x1,…,xnx_1,…,x_n. We may remove tautological clauses, repeated literals, and variables with no occurrence; the constant case is decided directly, so assume n≥1n≥ 1. For a literal occurrence o, let var(o)var(o) be its variable, let val(o)∈0,1val(o)∈\0,1\ be the value that makes its literal true, and order the occurrences OxO_x of each variable x by clause and then by position within the clause. Definition (Clause-local encoding). For every occurrence o, introduce two local bits bo,1b_o,1 and bo,0b_o,0, indexed by the values they certify. The equation bo,c=1b_o,c=1 says that occurrence o is locally consistent with value c. Occurrence o is locally true when bo,val(o)=1b_o,val(o)=1 and bo,1−val(o)=0b_o,1-val(o)=0. Write ΦC _C for the clause condition ΦC:=⋀i=1m(⋁o∈Ci(bo,val(o)∧¬bo,1−val(o))). _C:= _i=1^m ( _o∈ C_i (b_o,val(o) b_o,1-val(o) ) ). (3) The local bits of different clauses are disjoint. For every original variable x, introduce a global bit XxX_x. For each variable write ΦKx:=⋀o∈Oxbo,Xx,ΦK:=⋀xΦKx. _K^x:= _o∈ O_xb_o,X_x, _K:= _x _K^x. (4) Lemma (Clause-local equivalence). Formula φ is satisfiable iff its global and local bits have an assignment satisfying ΦC∧ΦK _C _K. Proof. If a valuation v satisfies φ , set Xx=v(x)X_x=v(x) and set bo,c=1b_o,c=1 exactly when c=v(var(o))c=v(var(o)). Every ΦKx _K^x holds. Every clause has an occurrence o with val(o)=v(var(o))val(o)=v(var(o)), so that occurrence has the locally true pattern and ΦC _C holds. Conversely, suppose ΦC∧ΦK _C _K holds and define v(x):=Xxv(x):=X_x. Each clause has a locally true occurrence o with bo,1−val(o)=0b_o,1-val(o)=0. Since ΦKvar(o) _K^var(o) forces bo,Xvar(o)=1b_o,X_var(o)=1, we have Xvar(o)=val(o)X_var(o)=val(o). Thus the literal at o is true under v, and every clause is satisfied. ∎ ΦK _K does not force an occurrence’s two bits to be complementary. The pair test is part of ΦC _C. Example (A clause-local encoding). Consider φ=(x1∨¬x2∨x3)∧(¬x1∨x2∨x3). =(x_1 x_2 x_3) ( x_1 x_2 x_3). Take the valuation: x1=x2=1,x3=0,x_1=x_2=1,x_3=0, so Xx1=Xx2=1 and Xx3=0.X_x_1=X_x_2=1 and X_x_3=0. Following the encoding in the proof above, set bo,c=1b_o,c=1 exactly when c=Xvar(o)c=X_var(o), for every occurrence o. Clause literal var(o)var(o) val(o)val(o) Xvar(o)X_var(o) (bo,1,bo,0)(b_o,1,b_o,0) locally true? C1C_1 x1x_1 x1x_1 11 11 (1,0)(1,0) yes ¬x2 x_2 x2x_2 00 11 (1,0)(1,0) no x3x_3 x3x_3 11 00 (0,1)(0,1) no C2C_2 ¬x1 x_1 x1x_1 00 11 (1,0)(1,0) no x2x_2 x2x_2 11 11 (1,0)(1,0) yes x3x_3 x3x_3 11 00 (0,1)(0,1) no A literal is locally true exactly when bo,val(o)=1b_o,val(o)=1, i.e., when val(o)=Xvar(o)val(o)=X_var(o): this holds for x1x_1 in C1C_1 and x2x_2 in C2C_2, matching the fact that these are the literals true under the valuation. Using the labels o1,…,o6o_1,…,o_6, the clause and consistency conditions instantiate to ΦC=[(bo1,1∧¬bo1,0)∨(bo2,0∧¬bo2,1)∨(bo3,1∧¬bo3,0)]∧[(bo4,0∧¬bo4,1)∨(bo5,1∧¬bo5,0)∨(bo6,1∧¬bo6,0)], _C= [(b_o_1,1 b_o_1,0) (b_o_2,0 b_o_2,1) (b_o_3,1 b_o_3,0) ] [(b_o_4,0 b_o_4,1) (b_o_5,1 b_o_5,0) (b_o_6,1 b_o_6,0) ], ΦKx1=bo1,1∧bo4,1,ΦKx2=bo2,1∧bo5,1,ΦKx3=bo3,0∧bo6,0,ΦK=ΦKx1∧ΦKx2∧ΦKx3. _K^x_1=b_o_1,1 b_o_4,1, _K^x_2=b_o_2,1 b_o_5,1, _K^x_3=b_o_3,0 b_o_6,0, _K= _K^x_1 _K^x_2 _K^x_3. Substituting the values from the table: in ΦC _C’s first bracket, o1o_1 gives (1∧1)=1(1 1)=1 while o2,o3o_2,o_3 give 00, so the bracket is 11; in the second, o5o_5 gives (1∧1)=1(1 1)=1 while o4,o6o_4,o_6 give 00, so that bracket is also 11; hence ΦC=1 _C=1. Each ΦKx _K^x is a conjunction of two matching bits (e.g. ΦKx1=1∧1=1 _K^x_1=1 1=1), so ΦK=1 _K=1 as well. The reduction realizes ΦC _C as a clause scan and each ΦKx _K^x as one audit branch in the same RMDP. Nature selects the global and local bits. The two paths share every local-bit choice, so they evaluate the same assignment. Definition 6 (Boolean comparison RMDP). For a 3-CNF formula φ=⋀i=1mCi = _i=1^mC_i over variables x1,…,xnx_1,…,x_n with n≥1n≥ 1, no tautological clause, no repeated literal within a clause, and no variable absent from every clause, the Boolean comparison RMDP is Mφ=(S,A,,R,sι,γ0)M_ =(S,A,U,R,s_ , _0), with the following components. • S is the disjoint union of the following groups. – The initial state sιs_ . – Clause-scan states: a control state fi,jf_i,j for each literal occurrence o=(i,j)o=(i,j), together with the terminals accCacc_C and rejCrej_C. – Audit states: global selectors qXxq_X_x with outcomes qXx0,qXx1q_X_x^0,q_X_x^1, controls kx,c,ℓk_x,c, that inspect the ℓ occurrence of x after committing to c∈0,1c∈\0,1\, together with the terminals accKacc_K and rejKrej_K. – Shared local-bit selectors: for each occurrence o and c∈0,1c∈\0,1\, the selector of Definition 3, used by both policies. – Padding states SpadS_pad, reward-free, fixed once the transitions below are defined. – A ruinous sink ⊥r _ r. • At sιs_ , action aCa_C enters f1,1f_1,1, whereas action aKa_K has the fixed uniform transition to qXxq_X_x, x∈x1,…,xnx∈\x_1,…,x_n\. Every selector has one action. Outcome qXxcq_X_x^c leads to kx,c,1k_x,c,1, each fi,jf_i,j leads to the first local selector for its occurrence, and each kx,c,ℓk_x,c, leads to the corresponding qo,cq_o,c. From a shared outcome qo,cbq_o,c^b, the clause-scan action and audit action have their respective deterministic continuations, ending in accCacc_C/rejCrej_C or accKacc_K/rejKrej_K as described below. All other control states have the indicated unique deterministic continuation. Fix H at least as long as the longest of these paths. SpadS_pad consists of fresh states inserted along every shorter path so it also reaches its terminal after exactly H transitions, each with a single reward-free action continuing toward that terminal. This common depth is necessary because a shared accepting terminal can be reached at realization-dependent depths, so one terminal payoff cannot otherwise cancel every discount factor. • U is the product of the two-Dirac segments in Equation 2, one for every global bit XxX_x and local bit (o,c)(o,c). All remaining described choices are singletons, including the certain uniform splitter at sιs_ . Its vertices are exactly the Boolean realizations pz∈0,1p_z∈\0,1\. • accCacc_C is the terminal with payoff γ0−H _0^-H and accKacc_K the terminal with payoff −γ0−H- _0^-H, while every other described reward, including at rejC,rejKrej_C,rej_K and at padding states, is zero. • All remaining choices use ruinous-sink completion. • The initial state is sιs_ and the discount is γ0 _0. Fix a realization u∈u and a stationary policy π. Since π prescribes one action at every state and u fixes one outcome at every two-Dirac selector, the only randomness left in π’s run under u comes from any fixed-probability transitions π itself uses, such as the certain uniform splitter. Because the graph is acyclic and S is finite, this run reaches a terminal with probability one. Say π accepts under u with probability equal to the chance of reaching an accepting terminal; if π never uses such a transition – as is the case for πC _C – this probability is always 00 or 11, and we speak of π accepting or rejecting outright. The clause policy. Policy πC _C processes clauses and their literals in order. At occurrence o=(i,j)o=(i,j), it uses the pair test of Definition 3, accepting the locally true outcome pair. A true literal advances to the next clause, a false literal advances to the next literal, and an entirely false clause rejects. Satisfying the last clause accepts. Thus πC _C checks exactly ΦC _C. The consistency policy. Policy πK _K first takes the certain uniform splitter, which selects a variable x. It reads XxX_x and thereby commits to c∈0,1c∈\0,1\. It then uses the audit chain of Definition 3 over OxO_x in clause-major order. Conditioned on the certain uniform splitter selecting x, πK _K therefore checks exactly ΦKx _K^x. Lemma (Unambiguous prescriptions). Both policies above are stationary deterministic policies. Proof. The clause scan encounters each fi,jf_i,j once and reaches the two selectors of an occurrence in the fixed order prescribed above. An audit branch commits at qXxcq_X_x^c before reaching any kx,c,ℓk_x,c, . Thus each policy prescribes a single continuation at every outcome state it can reach. At a shared outcome qo,cbq_o,c^b, the two roles use distinct actions, so their continuations need not agree. Complete each policy at its unreachable states with a fixed default action, using ruinous-sink completion when no role action was described there. ∎ By Lemma 10, their value difference is the sum of their acceptance probabilities. The shared fragment for a positive occurrence is shown in Figure 3. The audit path shown is the branch that committed to Xx=1X_x=1. certain uniform splitterqXxq_X_xqXx1q_X_x^1kx,1,ℓk_x,1, fi,jf_i,j: test xxqo,1q_o,1qo,10q_o,1^0qo,11q_o,1^1πC _C: next literalπK _K: rejectqo,0q_o,0πK _K: next copyor acceptqo,00q_o,0^0qo,01q_o,0^1πC _C: next clauseor acceptπC _C: next literalor reject1/n1/npXxp_X_x1−po,11-p_o,1po,1p_o,1πC _CπK _K1−po,01-p_o,0po,0p_o,0 Figure 3: The shared fragment for a positive occurrence o=(i,j)o=(i,j) and the audit branch Xx=1X_x=1. The clause scan tests the pair (bo,1,bo,0)(b_o,1,b_o,0), whereas this audit branch needs only bo,1b_o,1. The branch Xx=0X_x=0 analogously audits qo,0q_o,0. Selector arrows are uncertain; arrows from outcome states are the certain, role-specific actions of the two policies. Lemma (Policy semantics). At a vertex u of the uncertainty polytope, πC _C accepts under u exactly when ΦC _C holds under u. Conditioned on the certain uniform splitter selecting x, πK _K accepts under u exactly when ΦKx _K^x holds under u; unconditionally, this makes πK _K’s probability of accepting under u equal to 1n|x:ΦKx holds under | 1n|\x: _K^x holds under u\|, the fraction of variables whose audit would pass. Moreover, DπC,πK()=πC accepts under +Pr[πK accepts under ].D_ _C, _K( u)=1_\ _C accepts under u\+ [ _K accepts under u]. Proof. At a vertex, each transition in (2) selects one Boolean value. The clause path implements (3), and the audit branch for x implements its conjunct in (4). Padding places every final state at depth H, so the accepting rewards contribute 11 and −1-1 to the two policy values. The certain uniform splitter averages the audit contribution over the n variables, and rejecting paths contribute zero. ∎ Example. For the satisfying assignment in the encoding table, πC _C confirms x1x_1 in C1C_1 and x2x_2 in C2C_2, and every variable audit passes, giving difference 22. Now take the unsatisfying valuation x1=0,x2=1,x3=0x_1=0,x_2=1,x_3=0 and its canonical local pairs. The clause scan rejects C1C_1, although every audit passes. If only the copy of x1x_1 in C1C_1 is changed from (0,1)(0,1) to (1,0)(1,0), the clause scan accepts, but the x1x_1 audit, committed to 00, reads bo,0=0b_o,0=0 and rejects. The malformed pairs (0,0)(0,0) and (1,1)(1,1) cannot make a literal locally true because the clause scan tests both bits. Lemma 15. There is a vertex under which πC _C accepts and every variable audit passes if and only if φ is satisfiable. Proof. This is the clause-local equivalence, together with the policy semantics established above. ∎ The uncertain choices are independent line segments between two Dirac distributions. Hence the RMDP is (s,a)(s,a)-rectangular and every uncertain choice is two-Dirac. The only other stochastic row is the certain uniform splitter. After deleting terminal self-loops, the full transition graph is a DAG: after the initial state, order the global-selector blocks first, then the occurrence blocks in clause-major order, placing within each occurrence the selector for val(o)val(o) before the other selector, and finally the padding and terminal states. Every control and outcome state can be placed immediately before or after its associated selector. In particular, no run under either policy uses the same uncertain choice twice, and every terminal that both policies reach is absorbing under each of them, so every shared choice is cycle-free under both policies in the sense of Definition 5. By Lemma 17, πC _C and πK _K’s value difference attains its maximum at a tuple of choice vertices. By this and the two lemmas above, φ∈SAT ⟹Δ(πC,πK)=2, _U( _C, _K)=2, φ∈UNSAT ⟹Δ(πC,πK)≤2−1n. _U( _C, _K)≤ 2- 1n. In the first case, nature chooses the canonical vertex of a satisfying valuation. In the second, a vertex satisfying ΦC _C has at least one failing variable audit by Lemma 15, and therefore has difference at most 1+(n−1)/n1+(n-1)/n; a vertex violating ΦC _C has difference at most 11. Vertex sufficiency shows that an interior realization cannot do better. Proof of Theorem 14. Use threshold 2−12n2- 12n. The construction satisfies φ∈UNSAT⇔Δ(πC,πK)≤2−12n. _U( _C, _K)≤ 2- 12n. Indeed, 2−1n<2−12n<2.2- 1n<2- 12n<2. The construction has polynomial size, γ0−H=(400/361)H _0^-H=(400/361)^H has O(H)O(H) bits, and all uncertain choices are independent two-Dirac choices. This is a polynomial reduction from UNSAT. ∎ B.3 Vertex-Extremal Membership Theorem 16 (Vertex-extremal membership). Robust policy comparison is in coNP for (s,a)(s,a)-rectangular polytopes when both policies are cycle-free on shared choices (Definition 5). Definition 7 (Vertex-extremal pair). The pair (π1,π2)( _1, _2) is vertex-extremal if sup∈Dπ1,π2()=max∈Vert()Dπ1,π2(). _ u D_ _1, _2( u)= _ v (U)D_ _1, _2( v). Lemma 17 (Cycle-freeness on shared choices implies vertex-extremality). If (π1,π2)( _1, _2) is cycle-free on shared choices (Definition 5), then it is vertex-extremal (Definition 7). The main-body example Example 1 shows why the hypothesis is necessary: one shared choice on a policy cycle can create an irrational interior maximum, so endpoint evaluation is no longer sound. We use two standard facts. A separately affine function on a product of polytopes is extremized at a tuple of vertices by optimizing one block at a time. A finite linear-fractional function on a polytope is extremized at a vertex because its value on a segment lies between its endpoint values. Proof of Lemma 17. Fix a single block s0,a0U_s_0,a_0, hold every other block fixed, and consider two cases according to whether (s0,a0)∈Sh(π1,π2)(s_0,a_0) ( _1, _2). Then iterate over the blocks. • (s0,a0)∉Sh(π1,π2)(s_0,a_0) ( _1, _2), say only π1 _1 uses it. Then Vπ2(sι)V_ u _2(s_ ) is constant in this block, and Dπ1,π2D_ _1, _2 differs from Vπ1(sι)V_ u _1(s_ ) by a constant. By Cramer’s rule applied to the one equation of π1 _1’s Bellman system that this block enters, Vπ1V_ u _1 is linear-fractional in this block, a ratio of two functions each affine in it regardless of cycles elsewhere in the graph, so the standard fact above makes it, and hence Dπ1,π2D_ _1, _2, extremal at a vertex. • (s0,a0)∈Sh(π1,π2)(s_0,a_0) ( _1, _2) (hence, by hypothesis, cycle-free under both π1 _1 and π2 _2). If s0s_0 is absorbing under one of the two policies, then that policy uses (s0,a0)(s_0,a_0) and the choice has row δs0\ _s_0\, so the block is the singleton δs0\ _s_0\ and Dπ1,π2D_ _1, _2 is constant in it. Otherwise no self-loop was omitted at s0s_0, so cycle-freeness is the literal graph condition. Under either policy, a run then uses the choice (s0,a0)(s_0,a_0) at most once. The probability of reaching s0s_0 is independent of its outgoing row, and the continuation value after leaving s0s_0 cannot depend on that row because the run never returns. Conditioning on reaching and selecting (s0,a0)(s_0,a_0) therefore makes each policy value affine in the free block. Their difference is affine as well and is extremized at a vertex. Every block falls under one of the two cases, so Dπ1,π2D_ _1, _2 is extremal at a vertex in every block, giving vertex-tuple extremality. ∎ Proof of Theorem 16. By Lemma 17, the pair is vertex-extremal. For the strict complement, guess a vertex tuple v with Dπ1,π2()>tD_ _1, _2( v)>t. Such a tuple has polynomial encoding length because each component vertex solves a full-rank subsystem of tight rational constraints. The verifier checks ∈ v , solves the two rational Bellman systems, and compares their initial values in polynomial time. Thus the complement is in NP. ∎ B.4 Shared Cycles and Square-Root-Sum Hardness Theorem 18 (Shared-cycle algebraic hardness). Robust policy comparison is coSQRS-hard for deterministic policies on (s,a)(s,a)-rectangular RMDPs in which every uncertain choice is two-Dirac and the only other stochastic rows are certain uniform splitters. We construct a gadget with a shared choice on a cycle, which creates one normalized square-root term. An exact derivative calculation locates its interior maximum, and a certain splitter combines independently chosen local maxima into the target sum of square roots. The delicate point is sign control at the critical point. All choices stay (s,a)(s,a)-rectangular and use the appendix-wide discount γ0 _0 required by the exact lift. Fix b≥2,m=⌈b⌉.b≥ 2, m= b . We round b b up to the nearest integer m, so that b≤m2b≤ m^2 (needed below), while m stays close enough to b b for the final identity to come out exactly right. The local gadget in Figure 4 has entry state s, intermediate states s1,s2s_1,s_2, and a zero-reward sink. Policy πu _u chooses u at s and moves to s1s_1 with reward rur_u. Policy πv _v chooses v and moves to s2s_2 directly, with reward zero. The forced edge s1→s2s_1→ s_2 has reward zero: its only purpose is to give πu _u one extra step before reaching s2s_2, so that its eventual return to s is discounted one extra factor of γ0 _0 compared to πv _v’s. This asymmetry in cycle length is essential: without it, Qu−QvQ_u-Q_v below would be a ratio of two affine functions, which is monotone and has no interior maximum. The same mechanism appears in Example 1, where one policy closes the cycle and the other exits immediately. At s2s_2, the unique shared uncertain choice returns to s with probability p and enters the sink with probability 1−p1-p, paying reward cvc_v either way. s1s_1s2s_2⊥ ,ruu,r_uv,0v,000p,cvp,c_v1−p,cv1-p,c_v00 Figure 4: The shared-cycle gadget realizing one normalized square-root term. Our goal is to choose U,V,cv,ruU,V,c_v,r_u so that supp∈[0,1](Qu(p)−Qv(p)) _p∈[0,1] (Q_u(p)-Q_v(p) ) takes the form Cb−bC_b- b, for a constant CbC_b depending only on b. Lemma 19 establishes this. Set U=m(1−γ0)2γ0,U= m(1- _0)2 _0, V=b(1−γ0)2m,V= b(1- _0)2m, cv=Vγ0,c_v= V _0, ru=U−γ0V=(1−γ0)(m2−γ02b)2γ0m.r_u=U- _0V= (1- _0)(m^2- _0^2b)2 _0m. All constants are nonnegative: U,V,cv>0U,V,c_v>0, while m2≥b>γ02bm^2≥ b> _0^2b gives ru>0r_u>0. The Bellman equations give, writing Qi(p):=Vπi(s)Q_i(p):=V_ u _i(s) for the value of πi _i at the entry state as a function of the shared return probability p, Qu(p)=ru+γ02cv+γ03pQu(p)=U1−γ03p,Q_u(p)=r_u+ _0^2c_v+ _0^3pQ_u(p)= U1- _0^3p, Qv(p)=γ0cv+γ02pQv(p)=V1−γ02p.Q_v(p)= _0c_v+ _0^2pQ_v(p)= V1- _0^2p. Lemma 19 (Rational-fraction maximum). With the constants above, supp∈[0,1](Qu(p)−Qv(p))=Cb−b,Cb=m2γ0+γ0b2m. _p∈[0,1] (Q_u(p)-Q_v(p) )=C_b- b, C_b= m2 _0+ _0b2m. Proof. Put x=1−γ02px=1- _0^2p. Then x∈[1−γ02,1]x∈[1- _0^2,1] and f(x)=U1−γ0+γ0x−Vx.f(x)= U1- _0+ _0x- Vx. After multiplying by the positive denominators, the sign of f′(x)f (x) is the sign of V(1−γ0+γ0x)−γ0Ux. V(1- _0+ _0x)- _0U\,x. Since V≤γ0UV≤ _0U, the affine sign factor has negative slope. It is positive before its unique zero and negative after it, so the zero is a maximum. It lies in the interval provided V≤γ0Uandγ0U≤hγ02V,hγ0=1−γ031−γ02=434721304400.V≤ _0U _0U≤ h_ _0^2V, h_ _0= 1- _0^31- _0^2= 434721304400. The first inequality is b≤m2b≤ m^2. The second follows from m2/b≤2m^2/b≤ 2 and the exact rational comparison hγ02>2h_ _0^2>2. At the critical point, direct substitution yields maxf=(U−γ0V)21−γ0=m2γ0+γ0b2m−b. f= ( U- _0V)^21- _0= m2 _0+ _0b2m- b. This value is nonnegative by the arithmetic-geometric mean inequality applied to m/γ0m/ _0 and γ0b/m _0b/m. ∎ Combining independent copies. For inputs b1,…,bnb_1,…,b_n, take disjoint copies of the gadget. A fresh certain uniform splitter enters each copy with probability 1/n1/n. Scaling all rewards in every copy by n/γ0n/ _0 cancels the splitter probability and first discount. After this scaling, every remaining choice uses ruinous-sink completion. Rectangularity makes the local parameters independent, so Δ(πu,πv)=∑i=1nCbi−∑i=1nbi. _U( _u, _v)= _i=1^nC_b_i- _i=1^n b_i. Proof of Theorem 18. Reduce from the coSQRS variant asking whether ∑ibi≥k _i b_i≥ k. Set t=∑iCbi−k.t= _iC_b_i-k. Then Δ(πu,πv)≤t _U( _u, _v)≤ t exactly when the coSQRS instance is positive. Every uncertain choice is two-Dirac. ∎ B.5 Real-Hierarchy Completeness of Policy Comparison Theorem 20 (General policy comparison). Robust policy comparison is ∀ℝ -complete for deterministic policies under general rational polytopic uncertainty. Lemma 21 (∀ℝ membership for policy comparison). Robust policy comparison is in ∀ℝ for deterministic policies under general rational polytopic uncertainty. Proof. Apply Lemma 13 with τ fixed to π1 _1 and the singleton family π2\ _2\. ∎ Definition 8 (Polynomial-evaluation RMDP). Fix an explicit sparse polynomial f(p)=∑ℓ=1Ncℓ∏j=1dℓpiℓ,j,p∈[0,1]m,f(p)= _ =1^Nc_ _j=1^d_ p_i_ ,j, p∈[0,1]^m, and a rational discount γ∈(0,1)γ∈(0,1). The component Polyγ(f)Poly_γ(f) is defined as follows. • A reward-zero certain uniform splitter at sfs_f enters branch ℓ with probability 1/N1/N. That branch has states bℓ0,…,bℓdℓb_ ^0,…,b_ ^d_ and a common zero-reward sink ⊥ . • At bℓj−1b_ ^j-1, the unique action continues to bℓjb_ ^j with probability uℓ,ju_ ,j and enters ⊥ otherwise. State bℓdℓb_ ^d_ is absorbing with value rℓ=Nγ−(dℓ+1)cℓr_ =Nγ^-(d_ +1)c_ . • Each uℓ,ju_ ,j is a coordinate of a two-successor row in [0,1][0,1]. Occurrences representing the same logical coordinate may be tied by rational linear equalities. • At each state the action described above is intended, every other described reward is zero, and R(bℓdℓ)=(1−γ)rℓR(b_ ^d_ )=(1-γ)r_ . • All remaining choices use ruinous-sink completion. For policy comparison, choose a representative uirepu_i rep for every parameter and impose uℓ,j=uirepu_ ,j=u_i rep whenever iℓ,j=i_ ,j=i; occurrences of 1−pi1-p_i, when present, instead satisfy uℓ,j=1−uirepu_ ,j=1-u_i rep. Together with stochasticity and box constraints, these equalities define U and the resulting RMDP Mf=(S,A,,R,sf,γ)M_f=(S,A,U,R,s_f,γ). Repeated indices in a monomial represent powers and are realized by distinct rows tied to the same representative. Figure 5 shows one monomial branch of this construction. bℓ0b_ ^0bℓ1b_ ^1⋯·sbℓdℓb_ ^d_ ⊥ ℓ,1u_ ,1uℓ,2u_ ,2uℓ,dℓu_ ,d_ 1−uℓ,11-u_ ,11−uℓ,21-u_ ,21−uℓ,dℓ1-u_ ,d_ (1−γ)rℓ(1-γ)r_ 00 Figure 5: One branch of the polynomial-evaluation RMDP. Equalities in U tie repeated parameter occurrences across branches. Lemma 22 (Polynomial evaluation). For every realization of the occurrence rows, the compliant value of Polyγ(f)Poly_γ(f) is ∑ℓcℓ∏juℓ,j _ c_ _ju_ ,j. In particular, when the representative coordinates equal p, the unique compliant policy of MfM_f has value f(p)f(p) at sfs_f. The component is acyclic apart from absorbing terminals, every uncertain row has two successors, and its only other stochastic row is a certain uniform splitter. It has size O(Nmaxℓdℓ)O(N _ d_ ) and rewards of polynomial encoding length. Moreover, U is one rational polytope of polynomial description size. Proof. Branch ℓ is reached with probability 1/N1/N, survives with probability ∏juℓ,j _ju_ ,j, and reaches its terminal after dℓ+1d_ +1 transitions. Its discounted contribution is therefore 1Nγdℓ+1(Nγ−(dℓ+1)cℓ)∏juℓ,j, 1Nγ^d_ +1 (Nγ^-(d_ +1)c_ ) _ju_ ,j, and summing gives the first identity. The representative equalities then give f(p)f(p). Each occurrence contributes one row. Every branch is a directed chain, and the payoff exponent is at most the polynomial input size. The tying, complement, stochasticity, and interval constraints are rational linear constraints, so their intersection is a polynomial-size rational polytope. ∎ Lemma 23 (∀ℝ hardness for policy comparison). Robust policy comparison is ∀ℝ -hard for deterministic policies under general rational polytopic uncertainty. Proof. By the strict degree-six normal form of 19 and their bounded-open equivalence (19, Proposition 2.12), ∃p∈[0,1]m:f(p)>0∃ p∈[0,1]^m:f(p)>0 is ∃ℝ -complete for an explicitly represented degree-six polynomial. Indeed, the affine image of the source box is (0,1)m(0,1)^m, and strict positivity there is equivalent to strict positivity on its closure by continuity. Its complement is ∀p:f(p)≤0∀ p:f(p)≤ 0. Construct MfM_f by Definition 8, add a fresh initial choice between sfs_f and a zero-reward sink, and let deterministic policies πf,π⊥ _f, _ choose the two actions. By Lemma 22, Δ(πf,π⊥)≤0⇔∀p∈[0,1]m:f(p)≤0. _U( _f, _ )≤ 0 ∀ p∈[0,1]^m:\ f(p)≤ 0. This proves hardness. ∎ Proof of Theorem 20. Immediate from Lemmas 21 and 23. ∎ B.6 Portfolio Comparison and the Shared-Selector Evaluator Problem 6 (Portfolio comparison). Given an RMDP M, a policy π0∈ΠMR _0∈ ^MR, an input portfolio Π⊂ΠMR ⊂ ^MR, and rational t, decide whether Δ(π0,Π)=sup∈(Vπ0(sι)−maxπ∈ΠVπ(sι))≤t. _U( _0, )= _ u (V_ u _0(s_ )- _π∈ V_ u^π(s_ ) )≤ t. Theorem 24. Portfolio comparison is ∀ℝ -complete, with portfolio size part of the input. Hardness already holds for deterministic policies and acyclic (s,a)(s,a)-rectangular RMDPs with two-successor uncertain choices. Lemma 25 (Membership). Portfolio comparison is in ∀ℝ . Proof. Apply Lemma 13 with τ fixed to π0 _0 and the explicit family Π . ∎ Problem 7 (Strict elementary feasibility). Given rational expressions g1,…,grg_1,…,g_r over variables x∈[0,1]nx∈[0,1]^n, each affine or affine plus one bilinear term, with no variable occurring twice in the same expression, decide whether g1(x)>0,…,gr(x)>0g_1(x)>0,…,g_r(x)>0 has a solution x∈[0,1]nx∈[0,1]^n. Lemma 26. 7 is ∃ℝ -complete. Proof. Membership is immediate. For hardness, use the bounded degree-four equality normal form underlying Definition 4. It is ∃ℝ -complete to decide ∃y∈[−1,1]n:f(y)=0,∃ y∈[-1,1]^n: f(y)=0, and substituting yi=2xi−1y_i=2x_i-1 changes the domain to [0,1]n[0,1]^n. Apply Definition 4 without its optional output coordinate and append the affine residual f^/B f/B, which sets the decoded polynomial to zero. Denote all residuals by h1,…,hth_1,…,h_t. If they have no common zero on the compact box, then η=minxmaxj|hj(x)|>0.η= _x _j|h_j(x)|>0. Clear denominators and put F=∑jhj2F= _jh_j^2. This is a nonnegative integer polynomial of degree at most four, with polynomial coefficient bit length. If there is no common zero, apply the effective Łojasiewicz bound of 19 on the compact box to F and the constant polynomial one. It gives a lower bound 2−ℓDcN22^- D^cN^2 in terms of the number N of variables, degree D≤4D≤ 4, and coefficient length ℓ . Consequently an explicit polynomial p in the input length satisfies η>2−2pη>2^-2^p. Introduce positive variables a0,b0,…,ap,bpa_0,b_0,…,a_p,b_p with 0<a0<12,0<b0<12,0<a_0< 12, 0<b_0< 12, 0<aj+1<ajbj4,0<bj+1<ajbj4(j<p).0<a_j+1< a_jb_j4, 0<b_j+1< a_jb_j4 (j<p). The exponent recurrence gives ap<2−2pa_p<2^-2^p. Replace hj=0h_j=0 by ap+hj>0,ap−hj>0.a_p+h_j>0, a_p-h_j>0. An exact normal-form solution satisfies the strict system. Conversely, a strict solution would have |hj|<ap<η|h_j|<a_p<η for every j, contradicting the definition of η when the residual system is infeasible. Each constraint is affine or affine plus one product of distinct variables. Input copies ensure that an input variable occurs only in affine copy residuals. ∎ Lemma 27 (Hardness). Portfolio comparison is ∀ℝ -hard already for deterministic policies and acyclic (s,a)(s,a)-rectangular RMDPs with two-successor uncertain choices. Definition 9 (Shared-selector evaluator). Fix a strict elementary feasibility instance g1,…,grg_1,…,g_r over x∈[0,1]nx∈[0,1]^n (7) and a discount γ. For each i, treat −gi-g_i as its constant term plus a list of monomials, each either linear or bilinear in two distinct variables, and order the variables of every monomial by increasing index. The shared-selector evaluator is the RMDP M=(S,A,,R,sι,γ)M=(S,A,U,R,s_ ,γ), where • S=s0,⊥∪qj,qj0,qj1:1≤j≤n∪τi,ℓS=\s_0, \∪\q_j,q_j^0,q_j^1:1≤ j≤ n\∪\ _i, \: the initial state s0s_0; a fresh absorbing zero-reward state ⊥ ; one selector qjq_j and its two successors qj0,qj1q_j^0,q_j^1 per variable xjx_j, shared by every branch that mentions xjx_j; and one terminal τi,ℓ _i, per branch ℓ of −gi-g_i (its constant term counts as one branch); • A=a0,a1,…,ar∪di,j,bA=\a_0,a_1,…,a_r\∪\d_i,j,b\: at s0s_0, action a0a_0 leads deterministically to ⊥ , and action aia_i enters a rational certain splitter with one branch per term of −gi-g_i; at qjbq_j^b, the decoder action di,j,bd_i,j,b is enabled for every policy i whose current branch visits xjx_j; it leads to ⊥ when b=0b=0, and otherwise to the next selector or to the branch’s terminal if xjx_j was its last variable; • U is (s,a)(s,a)-rectangular: the certain splitter at aia_i and every decoder are deterministic; the one uncertain choice at qjq_j has distribution (1−xj)δqj0+xjδqj1(1-x_j) _q_j^0+x_j _q_j^1, the same distribution regardless of which branch or which gig_i is passing through; • branch ℓ , selected with splitter probability w>0w>0 and reaching its terminal τi,ℓ _i, after d transitions, has terminal payoff w−1γ−dw^-1γ^-d times its coefficient (including its sign); every other described choice pays reward 00, and no common branch depth is needed because each payoff cancels its own depth; • all remaining choices use ruinous-sink completion; • sι=s0s_ =s_0. Lemma 28 (Evaluator policies). In the shared-selector evaluator of Definition 9, the following are well-defined deterministic (stationary) policies. • π0 _0 chooses a0a_0 at s0s_0 and a fixed ruinous-completed default choice at every other nonterminal state, which is unreachable under π0 _0. • For each i∈1,…,ri∈\1,…,r\, πi _i chooses aia_i at s0s_0; and for every variable xjx_j occurring in gig_i and every outcome b∈0,1b∈\0,1\, πi _i chooses di,j,bd_i,j,b at qjbq_j^b. This assignment is well-defined because a stationary policy fixes a single action per state and no variable occurs twice in one expression gig_i. Proof of Lemma 28. No prescription is repeated within one policy because no variable occurs twice in one expression. Prescriptions made by different policies need not agree. ∎ s0s_0⊥ τ1,0 _1,0τ2,0 _2,0q1q_1q11q_1^1q10q_1^0τ1,1 _1,1q2q_2q21q_2^1q20q_2^0τ2,1 _2,1a0a_0a1,12a_1,\, 12R(τ1,0)R( _1,0)a2,12a_2,\, 12R(τ2,0)R( _2,0)a1,12a_1,\, 12a2,12a_2,\, 12x1x_11−x11-x_1d1,1,0,d2,1,0d_1,1,0,d_2,1,0d1,1,1d_1,1,1d2,1,1d_2,1,1x2x_21−x21-x_2d2,2,0d_2,2,0d2,2,1d_2,2,1 Figure 6: The shared-selector evaluator of Example 2. Each branch payoff cancels that branch’s own probability and depth. Each absorbing terminal uses the payoff convention of Appendix A. Example 2 (A worked evaluator). Take n=2n=2, r=2r=2, γ=12γ= 12, g1(x)=x1−12g_1(x)=x_1- 12, and g2(x)=x1x2−14g_2(x)=x_1x_2- 14, so that −g1(x)=12−x1-g_1(x)= 12-x_1 and −g2(x)=14−x1x2-g_2(x)= 14-x_1x_2. Figure 6 shows the resulting RMDP. By Lemma 28, π0 _0 (always a0a_0), π1 _1 (choosing a1a_1 at s0s_0 and d1,1,1d_1,1,1 at q11q_1^1), and π2 _2 (choosing a2a_2 at s0s_0, d2,1,1d_2,1,1 at q11q_1^1, and d2,2,1d_2,2,1 at q21q_2^1) are all well-defined. Each constant branch reaches τi,0 _i,0 in one step with probability 1/21/2. The monomial branch of π1 _1 follows s0→q1→q11→τ1,1s_0→ q_1→ q_1^1→ _1,1, with total branch probability x1/2x_1/2 and depth three. That of π2 _2 follows s0→q1→q11→q2→q21→τ2,1s_0→ q_1→ q_1^1→ q_2→ q_2^1→ _2,1, with probability x1x2/2x_1x_2/2 and depth five. The policies share the selector q1q_1 and diverge only through their decoder actions at q11q_1^1. The monomial branches reach their terminals after depths three and five, while each constant branch has depth one. With w=12w= 12 and γ=12γ= 12, the rule R=w−1γ−d×(coefficient)R=w^-1γ^-d×(coefficient) applies at each branch’s own depth and gives R(τ1,0)=2,R(τ1,1)=−16,R(τ2,0)=1,R(τ2,1)=−64.R( _1,0)=2, R( _1,1)=-16, R( _2,0)=1, R( _2,1)=-64. The first policy consequently has value Vxπ1(s0)=γ⋅12⋅2+γ3⋅12x1(−16)=12−x1,V_x _1(s_0)=γ· 12· 2+γ^3· 12x_1(-16)= 12-x_1, and similarly Vxπ2(s0)=γ⋅12⋅1+γ5⋅12x1x2(−64)=14−x1x2,V_x _2(s_0)=γ· 12· 1+γ^5· 12x_1x_2(-64)= 14-x_1x_2, as required by −g1-g_1 and −g2-g_2. Since π0 _0 always reaches ⊥ , Vxπ0(s0)=0V_x _0(s_0)=0 for every x. Hence Δ(π0,π1,π2)=supx∈[0,1]2min(g1(x),g2(x)), _U( _0,\ _1, _2\)= _x∈[0,1]^2 (g_1(x),g_2(x) ), which is maximized at x=(1,1)x=(1,1), giving min(12,34)=12 ( 12, 34)= 12. Proof of Lemma 27. We reduce from strict elementary feasibility (Lemma 26) using the shared-selector evaluator of Definition 9 at discount γ=γ0γ= _0. Its policies π0,π1,…,πr _0, _1,…, _r are well-defined by Lemma 28. Every uncertain choice is at a selector qjq_j and has two successors, and the selectors’ choices are independent, so the construction is (s,a)(s,a)-rectangular with two-successor choices. Ordering every monomial’s selectors by increasing variable index makes the full transition graph acyclic apart from its absorbing finals. There are polynomially many selectors, decoders, and terminals, and every branch depth is polynomial, so the terminal payoffs have polynomial bit length. By construction, π0 _0 reaches only ⊥ , so Vxπ0(sι)=0V_x _0(s_ )=0. Policy πi _i realizes exactly the discounted sum of −gi-g_i’s terms, so Vxπi(sι)=−gi(x)V_x _i(s_ )=-g_i(x). Hence, with Π=π1,…,πr =\ _1,…, _r\, Δ(π0,Π)=supx∈[0,1]n(0−maxi(−gi(x)))=supx∈[0,1]nminigi(x). _U( _0, )= _x∈[0,1]^n (0- _i (-g_i(x) ) )= _x∈[0,1]^n _ig_i(x). The right side is positive exactly when the strict system is feasible and is at most zero otherwise. Hence its upper-threshold language at threshold zero is the complement of an ∃ℝ -complete problem, proving hardness. ∎ Proof of Theorem 24. Immediate from Lemmas 25 and 27. ∎ Appendix C Proofs of Theorems 1 and 5: Membership for Certification and Synthesis Bellman equations encode explicit or existentially quantified portfolio members together with a universally quantified policy. See 1 Proof. Apply Lemma 13 to the explicit input portfolio. Quantifying all memoryless randomized policies is sound because every realized discounted MDP has an optimal deterministic policy, so the encoded assertion is exactly Rreg(Π)≤tRreg( )≤ t. The given-policy problem is the case r=1r=1. ∎ See 5 Proof. Existentially quantify the k policy tables before the universal encoding of Lemma 13. Their policy-simplex constraints remain outside the universal implication, and unary k keeps the formula polynomial. The single-policy problem is the case k=1k=1. The resulting formula asserts that some portfolio of at most k members has regret at most t, whereas ρk _k is an infimum, so the two agree only when that infimum is attained. It is: the input uncertainty set is a rational polytope, hence compact, and Lemma 29 applies. ∎ Lemma 29 (Portfolio attainment). In a finite discounted RMDP with compact U, the infimum ρr=inf|Π|≤rRreg(Π) _r= _| |≤ rRreg( ) is attained. Proof. Represent a portfolio by an ordered r-tuple, repeating members when the set is smaller. This does not change its pointwise maximum, so the two infima agree. Three facts give the claim. The space of ordered r-tuples of memoryless randomized policies is a finite product of simplexes, hence compact, and U is compact by hypothesis. For a fixed discount, the Bellman system of a policy has a unique solution that depends continuously on the policy probabilities and the realization jointly, and Vu∗(sι)V_u^*(s_ ) is the maximum of finitely many such solutions, one per memoryless deterministic policy, hence also jointly continuous. Therefore f(,u)=Vu∗(sι)−maxiVuπi(sι)f( π,u)=V_u^*(s_ )- _iV_u _i(s_ ) is jointly continuous, ↦maxu∈f(,u) π _u f( π,u) is continuous, and it attains its minimum on the compact policy-tuple space. ∎ No acyclicity is needed, so the lemma applies to every input of 4 and to the synthesis RMDP of Appendix J alike. Appendix D Exact Transfer from Policy Comparison to Robust Regret Regret uses a realization-dependent best response, whereas comparison fixes both policies. The lift below makes one fixed reference optimal at every realization: it factors each source choice through a separate routing state and gives only the reference an additional bonus. We state it for an allowed-action family AallowA_ allow. For a finite portfolio, take the union of its supports. Definition 10 (Lifted RMDP). Fix an (s,a)(s,a)-rectangular source RMDP M=(S,A,,R,sι,γ0)M=(S,A,U,R,s_ , _0), a deterministic reference policy π0 _0, and a nonempty allowed-action family Aallow(s)⊆A_ allow(s) A at each s∈Ss∈ S, not necessarily containing π0(s) _0(s). Let F⊆SF S be its absorbing final states, and let cfc_f be the payoff of f∈Ff∈ F. Fix Vmax=maxs,a∈Aallow(s)∪π0(s)|R(s,a)|1−γ0,K=2Vmax+1,Λ=K1−γ0.V_ = _s,a∈ A_ allow(s)∪\ _0(s)\|R(s,a)|1- _0, K=2V_ +1, = K1- _0. Choose a rational Z of polynomial encoding length such that βZ>Λ+Vmaxβ Z> +V_ . The lifted RMDP is the tuple M^=(S^,A^,^,R^,s^ι,β) M=( S, A, U, R, s_ ,β), where • S^=xs:s∈S∪ys,a:s∈S∖F,a∈Aallow(s)∪π0(s)∪⊥r S=\x_s:s∈ S\∪\y_s,a:s∈ S F,\ a∈ A_ allow(s)∪\ _0(s)\\∪\ _ r\. There is one tag state xsx_s per source state, one selector state ys,ay_s,a for every allowed or reference action at a nonfinal source state, and one ruinous sink. • A^=A∪bonus,route A=A∪\bonus,route\ adds two fresh action symbols to the source action set. • U is (s,a)(s,a)-rectangular. At a nonfinal tag state, an allowed action a sends xsx_s to ys,ay_s,a and the bonus action sends it to ys,π0(s)y_s, _0(s). The route action at ys,ay_s,a carries exactly the original uncertainty set (s,a)U_(s,a), redirected from successors s′s to tag states xs′x_s . At a final tag xfx_f, every allowed action self-loops, as does the bonus action. • At a nonfinal tag, R^(xs,a)=R(s,a) R(x_s,a)=R(s,a) for a∈Aallow(s)a∈ A_ allow(s) and R^(xs,bonus)=R(s,π0(s))+K R(x_s,bonus)=R(s, _0(s))+K. Every route action has reward zero. At a final tag xfx_f, every allowed action has reward (1−β)cf(1-β)c_f, while the bonus action has reward (1−β)(cf+Λ)(1-β)(c_f+ ). • Every action at ⊥r _ r has reward −(1−β)Z-(1-β)Z and self-loops. Every action at xfx_f not already described also self-loops with reward −(1−β)Z-(1-β)Z. All remaining choices use ruinous-sink completion with this Z. • s^ι=xsι s_ =x_s_ . Write π^0 π_0 for the policy always choosing the bonus action. The lift π π of any memoryless randomized policy π supported on AallowA_ allow uses the same action distribution as π at each tag state and the route action at every selector state. For a finite portfolio Π=π1,…,πr =\ _1,…, _r\, write Π^=π^1,…,π^r =\ π_1,…, π_r\. s0s_0s1s_1a, 0a,\,0b,1−γ02b,\, 1- _02p1−p1-pstop, 1−γ0stop,\,1- _0 (a) Source. xs0x_s_0ys0,ay_s_0,ays0,by_s_0,bxs1x_s_1bonus,Kbonus,Kb,1−γ02b, 1- _0211p1−p1-pstop,(1−β)stop,(1-β)bonus,(1−β)(1+Λ)bonus,(1-β)(1+ ) (b) Lift. Figure 7: The source and its lifted RMDP in Example 3. Example 3 (A worked lift). Take a source RMDP with states S=s0,s1S=\s_0,s_1\, sι=s0s_ =s_0, actions A=a,b,stopA=\a,b,stop\, and discount γ0 _0. At s0s_0, action a moves deterministically to s1s_1 with reward R(s0,a)=0R(s_0,a)=0. Action b is uncertain, moving to s1s_1 with probability p and back to s0s_0 with probability 1−p1-p for any p∈[0,1]p∈[0,1], with reward R(s0,b)=1−γ02R(s_0,b)= 1- _02 regardless of outcome. At s1s_1, the only action stopstop self-loops deterministically with reward R(s1,stop)=1−γ0R(s_1,stop)=1- _0, so V(s1)=1V(s_1)=1 (Figure 7(a)). Fix reference π0(s0)=a,π0(s1)=stop _0(s_0)=a, _0(s_1)=stop and a single candidate π1(s0)=b,π1(s1)=stop _1(s_0)=b, _1(s_1)=stop, so Π=π1 =\ _1\ and Aallow(s0)=bA_ allow(s_0)=\b\, Aallow(s1)=stopA_ allow(s_1)=\stop\. Note Aallow(s0)A_ allow(s_0) does not contain π0(s0)=a _0(s_0)=a, while Aallow(s1)A_ allow(s_1) happens to coincide with π0(s1) _0(s_1). The Bellman equations give Vuπ0(s0)=γ0,Vuπ1(s0)=1−γ02+γ0p(1−γ0)+γ0p,V_u _0(s_0)= _0, V_u _1(s_0)= 1- _02+ _0p(1- _0)+ _0p, and the second value is increasing in p. Hence Δ(π0,π1)=γ0−12=161400. _U( _0,\ _1\)= _0- 12= 161400. Definition 10 gives tag states xs0,xs1x_s_0,x_s_1, selectors ys0,a,ys0,by_s_0,a,y_s_0,b, a ruinous sink, and β=19/20β=19/20 (Figure 7(b)). Because s1s_1 is an absorbing final of payoff one, the allowed and bonus actions at xs1x_s_1 self-loop with rewards 1−β1-β and (1−β)(1+Λ)(1-β)(1+ ). The selector ys0,by_s_0,b inherits the source interval for p. The relevant rewards are R(s0,a)=0,R(s0,b)=1−γ02,R(s1,stop)=1−γ0R(s_0,a)=0,R(s_0,b)= 1- _02,R(s_1,stop)=1- _0, so Definition 10 gives Vmax=1−γ01−γ0=1,K=2Vmax+1=3,Λ=K1−γ0=40013,V_ = 1- _01- _0=1, K=2V_ +1=3, = K1- _0= 40013, and Rreg(π^1)=Λ+Δ(π0,π1)=40013+161400Rreg(\ π_1\)= + _U( _0,\ _1\)= 40013+ 161400. The margin in K=2Vmax+1K=2V_ +1 is what makes the bonus action uniquely optimal at every tag state. Lemma 30 formalizes this point. Lemma 30 (Exact comparison-to-regret lift). Consider the construction of Definition 10 for a deterministic reference π0 _0 and an allowed-action family AallowA_ allow. For every memoryless randomized policy π supported on this family and every realization u, its lift satisfies Vu^π^(xs)=Vuπ(s)(s∈S).V_ u π(x_s)=V_u^π(s) (s∈ S). This construction preserves (s,a)(s,a)-rectangularity. It preserves determinism when the lifted policy is deterministic. It preserves acyclicity of the RMDP and of policy graphs, with every source absorbing final remaining an absorbing final. Each non-singleton source choice is copied unchanged to one selector state. In particular, two-successor and two-Dirac restrictions on uncertain choices are preserved. The bonus policy π^0 π_0 is pointwise optimal in every realization, and the bonus action is the unique optimal action at every tag state. Consequently, for every finite portfolio Π of policies supported on AallowA_ allow, Rreg(Π^)=Λ+Δ(π0,Π).Rreg( )= + _U( _0, ). Proof of Lemma 30. We first show that the bonus policy is optimal in the target RMDP at every realization, together with its value. Fix a realization u of the source RMDP, inducing a realization u u of the target RMDP via the redirected transitions of Definition 10. Define W(s):=Λ+Vuπ0(s)W(s):= +V_u _0(s) for every source state s, and read it as a candidate value for the tag state xsx_s. For a nonfinal source state, β2=γ0β^2= _0 means that going from xsx_s through its selector to the next tag state contributes the source discount overall. We may therefore compare W against this two-step Bellman backup directly. For the bonus action at xsx_s, the backup is R(s,π0(s))+K+γ0∑s′u(s,π0(s),s′)W(s′).R(s, _0(s))+K+ _0 _s u(s, _0(s),s )W(s ). Substituting π0 _0’s own Bellman equation Vuπ0(s)=R(s,π0(s))+γ0∑s′u(s,π0(s),s′)Vuπ0(s′)V_u _0(s)=R(s, _0(s))+ _0 _s u(s, _0(s),s )V_u _0(s ) for R(s,π0(s))R(s, _0(s)), this simplifies to Vuπ0(s)+K+γ0Λ,V_u _0(s)+K+ _0 , which equals W(s)=Λ+Vuπ0(s)W(s)= +V_u _0(s) exactly, since K=Λ(1−γ0)K= (1- _0) by definition of Λ . For any allowed action a∈Aallow(s)a∈ A_ allow(s), the same two-step backup is R(s,a)+γ0∑s′u(s,a,s′)W(s′)=R(s,a)+γ0∑s′u(s,a,s′)Vuπ0(s′)−Vuπ0(s)⏟at most 2Vmax in absolute value+Vuπ0(s)+γ0Λ.R(s,a)+ _0 _s u(s,a,s )W(s )= R(s,a)+ _0 _s u(s,a,s )V_u _0(s )-V_u _0(s)_at most 2V_ in absolute value+V_u _0(s)+ _0 . The bracketed term is at most 2Vmax2V_ because the reward is at most (1−γ0)Vmax(1- _0)V_ and both value terms are at most VmaxV_ in absolute value. Combined with (1−γ0)Λ=K=2Vmax+1(1- _0) =K=2V_ +1, the whole backup is at most W(s)−1<W(s)W(s)-1<W(s). At an absorbing final f of payoff cfc_f, the bonus backup is (1−β)(cf+Λ)+βW(f)=W(f),(1-β)(c_f+ )+β W(f)=W(f), while every allowed-action backup is (1−β)cf+βW(f)=cf+βΛ=W(f)−(1−β)Λ<W(f).(1-β)c_f+β W(f)=c_f+β =W(f)-(1-β) <W(f). Every other action at xfx_f has value below W(f)W(f) because its self-loop payoff is −Z-Z, and every undescribed choice at a nonfinal state has backup −βZ<W(s)-β Z<W(s) by the choice of Z. At selector states, the route action is likewise better than entering the ruinous sink. Thus W satisfies the Bellman optimality equation at every tag state, with the bonus action as the unique maximizer. Since the discounted Bellman optimality equation has a unique solution, W is exactly the optimal value function on tag states and the bonus policy is pointwise optimal. In particular, Vu^π^0(xs)=Λ+Vuπ0(s)V_ u π_0(x_s)= +V_u _0(s) for every source state s. For any policy π supported on AallowA_ allow, its lift π π replays π’s Bellman equation over two lifted steps at nonfinal states and uses the payoff-preserving self-loop at final states. Direct substitution using β2=γ0β^2= _0 therefore gives Vu^π^(xs)=Vuπ(s)V_ u π(x_s)=V_u^π(s) for every s. No optimality claim is needed here, only that π π’s value matches π’s under the same discount-matching substitution used above. Combining the two identities at sιs_ , Rreg(Π^) ( ) =supu^(Vu^∗(s^ι)−max1≤i≤rVu^π^i(s^ι)) = _ u (V_ u^*( s_ )- _1≤ i≤ rV_ u π_i( s_ ) ) =supu(Λ+Vuπ0(sι)−max1≤i≤rVuπi(sι)) = _u ( +V_u _0(s_ )- _1≤ i≤ rV_u _i(s_ ) ) =Λ+Δ(π0,Π), = + _U( _0, ), using pointwise optimality of the bonus policy, so Vu^∗(s^ι)=Vu^π^0(s^ι)V_ u^*( s_ )=V_ u π_0( s_ ). Every uncertain source choice occurs at one selector state, so shared choices are not copied. Products of source choice uncertainty sets remain products, which preserves (s,a)(s,a)-rectangularity. Replacing each nonfinal source edge by its two-edge tag-selector path preserves a topological order, while each final tag and the ruinous sink remains absorbing. For policy graphs the reachability qualifier in the definition of a used choice is load-bearing rather than incidental: route actions are installed at every selector state, including selectors for source actions the lifted policy never chooses, and those states are unreachable under it. Reading Gπ^G_ π as containing every transition the policy gives positive probability, instead of only its used choices, would therefore add edges that no run traverses and break the claim. This proves the stated acyclicity preservation for the full RMDP and for its policy graphs. ∎ Appendix E Proofs of Theorems 2, 3 and 4: Transferring Comparison Bounds to Certification E.1 Rectangular Given-Policy Hardness The exact lift transfers the Boolean and square-root-sum comparison bounds. See 2 Proof. For the coNP lower bound, start with Cmp(φ)Cmp( ) and apply Lift(Cmp(φ),πC)Lift(Cmp( ), _C) with singleton portfolio πK\ _K\. The source consists of deterministic policies πC,πK _C, _K in an acyclic (s,a)(s,a)-rectangular RMDP with independent two-Dirac uncertain choices, one certain uniform splitter, and discount γ0 _0, and it satisfies φ∈UNSAT⟺Δ(πC,πK)≤2−12n. _U( _C, _K)≤ 2- 12n. For the lifted candidate π^K π_K the lemma gives Rreg(π^K)=Λ+Δ(πC,πK).Rreg( π_K)= + _U( _C, _K). Thus, with the rational target threshold t^=Λ+2−12n t= +2- 12n, the lifted regret instance is a yes-instance exactly when φ∈UNSAT . The structural restrictions follow from Lemma 30, proving coNP-hardness. For the coSQRS lower bound, use the deterministic policies πu,πv _u, _v and threshold t produced by Theorem 18. That construction uses the same discount γ0 _0, is (s,a)(s,a)-rectangular, and has two-Dirac uncertain choices. Apply Lift(N,πu)Lift(N, _u) with singleton candidate πv\ _v\. Then Δ(πu,πv)≤t⟺Rreg(π^v)≤Λ+t. _U( _u, _v)≤ t ( π_v)≤ +t. Hence given-policy robust regret is coSQRS-hard. Together the two reductions prove the theorem. ∎ E.2 Rectangular Portfolio Certification The family form of the exact lift transfers the rectangular portfolio-comparison bound. See 3 Proof. The evaluator above was instantiated at γ0 _0, so apply Lemma 30 to its reference policy and explicit portfolio. The exact identity Rreg(Π^)=Λ+Δ(π0,Π)Rreg( )= + _U( _0, ) translates the zero comparison threshold to the rational regret threshold Λ . The structural conclusions are those of Lemma 30. Therefore portfolio-regret certification is ∀ℝ -hard under all restrictions stated in the theorem. ∎ E.3 General-Polytope Regret Certification Membership is the singleton case of Theorem 1. For hardness, a choice between the polynomial evaluator and zero makes regret compute the polynomial’s positive part. See 4 The membership half of Theorem 4 is the singleton-family case of Lemma 13. Polynomial-evaluation hardness. Definition 11 (Positive-part gadget). Given MfM_f from Definition 8, add a fresh initial state s+s^+ with two reward-zero actions: afa_f enters MfM_f at sfs_f, and a⊥a_ enters a zero-reward sink. Let π⊥ _ choose a⊥a_ at s+s^+. All choices left undescribed after enlarging the global action set use the same ruinous-sink completion as MfM_f. Lemma 31 (Positive-part regret). The fixed policy in Definition 11 satisfies Rreg(π⊥)=supp∈[0,1]mmaxγ0f(p),0.Rreg( _ )= _p∈[0,1]^m \ _0f(p),0\. Consequently Rreg(π⊥)≤0Rreg( _ )≤ 0 exactly when ∀p∈[0,1]m:f(p)≤0∀ p∈[0,1]^m:f(p)≤ 0. Proof. At realization p, the two initial actions have values γ0f(p) _0f(p) and zero by Lemma 22. Their positive part is precisely the shortfall of π⊥ _ . Taking the supremum proves the identity. Regret is nonnegative, so threshold zero is tight. ∎ Example 4 illustrates the zero-threshold case. Example 4. For f(p)=p−p2f(p)=p-p^2, the unique compliant policy inside MfM_f has value p−p2p-p^2 and Rreg(π⊥)=γ0maxp∈[0,1](p−p2)=γ0/4>0.Rreg( _ )= _0 _p∈[0,1](p-p^2)= _0/4>0. Thus this instance is a no-instance at threshold zero. Proof of Theorem 4. Apply Lemma 31 to the bounded universal-polynomial instances used in Lemma 23. Together with the membership encoding above, this proves the theorem. ∎ Appendix F Proof of Theorem 6: Combinatorial Minimal-Regret Hardness We prove the Boolean lower bounds for minimal robust regret. See 6 Both reductions first constrain the candidate to allowed actions. Lemma 32 makes disallowed actions ruinous and thereby transfers this restricted minimum to unrestricted synthesis within an arbitrarily small ε . F.1 Policy Restriction Fix an RMDP N, nonempty allowed action sets, and rational ε>0 >0. The construction below turns restricted synthesis into ordinary unrestricted synthesis: every disallowed choice is handed to the adversary as an extra option that can collapse straight into a state so bad that no min-regret policy will ever choose to use it. For ∈ΠMR,ΠMDP∈\ ^MR, ^MD\, write allowP_allow for the policies in P supported on the allowed actions. Definition 12 (ε -restricted RMDP). Let N=(S,A,,R,sι,γ)N=(S,A,U,R,s_ ,γ) be an RMDP and let Aallow(s)⊆A_allow(s) A be a nonempty set of allowed actions for every s∈Ss∈ S. Suppose every disallowed choice has a fixed transition distribution, i.e., (s,a)=ps,aU_(s,a)=\p_s,a\ for every s∈Ss∈ S and a∈A∖Aallow(s)a∈ A A_allow(s). Choices supplied by ruinous-sink completion satisfy this hypothesis. The construction proceeds in two steps. First it unfolds the absorbing finals of N, so that no state both self-loops and can leave. Add a fresh zero-reward absorbing sink ⊥0 _0, every action of which has reward zero and row δ⊥0\ _ _0\, and let every action be allowed there. At every absorbing final f of N, replace the reward R(f,a)R(f,a) by R(f,a)/(1−γ)R(f,a)/(1-γ) and the row by δ⊥0\ _ _0\, keeping Aallow(f)A_allow(f) as it is. An action a at f had value R(f,a)/(1−γ)R(f,a)/(1-γ) before the step, since it self-looped forever, and it collects exactly that reward once and then nothing after the step. The unfolding therefore leaves the value of every choice at f unchanged. Every state therefore keeps its value under every stationary randomized policy and every realization, so the optimal value and every robust regret are unchanged as well. The unfolding adds no uncertain choice, preserves rectangularity and acyclicity, and leaves ⊥0 _0 as the only absorbing final. It raises the largest reward magnitude to at most the largest value magnitude of N, hence multiplies VmaxV_ below by at most 1/(1−γ)1/(1-γ) and keeps every constant of polynomial encoding length. Write N for the unfolded RMDP from here on. Second, let ε>0 >0 be rational, and set Vmax=max1,maxs,a|R(s,a)|1−γ,Zε=(2−γ)Vmax+4Vmax2/εγ.V_ = \1, _s,a|R(s,a)|1-γ \, Z_ = (2-γ)V_ +4V_ ^2/ γ. The ε -restricted RMDP is the tuple Nε=(Sε,Aε,ε,Rε,sιε,γε)N_ =(S_ ,A_ ,U_ ,R_ ,s_ _ , _ ), where: • Sε=S∪⊥rS_ =S∪\ _ r\, adding one fresh ruinous sink ⊥r _ r; • Aε=A_ =A, γε=γ _ =γ, and sιε=sιs_ _ =s_ ; • Rε(s,a)=R(s,a)R_ (s,a)=R(s,a) for every s∈Ss∈ S and a∈Aa∈ A, while every action at ⊥r _ r has reward −(1−γ)Zε-(1-γ)Z_ ; • ε(s,a)=(s,a)U_ (s,a)=U(s,a) for every allowed choice, a∈Aallow(s)a∈ A_allow(s); • ε(s,a)=θps,a+(1−θ)δ⊥r:θ∈[0,1]U_ (s,a)= \θ\,p_s,a+(1-θ) _ _ r:θ∈[0,1] \ for every disallowed choice, a∈A∖Aallow(s)a∈ A A_allow(s); • every action at ⊥r _ r has row δ⊥r\ _ _ r\. The self-loop reward at ⊥r _ r gives it value −Zε-Z_ under every realization: V(⊥r)=−(1−γ)Zε+γV(⊥r)V( _ r)=-(1-γ)Z_ +γ V( _ r) forces V(⊥r)=−ZεV( _ r)=-Z_ . At the endpoint θ=1θ=1, ε(s,a)U_ (s,a) reduces to ps,a\p_s,a\, exactly N’s original choice. At θ=0θ=0, it collapses to δ⊥r\ _ _ r\, routing straight into the sink. The unfolding is what makes the interpolation safe. When N is acyclic its only self-loops sit at absorbing finals, so after the unfolding the only self-looping state is ⊥0 _0, where nothing is disallowed. Every interpolated row therefore lies between two distributions that both leave their state, and no state acquires a self-loop it did not already have. Lemma 32 (Policy restriction). For either =ΠMRP= ^MR or =ΠMDP= ^MD, infρ∈RregNε(ρ) _ρ Rreg^N_ (ρ) ≤infπ∈allowRregN(π), ≤ _π _allowRreg^N(π), infρ∈RregNε(ρ) _ρ Rreg^N_ (ρ) ≥infπ∈allowRregN(π)−ε. ≥ _π _allowRreg^N(π)- . Example 5 illustrates the transformation on two states. Example 5 (A two-state restriction). Let the source RMDP have states s and g, with s initial and g an absorbing zero-payoff terminal. At s, both the allowed action a and the disallowed action b move deterministically to g, and Aallow(s)=aA_allow(s)=\a\. In Restrict(N,Aallow,ε)Restrict(N,A_allow, ), the unfolding first sends g to the fresh zero sink ⊥0 _0 in one step, leaving its value at zero. Action a is then unchanged, while b reaches g with probability θ and ⊥r _ r with probability 1−θ1-θ, as shown in Figure 8. The allowed policy reproduces the restricted source optimum, and Lemma 32 places the unrestricted optimum in the interval from that value minus ε to that value. Thus the transformation introduces at most the promised ε gap, which is zero in this symmetric example because choosing a has regret zero. ssggaa (allowed)b (disallowed)00 (a) Before. ssgg⊥0 _0⊥r _ ra (allowed)b (disallowed)θ 1−θ1- 0000−Zε-Z_ (b) After. Figure 8: Policy restriction before and after the transformation. The allowed action remains unchanged, while nature can route the disallowed action to the ruinous sink. Proof of Lemma 32. The unfolding step changes no state’s value under any stationary policy or realization, so it changes neither RregNRreg^N nor the set of allowed policies, and N below denotes the unfolded RMDP. Fix a source realization u and let W=Vu,θ≡1∗W=V^*_u,θ≡ 1 in NεN_ . At the all-normal realization, the original states reproduce NuN_u, V(⊥r)=−ZεV( _ r)=-Z_ , and no sink-routed action improves on an original action. Thus W(s)=Vu∗(s)W(s)=V_u^*(s) for s∈Ss∈ S and W(⊥r)=−ZεW( _ r)=-Z_ . For a disallowed choice and arbitrary θ∈[0,1]θ∈[0,1], its backup at W is R(s,a)+γ(θ∑s′ps,a(s′)W(s′)+(1−θ)(−Zε))≤R(s,a)+γ∑s′ps,a(s′)W(s′),R(s,a)+γ (θ _s p_s,a(s )W(s )+(1-θ)(-Z_ ) )≤ R(s,a)+γ _s p_s,a(s )W(s ), because −Zε≤−Vmax≤mins∈SW(s)-Z_ ≤-V_ ≤ _s∈ SW(s). Allowed backups are unchanged, so the optimal Bellman operator satisfies Tu,θW≤WT_u,θW≤ W. Monotonicity and contraction give Vu,θ∗≤WV^*_u,θ≤ W. An allowed policy never uses a modified choice, hence its value is independent of θ and agrees with its value in NuN_u. Its regret is therefore maximized at θ≡1θ≡ 1, and every allowed policy has the same robust regret in N and NεN_ . This proves the upper inequality. Fix an arbitrary policy ρ and condition it on allowed actions at every state, using an arbitrary allowed action if the conditioning probability is zero. Call the result ρ¯ ρ. The conditioning is total because Aallow(s)A_allow(s) is nonempty at every state. It preserves membership in ΠMR ^MR, and it preserves determinism when =ΠMDP= ^MD. The weight below depends on the realization, so fix a source realization u∈u and argue pointwise in it, taking the supremum over u only at the end. Couple the two trajectories by reusing the same transition draw and, while an allowed action is selected, the same normalized action draw. The two trajectories then agree until ρ first chooses a nonallowed action at time τ. Put d=[γτ<∞].d=E[γ^τ1_\τ<∞\]. At the joint realization (u,θ≡1)(u,θ≡ 1), every action value, including its immediate reward and discounted continuation, lies in [−Vmax,Vmax][-V_ ,V_ ]. Conditional on the first differing choice, ρ therefore gains at most 2Vmax2V_ over ρ¯ ρ, so Vu,θ≡1ρ(sι)≤Vuρ¯(sι)+2Vmaxd,RregNε(ρ)≥Vu∗(sι)−Vuρ¯(sι)−2Vmaxd.V_u,θ≡ 1^ρ(s_ )≤ V_u ρ(s_ )+2V_ d, ^N_ (ρ)≥ V_u^*(s_ )-V_u ρ(s_ )-2V_ d. At the joint realization extending the same u with θ=0θ=0 at every nonallowed choice, the first such choice incurs loss at least γZε−(2−γ)Vmax=4Vmax2ε,γ Z_ -(2-γ)V_ = 4V_ ^2 , and therefore RregNε(ρ)≥4Vmax2εd.Rreg^N_ (ρ)≥ 4V_ ^2 d. Both endpoints are valid joint realizations extending this same u, because the modified choices are independent. If 2Vmaxd≤ε2V_ d≤ , the first bound loses at most ε . Otherwise the second exceeds 2Vmax2V_ and hence dominates every possible regret in N. Either way RregNε(ρ)≥Vu∗(sι)−Vuρ¯(sι)−ε.Rreg^N_ (ρ)≥ V_u^*(s_ )-V_u ρ(s_ )- . The left side does not depend on u, so taking the supremum over u∈u gives RregNε(ρ)≥RregN(ρ¯)−ε≥infπ∈allowRregN(π)−ε.Rreg^N_ (ρ) ^N( ρ)- ≥ _π _allowRreg^N(π)- . Taking the infimum over ρ proves the lower inequality. For B-bit rational inputs VmaxV_ and ε , the formula above gives ZεZ_ polynomial bit length in B and the model size. Each modified choice is independent, so rectangularity is preserved, and a Dirac ps,ap_s,a yields a two-Dirac segment. Acyclicity is preserved as well: after the unfolding, ⊥0 _0 is the only self-looping state of N and nothing is disallowed there, so every interpolated row leaves its state, and the two added sinks are absorbing finals. ∎ F.2 coNP-Hardness Apply the exact lift (Definition 10) to the comparison instance of Theorem 14, which builds from φ a Boolean comparison RMDP with a clause policy πC _C and a consistency policy πK _K such that Δ(πC,πK)≤2−1n if φ∈UNSAT,Δ(πC,πK)=2 if φ∈SAT. _U( _C, _K)≤ 2- 1n if , _U( _C, _K)=2 if . Take π0=πC _0= _C as the lift’s reference policy. No optimality property of πC _C is needed, only that it is the fixed policy the lift compares against. Restrict the candidates admitted by the lift to πK _K alone: at every tag state xsx_s, set Aallow(xs)=πK(s)A_allow(x_s)=\ _K(s)\, while every selector state has only its allowed routeroute action. Recall from Definition 10 that a tag state’s available actions are Aallow(s)∪bonusA_allow(s)∪\bonus\, never the reference’s own action directly. The action πC(s) _C(s) is reachable only through bonusbonus and ys,πC(s)y_s, _C(s). Thus policy restriction keeps a candidate from taking the bonus route meant only for the reference. Because AallowA_allow is a singleton at every tag state and selector states offer no choice at all, ΠallowMR ^MR_allow contains exactly one policy, the lift π^K π_K of πK _K. So there is no actual minimization left to do: writing N for this lifted RMDP, infπ∈ΠallowMRRregN(π)=RregN(π^K)=Lemma 30Λ+Δ(πC,πK), _π∈ ^MR_allowRreg^N(π)=Rreg^N( π_K) @crefcreftypecap @tilde refnumlem:exact-regret-lift= + _U( _C, _K), which is exactly Theorem 14’s gap plus the lift’s constant Λ . The certification gap transfers verbatim, with no separate minimization argument needed. The complete chained construction is Nε=Restrict(Lift(Cmp(φ),πC),Aallow,14n).N_ =Restrict (Lift(Cmp( ), _C),A_allow, 14n ). From here on write Rreg(π)Rreg(π) for RregNε(π)Rreg^N_ (π), matching Theorem 6’s notation. Lemma 32 with =ΠMRP= ^MR then converts the two cases above into φ∈UNSAT⟹infπRreg(π)≤infπ∈ΠallowMRRregN(π)≤Λ+2−1n, _πRreg(π)≤ _π∈ ^MR_allowRreg^N(π)≤ +2- 1n, φ∈SAT⟹infπRreg(π)≥infπ∈ΠallowMRRregN(π)−14n=Λ+2−14n, _πRreg(π)≥ _π∈ ^MR_allowRreg^N(π)- 14n= +2- 14n, using the lemma’s upper inequality (no slack) in the first line and its lower inequality (losing ε=14n = 14n) in the second. Since Λ+2−1n<Λ+2−12n<Λ+2−14n, +2- 1n< +2- 12n< +2- 14n, the threshold Λ+2−12n +2- 12n gives the coNP-hard part of Theorem 6. F.3 NP-Hardness The NP reduction swaps the roles of the two policies. The fixed reference now looks for a falsified clause, while the synthesized policy names a valuation whose local occurrences nature can audit. Definition 13 (Falsification and valuation verifier RMDP). For a 3-CNF formula φ=⋀i=1mCi = _i=1^mC_i over variables x1,…,xnx_1,…,x_n, the verifier RMDP is Nφ=(Sφ,Aφ,φ,Rφ,sι,γ0),N_ =(S_ ,A_ ,U_ ,R_ ,s_ , _0), with the following components. • Sφ=sι∪Sscan∪Saud∪Ssel∪⊥rS_ =\s_ \∪ S_scan∪ S_aud∪ S_sel∪\ _ r\, consisting of four verifier groups and a ruinous sink: – SscanS_scan, visited only by the falsification (scanner) policy: SF=fi,j:i∈[m],j∈1,2,3S_F=\f_i,j:i∈[m],\,j∈\1,2,3\\, for clause CiC_i and literal j, together with accFacc_F, rejFrej_F, and scanner-side padding states, fixed once the transitions below are defined. – SaudS_aud, visited only by the valuation (audit) policy: vx:x occurs in φ\v_x:x occurs in \ and, for every x, Sx,T=sx,T,ℓ=1|Ox|S_x,T=\s_x,T, \_ =1^|O_x|, Sx,F=sx,F,ℓ=1|Ox|S_x,F=\s_x,F, \_ =1^|O_x|, where x is assigned b and occurrence ℓ of OxO_x is audited (occurrences of x, fixed order), together with accKacc_K, rejKrej_K, and audit-side padding states. – Ssel=qo,t,qo,t0,qo,t1:o an occurrence,t∈T,FS_sel=\q_o,t,q_o,t^0,q_o,t^1:o an occurrence,\,t∈\T,F\\, the local-bit selectors of Definition 3, with T,FT,F in place of 1,01,0. These are the only states either policy’s transitions can lead into from the other’s territory. Let val(o)=Tval(o)=T for a positive occurrence and val(o)=Fval(o)=F for a negative occurrence, and write ¬val(o) (o) for the other Boolean value. • sιs_ has actions aFinita_F^init, leading into SscanS_scan at f1,1f_1,1, and aKinita_K^init, leading into SaudS_aud at vx1v_x_1. Within SscanS_scan: every qo,t∈Sselq_o,t∈ S_sel has a single action, whose outcome qo,t0q_o,t^0 or qo,t1q_o,t^1 is governed by φU_ below. Each selector outcome offers a scanner action aFa_F and an audit action aKa_K with the role-specific continuations described next. For o=(i,j)o=(i,j), action aFa_F at fi,jf_i,j uses the pair test of Definition 3, and its locally false outcome advances to fi,j+1f_i,j+1 or accFacc_F when j=3j=3. All other outcomes abandon the current clause, continuing to fi+1,1f_i+1,1, or to rejFrej_F if i=mi=m. Within SaudS_aud: every vxv_x offers actions T,FT,F leading to sx,T,1,sx,F,1s_x,T,1,s_x,F,1. The controls sx,b,ℓs_x,b, implement the audit chain of Definition 3; after its last occurrence, the chain continues to the next variable or to accKacc_K. Fix H at least as long as the longest path in either graph just described. The scanner-side and audit-side padding states each consist of fresh states inserted along every shorter path in their own graph so it also reaches its terminal after exactly H transitions, each with a single reward-free action continuing toward that terminal. • φU_ is the product of the local-bit segments in Equation 2, with T,FT,F in place of 1,01,0. All remaining described choices are singletons. • accFacc_F is the terminal with payoff γ0−H _0^-H and accKacc_K the terminal with payoff −γ0−H- _0^-H, while every other described reward, including at rejFrej_F and rejKrej_K, is zero. • All remaining choices use ruinous-sink completion. • The initial state is sιs_ and the discount is the appendix-wide γ0 _0. Variables with no occurrence are removed. Since φU_ is a product of two-Dirac segments, its vertices are exactly the Boolean assignments to the local bits bo,t\b_o,t\. Figures 9 and 6 illustrate the verifier RMDP and the two policy paths through its shared selectors. Definition 14 (Falsification and valuation policies). For the verifier RMDP of Definition 13, define πF(sι) _F(s_ ) =aFinit, =a_F^init, πF(s) _F(s) =aF(s) =a_F(s) (s∈SF), (s∈ S_F), πF(qo,tb) _F(q_o,t^b) =aF(qo,tb), =a_F(q_o,t^b), Kσ(sι) K_σ(s_ ) =aKinit, =a_K^init, Kσ(vx)(b) K_σ(v_x)(b) =σx(b), = _x(b), Kσ(s) K_σ(s) =ax,b(s) =a_x,b(s) (s∈Sx,b), (s∈ S_x,b), Kσ(qo,tb) K_σ(q_o,t^b) =aK(qo,tb). =a_K(q_o,t^b). On decision states outside their reachable verifier graphs, fix default actions whose otherwise undescribed choices use ruinous-sink completion. For a valuation α, the deterministic policy KαK_α is obtained from σx(T)=α(x) _x(T)=α(x) and σx(F)=1−α(x) _x(F)=1-α(x). At a Boolean realization, a vertex of φU_ , every selector sends its unique action to a fixed outcome, so a deterministic policy follows a single path. We say the policy accepts that realization when this path reaches its accepting terminal, accFacc_F for πF _F or accKacc_K for KαK_α. Thus πF _F accepts exactly when some clause is locally false, while KσK_σ audits the value selected at each vxv_x. The common depth and terminal payoffs satisfy Lemma 10, so the comparison value is the sum of the two acceptance probabilities. SscanS_scanSselS_selSaudS_audsιs_ f1,1f_1,1f1,2f_1,2f1,3f_1,3accFacc_Fγ0−H _0^-Hvx1v_x_1vx2v_x_2vx3v_x_3accKacc_K−γ0−H- _0^-Hq(1,1),Tq_(1,1),Tq(1,1),Fq_(1,1),Fq(1,2),Fq_(1,2),Fq(1,2),Tq_(1,2),Tq(1,3),Tq_(1,3),Tq(1,3),Fq_(1,3),FaFinita_F^initaKinita_K^init001100110011x1=Fx_1=F Figure 9: The verifier RMDP of Definition 13 for φ=(x1∨¬x2∨x3)∧(¬x1∨x2∨x3) =(x_1 x_2 x_3) ( x_1 x_2 x_3), showing the four state groups. For each literal of C1C_1, the scanner first reads the value that would make it true; only outcome 00 followed by outcome 11 at the opposite-value selector confirms that it is locally false. The displayed 0,10,1 paths advance through the three literals and then accept; every other outcome abandons C1C_1. The auditor policy KαK_α walks vx1,vx2,vx3v_x_1,v_x_2,v_x_3 and, having assigned a value to each variable, checks its occurrences. Dotted edges summarize audit reads of the shared selectors: the scanner and the auditor of x1=Fx_1=F read the same q(1,1),Fq_(1,1),F, coupling their acceptances. The remaining occurrences, both clauses, and the depth-H padding follow the same pattern. Example 6. For φ=(x1∨¬x2∨x3)∧(¬x1∨x2∨x3) =(x_1 x_2 x_3) ( x_1 x_2 x_3), the valuation (x1,x2,x3)=(1,1,0)(x_1,x_2,x_3)=(1,1,0) satisfies φ , so an accepting valuation audit precludes falsification. By contrast, (0,1,0)(0,1,0) falsifies the first clause, and its canonical local pairs make both verifiers accept. Lemma 33 (Verifier separation). Consider the verifier RMDP and policies of Definitions 13 and 14. At every Boolean realization at which πF _F and KαK_α both accept, α falsifies a clause of φ . Conversely, if α falsifies a clause of φ , then there exists a Boolean realization at which both accept. In particular, if α satisfies φ , the two acceptance events are disjoint at every realization. Proof. Fix a Boolean realization and suppose KαK_α accepts at it. Then every variable set true by α has bo,T=1b_o,T=1 at each occurrence, and every variable set false has bo,F=1b_o,F=1. In every clause satisfied by α, a true positive literal therefore cannot have the false pair (0,1)(0,1), and a true negative literal cannot have (1,0)(1,0). Hence no clause satisfied by α is locally false in all three positions. This also covers malformed pairs (0,0)(0,0) and (1,1)(1,1). Since πF _F accepts only by finding a clause that is locally false in all three positions, its acceptance at the same realization exhibits a clause that α falsifies. The same argument read contrapositively gives the disjointness claim for satisfying α. For the converse, let α falsify a clause and let nature use the canonical pair (1,0)(1,0) for true variables and (0,1)(0,1) for false variables. At that realization KαK_α accepts all of its audits and every literal of the falsified clause is locally false, so πF _F accepts as well. Only existence is claimed here, since another realization may make some audit fail. ∎ For a randomized valuation policy, put Gφ(σ)=supu(VuπF(sι)−VuKσ(sι)).G_ (σ)= _u (V_u _F(s_ )-V_u^K_σ(s_ ) ). At a vertex, acceptance by πF _F contributes one and acceptance by KσK_σ contributes another one to this difference. Lemma 34 (Verifier gap). For the verifier RMDP and policies of Definitions 13 and 14, the following gap holds. If φ is satisfiable, some deterministic valuation policy has Gφ≤1G_ ≤ 1. If φ is unsatisfiable, every randomized valuation policy has Gφ≥1+2−nG_ ≥ 1+2^-n. Proof. For a satisfying α, Lemma 33 bounds the difference by one at every vertex. Both policy graphs are acyclic and visit each local selector at most once, so Lemma 17 extends the bound to the entire product polytope. Now fix σ for an unsatisfiable formula. At each of the n variable states, choose a most probable action. These actions form a valuation α. Since every such state is visited exactly once, KσK_σ follows that complete valuation with probability at least δ=2−nδ=2^-n. Use the canonical realization for α. The formula has a clause falsified by α, so πF _F accepts with probability one and KσK_σ with probability at least δ. Thus Gφ(σ)≥1+δG_ (σ)≥ 1+δ. ∎ We now transfer the verifier gap to minimal robust regret while preventing the synthesized policy from leaving the valuation graph. Apply Lemma 30 with πF _F as reference. At variable states allow T,F\T,F\, at verifier states allow the unique action of KσK_σ, and at source states used only by πF _F allow their unique action. The lifted allowed policies are precisely the valuation policies and RregN(Kσ)=Λ+Gφ(σ).Rreg^N(K_σ)= +G_ (σ). Equivalently, the target is Restrict(Lift(Nφ,πF),Aallow,2−n/4)Restrict(Lift(N_ , _F),A_allow,2^-n/4), where NφN_ is the verifier RMDP of Definition 13. The disallowed bonus choices are singletons, so Lemma 32 applies with =ΠMRP= ^MR. The gap of Lemma 34 becomes φ∈SAT⟹infπRreg(π)≤Λ+1,φ∈UNSAT⟹infπRreg(π)≥Λ+1+342−n. _πRreg(π)≤ +1, _πRreg(π)≥ +1+ 342^-n. Threshold Λ+1+2−n−1 +1+2^-n-1 proves NP-hardness. Proof. The construction in the coNP subsection is a polynomial reduction from UNSAT, and the construction in the NP subsection is a polynomial reduction from SAT. Their structural restrictions follow from the source verifiers, Lemma 30, and Lemma 32. The rational gaps above leave a valid separating threshold after the restriction loss. Minimal robust regret is therefore both NP-hard and coNP-hard under the restrictions stated in the theorem. ∎ Appendix G Deterministic Minimal-Regret Complexity We first establish membership and then give the matching hardness construction. G.1 Acyclic Deterministic Membership Lemma 35. Minimal robust regret over memoryless deterministic policies is in Σ2p _2^p on acyclic (s,a)(s,a)-rectangular polytopic RMDPs. Proof. Fix an acyclic RMDP. For any uncertainty realization, ordinary finite discounted-MDP optimality gives Vu∗(s)=maxπ′∈ΠMDVuπ′(s).V_u^*(s)= _π ∈ ^MDV_u^π (s). Indeed, process decision states in reverse topological order and select a maximizing action. No history-dependent or randomized policy can improve the resulting backward-induction value. For every deterministic candidate π, Rreg(π) (π) =supumaxπ′∈ΠMD(Vuπ′(sι)−Vuπ(sι)) = _u _π ∈ ^MD (V_u^π (s_ )-V_u^π(s_ ) ) =maxsupuπ′∈ΠMD(Vuπ′(sι)−Vuπ(sι)). = _π ∈ ^MD _u (V_u^π (s_ )-V_u^π(s_ ) ). Acyclicity makes every policy pair cycle-free on its shared choices, the only self-loops being those at absorbing finals, which Definition 5 omits. By Lemma 17, the remaining supremum is attained at one vertex of every choice uncertainty set. Therefore Rreg(π)≤t⇔∀π′∈ΠMD∀v∈∏s,avert(s,a):Vvπ′(sι)−Vvπ(sι)≤t.Rreg(π)≤ t ∀π ∈ ^MD\ ∀ v∈ _s,avert(U_s,a):V_v^π (s_ )-V_v^π(s_ )≤ t. The existential certificate is the action table of π. The universal certificate contains the action table of π′π and, for every choice uncertainty set, a vertex represented by linearly independent tight input facets plus its rational coordinates. Cramer’s rule gives polynomial bit length. The predicate verifies the facets and evaluates both policies by exact backward induction in polynomial time. Thus the decision problem has an existential polynomial certificate followed by a universal polynomial certificate with a polynomial-time predicate, placing it in Σ2p _2^p. ∎ G.2 Σ2p _2^p-Hardness over Deterministic Policies Reduce from the canonical Σ2p _2^p-complete problem (16) of deciding whether ∃x∈0,1n∀y∈0,1m:ψ(x,y),∃ x∈\0,1\^n\ ∀ y∈\0,1\^m: ψ(x,y), where ψ is a 3-DNF. Definition 15 (Universal falsification reference). Write ψ=⋁i=1rDiψ= _i=1^rD_i, where every DiD_i is a conjunction of three literals. Decide constant cases directly, remove universal variables with no occurrence, and order every variable’s occurrences by term and then position. If necessary, add one unused existential variable so that n≥1n≥ 1. For an occurrence o, let val(o)∈T,Fval(o)∈\T,F\ be the value making its literal true. The universal falsification RMDP is Nψ=(Sψ,Aψ,ψ,Rψ,sι,γ0),N_ψ=(S_ψ,A_ψ,U_ψ,R_ψ,s_ , _0), with the following components. • SψS_ψ contains the initial state and one candidate branch-entry state per variable, r1K,…,rnK∪r1Y,…,rmY.\r^K_1,…,r^K_n\∪\r^Y_1,…,r^Y_m\. It contains a global selector qYjq_Y_j with outcomes qYjT,qYjFq_Y_j^T,q_Y_j^F for every universal variable, and the shared local-bit selector of Definition 3 for every occurrence o and c∈T,Fc∈\T,F\. • The reference-side controls are the term-scan states fi,hf_i,h. The candidate-side controls are the decision states vxiv_x_i, the existential audit states ki,c,ℓxk^x_i,c, , and the universal audit states kj,c,ℓyk^y_j,c, . There are also accepting, rejecting, padding, and zero-reward terminal states, together with the ruinous sink supplied below. • At sιs_ , action aFinita_F^init leads deterministically to the scanner entry f1,1f_1,1, and action aKinita_K^init has the certain uniform distribution over the n+mn+m branch-entry states. • State rjYr^Y_j leads to qYjq_Y_j. Outcome qYjcq_Y_j^c leads to kj,c,1yk^y_j,c,1, which implements the audit chain of Definition 3 for the occurrences of yjy_j in term-major order. A universal branch therefore offers the candidate no choice, the committed value being nature’s. • State riKr^K_i leads to vxiv_x_i. At vxiv_x_i, actions T and F enter the corresponding chain ki,c,1xk^x_i,c,1. That control implements the same audit chain for the occurrences of xix_i in term-major order. If xix_i has no occurrence, both actions at vxiv_x_i accept immediately. • At occurrence o=(i,h)o=(i,h), the term scanner uses the pair test of Definition 3; its locally false outcome advances to fi+1,1f_i+1,1, or accepts if i=ri=r. Every other outcome advances to fi,h+1f_i,h+1, or rejects if h=3h=3. • Every selector has one described action. At a shared local outcome, one described action takes the scanner continuation and another takes the audit continuation. Since the two audit families lie behind aKinita_K^init and the scanner behind aFinita_F^init, a policy that plays one of those initial actions needs only one of the two continuations, and each continuation is determined by the outcome state itself. All paths are padded so that acceptance or rejection occurs after a common depth H. • ψU_ψ is the product of the local-bit segments in Equation 2 and analogous segments for the global selectors qYjq_Y_j. The initial splitter of aKinita_K^init is certain and uniform, and all remaining described choices are singletons. • Before ruinous-sink completion, RψR_ψ is zero except at padded acceptance terminals. Every reference-side accepting terminal has payoff γ0−H _0^-H, every candidate-side accepting terminal has payoff −γ0−H- _0^-H, and every rejecting terminal has payoff zero. • All remaining choices use ruinous-sink completion. • The initial state is sιs_ and the discount is the appendix-wide γ0 _0. Definition 16 (Universal falsification policies). For the RMDP of Definition 15, the fixed deterministic reference πF _F takes aFinita_F^init and then uses the pair-test scanner action throughout. The synthesized deterministic policy KαK_α takes aKinita_K^init, chooses α(xi)α(x_i) at every vxiv_x_i, and follows the audit action for the committed value at every audit state, that value being α(xi)α(x_i) on an existential branch and nature’s selection at qYjq_Y_j on a universal one. Each policy therefore carries one role: the reference scans and the candidate audits. At states outside a policy’s reachable graph, fix default actions whose undescribed choices use ruinous-sink completion. By Lemma 10, the value difference is the sum of the reference and candidate acceptance probabilities. Lemma (Unambiguous verifier policies). The policies in Definition 16 are stationary and deterministic, and no run of either policy visits a local selector twice. Proof. The candidate’s certain uniform splitter chooses one branch. An audit commits to one value before visiting one variable’s occurrences in term-major order, while the term scanner visits the two selectors of each occurrence in their fixed pair-test order. Every occurrence belongs to one variable, so the audit reaching a given selector is unique, and the scanner reaches each selector once. Since every audit belongs to KαK_α and every scan to πF _F, no state asks either policy to distinguish the branch by which it was reached, and one action per state suffices. ∎ Ignoring final self-loops, the full RMDP is acyclic. A topological order places sιs_ first, then the branch-entry states, the global selectors Y1,…,YmY_1,…,Y_m, the decision states vx1,…,vxnv_x_1,…,v_x_n, the occurrence selectors in term-major order with their associated controls and outcomes, and finally the padding, terminal, and ruinous-sink states. For a valuation α of x, write Gψ(α)=supu(VuπF(sι)−VuKα(sι)).G_ψ(α)= _u (V_u _F(s_ )-V_u^K_α(s_ ) ). Lemma 36 (DNF dichotomy). Let M=n+mM=n+m. For every α, if ∀y:ψ(α,y)∀ y:ψ(α,y) then Gψ(α)≤2−1MG_ψ(α)≤ 2- 1M, while if ∃y:¬ψ(α,y)∃ y: ψ(α,y) then Gψ(α)=2G_ψ(α)=2. Proof. At a Boolean vertex, let AjA_j be the event that the yjy_j audit passes, let B be the event that the term scanner passes, and let CiC_i be the event that the xix_i audit against α(xi)α(x_i) passes. The reference reaches its single scanner branch with probability one, while the candidate’s splitter gives each of the n+mn+m audit branches weight 1n+m 1n+m, so the padding and terminal rewards give DπF,Kα=B+|j:Aj|+|i:Ci|n+m.D_ _F,K_α=1_\B\+ |\j:A_j\|+|\i:C_i\|n+m. If ∃y:¬ψ(α,y)∃ y: ψ(α,y), the canonical local pairs for (α,y)(α,y) and the global choices Yj=yjY_j=y_j make every event hold. This gives value two, which is also the largest possible value. Now suppose ∀y:ψ(α,y)∀ y:ψ(α,y). All events cannot hold at once. Indeed, if every audit passes, set yj=Yjy_j=Y_j. Whenever the pair test declares an occurrence locally false, its value-certifying bit is zero, while the passing audit forces the bit indexed by the committed variable value to one. The committed value therefore makes that literal false. Event B would then give a false literal in every DNF term, contradicting ψ(α,y)ψ(α,y). At least one event fails, and its weight is at least min1,1n+m=1M. \1, 1n+m \= 1M. Thus every vertex has value at most 2−1M2- 1M. No run repeats an uncertain choice, so Lemma 17 extends the bound to the full product polytope. ∎ Lemma 37. Minimal robust regret over ΠMD ^MD is Σ2p _2^p-hard on acyclic (s,a)(s,a)-rectangular RMDPs in which every uncertain choice is two-Dirac and the only other stochastic rows are certain uniform splitters. Proof. Set M=n+mM=n+m. By Lemma 36, a yes-instance has some KαK_α with Gψ(α)≤2−1MG_ψ(α)≤ 2- 1M, while every KαK_α in a no-instance has Gψ(α)=2G_ψ(α)=2. Apply the exact lift with reference πF _F. At existential variable states allow T,F\T,F\. At every other state allow the unique action used by the synthesized verifier, and at internal states used only by πF _F take Aallow(s)=πF(s)A_ allow(s)=\ _F(s)\. Thus every allowed set is nonempty. At a shared local outcome this allows the audit action and not the scanner action, which costs the reference nothing: by Definition 10 the lift replays πF _F through the bonus action rather than through AallowA_ allow. The allowed deterministic policies therefore have minimal regret at most Λ+2−1M +2- 1M in yes-instances and exactly Λ+2 +2 in no-instances. The composed target is Restrict(Lift(Nψ,πF),Aallow,14M).Restrict (Lift(N_ψ, _F),A_allow, 14M ). Apply Lemma 32 with =ΠMDP= ^MD. The disallowed bonus choices are singletons. In yes-instances the unrestricted minimum is at most Λ+2−1M +2- 1M, while in no-instances it is at least Λ+2−14M +2- 14M. Since Λ+2−1M<Λ+2−12M<Λ+2−14M, +2- 1M< +2- 12M< +2- 14M, threshold Λ+2−12M +2- 12M separates the cases. The structural restrictions follow from Lemmas 30 and 32, whose unfolding step is what keeps the composed target acyclic. ∎ Theorem 38. Minimal robust regret over memoryless deterministic policies is Σ2p _2^p-complete on acyclic (s,a)(s,a)-rectangular polytopic RMDPs. Hardness already holds when every uncertain choice is two-Dirac and the only other stochastic rows are certain uniform splitters. Proof of Theorem 38. Membership is Lemma 35. Hardness is Lemma 37. ∎ Appendix H Proof of Theorem 7: Signed Square-Root-Sum Hardness The source problem ± SQRS_± gives two lists of positive integers and asks, in its non-strict forward direction, whether ∑iai≤∑jbj. _i a_i≤ _j b_j. The reduction represents each square root by a one-state gadget whose regret balances a decreasing term against an increasing term in the policy’s mixing probability. The optimum is therefore the solution of a quadratic equation and is generally irrational. See 7 H.1 One-State Balancing s⊥ ,RLL,R_LR,R,R_RpLp_LpRp_R1−pL1-p_L1−pR1-p_R00 Figure 10: The one-state balancing gadget has independent choices pL,pR∈[0,h]p_L,p_R∈[0,h] and a zero-reward sink. Definition 17 (One-state balancing gadget). Fix q∈(0,1)q∈(0,1) and γ∈(1−q,1)γ∈(1-q,1), and put h=(1−q)/γh=(1-q)/γ. The one-state balancing RMDP shown in Figure 10 is G=(S,A,,R,s,γ),G=(S,A,U,R,s,γ), with the following components. • S=s,⊥S=\s, \, where ⊥ is a zero-reward sink. • The global action set is L,R\L,R\. At ⊥ , both actions have a zero-reward Dirac self-loop. • U is the product of the independent uncertainty sets (s,L)=pLδs+(1−pL)δ⊥:pL∈[0,h],(s,R)=pRδs+(1−pR)δ⊥:pR∈[0,h].U_(s,L)=\p_L _s+(1-p_L) _ :p_L∈[0,h]\, _(s,R)=\p_R _s+(1-p_R) _ :p_R∈[0,h]\. • R assigns rewards RLR_L and R_R to actions L and R at s, respectively, and assigns zero reward at ⊥ . • The initial state is s and the discount is the local parameter γ. The condition γ>1−qγ>1-q is exactly h<1h<1, so these are valid transition probabilities. Write dL=1−γpLd_L=1-γ p_L and dR=1−γpRd_R=1-γ p_R. Both range over [q,1][q,1]. For the gadget of Definition 17, the two parametrizations below choose (RL,R)(R_L,R_R) so that its minimal robust regret realizes the signed square-root forms m+m_+ and m−m_- summed by the ± SQRS_± reduction. For A,B>0A,B>0, put D=A+BD=A+B. The positive-reward parametrization is rL=q(A+qB)1−q2,rR=q(B+qA)1−q2,(RL,R)=(rL,rR),r_L= q(A+qB)1-q^2, r_R= q(B+qA)1-q^2, (R_L,R_R)=(r_L,r_R), and define m+(A,B)=D−D2−4(1−q2)AB2(1−q2).m_+(A,B)= D- D^2-4(1-q^2)AB2(1-q^2). The negative-reward parametrization is ℓ=B+qA1−q2,r=A+qB1−q2,(RL,R)=(−ℓ,−r), = B+qA1-q^2, r= A+qB1-q^2, (R_L,R_R)=(- ,-r), and define m−(A,B)=q2D2+4(1−q2)AB−qD2(1−q2).m_-(A,B)= q^2D^2+4(1-q^2)AB-qD2(1-q^2). Lemma 39 (One-state balancing gadgets). The positive-reward parametrization has minimal robust regret m+(A,B)m_+(A,B). If q2≥1/2q^2≥ 1/2, the negative-reward parametrization has minimal robust regret m−(A,B)m_-(A,B). Proof. A memoryless randomized policy in this gadget is determined by one number x∈[0,1]x∈[0,1], the probability of playing L at s. First, consider the positive-reward form. For fixed dL,dR∈[q,1]d_L,d_R∈[q,1], VL=rLdL,VR=rRdR,Vx=xrL+(1−x)rRxdL+(1−x)dR.V_L= r_Ld_L, V_R= r_Rd_R, V_x= xr_L+(1-x)r_Rxd_L+(1-x)d_R. A direct calculation gives VL−Vx=(1−x)(rLdR−rRdL)dL(xdL+(1−x)dR)V_L-V_x= (1-x)(r_Ld_R-r_Rd_L)d_L(xd_L+(1-x)d_R) and VR−Vx=x(rRdL−rLdR)dR(xdL+(1−x)dR).V_R-V_x= x(r_Rd_L-r_Ld_R)d_R(xd_L+(1-x)d_R). On the region VL≥VRV_L≥ V_R, the first expression is decreasing in dLd_L and increasing in dRd_R, so its maximum is attained at dL=q,dR=1d_L=q,d_R=1. Since rLq−rR=A, r_Lq-r_R=A, this maximum is A(1−x)1−(1−q)x. A(1-x)1-(1-q)x. Similarly, on the region VR≥VLV_R≥ V_L, the second expression is maximized at dL=1,dR=qd_L=1,d_R=q. Since rRq−rL=B, r_Rq-r_L=B, this maximum is Bxq+(1−q)x. Bxq+(1-q)x. Thus Rreg(x)=maxA(1−x)1−(1−q)x,Bxq+(1−q)x.Rreg(x)= \ A(1-x)1-(1-q)x, Bxq+(1-q)x \. The first term is strictly decreasing in x, and the second is strictly increasing in x. Hence the minimum is attained when the two terms are equal. If the common value is y, then (1−q2)y2−Dy+AB=0,D=A+B.(1-q^2)y^2-Dy+AB=0, D=A+B. The smaller root gives the claimed value. For the negative-reward form the same two-region split applies, now with VL=−ℓ/dLV_L=- /d_L and VR=−r/dRV_R=-r/d_R. The conditions A,B>0A,B>0 are equivalent to r−qℓ=A>0,ℓ−qr=B>0,r-q =A>0, -qr=B>0, and imply q<r/ℓ<1/q<r/ <1/q. For VL−VxV_L-V_x, set z=dR/dL∈[q,1/q]z=d_R/d_L∈[q,1/q]. On z∈[q,1]z∈[q,1], minimizing the feasible dLd_L gives (1−x)z(r−ℓz)q(x+(1−x)z) (1-x)z(r- z)q(x+(1-x)z), whose derivative has numerator x(r−2ℓz)−(1−x)ℓz2≤0x(r-2 z)-(1-x) z^2≤ 0 because z≥qz≥ q, r/ℓ<1/qr/ <1/q, and q2≥1/2q^2≥ 1/2. On z∈[1,1/q]z∈[1,1/q], the corresponding expression (1−x)(r−ℓz)q(x+(1−x)z) (1-x)(r- z)q(x+(1-x)z) is strictly decreasing. Thus the maximum occurs at z=qz=q, namely dL=1,dR=qd_L=1,d_R=q, and equals A(1−x)/(q+(1−q)x)A(1-x)/(q+(1-q)x). By symmetry the other region contributes Bx/(1−(1−q)x)Bx/(1-(1-q)x). Hence Rreg(x)=maxA(1−x)q+(1−q)x,Bx1−(1−q)x.Rreg(x)= \ A(1-x)q+(1-q)x, Bx1-(1-q)x \. Balancing the decreasing and increasing terms gives (1−q2)y2+qDy−AB=0(1-q^2)y^2+qDy-AB=0. Its positive root is m−(A,B)m_-(A,B). ∎ H.2 Rational Square-Root Gadgets Lemma 40 (Local gadget for a negative square-root coefficient). For every integer b≥2b≥ 2, one can compute in polynomial time rational numbers qb,Db,Ab,Bbq_b,D_b,A_b,B_b such that, for any γ∈(1−qb,1)γ∈(1-q_b,1), the positive-reward balancing gadget of Lemma 39, after a rational reward scaling, has minimal robust regret of Db−b.D_b- b. Proof. Choose a rational number η∈(b−1,b−1)η∈( b-1, b-1). The interval has length greater than 1/21/2 for b≥2b≥ 2, so scanning a constant-denominator dyadic grid finds such an η. Both endpoint tests use exact rational square comparisons. Thus η has O(logb)O( b) bits and is found in polynomial time. Define qb=b−1−η22η,Nb=η+b−1η2,Db=Nbqb. q_b= b-1-η^22η, N_b= η+ b-1η2, D_b= N_bq_b. The upper bound on η gives qb>0q_b>0, while η>b−1η> b-1 is equivalent to qb<1q_b<1. Direct expansion gives Nb2−qb2=b−1N_b^2-q_b^2=b-1. Hence Nb>qbN_b>q_b, so Db>1D_b>1. Hence, qb2Db2+1−qb2=bq_b^2D_b^2+1-q_b^2=b. Now set Ab=Db+12,Bb=Db−12.A_b= D_b+12, B_b= D_b-12. Then Ab,Bb>0A_b,B_b>0, Ab+Bb=DbA_b+B_b=D_b, and Db2−4(1−qb2)AbBb D_b^2-4(1-q_b^2)A_bB_b =Db2−(1−qb2)(Db2−1) =D_b^2-(1-q_b^2)(D_b^2-1) =qb2Db2+1−qb2 =q_b^2D_b^2+1-q_b^2 =b. =b. By Lemma 39, the unscaled positive-reward gadget has minimal robust regret Db−b2(1−qb2). D_b- b2(1-q_b^2). Scaling all rewards by 2(1−qb2)2(1-q_b^2) gives the value Db−bD_b- b. Moreover Db2=1+(b−1)/qb2>bD_b^2=1+(b-1)/q_b^2>b, so this local regret is positive. All rational operations preserve polynomial bit length. ∎ Example 7 instantiates the construction at b=2b=2. Example 7 (The gadget for b=2b=2). Take η=1/2η=1/2. Then q2=3/4q_2=3/4, N2=5/4N_2=5/4, and D2=5/3D_2=5/3, with N22−q22=1=b−1N_2^2-q_2^2=1=b-1. After the prescribed reward scaling, the local minimal regret is 5/3−25/3- 2. Lemma 41 (Local gadget for a positive square-root coefficient). For every integer b≥2b≥ 2, one can compute in polynomial time a rational constant CbC_b and a negative-reward (s,a)(s,a)-rectangular gadget such that, for any γ∈(15,1)γ∈( 15,1), its minimal robust regret is b−Cb. b-C_b. Proof. Choose a rational number m such that 2b3<m2<b. 2b3<m^2<b. The interval (2b/3,b)( 2b/3, b) has width at least 2(1−2/3) 2(1- 2/3). Scanning dyadics of polynomial bit length with rational square comparisons therefore finds m in polynomial time. Define D=m+bm2,c=bm−m2.D= m+ bm2, c= bm-m2. Then D,c∈ℚD,c , c>0c>0, and D2−c2=bD^2-c^2=b. Moreover, cD=b−m2b+m2<15. cD= b-m^2b+m^2< 15. Set q=45,E=53c,A=D+E2,B=D−E2. q= 45, E= 53c, A= D+E2, B= D-E2. Since ED<13 ED< 13, we have A,B>0A,B>0. Also A+B=DA+B=D, and because 1−q2=9251-q^2= 925, we have q2D2+4(1−q2)AB q^2D^2+4(1-q^2)AB =q2D2+(1−q2)(D2−E2) =q^2D^2+(1-q^2)(D^2-E^2) =D2−(1−q2)E2 =D^2-(1-q^2)E^2 =D2−c2 =D^2-c^2 =b. =b. Finally, cD<15 cD< 15 implies D2=b+c2<25b24D^2=b+c^2< 25b24, and therefore q2D2<bq^2D^2<b. Thus qD<bqD< b. Now use the negative-reward form of Lemma 39 with these q,A,B,Dq,A,B,D. Its unscaled minimal robust regret is b−qD2(1−q2). b-qD2(1-q^2). Scaling all rewards by 2(1−q2)2(1-q^2) gives minimal robust regret b−qD b-qD. Set Cb=qDC_b=qD. The strict inequality qD<bqD< b proved above makes this local regret positive, and all parameters have polynomial binary length. ∎ sins_inH1H_1H2H_2⋯·sHnH_n1/n1/n1/n1/n1/n1/n Figure 11: Additive splitter for minimal regret. H.3 Additive Composition Definition 18 (Additive splitter). Let H1,…,HnH_1,…,H_n be disjoint (s,a)(s,a)-rectangular gadgets with common discount γ, entry states sis_i, local regrets RregHiRreg_H_i, and mutually independent uncertainty sets. Add a zero-reward initial certain uniform splitter sins_in whose only action enters each sis_i with probability 1/n1/n, and scale every reward in every HiH_i by n/γn/γ (Figure 11). After scaling, every remaining choice uses ruinous-sink completion. Denote the resulting RMDP, whose uncertainty set is the product of the local sets, by H. Lemma 42 (Additive composition for minimal regret). If mi=infπi∈ΠMRRregHi(πi)m_i= _ _i∈ ^MRRreg_H_i( _i), then the additive splitter of Definition 18 satisfies infπ∈ΠMRRregH(π)=∑i=1nmi. _π∈ ^MRRreg_H(π)= _i=1^nm_i. Proof. For a global policy π, let πi _i be its restriction to HiH_i. For any competing policy π∗π^* and any rectangular uncertainty realization =(1,…,n) u=( u_1,…, u_n), the Bellman equation at the certain uniform splitter has value Vπ∗(sin)−Vπ(sin) V^π^*_ u(s_in)-V^π_ u(s_in) =γ∑i=1n1nnγ(Viπi∗(si)−Viπi(si))=∑i=1n(Viπi∗(si)−Viπi(si)). =γ _i=1^n 1n nγ (V _i^*_ u_i(s_i)-V _i_ u_i(s_i) )= _i=1^n (V _i^*_ u_i(s_i)-V _i_ u_i(s_i) ). The local uncertainty sets are independent and the competing policy can be chosen independently inside the disjoint gadgets. Hence RregH(π)=∑i=1nRregHi(πi).Rreg_H(π)= _i=1^nRreg_H_i( _i). Taking the infimum over the product of the local policy simplexes proves the claim. By Lemma 11, every ruinous choice is strictly worse than a described local one, so adding the global action alphabet creates no further minimizer or comparator. The construction preserves (s,a)(s,a)-rectangularity. ∎ H.4 Proof of Theorem 7 Proof of Theorem 7. Reduce from the non-strict ≤ direction of ± SQRS_±. Given two lists a1,…,ama_1,…,a_m and b1,…,bnb_1,…,b_n, we construct in polynomial time an (s,a)(s,a)-rectangular RMDP M and a rational threshold t such that infπ∈ΠMRRregM(π)≤t _π∈ ^MRRreg_M(π)≤ t if and only if ∑i=1mai≤∑j=1nbj. _i=1^m a_i≤ _j=1^n b_j. The reversed non-strict comparison uses the same construction after swapping the two lists. Let I=i∣ai≥2I=\i a_i≥ 2\, J=j∣bj≥2J=\j b_j≥ 2\, and let r0=|i∣ai=1|−|j∣bj=1|r_0=|\i a_i=1\|-|\j b_j=1\| be the rational contribution of unit roots. If I∪J=∅I∪ J= , we output a single-state zero-reward RMDP with threshold −r0-r_0, which is a yes-instance exactly when r0≤0r_0≤ 0. In the following, assume that at least one non-unit root is present. Put N=|I|+|J|N=|I|+|J| for the number of local gadgets. For every i∈Ii∈ I, apply Lemma 41. This gives a local gadget with minimal robust regret ai−Ci+ a_i-C_i^+ for a rational constant Ci+C_i^+. For every j∈Jj∈ J, apply Lemma 40 to obtain rational parameters qj,Dj−,Aj−,Bj−q_j,D_j^-,A_j^-,B_j^-. After the reward scaling from that lemma, gadget j has local minimal robust regret Dj−bj.D_j^-- b_j. Choose one common discount factor qmin=min(45∪qj∣j∈J),γ=1−qmin2.q_ = ( \ 45 \∪\q_j j∈ J\ ), γ=1- q_ 2. Then γ∈(15,1)γ∈( 15,1), so the positive-coefficient gadgets are valid, and γ>1−qjγ>1-q_j for every j∈Jj∈ J, so the negative-coefficient gadgets are valid as well. Compose all local gadgets using Lemma 42. The resulting RMDP has infπ∈ΠMRRreg(π) _π∈ ^MRRreg(π) =∑i∈I(ai−Ci+)+∑j∈J(Dj−bj) = _i∈ I( a_i-C_i^+)+ _j∈ J(D_j^-- b_j) =C+∑i∈Iai−∑j∈Jbj, =C+ _i∈ I a_i- _j∈ J b_j, where C=∑j∈JDj−∑i∈ICi+.C= _j∈ JD_j^-- _i∈ IC_i^+. Set the threshold t=C−r0t=C-r_0. Then infπ∈ΠMRRreg(π)≤t _π∈ ^MRRreg(π)≤ t ⇔∑i∈Iai−∑j∈Jbj≤−r0 _i∈ I a_i- _j∈ J b_j≤-r_0 ⇔∑i=1mai≤∑j=1nbj. _i=1^m a_i≤ _j=1^n b_j. The uncertainty set is a product of choice uncertainty sets, so the reduction preserves (s,a)(s,a)-rectangularity. ∎ Appendix I Proof of Theorem 8: General-Polytope Minimal-Regret Hardness We first prove the existential-universal upper bound, then use two-action anchoring to turn general policy comparison into a strictly monotone minimal-regret objective. See 8 I.1 Existential-Universal Membership The membership claim is proved with its certification counterpart in Appendix C. I.2 Two-Action Anchoring Start with a deterministic comparison instance (M,π1,π2,t)(M, _1, _2,t) (5) and write Δ=supp(Vpπ1(sι)−Vpπ2(sι)),Vmax=maxs,a|R(s,a)|1−γ. = _p (V_p _1(s_ )-V_p _2(s_ ) ), V_ = _s,a|R(s,a)|1-γ. Choose L=2γVmax+|γt|+1,Z=L/γ+2Vmax+1.L=2γ V_ +|γ t|+1, Z=L/γ+2V_ +1. Every compliant value of the construction below is bounded in absolute value by M^=L+γ(Z+Vmax)+ZM_ M=L+γ(Z+V_ )+Z, since the copies contribute at most VmaxV_ , the anchors ±Z± Z, and the initial action at most L on top of those. Choose a rational ZrZ_ r of polynomial encoding length such that γZr>M^+1,γ Z_ r>M_ M+1, which is the hypothesis of Lemma 11. Definition 19 (Two-action anchoring RMDP). Given (M,π1,π2,t)(M, _1, _2,t), the two-action anchoring RMDP is M^=(S^,A^,^,R^,s^,γ), M=( S, A, U, R, s,γ), with the following components. • S S contains a fresh initial state s s, two disjoint forced copies of M, absorbing states z−z_- and z+z_+ of values −Z-Z and Z, and a ruinous sink ⊥r _ r of value −Zr-Z_ r. • At each state in copy i, the action prescribed by πi _i is the described action. The initial state offers actions α and β. Every action at z−z_- and z+z_+ self-loops with the reward realizing its displayed payoff. • U ties corresponding transition coordinates of the forced copies to one realization p of U. It also contains mutually independent coordinates λα,λβ∈[0,1] _α, _β∈[0,1] that are unconstrained by the equalities tying the copies. Action α enters the first copy with probability λα _α and z−z_- otherwise. Action β enters the second copy with probability λβ _β and z+z_+ otherwise. • Rewards inside the forced copies agree with M. Action α pays L, action β pays zero, and the self-loop rewards at z−z_- and z+z_+ are −(1−γ)Z-(1-γ)Z and (1−γ)Z(1-γ)Z, respectively. Every action at ⊥r _ r self-loops with reward −(1−γ)Zr-(1-γ)Z_ r. All remaining choices use ruinous-sink completion with ZrZ_ r. • The initial state is s s and the discount is γ. Figure 12 illustrates the construction. Lemma 43 (Anchored action values). At a realization (p,λα,λβ)(p, _α, _β) of Definition 19, the values of α and β at s s are A=L+γ(λαVpπ1(sι)−(1−λα)Z),B=γ(λβVpπ2(sι)+(1−λβ)Z).A=L+γ ( _αV_p _1(s_ )-(1- _α)Z ), B=γ ( _βV_p _2(s_ )+(1- _β)Z ). Proof. The choice of ZrZ_ r makes every ruinous-completed action strictly worse than the prescribed continuation at a copied state, for both the comparator and the candidate. Thus the two copies have values Vpπ1(sι)V_p _1(s_ ) and Vpπ2(sι)V_p _2(s_ ). One-step conditioning on the two successors of each initial action gives the formulas. ∎ Set D=L+γΔD=L+γ and E=2γZ−LE=2γ Z-L. s sforced M,π1M, _1−Z-Zforced M,π2M, _2Zα;Lα;Lβ;0β;0λα _α1−λα1- _αλβ _β1−λβ1- _β Figure 12: The two-action anchoring RMDP. The two copies share the realization p, whereas λα _α and λβ _β are fresh coordinates. Lemma 44 (Two-action anchoring). The constants D and E are positive. A policy choosing α with probability x has robust regret max(1−x)D,xE \(1-x)D,xE\. Proof. By Lemma 43, the action-value difference is affine in each fresh coordinate, so its extrema occur at their four endpoint pairs. For A−BA-B these values are (λα,λβ)A−B(1,1)L+γ(Vpπ1−Vpπ2)(1,0)L+γ(Vpπ1−Z)(0,1)L−γ(Z+Vpπ2)(0,0)L−2γZ. array[]c|c( _α, _β)&A-B\\ (1,1)&L+γ(V _1_p-V _2_p)\\ (1,0)&L+γ(V _1_p-Z)\\ (0,1)&L-γ(Z+V _2_p)\\ (0,0)&L-2γ Z. array The definition of Z and |Vpπi|≤Vmax|V_p _i|≤ V_ make the first endpoint strictly largest after optimizing over p, so its supremum is D. For B−AB-A the four values are respectively γ(Vpπ2−Vpπ1)−L,γZ−L−γVpπ1,γ(Z+Vpπ2)−L,2γZ−L.γ(V _2_p-V _1_p)-L, γ Z-L-γ V _1_p, γ(Z+V _2_p)-L, 2γ Z-L. The last is strictly largest and equals E>0E>0. Moreover, γΔ≥−2γVmaxγ ≥-2γ V_ , and hence D≥|γt|+1>0D≥|γ t|+1>0. At any realization the loss of the x-mixture is (1−x)(A−B)(1-x)(A-B) when A≥BA≥ B and x(B−A)x(B-A) otherwise. Taking the supremum, using D,E>0D,E>0, gives the claimed maximum. ∎ Lemma 44 covers the policies that play α or β and then the prescribed continuation, whereas the infimum ranges over every stationary policy of the completed RMDP, so the two must first be identified. For an arbitrary policy π, its compliant projection π¯ π has value at least π’s at every realization by Lemma 11, hence regret at most π’s. Each copied state leaves π¯ π only the prescribed action, so π¯ π is determined by the single probability x=π¯(s^,α)x= π( s,α), and the two infima coincide. Balancing the two branches therefore gives minimum DE/(D+E)DE/(D+E). Let T=L+γt,t′=ETE+T.T=L+γ t, t = ETE+T. Since z↦Ez/(E+z)z Ez/(E+z) is strictly increasing for z>0z>0, infπRreg(π)≤t′⇔Δ≤t. _πRreg(π)≤ t ≤ t. Example 8 shows that the threshold remains rational for an irrational comparison gap. Example 8 (Anchoring an irrational comparison gap). For the RMDP of Example 1, γ=1/2γ=1/2, Vmax=2V_ =2, and Δ=7−43 =7-4 3. Taking t=0t=0 gives L=3L=3, Z=11Z=11, D=13/2−23D=13/2-2 3, E=8E=8, T=3T=3, and t′=24/11t =24/11. Thus the anchoring constants and threshold remain rational even though the balanced regret DE/(D+E)DE/(D+E) depends on the irrational source gap. Proof of Theorem 8. The equivalence above is a reduction from Theorem 20’s ∀ℝ -hard comparison problem. ∎ Appendix J Proof of Theorem 9: Bounded Portfolio Synthesis The reduction reads the two quantifiers of a bounded real sentence as the two players in synthesis. The portfolio plays the existential witness and nature plays the universal block. Three obstacles have to be handled: a reward may not depend on a policy or a realization, a stationary policy fixes one continuation per state, and different members must agree on the witness. The construction below resolves all three by normalizing the matrix into tests that are affine in the witness, and by making nature’s choice of audit a coefficient inside one polynomial per member rather than a branch in the model. See 9 J.1 Existential-Universal Membership Membership is proved in Appendix C. J.2 A Policy-Affine Max Normal Form Using the bounded degree-four normal form of Definition 4, it is ∃∀ℝ∃ -complete to decide ∃x∈[0,1]n∀y∈[0,1]m:F(x,y)≥0∃ x∈[0,1]^n\ ∀ y∈[0,1]^m: F(x,y)≥ 0 after the affine substitution that moves the source box from [−1,1][-1,1] to [0,1][0,1]. Write F(x,y)=∑ν=1Nmoncν∏j=1dνwν,j,dν≤4,F(x,y)= _ν=1^N_ monc_ν _j=1^d_νw_ν,j, d_ν≤ 4, where every wν,jw_ν,j is a variable of x∪yx∪ y, and put B=max1,∑ν=1Nmon|cν|.B= \1, _ν=1^N_ mon|c_ν| \. Thus |F|≤B|F|≤ B on the box, and B has polynomial encoding length. Apply Definition 4 with its optional output coordinate to the input vector (x,y)(x,y). Let η consist of y and every copy, product, and output coordinate, and list all residuals as h1,…,hsh_1,…,h_s. Only copy residuals for occurrences of x contain an existential coordinate; each does so affinely and contains exactly one. Definition 20 (Elementary tests). For every residual hjh_j and every σ∈−1,1σ∈\-1,1\, put gj,σ(x,η)=o+σ 9Bhj10B,g_j,σ(x,η)= o+σ\,9B\,h_j10B, and enumerate the resulting r=2sr=2s expressions as g1,…,grg_1,…,g_r. Lemma 45 (Elementary-test shape). Each test of Definition 20 satisfies: 1. gi(x,η)∈[−1,1]g_i(x,η)∈[-1,1] on the box; 2. gi(x,η)=ci(η)+∑ℓdi,ℓxℓg_i(x,η)=c_i(η)+ _ d_i, x_ , where at most one di,ℓd_i, is nonzero and that coefficient is ±910± 910; and 3. cic_i has degree at most two in η. Proof. The first claim follows from |o|≤B|o|≤ B and |hj|≤1|h_j|≤ 1. Only copy residuals contain an existential variable, each contains exactly one with coefficient −1-1, so its two tests have coefficient ∓910∓ 910. Every other residual and o are free of x. Copy and output residuals are affine, product residuals are quadratic in η, and o is affine in o¯ o. ∎ Lemma 46 (Policy-affine max form). ∃x∀y:F(x,y)≥0⟺∃x∀η:maxi∈[r]gi(x,η)≥0.∃ x\ ∀ y:\ F(x,y)≥ 0 ∃ x\ ∀η:\ _i∈[r]g_i(x,η)≥ 0. Proof. For the forward direction, fix a witness x and any η, retain its y-part, and let δ=maxj|hj|δ= _j|h_j|. Choose j with |hj|=δ|h_j|=δ and σ with σhj=δσ h_j=δ. By Lemma 12, o≥F(x,y)−9Bδ≥−9Bδ,o≥ F(x,y)-9Bδ≥-9Bδ, and therefore gj,σ≥0g_j,σ≥ 0. This also covers δ=0δ=0. Conversely, if x is not a witness, choose y with F(x,y)<0F(x,y)<0. Give every copy and product variable its correct value and set o¯=F(x,y)+B2B∈[0,1]. o= F(x,y)+B2B∈[0,1]. Then o=F(x,y)o=F(x,y) and every residual vanishes, so every test equals F(x,y)/(10B)<0F(x,y)/(10B)<0. ∎ Example 9 makes all constants in the normalization explicit. Example 9 (A policy-affine normal form). Let n=m=1n=m=1 and F(x,y)=x−12yF(x,y)=x- 12y, whose sentence is true exactly for x≥12x≥ 12. Here Nmon=2N_ mon=2, c1=1c_1=1, c2=−12c_2=- 12, and B=32B= 32. The copies are z1,z2z_1,z_2, with p1=z1p_1=z_1, p2=z2p_2=z_2 and no product residuals: h1=z1−x,h2=z2−y,h3=13(o−z1+12z2),o=3o¯−32.h_1=z_1-x, h_2=z_2-y, h_3= 13 (o-z_1+ 12z_2 ), o=3 o- 32. Thus s=3s=3, r=6r=6, 9B=2729B= 272, and 10B=1510B=15. Only g1,±g_1,± mention x, with coefficients ∓910∓ 910. For x=13x= 13, the reverse construction takes y=1y=1, z1=13z_1= 13, z2=1z_2=1, and o¯=49 o= 49. Every residual then vanishes and every test equals (x−12)/15<0(x- 12)/15<0. J.3 Exact Evaluators Both components use the terminal-payoff convention of Appendix A. Throughout this section, γ=12γ= 12. For a sparse polynomial P, write Poly(P)Poly(P) for the component of Definition 8 at this discount, with repeated logical coordinates tied later by Definition 24, and write ePe_P for its entry. Lemma 22 gives its exact compliant value and its structural bounds. Definition 21 (Affine-policy evaluator). For G(x,u)=P0(u)+∑ℓ=1nxℓPℓ(u),G(x,u)=P_0(u)+ _ =1^nx_ P_ (u), with every PℓP_ explicit, sparse, and of constant degree, the component Aff(G)Aff(G) has: • an entry eGe_G; coordinate states s1,…,sns_1,…,s_n, each with actions on and off; a zero-payoff terminal zrzr; and copies of Poly(n+1γP0)andPoly(n+1γ2Pℓ)(ℓ∈[n]);Poly ( n+1γP_0 ) ( n+1γ^2P_ ) ( ∈[n]); • at eGe_G, one action with the certain uniform splitter over the n+1n+1 successors eP0,s1,…,sne_P_0,s_1,…,s_n; at sℓs_ , a reward-zero singleton transition from on to ePℓe_P_ and from off to zrzr; • the rewards and completion of its PolyPoly copies; every other choice of this component uses ruinous-sink completion. Lemma 47 (Affine-policy evaluation). For every realization u and every compliant π∈ΠMRπ∈ ^MR, Vuπ(eG)=P0(u)+∑ℓ=1nxℓPℓ(u),xℓ=π(sℓ,).V_u^π(e_G)=P_0(u)+ _ =1^nx_ P_ (u), x_ =π(s_ , on). Proof. The constant branch contributes 1n+1γn+1γP0(u)=P0(u). 1n+1γ n+1γP_0(u)=P_0(u). At sℓs_ , Vuπ(sℓ)=xℓγn+1γ2Pℓ(u)+(1−xℓ)γ⋅0=xℓn+1γPℓ(u),V_u^π(s_ )=x_ γ n+1γ^2P_ (u)+(1-x_ )γ· 0=x_ n+1γP_ (u), so branch ℓ contributes γn+1xℓn+1γPℓ(u)=xℓPℓ(u) γn+1x_ n+1γP_ (u)=x_ P_ (u). Summing proves the identity. ∎ Lemma 48 (One predecessor per coordinate). In Aff(G)Aff(G) every coordinate state sℓs_ has exactly one predecessor, namely eGe_G, and each of its two actions has one fixed continuation. Thus a stationary policy’s behavior at sℓs_ has a single interpretation, and no continuation depends on the context from which sℓs_ was reached. Proof. The certain uniform splitter at eGe_G is the only transition into sℓs_ , while on and off always lead to ePℓe_P_ and zrzr, respectively. ∎ Every occurrence gets a fresh row, and the only policy choices are at the coordinate states. Thus the evaluator has neither shared selector decoder actions nor context-dependent continuations. Figure 13 shows the nested evaluator structure. sιs_ eGe_Gsℓs_ zrzrePℓe_P_ cν,1c_ν,1cν,2c_ν,2τν _νfixed payoffflflai,bha_i,b_hcertain uniform off oncertain uniformu1u_1u2u_21−u11-u_11−u21-u_2 Figure 13: The synthesis RMDP and its evaluator components. The only policy choices are at sιs_ and the coordinate states; every reward shown is a fixed rational. J.4 Roles, Cases, and Scores Definition 22 (Portfolio case scores). Let r be the number of tests and also the portfolio budget. Put ℋ=ev∪(i,ℓ,→),(i,ℓ,←):2≤i≤r,ℓ∈[n]∪(i,t):i∈[r],t∈[3r+1].H=\ev\∪\(i, ,→),(i, ,←):2≤ i≤ r,\ ∈[n]\∪\(i,t):i∈[r],\ t∈[3r+1]\. Nature’s coordinates are a case distribution λ∈(ℋ)λ (H), the evaluation vector η, and one coordinate qh∈[0,1]q_h∈[0,1] for every oriented equality case. Write ξh _h for the coordinates local to case h. For role i, define the pure-case score Ah,i(xi,ξh)A_h,i(x_i, _h) as follows. • In the evaluation case, Aev,i(xi,η)=gi(xi,η)A_ev,i(x_i,η)=g_i(x_i,η). • For h=(i,ℓ,→)h=(i, ,→), Ah,1=x1,ℓ−qh,Ah,i=qh−xi,ℓ,A_h,1=x_1, -q_h, A_h,i=q_h-x_i, , and Ah,j=−1A_h,j=-1 for j∉1,ij∉\1,i\. • For h=(i,ℓ,←)h=(i, ,←), Ah,1=qh−x1,ℓ,Ah,i=xi,ℓ−qh,A_h,1=q_h-x_1, , A_h,i=x_i, -q_h, and Ah,j=−1A_h,j=-1 for j∉1,ij∉\1,i\. • For h=(i,t)h=(i,t), set Ah,i=0A_h,i=0 and Ah,j=−1A_h,j=-1 for j≠ij≠ i. Lemma 49 (Pure-score shape). Every pure-case score of Definition 22 lies in [−1,1][-1,1] and has the form Ah,i(xi,ξh)=ch,i(ξh)+∑ℓdh,i,ℓxi,ℓ,A_h,i(x_i, _h)=c_h,i( _h)+ _ d_h,i, x_i, , where ch,ic_h,i has degree at most two in nature’s coordinates and every dh,i,ℓd_h,i, is rational. Proof. The evaluation scores have the claimed range and shape by Lemma 45. Equality scores are differences of two numbers in [0,1][0,1], with ch,⋅=∓qhc_h,·=∓ q_h and dh,⋅=±1d_h,·=± 1. Forcing scores are constants. ∎ Define the mixed score of role i by Wi=∑h∈ℋλhAh,i(xi,ξh)+1−∑h∈ℋλh2.W_i= _h _hA_h,i(x_i, _h)+1- _h _h^2. (5) Lemma 50 (Mixed-score polynomial). The score WiW_i has the form Wi=Pi,0(λ,η,q)+∑ℓxi,ℓPi,ℓ(λ),W_i=P_i,0(λ,η,q)+ _ x_i, P_i, (λ), where Pi,0=1−∑hλh2+∑hλhch,i(ξh),Pi,ℓ=∑hλhdh,i,ℓ.P_i,0=1- _h _h^2+ _h _hc_h,i( _h), P_i, = _h _hd_h,i, . The first polynomial has degree at most three, the second has degree one, and both have polynomially many monomials. Consequently, Lemma 47 applies to WiW_i. Proof. Substitute Lemma 49 into (5) and collect coefficients. The largest degree is 1+21+2, from λh _h multiplying a quadratic ch,ic_h,i. The number of monomials is bounded by the sum of the explicit monomial counts of the pure scores plus 1+|ℋ|1+|H|. ∎ The cases are coordinates of nature inside these polynomials, not branches in the model. This lets one evaluator compute all of WiW_i while every coordinate state retains the single predecessor guaranteed by Lemma 48. J.5 The Synthesis RMDP Definition 23 (Portfolio-synthesis RMDP). Let Msyn=(S,A,,R,sι,12)M_ syn=(S,A,U,R,s_ , 12) be defined as follows. • Its states are sιs_ ; for every role i∈[r]i∈[r], a copy EiE_i of Aff(γ−1Wi)Aff(γ^-1W_i) with coordinate states si,1,…,si,ns_i,1,…,s_i,n; for every h∈ℋh , a copy UhU_h of Poly(γ−1(3λh−1))Poly(γ^-1(3 _h-1)); and a ruinous sink. • At sιs_ , the role action aia_i has reward zero and its singleton row enters EiE_i. The auxiliary action bhb_h has reward zero and its singleton row enters UhU_h. All other described transitions are those of the two component families. • The uncertainty set is given in Definition 24. • Rewards are those of the components. Every choice still undescribed after the global action set has been installed uses ruinous-sink completion. • The initial state is sιs_ and γ=12γ= 12. Definition 24 (Portfolio uncertainty). Every occurrence of a logical nature coordinate inside a component is represented by a fresh two-successor row. For every λh _h, every coordinate of η, and every qhq_h, designate one occurrence as its representative and impose a rational linear equality setting every other occurrence’s success probability equal to that representative. On the λ representatives add λh≥0 _h≥ 0 and ∑hλh=1 _h _h=1, together with the usual stochasticity constraints on all rows. Lemma 51 (Uncertainty shape). The set U is a nonempty rational polytope. Every uncertain row has two successors, and the only other stochastic rows are the certain uniform splitters at component entries. The uncertainty is nonrectangular only through the tying equalities and the simplex constraint. Proof. Choose any λ in the simplex and arbitrary values in [0,1][0,1] for the other representatives, then propagate them through the tying equalities, which witnesses nonemptiness. Its half-space description consists of exactly four families, all listed in Definition 24: one equality per nonrepresentative occurrence tying it to its representative, the bounds λh≥0 _h≥ 0, the equality ∑hλh=1 _h _h=1, and nonnegativity with normalization on every row. Every coefficient is 00 or ±1± 1, and the number of constraints is linear in the number of rows, so the description has polynomial encoding length and the reduction can write it down. The remaining claims follow from Definitions 8, 21 and 24. ∎ J.6 Action Values and the Optimal-Value Bound Lemma 52 (Role-action values). In the RMDP of Definition 23, for every realization and every compliant π∈ΠMRπ∈ ^MR, Quπ(sι,ai)=Wi(xi,λ,η,q),xi,ℓ=π(si,ℓ,).Q_u^π(s_ ,a_i)=W_i(x_i,λ,η,q), x_i, =π(s_i, , on). Proof. The initial action makes one reward-zero transition into EiE_i, whose value is γ−1Wiγ^-1W_i by Lemmas 50 and 47. ∎ Lemma 53 (Auxiliary-action values). For every realization and every compliant policy, Qu(sι,bh)=3λh−1.Q_u(s_ ,b_h)=3 _h-1. At a pure case λ=δh∗λ= _h^*, this value is two for h=h∗h=h^* and −1-1 otherwise. Proof. Apply Lemma 22 to γ−1(3λh−1)γ^-1(3 _h-1) and include the initial discount. ∎ Lemma 54 (Optimal-value bound). For every realization, Vu∗(sι)≤2V_u^*(s_ )≤ 2, with equality whenever λ=δhλ= _h is a pure case. Proof. The only policy choices at described states are at sιs_ and at coordinate states. The action values are those of Lemmas 52 and 53. Since every pure score is at most one, Wi≤∑hλh+1−∑hλh2=2−∑hλh2≤2,W_i≤ _h _h+1- _h _h^2=2- _h _h^2≤ 2, and 3λh−1≤23 _h-1≤ 2. By Lemma 11, these upper bounds extend from compliant policies to all policies. A randomized action at sιs_ gives a convex combination of these values, so it cannot exceed two. At λ=δhλ= _h, action bhb_h attains two. ∎ Lemma 55 (Combining pure cases). For fixed coordinate vectors x1,…,xrx_1,…,x_r, the following are equivalent: 1. for every pure case h and every valuation of ξh _h, some role has Ah,i≥0A_h,i≥ 0; 2. for every λ∈(ℋ)λ (H) and every valuation of all coordinates, some role has Wi≥0W_i≥ 0. Proof. The second claim implies the first by taking λ=δhλ= _h, when Wi=Ah,iW_i=A_h,i. For the converse, fix a realization and take h∗∈argmaxhλh^*∈ _h _h. Apply the pure-case hypothesis at h∗h^* with the realization’s own ξh∗ _h^* to obtain a role i with Ah∗,i≥0A_h^*,i≥ 0. All other pure scores are at least −1-1, so ∑hλhAh,i≥−(1−λh∗). _h _hA_h,i≥-(1- _h^*). Moreover, ∑hλh2≤λh∗∑hλh=λh∗. _h _h^2≤ _h^* _h _h= _h^*. Substitution in (5) gives Wi≥−(1−λh∗)+1−λh∗=0.W_i≥-(1- _h^*)+1- _h^*=0. ∎ Each oriented equality case needs its own coordinate qhq_h: the role selected for h∗h^* depends on ξh∗ _h^*, which must remain free of every other case’s coordinates. Example 10 shows that the correction bound can be tight. Example 10 (The mixing correction). If λ is uniform on two cases, then 1−∑hλh2=121- _h _h^2= 12. If a role has score zero at one of those cases and −1-1 at the other, its mixed score is 12⋅0+12⋅(−1)+12=0. 12· 0+ 12·(-1)+ 12=0. Thus the combining bound is tight. J.7 Correctness Lemma 56 (Forward direction). If the source sentence holds with witness x, then the portfolio Π=π1,…,πr =\ _1,…, _r\ defined by πi(sι)=ai,πi(sj,ℓ,)=xℓfor every j,ℓ _i(s_ )=a_i, _i(s_j, , on)=x_ every j, and completed compliantly at every other state satisfies Rreg(Π)≤2Rreg( )≤ 2. Proof. Every πi _i is stationary and Vuπi(sι)=Wi(x)V_u _i(s_ )=W_i(x) by Lemma 52. We verify pure-case coverage. At evev, Lemma 46 gives maxigi(x,η)≥0 _ig_i(x,η)≥ 0 for every η. At an oriented equality case, the two nonconstant scores have maximum maxxℓ−qh,qh−xℓ=|xℓ−qh|≥0. \x_ -q_h,q_h-x_ \=|x_ -q_h|≥ 0. At a forcing case (i,t)(i,t), role i scores zero. By Lemma 55, every realization has some Wi≥0W_i≥ 0. Combining this with Lemma 54 bounds regret by two. ∎ Lemma 29 is needed here because the reverse direction turns ρr≤2 _r≤ 2 into a concrete portfolio. Its hypotheses hold: U is a compact rational polytope by Lemma 51. The other synthesis reductions compute their infimum in closed form. Lemma 57 (Role forcing). If Π has at most r members and Rreg(Π)≤2Rreg( )≤ 2, then it has exactly r members, exactly one member chooses each aia_i with probability one, and no member chooses an auxiliary action at sιs_ . Proof. At a pure case, Lemma 54 gives Vu∗(sι)=2V_u^*(s_ )=2. Thus the regret bound implies maxπ∈ΠVuπ(sι)≥0 _π∈ V_u^π(s_ )≥ 0 at every pure case and every valuation of its coordinates. A member need not be compliant: besides its initial choice it may play a globally installed action inside a component, where the action values below do not apply. Replace each member π by π¯ π, which Lemma 11 shows has value at least π’s at every state and realization, so the displayed bound is only strengthened. The projection keeps the initial distribution over ai,bh\a_i,b_h\ and renormalizes at each coordinate state, which leaves π(si,ℓ,)π(s_i, , on) in [0,1][0,1], so π¯ π still encodes a witness and the count below is unaffected. Fix a role i and a forcing case h=(i,t)h=(i,t). At λ=δhλ= _h, action aia_i has value zero, every other role action has value −1-1, action bhb_h has value two, every other auxiliary action has value −1-1, and every completed action has value at most −1-1. For a policy with initial distribution p, collect the mass outside ai,bh\a_i,b_h\ to obtain Vuπ(sι)≤p(ai)+3p(bh)−1.V_u^π(s_ )≤ p(a_i)+3p(b_h)-1. Suppose p(ai)<1p(a_i)<1 and put δπ=1−p(ai)>0 _π=1-p(a_i)>0. Covering h forces p(bh)≥δπ/3p(b_h)≥ _π/3. The actions b(i,t)b_(i,t) are distinct and outside aia_i, so ∑t=13r+1p(b(i,t))≤δπ. _t=1^3r+1p(b_(i,t))≤ _π. This policy can therefore cover at most three of the 3r+13r+1 forcing cases for role i. If every portfolio member had p(ai)<1p(a_i)<1, the at most r members would cover at most 3r3r such cases, a contradiction. Thus some member has p(ai)=1p(a_i)=1. No policy can put probability one on both aia_i and aja_j for i≠ji≠ j. The r roles therefore require r distinct members, exhausting the budget. Every member is pure on its role action at sιs_ , leaving none on an auxiliary action. ∎ Lemma 58 (Equality cases). Under the hypotheses of Lemma 57, let xix_i be the vector encoded by the member assigned to role i. Then x1=⋯=xrx_1=·s=x_r. Proof. Fix i≥2i≥ 2 and ℓ . At pure case (i,ℓ,→)(i, ,→), coverage for a given q∈[0,1]q∈[0,1] is maxx1,ℓ−q,q−xi,ℓ,−1≥0, \x_1, -q,\ q-x_i, ,\ -1\≥ 0, equivalently maxx1,ℓ−q,q−xi,ℓ≥0. \x_1, -q,\ q-x_i, \≥ 0. If x1,ℓ<xi,ℓx_1, <x_i, , the legal midpoint q=12(x1,ℓ+xi,ℓ)q= 12(x_1, +x_i, ) makes both terms negative. Conversely, if x1,ℓ≥xi,ℓx_1, ≥ x_i, , every q satisfies q≤x1,ℓq≤ x_1, or q≥xi,ℓq≥ x_i, , so one term is nonnegative. Coverage for every q is therefore equivalent to x1,ℓ≥xi,ℓx_1, ≥ x_i, . The reverse oriented case gives xi,ℓ≥x1,ℓx_i, ≥ x_1, . ∎ Lemma 59 (Evaluation case). Under the same hypotheses, with x the common vector, maxigi(x,η)≥0for every η. _ig_i(x,η)≥ 0 every η. Proof. At the pure case evev, role i has value Aev,i(xi,η)=gi(xi,η)A_ev,i(x_i,η)=g_i(x_i,η). Pure-case coverage gives maxigi(xi,η)≥0 _ig_i(x_i,η)≥ 0. Apply Lemma 58. ∎ Proof of Theorem 9. Membership is the existential-universal encoding in the first subsection. For hardness, Lemma 56 gives ρr≤2 _r≤ 2 whenever the source sentence holds. Conversely, if ρr≤2 _r≤ 2, then Lemma 29 supplies a portfolio of at most r members with regret at most two. Lemmas 57, 58 and 59, followed by Lemma 46, gives the source sentence. Thus ρr≤2⟺∃x∀y:F(x,y)≥0. _r≤ 2 ∃ x\ ∀ y:\ F(x,y)≥ 0. The reduction is polynomial and satisfies the stated restrictions by Lemmas 60 and 61. ∎ Example 11 illustrates both equality auditing and role forcing. Example 11 (A two-role synthesis instance). Take r=2r=2 and n=1n=1. Then 3r+1=73r+1=7 and |ℋ|=1+2+14=17|H|=1+2+14=17. At the pure case (2,1,→)(2,1,→) with q=25q= 25, role one scores x1,1−25x_1,1- 25 and role two scores 25−x2,1 25-x_2,1. For x1,1=310x_1,1= 310 and x2,1=12x_2,1= 12, both are −110- 110. No member is nonnegative, and the regret is 2+1102+ 110, exposing x1,1<x2,1x_1,1<x_2,1. If both coordinates are 12 12, role one scores 110 110 and covers the case. At forcing case (1,3)(1,3), a member with p(a1)=1p(a_1)=1 scores zero. A member with p(a1)=p(b(1,3))=12p(a_1)=p(b_(1,3))= 12 scores 3⋅12+12−1=13· 12+ 12-1=1 and also covers that case, but its remaining mass 12 12 can place the required 16 16 on at most three of role one’s seven forcing actions. J.8 Size and Structural Restrictions Lemma 60 (Synthesis size). The reduction runs in polynomial time. Proof. There is one copy variable per occurrence, at most three product variables per monomial, and one output coordinate. Thus s and r=2sr=2s are polynomial, and |ℋ|=1+2(r−1)n+r(3r+1).|H|=1+2(r-1)n+r(3r+1). Every WiW_i has degree at most three and polynomially many monomials. Each PolyPoly component has one branch per monomial and at most three factor rows per branch. The budget r is written in unary and is polynomial. Every constant comes from rational arithmetic on input coefficients, B, polynomially bounded integers, and powers 2eν+12^e_ν+1, so every encoding length is polynomial. ∎ Lemma 61 (Synthesis structure). The RMDP MsynM_ syn has fixed discount 12 12, threshold two, and is acyclic apart from absorbing terminals. Every uncertain row has two successors, and the only other stochastic rows are certain uniform splitters. Every reward is a fixed rational independent of the policy and realization. Nonrectangularity arises only from the tying equalities and simplex constraint of Definition 24. Proof. Every described path goes from sιs_ to a component entry, through a certain uniform splitter, an optional coordinate state and a chain of factor selectors, and then to a terminal. No transition returns to an earlier state, and the only self-loops are at terminal states and named ruinous sinks. The factor selectors are precisely the fresh two-successor uncertain rows. Policy probabilities enter only through coordinate-state actions, and realization coordinates only through factor rows; all terminal payoffs and rewards were fixed before the realization and policy are chosen. The remaining claims follow from Lemma 51. ∎ Folding the cases into the coefficients of one polynomial per role ensures that each role’s entire mixed score is computed by one evaluator and every coordinate state has one predecessor. Appendix K Experimental setup This appendix gives the details behind Section 4. We first fix the class of models the benchmarks belong to and the uncertainty set each one induces, then describe the offline construction of a portfolio, and then the two evaluations answering the research questions: whether portfolios reduce empirical robust regret as the budget grows (RQ1), and whether the best member can be identified online in a fixed but unknown environment (RQ2). Algorithm 2 summarizes the whole procedure. Detailed descriptions of the two benchmarks close the appendix, and the tables and figures themselves appear in Appendix L. K.1 Parametric MDPs and their uncertainty sets A parametric MDP (pMDP) is a tuple (S,A,P,R,sι,γ,X)(S,A,P,R,s_ ,γ,X) in which X is a finite set of parameters and every transition probability P(s,a,s′)P(s,a,s ) is a polynomial in ℚ[X]Q[X]. A valuation θ:X→ℝθ X is well defined when it turns every choice row into a probability distribution, and graph preserving when no transition polynomial that is not identically zero evaluates to zero under it. Both benchmarks below are affine pMDPs: every transition polynomial has degree one, and the admissible valuations form a compact box D⊆ℝXD ^X on which well-definedness holds by construction, so no clamping or renormalization is ever needed. Such a benchmark is an RMDP in the sense of Section 2: each θ∈Dθ∈ D instantiates a transition vector θ u_θ, and D=θ:θ∈DU_D=\ u_θ:θ∈ D\ is the induced uncertainty set. This set is not (s,a)(s,a)-rectangular. A single parameter occurs in the rows of many different choices — the wind intensity p governs every grid cell of the UAV benchmark, and the cooling effectiveness pcp_c every state of the datacenter benchmark — so fixing nature’s move at one choice fixes it everywhere else. Robust policy evaluation, however, is performed by robust value iteration (13), which requires a rectangular uncertainty set. We therefore relax each parameter region c⊆Dc D to the interval MDP whose per-choice uncertainty sets are the coordinatewise ranges of the transition polynomials over c. Writing c□U _c for the resulting rectangular set, this relaxation only ever adds transition vectors, c=θ:θ∈c⊆c□,U_c=\ u_θ:θ∈ c\ _c, because it drops the equalities tying repeated occurrences of a parameter to a common value. K.2 Offline portfolio construction Candidates. We split the parameter box D into a uniform grid of cells by dividing each parameter’s interval into 1010 equal-width bins, so a two-parameter benchmark yields ||=102=100 =10^2=100 cells. For every cell c∈c we instantiate the pMDP at the cell midpoint mid(c)mid(c) and solve the resulting ordinary MDP by value iteration at tolerance 10−810^-8, which gives an optimal policy πmid(c)∗π^*_mid(c) and its value Vmid(c)∗(sι)V^*_mid(c)(s_ ). The candidate set Π() (C) collects one such memoryless deterministic policy per cell. Scoring candidates. Every candidate is then evaluated robustly against every cell. For a candidate π and a cell c′c , robust value iteration on the interval relaxation c′□U _c returns V¯c′π=inf∈c′□Vπ(sι), V^π_c = _ u _c V^π_ u(s_ ), and the score recorded in the loss matrix is the midpoint-anchored difference Lπ,c′=Vmid(c′)∗(sι)−V¯c′π.L_π,c =V^*_mid(c )(s_ )- V^π_c . (6) Two approximations separate Lπ,c′L_π,c from the exact cellwise robust regret supθ∈c′(Vθ∗(sι)−Vθπ(sι)) _θ∈ c (V^*_θ(s_ )-V^π_θ(s_ ) ). First, the optimal value is taken at the single point mid(c′)mid(c ) rather than at the maximizing θ, which may err in either direction. Second, by the inclusion above, the infimum over c′□U _c is at most the infimum over c′U_c , so this term alone makes Lπ,c′L_π,c an over-estimate of the loss it stands in for. The matrix L is a clustering score, not a certificate; the guarantees reported in Section 4 come from the sampled evaluation of the next subsection, which uses no relaxation at all. Selecting the portfolio. Each candidate π thus carries a profile Lπ∈ℝL_π ^C, one entry per cell, describing where in the parameter space it does well. For a budget K we run K-means on these profiles and keep, from each of the K clusters, the candidate whose profile is nearest that cluster’s center, yielding a portfolio ΠK⊆Π() _K (C) of K memoryless deterministic policies. Clustering is a cheap stand-in for the intractable synthesis problem of 4: it never leaves the candidate set, and it optimizes profile similarity rather than portfolio regret. A single-policy reference point. The same loss matrix also yields an exact reference for K=1K=1. Minimizing each candidate’s worst cell, minπ∈Π()maxc∈Lπ,c, _π∈ (C)\ _c \ L_π,c, is the best worst-case score attainable by any single member of the candidate set, computed directly from L without sampling or clustering. It is the mini-max regret figure quoted in Section 4. Implementation. The prototype is written in Python. Models are built and instantiated with Stormvogel (22) on top of Storm, which also provides the parameter regions and the conversion of a region into the interval MDP used for the relaxation above. Value iteration, robust value iteration, and fixed-policy evaluation are our own NumPy implementations, in dense and sparse variants; the larger benchmarks use the sparse path throughout. Clustering uses scikit-learn’s K-means with automatic restart selection and the seed as its random state. Each stage of the pipeline caches its output in HDF5, so a stage can be resumed or re-run without repeating its predecessors. K.3 RQ1: measuring portfolio regret The portfolios are scored against valuations drawn directly from D, with no cells and no rectangular relaxation involved. For a seed we draw D^⊂D D⊂ D uniformly at random with |D^|=1000 D =1000, and at every θ∈D^θ∈ D we instantiate the pMDP and compute two exact quantities: the optimal value Vθ∗(sι)V^*_θ(s_ ) by value iteration, and the value Vθπ(sι)V^π_θ(s_ ) of each portfolio member by fixed-policy evaluation. The reported estimate is Rreg^D^(Π)=maxθ∈D^(Vθ∗(sι)−maxπ∈ΠVθπ(sι)). Rreg_ D( )= _θ∈ D (V^*_θ(s_ )- _π∈ V^π_θ(s_ ) ). Each valuation is thus charged the shortfall of the best member at that valuation, matching the offline coverage quantity of (1) and charging nothing for identifying that member online; RQ2 measures the identification cost separately. Because the supremum in (1) is replaced by a maximum over finitely many samples, Rreg^D^(Π) Rreg_ D( ) under-approximates Rreg(Π)Rreg( ). The whole construction-and-evaluation procedure is repeated for the three seeds 0,1,20,1,2, which reseed both the K-means initialization and the sample D D; Table 5 reports the individual seeds and Table 2 their mean. K.4 RQ2: online portfolio selection Setting. A fixed but hidden valuation θ defines a generative model GθG_θ from which trajectories of the instantiated MDP can be sampled starting at sιs_ . The portfolio members are treated as the arms of a bandit: pulling arm π rolls out one trajectory of horizon H=100H=100 under π and returns its discounted return. Nothing but these sampled returns is observed, neither θ nor any value function, so a run must discriminate between members from rollouts alone. Returns lie in [−BH,BH][-B_H,B_H] for BH=Rmax1−γH1−γ,B_H=R_ 1-γ^H1-γ, with RmaxR_ the benchmark’s largest reward magnitude. The selection rule. We use UCB (8) in its best-arm-identification form. After one warm-up pull of every arm, round t computes for each arm i still in contention a confidence radius: the empirical-Bernstein radius (15), whose leading term shrinks with the empirical variance rather than with the worst-case range; on these benchmarks the returns are far less variable than BHB_H suggests, so it converges considerably faster than a Hoeffding radius. Writing isafei_safe for the arm of greatest lower confidence bound, the run stops as soon as lcb(isafe)≥maxj≠isafeucb(j)−εabs,lcb(i_safe)\ ≥\ _j≠ i_safeucb(j)- _abs, that is, as soon as no other arm can be more than εabs _abs better. Otherwise every arm whose upper bound has fallen below lcb(isafe)−εabslcb(i_safe)- _abs is eliminated, and the arm of greatest upper confidence bound is pulled next. A run therefore has no fixed iteration budget: it stops when its own stopping test fires, and the number of pulls varies from run to run and grows with K. We use confidence δ=0.1δ=0.1 and tolerance ε=10−3 =10^-3, the latter expressed as a fraction of the return bound, so the absolute tolerance is εabs=ε⋅BH=10−3BH _abs= · B_H=10^-3B_H. Since the empirical-Bernstein radius does the work of separating the arms, ε acts only as a cap that keeps near-ties from running indefinitely, and is kept small. What is measured. At each iteration, a run has both a pulled arm, the exploratory one of greatest upper confidence bound, and a recommended arm, the one of greatest lower confidence bound — the member it would deploy if forced to stop right then. We report the recommended arm, the pulled arm being exploratory by design. A recommendation is scored against the best portfolio member at the hidden valuation, that is, argmaxπ∈ΠVθπ(sι) _π∈ V^π_θ(s_ ) computed exactly by fixed-policy evaluation, and not against the unrestricted optimum Vθ∗V^*_θ. The question is whether online selection finds the best policy the portfolio actually contains. Two quantities are recorded per iteration. The first is the fraction of runs whose recommendation is that best member. The second is the shortfall of the recommended member, normalized by the spread of the portfolio at that valuation, Lθπ=Vθbest(ι)−Vθπ(ι)Vθbest(ι)−Vθworst(ι),L^π_θ= V^best_θ( )-V^π_θ( )V^best_θ( )-V^worst_θ( ), so that recommending the best member scores 00 and recommending the worst scores 11 (with Lθπ=0L^π_θ=0 by convention when every member ties). The second measure is the more informative of the two: the first counts a near-tie between two almost equally good members as an outright failure, whereas the second charges only what that confusion actually costs. Sampling and aggregation. For each portfolio size K and each seed, we draw 3030 valuations uniformly from D and run the selection rule once per valuation, all from one seeded random stream. Pooling the three seeds gives the 9090 runs behind each curve. Because runs stop at different iterations, a curve at iteration t averages over runs still active at t together with runs that have already committed, each of the latter contributing its own deployed outcome from its stopping time onward. Curves are drawn on a logarithmic iteration axis with values binned accordingly, and are shown with standard-error bands. K.5 Datacenter benchmark This benchmark models a controller regulating a server room’s temperature and humidity while working off a job queue, uncertain about how strongly its actions and the ambient environment actually move the system. State space. A state s=(T,H,L)∈Ss=(T,H,L)∈ S records a discretized temperature level T∈0,…,10T∈\0,…,10\, a humidity level H∈0,…,5H∈\0,…,5\, and a queue length L∈0,…,4L∈\0,…,4\, so |S|=11⋅6⋅5=330 S =11· 6· 5=330. Episodes start at s0=(5,2,2)s_0=(5,2,2), a comfortable middle of every range. Action space. At every state, the controller picks one of five actions, A=cool-high,cool-low,hold,heat,dehumidify.A=\ cool-high, cool-low, hold, heat, dehumidify\. They trade energy against comfort: cool-high pushes hardest on temperature and costs the most, cool-low is its cheaper and weaker counterpart, hold spends almost nothing and lets the room drift, heat moves temperature the other way, and dehumidify targets humidity instead of temperature. Parameter space. Two parameters are unknown, θ=(pc,pe)∈Θ=[0.5,0.9]×[0.1,0.8]θ=(p_c,p_e)∈ =[0.5,0.9]×[0.1,0.8]. The cooling effectiveness pcp_c is how reliably an action moves the room as intended, and the environmental pressure pep_e is how strongly workload and ambient conditions push back. A high pcp_c makes the controller’s actions dependable; a high pep_e means the room heats, humidifies, and accumulates work regardless of what the controller does. Transitions. Every state-action pair has four successor branches, split evenly between a control outcome governed by pcp_c and an environment outcome governed by pep_e: ℙθ(s′∣s,a)∈pc2,1−pc2,pe2,1−pe2,pc2+1−pc2+pe2+1−pe2=1,P_θ(s s,a)∈ \ p_c2,\ 1-p_c2,\ p_e2,\ 1-p_e2 \, p_c2+ 1-p_c2+ p_e2+ 1-p_e2=1, so the four branches sum to one at every θ and every transition probability is affine in θ. Writing [x]lohi:=min(hi,max(lo,x))[x]_lo^hi:= (hi, (lo,x)) for clamping a coordinate to its range, and abbreviating T±:=[T±1]010T^±:=[T±1]_0^10, H±:=[H±1]05H^±:=[H±1]_0^5, L±:=[L±1]04L^±:=[L±1]_0^4, Table 3 gives the successor reached by each branch. At a boundary state, two branches can land on the same successor, in which case their probabilities are added. Action pc/2p_c/2 (1−pc)/2(1-p_c)/2 pe/2p_e/2 (1−pe)/2(1-p_e)/2 cool-high (T−,H,L)(T^-,H,L) (T+,H,L)(T^+,H,L) (T,H,L−)(T,H,L^-) (T,H+,L+)(T,H^+,L^+) cool-low (T−,H,L)(T^-,H,L) (T,H,L)(T,H,L) (T,H,L−)(T,H,L^-) (T+,H,L+)(T^+,H,L^+) hold (T,H,L)(T,H,L) (T+,H,L)(T^+,H,L) (T,H−,L−)(T,H^-,L^-) (T+,H+,L+)(T^+,H^+,L^+) heat (T+,H,L)(T^+,H,L) (T−,H,L)(T^-,H,L) (T,H,L−)(T,H,L^-) (T+,H+,L+)(T^+,H^+,L^+) dehumidify (T,H−,L)(T,H^-,L) (T,H+,L)(T,H^+,L) (T−,H,L−)(T^-,H,L^-) (T+,H+,L+)(T^+,H^+,L^+) Table 3: Successor state reached by each of the four branches of ℙθ(⋅∣s,a)P_θ(· s,a), for s=(T,H,L)s=(T,H,L), in the datacenter benchmark. Rewards and discount. The reward is deterministic and independent of θ: r(s,a)=rE(a)+rT(T)+rH(H)+rL(L),r(s,a)=r_E(a)+r_T(T)+r_H(H)+r_L(L), combining a per-action energy cost rE(cool-high)=−4,rE(cool-low)=−2,rE(hold)=−1,rE(heat)=−2,rE(dehumidify)=−3,r_E( cool-high)=-4, r_E( cool-low)=-2, r_E( hold)=-1, r_E( heat)=-2, r_E( dehumidify)=-3, with penalties that activate as each dimension approaches its ceiling: rT(T)=0T≤7−20T∈8,9−50T=10rH(H)=0H≤3−15H=4−40H=5rL(L)=0L≠4−10L=4r_T(T)= cases0&T≤ 7\\ -20&T∈\8,9\\\ -50&T=10 cases r_H(H)= cases0&H≤ 3\\ -15&H=4\\ -40&H=5 cases r_L(L)= cases0&L≠ 4\\ -10&L=4 cases The controller therefore pays continuously for energy and catastrophically for letting any dimension reach its ceiling, and the parameters decide how expensive it is to keep away from those ceilings. The largest reward magnitude is Rmax=maxs,a|r(s,a)|=104R_ = _s,a r(s,a) =104, attained at T=10,H=5,L=4T=10,H=5,L=4 under cool-high, and the discount is γ=0.95γ=0.95, giving Vmax=Rmax/(1−γ)=2080V_max=R_ /(1-γ)=2080. K.6 UAV benchmark This benchmark models a UAV flying through a cluttered three-dimensional grid from a fixed start to a landing pad, under wind drift and actuator-failure risk. State space. A grid state s=(x,y,z)s=(x,y,z) ranges over 0,…,Lx−1×0,…,Ly−1×0,…,Lz−1\0,…,L_x-1\×\0,…,L_y-1\×\0,…,L_z-1\, where x is the direction of travel, y the lateral axis the wind blows across, and z the altitude with z=0z=0 at ground level. Three further states complete the space: an absorbing Crash state, a Goal state, and the terminal sink done that Goal moves to. The start is s0=(0,⌊Ly/2⌋,1)s_0=(0, L_y/2 ,1). Action space. In every grid cell, the UAV chooses one of seven actions, =E,W,N,S,UP,DOWN,HOVER,A=\ E, W, N, S, UP, DOWN, HOVER\, the six unit moves along ±x± x, ±y± y, ±z± z together with a no-op. E advances toward the goal, N and S steer laterally, UP and DOWN trade altitude against exposure to the two hazards, and HOVER holds position while the disturbances still act. Goal offers the single forced action collect leading to done, and Crash and done offer only a self-loop. Parameter space. Two parameters are unknown, θ=(p,q)∈Θ=[0,pmax]×[0,qmax]θ=(p,q)∈ =[0,p_ ]×[0,q_ ]. The wind intensity p is the chance that a step is overridden by a one-cell lateral drift, and the actuator-drop probability q is the probability that it is overridden by losing a level of altitude. The generator requires pmax+qmax<1p_ +q_ <1, so 1−p−q>01-p-q>0 at every admissible valuation and every branch below is a probability with no clamping or renormalization. The two parameters penalize opposite routes, which is what makes the benchmark interesting: wind hurts the low corridor, altitude drops hurt the high crossing. Transitions. Writing clip(⋅)clip(·) for componentwise clamping into the grid bounds, every grid action has the same three-branch form ℙθ(s′∣s,a)=(1−p−q) 1[s′=redirect(sint)]+p 1[s′=redirect(swind)]+q 1[s′=redirect(sdrop)],P_θ(s s,a)=(1-p-q)\,1[s =redirect(s_int)]+p\,1[s =redirect(s_wind)]+q\,1[s =redirect(s_drop)], where sint=clip(s+move(a))s_int=clip(s+move(a)) is the intended move, the only branch that depends on a; swind=clip(s+(0,1,0))s_wind=clip(s+(0,1,0)) is the lateral drift; and sdrop=(x,y,z−1)s_drop=(x,y,z-1) if z>0z>0, else s itself, a ground-level skid. Coincident branches are summed, as in the datacenter benchmark. The map redirect(x,y,z)redirect(x,y,z) sends a candidate cell to Crash if it lies in the obstacle set O, to Goal if it lies in the target region T, and to the grid state (x,y,z)(x,y,z) otherwise. The layout is procedural in the grid extents. With yc=⌊Ly/2⌋y_c= L_y/2 , wx=max(1,⌊Lx/6⌋)w_x= (1, L_x/6 ), xw=⌊Lx/2⌋−⌊wx/2⌋x_w= L_x/2 - w_x/2 , xp=⌊3Lx/4⌋x_p= 3L_x/4 , and xc=Lx−max(2,⌊Lx/8⌋)x_c=L_x- (2, L_x/8 ), the obstacle set =slab∪pillar∪canopyO=O_slab _pillar _canopy consists of a wall spanning x∈[xw,xw+wx)x∈[x_w,x_w+w_x) at every altitude z≤Lz−2z≤ L_z-2 except a two-level corridor on the centerline (y=ycy=y_c, z≤1z≤ 1); a two-wide pillar at x=xpx=x_p, y∈yc,yc+1y∈\y_c,y_c+1\, z≤Lz−2z≤ L_z-2; and a canopy at the top altitude z=Lz−1z=L_z-1 restricted to x≥xcx≥ x_c. The target region =(Lx−1,y,0):y∈yc−1,yc,yc+1T=\(L_x-1,y,0):y∈\y_c-1,y_c,y_c+1\\ is a three-cell landing pad on the far wall. The generator checks that the start is not an obstacle and that ∩=∅T = . Together the slab, passable only through a corridor exposed to the wind, and the canopy, blocking the high route just before the goal, force a trade-off between a short low-altitude route hurt by p and a longer high-altitude route hurt by q, so the optimal route switches with (p,q)(p,q). Rewards and discount. The reward is deterministic and parameter-independent: r(s,a)=1r(s,a)=1 for (Goal,collect)( Goal, collect) and 00 for every other reachable state-action pair, so Rmax=1R_ =1. The optimal discounted value at s0s_0 is therefore exactly the discounted probability of eventually landing. The discount is γ=0.99γ=0.99, kept close to 11 because routes take on the order of LxL_x steps and a smaller discount would wash out the reachability signal over that horizon; this gives Vmax=Rmax/(1−γ)=100V_max=R_ /(1-γ)=100. Scalability. The grid extents (Lx,Ly,Lz)(L_x,L_y,L_z) are free parameters of the generator, subject to Lx≥8L_x≥ 8, Lz≥3L_z≥ 3, and odd Ly≥5L_y≥ 5 so that the centerline ycy_c is a single column. Every obstacle and goal formula above depends only on (Lx,Ly,Lz)(L_x,L_y,L_z), so the low-versus-high trade-off survives at every size, and ||=3+|(x,y,z)∈grid:(x,y,z)∉∪|=O(LxLyLz). =3+ \(x,y,z) :(x,y,z) \ =O(L_xL_yL_z). The benchmark comes in three sizes, listed in Table 4, and all share (pmax,qmax,γ)=(0.25,0.20,0.99)(p_ ,q_ ,γ)=(0.25,0.20,0.99) and the layout above, differing only in (Lx,Ly,Lz)(L_x,L_y,L_z). Name (Lx,Ly,Lz)(L_x,L_y,L_z) || uav-small (8,5,3)(8,5,3) 98 uav-medium (12,9,4)(12,9,4) 358 uav-large (24,15,6)(24,15,6) 1,813 Table 4: Sizes of the uav benchmark family used in the experiments. Every grid cell offers the same seven actions, so the family admits 7||−37 -3 memoryless deterministic policies. Even uav-small therefore rules out exhaustive search over policies. Appendix L Experimental data Regret results (RQ1). Table 5 gives the seed-level results summarized in Table 2. For each portfolio size K and each benchmark, it reports two quantities. The “max-regret” column is Rreg^D^(ΠK) Rreg_ D( _K), the largest portfolio regret over that seed’s 10001000 sampled valuations; these are the numbers averaged into Table 2, and they should be read against the benchmark’s VmaxV_max, listed in the header, since the datacenter values live on a scale over twenty times larger than the UAV ones. The “inertia” column is the K-means objective, the within-cluster sum of squared distances from each profile to its assigned center. It measures how tightly the loss profiles cluster, not how well the portfolio performs, and is included only as a diagnostic: it falls steeply with K on every benchmark, confirming that the candidate profiles do separate into distinguishable groups. Online selection results (RQ2). Figure 2 in the main text shows the two datacenter measures. Figures 14 and 15 show the same pair of measures for all four benchmarks, one benchmark per row, with all values of K overlaid within each panel. The left column is the fraction of the 9090 pooled runs whose recommended member is the best portfolio member at their hidden valuation; the right column is that recommendation’s normalized shortfall LθπL^π_θ, which is 00 when the best member is recommended and 11 when the worst is. Reading the two columns together is what the discussion in Section 4 relies on: the left column degrades visibly as K grows, since more members mean more near-ties to resolve, while the right column stays low throughout, showing that the members confused for one another are close in value and the cost of the confusion is small. uav-small uav-medium uav-large data-center-climate |S|=98|S|=98 |S|=358|S|=358 |S|=1813|S|=1813 |S|=330|S|=330 Vmax=100V_max=100 Vmax=100V_max=100 Vmax=100V_max=100 Vmax=2080V_max=2080 K seed max-regret inertia max-regret inertia max-regret inertia max-regret inertia 1 0 0.053 23.239 0.091 42.668 0.125 59.498 14.649 1313595.187 1 1 0.053 23.239 0.091 42.668 0.124 59.498 13.404 1313595.187 1 2 0.053 23.239 0.091 42.668 0.129 59.498 14.771 1313595.187 1 avg 0.053 23.239 0.091 42.668 0.126 59.498 14.275 1313595.187 2 0 0.032 1.935 0.019 3.974 0.016 1.629 4.127 215193.617 2 1 0.032 1.935 0.019 3.974 0.016 1.629 3.413 220731.474 2 2 0.032 1.935 0.020 3.974 0.018 1.629 4.053 215193.617 2 avg 0.032 1.935 0.019 3.974 0.017 1.629 3.864 217039.569 3 0 0.014 0.697 0.005 1.951 0.016 0.638 2.813 72737.797 3 1 0.027 1.157 0.005 1.951 0.014 1.317 2.836 72737.797 3 2 0.014 0.697 0.020 2.152 0.018 0.638 2.809 72737.797 3 avg 0.018 0.850 0.010 2.018 0.016 0.865 2.820 72737.797 5 0 0.002 0.094 0.003 0.193 0.016 0.107 2.809 37639.989 5 1 0.002 0.093 0.003 0.183 0.014 0.107 2.836 40156.574 5 2 0.002 0.093 0.003 0.183 0.015 0.107 2.730 39166.131 5 avg 0.002 0.093 0.003 0.186 0.015 0.107 2.792 38987.564 7 0 0.002 0.015 0.003 0.032 0.004 0.044 2.809 19076.922 7 1 0.002 0.012 0.003 0.032 0.003 0.044 1.170 20262.995 7 2 0.002 0.012 0.003 0.032 0.015 0.048 1.392 19462.184 7 avg 0.002 0.013 0.003 0.032 0.008 0.045 1.790 19600.700 10 0 0.002 0.002 0.003 0.007 0.004 0.010 0.817 8950.955 10 1 0.002 0.002 0.003 0.007 0.003 0.011 0.824 9239.430 10 2 0.002 0.002 0.003 0.009 0.002 0.010 0.759 8610.714 10 avg 0.002 0.002 0.003 0.008 0.003 0.011 0.800 8933.700 Table 5: Full regret results (RQ1). For each portfolio size K, rows 0–2 report the three clustering seeds and “avg” their arithmetic mean. “max-regret” is the largest sampled portfolio regret. “Inertia” is the K-means within-cluster sum of squared distances between data points and the cluster centroid, not a regret measure. Correct arm Normalised regret of recommended recommended arm Datacenter uav-small Figure 14: Reported UCB deployment results across all tested values of K, for the datacenter and uav-small benchmark (RQ2). Each row corresponds to a benchmark; columns show, left to right, the reported correct-arm rate for the recommended arm and the regret of the recommended arm. Correct arm Normalised regret of recommended recommended arm UAV-medium UAV-large Figure 15: Reported UCB deployment results across all tested values of K, for the UAV-medium and UAV-large benchmarks (RQ2). Each row corresponds to a benchmark; columns show, left to right, the reported correct-arm rate for the recommended arm and the regret of the recommended arm. Input: benchmark pMDP M, domain D, portfolio budgets K, seeds S, empirical robust regret sample size n, UCB sample size m, UCB parameters (H,ε,δ)(H, ,δ) foreach K∈K do // Offline candidate construction. Cells←DiscretizeDomain(D) Cells← DiscretizeDomain(D); Candidates←ComputeCandidatePolicies(M,Cells) Candidates← ComputeCandidatePolicies(M, Cells); // Offline robust candidate evaluation. Scores←RobustPolicyEvaluation(M,Cells,Candidates) Scores← RobustPolicyEvaluation(M, Cells, Candidates); // Offline mini-max regret evaluation. ComputeMinimaxRegret(Scores, Cells, Candidates); foreach s∈s do // Offline construction of portfolio. Π←ReduceAndCluster(Candidates,Scores,K,s) ← ReduceAndCluster( Candidates, Scores,K,s); // Offline empirical robust regret evaluation of portfolio. D^←SampleDomain(D,n,s) D← SampleDomain(D,n,s); foreach θ∈D^θ∈ D do V∗←OptimalValue(M,θ)V^*← OptimalValue(M,θ); VΠ←maxπ∈ΠEvaluatePolicy(M,θ,π)V_ ← _π∈ EvaluatePolicy(M,θ,π); r←V∗−VΠr← V^*-V_ ; Store(K,s,θ,r) Store(K,s,θ,r); Maximise empirical robust regret within one seed; // Online UCB-based deployment. D^←SampleDomain(D,m,s) D← SampleDomain(D,m,s); foreach θ∈D^θ∈ D do Create generative model GθG_θ; z←RunUCB(Gθ,Π,H,ε,δ)z← RunUCB(G_θ, ,H, ,δ); Store(K,s,θ,z) Store(K,s,θ,z); Average empirical robust regret over seeds; Pool UCB samples across seeds; GenerateReport() GenerateReport(); Algorithm 2 Paired portfolio synthesis and evaluation protocol