Adaptive Policy Portfolios for Robust Markov Decision Processes

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

cs.AIAug 18, 2026

Adaptive Policy Portfolios for Robust Markov Decision Processes

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

Organizations: University of Antwerp, Belgium · Radboud University, Nijmegen, The Netherlands

Abstract

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

Figures & tables

Figure 1: Portfolio regret in the actuator example.

Task	Nonrect. uncertainty	$(s,a)$ -rectangular uncertainty	Hardness already holds for
Certify one given policy	$\forall\mathbb{R}$ -complete	$\mathsf{coNP}$ -hard and $\mathsf{coSQRS}$ -hard; in $\forall\mathbb{R}$	deterministic policies; acyclic models whose uncertain choices are two-Dirac, for $\mathsf{coNP}$
Certify a given portfolio	$\forall\mathbb{R}$ -complete	$\forall\mathbb{R}$ -complete	deterministic portfolios with acyclic graphs and two-successor choices
Synthesize one randomized policy	$\forall\mathbb{R}$ -hard and in $\exists\forall\mathbb{R}$	$\mathsf{NP}$ -hard, $\mathsf{coNP}$ -hard, and $\mathsf{SQRS}_{\pm}$ -hard; in $\exists\forall\mathbb{R}$	two-Dirac models for the Boolean bounds
Synthesize at most $k$ policies	$\exists\forall\mathbb{R}$ -complete	hard already for $k=1$ ; exact complexity open	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 , 2 , 4 and 3 . Synthesis is established by Theorems 5 , 6 , 7 , 8 and 9 .

$K$	UAV-S (98)	UAV-M (358)	UAV-L (1813)	datacenter (330)
1	0.053	0.091	0.126	14.28
2	0.032	0.019	0.017	3.86
3	0.018	0.010	0.016	2.82
5	0.002	0.003	0.015	2.79
7	0.002	0.003	0.008	1.79
10	0.002	0.003	0.003	0.80

Table 2: Empirical robust regret, averaged over three seeds. Parentheses give the number of states. Bottom row indicates wall-clock time.

Panel of Figure 2 — Figure 2: Reported UCB deployment results on the datacenter across all tested values of $K$ .

Appendix figures & tables16 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 3 — Figure 3: The shared fragment for a positive occurrence $o=(i,j)$ and the audit branch $X_{x}=1$ . The clause scan tests the pair $(b_{o,1},b_{o,0})$ , whereas this audit branch needs only $b_{o,1}$ . The branch $X_{x}=0$ analogously audits $q_{o,0}$ . Selector arrows are uncertain; arrows from outcome states are the certain, role-specific actions of the two policies.

Panel of Figure 4 — Figure 4: The shared-cycle gadget realizing one normalized square-root term.

Panel of Figure 5 — Figure 5: One branch of the polynomial-evaluation RMDP. Equalities in $\mathcal{U}$ tie repeated parameter occurrences across branches.

Panel of Figure 6 — 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 .

Panel of Figure 7 — Figure 7: The source and its lifted RMDP in Example 3 .

Panel of Figure 8 — 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.

Panel of Figure 9 — Figure 9: The verifier RMDP of Definition 13 for $\varphi=(x_{1}\vee\lnot x_{2}\vee x_{3})\wedge(\lnot x_{1}\vee x_{2}\vee x_{3})$ , showing the four state groups. For each literal of $C_{1}$ , 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 $C_{1}$ . The auditor policy $K_{\alpha}$ walks $v_{x_{1}},v_{x_{2}},v_{x_{3}}$ and, having assigned a value to each variable, checks its occurrences. Dotted edges summarize audit reads of the shared selectors: the scanner and the auditor of $x_{1}=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.

Panel of Figure 10 — Figure 10: The one-state balancing gadget has independent choices $p_{L},p_{R}\in[0,h]$ and a zero-reward sink.

Panel of Figure 11 — Figure 11: Additive splitter for minimal regret.

Panel of Figure 12 — Figure 12: The two-action anchoring RMDP. The two copies share the realization $p$ , whereas $\lambda_{\alpha}$ and $\lambda_{\beta}$ are fresh coordinates.

Panel of Figure 13 — Figure 13: The synthesis RMDP and its evaluator components. The only policy choices are at $s_{\iota}$ and the coordinate states; every reward shown is a fixed rational.

Action	$p_{c}/2$	$(1-p_{c})/2$	$p_{e}/2$	$(1-p_{e})/2$
cool-high	$(T^{-},H,L)$	$(T^{+},H,L)$	$(T,H,L^{-})$	$(T,H^{+},L^{+})$
cool-low	$(T^{-},H,L)$	$(T,H,L)$	$(T,H,L^{-})$	$(T^{+},H,L^{+})$
hold	$(T,H,L)$	$(T^{+},H,L)$	$(T,H^{-},L^{-})$	$(T^{+},H^{+},L^{+})$
heat	$(T^{+},H,L)$	$(T^{-},H,L)$	$(T,H,L^{-})$	$(T^{+},H^{+},L^{+})$
dehumidify	$(T,H^{-},L)$	$(T,H^{+},L)$	$(T^{-},H,L^{-})$	$(T^{+},H^{+},L^{+})$

Appendix

Table 3: Successor state reached by each of the four branches of

\mathbb{P}_{\theta}(\cdot\mid s,a)

, for

s=(T,H,L)

, in the datacenter benchmark.

Name	$(L_{x},L_{y},L_{z})$	$\lvert\mathcal{S}\rvert$
uav-small	$(8,5,3)$	98
uav-medium	$(12,9,4)$	358
uav-large	$(24,15,6)$	1,813

Appendix

Table 4: Sizes of the uav benchmark family used in the experiments.

		uav-small		uav-medium		uav-large		data-center-climate
		$\|S\|=98$		$\|S\|=358$		$\|S\|=1813$		$\|S\|=330$
		${V_{\mathrm{max}}}=100$		${V_{\mathrm{max}}}=100$		${V_{\mathrm{max}}}=100$		${V_{\mathrm{max}}}=2080$
K	seed	max-regret	inertia	max-regret	inertia	max-regret	inertia	max-regret	inertia
1	0	0.053	23.239	0.091	42.668	0.125	59.498	14.649	1313595.187
1	1	0.053	23.239	0.091	42.668	0.124	59.498	13.404	1313595.187
1	2	0.053	23.239	0.091	42.668	0.129	59.498	14.771	1313595.187

Appendix

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.

Panel of Figure 14 — 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.

Panel of Figure 15 — 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.

Robust Markov Decision Processes

Robust Markov decision processes optimize decisions under uncertain dynamics, seeking reliable performance against adverse transition models.

See all 27 papers

Optimizing Minimax Regret in Uncertain MDPs with Small Sets of Policies
Aug 3, 2026Sterre Lutz, Daniël Vos, Matthijs T. J. Spaan +1Markov Decision Processes Branch and Bound
Delft University of Technology
Quantitative Analysis of $ω$ -Regular Robust MDPs
Aug 26, 2026Ali Asadi, Krishnendu Chatterjee, Ehsan Kafshdar Goharshady +3Robust Markov Decision Processes Sequential Decision Making
Institute of Science and Technology Austria
Linear Programming Representations and Strongly Polynomial Algorithms for Robust Markov Decision Processes
Oct 1, 2026Han Zhong, Yinyu YeRobust Markov Decision Processes Markov Decision Processes
Shanghai Jiao Tong University · Shanghai Jiao Tong University, SIMIS, and Stanford University

Aug 3, 2026J/K move · Enter open · S save

Optimizing Minimax Regret in Uncertain MDPs with Small Sets of Policies

Sterre Lutz, Daniël Vos, Matthijs T. J. Spaan, Anna Lukina

Delft University of Technology

Markov Decision Processes Branch and Bound Minimax Regret Policy Optimization Combinatorial Optimization Decision-Making under Uncertainty

Open paper AskPDF arXiv

Sequential decision-making in real-world applications often involves uncertainty about the environment's model. Uncertain Markov decision processes (UMDPs) represent the possible environments as a set of MDPs with shared states and actions but potentially different transition probabilities and rewards. Optimizing a single policy across all possible MDPs may sacrifice performance, while preparing an individually optimized policy for every MDP may violate operational, regulatory, or interpretability constraints on the number of policies that can be prepared and deployed. We consider settings in which model uncertainty is resolved shortly before execution, allowing the most suitable policy to be selected from a limited set prepared in advance. We introduce

k

-adaptable policy synthesis, which optimizes such a set of

k

policies under a minimax-regret objective. We prove that the problem is NP-hard and develop KAPS, an exact nested branch-and-bound algorithm with problem-specific bounds and heuristics. KAPS jointly optimizes which MDPs share a policy and the policies themselves. Experiments across various UMDP benchmarks show that the largest reduction in regret consistently occurs when increasing from one to two policies. In the single-policy setting, KAPS is competitive with existing methods in solution quality and proves optimality substantially more often.

Abstract

Robust Markov Decision Processes

Explore similar work

Optimizing Minimax Regret in Uncertain MDPs with Small Sets of Policies

Quantitative Analysis of ωωω-Regular Robust MDPs

Linear Programming Representations and Strongly Polynomial Algorithms for Robust Markov Decision Processes

Quantitative Analysis of $ω$ -Regular Robust MDPs