Adaptive Policy Portfolios for Robust Markov Decision Processes

1 Introduction

• Adaptive policy portfolios use a finite set of memoryless policies, synthesized offline for uncertainty regions and selected online from accumulated evidence.The portfolio is optimized by robust regret, providing a finite form of adaptation without online policy synthesis.Source: §1 · pp. 1–2
• In the actuator example, worst-case regret falls from 1/4 for the single calibration c = 1/2 to 1/16 with {0, 1/2, 1} and 1/64 with five calibrations.Larger portfolios provide controlled adaptation while online selection remains finite; Figure 1 plots the regret curves.Source: §1 · p. 1, Figure 1 · p. 1
• The practical construction discretizes uncertainty into cells, computes and evaluates candidate policies across cells, clusters regret profiles to the target budget, and uses UCB online.This separates expensive computation offline from runtime selection among a fixed portfolio.Source: §1 · p. 2
• Given-portfolio certification is ∀R-complete, while unary-bounded portfolio synthesis is ∃∀R-complete for general rational polytopic uncertainty, even under acyclic dynamics.Certification is already hard for deterministic portfolios in acyclic (s, a)-rectangular RMDPs, whereas the synthesis reduction does not establish ∃∀R-completeness under rectangular uncertainty.Source: §1 · p. 2
• The hardness arises from shared uncertain transitions, recurrent cycles, and policy choices, yielding Boolean, square-root-sum, and signed-square-root-sum sources of complexity.These bounds rule out efficient general-purpose algorithms under standard complexity assumptions, while leaving room for practical offline methods.Source: §1 · pp. 1–2

Related Work

• Adaptive policy portfolios occupy an intermediate position between belief-based adaptive MDPs and fixed robust policies by shifting expensive computation offline and limiting online adaptation to policy selection.Regret is appropriate because the portfolio should contain a near-optimal policy for whichever environment is true; related regret work includes Ghavamzadeh, Petrik, and Chow (2016).Source: Related Work · p. 2

RMDP model

• An RMDP specifies finite states and actions, rewards, an initial state, discount factor, and a convex polytope U of valid transition vectors.Each realization u in U induces a classical MDP, while candidate policies are generally memoryless randomized policies.Source: §2 · pp. 2–3

Uncertainty structure

• General uncertainty may couple choices, whereas (s,a)-rectangular uncertainty decomposes into independent per-choice uncertainty sets.The framework also identifies acyclic, two-successor, and two-Dirac subclasses for structural restrictions.Source: §2 · p. 3

Robust value and regret

• Robust regret measures a policy’s largest shortfall from the policy optimal for each realization u, rather than its absolute worst-case value.This comparative criterion accounts for environments that are intrinsically difficult for every policy.Source: §2 · p. 3

Adaptive policy portfolios

• An adaptive policy portfolio is a finite offline-synthesized set of memoryless randomized policies paired with a runtime selector that chooses among members as evidence accumulates.Portfolio regret compares the best portfolio member separately for each realization, idealizing away member-identification cost; that online cost is evaluated separately in Section 4.Source: §2 · p. 3

Portfolio optimization

• The optimization objective is ρk = inf over portfolios Π with |Π|≤k of portfolio robust regret, with ρ1 equal to minimal single-policy regret.Portfolio regret is no larger than the regret of its best individual member, but generally cannot be reconstructed from singleton regret values.Source: §2 · p. 3

3.1 Complexity Preliminaries

• All studied problems lie in PSPACE, while the paper uses ∃R, ∀R, ∃∀R, and SQRS± subclasses situated between NP and PSPACE.Inputs use binary-encoded rationals, with the portfolio budget encoded in unary.Source: §3 · p. 3, §3.1 · pp. 3–4

3.2 Policy and Portfolio Comparison

• Portfolio comparison is ∀R-complete under (s,a)-rectangular uncertainty because the explicit pointwise maximum over portfolio members supplies the quantifier alternation.For two policies, comparison ranges from polynomial time without shared uncertainty to coNP-hard, coSQRS-hard, and ∀R-complete depending on cycles and rectangularity.Source: §3.2 · pp. 4–5

3.3 Regret Certification

• Portfolio-regret certification is ∀R-hard for deterministic portfolios in acyclic (s,a)-rectangular RMDPs and belongs to ∀R for both policies and portfolios.The hardness already holds with two-successor uncertain choices, while membership universally quantifies realizations, optimal policies, and Bellman systems.Source: §3.3 · p. 5
• Given-policy robust-regret certification is ∀R-complete under general rational polytopic uncertainty, even for deterministic policies.Under rectangular uncertainty it is coNP-hard and coSQRS-hard, with coNP-hardness already for two-Dirac uncertain choices and uniform splitters.Source: §3.3 · p. 5

3.4 Minimal Robust Regret & Bounded Synthesis

• Minimal robust regret and bounded portfolio synthesis belong to ∃∀R, with minimal regret equal to the unary-budget synthesis case k = 1.The upper bound existentially quantifies candidate policy or portfolio tables, then universally quantifies realizations, optimal policies, and Bellman systems.Source: §3.4 · p. 5
• Under (s,a)-rectangular uncertainty, minimal robust regret is both NP-hard and coNP-hard, and is also SQRS±-hard.These results hold with two-Dirac uncertain choices and certain uniform splitters; irrational interior optima encode signed sums of square roots.Source: §3.4 · pp. 5–6
• For general rational polytopic uncertainty, single-policy minimal robust regret is ∀R-hard but only known to lie in ∃∀R, so completeness remains open.Restricting to memoryless deterministic policies on acyclic rectangular RMDPs instead yields a distinct Σp2-complete problem.Source: §3.4 · p. 6
• Bounded portfolio synthesis is ∃∀R-complete for general rational polytopes, even with unary k, threshold two, fixed γ = 1/2, and nearly acyclic dynamics.The reduction uses one portfolio member per affine test; equality constraints couple state-action choices, so the result does not settle rectangular uncertainty, where hardness already holds for k = 1.Source: §3.4 · p. 6

Benchmarks

• The benchmarks cover datacenter climate control and UAV grid planning, with UAV-small already admitting 795 memoryless deterministic policies and three UAV instance sizes.Datacenter uncertainty concerns cooling effectiveness and ambient pressure; UAV uncertainty concerns wind intensity and actuator-drop probability.Source: §4 · pp. 6–7

Portfolio construction

• The pipeline discretizes each two-parameter box into 100 cells, selects midpoint-optimal candidate policies, computes approximate regret vectors, and uses K-means to form deterministic portfolios.Clustering selects the policy nearest each regret-vector center as a computationally cheap approximation.Source: §4 · p. 7

Portfolio evaluation

• The evaluation samples 1000 parameter valuations to estimate portfolio regret, which under-approximates true regret because it maximizes only over finitely many samples.The same evaluation measures online identification through the fraction of runs recommending the best member and normalized regret relative to it.Source: §4 · p. 7

RQ1: Portfolios reduce robust regret

• Empirical robust regret decreases with K on every benchmark, with the largest drop at K = 2 and further gains as K increases.Portfolios beat mini-max regret on the three largest benchmarks for all K.Source: Table 2 · p. 7, §4 · p. 7

RQ2: Portfolio members can be identified online

• After 104 UCB iterations, about half the K = 10 runs identify the best member, while the recommended policy’s regret gap is minimal.UCB uses fixed-length trajectories in a fixed but unknown environment, with ε = 0.001, δ = 0.1, and H = 100; it follows Cesa-Bianchi and Lugosi (2006) with empirical-Bernstein bounds from Mnih, Szepesvári, and Audibert (2008).Source: Figure 2 · p. 7, §4 · p. 7

5 Conclusion

• The conclusion identifies finite, certifiable adaptation as the portfolio advantage, with ∀R-complete certification, ∃∀R-complete bounded synthesis, and regret decreasing sharply with early portfolio members at increasing identification cost.Certification remains hard under rectangularity; bounded synthesis under rectangular uncertainty and the gap for single-policy minimal robust regret remain open.Source: §5 · p. 7

A Conventions and primitives

• The appendix fixes discount and encoding conventions, then organizes reusable gadgets, ruinous-sink completion, degree-four residual encodings, and Bellman formulas for later reductions.The conventions include a discount chosen for an exact comparison-to-regret lift and an inequality needed by the normalized square-root gadget.Source: A Conventions and primitives · p. 10

A.1 Reduction primitives

• Reduction primitives prescribe terminal values, encode Boolean assignments and verifier audits with two-Dirac gadgets, and use ruinous sinks to penalize undescribed actions while preserving acyclicity and rectangularity.The acceptance-difference verifier converts padded-path value differences into differences of acceptance probabilities.Source: §A.1 · p. 10

A.2 Degree-Four Residual Normal Form

• Degree-four residual normal form represents bounded polynomial constraints using copy and product residuals, with errors bounded by |wν,j − zν,j| ≤ 7δ, |F̂ − F| ≤ 7Bδ, and output error ≤ 9Bδ′.The construction uses auxiliary coordinates in [0,1] and has a common zero exactly when the copies and products are correct.Source: §A.2 · p. 11

A.3 Encoding primitives

• Universal Bellman encoding gives polynomial-size real formulas for explicit policy families and universally quantified policies, while unary-bounded existential policy tables yield existential-universal formulas.Discounting ensures uniqueness of valid Bellman systems, and compactness ensures the relevant extrema are attained.Source: §A.3 · p. 12

B On Policy and Portfolio Comparison

• The policy-comparison section introduces robust comparison problems and constructions that support the later regret lower bounds.Its setup compares memoryless randomized policies under uncertainty using value differences and policy-specific graph structure.Source: B On Policy and Portfolio Comparison · p. 12, §B.1 · p. 12

B.1 Comparison Preliminaries

• When two policies share no uncertain choice, rectangularity separates nature’s optimization over their used rows, making the comparison computable in polynomial time.The result follows from optimistic and robust fixed-policy linear programs and applies to vertex tuples of rectangular uncertainty sets.Source: §B.1 · p. 12

B.2 Combinatorial Hardness of Robust Policy Comparison

• Robust policy comparison is coNP-hard for deterministic policies in acyclic (s,a)-rectangular RMDPs with two-Dirac uncertainty and only a certain uniform splitter.The reduction uses a clause-scanning policy and a variable-auditing policy whose shared local-bit choices evaluate the same assignment.Source: §B.2 · pp. 12, 13, 15
• The hardness construction uses deterministic stationary policies, independent two-Dirac segments, a uniform variable splitter, and an acyclic graph with cycle-free shared choices.Padding equalizes path depths so accepting terminal rewards contribute consistently to the policy difference.Source: §B.2 · pp. 14–15
• A vertex accepts under the clause policy and passes every variable audit exactly when the encoded Boolean formula is satisfiable.Vertex sufficiency bounds nonsatisfying realizations below the satisfying case, yielding the reduction threshold 2 − 1/(2n).Source: §B.2 · p. 15

B.3 Vertex-Extremal Membership

• Robust policy comparison is in coNP for rectangular polytopes when both policies are cycle-free on shared choices.Cycle-freeness implies vertex-extremality; a violating vertex tuple has polynomial encoding length and can be checked using rational Bellman systems.Source: §B.3 · pp. 15–16
• Cycle-freeness makes each shared choice affine and each policy-exclusive choice linear-fractional, so iterated vertex optimization certifies the maximum.A shared choice used at most once cannot influence its own continuation value, whereas a cycle can create an irrational interior maximum.Source: §B.3 · pp. 15–16

B.4 Shared Cycles and Square-Root-Sum Hardness

• Robust policy comparison is coSQRS-hard for deterministic policies with two-Dirac uncertainty and certain uniform splitters.The reduction combines independent shared-cycle gadgets, each producing a normalized square-root term, with the splitter aggregating their maxima.Source: §B.4 · pp. 16–17
• A shared cycle with asymmetric discount lengths yields a rational-fraction policy difference whose unique interior maximum produces the required square-root contribution.The asymmetry is essential: without the extra discounted step, the difference becomes monotone and has no interior maximum; sign control places the critical point as the maximum.Source: §B.4 · pp. 16–17

B.5 Real-Hierarchy Completeness of Policy Comparison

• Robust policy comparison is ∀R-complete for deterministic policies under general rational polytopic uncertainty.Membership follows by fixing one policy and comparing it against a singleton family containing the other.Source: §B.5 · p. 17
• The polynomial-evaluation component maps each realization of occurrence rows to the polynomial value, including f(p) when representative coordinates equal p.It is acyclic apart from absorbing terminals, uses two-successor uncertain rows and a uniform splitter, and has polynomial size and a polynomial-description rational polytope.Source: §B.5 · p. 18
• ∀R-hardness reduces the complement of strict positivity for an explicitly represented degree-six polynomial to deterministic policy comparison.The reduction adds an initial choice between the polynomial-evaluation component and a zero-reward sink, with policies selecting the two alternatives.Source: §B.5 · p. 18
• The completeness theorem follows immediately by combining the ∀R membership and ∀R-hardness lemmas.Source: §B.5 · pp. 17–18

B.6 Portfolio Comparison and the Shared-Selector Evaluator

• Portfolio comparison is ∀R-complete, with hardness for deterministic policies and acyclic (s,a)-rectangular RMDPs having two-successor uncertain choices.Membership is established separately, while hardness follows from a reduction from strict elementary feasibility.Source: §B.6 · p. 19
• Strict elementary feasibility for affine or single-bilinear inequalities over [0,1]^n is ∃R-complete.Each expression contains no repeated variable, matching the later stationary-policy construction.Source: §B.6 · p. 19
• The shared-selector evaluator gives each variable a shared selector with outcomes weighted by x_j and 1−x_j, while branch payoffs cancel probability and discount-depth factors.Deterministic splitters and decoders leave uncertainty only at selectors, preserving (s,a)-rectangular structure.Source: §B.6 · p. 19
• The evaluator defines π0 as a zero-value default policy and πi to select ai and decode exactly the variables appearing in gi.No variable repetition within an expression ensures each deterministic stationary policy is well-defined.Source: §B.6 · p. 20
• In the worked evaluator, terminal rewards 2, −16, 1, and −64 realize the branch contributions for −g1 and −g2 after discounting.The construction shares selector q1 while policies diverge through decoder actions.Source: §B.6 · p. 20, The first policy consequently has value · p. 20

The first policy consequently has value

• The reduction is polynomial, acyclic apart from absorbing finals, and uses polynomial-bit-length terminal payoffs; π0 has value 0 and πi has value −gi(x).Selectors are independently uncertain, giving the required rectangularity and two-successor property.Source: The first policy consequently has value · pp. 20–21
• The comparison threshold is positive exactly when the strict system is feasible, so its upper-threshold language is the complement of an ∃R-complete problem.This establishes ∀R-hardness, which combined with membership proves Theorem 24.Source: The first policy consequently has value · p. 21

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

• Regret certification belongs to ∀R because Bellman equations encode explicit portfolio members and universally quantified memoryless randomized policies.Quantifying all such policies is sound because every realized discounted MDP has an optimal deterministic policy; the given-policy case is r = 1.Source: C Proofs of Theorems 1 and 5:… · p. 21
• Minimal robust regret and bounded portfolio synthesis belong to ∃∀R by existentially quantifying k policy tables before Lemma 13’s universal encoding.Unary-bounded k keeps the formula polynomial, and the single-policy case is k = 1.Source: C Proofs of Theorems 1 and 5:… · p. 21
• The synthesis formula matches the infimum defining ρ_k because rational-polytope uncertainty is compact and portfolio attainment holds.Ordered policy tuples lie in a compact product of simplexes, while Bellman solutions and the maximum over finitely many deterministic policies vary continuously.Source: C Proofs of Theorems 1 and 5:… · p. 21
• The attainment lemma applies to every input of Problem 4 and to the synthesis RMDP because its proof requires no acyclicity.Repeating portfolio members represents smaller sets without changing their pointwise maximum.Source: C Proofs of Theorems 1 and 5:… · p. 21

D Exact Transfer from Policy Comparison to Robust Regret

• The lift makes a fixed reference policy pointwise optimal by routing source actions through selector states and adding a calibrated bonus action.The construction preserves (s, a)-rectangularity, determinism, acyclicity, and source uncertainty structures, including two-successor and two-Dirac choices.Source: D Exact Transfer from Policy… · pp. 22–23
• The bonus action is uniquely optimal at every tag state because K = 2Vmax + 1 creates a margin exceeding every allowed-action backup.A sufficiently large ruinous-sink penalty Z makes undescribed or sink-entering choices suboptimal, completing the Bellman argument.Source: D Exact Transfer from Policy… · pp. 22–23
• For every realization, the lifted candidate policy preserves the source policy’s value, while the lifted bonus policy realizes the reference value plus a fixed offset.The discount choice β^2 = γ0 makes each lifted two-step path match one source step, enabling exact comparison-to-regret identities.Source: D Exact Transfer from Policy… · p. 23

E.1 Rectangular Given-Policy Hardness

• Given-policy robust regret is coNP-hard and coSQRS-hard under (s, a)-rectangular uncertainty, with coNP-hardness already for two-Dirac uncertain choices and certain uniform splitters.The reductions use singleton portfolios and transfer comparison thresholds to rational regret thresholds while retaining acyclic structure.Source: §E.1 · p. 24
• The coNP reduction maps an unsatisfiable formula to a yes-instance of lifted robust-regret certification using threshold Λ + 2 − 1/2^n.It starts from an acyclic rectangular comparison instance with deterministic policies, independent two-Dirac choices, and one certain uniform splitter.Source: §E.1 · p. 24
• The coSQRS reduction transfers a comparison inequality directly: ΔU(πu, πv) ≤ t if and only if Rreg(bπv) ≤ Λ + t.It uses deterministic policies and a rectangular source with two-Dirac uncertainty.Source: §E.1 · p. 24

E.2 Rectangular Portfolio Certification

• Portfolio-regret certification is ∀R-hard even for deterministic portfolios in acyclic (s, a)-rectangular RMDPs with two-successor uncertain choices.The family-form lift applies to a reference policy and explicit portfolio, translating the zero comparison threshold into the rational regret threshold Λ.Source: §E.2 · p. 24

E.3 General-Polytope Regret Certification

• Given-policy robust regret is ∀R-complete under general rational polytopic uncertainty, even for deterministic policies.Membership is the singleton-family case of Lemma 13.Source: §E.3 · p. 24
• The positive-part gadget makes regret equal sup_p∈[0,1]m max{γ0f(p), 0}, so threshold zero decides whether f(p)≤0 universally.A fresh initial choice compares entering the polynomial evaluator with a zero-reward sink.Source: §E.3 · p. 24

F Proof of Theorem 6: Combinatorial Minimal-Regret Hardness

• Minimal robust regret is NP-hard and coNP-hard for (s,a)-rectangular RMDPs whose uncertain choices are two-Dirac and whose other stochastic rows are uniform splitters.The hardness applies to both Boolean lower bounds under this restricted uncertainty structure.Source: F Proof of Theorem 6: Combinatorial… · p. 25

F.1 Policy Restriction

• Unfolding absorbing finals preserves every policy value and robust regret while maintaining rectangularity, acyclicity, and polynomial encoding length.After unfolding, the zero-reward sink is the only self-looping state, and interpolated modified rows leave their source states.Source: §F.1 · pp. 25, 27
• The policy-restriction transformation routes disallowed actions through a ruinous sink, transferring restricted synthesis to unrestricted synthesis within an arbitrarily small ε.For randomized or deterministic policy classes, inf ρ Rreg_Nε(ρ) ≥ inf π∈Pallow Rreg_N(π) − ε.Source: §F.1 · p. 25, F Proof of Theorem 6: Combinatorial… · p. 25

F.2 coNP-Hardness

• The coNP-hardness reduction restricts the lifted candidates to the single consistency policy, preventing candidates from using the reference policy’s bonus route.Singleton allowed actions eliminate any remaining minimization over candidate policies.Source: §F.2 · p. 27
• The certification gap transfers unchanged apart from the lift’s constant Λ, with the final threshold Λ + 2 − 1 2n establishing the coNP-hard part.The second case incurs ε = 1 4n through policy restriction, while the first case has no slack.Source: §F.2 · p. 27

F.3 NP-Hardness

• The construction uses acyclic scanner and audit policy graphs with shared local-bit selectors, equalized path depth H, and terminal payoffs that encode acceptance probabilities.The scanner searches for a locally false clause, while the valuation policy audits the assignment selected at each variable state.Source: §F.3 · p. 28
• Satisfying assignments make scanner and valuation acceptances disjoint, whereas falsifying assignments admit a shared Boolean realization where both policies accept.This verifier separation is the core correspondence between formula satisfaction and joint policy acceptance.Source: §F.3 · p. 28
• The verifier gap is Gφ ≤1 for some deterministic valuation policy when φ is satisfiable, but Gφ ≥1 + 2^-n for every randomized valuation policy when φ is unsatisfiable.The satisfiable bound extends over the product polytope, while unsatisfiability forces a complete valuation with probability at least 2^-n.Source: §F.3 · p. 29
• Applying the restriction and lifting lemmas transfers the verifier gap to minimal robust regret while constraining synthesized policies to the valuation graph.The reduction sets the restriction target to 2^-n/4 and uses singleton disallowed bonus choices.Source: §F.3 · p. 29
• A threshold of Λ + 1 + 2^-n−1 separates the reduced instances, proving NP-hardness; combined SAT and UNSAT reductions establish both NP- and coNP-hardness.The rational gaps remain separating after restriction loss, and the reductions preserve the stated structural restrictions.Source: §F.3 · p. 29

G Deterministic Minimal-Regret Complexity

• The deterministic minimal-regret complexity section begins by establishing membership before presenting a matching hardness construction.This section therefore frames the subsequent complexity characterization around both membership and hardness.Source: G Deterministic Minimal-Regret… · p. 29

G.1 Acyclic Deterministic Membership

• The reduction remains valid because its verifier policies are stationary deterministic, each uncertain choice is visited at most once, and the composed RMDP is acyclic apart from absorbing finals.Acyclicity permits backward induction and vertex attainment for the remaining uncertainty choices.Source: §G.1 · pp. 30–31
• For every assignment α, the reduction satisfies Gψ(α) ≤ 2 − 1/M when every universal assignment satisfies ψ(α, y), and Gψ(α) = 2 when some falsifying assignment exists.Source: §G.1 · p. 31
• Minimal robust regret over memoryless deterministic policies is Σ_2^p-complete on acyclic (s, a)-rectangular polytopic RMDPs, even with two-Dirac uncertainty and uniform splitters.Membership uses existential and universal polynomial certificates evaluated by exact backward induction; hardness reduces from the canonical Σ_2^p-complete problem.Source: §G.1 · pp. 30, 32

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

• Minimal robust regret is SQRS±-hard under (s, a)-rectangular uncertainty, using one-state gadgets whose regret balances decreasing and increasing functions of a policy’s mixing probability.The balancing optimum solves a quadratic equation and is generally irrational.Source: H Proof of Theorem 7: Signed… · p. 32

H.1 One-State Balancing

• The one-state gadget has two actions with independent continuation probabilities pL, pR ∈ [0, h] and a zero-reward sink, where h = (1 − q)/γ.The parameters satisfy q ∈ (0, 1) and γ ∈ (1 − q, 1), ensuring valid transition probabilities.Source: Figure 10 · p. 32, §H.1 · p. 32
• The positive-reward parametrization realizes m+(A, B), while the negative-reward parametrization realizes m−(A, B) when q^2 ≥ 1/2.A randomized memoryless policy is determined by its probability x of playing L.Source: §H.1 · p. 33
• For the negative-reward form, the minimum is attained by balancing a strictly decreasing term against a strictly increasing term, yielding (1 − q^2)y^2 + qDy − AB = 0, whose positive root is m−(A, B).Source: §H.1 · p. 33

H.2 Rational Square-Root Gadgets

• Polynomial-time rational gadgets realize local minimal-regret contributions for both negative and positive square-root coefficients while preserving polynomial binary length.Lemma 40 provides the negative-coefficient gadget, and Lemma 41 provides the positive-coefficient gadget using a negative-reward (s,a)-rectangular construction.Source: §H.2 · pp. 34–35
• The positive-coefficient gadget constructs rational D and c satisfying D^2 − c^2 = b, while ensuring its local regret is positive.The construction chooses rational parameters with polynomial bit length and applies the negative-reward form of Lemma 39.Source: §H.2 · pp. 34–35

H.3 Additive Composition

• An additive splitter combines disjoint independent gadgets so that global minimal robust regret equals the sum of their local minima, while preserving (s,a)-rectangularity.The splitter uses a uniform initial state, scales gadget rewards by n/γ, and completes remaining choices with ruinous sinks.Source: §H.3 · p. 35

H.4 Proof of Theorem 7

• Theorem 7 reduces the non-strict ≤ direction of SQRS± to an (s,a)-rectangular RMDP and rational threshold by instantiating positive- and negative-coefficient local gadgets.Unit roots contribute separately, while non-unit roots are represented by Lemmas 41 and 40 and then composed with a common discount factor.Source: §H.4 · pp. 35–36
• The resulting SQRS± reduction preserves (s,a)-rectangularity because the uncertainty set is the product of the local choice uncertainty sets.The construction also uses additive composition of the local gadgets after selecting a common discount factor valid for every gadget.Source: §H.4 · p. 36

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

• Theorem 8 proves that single-policy minimal robust regret is ∀R-hard for arbitrary rational polytopic uncertainty.The proof first establishes an existential-universal upper bound and then uses two-action anchoring to obtain a strictly monotone minimal-regret objective.Source: I Proof of Theorem 8: General-Polytope… · p. 36

I.1 Existential-Universal Membership

• The existential-universal membership claim is established together with its certification counterpart in Appendix C.This supplies the membership component associated with the general-polytopic single-policy result.Source: §I.1 · p. 36

Two-action anchoring RMDP

• The anchoring RMDP uses two forced copies sharing realization p, fresh mixing coordinates λα and λβ, absorbing anchors ±Z, and a ruinous sink −Zr.The initial actions enter separate copies with probabilities λα and λβ; all remaining choices use ruinous-sink completion.Source: §I.2 · p. 37, Figure 12 · p. 37

Anchored action values

• A policy choosing α with probability x has robust regret max{(1 −x)D, xE}, where D = L + γ∆ and E = 2γZ −L are positive.The endpoint analysis shows D and E are the worst-case branch losses, with D ≥ |γt| + 1 > 0.Source: §I.2 · p. 37

Two-action anchoring

• After projecting arbitrary stationary policies to compliant policies, the minimum robust regret is attained by balancing the branches at DE/(D + E).The projection preserves or improves values at every realization, reducing the optimization to the single initial mixing probability x.Source: §I.2 · pp. 37–38

Anchoring an irrational comparison gap

• For Example 8, E = 8, T = 3, and t′ = 24/11, and the anchoring constants and threshold remain rational despite an irrational comparison gap.The balanced regret DE/(D + E) depends on the irrational source gap.Source: §I.2 · p. 38

Proof of Theorem 8

• The construction establishes the comparison equivalence used in the reduction from Theorem 20’s ∀R-hard problem.The proof invokes the equivalence above as the final reduction step.Source: §I.2 · p. 38

J Proof of Theorem 9: Bounded Portfolio Synthesis

• Theorem 9 proves bounded portfolio synthesis is ∃∀R-complete for rational polytopic uncertainty, unary-encoded portfolio size, regret threshold two, discount γ = 1/2, and acyclic RMDPs with two-successor uncertain rows.The reduction handles policy-independent rewards, stationary continuation choices, and agreement on a shared witness by placing nature’s audits inside polynomial coefficients rather than model branches.Source: J Proof of Theorem 9: Bounded… · p. 38

J.1 Existential-Universal Membership

• Membership in ∃∀R is established separately in Appendix C.Source: §J.1 · p. 38

J.2 A Policy-Affine Max Normal Form

• The policy-affine max normal form converts bounded-degree polynomial constraints into tests affine in the existential witness, with bounded values and coefficients and quadratic dependence on auxiliary coordinates.The construction uses residual tests so a valid witness makes every test nonnegative, while an invalid witness yields an auxiliary valuation making all tests negative.Source: §J.2 · pp. 38–39

J.3 Exact Evaluators

• Exact evaluator components represent sparse polynomials and affine policies while giving each coordinate state one predecessor, preventing context-dependent interpretations of stationary policy choices.The evaluator’s choices occur only at coordinate states, with fixed continuations and ruinous-sink completion elsewhere.Source: §J.3 · pp. 39–40

J.4 Roles, Cases, and Scores

• Portfolio case scores encode evaluation, oriented equality, and forcing cases; their mixed scores remain polynomially representable, with degrees at most three and one for the two resulting terms.Nature’s cases are polynomial coordinates rather than branches, preserving the single-predecessor evaluator structure.Source: §J.4 · pp. 40–41

J.5 The Synthesis RMDP

• The synthesis RMDP uses evaluator copies, auxiliary polynomial components, tied occurrence coordinates, and simplex-constrained case weights, yielding a nonempty rational polytope with two-successor uncertain rows and polynomial encoding length.Source: §J.5 · p. 41

J.6 Action Values and the Optimal-Value Bound

• The optimal value at the initial state is at most two for every realization and equals two at pure cases, while pure-case coverage is equivalent to nonnegative mixed scores.The mixing correction can be tight: a role scoring zero in one of two equally weighted cases and −1 in the other has mixed score zero after the correction.Source: §J.6 · pp. 41–42

J.7 Correctness

• Correctness shows a source witness yields a portfolio with Rreg(Π) ≤2, while any such portfolio has exactly one pure role member per role and all members encode the same witness.Forcing cases enforce role coverage, and oppositely oriented equality cases enforce coordinate-wise equality between role vectors.Source: §J.7 · pp. 42–43
• Theorem 9 establishes ρ_r ≤ 2 iff ∃x ∀y: F(x,y) ≥ 0, with a polynomial reduction satisfying the stated restrictions.Membership follows from existential-universal encoding, while hardness uses Lemmas 56–59 and the reduction’s structural bounds.Source: §J.7 · p. 43

J.8 Size and Structural Restrictions

• The synthesis reduction is polynomial and uses unary budget r, degree-at-most-three polynomial components, fixed discount 1/2, threshold two, and acyclic dynamics except absorbing terminals.Uncertainty has two successors per uncertain row; rewards are fixed rational values, and nonrectangularity comes only from tying equalities and the simplex constraint.Source: §J.8 · pp. 43–44

K Experimental setup

• The experimental appendix evaluates whether portfolio size reduces robust regret and whether online selection identifies the best member in a fixed unknown environment.It defines the benchmark models and uncertainty sets, offline construction, two evaluations, and reports results in later tables and figures.Source: K Experimental setup · p. 44

K.1 Parametric MDPs and their uncertainty sets

• Both benchmarks are affine pMDPs over compact parameter boxes, but repeated parameters induce nonrectangular uncertainty sets that are relaxed to rectangular interval MDPs for robust value iteration.The relaxation adds transition vectors by dropping equalities tying repeated parameter occurrences together.Source: §K.1 · p. 44

K.2 Offline portfolio construction

• Offline construction grids the parameter box, obtains one midpoint-optimal deterministic candidate per cell, robustly scores candidates, and selects K representatives by K-means profile clustering.The clustering score is not a certificate: midpoint anchoring and rectangular relaxation approximate cellwise regret, while sampled evaluation supplies the reported guarantees.Source: §K.2 · pp. 44–45

K.3 RQ1: measuring portfolio regret

• RQ1 evaluates each portfolio on 1,000 uniformly sampled valuations using exact instantiated-MDP values, so the reported sampled regret under-approximates true robust regret.The procedure repeats for seeds 0, 1, and 2; Table 5 reports individual seeds and Table 2 reports their mean.Source: §K.3 · p. 45

K.4 RQ2: online portfolio selection

• RQ2 treats portfolio policies as bandit arms and uses empirical-Bernstein UCB to eliminate inferior members and recommend the greatest-lower-confidence-bound arm until the stopping test fires.It measures recommendation accuracy and normalized shortfall against the best portfolio member, using 90 runs per portfolio size after pooling three seeds.Source: §K.4 · pp. 45–46

K.5 Datacenter benchmark

• The datacenter benchmark has 330 states, five energy-comfort actions, and unknown cooling effectiveness and environmental pressure in [0.5, 0.9] × [0.1, 0.8].Transitions have four affine successor branches, while deterministic rewards combine energy costs with ceiling penalties; γ = 0.95, Rmax = 104, and Vmax = 2080.Source: §K.5 · pp. 46–47

• The benchmark represents UAV flight from a fixed start to a landing pad through a three-dimensional grid with absorbing Crash, Goal, and terminal done states.States use coordinates (x, y, z), with the start at s0 = (0, floor(Ly/2), 1) and a three-cell landing pad on the far wall.Source: §K.6 · p. 47
• Wind intensity p and actuator-drop probability q penalize opposite routes, causing the optimal route to switch with (p, q).Wind hurts the low corridor, whereas altitude drops hurt the high crossing; the procedural slab, pillar, and canopy enforce this trade-off.Source: §K.6 · p. 47
• Three transition branches implement intended motion, one-cell lateral wind drift, or altitude loss, with obstacle and target redirection to Crash or Goal.The branch probabilities are 1−p−q, p, and q, respectively, under pmax + qmax < 1.Source: §K.6 · p. 47
• The generator scales across grid extents (Lx, Ly, Lz), with three benchmark sizes sharing (pmax, qmax, γ) = (0.25, 0.20, 0.99).The obstacle and goal formulas preserve the low-versus-high route trade-off at every size.Source: §K.6 · p. 48, Table 4 · p. 48
• 7|S|−3 memoryless deterministic policies make exhaustive policy search infeasible even for uav-small.Every grid cell offers seven actions, while Goal, Crash, and done reduce the count by three.Source: §K.6 · pp. 47–48

Regret results (RQ1)

• Across benchmarks, max-regret reports each portfolio’s worst sampled loss relative to Vmax, while inertia declines steeply with K as a clustering diagnostic rather than a performance measure.Table 5 contains seed-level regret results, averaging three clustering seeds for each portfolio size.Source: L Experimental data · p. 48, Table 5 · p. 49

Online selection results (RQ2)

• As K grows, the UCB selector’s correct-arm rate visibly decreases, but normalized shortfall remains low because confused portfolio members have similar values.The reported measures are pooled correct-arm fraction and normalized regret across all four benchmarks and tested portfolio sizes.Source: L Experimental data · p. 48, Figure 14 · p. 50, Figure 15 · p. 51

Experimental protocol

• The evaluation pipeline discretizes the domain, constructs and robustly scores candidate policies, clusters them into portfolios, computes empirical robust regret, and deploys each portfolio with UCB.Results are averaged over seeds, with UCB samples pooled across seeds for reporting.Source: L Experimental data · p. 52