Adaptive Policy Portfolios for Robust Markov Decision Processes

Adaptive Policy Portfolios for Robust Markov Decision Processes Kasper Engelen1 , Sebastian Junges2 , Guillermo A. Pérez1 , Marnix Suilen1 1

University of Antwerp, Belgium Radboud University, Nijmegen, The Netherlands {kasper.engelen,guillermo.perez,marnix.suilen}@uantwerpen.be, sebastian.junges@ru.nl

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 ∀R-complete already for deterministic portfolios in acyclic (s, a)-rectangular RMDPs. Synthesizing a portfolio of unarybounded size is ∃∀R-complete for general rational polytopes, even with fixed discount and acyclic dynamics. The singlepolicy 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) (Wiesemann, Kuhn, and Rustem 2013) 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 (Ahmed et al. 2013; Rigter, Lacerda, and Hawes 2021) 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.

0.25

P1 = {1/2} P3 = {0, 1/2, 1} P5 = {0, 1/4, 1/2, 3/4, 1} P9 = C

0.20 Regret

arXiv:2608.17929v1 [cs.AI] 18 Aug 2026

2

0.15 0.10 0.05 0.00 0.0

0.2

0.4 0.6 True slip level p

0.8

1.0

Figure 1: Portfolio regret in the actuator example. 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. As a motivating example, consider an actuator whose true slip level is an unknown parameter p ∈ [0, 1]. Viewed as a single-state RMDP, each action is a calibration c ∈ C = {0, 1/8, . . . , 1}, and the unknown p sets the success probability 1 − (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/2 and has worst-case regret 1/4. The portfolio {0, 1/2, 1} reduces this to 1/16, while {0, 1/4, 1/2, 3/4, 1} reduces it to 1/64. Increasing the portfolio size provides a controlled form of adaptation while online selection remains over a finite set. Figure 1 plots these regret curves. 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 (Schaefer and Stefankovic 2024). The coNP lower bound was stated by Ghavamzadeh, Petrik, and Chow (2016) 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

Task

Nonrect. uncertainty

(s, a)-rectangular uncertainty

Hardness already holds for

Certify one given policy

∀R-complete

coNP-hard and coSQRS-hard; in ∀R

deterministic policies; acyclic models whose uncertain choices are two-Dirac, for coNP

Certify a given portfolio

∀R-complete

∀R-complete

deterministic portfolios with acyclic graphs and twosuccessor choices

Synthesize one randomized policy

∀R-hard and in ∃∀R

NP-hard, coNP-hard, SQRS± -hard; in ∃∀R

Synthesize at most k policies

∃∀R-complete

hard already for k = 1; exact complexity open

and

two-Dirac models for the Boolean bounds regret threshold 2, fixed discount, acyclic dynamics, two-successor uncertain choices

Table 1: Complexity of regret certification and synthesis. Certification is established by Theorems 1 to 4. Synthesis is established by Theorems 5 to 9.

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 (Iyengar 2005; Wiesemann, Kuhn, and Rustem 2013; Suilen et al. 2024). 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 ∀R-complete already for deterministic portfolios in acyclic (s, a)-rectangular RMDPs. Choosing a portfolio under a unary size budget adds one existential real block and is ∃∀R-complete for general rational polytopic uncertainty. The reduction couples choices, so it does not establish ∃∀Rcompleteness 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 (Cesa-Bianchi and Lugosi 2006) 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 ∀R-complete and bounded-portfolio synthesis is ∃∀Rcomplete (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 worstcase robust policies by optimizing over less conservative uncertainty sets (Wiesemann, Kuhn, and Rustem 2013; Benyamine et al. 2026). When multiple optimal robust policies exist, best-effort approaches can select among them without sacrificing worst-case value (Abate et al. 2026). A more adaptive response to fixed but initially unknown transition dynamics is provided by Bayes-adaptive MDPs (Guez, Silver, and Dayan 2012), hidden-model MDPs (Chades et al. 2012), and hidden-parameter MDPs (Doshi-Velez and Konidaris 2016). 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 nearoptimally for whichever environment turns out to be true (cf. Ghavamzadeh, Petrik, and Chow (2016)).

2

Problem Statement

For a finite set X, we write |X| for its cardinality, and D(X) for the set of discrete probability P distributions over X, i.e., functions µ : X → [0, 1] with x∈X µ(x) = 1. Vectors and matrices are boldface. For x ∈ Rn , 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 a choice. We fix an arbitrary ordering of the triples (s, a, s′ ) ∈ S × A × S, so that a vector u ∈ RS×A×S assigns a value u(s, a, s′ ) to each triple. We call u a transition vector if u(s, a, ·) ∈ D(S) for every choice (s, a). Definition 1 (RMDP). A robust Markov decision process (RMDP) is a tuple (S, A, U, R, sι , γ), where R : S × A → R is the reward function, sι ∈ S is the initial state, γ ∈ (0, 1)

is a discount factor, and U = {u ∈ RS×A×S | F u ≤ g} is a convex polytope of transition vectors, for F ∈ Rm×n , g ∈ Rm (n = |S||A||S|). The inequalities F u ≤ g include the constraints defining a transition vector, so every u ∈ U is a valid transition function. A policy maps paths to distributions over actions, π : (SA)∗ S → D(A). A memoryless randomized policy π : S → D(A) depends only on the current state. The set of such policies is ΠMR . A memoryless deterministic policy π : S → A further selects a single action per state. The set of such policies is ΠMD ⊆ ΠMR . Unless stated otherwise, candidate policies range over ΠMR . Each u ∈ U induces a classical MDP Mu = (S, A, Pu , R, sι , γ) with Pu (s, a)(s′ ) = u(s, a, s′ ). For a policy π, its value Vuπ : S → R in Mu is the expected discounted cumulative reward, ∞ i hX Vuπ (s) = Eπ γ t R(st , at ) s0 = s ,

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 , its robust regret (at sι ) is
Rreg(π) = sup Vu∗ (sι ) − Vuπ (sι ) , u∈U

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 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 Vu∗ (sι ) − max Vuπ (sι ) . (1)

and Vu∗ (s) = supπ Vuπ (s) is the optimal value. This supremum is attained by a policy in ΠMD and Vu∗ is computable in polynomial time for fixed u (Puterman 1994). 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 perchoice uncertainty sets is (s, a)-rectangular: U=

× U(s,a), (s,a)∈S×A

U(s,a) ⊆ R{s}×{a}×S .

We call U(s,a) the uncertainty set of choice (s, a), and the choice uncertain if U(s,a) is not a singleton. Intuitively, (s, a)rectangularity is an independence assumption across choices. The general case allows U to couple choices, whereas (s, a)rectangularity prohibits this. Subclasses of RMDPs. An uncertain choice is twosuccessor 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. V

π,rob

For a policy π, its robust value is

(s) = inf Vuπ (s), u∈U

the worst-case value π can guarantee against any realization in U. The robust optimal value is V rob (s) = supπ V π,rob (s), and a policy attaining it is robust optimal. Robust value compares policies in absolute terms, but it does not distinguish

π∈Π

u∈U

t=0

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(π) : π ∈ Π}. 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(π) follows. We seek the best guarantee achievable by a portfolio of bounded size k ≥ 1: ρk =

inf

Π⊆ΠMR :|Π|≤k

Rreg(Π).

Note ρ1 = inf π∈ΠMR Rreg(π): minimal single-policy regret is the k = 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 (Papadimitriou 1994; Arora and Barak 2009). Input conventions. The rewards, γ, threshold t, polytope data F , g, and policy matrices in QS×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 (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 );

• universal sentences ∀x1 , . . . , xn φ(x1 , . . . , xn ); • existential-universal sentences ∃x1 , . . . , xn ∀y1 , . . . , ym φ(x1 , . . . , xn , y1 , . . . , ym ). The truth problem of each fragment defines a complexity class, denoted ∃R, ∀R, and ∃∀R respectively (Schaefer and Stefankovic 2024). These classes sit between NP and PSPACE (Canny 1988; Basu, Pollack, and Roy 2006), and ∀R = co∃R and ∃R = co∀R. Square-root-sum. We also consider variants of the wellknown square-root-sum (SQRS) decision problem and their associated complexity classes. For the variants below, assume finite lists of positive integers a1 , . . . , am and b1 , . . . , bn , and an integer k, all encoded in binary. Pm √ • SQRS. Decide whether i=1 ai ≤ k. coSQRS is the complement class. • P SQRS± . GivenPan operator ▷◁∈ {≤, ≥}, decide whether p m √ n a ▷◁ b . i j i=1 j=1 Both SQRS and coSQRS reduce to SQRS± : SQRS uses bP= √(k 2 ); for coSQRS, test equality in polynomial time ( i ai ∈ Q iff every ai 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, Σp2 begins with an existential block followed by a universal block (Papadimitriou 1994; Arora and Barak 2009). Every level of PH, every fixed level of the real hierarchy considered above, and SQRS± lie in PSPACE (Canny 1988; Allender et al. 2009). 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 and a threshold t, decide whether
∆U (π1 , π2 ) = sup Vuπ1 (sι ) − Vuπ2 (sι ) ≤ t. u∈U

Policy comparison is tractable when π1 and π2 share no uncertain choice (Appendix 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 (Iyengar 2005; Suilen and Pérez 2026). Otherwise, it is coNP-hard1 already in acyclic (s, a)-rectangular RMDPs, and coNP-complete when no uncertain choice used by both policies lies on a cycle of either policy graph (Appendices 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 UNSAT. For a 3CNF formula φ, the RMDP keeps two local bits per literal occurrence, one certifying each value for the bits, and lets 1

This was stated by Ghavamzadeh, Petrik, and Chow (2016) but proved only under a restrictive constraint imposed on the policies. We give an unconditional proof of the fact in Appendix B.2.

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 accepts when every clause has a locally true literal. The consistency policy πK uniformly selects a variable and accepts when all its copies agree with one global value. Thus πC contributes either 0 or 1 to ∆U , while πK contributes the fraction of variables whose audits pass. Nature attains 2 exactly when φ is satisfiable; otherwise the difference is at most 2 − 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 Appendix B.4 and the example below). Membership in ∀R follows from a known adaptation of the Bellman equations for the value functions to the parametric setting (Junges et al. 2021). Example 1. Consider this RMDP with discount γ = 1/2. π1 (c)

sι

a

x 1−

x

c

π2 (c)

g

R=1

Fix the realization u ∈ U corresponding to x. The value of g is 2. Under π1 , reaching c gives one zero-reward step back to sι . Hence   1 1 x Vuπ1 (sι ) + (1 − x)2 , Vuπ1 (sι ) = 2 2 1−x hence Vuπ1 (sι ) = 1−x/4 . Under π2 , the state c has value zero,

so Vuπ2 (sι ) = 1−x. Thus Vuπ1 (sι )−Vuπ2 (sι ) = x(1−x) 4−x . This difference is zero at x = 0 and x = 1, but positive between √ ∗ them. Its maximum over [0, 1] is attained √ at x = 4 − 2 3. Substitution gives ∆U (π1 , π2 ) = 7 − 4 3. The square root appears because π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 ∀R-complete (Appendix 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 · · · pid 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 (Appendix B.5).

Portfolio comparison. Portfolio comparison remains ∀Rcomplete even under (s, a)-rectangular uncertainty. The pointwise maximum maxπ∈Π Vuπ 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 , and a threshold t ∈ Q, decide whether Rreg(π) ≤ t. Problem 2 (Portfolio-regret certification). Given an RMDP, a portfolio Π ⊆ ΠMR , and a threshold t ∈ Q, decide whether Rreg(Π) ≤ t. We show ∀R-membership for both problems: Theorem 1 (Membership). Regret certification is in ∀R. 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   π′ ∆U (π, Π) = sup Vuπ (sι ) − max V (s ) . ι u ′ u∈U

π ∈Π

b = For a source RMDP N and reference policy π0 , N Lift(N, π0 ) makes π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 uncerb be its image under Lift. tainty. For a source portfolio Π, let Π b then becomes comparison against π0 , up Certification in N b = Λ + ∆U (π0 , Π). to a known constant Λ: Rreg(Π) 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)-rectangular uncertainty. coNPhardness already holds when every uncertain choice is twoDirac and the only other stochastic rows are certain uniform splitters. Proof sketch. Apply Lift to Cmp(φ) and to the shared-cycle square-root-sum construction, respectively. The transformation converts each comparison threshold by one known additive constant. See Appendix E.1. The pointwise maximum over members makes portfolio comparison ∀R-hard even when rectangularity removes the corresponding alternation for one acyclic policy pair. The transformation Lift transfers this hardness to certification: Theorem 3. Portfolio-regret certification is ∀R-hard, already for deterministic portfolios and acyclic (s, a)rectangular RMDPs with two-successor uncertain choices.

Proof sketch. Apply Lift to the portfolio-comparison construction in Section 3.2. See Appendix E.2. Theorem 4. Given-policy robust regret is ∀R-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 ∀R-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 Appendix 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 ∈ Q, decide whether inf π∈ΠMR Rreg(π) ≤ t. Problem 4 (Bounded portfolio synthesis). Given an RMDP, a budget k encoded in unary, and a threshold t ∈ Q, decide whether ρk ≤ t. Portfolio regret is monotone under inclusion, and Rreg({π}) = Rreg(π). Thus minimal robust regret is the special case of bounded portfolio synthesis with k = 1. Theorem 5 (Membership). Minimal robust regret and bounded portfolio synthesis belong to ∃∀R. 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 Restrict makes disallowed actions so costly that minimizing over all policies comes within any rational ε > 0 of minimizing over the allowed policies (Appendix F). Combinatorial hardness under rectangular uncertainty. Theorem 6. Minimal robust regret is NP-hard and coNPhard on (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(φ) 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 NPhardness, 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−n , which supplies the required gap. The transformations Lift and Restrict preserve both gaps. Both reductions retain independent twoDirac 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)-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 > 0, its regret is   A(1 − x) Bx max , . 1 − (1 − q)x q + (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 − b and b − Cb . 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 ∀R-hard for arbitrary rational polytopic uncertainty. Proof sketch. Reduce from the ∀R-complete generalpolytope 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 anchor the branches so that only this mixing probability matters. They make its regret max{(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), again strictly increasing in ∆, so the comparison threshold transfers by a rational transformation. See Appendix I. Together with the upper bound above, this places singlepolicy minimal robust regret between ∀R-hardness and ∃∀Rmembership under general rational polytopic uncertainty. The current bounds do not establish completeness. Restricting the search to memoryless deterministic policies on acyclic (s, a)-rectangular RMDPs makes minimal robust regret Σp2 -complete (Appendix G). This is a different problem from Problem 3, which minimizes over ΠMR , and neither classification implies the other. In particular, the Σp2 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−n gap randomization cannot close.

Algorithm 1: Experimental pipeline 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;

Bounded portfolio synthesis. general upper bound is tight.

For bounded portfolios, the

Theorem 9. Bounded portfolio synthesis is ∃∀R-complete under general rational polytopic uncertainty, with k encoded in unary. Hardness holds already for regret threshold two, the fixed discount γ = 21 , 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 into tests gi (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 = 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. 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 = 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 = 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 795 memoryless deterministic policies, ruling out exhaustive search.

b θ∈D

π∈Π

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 (Cesa-Bianchi and Lugosi 2006) 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 (as a fraction of the return bound), confidence δ = 0.1, and empirical-Bernstein bounds (Mnih, Szepesvári, and Audibert 2008) to speed up convergence. For the UCB-based deployment, we uniformly draw 30 valuations and run UCB once per valuation with a trajectory of length H = 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 0 (best) and 1 (worst). Setup. The Python prototype uses Stormvogel (Volk et al. 2026), robust value iteration (Iyengar 2005), 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 90 samples across the three seeds. RQ1: Portfolios reduce robust regret. Table 2 shows empirical robust regret decreasing with K on every benchmark, with the largest single drop at K = 2, and further gains as K increases. The K = 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π∈Π(C) maxc∈C Lπ,c is 0.039, 0.118, 0.146, and 41.502 by column. Policy portfolios beat it for all K on the three largest benchmarks.

1 2 3 5 7 10

0.053 0.032 0.018 0.002 0.002 0.002

0.091 0.019 0.010 0.003 0.003 0.003

0.126 0.017 0.016 0.015 0.008 0.003

14.28 3.86 2.82 2.79 1.79 0.80

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. 100 80 60 40

K=2 K=3 K=5 K=7 K=10

20 0

100

104 102 106 Number of iterations

(a) Runs with the correct arm recommended.

Regret (best and worst policy)

b ⊂D Portfolio evaluation. A uniform parameter sample D b with |D| = 1000 is drawn to estimate portfolio regret by   [ b (Π) = max Vθ∗ (sι ) − max Vθπ (sι ) , Rreg D

UAV-S UAV-M UAV-L datacenter (98) (358) (1813) (330)

Construction time 43.8s

% of correct samples

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 induces a realization u ∈ U. Discretizing each parameter into 10 bins gives a set C of 100 cells c for our two-parameter benchmarks, and the optimal policy at each cell midpoint mid(c) becomes a candidate π ∈ Π(C) in the candidate set. Robust policy evaluation then assigns each candidate π a midpoint-based approximate regret vector Lπ ∗ with one entry per cell: Lπ,c = Vmid(c) (sι ) − inf θ∈c Vθπ (sι ). We then use K-means over these vectors to select the policy nearest each center, resulting in a set ΠK ⊆ Π(C) of policies. Clustering is a computationally cheap approximation for obtaining portfolios of deterministic policies.

K

K=2 K=3 K=5 K=7 K=10

0.6 0.5 0.4 0.3 0.2 0.1 0.0

100

104 102 106 Number of iterations

(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 2a gives the fraction of UCB runs recommending the best portfolio policy at each iteration. Identification slows as the portfolio grows: after 104 iterations, about half the runs recover the best member at K = 10. Since this ignores how well the remaining members perform, Figure 2b instead reports the regret of the recommended policy relative to the best portfolio policy, and there the value difference after 104 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 ∀R-complete and bounded synthesis ∃∀R-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 ∀R-hardness and ∃∀Rmembership for single-policy minimal robust regret, remain open.

References Abate, A.; Badings, T.; Giacomo, G. D.; and Fabiano, F. 2026. Best-Effort Policies for Robust Markov Decision Processes. In AAAI, 36120–36128. AAAI Press. Ahmed, A.; Varakantham, P.; Adulyasak, Y.; and Jaillet, P. 2013. Regret based Robust Solutions for Uncertain Markov Decision Processes. In NIPS, 881–889. Allender, E.; Bürgisser, P.; Kjeldgaard-Pedersen, J.; and Miltersen, P. B. 2009. On the Complexity of Numerical Analysis. SIAM J. Comput., 38(5): 1987–2006. Arora, S.; and Barak, B. 2009. Computational Complexity A Modern Approach. Cambridge University Press. Basu, S.; Pollack, R.; and Roy, M.-F. 2006. Algorithms in real algebraic geometry. Springer. Benyamine, A.; Grand-Clément, J.; Petrik, M.; Jordan, M. I.; and Durmus, A. 2026. Dynamic Programming for Epistemic Uncertainty in Markov Decision Processes. CoRR, abs/2602.03381. Canny, J. F. 1988. Some Algebraic and Geometric Computations in PSPACE. In STOC, 460–467. ACM. Cesa-Bianchi, N.; and Lugosi, G. 2006. Prediction, learning, and games. Cambridge University Press. ISBN 978-0-52184108-5. Chades, I.; Carwardine, J.; Martin, T. G.; Nicol, S.; Sabbadin, R.; and Buffet, O. 2012. MOMDPs: A Solution for Modelling Adaptive Management Problems. In AAAI, 267–273. AAAI Press. Doshi-Velez, F.; and Konidaris, G. D. 2016. Hidden Parameter Markov Decision Processes: A Semiparametric Regression Approach for Discovering Latent Task Parametrizations. In IJCAI, 1432–1440. IJCAI/AAAI Press. Ghavamzadeh, M.; Petrik, M.; and Chow, Y. 2016. Safe Policy Improvement by Minimizing Robust Baseline Regret. In NIPS, 2298–2306. Guez, A.; Silver, D.; and Dayan, P. 2012. Efficient Bayes-Adaptive Reinforcement Learning using SampleBased Search. In NIPS, 1034–1042. Iyengar, G. N. 2005. Robust Dynamic Programming. Math. Oper. Res., 30(2): 257–280. Junges, S.; Katoen, J.; Pérez, G. A.; and Winkler, T. 2021. The complexity of reachability in parametric Markov decision processes. J. Comput. Syst. Sci., 119: 183–210. Mnih, V.; Szepesvári, C.; and Audibert, J.-Y. 2008. Empirical Bernstein stopping. In Proceedings of the 25th International Conference on Machine Learning, ICML ’08, 672–679. New York, NY, USA: Association for Computing Machinery. ISBN 9781605582054. Papadimitriou, C. H. 1994. Computational complexity. Addison-Wesley. Puterman, M. L. 1994. Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley Series in Probability and Statistics. Wiley. Rigter, M.; Lacerda, B.; and Hawes, N. 2021. Minimax Regret Optimisation for Robust Planning in Uncertain Markov Decision Processes. In AAAI, 11930–11938. AAAI Press.

Schaefer, M.; and Stefankovic, D. 2024. Beyond the Existential Theory of the Reals. Theory Comput. Syst., 68(2): 195–226. Suilen, M.; Badings, T.; Bovy, E. M.; Parker, D.; and Jansen, N. 2024. Robust Markov Decision Processes: A Place Where AI and Formal Methods Meet. In Principles of Verification (3), volume 15262 of Lecture Notes in Computer Science, 126–154. Springer. Suilen, M.; and Pérez, G. A. 2026. On the Complexity of Robust Markov Decision Processes and Bisimulation Metrics. In CONCUR. To appear; arXiv:2604.26748. Volk, M.; Heck, L.; Junges, S.; Katoen, J.; and Quatmann, T. 2026. Probabilistic Model Checking Taken by Storm: A Tutorial on the Probabilistic Model Checker Storm. In FM, volume 16557 of Lecture Notes in Computer Science, 524–549. Springer. Wiesemann, W.; Kuhn, D.; and Rustem, B. 2013. Robust Markov Decision Processes. Math. Oper. Res., 38(1): 153– 183.

Appendix Contents A Conventions and primitives

10

B On Policy and Portfolio Comparison

12

C Proofs of Theorems 1 and 5: Membership for Certification and Synthesis

21

D Exact Transfer from Policy Comparison to Robust Regret

21

E Proofs of Theorems 2 to 4: Transferring Comparison Bounds to Certification

24

F Proof of Theorem 6: Combinatorial Minimal-Regret Hardness

25

G Deterministic Minimal-Regret Complexity

29

H Proof of Theorem 7: Signed Square-Root-Sum Hardness

32

I

Proof of Theorem 8: General-Polytope Minimal-Regret Hardness

36

J

Proof of Theorem 9: Bounded Portfolio Synthesis

38

K Experimental setup

44

L Experimental data

48

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 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 β=

19 , 20

γ0 = β 2 =

361 . 400

The identity β 2 = γ0 is needed by the exact comparison-to-regret lift, while  2 1 + γ0 + γ02 >2 1 + γ0 is the numerical inequality used by the normalized square-root gadget. All appendix constructions use γ0 unless stated otherwise. The bounded-synthesis reduction uses γ = 21 because it does not invoke the lift and hence does not require β 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, 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γ d c to the value at the initial state. For a choice (s, a), call the distribution 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 for a ruinous sink. Definition 3 (Local-bit verifier primitives). For an occurrence o and Boolean value c, a local-bit selector qo,c has outcomes 1 0 and row , qo,c qo,c 0 1 {(1 − p)δqo,c + pδqo,c : p ∈ [0, 1]}. (2) Its vertices encode the bit bo,c = p ∈ {0, 1}. A pair test for an occurrence with designated satisfying value val(o) reads qo,val(o) and then qo,1−val(o) . Outcomes (1, 0) certify local truth and (0, 1) certify local falsity. An audit committed to value c visits qo,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 and −γ −H . Then their value difference is the sum of their acceptance probabilities. Proof. Every accepting run contributes γ 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 and a rational Z > 0. Every action at ⊥r has reward −(1 − γ)Z and the singleton row {δ⊥r }, so V (⊥r ) = −Z. Every otherwise undescribed choice at a nonterminal state has reward zero and the singleton row {δ⊥r }. Write V bd = maxs,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 > 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 } 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 for every compliant policy ρ̄, every state s other than ⊥r , and every realization u, and suppose γZ > M + 1. Then Vuπ (s) ≤ Vuπ̄ (s) for every stationary randomized policy π, every state, and every realization.

Proof. Both policies have value −Z at ⊥r , so fix any other state s. The action value of a nonruinous choice (s, a) under Vuπ̄ is the value at s of the compliant policy that plays a once and follows π̄ afterwards, hence at least −M . A ruinous choice has action value γV (⊥r ) = −γZ < −M − 1, strictly smaller. Writing Tπ for the Bellman operator of π at u, evaluating both policies at Vuπ̄ therefore gives Tπ Vuπ̄ ≤ Tπ̄ Vuπ̄ = Vuπ̄ , since π̄ redistributes π’s ruinous mass onto strictly larger action values. Monotonicity and contraction of Tπ give Vuπ ≤ Vuπ̄ . Under the default rule, M = V bd by the standard bound on discounted values, so the hypothesis holds. A construction that fixes its own constant instead, such as Zr 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ε 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(φ) 1 denotes the Boolean comparison RMDP of Definition 6, together with its clause and consistency policies and threshold 2 − 2n . For a source RMDP N and reference policy π0 , Lift(N, π0 ) denotes the exact regret lift of Definition 10, with its allowedaction family specified by context. Restrict(N, Aallow , ε) denotes the policy-restriction transformation of Definition 12. Finally, 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|) 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 Schaefer and Stefankovic (2024, Proposition 2.13) 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 . Write such a polynomial as ) ( N N dν mon mon X X Y |cν | . cν wν,j , dν ≤ 4, B = max 1, F (w) = ν=1

ν=1

j=1

Thus |F | ≤ B on the box, and B has polynomial encoding length. Definition 4 (Degree-four residual normal form). For every occurrence wν,j , introduce a copy zν,j ∈ [0, 1] and residual hcp ν,j = zν,j − wν,j . Compute each monomial with auxiliary coordinates in [0, 1]: • for dν = 0, set pν = 1, and for dν = 1, set pν = zν,1 ; • for dν = 2, use hν = pν − zν,1 zν,2 ; • for dν = 3, use tν − zν,1 zν,2 and pν − tν zν,3 ; • for dν = 4, use tν,12 − zν,1 zν,2 , tν,34 − zν,3 zν,4 , and pν − tν,12 tν,34 . These copy and product residuals lie in [−1, 1], are affine or affine plus one product of distinct variables, and have a common P zero exactly at correct copies and products. The decoded polynomial is Fb = ν cν pν . When an explicit output is needed, introduce ō ∈ [0, 1], put o = B(2ō − 1), and append hout = (o − Fb)/(2B); this residual also lies in [−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 Q |pν − j wν,j | ≤ 7δ and |Fb − F | ≤ 7Bδ. If the output residual is present and δ ′ also includes |hout |, then |o − F | ≤ 9Bδ ′ . Proof. For a, b, a′ , b′ ∈ [0, 1], |ab − a′ b′ | ≤ |a − a′ | + |b − b′ |, because 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δ. For degree three it is at most P δ + 3δ + δ = 5δ, and for degree four it is at most δ + 3δ + 3δ = 7δ. Therefore |Fb − F | ≤ 7δ ν |cν | ≤ 7Bδ. With the output residual, |o − Fb| = 2B|hout | ≤ 2Bδ ′ , and the triangle inequality gives the last claim.

A.3

Encoding primitives

For an uncertainty vector u, policy table σ, values vs , and action values qs,a , define ! ! ^ X ^ X ′ Bell(σ, u, v, q) = vs = σs,a qs,a ∧ qs,a = R(s, a) + γ u(s, a, s )vs′ . s

a

s′

s,a

Let ΦU (u) be the rational linear description of the uncertainty polytope, including nonnegativity and normalization, and let ! ^ X ^ Policy(σ) = σs,a = 1 ∧ σs,a ≥ 0. s

a

s,a

Lemma 13 (Universal Bellman encoding). For an explicit family Π = {π1 , . . . , πr } and a universally quantified policy τ , the assertion Vuτ (sι ) − max Vuπi (sι ) ≤ t for every u ∈ U i≤r

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 r r   ^ _
τ τ i i r τ τ i i ∀ τ, u, v , q , (v , q )i=1 : Policy(τ ) ∧ ΦU (u) ∧ Bell(τ, u, v , q ) ∧ Bell(πi , u, v , q ) =⇒ vsτι − vsi ι ≤ t . i=1

i=1

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.

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 , and a rational threshold t, decide whether
∆U (π1 , π2 ) = sup Vuπ1 (sι ) − Vuπ2 (sι ) ≤ t. u∈U

A choice (s, a) is used by π if s is reachable with positive probability under some realization and π(s, a) > 0. It is shared by π1 and π2 if both use it. The set of shared choices is denoted Sh(π1 , π2 ). Call s absorbing under π when every choice used by π at s has row {δs }. Let Gπ contain s → s′ when a choice used by π at s can reach 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) is cycle-free under π if s lies on no directed cycle of Gπ . We write CF(π) for these choices. Definition 5 (Cycle-free on shared choices). The pair (π1 , π2 ) is cycle-free on shared choices if Sh(π1 , π2 ) ⊆ CF(π1 )∩CF(π2 ). , π2 ) = supu∈U Dπ1 ,π2 (u). For a polytope P , For π1 , π2 and u ∈ U, write Dπ1 ,π2 (u) := Vuπ1 (sι ) − Vuπ2 (sι ), so that ∆U (π1Q write vert(P ) for its set of vertices. For (s, a)-rectangular U, write Vert(U) := s,a vert(Us,a ) for the set of vertex tuples. Separated choices. so

If π1 and π2 share no uncertain choice, rectangularity lets nature optimize their used rows independently, ∆U (π1 , π2 ) = sup Vuπ11 (sι ) − inf Vuπ22 (sι ). u1

u2

This is a direct consequence of the standard optimistic and robust fixed-policy linear programs and is computable in polynomial time (Iyengar 2005; Suilen and Pérez 2026).

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)-rectangular RMDPs in which every uncertain choice is a two-Dirac segment and the only other stochastic row is a certain uniform splitter. Vm Fix a 3-CNF formula φ = i=1 Ci over variables x1 , . . . , xn . We may remove tautological clauses, repeated literals, and variables with no occurrence; the constant case is decided directly, so assume n ≥ 1. For a literal occurrence o, let var(o) be its variable, let val(o) ∈ {0, 1} be the value that makes its literal true, and order the occurrences Ox 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,1 and bo,0 , indexed by the values they certify. The equation bo,c = 1 says that occurrence o is locally consistent with value c. Occurrence o is locally true when bo,val(o) = 1 and bo,1−val(o) = 0. Write ΦC for the clause condition ! m ^ _
ΦC := bo,val(o) ∧ ¬bo,1−val(o) . (3) i=1

o∈Ci

The local bits of different clauses are disjoint. For every original variable x, introduce a global bit Xx . For each variable write ^ ^ ΦxK := bo,Xx , ΦK := ΦxK .

(4)

x

o∈Ox

Lemma (Clause-local equivalence). Formula φ is satisfiable iff its global and local bits have an assignment satisfying ΦC ∧ΦK . Proof. If a valuation v satisfies φ, set Xx = v(x) and set bo,c = 1 exactly when c = v(var(o)). Every ΦxK holds. Every clause has an occurrence o with val(o) = v(var(o)), so that occurrence has the locally true pattern and ΦC holds. Conversely, suppose ΦC ∧ ΦK holds and define v(x) := Xx . Each clause has a locally true occurrence o with bo,1−val(o) = 0. var(o)

Since ΦK satisfied.

forces bo,Xvar(o) = 1, we have Xvar(o) = val(o). Thus the literal at o is true under v, and every clause is

ΦK does not force an occurrence’s two bits to be complementary. The pair test is part of ΦC . Example (A clause-local encoding). Consider φ = (x1 ∨ ¬x2 ∨ x3 ) ∧ (¬x1 ∨ x2 ∨ x3 ). Take the valuation: x1 = x2 = 1, x3 = 0, so Xx1 = Xx2 = 1 and Xx3 = 0. Following the encoding in the proof above, set bo,c = 1 exactly when c = Xvar(o) , for every occurrence o. Clause

literal

var(o)

val(o)

Xvar(o)

(bo,1 , bo,0 )

locally true?

C1

x1 ¬x2 x3

x1 x2 x3

1 0 1

1 1 0

(1, 0) (1, 0) (0, 1)

yes no no

C2

¬x1 x2 x3

x1 x2 x3

0 1 1

1 1 0

(1, 0) (1, 0) (0, 1)

no yes no

A literal is locally true exactly when bo,val(o) = 1, i.e., when val(o) = Xvar(o) : this holds for x1 in C1 and x2 in C2 , matching the fact that these are the literals true under the valuation. Using the labels o1 , . . . , o6 , 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 ) , ΦxK1 = bo1 ,1 ∧ bo4 ,1 ,

ΦxK2 = bo2 ,1 ∧ bo5 ,1 ,

ΦxK3 = bo3 ,0 ∧ bo6 ,0 ,

ΦK = ΦxK1 ∧ ΦxK2 ∧ ΦxK3 .

Substituting the values from the table: in ΦC ’s first bracket, o1 gives (1 ∧ 1) = 1 while o2 , o3 give 0, so the bracket is 1; in the second, o5 gives (1 ∧ 1) = 1 while o4 , o6 give 0, so that bracket is also 1; hence ΦC = 1. Each ΦxK is a conjunction of two matching bits (e.g. ΦxK1 = 1 ∧ 1 = 1), so ΦK = 1 as well. The reduction realizes ΦC as a clause scan and each ΦxK 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. Vm Definition 6 (Boolean comparison RMDP). For a 3-CNF formula φ = i=1 Ci over variables x1 , . . . , xn with n ≥ 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, U, R, sι , γ0 ), with the following components. • S is the disjoint union of the following groups. – The initial state sι . – Clause-scan states: a control state fi,j for each literal occurrence o = (i, j), together with the terminals accC and rejC . 0 1 – Audit states: global selectors qXx with outcomes qX , qX , controls kx,c,ℓ that inspect the ℓth occurrence of x after x x committing to c ∈ {0, 1}, together with the terminals accK and rejK . – Shared local-bit selectors: for each occurrence o and c ∈ {0, 1}, the selector of Definition 3, used by both policies. – Padding states Spad , reward-free, fixed once the transitions below are defined. – A ruinous sink ⊥r .

fi,j : test x

1 − po,1

πC : next literal πK : reject

0 qo,1

1 − po,0

qo,1 po,1

certain uniform splitter

qXx 1/n

pX x

1 qX x

kx,1,ℓ

πC 1 qo,1

πC : next clause or accept

1 qo,0

πC : next literal or reject

qo,0 po,0

πK

0 qo,0

πK : next copy or accept

Figure 3: The shared fragment for a positive occurrence o = (i, j) and the audit branch Xx = 1. The clause scan tests the pair (bo,1 , bo,0 ), whereas this audit branch needs only bo,1 . The branch Xx = 0 analogously audits qo,0 . Selector arrows are uncertain; arrows from outcome states are the certain, role-specific actions of the two policies. • At sι , action aC enters f1,1 , whereas action aK has the fixed uniform transition to qXx , x ∈ {x1 , . . . , xn }. Every selector c has one action. Outcome qX leads to kx,c,1 , each fi,j leads to the first local selector for its occurrence, and each kx,c,ℓ x b leads to the corresponding qo,c . From a shared outcome qo,c , the clause-scan action and audit action have their respective deterministic continuations, ending in accC /rejC or accK /rejK 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. Spad 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 Xx and local bit (o, c). All remaining described choices are singletons, including the certain uniform splitter at sι . Its vertices are exactly the Boolean realizations pz ∈ {0, 1}. • accC is the terminal with payoff γ0−H and accK the terminal with payoff −γ0−H , while every other described reward, including at rejC , rejK and at padding states, is zero. • All remaining choices use ruinous-sink completion. • The initial state is sι and the discount is γ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 – this probability is always 0 or 1, and we speak of π accepting or rejecting outright. The clause policy. Policy πC processes clauses and their literals in order. At occurrence 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 checks exactly ΦC . The consistency policy. Policy πK first takes the certain uniform splitter, which selects a variable x. It reads Xx and thereby commits to c ∈ {0, 1}. It then uses the audit chain of Definition 3 over Ox in clause-major order. Conditioned on the certain uniform splitter selecting x, πK therefore checks exactly ΦxK . Lemma (Unambiguous prescriptions). Both policies above are stationary deterministic policies. Proof. The clause scan encounters each fi,j once and reaches the two selectors of an occurrence in the fixed order prescribed c above. An audit branch commits at qX before reaching any kx,c,ℓ . Thus each policy prescribes a single continuation at every x b outcome state it can reach. At a shared outcome qo,c , 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 = 1. Lemma (Policy semantics). At a vertex u of the uncertainty polytope, πC accepts under u exactly when ΦC holds under u. Conditioned on the certain uniform splitter selecting x, πK accepts under u exactly when ΦxK holds under u; unconditionally, this makes πK ’s probability of accepting under u equal to n1 |{x : ΦxK holds under u}|, the fraction of variables whose audit would pass. Moreover, DπC ,πK (u) = 1{πC accepts under u} + Pr[π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 1 and −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 confirms x1 in C1 and x2 in C2 , and every variable audit passes, giving difference 2. Now take the unsatisfying valuation x1 = 0, x2 = 1, x3 = 0 and its canonical local pairs. The clause scan rejects C1 , although every audit passes. If only the copy of x1 in C1 is changed from (0, 1) to (1, 0), the clause scan accepts, but the x1 audit, committed to 0, reads bo,0 = 0 and rejects. The malformed pairs (0, 0) and (1, 1) cannot make a literal locally true because the clause scan tests both bits. Lemma 15. There is a vertex under which π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)-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) 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 and πK ’s value difference attains its maximum at a tuple of choice vertices. By this and the two lemmas above, φ ∈ SAT =⇒ ∆U (πC , πK ) = 2, 1 . n In the first case, nature chooses the canonical vertex of a satisfying valuation. In the second, a vertex satisfying ΦC has at least one failing variable audit by Lemma 15, and therefore has difference at most 1 + (n − 1)/n; a vertex violating ΦC has difference at most 1. Vertex sufficiency shows that an interior realization cannot do better. φ ∈ UNSAT =⇒ ∆U (πC , πK ) ≤ 2 −

1 . The construction satisfies Proof of Theorem 14. Use threshold 2 − 2n

φ ∈ UNSAT ⇐⇒ ∆U (πC , πK ) ≤ 2 −

1 . 2n

Indeed,

1 1 <2− < 2. n 2n The construction has polynomial size, γ0−H = (400/361)H has O(H) bits, and all uncertain choices are independent two-Dirac choices. This is a polynomial reduction from UNSAT. 2−

B.3

Vertex-Extremal Membership

Theorem 16 (Vertex-extremal membership). Robust policy comparison is in coNP for (s, a)-rectangular polytopes when both policies are cycle-free on shared choices (Definition 5). Definition 7 (Vertex-extremal pair). The pair (π1 , π2 ) is vertex-extremal if sup Dπ1 ,π2 (u) = u∈U

max v∈Vert(U )

Dπ1 ,π2 (v).

Lemma 17 (Cycle-freeness on shared choices implies vertex-extremality). If (π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 Us0 ,a0 , hold every other block fixed, and consider two cases according to whether (s0 , a0 ) ∈ Sh(π1 , π2 ). Then iterate over the blocks. • (s0 , a0 ) ∈ / Sh(π1 , π2 ), say only π1 uses it. Then Vuπ2 (sι ) is constant in this block, and Dπ1 ,π2 differs from Vuπ1 (sι ) by a constant. By Cramer’s rule applied to the one equation of π1 ’s Bellman system that this block enters, Vuπ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 ,π2 , extremal at a vertex.

u, r u

s1

s

0 v, 0 p, cv

s2

1 − p, cv

⊥

0

Figure 4: The shared-cycle gadget realizing one normalized square-root term. • (s0 , a0 ) ∈ Sh(π1 , π2 ) (hence, by hypothesis, cycle-free under both π1 and π2 ). If s0 is absorbing under one of the two policies, then that policy uses (s0 , a0 ) and the choice has row {δs0 }, so the block is the singleton {δs0 } and Dπ1 ,π2 is constant in it. Otherwise no self-loop was omitted at s0 , so cycle-freeness is the literal graph condition. Under either policy, a run then uses the choice (s0 , a0 ) at most once. The probability of reaching s0 is independent of its outgoing row, and the continuation value after leaving s0 cannot depend on that row because the run never returns. Conditioning on reaching and selecting (s0 , a0 ) 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 ,π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 (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 ∈ U , 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)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)-rectangular and use the appendix-wide discount γ0 required by the exact lift. Fix √ b ≥ 2, m = ⌈ b⌉. √ √ We round b up to the nearest integer m, so that b ≤ m2 (needed below), while m stays close enough to b for the final identity to come out exactly right. The local gadget in Figure 4 has entry state s, intermediate states s1 , s2 , and a zero-reward sink. Policy πu chooses u at s and moves to s1 with reward ru . Policy πv chooses v and moves to s2 directly, with reward zero. The forced edge s1 → s2 has reward zero: its only purpose is to give πu one extra step before reaching s2 , so that its eventual return to s is discounted one extra factor of γ0 compared to πv ’s. This asymmetry in cycle length is essential: without it, Qu − Qv 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 s2 , the unique shared uncertain choice returns to s with probability p and enters the √1 − p, paying reward cv either way. Our goal is to choose U, V, cv , ru
sink with probability so that supp∈[0,1] Qu (p) − Qv (p) takes the form Cb − b, for a constant Cb depending only on b. Lemma 19 establishes this. Set m(1 − γ0 ) U= , 2γ0 b(1 − γ0 ) V = , 2m V cv = , γ0 (1 − γ0 )(m2 − γ02 b) ru = U − γ0 V = . 2γ0 m All constants are nonnegative: U, V, cv > 0, while m2 ≥ b > γ02 b gives ru > 0. The Bellman equations give, writing Qi (p) := Vuπi (s) for the value of πi at the entry state as a function of the shared return probability p, Qu (p) = ru + γ02 cv + γ03 pQu (p) =

U , 1 − γ03 p

Qv (p) = γ0 cv + γ02 pQv (p) =

V . 1 − γ02 p

Lemma 19 (Rational-fraction maximum). With the constants above, √
sup Qu (p) − Qv (p) = Cb − b,

Cb =

p∈[0,1]

Proof.

m γ0 b + . 2γ0 2m

Put x = 1 − γ02 p. Then x ∈ [1 − γ02 , 1] and f (x) =

V U − . 1 − γ 0 + γ0 x x

After multiplying by the positive denominators, the sign of f ′ (x) is the sign of p √ V (1 − γ0 + γ0 x) − γ0 U x. Since V ≤ γ0 U , 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 ≤ γ0 U

and

γ0 U ≤ h2γ0 V,

1 − γ03 434721 = . 1 − γ02 304400

h γ0 =

The first inequality is b ≤ m2 . The second follows from m2 /b ≤ 2 and the exact rational comparison h2γ0 > 2. At the critical point, direct substitution yields √ √ ( U − γ0 V ) 2 m γ0 b √ max f = − b. = + 1 − γ0 2γ0 2m This value is nonnegative by the arithmetic-geometric mean inequality applied to m/γ0 and γ0 b/m. Combining independent copies. For inputs b1 , . . . , bn , take disjoint copies of the gadget. A fresh certain uniform splitter enters each copy with probability 1/n. Scaling all rewards in every copy by n/γ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 n n p X X ∆U (πu , πv ) = Cbi − bi . i=1

i=1

Proof of Theorem 18. Reduce from the coSQRS variant asking whether X t= Cbi − k.

P √ i

bi ≥ k. Set

i

Then ∆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 ∀R-complete for deterministic policies under general rational polytopic uncertainty. Lemma 21 (∀R membership for policy comparison). Robust policy comparison is in ∀R for deterministic policies under general rational polytopic uncertainty. Proof. Apply Lemma 13 with τ fixed to π1 and the singleton family {π2 }. Definition 8 (Polynomial-evaluation RMDP). Fix an explicit sparse polynomial f (p) =

N X ℓ=1

cℓ

dℓ Y

piℓ,j ,

p ∈ [0, 1]m ,

j=1

and a rational discount γ ∈ (0, 1). The component Polyγ (f ) is defined as follows. • A reward-zero certain uniform splitter at sf enters branch ℓ with probability 1/N . That branch has states b0ℓ , . . . , bdℓ ℓ and a common zero-reward sink ⊥. • At bj−1 , the unique action continues to bjℓ with probability uℓ,j and enters ⊥ otherwise. State bdℓ ℓ is absorbing with value ℓ rℓ = N γ −(dℓ +1) cℓ .

(1 − γ)rℓ b0ℓ

uℓ,1

uℓ,2

b1ℓ 1−

uℓ,

1

uℓ

,2

uℓ,dℓ

bdℓ ℓ

1 − uℓ,dℓ

1−

···

⊥

0

Figure 5: One branch of the polynomial-evaluation RMDP. Equalities in U tie repeated parameter occurrences across branches. • Each uℓ,j is a coordinate of a two-successor row in [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(bdℓ ℓ ) = (1 − γ)rℓ . • All remaining choices use ruinous-sink completion. whenever iℓ,j = i; occurrences for every parameter and impose uℓ,j = urep For policy comparison, choose a representative urep i i of 1 − pi , when present, instead satisfy uℓ,j = 1 − urep . Together with stochasticity and box constraints, these equalities define i U and the resulting RMDP Mf = (S, A, U , R, sf , γ). 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. Lemma P Q 22 (Polynomial evaluation). For every realization of the occurrence rows, the compliant value of Polyγ (f ) is c ℓ ℓ j uℓ,j . In particular, when the representative coordinates equal p, the unique compliant policy of Mf has value f (p) at sf . 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(N maxℓ dℓ ) and rewards of polynomial encoding length. Moreover, U is one rational polytope of polynomial description size. Q Proof. Branch ℓ is reached with probability 1/N , survives with probability j uℓ,j , and reaches its terminal after dℓ + 1 transitions. Its discounted contribution is therefore 1 dℓ +1  −(dℓ +1)  Y γ Nγ cℓ uℓ,j , N j and summing gives the first identity. The representative equalities then give 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 (∀R hardness for policy comparison). Robust policy comparison is ∀R-hard for deterministic policies under general rational polytopic uncertainty. Proof. By the strict degree-six normal form of Schaefer and Stefankovic (2024, Lemma 2.8) and their bounded-open equivalence (Schaefer and Stefankovic 2024, Proposition 2.12), ∃p ∈ [0, 1]m : f (p) > 0 is ∃R-complete for an explicitly represented degree-six polynomial. Indeed, the affine image of the source box is (0, 1)m , and strict positivity there is equivalent to strict positivity on its closure by continuity. Its complement is ∀p : f (p) ≤ 0. Construct Mf by Definition 8, add a fresh initial choice between sf and a zero-reward sink, and let deterministic policies πf , π⊥ choose the two actions. By Lemma 22, ∆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 , an input portfolio Π ⊂ ΠMR , and rational t, decide whether   ∆U (π0 , Π) = sup Vuπ0 (sι ) − max Vuπ (sι ) u∈U

π∈Π

≤ t.

Theorem 24. Portfolio comparison is ∀R-complete, with portfolio size part of the input. Hardness already holds for deterministic policies and acyclic (s, a)-rectangular RMDPs with two-successor uncertain choices. Lemma 25 (Membership). Portfolio comparison is in ∀R. Proof. Apply Lemma 13 with τ fixed to π0 and the explicit family Π. Problem 7 (Strict elementary feasibility). Given rational expressions g1 , . . . , gr over variables x ∈ [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) > 0 has a solution x ∈ [0, 1]n . Lemma 26. Problem 7 is ∃R-complete. Proof. Membership is immediate. For hardness, use the bounded degree-four equality normal form underlying Definition 4. It is ∃R-complete to decide ∃y ∈ [−1, 1]n : f (y) = 0, and substituting yi = 2xi − 1 changes the domain to [0, 1]n . Apply Definition 4 without its optional output coordinate and append the affine residual fb/B, which sets the decoded polynomial to zero. Denote all residuals by h1 , . . . , ht . If they have no common zero on the compact box, then η = min max |hj (x)| > 0. x j P 2 Clear denominators and put F = j hj . 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 Schaefer and Stefankovic (2024, cN 2

Theorem 2.2) on the compact box to F and the constant polynomial one. It gives a lower bound 2−ℓD in terms of the number N of variables, degree D ≤ 4, and coefficient length ℓ. Consequently an explicit polynomial p in the input length satisfies p η > 2−2 . Introduce positive variables a0 , b0 , . . . , ap , bp with 0 < a0 <

1 , 2

0 < b0 <

1 , 2

aj bj aj bj , 0 < bj+1 < 4 4 p The exponent recurrence gives ap < 2−2 . Replace hj = 0 by 0 < aj+1 <

ap + hj > 0,

(j < p).

ap − hj > 0.

An exact normal-form solution satisfies the strict system. Conversely, a strict solution would have |hj | < ap < η 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 ∀R-hard already for deterministic policies and acyclic (s, a)-rectangular RMDPs with two-successor uncertain choices. Definition 9 (Shared-selector evaluator). Fix a strict elementary feasibility instance g1 , . . . , gr over x ∈ [0, 1]n (Problem 7) and a discount γ. For each i, treat −gi 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, U, R, sι , γ), where • S = {s0 , ⊥} ∪ {qj , qj0 , qj1 : 1 ≤ j ≤ n} ∪ {τi,ℓ }: the initial state s0 ; a fresh absorbing zero-reward state ⊥; one selector qj and its two successors qj0 , qj1 per variable xj , shared by every branch that mentions xj ; and one terminal τi,ℓ per branch ℓ of −gi (its constant term counts as one branch); • A = {a0 , a1 , . . . , ar } ∪ {di,j,b }: at s0 , action a0 leads deterministically to ⊥, and action ai enters a rational certain splitter with one branch per term of −gi ; at qjb , the decoder action di,j,b is enabled for every policy i whose current branch visits xj ; it leads to ⊥ when b = 0, and otherwise to the next selector or to the branch’s terminal if xj was its last variable; • U is (s, a)-rectangular: the certain splitter at ai and every decoder are deterministic; the one uncertain choice at qj has distribution (1 − xj )δqj0 + xj δqj1 , the same distribution regardless of which branch or which gi is passing through; • branch ℓ, selected with splitter probability w > 0 and reaching its terminal τi,ℓ after d transitions, has terminal payoff w−1 γ −d times its coefficient (including its sign); every other described choice pays reward 0, and no common branch depth is needed because each payoff cancels its own depth; • all remaining choices use ruinous-sink completion;

τ1,0

R(τ

2

1,0 )

R

τ2,0

τ1,1

d1,1,1

a1 , 1

s0

(τ2,0)

a1 , 21 a2 ,

q11

x1

x2

1−

1 a2, 2

1− x1

d2,2,1

τ2,1

q2

d2,1,1

q1

1 2

q21

q10

x2

q20

a0

⊥

0,

, d 1,1

,0

d 2,1

d2,2,0

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. • sι = s0 . Lemma 28 (Evaluator policies). In the shared-selector evaluator of Definition 9, the following are well-defined deterministic (stationary) policies. • π0 chooses a0 at s0 and a fixed ruinous-completed default choice at every other nonterminal state, which is unreachable under π0 . • For each i ∈ {1, . . . , r}, πi chooses ai at s0 ; and for every variable xj occurring in gi and every outcome b ∈ {0, 1}, πi chooses di,j,b at qjb . This assignment is well-defined because a stationary policy fixes a single action per state and no variable occurs twice in one expression gi . 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. Example 2 (A worked evaluator). Take n = 2, r = 2, γ = 21 , g1 (x) = x1 − 12 , and g2 (x) = x1 x2 − 14 , so that −g1 (x) = 12 − x1 and −g2 (x) = 41 − x1 x2 . Figure 6 shows the resulting RMDP. By Lemma 28, π0 (always a0 ), π1 (choosing a1 at s0 and d1,1,1 at q11 ), and π2 (choosing a2 at s0 , d2,1,1 at q11 , and d2,2,1 at q21 ) are all well-defined. Each constant branch reaches τi,0 in one step with probability 1/2. The monomial branch of π1 follows s0 → q1 → q11 → τ1,1 , with total branch probability x1 /2 and depth three. That of π2 follows s0 → q1 → q11 → q2 → q21 → τ2,1 , with probability x1 x2 /2 and depth five. The policies share the selector q1 and diverge only through their decoder actions at q11 . The monomial branches reach their terminals after depths three and five, while each constant branch has depth one. With w = 12 and γ = 21 , the rule 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.

The first policy consequently has value Vxπ1 (s0 ) = γ · 21 · 2 + γ 3 · 21 x1 (−16) = 12 − x1 , and similarly

Vxπ2 (s0 ) = γ · 12 · 1 + γ 5 · 21 x1 x2 (−64) = 14 − x1 x2 , as required by −g1 and −g2 . Since π0 always reaches ⊥, Vxπ0 (s0 ) = 0 for every x. Hence
∆U (π0 , {π1 , π2 }) = sup min g1 (x), g2 (x) , x∈[0,1]2

which is maximized at x = (1, 1), giving min( 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 . Its policies π0 , π1 , . . . , πr are well-defined by Lemma 28. Every uncertain choice is at a selector qj and has two successors, and the selectors’ choices are independent, so the construction is (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 reaches only ⊥, so Vxπ0 (sι ) = 0. Policy πi realizes exactly the discounted sum of −gi ’s terms, so Vxπi (sι ) = −gi (x). Hence, with Π = {π1 , . . . , πr }, 
 ∆U (π0 , Π) = sup 0 − max −gi (x) = sup min gi (x). i

x∈[0,1]n

x∈[0,1]n

i

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 ∃R-complete problem, proving hardness. Proof of Theorem 24. Immediate from Lemmas 25 and 27.

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. Theorem 1 (Membership). Regret certification is in ∀R. 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(Π) ≤ t. The given-policy problem is the case r = 1. Theorem 5 (Membership). Minimal robust regret and bounded portfolio synthesis belong to ∃∀R. 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 = 1. The resulting formula asserts that some portfolio of at most k members has regret at most t, whereas ρ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 Rreg(Π) |Π|≤r

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ι ) is the maximum of finitely many such solutions, one per memoryless deterministic policy, hence also jointly continuous. Therefore f (π, u) = Vu∗ (sι ) − max Vuπi (sι ) i

is jointly continuous, π 7→ maxu∈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 Problem 4 and to the synthesis RMDP of Appendix J alike.

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 Aallow . For a finite portfolio, take the union of its supports. Definition 10 (Lifted RMDP). Fix an (s, a)-rectangular source RMDP M = (S, A, U, R, sι , γ0 ), a deterministic reference policy π0 , and a nonempty allowed-action family Aallow (s) ⊆ A at each s ∈ S, not necessarily containing π0 (s). Let F ⊆ S be its absorbing final states, and let cf be the payoff of f ∈ F . Fix Vmax =

maxs,a∈Aallow (s)∪{π0 (s)} |R(s, a)| , 1 − γ0

K = 2Vmax + 1,

Λ=

K . 1 − γ0

c = Choose a rational Z of polynomial encoding length such that βZ > Λ + Vmax . The lifted RMDP is the tuple M b b b b (S, A, U, R, sbι , β), where • Sb = {xs : s ∈ S} ∪ {ys,a : s ∈ S \ F, a ∈ Aallow (s) ∪ {π0 (s)}} ∪ {⊥r }. There is one tag state xs per source state, one selector state ys,a for every allowed or reference action at a nonfinal source state, and one ruinous sink.

us, bon

ys0 ,a 1

xs0

a, 0 s0

K

p

s1

1−γ0 2

xs1 b, 1−γ

stop, 1 − γ0

2

b, 1−p

stop, (1 − β)

1−p

bonus, (1 − β)(1 + Λ)

p

0

ys0 ,b

(a) Source.

(b) Lift.

Figure 7: The source and its lifted RMDP in Example 3. b = A ∪ {bonus, route} adds two fresh action symbols to the source action set. • A b • U is (s, a)-rectangular. At a nonfinal tag state, an allowed action a sends xs to ys,a and the bonus action sends it to ys,π0 (s) . The route action at ys,a carries exactly the original uncertainty set U(s,a) , redirected from successors s′ to tag states xs′ . At a final tag xf , every allowed action self-loops, as does the bonus action. b s , a) = R(s, a) for a ∈ Aallow (s) and R(x b s , bonus) = R(s, π0 (s)) + K. Every route action has • At a nonfinal tag, R(x reward zero. At a final tag xf , every allowed action has reward (1 − β)cf , while the bonus action has reward (1 − β)(cf + Λ). • Every action at ⊥r has reward −(1 − β)Z and self-loops. Every action at xf not already described also self-loops with reward −(1 − β)Z. All remaining choices use ruinous-sink completion with this Z. • sbι = xsι . Write π b0 for the policy always choosing the bonus action. The lift π b of any memoryless randomized policy π supported on Aallow uses the same action distribution as π at each tag state and the route action at every selector state. For a finite portfolio b = {b Π = {π1 , . . . , πr }, write Π π1 , . . . , π br }. Example 3 (A worked lift). Take a source RMDP with states S = {s0 , s1 }, sι = s0 , actions A = {a, b, stop}, and discount γ0 . At s0 , action a moves deterministically to s1 with reward R(s0 , a) = 0. Action b is uncertain, moving to s1 with probability 0 p and back to s0 with probability 1 − p for any p ∈ [0, 1], with reward R(s0 , b) = 1−γ regardless of outcome. At s1 , the 2 only action stop self-loops deterministically with reward R(s1 , stop) = 1 − γ0 , so V (s1 ) = 1 (Figure 7a). Fix reference π0 (s0 ) = a, π0 (s1 ) = stop and a single candidate π1 (s0 ) = b, π1 (s1 ) = stop, so Π = {π1 } and Aallow (s0 ) = {b}, Aallow (s1 ) = {stop}. Note Aallow (s0 ) does not contain π0 (s0 ) = a, while Aallow (s1 ) happens to coincide with π0 (s1 ). The Bellman equations give 1−γ0 + γ0 p 2 , Vuπ0 (s0 ) = γ0 , Vuπ1 (s0 ) = (1 − γ0 ) + γ0 p and the second value is increasing in p. Hence 161 . ∆U (π0 , {π1 }) = γ0 − 21 = 400

Definition 10 gives tag states xs0 , xs1 , selectors ys0 ,a , ys0 ,b , a ruinous sink, and β = 19/20 (Figure 7b). Because s1 is an absorbing final of payoff one, the allowed and bonus actions at xs1 self-loop with rewards 1 − β and (1 − β)(1 + Λ). The 0 selector ys0 ,b inherits the source interval for p. The relevant rewards are R(s0 , a) = 0, R(s0 , b) = 1−γ 2 , R(s1 , stop) = 1 − γ0 , so Definition 10 gives Vmax =

1 − γ0 = 1, 1 − γ0

K = 2Vmax + 1 = 3,

Λ=

K 400 = , 1 − γ0 13

161 and Rreg({b π1 }) = Λ + ∆U (π0 , {π1 }) = 400 13 + 400 . The margin in K = 2Vmax + 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 and an allowed-action family Aallow . For every memoryless randomized policy π supported on this family and every realization u, its lift satisfies Vubπb (xs ) = Vuπ (s) (s ∈ S). This construction preserves (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 π b0 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 Aallow , b = Λ + ∆U (π0 , Π). Rreg(Π) 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 b of the target RMDP via the redirected transitions of Definition 10. Define W (s) := Λ + Vuπ0 (s) for every source state s, and read it as a candidate value for the tag state xs . For a nonfinal source state, β 2 = γ0 means that going from xs 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 xs , the backup is X R(s, π0 (s)) + K + γ0 u(s, π0 (s), s′ )W (s′ ). s′

Substituting π0 ’s own Bellman equation Vuπ0 (s) = R(s, π0 (s)) + γ0

′ π0 ′ s′ u(s, π0 (s), s )Vu (s ) for R(s, π0 (s)), this simplifies

P

to

Vuπ0 (s) + K + γ0 Λ, which equals W (s) = Λ + Vuπ0 (s) exactly, since K = Λ(1 − γ0 ) by definition of Λ. For any allowed action a ∈ Aallow (s), the same two-step backup is X X R(s, a) + γ0 u(s, a, s′ )W (s′ ) = R(s, a) + γ0 u(s, a, s′ )Vuπ0 (s′ ) − Vuπ0 (s) +Vuπ0 (s) + γ0 Λ. s′

s′

|

{z

at most 2Vmax in absolute value

}

The bracketed term is at most 2Vmax because the reward is at most (1 − γ0 )Vmax and both value terms are at most Vmax in absolute value. Combined with (1 − γ0 )Λ = K = 2Vmax + 1, the whole backup is at most W (s) − 1 < W (s). At an absorbing final f of payoff cf , the bonus backup is (1 − β)(cf + Λ) + βW (f ) = W (f ), while every allowed-action backup is (1 − β)cf + βW (f ) = cf + βΛ = W (f ) − (1 − β)Λ < W (f ). Every other action at xf has value below W (f ) because its self-loop payoff is −Z, and every undescribed choice at a nonfinal state has backup −β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, Vubπb0 (xs ) = Λ + Vuπ0 (s) for every source state s. For any policy π supported on Aallow , its lift π b 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 therefore gives Vubπb (xs ) = Vuπ (s) for every s. No optimality claim is needed here, only that π b’s value matches π’s under the same discount-matching substitution used above. Combining the two identities at sι ,   b = sup V ∗ (sbι ) − max V πbi (sbι ) Rreg(Π) u b b 1≤i≤r u u b   = sup Λ + Vuπ0 (sι ) − max Vuπi (sι ) u

1≤i≤r

= Λ + ∆U (π0 , Π), using pointwise optimality of the bonus policy, so Vub∗ (sbι ) = Vubπb0 (sbι ). 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)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πb 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.

E E.1

Proofs of Theorems 2 to 4: Transferring Comparison Bounds to Certification

Rectangular Given-Policy Hardness

The exact lift transfers the Boolean and square-root-sum comparison bounds. Theorem 2. Given-policy robust regret is coNP-hard and coSQRS-hard under (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. For the coNP lower bound, start with Cmp(φ) and apply Lift(Cmp(φ), πC ) with singleton portfolio {πK }. The source consists of deterministic policies πC , πK in an acyclic (s, a)-rectangular RMDP with independent two-Dirac uncertain choices, one certain uniform splitter, and discount γ0 , and it satisfies φ ∈ UNSAT

⇐⇒

∆U (πC , πK ) ≤ 2 −

1 . 2n

For the lifted candidate π bK the lemma gives Rreg(b πK ) = Λ + ∆U (πC , πK ). 1 Thus, with the rational target threshold b t = Λ + 2 − 2n , 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 and threshold t produced by Theorem 18. That construction uses the same discount γ0 , is (s, a)-rectangular, and has two-Dirac uncertain choices. Apply Lift(N, πu ) with singleton candidate {πv }. Then ∆U (πu , πv ) ≤ t ⇐⇒ Rreg(b π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. Theorem 3. Portfolio-regret certification is ∀R-hard, already for deterministic portfolios and acyclic (s, a)-rectangular RMDPs with two-successor uncertain choices. Proof. The evaluator above was instantiated at γ0 , so apply Lemma 30 to its reference policy and explicit portfolio. The exact identity b = Λ + ∆U (π0 , Π) Rreg(Π) translates the zero comparison threshold to the rational regret threshold Λ. The structural conclusions are those of Lemma 30. Therefore portfolio-regret certification is ∀R-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. Theorem 4. Given-policy robust regret is ∀R-complete under general rational polytopic uncertainty, even for deterministic policies. The membership half of Theorem 4 is the singleton-family case of Lemma 13. Polynomial-evaluation hardness. Definition 11 (Positive-part gadget). Given Mf from Definition 8, add a fresh initial state s+ with two reward-zero actions: af enters Mf at sf , and a⊥ enters a zero-reward sink. Let π⊥ choose a⊥ at s+ . All choices left undescribed after enlarging the global action set use the same ruinous-sink completion as Mf . Lemma 31 (Positive-part regret). The fixed policy in Definition 11 satisfies Rreg(π⊥ ) =

sup max{γ0 f (p), 0}. p∈[0,1]m

Consequently Rreg(π⊥ ) ≤ 0 exactly when ∀p ∈ [0, 1]m : f (p) ≤ 0. Proof. At realization p, the two initial actions have values γ0 f (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 − p2 , the unique compliant policy inside Mf has value p − p2 and Rreg(π⊥ ) = γ0 max (p − p2 ) = γ0 /4 > 0. p∈[0,1]

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.

F

Proof of Theorem 6: Combinatorial Minimal-Regret Hardness

We prove the Boolean lower bounds for minimal robust regret. Theorem 6. Minimal robust regret is NP-hard and coNP-hard on (s, a)-rectangular RMDPs in which every uncertain choice is two-Dirac and the only other stochastic rows are certain uniform splitters. 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. 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 P ∈ {ΠMR , ΠMD }, write Pallow for the policies in P supported on the allowed actions. Definition 12 (ε-restricted RMDP). Let N = (S, A, U, R, sι , γ) be an RMDP and let Aallow (s) ⊆ A be a nonempty set of allowed actions for every s ∈ S. Suppose every disallowed choice has a fixed transition distribution, i.e., U(s,a) = {ps,a } for every s ∈ S and a ∈ A \ Aallow (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 , every action of which has reward zero and row {δ⊥0 }, and let every action be allowed there. At every absorbing final f of N , replace the reward R(f, a) by R(f, a)/(1 − γ) and the row by {δ⊥0 }, keeping Aallow (f ) as it is. An action a at f had value 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 as the only absorbing final. It raises the largest reward magnitude to at most the largest value magnitude of N , hence multiplies Vmax below by at most 1/(1 − γ) and keeps every constant of polynomial encoding length. Write N for the unfolded RMDP from here on. Second, let ε > 0 be rational, and set   2 maxs,a |R(s, a)| /ε (2 − γ)Vmax + 4Vmax Vmax = max 1, , Zε = . 1−γ γ The ε-restricted RMDP is the tuple Nε = (Sε , Aε , Uε , Rε , sιε , γε ), where: • Sε = S ∪ {⊥r }, adding one fresh ruinous sink ⊥r ; • Aε = A, γε = γ, and sιε = sι ; • Rε (s, a) = R(s, a) for every s ∈ S and a ∈ A, while every action at ⊥r has reward −(1 − γ)Zε ; • Uε (s, a) = U(s,  a) for every allowed choice, a ∈ Aallow (s); • Uε (s, a) = θ ps,a + (1 − θ)δ⊥r : θ ∈ [0, 1] for every disallowed choice, a ∈ A \ Aallow (s); • every action at ⊥r has row {δ⊥r }. The self-loop reward at ⊥r gives it value −Zε under every realization: V (⊥r ) = −(1−γ)Zε +γV (⊥r ) forces V (⊥r ) = −Zε . At the endpoint θ = 1, Uε (s, a) reduces to {ps,a }, exactly N ’s original choice. At θ = 0, it collapses to {δ⊥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 , 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 P = ΠMR or P = ΠMD , inf RregNε (ρ) ≤

ρ∈P

inf RregNε (ρ) ≥

ρ∈P

inf

RregN (π),

inf

RregN (π) − ε.

π∈Pallow π∈Pallow

g

ed) a (allow

s

⊥0

0

θ b (d

a (allowed) g

s

0

isal

0

low ed)

1−

b (disallowed) (a) Before.

θ

⊥r

−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. 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) = {a}. In Restrict(N, Aallow , ε), the unfolding first sends g to the fresh zero sink ⊥0 in one step, leaving its value at zero. Action a is then unchanged, while b reaches g with probability θ and ⊥r with probability 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. Proof of Lemma 32. The unfolding step changes no state’s value under any stationary policy or realization, so it changes neither ∗ RregN nor the set of allowed policies, and N below denotes the unfolded RMDP. Fix a source realization u and let W = Vu,θ≡1 in Nε . At the all-normal realization, the original states reproduce Nu , V (⊥r ) = −Zε , and no sink-routed action improves on an original action. Thus W (s) = Vu∗ (s) for s ∈ S and W (⊥r ) = −Zε . For a disallowed choice and arbitrary θ ∈ [0, 1], its backup at W is ! X X ps,a (s′ )W (s′ ), ps,a (s′ )W (s′ ) + (1 − θ)(−Zε ) ≤ R(s, a) + γ R(s, a) + γ θ s′

s′

because −Zε ≤ −Vmax ≤ mins∈S W (s). Allowed backups are unchanged, so the optimal Bellman operator satisfies Tu,θ W ≤ ∗ W . Monotonicity and contraction give Vu,θ ≤ W . An allowed policy never uses a modified choice, hence its value is independent of θ and agrees with its value in Nu . Its regret is therefore maximized at θ ≡ 1, and every allowed policy has the same robust regret in N and 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) is nonempty at every state. It preserves membership in ΠMR , and it preserves determinism when P = Π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 = E[γ τ 1{τ <∞} ]. At the joint realization (u, θ ≡ 1), every action value, including its immediate reward and discounted continuation, lies in [−Vmax , Vmax ]. Conditional on the first differing choice, ρ therefore gains at most 2Vmax over ρ̄, so ρ Vu,θ≡1 (sι ) ≤ Vuρ̄ (sι ) + 2Vmax d,

RregNε (ρ) ≥ Vu∗ (sι ) − Vuρ̄ (sι ) − 2Vmax d.

At the joint realization extending the same u with θ = 0 at every nonallowed choice, the first such choice incurs loss at least γZε − (2 − γ)Vmax = and therefore

2 4Vmax , ε

2 4Vmax d. ε Both endpoints are valid joint realizations extending this same u, because the modified choices are independent. If 2Vmax d ≤ ε, the first bound loses at most ε. Otherwise the second exceeds 2Vmax and hence dominates every possible regret in N . Either way RregNε (ρ) ≥ Vu∗ (sι ) − Vuρ̄ (sι ) − ε.

RregNε (ρ) ≥

The left side does not depend on u, so taking the supremum over u ∈ U gives RregNε (ρ) ≥ RregN (ρ̄) − ε ≥

inf

π∈Pallow

RregN (π) − ε.

Taking the infimum over ρ proves the lower inequality. For B-bit rational inputs Vmax and ε, the formula above gives Zε polynomial bit length in B and the model size. Each modified choice is independent, so rectangularity is preserved, and a Dirac ps,a yields a two-Dirac segment. Acyclicity is preserved as well: after the unfolding, ⊥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 and a consistency policy πK such that 1 if φ ∈ UNSAT, ∆U (πC , πK ) = 2 if φ ∈ SAT. n Take π0 = πC as the lift’s reference policy. No optimality property of πC is needed, only that it is the fixed policy the lift compares against. Restrict the candidates admitted by the lift to πK alone: at every tag state xs , set Aallow (xs ) = {πK (s)}, while every selector state has only its allowed route action. Recall from Definition 10 that a tag state’s available actions are Aallow (s) ∪ {bonus}, never the reference’s own action directly. The action πC (s) is reachable only through bonus and ys,πC (s) . Thus policy restriction keeps a candidate from taking the bonus route meant only for the reference. Because Aallow is a singleton at every tag state and selector states offer no choice at all, ΠMR allow contains exactly one policy, the lift π bK of πK . So there is no actual minimization left to do: writing N for this lifted RMDP, ∆U (πC , πK ) ≤ 2 −

inf

π∈ΠMR allow

Lemma 30

RregN (π) = RregN (b πK )

=

Λ + ∆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
1 Nε = Restrict Lift(Cmp(φ), πC ), Aallow , 4n . From here on write Rreg(π) for RregNε (π), matching Theorem 6’s notation. Lemma 32 with P = ΠMR then converts the two cases above into 1 φ ∈ UNSAT =⇒ inf Rreg(π) ≤ inf RregN (π) ≤ Λ + 2 − , MR π n π∈Πallow φ ∈ SAT =⇒ inf Rreg(π) ≥ π

inf

π∈ΠMR allow

RregN (π) −

1 1 =Λ+2− , 4n 4n

1 using the lemma’s upper inequality (no slack) in the first line and its lower inequality (losing ε = 4n ) in the second. Since

Λ+2−

1 1 1 <Λ+2− <Λ+2− , n 2n 4n

1 the threshold Λ + 2 − 2n 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. Vm Definition 13 (Falsification and valuation verifier RMDP). For a 3-CNF formula φ = i=1 Ci over variables x1 , . . . , xn , the verifier RMDP is Nφ = (Sφ , Aφ , Uφ , Rφ , sι , γ0 ), with the following components. • Sφ = {sι } ∪ Sscan ∪ Saud ∪ Ssel ∪ {⊥r }, consisting of four verifier groups and a ruinous sink: – Sscan , visited only by the falsification (scanner) policy: SF = {fi,j : i ∈ [m], j ∈ {1, 2, 3}}, for clause Ci and literal j, together with accF , rejF , and scanner-side padding states, fixed once the transitions below are defined. |O |

x – Saud , visited only by the valuation (audit) policy: {vx : x occurs in φ} and, for every x, Sx,T = {sx,T,ℓ }ℓ=1 , Sx,F = |Ox | {sx,F,ℓ }ℓ=1 , where x is assigned b and occurrence ℓ of Ox is audited (occurrences of x, fixed order), together with accK , rejK , and audit-side padding states.

0 1 – Ssel = {qo,t , qo,t , qo,t : o an occurrence, t ∈ {T, F }}, the local-bit selectors of Definition 3, with T, F in place of 1, 0. These are the only states either policy’s transitions can lead into from the other’s territory. Let val(o) = T for a positive occurrence and val(o) = F for a negative occurrence, and write ¬ val(o) for the other Boolean value. init • sι has actions ainit F , leading into Sscan at f1,1 , and aK , leading into Saud at vx1 . 0 1 Within Sscan : every qo,t ∈ Ssel has a single action, whose outcome qo,t or qo,t is governed by Uφ below. Each selector outcome offers a scanner action aF and an audit action aK with the role-specific continuations described next. For o = (i, j), action aF at fi,j uses the pair test of Definition 3, and its locally false outcome advances to fi,j+1 or accF when j = 3. All other outcomes abandon the current clause, continuing to fi+1,1 , or to rejF if i = m. Within Saud : every vx offers actions T, F leading to sx,T,1 , sx,F,1 . The controls sx,b,ℓ implement the audit chain of Definition 3; after its last occurrence, the chain continues to the next variable or to accK . 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, F in place of 1, 0. All remaining described choices are singletons. • accF is the terminal with payoff γ0−H and accK the terminal with payoff −γ0−H , while every other described reward, including at rejF and rejK , is zero. • All remaining choices use ruinous-sink completion. • The initial state is sι and the discount is the appendix-wide γ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 }. Figure 9 and example 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ι ) = ainit F , b b πF (qo,t ) = aF (qo,t ), init Kσ (sι ) = aK ,

Kσ (s) = ax,b (s)

πF (s) = aF (s)

(s ∈ SF ),

Kσ (vx )(b) = σx (b), (s ∈ Sx,b ),

b b Kσ (qo,t ) = aK (qo,t ).

On decision states outside their reachable verifier graphs, fix default actions whose otherwise undescribed choices use ruinoussink completion. For a valuation α, the deterministic policy Kα is obtained from σx (T ) = α(x) and σ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, accF for πF or accK for Kα . Thus πF accepts exactly when some clause is locally false, while Kσ audits the value selected at each vx . The common depth and terminal payoffs satisfy Lemma 10, so the comparison value is the sum of the two acceptance probabilities. Example 6. For φ = (x1 ∨ ¬x2 ∨ x3 ) ∧ (¬x1 ∨ x2 ∨ x3 ), the valuation (x1 , x2 , x3 ) = (1, 1, 0) satisfies φ, so an accepting valuation audit precludes falsification. By contrast, (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 and 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α accepts at it. Then every variable set true by α has bo,T = 1 at each occurrence, and every variable set false has bo,F = 1. In every clause satisfied by α, a true positive literal therefore cannot have the false pair (0, 1), and a true negative literal cannot have (1, 0). Hence no clause satisfied by α is locally false in all three positions. This also covers malformed pairs (0, 0) and (1, 1). Since π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) for true variables and (0, 1) for false variables. At that realization Kα accepts all of its audits and every literal of the falsified clause is locally false, so πF accepts as well. Only existence is claimed here, since another realization may make some audit fail.

f1,1

Sscan

f1,2

ainit F Ssel

1 q(1,1),T

sι ainit K

Saud

0

q(1,1),F

1 q(1,2),F

x1 =F

vx1

accF γ0−H

f1,3

0

q(1,2),T

vx2

1 q(1,3),T

0

q(1,3),F

vx3

accK −γ0−H

Figure 9: The verifier RMDP of Definition 13 for φ = (x1 ∨ ¬x2 ∨ x3 ) ∧ (¬x1 ∨ x2 ∨ x3 ), showing the four state groups. For each literal of C1 , the scanner first reads the value that would make it true; only outcome 0 followed by outcome 1 at the opposite-value selector confirms that it is locally false. The displayed 0, 1 paths advance through the three literals and then accept; every other outcome abandons C1 . The auditor policy Kα walks vx1 , vx2 , vx3 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 = F read the same q(1,1),F , coupling their acceptances. The remaining occurrences, both clauses, and the depth-H padding follow the same pattern.

For a randomized valuation policy, put
Gφ (σ) = sup VuπF (sι ) − VuKσ (sι ) . u

At a vertex, acceptance by πF contributes one and acceptance by 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φ ≤ 1. If φ is unsatisfiable, every randomized valuation policy has Gφ ≥ 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σ follows that complete valuation with probability at least δ = 2−n . Use the canonical realization for α. The formula has a clause falsified by α, so πF accepts with probability one and Kσ with probability at least δ. Thus 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 as reference. At variable states allow {T, F }, at verifier states allow the unique action of Kσ , and at source states used only by πF allow their unique action. The lifted allowed policies are precisely the valuation policies and RregN (Kσ ) = Λ + Gφ (σ). Equivalently, the target is Restrict(Lift(Nφ , πF ), Aallow , 2−n /4), where Nφ is the verifier RMDP of Definition 13. The disallowed bonus choices are singletons, so Lemma 32 applies with P = ΠMR . The gap of Lemma 34 becomes φ ∈ SAT =⇒ inf Rreg(π) ≤ Λ + 1, π

3 φ ∈ UNSAT =⇒ inf Rreg(π) ≥ Λ + 1 + 2−n . π 4

Threshold Λ + 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.

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 Σp2 on acyclic (s, a)-rectangular polytopic RMDPs.

Proof. Fix an acyclic RMDP. For any uncertainty realization, ordinary finite discounted-MDP optimality gives ′

Vu∗ (s) = max Vuπ (s). π ′ ∈ΠMD

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(π) = sup max Vuπ (sι ) − Vuπ (sι ) ′ MD u π ∈Π
′ = max sup Vuπ (sι ) − Vuπ (sι ) . π ′ ∈ΠMD

u

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 Y ′ Rreg(π) ≤ t ⇐⇒ ∀π ′ ∈ ΠMD ∀v ∈ vert(Us,a ) : Vvπ (sι ) − Vvπ (sι ) ≤ t. s,a

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 Σp2 .

G.2

Σp2 -Hardness over Deterministic Policies

Reduce from the canonical Σp2 -complete problem (Papadimitriou 1994) of deciding whether ∃x ∈ {0, 1}n ∀y ∈ {0, 1}m :

ψ(x, y),

where ψ is a 3-DNF. Wr Definition 15 (Universal falsification reference). Write ψ = i=1 Di , where every Di 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 ≥ 1. For an occurrence o, let val(o) ∈ {T, F } be the value making its literal true. The universal falsification RMDP is Nψ = (Sψ , Aψ , Uψ , Rψ , sι , γ0 ), with the following components. • Sψ contains the initial state and one candidate branch-entry state per variable, Y {r1K , . . . , rnK } ∪ {r1Y , . . . , rm }.

It contains a global selector qYj with outcomes qYTj , qYFj for every universal variable, and the shared local-bit selector of Definition 3 for every occurrence o and c ∈ {T, F }. • The reference-side controls are the term-scan states fi,h . The candidate-side controls are the decision states vxi , the existential y x audit states ki,c,ℓ , and the universal audit states kj,c,ℓ . There are also accepting, rejecting, padding, and zero-reward terminal states, together with the ruinous sink supplied below. init • At sι , action ainit F leads deterministically to the scanner entry f1,1 , and action aK has the certain uniform distribution over the n + m branch-entry states. y • State rjY leads to qYj . Outcome qYc j leads to kj,c,1 , which implements the audit chain of Definition 3 for the occurrences of yj in term-major order. A universal branch therefore offers the candidate no choice, the committed value being nature’s. x • State riK leads to vxi . At vxi , actions T and F enter the corresponding chain ki,c,1 . That control implements the same audit chain for the occurrences of xi in term-major order. If xi has no occurrence, both actions at vxi accept immediately. • At occurrence o = (i, h), the term scanner uses the pair test of Definition 3; its locally false outcome advances to fi+1,1 , or accepts if i = r. Every other outcome advances to fi,h+1 , or rejects if h = 3. • Every selector has one described action. At a shared local outcome, one described action takes the scanner continuation init and another takes the audit continuation. Since the two audit families lie behind ainit K and the scanner behind aF , 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 qYj . The initial splitter of ainit K is certain and uniform, and all remaining described choices are singletons.

• Before ruinous-sink completion, Rψ is zero except at padded acceptance terminals. Every reference-side accepting terminal has payoff γ0−H , every candidate-side accepting terminal has payoff −γ0−H , and every rejecting terminal has payoff zero. • All remaining choices use ruinous-sink completion. • The initial state is sι and the discount is the appendix-wide γ0 . Definition 16 (Universal falsification policies). For the RMDP of Definition 15, the fixed deterministic reference πF takes ainit F and then uses the pair-test scanner action throughout. The synthesized deterministic policy Kα takes ainit K , chooses α(xi ) at every vxi , and follows the audit action for the committed value at every audit state, that value being α(xi ) on an existential branch and nature’s selection at qYj 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α and every scan to π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ι first, then the branch-entry states, the global selectors Y1 , . . . , Ym , the decision states vx1 , . . . , vxn , 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ψ (α) = sup VuπF (sι ) − VuKα (sι ) . u

1 Lemma 36 (DNF dichotomy). Let M = n + m. For every α, if ∀y : ψ(α, y) then Gψ (α) ≤ 2 − M , while if ∃y : ¬ψ(α, y) then Gψ (α) = 2.

Proof. At a Boolean vertex, let Aj be the event that the yj audit passes, let B be the event that the term scanner passes, and let Ci be the event that the xi audit against α(xi ) passes. The reference reaches its single scanner branch with probability one, 1 while the candidate’s splitter gives each of the n + m audit branches weight n+m , so the padding and terminal rewards give DπF ,Kα = 1{B} +

|{j : Aj }| + |{i : Ci }| . n+m

If ∃y : ¬ψ(α, y), the canonical local pairs for (α, y) and the global choices Yj = yj make every event hold. This gives value two, which is also the largest possible value. Now suppose ∀y : ψ(α, y). All events cannot hold at once. Indeed, if every audit passes, set yj = Yj . 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). At least one event fails, and its weight is at least   1 1 = . min 1, n+m M 1 Thus every vertex has value at most 2 − M . No run repeats an uncertain choice, so Lemma 17 extends the bound to the full product polytope.

Lemma 37. Minimal robust regret over ΠMD is Σp2 -hard on acyclic (s, a)-rectangular RMDPs in which every uncertain choice is two-Dirac and the only other stochastic rows are certain uniform splitters. 1 Proof. Set M = n + m. By Lemma 36, a yes-instance has some Kα with Gψ (α) ≤ 2 − M , while every Kα in a no-instance has Gψ (α) = 2. Apply the exact lift with reference πF . At existential variable states allow {T, F }. At every other state allow the unique action used by the synthesized verifier, and at internal states used only by πF take Aallow (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 through the bonus action rather than through Aallow . The allowed 1 deterministic policies therefore have minimal regret at most Λ + 2 − M in yes-instances and exactly Λ + 2 in no-instances. The composed target is   1 Restrict Lift(Nψ , πF ), Aallow , . 4M

Apply Lemma 32 with P = ΠMD . The disallowed bonus choices are singletons. In yes-instances the unrestricted minimum is 1 1 at most Λ + 2 − M , while in no-instances it is at least Λ + 2 − 4M . Since Λ+2−

1 1 1 <Λ+2− <Λ+2− , M 2M 4M

1 separates the cases. The structural restrictions follow from Lemmas 30 and 32, whose unfolding step is threshold Λ + 2 − 2M what keeps the composed target acyclic.

Theorem 38. Minimal robust regret over memoryless deterministic policies is Σp2 -complete on acyclic (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.

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 Xp X√ ai ≤ bj . j

i

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. Theorem 7. Minimal robust regret is SQRS± -hard under (s, a)-rectangular uncertainty.

H.1

One-State Balancing 1 − pL

L, RL pL s

⊥

0

pR R, RR

1 − pR

Figure 10: The one-state balancing gadget has independent choices pL , pR ∈ [0, h] and a zero-reward sink. Definition 17 (One-state balancing gadget). Fix q ∈ (0, 1) and γ ∈ (1 − q, 1), and put h = (1 − q)/γ. The one-state balancing RMDP shown in Figure 10 is G = (S, A, U, R, s, γ), with the following components. • S = {s, ⊥}, where ⊥ is a zero-reward sink. • The global action set is {L, R}. At ⊥, both actions have a zero-reward Dirac self-loop. • U is the product of the independent uncertainty sets U(s,L) = {pL δs + (1 − pL )δ⊥ : pL ∈ [0, h]},

U(s,R) = {pR δs + (1 − pR )δ⊥ : pR ∈ [0, h]}.

• R assigns rewards RL and RR 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 is exactly h < 1, so these are valid transition probabilities. Write dL = 1 − γpL and dR = 1 − γpR . Both range over [q, 1]. For the gadget of Definition 17, the two parametrizations below choose (RL , RR ) so that its minimal robust regret realizes the signed square-root forms m+ and m− summed by the SQRS± reduction. For A, B > 0, put D = A + B. The positive-reward parametrization is q(A + qB) q(B + qA) rL = , rR = , (RL , RR ) = (rL , rR ), 1 − q2 1 − q2 and define p D − D2 − 4(1 − q 2 )AB m+ (A, B) = . 2(1 − q 2 )

The negative-reward parametrization is ℓ=

B + qA , 1 − q2

A + qB , 1 − q2

r=

and define

(RL , RR ) = (−ℓ, −r),

p

q 2 D2 + 4(1 − q 2 )AB − qD . 2(1 − q 2 ) Lemma 39 (One-state balancing gadgets). The positive-reward parametrization has minimal robust regret m+ (A, B). If q 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], the probability of playing L at s. First, consider the positive-reward form. For fixed dL , dR ∈ [q, 1], VL =

rL , dL

rR , dR

VR =

A direct calculation gives VL − Vx =

Vx =

xrL + (1 − x)rR . xdL + (1 − x)dR

(1 − x)(rL dR − rR dL ) dL (xdL + (1 − x)dR )

and

x(rR dL − rL dR ) . dR (xdL + (1 − x)dR ) On the region VL ≥ VR , the first expression is decreasing in dL and increasing in dR , so its maximum is attained at dL = q, dR = 1. Since rL − rR = A, q this maximum is A(1 − x) . 1 − (1 − q)x Similarly, on the region VR ≥ VL , the second expression is maximized at dL = 1, dR = q. Since rR − rL = B, q VR − V x =

this maximum is

Bx . q + (1 − q)x

Thus



 A(1 − x) Bx , . 1 − (1 − q)x q + (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 Rreg(x) = max

(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 = −ℓ/dL and VR = −r/dR . The conditions A, B > 0 are equivalent to r − qℓ = A > 0, ℓ − qr = B > 0, and imply q < r/ℓ < 1/q. For VL − Vx , set z = dR /dL ∈ [q, 1/q]. On z ∈ [q, 1], minimizing the feasible dL gives (1−x)z(r−ℓz) q(x+(1−x)z) , 2 2 whose derivative has numerator x(r − 2ℓz) − (1 − x)ℓz ≤ 0 because z ≥ q, r/ℓ < 1/q, and q ≥ 1/2. On z ∈ [1, 1/q], the (1−x)(r−ℓz) is strictly decreasing. Thus the maximum occurs at z = q, namely dL = 1, dR = q, and corresponding expression q(x+(1−x)z) equals A(1 − x)/(q + (1 − q)x). By symmetry the other region contributes Bx/(1 − (1 − q)x). Hence   A(1 − x) Bx Rreg(x) = max , . q + (1 − q)x 1 − (1 − q)x Balancing the decreasing and increasing terms gives (1 − q 2 )y 2 + qDy − AB = 0. Its positive root is m− (A, B).

H.2

Rational Square-Root Gadgets

Lemma 40 (Local gadget for a negative square-root coefficient). For every integer b ≥ 2, one can compute in polynomial time rational numbers qb , Db , Ab , Bb such that, for any γ ∈ (1 − qb , 1), the positive-reward balancing gadget of Lemma 39, after a rational reward scaling, has minimal robust regret of √ Db − b. √ √ Proof. Choose a rational number η ∈ ( b − 1, b − 1). The interval has length greater than 1/2 for b ≥ 2, so scanning a constant-denominator dyadic grid finds such an η. Both endpoint tests use exact rational square comparisons. Thus η has O(log b) bits and is found in polynomial time. Define η + b−1 b − 1 − η2 Nb η , Nb = , Db = . 2η 2 qb √ The upper bound on η gives qb > 0, while η > b − 1 is equivalent to qb < 1. Direct expansion gives Nb2 − qb2 = b − 1. Hence Nb > qb , so Db > 1. Hence, qb2 Db2 + 1 − qb2 = b. Now set Db + 1 Db − 1 Ab = , Bb = . 2 2 Then Ab , Bb > 0, Ab + Bb = Db , and qb =

Db2 − 4(1 − qb2 )Ab Bb = Db2 − (1 − qb2 )(Db2 − 1) = qb2 Db2 + 1 − qb2 = b. By Lemma 39, the unscaled positive-reward gadget has minimal robust regret √ Db − b . 2(1 − qb2 ) √ Scaling all rewards by 2(1 − qb2 ) gives the value Db − b. Moreover Db2 = 1 + (b − 1)/qb2 > b, so this local regret is positive. All rational operations preserve polynomial bit length. Example 7 instantiates the construction at b = 2. Example 7 (The gadget for b = 2). Take η = 1/2. Then q2 = 3/4, N√2 = 5/4, and D2 = 5/3, with N22 − q22 = 1 = b − 1. After the prescribed reward scaling, the local minimal regret is 5/3 − 2. Lemma 41 (Local gadget for a positive square-root coefficient). For every integer b ≥ 2, one can compute in polynomial time a rational constant Cb and a negative-reward (s, a)-rectangular gadget such that, for any γ ∈ ( 51 , 1), its minimal robust regret is √ b − Cb . Proof. Choose a rational number m such that

2b < m2 < b. 3 p p √ √ The interval ( 2b/3, b) has width at least 2(1 − 2/3). Scanning dyadics of polynomial bit length with rational square comparisons therefore finds m in polynomial time. Define D=

b m+ m , 2

b

c= m

−m . 2

Then D, c ∈ Q, c > 0, and D2 − c2 = b. Moreover, c b − m2 1 = < . D b + m2 5 Set

4 5 D+E D−E , E = c, A = , B= . 5 3 2 2 E 9 Since D < 13 , we have A, B > 0. Also A + B = D, and because 1 − q 2 = 25 , we have q=

q 2 D2 + 4(1 − q 2 )AB = q 2 D2 + (1 − q 2 )(D2 − E 2 ) = D2 − (1 − q 2 )E 2 = D 2 − c2 = b.

√ 2 2 Finally, Dc < 15 implies D2 = b + c2 < 25b b. 24 , and therefore q D < b. Thus qD < Now use the negative-reward form of Lemma 39 with these q, A, B, D. Its unscaled minimal robust regret is √ b − qD . 2(1 − q 2 ) √ √ Scaling all rewards by 2(1 − q 2 ) gives minimal robust regret b − qD. Set Cb = qD. The strict inequality qD < b proved above makes this local regret positive, and all parameters have polynomial binary length.

sin

1/n

1/n

H1

1/n ···

H2

Hn

Figure 11: Additive splitter for minimal regret.

H.3

Additive Composition

Definition 18 (Additive splitter). Let H1 , . . . , Hn be disjoint (s, a)-rectangular gadgets with common discount γ, entry states si , local regrets RregHi , and mutually independent uncertainty sets. Add a zero-reward initial certain uniform splitter sin whose only action enters each si with probability 1/n, and scale every reward in every Hi by 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 ∈ΠMR RregHi (πi ), then the additive splitter of Definition 18 satisfies n X mi . inf RregH (π) = π∈ΠMR

i=1

Proof. For a global policy π, let πi be its restriction to Hi . For any competing policy π ∗ and any rectangular uncertainty realization u = (u1 , . . . , un ), the Bellman equation at the certain uniform splitter has value ∗

Vuπ (sin ) − Vuπ (sin ) = γ

n X 1n i=1

nγ

n    X π∗ π∗ Vuii (si ) − Vuπii (si ) . Vuii (si ) − Vuπii (si ) = i=1

The local uncertainty sets are independent and the competing policy can be chosen independently inside the disjoint gadgets. Hence n X RregH (π) = RregHi (πi ). i=1

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)-rectangularity.

H.4

Proof of Theorem 7

Proof of Theorem 7. Reduce from the non-strict ≤ direction of SQRS± . Given two lists a1 , . . . , am and b1 , . . . , bn , we construct in polynomial time an (s, a)-rectangular RMDP M and a rational threshold t such that inf

π∈ΠMR

if and only if

m X √ i=1

RregM (π) ≤ t

ai ≤

n X p j=1

bj .

The reversed non-strict comparison uses the same construction after swapping the two lists. Let I = {i | ai ≥ 2}, J = {j | bj ≥ 2}, and let r0 = |{i | ai = 1}| − |{j | bj = 1}| be the rational contribution of unit roots. If I ∪ J = ∅, we output a single-state zero-reward RMDP with threshold −r0 , which is a yes-instance exactly when r0 ≤ 0. In the following, assume that at least one non-unit root is present. Put N = |I| + |J| for the number of local gadgets. For every i ∈ I, apply Lemma 41. This gives a local gadget with minimal robust regret √ ai − Ci+ − for a rational constant Ci+ . For every j ∈ J, apply Lemma 40 to obtain rational parameters qj , Dj− , A− j , Bj . After the reward scaling from that lemma, gadget j has local minimal robust regret p Dj− − bj .

Choose one common discount factor    4 qmin = min ∪ {qj | j ∈ J} , 5

γ =1−

qmin . 2

Then γ ∈ ( 51 , 1), so the positive-coefficient gadgets are valid, and γ > 1 − qj for every j ∈ J, so the negative-coefficient gadgets are valid as well. Compose all local gadgets using Lemma 42. The resulting RMDP has X√ X p ( ai − Ci+ ) + inf Rreg(π) = (Dj− − bj ) π∈ΠMR

i∈I

=C+

j∈J

X√

ai −

C=

X

bj ,

j∈J

i∈I

where

Xp

Dj− −

X

Ci+ .

i∈I

j∈J

Set the threshold t = C − r0 . Then inf

π∈ΠMR

Rreg(π) ≤ t ⇐⇒

X√

ai −

i∈I

⇐⇒

m X √ i=1

ai ≤

Xp bj ≤ −r0 j∈J n X

p bj .

j=1

The uncertainty set is a product of choice uncertainty sets, so the reduction preserves (s, a)-rectangularity.

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. Theorem 8. Single-policy minimal robust regret is ∀R-hard for arbitrary rational polytopic uncertainty.

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) (Problem 5) and write
∆ = sup Vpπ1 (sι ) − Vpπ2 (sι ) , p

Vmax =

maxs,a |R(s, a)| . 1−γ

Choose L = 2γVmax + |γt| + 1, Z = L/γ + 2Vmax + 1. Every compliant value of the construction below is bounded in absolute value by MM c = L + γ(Z + Vmax ) + Z, since the copies contribute at most Vmax , the anchors ±Z, and the initial action at most L on top of those. Choose a rational Zr of polynomial encoding length such that γZr > MM c + 1, which is the hypothesis of Lemma 11.

λα α;

L

1−

λα

−Z

λβ

forced M, π2

sb β;

0

forced M, π1

1−

λβ

Z

Figure 12: The two-action anchoring RMDP. The two copies share the realization p, whereas λα and λβ are fresh coordinates. Definition 19 (Two-action anchoring RMDP). Given (M, π1 , π2 , t), the two-action anchoring RMDP is c = (S, b A, b U, b R, b sb, γ), M with the following components. • Sb contains a fresh initial state sb, two disjoint forced copies of M , absorbing states z− and z+ of values −Z and Z, and a ruinous sink ⊥r of value −Zr . • At each state in copy i, the action prescribed by πi is the described action. The initial state offers actions α and β. Every action at z− and z+ self-loops with the reward realizing its displayed payoff. • Ub ties corresponding transition coordinates of the forced copies to one realization p of U. It also contains mutually independent coordinates λα , λβ ∈ [0, 1] that are unconstrained by the equalities tying the copies. Action α enters the first copy with probability λα and z− otherwise. Action β enters the second copy with probability λβ and z+ otherwise. • Rewards inside the forced copies agree with M . Action α pays L, action β pays zero, and the self-loop rewards at z− and z+ are −(1 − γ)Z and (1 − γ)Z, respectively. Every action at ⊥r self-loops with reward −(1 − γ)Zr . All remaining choices use ruinous-sink completion with Zr . • The initial state is sb and the discount is γ. Figure 12 illustrates the construction. Lemma 43 (Anchored action values). At a realization (p, λα , λβ ) of Definition 19, the values of α and β at sb are

B = γ λβ Vpπ2 (sι ) + (1 − λβ )Z . A = L + γ λα Vpπ1 (sι ) − (1 − λα )Z , Proof. The choice of Zr 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ι ) and Vpπ2 (sι ). One-step conditioning on the two successors of each initial action gives the formulas. Set D = L + γ∆ and E = 2γZ − L. 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}. 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 − 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. The definition of Z and |Vpπi | ≤ Vmax make the first endpoint strictly largest after optimizing over p, so its supremum is D. For B − A the four values are respectively γ(Vpπ2 − Vpπ1 ) − L,

γZ − L − γVpπ1 ,

γ(Z + Vpπ2 ) − L,

2γZ − L.

The last is strictly largest and equals E > 0. Moreover, γ∆ ≥ −2γVmax , and hence D ≥ |γt| + 1 > 0. At any realization the loss of the x-mixture is (1 − x)(A − B) when A ≥ B and x(B − A) otherwise. Taking the supremum, using D, 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 = π̄(b s, α), and the two infima coincide. Balancing the two branches therefore gives minimum DE/(D + E). Let t′ =

T = L + γt,

ET . E+T

Since z 7→ Ez/(E + z) is strictly increasing for z > 0, inf Rreg(π) ≤ t′ ⇐⇒ ∆ ≤ t. π

Example 8 shows that the threshold remains rational for an irrational comparison gap.

√ Example 8 (Anchoring an irrational comparison gap). 1, γ = 1/2, Vmax = 2, and ∆ = 7 − 4 3. √ For the RMDP of Example Taking t = 0 gives L = 3, Z = 11, D = 13/2 − 2 3, E = 8, T = 3, and t′ = 24/11. Thus the anchoring constants and threshold remain rational even though the balanced regret DE/(D + E) depends on the irrational source gap. Proof of Theorem 8. The equivalence above is a reduction from Theorem 20’s ∀R-hard comparison problem.

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. Theorem 9. Bounded portfolio synthesis is ∃∀R-complete under general rational polytopic uncertainty, with k encoded in unary. Hardness holds already for regret threshold two, the fixed discount γ = 12 , RMDPs acyclic apart from absorbing final states, and uncertain choices with two successors.

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 ∃∀R-complete to decide ∃x ∈ [0, 1]n ∀y ∈ [0, 1]m :

F (x, y) ≥ 0

after the affine substitution that moves the source box from [−1, 1] to [0, 1]. Write F (x, y) =

N mon X ν=1

cν

dν Y

dν ≤ 4,

wν,j ,

j=1

where every wν,j is a variable of x ∪ y, and put ( B = max 1,

N mon X

) |cν | .

ν=1

Thus |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). Let η consist of y and every copy, product, and output coordinate, and list all residuals as h1 , . . . , hs . 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 hj and every σ ∈ {−1, 1}, put gj,σ (x, η) =

o + σ 9B hj , 10B

and enumerate the resulting r = 2s expressions as g1 , . . . , gr . Lemma 45 (Elementary-test shape). Each test of Definition 20 satisfies: 1. gi (x, η) ∈ [−1, 1] on Pthe box; 9 2. gi (x, η) = ci (η) + ℓ di,ℓ xℓ , where at most one di,ℓ is nonzero and that coefficient is ± 10 ; and

3. ci has degree at most two in η. Proof. The first claim follows from |o| ≤ B and |hj | ≤ 1. Only copy residuals contain an existential variable, each contains 9 . Every other residual and o are free of x. Copy and output exactly one with coefficient −1, so its two tests have coefficient ∓ 10 residuals are affine, product residuals are quadratic in η, and o is affine in ō. Lemma 46 (Policy-affine max form). ∃x ∀y : F (x, y) ≥ 0

⇐⇒

∃x ∀η : max gi (x, η) ≥ 0. i∈[r]

Proof. For the forward direction, fix a witness x and any η, retain its y-part, and let δ = maxj |hj |. Choose j with |hj | = δ and σ with σhj = δ. By Lemma 12, o ≥ F (x, y) − 9Bδ ≥ −9Bδ, and therefore gj,σ ≥ 0. This also covers δ = 0. Conversely, if x is not a witness, choose y with F (x, y) < 0. Give every copy and product variable its correct value and set F (x, y) + B ∈ [0, 1]. 2B Then o = F (x, y) and every residual vanishes, so every test equals F (x, y)/(10B) < 0. ō =

Example 9 makes all constants in the normalization explicit. Example 9 (A policy-affine normal form). Let n = m = 1 and F (x, y) = x − 12 y, whose sentence is true exactly for x ≥ 21 . Here Nmon = 2, c1 = 1, c2 = − 12 , and B = 32 . The copies are z1 , z2 , with p1 = z1 , p2 = z2 and no product residuals:   1 1 3 h1 = z1 − x, h2 = z2 − y, h3 = o − z 1 + z2 , o = 3ō − . 3 2 2 9 1 Thus s = 3, r = 6, 9B = 27 2 , and 10B = 15. Only g1,± mention x, with coefficients ∓ 10 . For x = 3 , the reverse construction 1 4 1 takes y = 1, z1 = 3 , z2 = 1, and ō = 9 . Every residual then vanishes and every test equals (x − 2 )/15 < 0.

J.3

Exact Evaluators

Both components use the terminal-payoff convention of Appendix A. Throughout this section, γ = 12 . For a sparse polynomial P , write Poly(P ) for the component of Definition 8 at this discount, with repeated logical coordinates tied later by Definition 24, and write eP 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) +

n X

xℓ Pℓ (u),

ℓ=1

with every Pℓ explicit, sparse, and of constant degree, the component Aff(G) has: • an entry eG ; coordinate states s1 , . . . , sn , each with actions on and off; a zero-payoff terminal zr; and copies of     n+1 n+1 Poly P0 and Poly P (ℓ ∈ [n]); ℓ γ γ2 • at eG , one action with the certain uniform splitter over the n + 1 successors eP0 , s1 , . . . , sn ; at sℓ , a reward-zero singleton transition from on to ePℓ and from off to zr; • the rewards and completion of its Poly copies; every other choice of this component uses ruinous-sink completion. Lemma 47 (Affine-policy evaluation). For every realization u and every compliant π ∈ ΠMR , Vuπ (eG ) = P0 (u) +

n X

xℓ Pℓ (u),

xℓ = π(sℓ , on).

ℓ=1

Proof. The constant branch contributes

At sℓ ,

1 n+1 γ P0 (u) = P0 (u). n+1 γ

n+1 n+1 Pℓ (u) + (1 − xℓ )γ · 0 = xℓ Pℓ (u), γ2 γ γ so branch ℓ contributes n+1 xℓ n+1 γ Pℓ (u) = xℓ Pℓ (u). Summing proves the identity. Vuπ (sℓ ) = xℓ γ

zr off

sι

ai , bh

eG

certain uniform

sℓ on

ePℓ

certain uniform

u1

cν,1 1

−

cν,2

u2

τν fixed payoff

1 − u2 u

1

fl

Figure 13: The synthesis RMDP and its evaluator components. The only policy choices are at sι and the coordinate states; every reward shown is a fixed rational. Lemma 48 (One predecessor per coordinate). In Aff(G) every coordinate state sℓ has exactly one predecessor, namely eG , and each of its two actions has one fixed continuation. Thus a stationary policy’s behavior at sℓ has a single interpretation, and no continuation depends on the context from which sℓ was reached. Proof. The certain uniform splitter at eG is the only transition into sℓ , while on and off always lead to ePℓ and zr, 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.

J.4

Roles, Cases, and Scores

Definition 22 (Portfolio case scores). Let r be the number of tests and also the portfolio budget. Put H = {ev} ∪ {(i, ℓ, →), (i, ℓ, ←) : 2 ≤ i ≤ r, ℓ ∈ [n]} ∪ {(i, t) : i ∈ [r], t ∈ [3r + 1]}. Nature’s coordinates are a case distribution λ ∈ D(H), the evaluation vector η, and one coordinate qh ∈ [0, 1] for every oriented equality case. Write ξh for the coordinates local to case h. For role i, define the pure-case score Ah,i (xi , ξh ) as follows. • In the evaluation case, Aev,i (xi , η) = gi (xi , η). • For h = (i, ℓ, →), Ah,1 = x1,ℓ − qh ,

Ah,i = qh − xi,ℓ ,

and Ah,j = −1 for j ∈ / {1, i}. • For h = (i, ℓ, ←), Ah,1 = qh − x1,ℓ ,

Ah,i = xi,ℓ − qh ,

and Ah,j = −1 for j ∈ / {1, i}. • For h = (i, t), set Ah,i = 0 and Ah,j = −1 for j ̸= i. Lemma 49 (Pure-score shape). Every pure-case score of Definition 22 lies in [−1, 1] and has the form X Ah,i (xi , ξh ) = ch,i (ξh ) + dh,i,ℓ xi,ℓ , ℓ

where ch,i has degree at most two in nature’s coordinates and every dh,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], with ch,· = ∓qh and dh,· = ±1. Forcing scores are constants. Define the mixed score of role i by Wi =

X

λh Ah,i (xi , ξh ) + 1 −

h∈H

X

λ2h .

h∈H

Lemma 50 (Mixed-score polynomial). The score Wi has the form X Wi = Pi,0 (λ, η, q) + xi,ℓ Pi,ℓ (λ), ℓ

(5)

where Pi,0 = 1 −

X

λ2h +

h

X

λh ch,i (ξh ),

Pi,ℓ =

h

X

λh dh,i,ℓ .

h

The first polynomial has degree at most three, the second has degree one, and both have polynomially many monomials. Consequently, Lemma 47 applies to Wi . Proof. Substitute Lemma 49 into (5) and collect coefficients. The largest degree is 1 + 2, from λh multiplying a quadratic ch,i . The number of monomials is bounded by the sum of the explicit monomial counts of the pure scores plus 1 + |H|. The cases are coordinates of nature inside these polynomials, not branches in the model. This lets one evaluator compute all of Wi 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, U , R, sι , 21 ) be defined as follows. • Its states are sι ; for every role i ∈ [r], a copy Ei of Aff(γ −1 Wi ) with coordinate states si,1 , . . . , si,n ; for every h ∈ H, a copy Uh of Poly(γ −1 (3λh − 1)); and a ruinous sink. • At sι , the role action ai has reward zero and its singleton row enters Ei . The auxiliary action bh has reward zero and its singleton row enters Uh . 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ι and γ = 21 . 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 , every coordinate of η, and every qh , designate one occurrence as its representative and impose a rational linear equality P setting every other occurrence’s success probability equal to that representative. On the λ representatives add λh ≥ 0 and 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] 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, the equality P h λh = 1, and nonnegativity with normalization on every row. Every coefficient is 0 or ±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 , Qπu (sι , ai ) = Wi (xi , λ, η, q),

xi,ℓ = π(si,ℓ , on).

Proof. The initial action makes one reward-zero transition into Ei , whose value is γ −1 Wi by Lemmas 47 and 50. Lemma 53 (Auxiliary-action values). For every realization and every compliant policy, Qu (sι , bh ) = 3λh − 1. ∗

At a pure case λ = δh∗ , this value is two for h = h and −1 otherwise. Proof. Apply Lemma 22 to γ −1 (3λh − 1) and include the initial discount. Lemma 54 (Optimal-value bound). For every realization, Vu∗ (sι ) ≤ 2, with equality whenever λ = δh is a pure case. Proof. The only policy choices at described states are at sι and at coordinate states. The action values are those of Lemmas 52 and 53. Since every pure score is at most one, X X X Wi ≤ λh + 1 − λ2h = 2 − λ2h ≤ 2, h

h

h

and 3λh − 1 ≤ 2. By Lemma 11, these upper bounds extend from compliant policies to all policies. A randomized action at sι gives a convex combination of these values, so it cannot exceed two. At λ = δh , action bh attains two.

Lemma 55 (Combining pure cases). For fixed coordinate vectors x1 , . . . , xr , the following are equivalent: 1. for every pure case h and every valuation of ξh , some role has Ah,i ≥ 0; 2. for every λ ∈ D(H) and every valuation of all coordinates, some role has Wi ≥ 0. Proof. The second claim implies the first by taking λ = δh , when Wi = Ah,i . For the converse, fix a realization and take h∗ ∈ arg maxh λh . Apply the pure-case hypothesis at h∗ with the realization’s own ξh∗ to obtain a role i with Ah∗ ,i ≥ 0. All other pure scores are at least −1, so X λh Ah,i ≥ −(1 − λh∗ ). h

Moreover,

X

λ2h ≤ λh∗

h

X

λh = λh∗ .

h

Substitution in (5) gives Wi ≥ −(1 − λh∗ ) + 1 − λh∗ = 0. Each oriented equality case needs its own coordinate qh : the role selected for h∗ depends on ξh∗ , which must remain free of every other case’s coordinates. Example 10 shows that the correction bound can be tight. P Example 10 (The mixing correction). If λ is uniform on two cases, then 1 − h λ2h = 21 . If a role has score zero at one of those cases and −1 at the other, its mixed score is 1 1 1 · 0 + · (−1) + = 0. 2 2 2 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 } defined by πi (sι ) = ai ,

πi (sj,ℓ , on) = xℓ

for every j, ℓ

and completed compliantly at every other state satisfies Rreg(Π) ≤ 2. Proof. Every πi is stationary and Vuπi (sι ) = Wi (x) by Lemma 52. We verify pure-case coverage. At ev, Lemma 46 gives maxi gi (x, η) ≥ 0 for every η. At an oriented equality case, the two nonconstant scores have maximum max{xℓ − qh , qh − xℓ } = |xℓ − qh | ≥ 0. At a forcing case (i, t), role i scores zero. By Lemma 55, every realization has some Wi ≥ 0. Combining this with Lemma 54 bounds regret by two. Lemma 29 is needed here because the reverse direction turns ρ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(Π) ≤ 2, then it has exactly r members, exactly one member chooses each ai with probability one, and no member chooses an auxiliary action at sι . Proof. At a pure case, Lemma 54 gives Vu∗ (sι ) = 2. Thus the regret bound implies max Vuπ (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 } and renormalizes at each coordinate state, which leaves π(si,ℓ , on) in [0, 1], so π̄ still encodes a witness and the count below is unaffected. Fix a role i and a forcing case h = (i, t). At λ = δh , action ai has value zero, every other role action has value −1, action bh has value two, every other auxiliary action has value −1, and every completed action has value at most −1. For a policy with initial distribution p, collect the mass outside {ai , bh } to obtain Vuπ (sι ) ≤ p(ai ) + 3p(bh ) − 1.

Suppose p(ai ) < 1 and put δπ = 1 − p(ai ) > 0. Covering h forces p(bh ) ≥ δπ /3. The actions b(i,t) are distinct and outside ai , so 3r+1 X p(b(i,t) ) ≤ δπ . t=1

This policy can therefore cover at most three of the 3r + 1 forcing cases for role i. If every portfolio member had p(ai ) < 1, the at most r members would cover at most 3r such cases, a contradiction. Thus some member has p(ai ) = 1. No policy can put probability one on both ai and aj for i ̸= j. The r roles therefore require r distinct members, exhausting the budget. Every member is pure on its role action at sι , leaving none on an auxiliary action. Lemma 58 (Equality cases). Under the hypotheses of Lemma 57, let xi be the vector encoded by the member assigned to role i. Then x1 = · · · = xr . Proof. Fix i ≥ 2 and ℓ. At pure case (i, ℓ, →), coverage for a given q ∈ [0, 1] is max{x1,ℓ − q, q − xi,ℓ , −1} ≥ 0, equivalently max{x1,ℓ − q, q − xi,ℓ } ≥ 0. If x1,ℓ < xi,ℓ , the legal midpoint q = 12 (x1,ℓ + xi,ℓ ) makes both terms negative. Conversely, if x1,ℓ ≥ xi,ℓ , every q satisfies q ≤ x1,ℓ or q ≥ xi,ℓ , so one term is nonnegative. Coverage for every q is therefore equivalent to x1,ℓ ≥ xi,ℓ . The reverse oriented case gives xi,ℓ ≥ x1,ℓ . Lemma 59 (Evaluation case). Under the same hypotheses, with x the common vector, max gi (x, η) ≥ 0 i

for every η.

Proof. At the pure case ev, role i has value Aev,i (xi , η) = gi (xi , η). Pure-case coverage gives maxi gi (xi , η) ≥ 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 whenever the source sentence holds. Conversely, if ρr ≤ 2, then Lemma 29 supplies a portfolio of at most r members with regret at most two. Lemmas 57 to 59, followed by Lemma 46, gives the source sentence. Thus ρ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 = 2 and n = 1. Then 3r + 1 = 7 and |H| = 1 + 2 + 14 = 17. At the pure 3 1 case (2, 1, →) with q = 25 , role one scores x1,1 − 52 and role two scores 25 − x2,1 . For x1,1 = 10 and x2,1 = 12 , both are − 10 . 1 1 1 No member is nonnegative, and the regret is 2 + 10 , exposing x1,1 < x2,1 . If both coordinates are 2 , role one scores 10 and covers the case. At forcing case (1, 3), a member with p(a1 ) = 1 scores zero. A member with p(a1 ) = p(b(1,3) ) = 12 scores 3·

1 1 + −1=1 2 2

and also covers that case, but its remaining mass 12 can place the required 61 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 = 2s are polynomial, and |H| = 1 + 2(r − 1)n + r(3r + 1). Every Wi has degree at most three and polynomially many monomials. Each Poly 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ν +1 , so every encoding length is polynomial.

Lemma 61 (Synthesis structure). The RMDP Msyn has fixed discount 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ι 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.

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) in which X is a finite set of parameters and every transition probability P (s, a, s′ ) is a polynomial in Q[X]. A valuation θ : X → R 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 ⊆ RX 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 instantiates a transition vector uθ , and UD = {uθ : θ ∈ D} is the induced uncertainty set. This set is not (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 pc 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 (Iyengar 2005), which requires a rectangular uncertainty set. We therefore relax each parameter region c ⊆ D to the interval MDP whose per-choice uncertainty sets are the coordinatewise ranges of the transition polynomials over c. Writing Uc□ for the resulting rectangular set, this relaxation only ever adds transition vectors, Uc = {uθ : θ ∈ c} ⊆ Uc□ , 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 10 equalwidth bins, so a two-parameter benchmark yields |C| = 102 = 100 cells. For every cell c ∈ C we instantiate the pMDP at the cell midpoint mid(c) and solve the resulting ordinary MDP by value iteration at tolerance 10−8 , which gives an optimal policy ∗ ∗ πmid(c) and its value Vmid(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′ , robust value iteration on the interval relaxation Uc□′ returns V πc′ = inf Vuπ (sι ), u∈Uc□′

and the score recorded in the loss matrix is the midpoint-anchored difference π ∗ Lπ,c′ = Vmid(c ′ ) (sι ) − V c′ .

(6)
Two approximations separate Lπ,c′ from the exact cellwise robust regret supθ∈c′ Vθ∗ (sι ) − Vθπ (sι ) . First, the optimal value is taken at the single point mid(c′ ) rather than at the maximizing θ, which may err in either direction. Second, by the inclusion above, the infimum over Uc□′ is at most the infimum over Uc′ , so this term alone makes 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π ∈ RC , 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 ⊆ Π(C) of K memoryless deterministic policies. Clustering is a cheap stand-in for the intractable synthesis problem of Problem 4: it never leaves the candidate set, and it optimizes profile similarity rather than portfolio regret. A single-policy reference point. worst cell,

The same loss matrix also yields an exact reference for K = 1. Minimizing each candidate’s min max Lπ,c ,

π∈Π(C) c∈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 (Volk et al. 2026) 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 b ⊂ D uniformly at random with |D| b = 1000, and at every θ ∈ D b we instantiate the pMDP and compute two seed we draw D exact quantities: the optimal value Vθ∗ (sι ) by value iteration, and the value Vθπ (sι ) of each portfolio member by fixed-policy evaluation. The reported estimate is   [ b (Π) = max Vθ∗ (sι ) − max Vθπ (sι ) . Rreg D

π∈Π

b θ∈D

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 [ b (Π) under-approximates Rreg(Π). The whole supremum in (1) is replaced by a maximum over finitely many samples, Rreg D construction-and-evaluation procedure is repeated for the three seeds 0, 1, 2, which reseed both the K-means initialization and b Table 5 reports the individual seeds and Table 2 their mean. the sample D;

K.4

RQ2: online portfolio selection

Setting. A fixed but hidden valuation θ defines a generative model Gθ from which trajectories of the instantiated MDP can be sampled starting at sι . The portfolio members are treated as the arms of a bandit: pulling arm π rolls out one trajectory of horizon H = 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 ] for BH = Rmax

1 − γH , 1−γ

with Rmax the benchmark’s largest reward magnitude. The selection rule. We use UCB (Cesa-Bianchi and Lugosi 2006) 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 (Mnih, Szepesvári, and Audibert 2008), 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 BH suggests, so it converges considerably faster than a Hoeffding radius. Writing isafe for the arm of greatest lower confidence bound, the run stops as soon as lcb(isafe ) ≥ max ucb(j) − εabs , j̸=isafe

that is, as soon as no other arm can be more than εabs better. Otherwise every arm whose upper bound has fallen below lcb(isafe ) − ε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 and tolerance ε = 10−3 , the latter expressed as a fraction of the return bound, so the absolute tolerance is εabs = ε · BH = 10−3 BH . 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, arg maxπ∈Π Vθπ (sι ) computed exactly by fixed-policy evaluation, and not against the unrestricted optimum 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, Vθbest (ι) − Vθπ (ι) Lπθ = best , Vθ (ι) − Vθworst (ι) so that recommending the best member scores 0 and recommending the worst scores 1 (with Lπθ = 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 30 valuations uniformly from D and run the selection rule once per valuation, all from one seeded random stream. Pooling the three seeds gives the 90 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) ∈ S records a discretized temperature level T ∈ {0, . . . , 10}, a humidity level H ∈ {0, . . . , 5}, and a queue length L ∈ {0, . . . , 4}, so |S| = 11 · 6 · 5 = 330. Episodes start at s0 = (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}.

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]. The cooling effectiveness pc is how reliably an action moves the room as intended, and the environmental pressure pe is how strongly workload and ambient conditions push back. A high pc makes the controller’s actions dependable; a high pe 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 pc and an environment outcome governed by pe :  pc pe 1−pe 1−pc pe 1−pe c Pθ (s′ | s, a) ∈ p2c , 1−p , = 1, 2 , 2 , 2 2 + 2 + 2 + 2 so the four branches sum to one at every θ and every transition probability is affine in θ. Writing [x]hi lo := min(hi, max(lo, x)) ± 5 ± for clamping a coordinate to its range, and abbreviating T ± := [T ±1]10 , H := [H±1] , L := [L±1]40 , Table 3 gives the 0 0 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 cool-high cool-low hold heat dehumidify

pc /2 −

(T , H, L) (T − , H, L) (T, H, L) (T + , H, L) (T, H − , L)

(1 − pc )/2 +

(T , H, L) (T, H, L) (T + , H, L) (T − , H, L) (T, H + , L)

(1 − pe )/2

pe /2 −

(T, H, L ) (T, H, L− ) (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 Pθ (· | s, a), for 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),

combining a per-action energy cost rE (cool-high) = −4,

rE (cool-low) = −2,

rE (hold) = −1,

with penalties that activate as each dimension approaches its ceiling:   T ≤7 0 0 rT (T ) = −20 T ∈ {8, 9} rH (H) = −15   −50 T = 10 −40

rE (heat) = −2,

H≤3 H=4 H=5

rE (dehumidify) = −3,

 rL (L) =

0 −10

L ̸= 4 L=4

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)| = 104, attained at T =10, H=5, L=4 under cool-high, and the discount is γ = 0.95, giving Vmax = Rmax /(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) ranges over {0, . . . , Lx −1}×{0, . . . , Ly −1}×{0, . . . , Lz −1}, where x is the direction of travel, y the lateral axis the wind blows across, and z the altitude with z = 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). Action space.

In every grid cell, the UAV chooses one of seven actions, A = {E, W, N, S, UP, DOWN, HOVER},

the six unit moves along ±x, ±y, ±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 ]. 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 < 1, so 1 − 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. form

Writing clip(·) for componentwise clamping into the grid bounds, every grid action has the same three-branch

Pθ (s′ | s, a) = (1 − p − q) 1[s′ = redirect(sint )] + p 1[s′ = redirect(swind )] + q 1[s′ = redirect(sdrop )], where sint = clip(s + move(a)) is the intended move, the only branch that depends on a; swind = clip(s + (0, 1, 0)) is the lateral drift; and sdrop = (x, y, z−1) if z > 0, else s itself, a ground-level skid. Coincident branches are summed, as in the datacenter benchmark. The map 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) otherwise. The layout is procedural in the grid extents. With yc = ⌊Ly /2⌋, wx = max(1, ⌊Lx /6⌋), xw = ⌊Lx /2⌋ − ⌊wx /2⌋, xp = ⌊3Lx /4⌋, and xc = Lx − max(2, ⌊Lx /8⌋), the obstacle set O = Oslab ∪ Opillar ∪ Ocanopy consists of a wall spanning x ∈ [xw , xw +wx ) at every altitude z ≤ Lz −2 except a two-level corridor on the centerline (y = yc , z ≤ 1); a two-wide pillar at x = xp , y ∈ {yc , yc +1}, z ≤ Lz −2; and a canopy at the top altitude z = Lz −1 restricted to x ≥ xc . The target region T = {(Lx −1, y, 0) : y ∈ {yc −1, yc , yc +1}} is a three-cell landing pad on the far wall. The generator checks that the start is not an obstacle and that T ∩ O = ∅. 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). Rewards and discount. The reward is deterministic and parameter-independent: r(s, a) = 1 for (Goal, collect) and 0 for every other reachable state-action pair, so Rmax = 1. The optimal discounted value at s0 is therefore exactly the discounted probability of eventually landing. The discount is γ = 0.99, kept close to 1 because routes take on the order of Lx steps and a smaller discount would wash out the reachability signal over that horizon; this gives Vmax = Rmax /(1 − γ) = 100.

Scalability. The grid extents (Lx , Ly , Lz ) are free parameters of the generator, subject to Lx ≥ 8, Lz ≥ 3, and odd Ly ≥ 5 so that the centerline yc is a single column. Every obstacle and goal formula above depends only on (Lx , Ly , Lz ), so the low-versus-high trade-off survives at every size, and |S| = 3 + {(x, y, z) ∈ grid : (x, y, z) ∈ / O ∪ T } = O(Lx Ly Lz ). The benchmark comes in three sizes, listed in Table 4, and all share (pmax , qmax , γ) = (0.25, 0.20, 0.99) and the layout above, differing only in (Lx , Ly , Lz ). Name

(Lx , Ly , Lz )

|S|

uav-small uav-medium uav-large

(8, 5, 3) (12, 9, 4) (24, 15, 6)

98 358 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|S|−3 memoryless deterministic policies. Even uav-small therefore rules out exhaustive search over policies.

L

Experimental data

Regret results (RQ1). Table 5 gives the seed-level results summarized in Table 2. For each portfolio size K and each [ b (ΠK ), the largest portfolio regret over that seed’s 1000 benchmark, it reports two quantities. The “max-regret” column is Rreg D sampled valuations; these are the numbers averaged into Table 2, and they should be read against the benchmark’s Vmax , 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 90 pooled runs whose recommended member is the best portfolio member at their hidden valuation; the right column is that recommendation’s normalized shortfall Lπθ , which is 0 when the best member is recommended and 1 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 Vmax = 100 max-regret inertia

|S| = 358 Vmax = 100 max-regret inertia

|S| = 1813 Vmax = 100 max-regret inertia

|S| = 330 Vmax = 2080 max-regret inertia

K

seed

1 1 1 1

0 1 2 avg

0.053 0.053 0.053 0.053

23.239 23.239 23.239 23.239

0.091 0.091 0.091 0.091

42.668 42.668 42.668 42.668

0.125 0.124 0.129 0.126

59.498 59.498 59.498 59.498

14.649 13.404 14.771 14.275

1313595.187 1313595.187 1313595.187 1313595.187

2 2 2 2

0 1 2 avg

0.032 0.032 0.032 0.032

1.935 1.935 1.935 1.935

0.019 0.019 0.020 0.019

3.974 3.974 3.974 3.974

0.016 0.016 0.018 0.017

1.629 1.629 1.629 1.629

4.127 3.413 4.053 3.864

215193.617 220731.474 215193.617 217039.569

3 3 3 3

0 1 2 avg

0.014 0.027 0.014 0.018

0.697 1.157 0.697 0.850

0.005 0.005 0.020 0.010

1.951 1.951 2.152 2.018

0.016 0.014 0.018 0.016

0.638 1.317 0.638 0.865

2.813 2.836 2.809 2.820

72737.797 72737.797 72737.797 72737.797

5 5 5 5

0 1 2 avg

0.002 0.002 0.002 0.002

0.094 0.093 0.093 0.093

0.003 0.003 0.003 0.003

0.193 0.183 0.183 0.186

0.016 0.014 0.015 0.015

0.107 0.107 0.107 0.107

2.809 2.836 2.730 2.792

37639.989 40156.574 39166.131 38987.564

7 7 7 7

0 1 2 avg

0.002 0.002 0.002 0.002

0.015 0.012 0.012 0.013

0.003 0.003 0.003 0.003

0.032 0.032 0.032 0.032

0.004 0.003 0.015 0.008

0.044 0.044 0.048 0.045

2.809 1.170 1.392 1.790

19076.922 20262.995 19462.184 19600.700

10 10 10 10

0 1 2 avg

0.002 0.002 0.002 0.002

0.002 0.002 0.002 0.002

0.003 0.003 0.003 0.003

0.007 0.007 0.009 0.008

0.004 0.003 0.002 0.003

0.010 0.011 0.010 0.011

0.817 0.824 0.759 0.800

8950.955 9239.430 8610.714 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.

80 60 40

K=2 K=3 K=5 K=7 K=10

20 0

100

% of correct samples

uav-small

100

102

104

Number of iterations

80 60 40

K=2 K=3 K=5 K=7 K=10

20 0

100

102

104

Number of iterations

106

K=2 K=3 K=5 K=7 K=10

0.6 0.5 0.4 0.3 0.2 0.1 0.0

106

Regret (best and worst policy)

% of correct samples

Datacenter

100

Normalised regret of recommended arm

Regret (best and worst policy)

Correct arm recommended

100

104 102 106 Number of iterations K=2 K=3 K=5 K=7 K=10

0.8 0.6 0.4 0.2 0.0

100

104 102 Number of iterations

106

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 recommended

60 40

K=2 K=3 K=5 K=7 K=10

20 100

% of correct samples

100

102

104

Number of iterations

K=2 K=3 K=5 K=7 K=10

0.5 0.4 0.3 0.2 0.1 0.0

106

100

104 102 Number of iterations

0.6

80 60 40

K=2 K=3 K=5 K=7 K=10

20 0

Regret (best and worst policy)

80

0

UAV-large

0.6

100

102

104

Number of iterations

106

Regret (best and worst policy)

% of correct samples

UAV-medium

100

Normalised regret of recommended arm

106 K=2 K=3 K=5 K=7 K=10

0.5 0.4 0.3 0.2 0.1 0.0

100

104 102 Number of iterations

106

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.

Algorithm 2: Paired portfolio synthesis and evaluation protocol Input: benchmark pMDP M , domain D, portfolio budgets K, seeds S, empirical robust regret sample size n, UCB sample size m, UCB parameters (H, ε, δ) foreach K ∈ K do // Offline candidate construction. Cells ← DiscretizeDomain(D); Candidates ← ComputeCandidatePolicies(M, Cells); // Offline robust candidate evaluation. 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); // Offline empirical robust regret evaluation of portfolio. b ← SampleDomain(D, n, s); D b do foreach θ ∈ D V ∗ ← OptimalValue(M, θ); VΠ ← maxπ∈Π EvaluatePolicy(M, θ, π); r ← V ∗ − VΠ ; Store(K, s, θ, r); Maximise empirical robust regret within one seed; // Online UCB-based deployment. b ← SampleDomain(D, m, s); D b do foreach θ ∈ D Create generative model Gθ ; z ← RunUCB(Gθ , Π, H, ε, δ); Store(K, s, θ, z); Average empirical robust regret over seeds; Pool UCB samples across seeds; GenerateReport();

Related documents

• Path-Space Robust Bayesian Portfolio Selection#1155242
• Kolmogorov Regression for Robust Diffusion Policies#282780
• SafePG: Safe and Globally Optimal Reinforcement Learning with Hard Constraints#1083552
• Optimal Posterior Sampling for Policy Identification in Tabular Markov Decision Processes#155281
• Learning-Augmented Robust Algorithmic Recourse#173226