PaperlayerView exact revision on arXiv

Source-linked AI summary

Adaptive Policy Portfolios for Robust Markov Decision Processes

Kasper Engelen, Sebastian Junges, Guillermo A. Pérez, Marnix Suilen

arXiv:2608.17929v1cs.AIcs.LO

TL;DR

Robust policies can be overly conservative when fixed unknown dynamics become identifiable after deployment. This paper studies offline-synthesized adaptive policy portfolios and proves exact complexity classifications for certification and bounded synthesis, while identifying open gaps for single-policy minimal robust regret.

  • Problem

    Robust MDPs may produce overly conservative policies because they optimize against worst-case dynamics, motivating finite portfolios that adapt after deployment.

  • Method

    The paper synthesizes finite sets of memoryless policies for uncertainty-set regions and pairs them with runtime selection based on accumulated evidence, minimizing robust regret.

  • Results

    Portfolio certification is ∀R-complete, while unary-bounded portfolio synthesis is ∃∀R-complete; these hardness results persist under acyclic rectangular uncertainty.

  • Takeaways & Limitations

    Adaptive portfolios offer finite, certifiable adaptation between committing to one robust policy and planning over a full belief state.

  • Takeaways & Limitations

    The current bounds do not establish completeness for single-policy minimal robust regret under general rational polytopic uncertainty.

Abstract

from arXiv · show

Robust Markov decision processes optimize one policy against a set of plausible transition functions. This can be conservative when the unknown dynamics are fixed and become partially identifiable after deployment. We study adaptive policy portfolios: finite sets of memoryless randomized policies synthesized offline and paired with a lightweight online selector. Robust regret is a natural measure of portfolio quality: for each plausible environment, it measures the loss of the best portfolio member relative to the policy that would have been optimal had that environment been known. Related regret objectives were studied by Ghavamzadeh et al. (2016) with an emphasis on approximations and relaxations for safe policy improvement. We give a complexity-theoretic account of portfolio certification and synthesis. Certifying a given portfolio is $\forall\mathbb{R}$-complete already for deterministic portfolios in acyclic (s,a)-rectangular RMDPs. Synthesizing a portfolio of unary-bounded size is $\exists\forall\mathbb{R}$-complete for general rational polytopes, even with fixed discount and acyclic dynamics. The single-policy case is already hard, both combinatorially and algebraically. Finally, we present an offline portfolio construction that is amenable to runtime specialization.

1 Introduction

The paper introduces adaptive policy portfolios: finite, certifiable sets of memoryless policies synthesized offline and selected online using accumulated evidence. It establishes strong complexity lower bounds for portfolio certification and synthesis while presenting a practical offline construction amenable to runtime specialization.

  • Adaptive policy portfolios: Adaptive policy portfolios provide a finite and certifiable form of RMDP adaptation by tailoring policies offline to uncertainty regions and selecting among them online.The portfolio is synthesized by minimizing robust regret and focuses on memoryless policies.
  • Motivation: A single robust-regret policy can remain conservative: in the actuator example, c = 1/2 has worst-case regret 1/4, whereas {0, 1/2, 1} reduces it.The example models unknown slip p ∈[0, 1] and calibration actions C = {0, 1/8, . . . , 1}.
  • Complexity results: Hardness persists under structural assumptions that usually simplify RMDPs, including rectangularity, with additional Boolean and square-root-sum sources arising from shared uncertainty, recurrence, and policy choice.The introduction states that rectangularity does not rescue portfolio certification and identifies signed-square-root-sum hardness from policy selection.
  • Practical construction: The practical construction discretizes uncertainty into cells, computes and evaluates candidate policies across cells, clusters regret profiles to the portfolio budget, and uses UCB for runtime selection.This offline construction remains useful despite worst-case bounds and is designed for runtime specialization.
  • Complexity results: Given-portfolio certification is ∀R-complete, while bounded-portfolio synthesis is ∃∀R-complete.These classifications are stated as exact portfolio results in the introduction and summarized in Table 1.

2 Problem Statement

The paper models uncertainty with robust Markov decision processes whose transition functions form a convex polytope, and evaluates policies by their shortfall from environment-specific optima. It then defines adaptive policy portfolios as finite offline-synthesized sets of memoryless randomized policies, seeking the lowest robust regret achievable with at most k members.

  • RMDP model: An RMDP consists of finite states and actions, rewards, an initial state, a discount factor, and a convex polytope of valid transition vectors.Each uncertainty realization induces a classical MDP.
  • Policy classes: Candidate policies are generally memoryless randomized policies, while memoryless deterministic policies select one action per state.The policy classes are denoted ΠMR and ΠMD, with ΠMD ⊆ ΠMR.
  • Robust value and regret: Robust regret measures a policy’s largest shortfall from the policy optimal for each particular transition realization, rather than its raw worst-case value.The realization is treated as nature’s move.
  • Adaptive policy portfolios: An adaptive policy portfolio is a finite set of offline-synthesized candidate policies paired with a runtime mechanism that selects among them as evidence accumulates.Portfolio regret compares the best portfolio member for each realization and idealizes away the cost of identifying that member.
  • Portfolio objective: The optimization target is ρk, the infimum robust regret over portfolios containing at most k memoryless randomized policies.The single-policy objective is the k = 1 case.

3 Computational Complexity

The section establishes a PSPACE-bounded complexity landscape for policy comparison, regret certification, and portfolio synthesis. Certification is already highly intractable for deterministic portfolios, while bounded synthesis reaches ∃∀R-completeness under general rational polytopic uncertainty.

  • Common upper bound: All studied complexity classes share a PSPACE upper bound.This includes every polynomial-hierarchy level, each fixed real-hierarchy level considered, and SQRS±.
  • Policy and portfolio comparison: ∀R-completeness holds for portfolio comparison even under (s, a)-rectangular uncertainty.The pointwise maximum over the explicit portfolio supplies the real quantifier alternation.
  • Regret certification: Given-policy robust regret is coNP-hard and coSQRS-hard under (s, a)-rectangular uncertainty, and ∀R-complete under general rational polytopic uncertainty.The coNP-hardness persists with two-Dirac uncertain choices and certain uniform splitters; the ∀R-completeness also holds for deterministic policies.
  • Regret certification: ∀R-hardness holds for portfolio-regret certification with deterministic portfolios and acyclic (s, a)-rectangular RMDPs.The hard instances use two-successor uncertain choices.
  • Portfolio synthesis: ∃∀R-completeness holds for bounded portfolio synthesis under general rational polytopic uncertainty with unary-encoded k.Hardness already holds for regret threshold two and fixed discount γ = 1.

4 Portfolio Construction and Evaluation

The evaluation uses two new uncertain-control benchmarks and a three-phase offline pipeline that discretizes parameter space, clusters candidate policies, and evaluates portfolios by sampled robust regret. Empirical regret decreases as portfolio size grows, while UCB can identify the best member online, with identification slowing for larger portfolios.

  • Benchmarks: Two new benchmarks cover datacenter climate control and UAV control under uncertain parameters.The datacenter instance has Vmax = 2080; UAV value is discounted landing probability with Vmax = 100, across small, medium, and large grids.
  • Benchmarks: 795 deterministic memoryless policies already exist in uav-small, ruling out exhaustive search.Each grid position offers seven actions.
  • Portfolio construction: The offline pipeline generates midpoint-optimal candidates from 100 parameter cells and uses K-means to select policies nearest cluster centers.Each of the two benchmark parameters is discretized into 10 bins, producing 100 cells; clustering provides a computationally cheap approximation.
  • RQ1: Portfolios reduce robust regret: Empirical robust regret decreases with K on every benchmark, with the largest single drop at K = 2 and further gains as K increases.Portfolios beat mini-max regret for all K on the three largest benchmarks.
  • RQ2: Portfolio members can be identified online: After 104 iterations, about half of UCB runs recover the best member at K = 10, and identification slows as the portfolio grows.UCB uses fixed-length trajectories in a fixed but unknown environment with ε = 0.001 and δ = 0.1.

5 Conclusion … B.1 Comparison Preliminaries

The paper positions adaptive policy portfolios between single robust policies and full belief-state planning, while establishing strong complexity barriers for certification and synthesis. Its comparison preliminaries characterize when policy differences under rectangular uncertainty become independently optimizable and polynomial-time computable.

  • 5 Conclusion: Adaptive policy portfolios provide finite, certifiable adaptation between committing to one robust policy and planning over a full belief state.The paper describes portfolios as finite sets of memoryless randomized policies paired with lightweight online selection.
  • 5 Conclusion: Certification is ∀R-complete, while unary-bounded portfolio synthesis is ∃∀R-complete under rational polytopic uncertainty.Certification remains hard under rectangularity because the pointwise maximum over portfolio members restores quantifier alternation.
  • A.1 Reduction primitives: A terminal with payoff c contributes wγ^dc after d transitions reached with probability w, enabling exact value-preserving reduction gadgets.Absorbing finals use Dirac self-loops, and terminal rewards are scaled by (1 −γ).
  • A.1 Reduction primitives: Local-bit selectors encode Boolean values through two-Dirac outcomes, while pair tests and audits verify local truth, falsity, or assigned values.Pair tests read designated satisfying and nonsatisfying outcomes; audits advance on outcome one and reject on outcome zero.
  • A.2 Degree-Four Residual Normal Form: Degree-four residual encoding bounds polynomial error by |bF −F| ≤7Bδ and output error by |o −F| ≤9Bδ′.Auxiliary coordinates represent copies and products, with residuals restricted to [−1, 1].
  • A.3 Encoding primitives: Universal Bellman encoding yields polynomial-size universal real formulas, and unary-bounded existential policy families produce existential-universal formulas.Discounting ensures unique valid Bellman systems, while compactness ensures the relevant extrema are attained.
  • B.1 Comparison Preliminaries: Policy comparison measures the supremum over realizations of the initial-state value difference Dπ1,π2(u), with vertex tuples representing rectangular uncertainty realizations.Shared choices and policy-induced reachability graphs provide the structural definitions used in the comparison problems.
  • B.1 Comparison Preliminaries: For separated policies sharing no uncertain choice, rectangularity lets nature optimize their used rows independently.The resulting comparison is computable in polynomial time through optimistic and robust fixed-policy linear programs.

B.2 Combinatorial Hardness of Robust Policy Comparison · B.3 Vertex-Extremal Membership · B.4 Shared Cycles and Square-Root-Sum Hardness

The paper establishes combinatorial and algebraic hardness for robust policy comparison, while identifying a cycle-free regime where vertex analysis yields coNP membership. Shared cycles instead enable interior maxima and coSQRS-hardness through normalized square-root terms.

  • 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 uncertain choices and one certain uniform splitter.The reduction uses shared local-bit choices so clause scanning and variable auditing evaluate the same assignment.
  • B.2 Combinatorial Hardness of Robust Policy Comparison: The reduction distinguishes satisfying assignments, whose canonical vertices attain difference 2, from unsatisfying cases bounded by 2 − 1/(2n).A vertex satisfying the clause constraints has at least one failing variable audit, while a vertex violating them has difference at most 1.
  • B.3 Vertex-Extremal Membership: Cycle-free shared choices make robust policy comparison vertex-extremal and place it in coNP for (s, a)-rectangular polytopes.The complement guesses a polynomial-size vertex tuple, verifies membership, solves rational Bellman systems, and compares initial values in polynomial time.
  • B.3 Vertex-Extremal Membership: The vertex-extremality hypothesis is necessary: a shared choice on a policy cycle can create an irrational interior maximum, making endpoint evaluation unsound.The proof analyzes blocks separately, using linear-fractional dependence for choices used by one policy and single-use behavior for cycle-free shared choices.
  • B.4 Shared Cycles and Square-Root-Sum Hardness: Robust policy comparison is coSQRS-hard for deterministic policies with two-Dirac uncertain choices and certain uniform splitters.The construction remains (s, a)-rectangular and uses the appendix-wide discount γ0.
  • B.4 Shared Cycles and Square-Root-Sum Hardness: A shared choice on a cycle yields a normalized square-root term whose exact derivative identifies an interior maximum; uniform splitting combines independent maxima into a square-root sum.Sign control at the critical point establishes that the unique derivative zero is a maximum.
  • B.4 Shared Cycles and Square-Root-Sum Hardness: The reduction satisfies ΔU(πu, πv) ≤ t exactly when the coSQRS instance is positive, with every uncertain choice remaining two-Dirac.Independent gadget copies are combined through certain uniform splitters and rectangularity.

B.5 Real-Hierarchy Completeness of Policy Comparison

Robust policy comparison for deterministic policies under general rational polytopic uncertainty is ∀R-complete. The completeness proof combines ∀R membership with a polynomial-evaluation RMDP construction establishing ∀R-hardness.

  • B.5 Real-Hierarchy Completeness of Policy Comparison: ∀R-complete: Robust policy comparison is ∀R-complete for deterministic policies under general rational polytopic uncertainty.Membership and hardness are established separately for this setting.
  • B.5 Real-Hierarchy Completeness of Policy Comparison: ∀R membership: Robust policy comparison belongs to ∀R for deterministic policies under general rational polytopic uncertainty.The proof applies the general comparison lemma with τ fixed to π1 and singleton family {π2}.
  • B.5 Real-Hierarchy Completeness of Policy Comparison: Polynomial evaluation: The constructed RMDP realizes f(p) as the compliant value at its initial state when representative coordinates equal p.The component is acyclic apart from absorbing terminals, has two-successor uncertain rows, and uses a polynomial-size rational polytope.
  • B.5 Real-Hierarchy Completeness of Policy Comparison: ∀R-hardness: Robust policy comparison is ∀R-hard for deterministic policies under general rational polytopic uncertainty.The reduction uses strict degree-six polynomial positivity and its complement.

B.6 Portfolio Comparison and the Shared-Selector Evaluator · The first policy consequently has value

Portfolio comparison is ∀R-complete, with hardness already for deterministic policies and acyclic (s,a)-rectangular RMDPs with two-successor uncertainty. The shared-selector evaluator reduces strict elementary feasibility to policy values, establishing this hardness through a first policy of value zero and portfolio policies encoding the constraint expressions.

  • B.6 Portfolio Comparison and the Shared-Selector Evaluator: Portfolio comparison is ∀R-complete when portfolio size is part of the input.Membership is in ∀R, and hardness holds under restricted deterministic, acyclic dynamics.
  • B.6 Portfolio Comparison and the Shared-Selector Evaluator: Strict elementary feasibility is ∃R-complete for affine or single-bilinear strict inequalities over x ∈ [0,1]^n.Each expression contains no repeated variable, and the hardness construction uses bounded degree-four equality normal form.
  • B.6 Portfolio Comparison and the Shared-Selector Evaluator: Hardness already holds for deterministic policies and acyclic (s,a)-rectangular RMDPs with two-successor uncertain choices.The reduction uses independent selector choices and an acyclic transition graph apart from absorbing finals.
  • B.6 Portfolio Comparison and the Shared-Selector Evaluator: The shared-selector evaluator represents each variable with one selector shared across every branch whose expression mentions that variable.Each expression −g_i is decomposed into linear or bilinear monomial branches, with branch payoffs cancelling their own probabilities and depths.
  • B.6 Portfolio Comparison and the Shared-Selector Evaluator: The evaluator provides deterministic stationary policies π0,π1,…,πr, with π0 choosing the zero-reward sink and πi selecting the branch structure for g_i.The policy assignments are well-defined because no variable occurs twice in any expression g_i.
  • B.6 Portfolio Comparison and the Shared-Selector Evaluator: In the worked evaluator, terminal rewards are R(τ1,0) = 2, R(τ1,1) = −16, R(τ2,0) = 1, and R(τ2,1) = −64.These rewards implement the constant and monomial coefficients at their respective branch depths.
  • The first policy consequently has value: The first policy consequently has value V^π0_x(s0) = 0 for every x, while each πi realizes V^πi_x(sι) = −g_i(x).Thus the portfolio comparison threshold is positive exactly when the strict feasibility system has a solution.
  • The first policy consequently has value: The resulting upper-threshold language at threshold zero is the complement of an ∃R-complete problem, proving ∀R-hardness and, with membership, Theorem 24.The reduction has polynomially many states and polynomial-bit-length terminal payoffs.

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

The section establishes membership in ∀R for regret certification and in ∃∀R for minimal robust regret and bounded portfolio synthesis. The proofs encode policy values with Bellman equations and justify synthesis attainment through compactness and continuity.

  • Theorem 1 (Membership): Regret certification belongs to ∀R by encoding an explicit portfolio and universally quantified memoryless randomized policies through Bellman equations.Quantifying all such policies is sound because every realized discounted MDP has an optimal deterministic policy.
  • Theorem 5 (Membership): Minimal robust regret and bounded portfolio synthesis belong to ∃∀R by existentially quantifying k policy tables before the universal Bellman encoding.Unary-bounded k keeps the resulting formula polynomial, and the single-policy problem is the case k = 1.
  • Portfolio attainment: Synthesis formulas characterize portfolios with regret at most t because the regret infimum is attained for rational-polytope uncertainty sets.Compactness of the uncertainty set and the portfolio policy-simplex space, together with continuity, yields attainment.
  • Portfolio attainment: The portfolio-attainment lemma applies to general finite discounted RMDPs, since no acyclicity assumption is needed.It therefore covers both inputs of Problem 4 and the synthesis RMDP in Appendix J.

D Exact Transfer from Policy Comparison to Robust Regret … E.2 Rectangular Portfolio Certification

An exact lift converts policy-comparison instances into robust-regret instances while preserving key structural restrictions and making a fixed reference policy pointwise optimal. This transfer yields hardness for given-policy regret and portfolio-regret certification, including under rectangular, acyclic, and deterministic restrictions.

  • D Exact Transfer from Policy Comparison to Robust Regret: The lift routes each source choice through selector states and adds a bonus action that makes the fixed reference policy optimal at every realization.It preserves (s, a)-rectangularity, determinism for deterministic lifted policies, acyclicity, and restrictions such as two-successor and two-Dirac uncertainty.
  • D Exact Transfer from Policy Comparison to Robust Regret: For every supported policy, the lift preserves its value under discount matching, while the bonus policy is pointwise optimal in every realization.The construction uses β^2 = γ0 and gives the bonus action a unique optimum at every tag state.
  • E Proofs of Theorems 2 to 4: Transferring Comparison Bounds to Certification: The exact lift transfers Boolean and square-root-sum comparison bounds to robust-regret hardness results.The transfer applies to both singleton-candidate given-policy instances and finite portfolio comparisons.
  • E.1 Rectangular Given-Policy Hardness: Given-policy robust regret is coNP-hard and coSQRS-hard under (s, a)-rectangular uncertainty.coNP-hardness already holds with two-Dirac uncertain choices and certain uniform splitters.
  • E.1 Rectangular Given-Policy Hardness: The coNP reduction maps φ ∈ UNSAT exactly to a lifted regret yes-instance using the rational threshold Λ + 2 − 1/2^n.The source is acyclic and (s, a)-rectangular, with deterministic policies and independent two-Dirac uncertainty.
  • E.1 Rectangular Given-Policy Hardness: The coSQRS reduction preserves the comparison threshold through the identity ∆U(πu, πv) ≤ t iff Rreg(bπv) ≤ Λ + t.It uses deterministic policies and an acyclic (s, a)-rectangular construction with two-Dirac uncertain choices.
  • E.2 Rectangular Portfolio Certification: Portfolio-regret certification is ∀R-hard already for deterministic portfolios and acyclic (s, a)-rectangular RMDPs with two-successor uncertain choices.The family lift translates the zero comparison threshold into the rational regret threshold Λ without losing the theorem’s structural restrictions.

E.3 General-Polytope Regret Certification … F.2 coNP-Hardness

The paper establishes algebraic hardness for certifying fixed-policy regret under general rational polytopes, then derives combinatorial hardness for minimal robust regret through policy restriction and a lifted coNP reduction. The reductions remain hard under deterministic policies, highly restricted uncertainty, and arbitrarily small approximation slack.

  • E.3 General-Polytope Regret Certification: ∀R-completeness holds for given-policy robust regret under general rational polytopic uncertainty, even for deterministic policies.Membership is obtained from the singleton-family case of Lemma 13.
  • E.3 General-Polytope Regret Certification: The positive-part gadget makes a fixed policy’s regret equal sup p∈[0,1]^m max{γ0f(p), 0}.It adds a zero-reward initial choice between evaluating the polynomial gadget and entering a zero-reward sink.
  • E.3 General-Polytope Regret Certification: Threshold zero is tight: Rreg(π⊥) ≤ 0 exactly when ∀p ∈[0, 1]^m, f(p) ≤ 0.Regret is nonnegative, so the zero threshold directly encodes universal polynomial nonpositivity.
  • F Proof of Theorem 6: Combinatorial Minimal-Regret Hardness: Minimal robust regret is NP-hard and coNP-hard on (s, a)-rectangular RMDPs with two-Dirac uncertainty and certain uniform splitters.This theorem provides the Boolean lower bounds for minimal robust regret.
  • F.1 Policy Restriction: Policy restriction converts constrained synthesis into unrestricted synthesis by routing disallowed actions to a ruinous sink.The construction preserves the relevant uncertainty structure and transfers the restricted minimum within ε.
  • F.1 Policy Restriction: For P ∈ {ΠMR, ΠMD}, inf ρ∈P RregNε(ρ) ≥ inf π∈Pallow RregN(π) − ε.The inequality holds for arbitrary nonempty allowed action sets under the ε-restricted construction.
  • F.2 coNP-Hardness: Restricting the lifted coNP reduction to a singleton candidate family removes minimization, while the certification gap transfers verbatim.Using ε = 1/4^n and threshold Λ + 2 − 1/2^n yields the coNP-hard part of Theorem 6.

F.3 NP-Hardness · G Deterministic Minimal-Regret Complexity

The NP-hardness construction uses verifier policies whose joint acceptance characterizes falsified clauses, yielding an exponentially separated satisfiable-versus-unsatisfiable gap. This gap transfers to minimal robust regret, which is both NP-hard and coNP-hard, while the next section establishes membership and matching hardness.

  • F.3 NP-Hardness: The construction reverses the policy roles: a fixed falsification scanner seeks a falsified clause, while the synthesized valuation auditor encodes a Boolean assignment.Their shared selectors expose local literal-value tests and variable-occurrence audits.
  • F.3 NP-Hardness: The verifier RMDP has acyclic scanner and auditor policy graphs, with deterministic valuation policies following single paths at Boolean realizations.The uncertainty polytope is a product of two-Dirac segments whose vertices correspond exactly to Boolean assignments of local bits.
  • F.3 NP-Hardness: Verifier separation holds exactly when a valuation falsifies a clause: joint acceptance is possible for falsifying valuations, but acceptance events are disjoint for satisfying ones.The converse uses a canonical Boolean realization for any falsified clause.
  • F.3 NP-Hardness: 2^-n is the critical gap scale: satisfiable formulas admit a deterministic valuation policy with Gφ ≤1, whereas unsatisfiable formulas force every randomized valuation policy to Gφ ≥1 + 2^-n.The unsatisfiable-case bound follows by selecting the most probable action at each variable state, producing a valuation followed with probability at least 2^-n.
  • F.3 NP-Hardness: The reduction transfers the verifier gap to minimal robust regret by restricting lifted policies to valuation policies and fixing the reference policy to πF.The target threshold is Λ + 1 + 2^-n−1, which separates the reduced instances.
  • F.3 NP-Hardness: Minimal robust regret is both NP-hard and coNP-hard under the stated structural restrictions.The proof combines polynomial reductions from UNSAT and SAT, with rational gaps preserving a separating threshold after restriction loss.
  • G Deterministic Minimal-Regret Complexity: The deterministic minimal-regret complexity section first establishes membership and then presents a matching hardness construction.This introduces the complexity characterization following the NP-hardness transfer.

G.1 Acyclic Deterministic Membership · H Proof of Theorem 7: Signed Square-Root-Sum Hardness · H.1 One-State Balancing

The paper establishes tight complexity results for deterministic portfolio certification on acyclic RMDPs and proves algebraic hardness through one-state gadgets whose optimal mixing balances competing regret terms. The resulting constructions connect robust regret to Σp2-completeness and signed square-root expressions.

  • G.1 Acyclic Deterministic Membership: Σp2-completeness holds for minimal robust regret over memoryless deterministic policies on acyclic (s, a)-rectangular polytopic RMDPs.Membership uses existential and universal polynomial certificates, while hardness is obtained through a Boolean falsification reduction.
  • G.1 Acyclic Deterministic Membership: 2 separates the reduction’s cases: Gψ(α) ≤ 2 − 1/M when ∀y: ψ(α, y), and Gψ(α) = 2 when ∃y: ¬ψ(α, y).Here M = n + m, with the gap arising from the weighted audit and scanner events.
  • G.1 Acyclic Deterministic Membership: Hardness persists when every uncertain choice is two-Dirac and all other stochastic rows are certain uniform splitters.The reduction preserves acyclicity through an unfolding construction.
  • H Proof of Theorem 7: Signed Square-Root-Sum Hardness: The signed square-root-sum reduction encodes each square root with a one-state gadget balancing decreasing and increasing regret terms in the policy’s mixing probability.The optimum solves a quadratic equation and is generally irrational.
  • H Proof of Theorem 7: Signed Square-Root-Sum Hardness: SQRS±-hardness holds for minimal robust regret under (s, a)-rectangular uncertainty.The reduction uses the one-state balancing construction to realize signed square-root forms.
  • H.1 One-State Balancing: The one-state balancing gadget has state set {s, ⊥}, actions {L, R}, independent pL, pR ∈ [0, h] transition choices, and a zero-reward sink.It fixes q ∈ (0, 1), γ ∈ (1 − q, 1), and h = (1 − q)/γ.
  • H.1 One-State Balancing: The positive-reward parametrization realizes m+(A, B), while the negative-reward parametrization realizes m−(A, B) when q2 ≥ 1/2.A memoryless randomized policy is determined by its probability x of playing L.
  • H.1 One-State Balancing: The negative-reward construction reduces to balancing two monotone terms, yielding the quadratic (1 − q2)y2 + qDy − AB = 0 whose positive root is m−(A, B).The condition q2 ≥ 1/2 ensures the required monotonicity in the maximization argument.

H.2 Rational Square-Root Gadgets … I.1 Existential-Universal Membership

The paper develops rational square-root gadgets and an additive composition rule to encode SQRS± into robust-regret instances while preserving polynomial constructibility and (s,a)-rectangularity. It then establishes hardness results for minimal robust regret, including arbitrary rational polytopic uncertainty and an existential-universal membership argument.

  • H.2 Rational Square-Root Gadgets: For every integer b ≥2, rational positive-reward gadgets realize negative square-root coefficients in polynomial time, with positive local minimal robust regret.The construction uses rational parameters and applies for γ ∈(1 −qb, 1).
  • H.2 Rational Square-Root Gadgets: For every integer b ≥2, rational negative-reward gadgets realize positive square-root coefficients in polynomial time, with positive local minimal robust regret.The parameters satisfy D2 −c2 = b and have polynomial binary length.
  • H.3 Additive Composition: An additive splitter scales disjoint gadgets and enters each uniformly, producing a product-uncertainty RMDP whose minimal robust regret is the sum of local minima.The construction preserves (s,a)-rectangularity and excludes additional ruinous minimizers or comparators.
  • H.4 Proof of Theorem 7: Theorem 7 reduces the non-strict ≤ direction of SQRS± to a rational-threshold (s,a)-rectangular RMDP by combining positive- and negative-coefficient gadgets.Unit roots contribute a rational offset, while non-unit roots are composed with a common discount factor.
  • H.4 Proof of Theorem 7: The reduction’s uncertainty set is a product of local choice uncertainty sets, so it preserves (s,a)-rectangularity.This follows from composing independent local gadgets through the additive splitter.
  • I Proof of Theorem 8: General-Polytope Minimal-Regret Hardness: Single-policy minimal robust regret is ∀R-hard for arbitrary rational polytopic uncertainty.The proof uses an existential-universal upper bound and two-action anchoring to obtain a strictly monotone minimal-regret objective.
  • I.1 Existential-Universal Membership: The membership claim is established using the certification counterpart developed in Appendix C.This supplies the existential-universal membership argument associated with the single-policy result.

I.2 Two-Action Anchoring

The two-action anchoring RMDP reduces a comparison instance to choosing between two anchored initial actions, with sufficiently large anchors and a ruinous sink enforcing prescribed continuations. Its robust regret is an explicit max of two affine losses, enabling a balanced threshold and the hardness reduction.

  • Construction: The construction uses two forced copies of M, shared realization coordinates, fresh initial-action coordinates, absorbing anchors ±Z, and a ruinous sink of value −Zr.The initial state offers actions α and β, while each copy follows the corresponding prescribed policy.
  • Anchored regret: Choosing α with probability x yields robust regret max{(1 − x)D, xE}, where D = L + γ∆ and E = 2γZ − L are positive.The positivity follows from the anchor choice and the bound on the comparison gap.
  • Policy reduction: Every stationary policy can be replaced by a compliant projection with no lower value, reducing the optimization to the single initial probability x.The projection leaves only the prescribed action in each copied state, so the relevant policies are exactly α/β mixtures followed by the prescribed continuation.
  • Irrational comparison gaps: The balanced threshold is rational even when the source comparison gap is irrational: with γ = 1/2, ∆= 7 −4, the example gives t′ = 24/11.The same example reports L = 3, Z = 11, D = 13/2 −2, E = 8, and T = 3.
  • Hardness reduction: The anchoring equivalence provides a reduction from Theorem 20’s ∀R-hard comparison problem.This establishes the role of the construction in the hardness proof.

J Proof of Theorem 9: Bounded Portfolio Synthesis … K.5 Datacenter benchmark

The paper proves bounded portfolio synthesis hard through a polynomial reduction whose RMDP satisfies strict structural restrictions, then evaluates an approximate offline portfolio pipeline on parametric benchmarks using sampled regret and online bandit selection.

  • J Proof of Theorem 9: Bounded Portfolio Synthesis: The reduction maps existential and universal quantifiers to portfolio synthesis and nature, resolving fixed rewards, stationary continuations, and shared witnesses through policy-affine tests.The source construction normalizes the matrix into tests affine in the existential witness.
  • J.1 Existential-Universal Membership: Membership is established for the existential-universal encoding, while hardness follows from the equivalence ρr ≤2 ⇔ ∃x ∀y: F(x, y) ≥0.The reduction is polynomial and satisfies the stated restrictions.
  • J.3 Exact Evaluators: The evaluator realizes policy-affine polynomial scores using coordinate states with one predecessor, so each stationary policy coordinate has a single interpretation.The construction uses certain uniform splitters and fixed on/off continuations, avoiding context-dependent behavior.
  • J.4 Roles, Cases, and Scores: Mixed role scores have polynomially many monomials, with degrees at most three for the first polynomial and one for the second, enabling exact evaluation.The cases are folded into polynomial coefficients rather than represented as model branches.
  • J.5 The Synthesis RMDP: The synthesis RMDP uses a nonempty rational-polytope uncertainty set with two-successor uncertain rows; nonrectangularity comes only from tying equalities and the simplex constraint.The constraint description has polynomial encoding length and coefficients 0 or ±1.
  • J.6 Action Values and the Optimal-Value Bound: The optimal initial value is at most 2, with equality at pure cases, and pure-case coverage is equivalent to mixed-score coverage over all nature distributions.The correction bound for combining cases is tight.
  • J.7 Correctness: Regret at most 2 forces exactly r role members, makes their encoded vectors equal, and yields the source sentence through the evaluation cases.The forward direction constructs a portfolio with regret at most 2, while the reverse direction uses role forcing and equality cases.

K.6 UAV benchmark

The UAV benchmark models flight through a cluttered 3D grid with wind drift and actuator-failure hazards, using a procedural obstacle layout and parameterized transitions. Its seven-action-per-cell design yields a policy family too large for exhaustive search even at the smallest size.

  • Environment: The benchmark models a UAV flying from a fixed start to a landing pad through a cluttered three-dimensional grid with wind drift and actuator-failure risk.The start state is s0 = (0, ⌊Ly/2⌋, 1), with Crash, Goal, and terminal done states completing the state space.
  • Action space: Each grid cell offers seven actions: six unit moves along ±x, ±y, and ±z, plus a no-op.Goal has a forced collect action, while Crash and done self-loop.
  • Parameter space: Two unknown parameters govern opposite route penalties: wind intensity p causes lateral drift, while actuator-drop probability q causes altitude loss.The parameter domain is θ = (p, q) ∈ [0, pmax] × [0, qmax], with pmax + qmax < 1.
  • Transitions: Transitions share three branches with probabilities 1 − p − q, p, and q for the intended move, lateral drift, and altitude drop, respectively.Branches are clamped to grid bounds and redirected to Crash, Goal, or the resulting grid state according to the procedural map.
  • Scalability: Every cell’s seven actions induce 7|S|−3 memoryless deterministic policies, making exhaustive policy search infeasible even for uav-small.The generator supports free grid extents subject to Lx ≥ 8, Lz ≥ 3, and odd Ly ≥ 5.

L Experimental data

The experiments evaluate portfolio regret and online selection across portfolio sizes and benchmarks. Results show that larger portfolios make exact member selection harder, while recommendation mistakes generally incur small value losses.

  • Online selection results (RQ2): Online evaluation reports correct-arm rate and normalized shortfall across pooled runs for all tested portfolio sizes and four benchmarks.The correct-arm rate is the fraction of runs selecting the best member at the hidden valuation, while normalized shortfall ranges from 0 for the best member to 1 for the worst.
  • Online selection results (RQ2): As portfolio size K grows, the correct-arm rate visibly declines, whereas normalized shortfall remains low throughout.The reported interpretation is that larger portfolios create more near-ties, but confused members are close in value, so selection errors have small costs.
  • Regret results (RQ1): Table 5 reports max-regret and inertia for each portfolio size, benchmark, and clustering seed, with averages computed across three seeds.Max-regret is the largest sampled portfolio regret; inertia is the K-means within-cluster sum of squared distances, not a regret measure.
  • Portfolio synthesis and evaluation protocol: The protocol discretizes the domain, constructs and robustly evaluates candidate policies, then reduces and clusters them into portfolios for each budget and seed.It subsequently evaluates empirical robust regret, runs UCB-based deployment, pools samples across seeds, and generates the report.
Loading 2608.17929v1…