Optimizing Minimax Regret in Uncertain MDPs with Small Sets of Policies

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 {s.lutz, d.a.vos, m.t.j.spaan, a.lukina}@tudelft.nl

arXiv:2608.02509v1 [cs.AI] 3 Aug 2026

Abstract 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 NPhard 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.

1

Introduction

Sequential decision-making often takes place under uncertainty about how an environment will behave. A decision maker must choose a strategy of consecutive actions—a policy—whose consequences depend on stochastic transitions and rewards. In many applications, there is an additional layer of model uncertainty: several probabilistic models of the environment are considered plausible, but it is initially unknown which model describes the true environment for the policy to be executed. Markov decision processes (MDPs) are a standard modeling formalism for sequential decision-making under uncertainty (Puterman 2014). An MDP consists of states connected by stochastic transitions: an agent selects an action, after which the environment samples the next state according to a probability distribution conditioned on the current state and action. The agent receives rewards and seeks a policy that maps states to actions and maximizes the expected cumulative discounted reward. In comparison, an uncertain MDP (UMDP) can represent the additional layer of the en-

Uncertain MDP

? ? ? ? ? ?

Design time ? ?

6 possible MDPs !

!

!

! !

1

2 !

? ?

Deployment time True MDP realizes

? ?

Prepare 2 policies

? ? 1

!

2

? ? ? ?

Choose from 2 policies

Figure 1: A k-adaptable policy for k = 2. The uncertain MDP induces a set of possible MDPs (here "?" marks a possible obstacle location, "!" the true one; in general, the set varies in transition probabilities and rewards). At design time, two policies are prepared. Shortly before deployment, the realized environment is identified and the best-suited prepared policy is selected. A single policy may need to compromise between environments, whereas preparing one policy for every environment may be operationally infeasible. vironment’s model uncertainty by specifying a finite set of candidate MDPs, each describing a possible environment realization (Xu and Mannor 2009). We consider settings in which the model uncertainty is resolved shortly before deployment. Once identified, the realized environment could be handled by an optimal policy. In practice, however, policies may need to be designed, communicated, validated, or approved well in advance. Operational, regulatory, and interpretability constraints can therefore limit the number of distinct policies that can be prepared. The challenge is to prepare a small number of policies to select from, after uncertainty resolves. Example 1 motivates our setting based on one of the benchmark problems we considered. Example 1 (Disaster Rescue). A rescue team may prepare for several possible layouts of an area affected by a natural disaster, differing in which routes are blocked or which regions are difficult to traverse. An on-site assessment reveals the relevant details before the team begins its mission. Preparing one strategy per layout may be infeasible because instructions must be communicated, responders trained, and protocols validated or approved. The objective is a small

policy set that performs well across all layouts. Figure 1 illustrates this setting. Similar restrictions arise in healthcare, where each treatment protocol for different patient types may require clinical validation, and in maintenance scheduling, where deploying a policy can require investments or operational preparations to be made in advance. More generally, the objective arises in any application where model uncertainty resolves at deployment time, but preparing policies is costly. Robust MDP policy synthesis generally assumes a conceptually different problem setting: model uncertainty does not resolve at deployment, and rather one policy is constructed for the whole UMDP (Iyengar 2005; El Ghaoui and Nilim 2005). It has recently seen many efficient approaches (Wolff, Topcu, and Murray 2012; Abate et al. 2026; Meggendorfer, Weininger, and Wienhöft 2025; Schnitzer, Abate, and Parker 2026). These methods have primarily adopted a maximin-value objective, computing a single policy that maximizes performance against the worst-case MDP in the set. Minimax-regret approaches (Ahmed et al. 2013, 2017; Rigter, Lacerda, and Hawes 2021) instead measure a policy’s loss relative to the environment-specific optimum, yielding less conservative solutions (Regan and Boutilier 2011; Xu and Mannor 2009). In contrast, we formulate k-adaptable problem setting, in which the model uncertainty resolves shortly before deployment, and extend the minimax-regret optimization to the k-adaptable policy synthesis, which prepares k policies for selection. This gap between single and one-per-model solutions has been studied outside the MDP setting: work on finite adaptability and k-adaptability in robust optimization (Bertsimas and Caramanis 2010; Malaguti, Monaci, and Pruente 2022) shows that committing to a small fixed set of k solutions before the uncertainty is resolved can close most of the gap to full adaptability at a fraction of the complexity. To our knowledge, no existing approach brings this idea to the general UMDP setting. In this paper, we introduce the problem of k-adaptable minimax-regret policy synthesis for UMDPs, prove that it is NP-hard, and propose KAPS, a specialized exact branchand-bound algorithm for solving it. KAPS jointly searches for a partition of the UMDP’s underlying MDPs and one shared policy per subset, minimizing worst-case regret after the realized MDP is revealed. Problem-specific bounds and heuristics substantially reduce the resulting search space. In the single-policy setting (k = 1), KAPS consistently outperforms state-of-the-art UMDP planning approaches based on approximate dynamic programming (Rigter, Lacerda, and Hawes 2021) and mixed-integer linear programming (Ahmed et al. 2013). In the k > 1 setting, across all benchmarks, most of the benefit is obtained from the first few policies: increasing from one to two policies yields the largest reduction in regret, often reducing it to near zero. This shows that even a small amount of adaptability can capture much of the value of tailoring a policy to the realized MDP. In summary, our contributions are: (i) a formal definition of the k-adaptable minimax-regret policy synthesis problem and a proof of its NP-hardness; (ii) the first exact algorithm to solve it; and (iii) an experimental evaluation on a range of

UMDP benchmarks.

2

Related Work

Although our work relates to several approaches to decisionmaking under model uncertainty, none directly applies to our problem setting. We discuss the key differences below. Minimax Regret in Uncertain MDPs Prior work on minimax regret in UMDPs focuses on synthesizing a single policy. Ahmed et al. (2013, 2017) propose an exact MILP formulation and scalable approximations, including Cumulative Expected Myopic Regret (CEMR). For stochastic-shortest-path UMDPs, Rigter, Lacerda, and Hawes (2021) develop minimax value iteration and n-step approximations for dependent uncertainty; we refer to its three-step variant as cumulative regret (CREG) in the experimental evaluation. These methods provide relevant comparisons for single-policy synthesis, but do not address the synthesis of multiple policies. Finite Adaptability and Min–Max–Min Optimization Outside the MDP setting, finite adaptability restricts fully adaptive robust optimization to finitely many contingency plans (Bertsimas and Caramanis 2010). In two-stage kadaptability, k candidate recourse decisions are prepared together with a common first-stage decision (Hanasusanto, Kuhn, and Wiesemann 2015; Subramanyam, Gounaris, and Wiesemann 2020). Unlike our setting, this commits to a partial solution shared by all candidates. More directly related formulations prepare k complete solutions and select one after uncertainty is revealed, optimizing either worst-case cost (Buchheim and Kurtz 2017) or expected cost (Malaguti, Monaci, and Pruente 2022). None of the discussed approaches address the synthesis of policies for UMDPs. Policy Synthesis for Sets of MDPs Andriushchenko et al. (2025a) construct policy trees that partition a set of MDPs (which they call a family) and assign each subset a common policy satisfying a reachability threshold, while identifying MDPs for which no such policy exists. Their abstractionguided divide-and-conquer method recursively splits the MDPs without a prescribed limit on the resulting number of policies; compactness is promoted through splitting heuristics and post-processing rather than optimized exactly. In contrast, we prescribe the number k of policies and search over alternative size-k partitions to minimize worst-case regret over all MDPs. Adaptive Policies During Execution Related work also considers settings in which the realized MDP is initially hidden and policies adapt during execution as observations reveal information about the true MDP. This includes memoryful or belief-based policies for UMDPs (Sharma et al. 2019) and multiple-environment MDPs (Raskin and Sankur 2014; Bordais and Raskin 2026). In contrast, we assume that the realized MDP is identified before execution and select one of k stationary memoryless policies. This keeps k interpretable as a bound on the number of prepared state-dependent decision rules, rather than allowing a single policy to identify the MDP online and subsequently specialize its behavior further. Luque-Cerpa et al. (2026) instead take an existing ensemble

of controllers and learn a contextual runtime monitor that continuously observes the operating context and selects a controller subject to safety requirements. We jointly synthesize the candidate policies to be selected from after uncertainty is resolved, rather than learning a runtime selector for a given set of policies.

Problem 1 (k-Adaptable Policy Synthesis). Given a UMDP M and an integer k > 0, find a set of deterministic, memoryless policies {π1 , . . . , πk } that minimizes worst-case regret relative to the optimal value: arg min max

min

π1 ,...,πk M ∈M i∈{1,...,k}

3

Preliminaries

We introduce the definitions needed to compare a policy across multiple possible MDPs. In particular, we define uncertain MDPs and evaluate policies by their worst-case loss relative to the optimal policy for the realized MDP. Markov Decision Processes (MDPs) A (discounted) Markov decision process is a tuple M = (S, A, T, R, γ, µ), where S is a finite set of states, A is a finite set of actions, T ( · | s, a) ∈ ∆(S) is the transition distribution for (s, a), R : S ×A×S → R is a reward function, the scalar γ ∈ (0, 1) is the discount factor, and µ ∈ ∆(S) the initial distribution. Policies A deterministic, memoryless policy is a function π : S → A that selects an action based only on the current state. Its value in M is defined P∞ as the expected discounted return V (M, π) = EM,π [ t=0 γ t R(st , π(st ), st+1 )] , where s0 ∼ µ and st+1 ∼ T (· | st , π(st )). The optimal value of M is denoted by V ⋆ (M ) and a policy achieving it by π ⋆ . Uncertain MDPs An uncertain MDP (UMDP) M = {M1 , . . . , Mn } is a finite set of MDPs sharing the state space S, action space A, and discount factor γ. The MDPs may differ in their transition kernels Ti , reward functions Ri , and initial state distributions µi . Each Mi ∈ M represents one possible realization of the environment. Regret An optimal policy for one MDP may perform poorly for another. For an MDP M , the regret of using policy π is the loss in value from the optimal policy for that MDP: reg(M, π) := V ⋆ (M ) − V (M, π). The regret of π on a UMDP M is the worst-case regret across its MDPs. The minimum such worst-case regret is called minimax regret, and a policy that achieves it a minimax-regret policy π reg ∈ arg min max (V ⋆ (M ) − V (M, π)). π

M ∈M

(1)

In this paper, we restrict all synthesized policies to be deterministic and memoryless. We motivate this modeling choice in Section 4.

4

k-Adaptable Policy Synthesis

We consider settings where the realized MDP is unknown during synthesis but revealed before execution. The decision maker can therefore prepare multiple policies in advance and select one after the uncertainty has resolved. At the extreme, this means one could prepare a dedicated policy for each scenario. While this achieves optimal performance in every scenario, a large policy set may be impractical: each policy may need to be validated or approved, its possible behavior communicated to affected users, or its execution practiced by human operators. We therefore ask: how do we minimize worst-case regret with only k prepared policies? We formalize this as follows.

(V ⋆ (M ) − V (M, πi )) . (2)

We restrict the candidate policies to be deterministic and memoryless. The memoryless restriction is central to the intended meaning of k: a history-dependent policy could use observed transitions to infer which MDP is active and subsequently branch into MDP-specific behavior, effectively encoding multiple policies in a single candidate. The determinism restriction is primarily computational. It yields a finite policy space that can be searched exactly by KAPS, aligns our setting with much of the existing UMDP policy-synthesis literature, and appears mild on our benchmarks, where deterministic policy sets already attain very low, and often zero, regret. Randomized policies may nevertheless improve performance on other instances, and extending KAPS to them remains future work. Complexity Whereas a single discounted MDP can be solved in polynomial time, k-adaptable policy synthesis is NP-hard even for k = 1 (proof in supplementary material). Theorem 1 (NP-hardness). Solving k-adaptable policy synthesis (Problem 1) is NP-hard, even for k = 1. Proof sketch. We reduce 3-SAT to Problem 1 by constructing a UMDP that admits a zero-regret policy if and only if the given formula is satisfiable. Thus, the computational difficulty does not arise only from assigning MDPs to multiple policies: even finding a single policy that minimizes worst-case regret across multiple MDPs is hard. This motivates the problem-specific exact search we describe in Section 5.

5

Algorithm for k-Adaptable Policy Synthesis

In this section, we introduce KAPS, an exact algorithm for k-adaptable policy synthesis. KAPS relies on a partitionbased formulation that jointly determines which MDPs share a policy and synthesizes one minimax-regret policy for each resulting subset. We first show that solving this formulation yields an optimal solution to k-adaptable policy synthesis. We then describe the nested branch-and-bound searches used by KAPS, followed by the problem-specific bounds and heuristics, and establish the correctness of the algorithm.

5.1

Partition-Based Formulation

To solve Problem 1 exactly, we propose KAPS. As in kadaptability approaches in optimization, assigning realizations to k prepared solutions induces a partition of the uncertainty set (Bertsimas and Caramanis 2010). Here, each subset in such a partition contains the MDPs selecting the same policy. These MDPs together form a smaller UMDP whose policy must be synthesized jointly.

This representation makes explicit the two coupled choices in Problem 1: which MDPs share a policy and what policy is synthesized for each resulting UMDP. KAPS searches jointly for a partition of the UMDP and a minimax-regret policy for every smaller UMDP in that partition. Problem 2 (k-Partition Synthesis). Given UMDP M and integer k > 0, find partition P = {M1 , . . . , Mk } with Sk reg reg i=1 Mi = M, and minimax-regret π1 , . . . , πk , s.t. arg min max P

max (V ⋆ (M ) − V (M, πireg )) .

i∈1,...,k M ∈Mi

(3)

Solving k-partition synthesis directly solves k-adaptable policy synthesis. The minimax-regret policies associated with the solution to Problem 2, form an optimal set of prepared policies for Problem 1. Proposition 1 (Optimality Equivalence). The optimal value obtained by solving Problem 2 equals the optimal value obtained by solving Problem 1. Proof sketch. Any partition yields a set of k policies for Problem 1 with the same or lower regret. Conversely, any k policies induce a partition by assigning each MDP to its best policy; replacing each policy by a minimax-regret policy for its subset cannot increase regret. Hence the optimal values coincide. A full proof is provided in the supplementary material.

5.2

Nested Branch-and-Bound

KAPS performs k-partition synthesis (and consequently, Problem 1) through two nested Branch-and-Bound (BnB) searches. BnB is a search strategy that recursively divides a solution space into smaller parts, creating a search tree in which each node represents a set of candidate solutions. Problem specific insights are used to lower bound all solutions represented by a node, permitting pruning of its children when the bound cannot improve the incumbent, the best solution found so far. Otherwise, the search continues until a leaf is reached, where the node represents a single solution that can be evaluated exactly. KAPS nests two such searches to jointly optimize the partition and its policies. The outer BnB searches over partitions of the MDPs. Each search node represents all partitions completing some partial partition, in which some MDPs have already been assigned to subsets and the remaining MDPs are still unassigned. Branching assigns one additional unassigned MDP to a subset until a complete partition is obtained. Evaluating the regret of a partition solution requires synthesizing a minimax-regret policy for the UMDPs it contains. This is performed by the inner BnB. Each search node represents a set of deterministic memoryless policies through restrictions on the actions available in each state. Branching iteratively restricts these actions until only a single policy remains. The inner search therefore determines the policies that are used for the UMDPs in the partition determined by the outer search. When k = 1, the partition is fixed and only the inner search is required.

Algorithm 1 KAPS Input UMDP M and policy-set size k Output Partition Pbest , policies Πbest , and regret regbest 1: N0 ← ((∅, . . . , ∅), M) 2: Initialize queue Q with N0 3: (Pbest , Πbest , regbest ) ← GuessPartition(M, k) 4: while Q is not empty and L < regbest do 5: N = (PN , Mremaining ) ← NextPartition(Q) 6: if Mremaining = ∅ then 7: for all Mi ∈ PN do 8: (πi , regi ) ← PolicySearch(Mi , regbest ) ▷ see Alg. 2 9: regN ← maxi regi , ΠN ← {πi }ki=1 10: if regN < regbest then 11: (Pbest , Πbest , regbest ) ← (PN , ΠN , regN ) 12: else if BoundPartition(N ) < regbest then 13: M ← BranchPartition(N ) 14: Q ← Q ∪ {PN with M added to Mi }ki=1 15: L ← minN ′ ∈Q BoundPartition(N ′ ) 16: return (Pbest , Πbest , regbest )

5.3

Problem-Specific Reasoning and Heuristics

Both search spaces  in the nested BnB are combinatorial: a UMDP M has |M| possible k-partitions (Stirling number k of the second kind), and there are |A||S| deterministic memoryless policies. Unguided exploration of the search space is therefore infeasible even for moderate instances. To reduce the search effort, both BnB procedures use problem-specific reasoning and heuristics. Their overall structure is shown in Alg. 1 and 2. We introduce four key problem-specific components in both layers of the BnB: (1) a bounding rule that lower-bounds the best solution represented by a search node; (2) a branching heuristic that determines how a node is divided into children; (3) an incumbent heuristic that constructs promising complete solutions early; and (4) a node-ordering heuristic that determines the order in which nodes are explored. BoundPartition For each subset in a partial partition, we first check whether any subset of that subset is in the cache, and take the largest available policy-search lower bound. Then, to strengthen the bound, we perform policy search for each partial partition subset and each pair of MDPs within the subset for a short duration. We again take the maximum of their lower bounds as a bound for the partition. Validity follows from monotonicity: adding MDPs to a UMDP cannot reduce minimax regret. BranchPartition To branch partitions efficiently, we aim to create partial partitions containing conflicting MDPs, i.e., MDPs that do not admit good policies when grouped together in a partition. This is useful, since it allows for quick pruning of the search space. We determine a conflict order once before the search, by performing GuessPolicy for each pair of MDPs, and sorting the MDPs by their worst pair’s regret value in decreasing order. During the search, we select

Algorithm 2 Subprocedure PolicySearch Input Subset M′ ⊆ M and regret cutoff regcutoff Output Policy πbest and value U , where πbest = ⊥ if no policy has regret below regcutoff 1: Let N0 allow every action in every non-terminal state 2: Initialize queue Q with N0 3: πbest ← ⊥, U ← regcutoff , and L ← 0 4: while Q is not empty and L < U do 5: N ← NextPolicy(Q) 6: if N represents a complete policy π then 7: if maxM ∈M′ reg(M, π) < U then 8: πbest ← π, U ← maxM ∈M′ reg(M, π) 9: else if BoundPolicy(N ) < U then 10: π ← GuessPolicy(N ) 11: if maxM ∈M′ reg(M, π) < U then 12: πbest ← π, U ← maxM ∈M′ reg(M, π) 13: (s, a) ← BranchPolicy(N ) 14: Q ← Q ∪ {N + force(s, a), N + forbid(s, a)} 15: L ← minN ′ ∈Q BoundPolicy(N ′ ) 16: return (πbest , U ) the next MDP to branch on in conflict order and create a branch for each subset to which this MDP is added. GuessPartition Starting with all MDPs arbitrarily distributed across the subsets, we repeatedly move a single MDP between subsets whenever this improves the partition regret estimate using GuessPolicy. Ties are broken in favor of more evenly sized subsets. Once no improving move remains, we evaluate the resulting partition using GuessPolicy or PolicySearch (Alg. 2) and use it as the initial incumbent. NextPartition Each search node is represented by a partial partition and is stored in the queue Q. We select the next node to expand as the one with the lowest (lower) bound. BoundPolicy We solve each M ∈ M′ through policy iteration under search node N ’s action restrictions, finding the optimal value VN⋆ (M ). The highest regret relative to
the unrestricted optimum, maxM ∈M′ V ⋆ (M ) − VN⋆ (M ) , lower bounds the regret of any policy represented by N . GuessPolicy We construct an average MDP like in (Rigter, Lacerda, and Hawes 2021) by averaging the transition kernels Ti , reward functions Ri , and initial-state distributions µi over all Mi ∈ M′ . The optimal policy of this average MDP is suggested as a candidate policy. BranchPolicy We also use the policy proposed by GuessPolicy to guide branching. Among the states whose actions are not yet fixed, we select the state with the highest occupancy under this policy and branch on the action chosen there. One child fixes this action, while the other excludes it. NextPolicy We select the next node with equal probability from two orderings: the node with the smallest upper bound, to prioritize promising candidate policies, or the node with the smallest lower bound, to prioritize regions that may still contain a low-regret policy.

5.4

Correctness

When run without a time limit, KAPS is guaranteed to have considered all possible partitions and corresponding policies and thus returns an optimal solution to Problem 1. Theorem 2 (Correctness of KAPS). KAPS terminates and returns an optimal solution to Problem 1. Proof outline. KAPS terminates because both search trees are finite. Branching fully covers the solution space represented by each parent node. Both bounding rules are valid for the entire subtree rooted at a node: the BoundPolicy optimizes each MDP independently under the node restrictions, which is optimistic relative to requiring a fully shared policy, while BoundPartition uses smaller subsets of MDPs, which is optimistic compared to the level of uncertainty of the full subsets. Hence, pruning discards only nodes that cannot improve the incumbent. Since all unpruned leaves are evaluated exactly, the final incumbent is optimal.

6

Experiments

We evaluate both the practical value of k-adaptable policy synthesis and the effectiveness of KAPS in solving it. Our experiments on a range of UMDP instances support the following conclusions: C1. KAPS outperforms existing methods on single-policy minimax-regret synthesis, particularly in optimality. C2. A small policy set can capture much of the benefit of full adaptation, providing a favorable tradeoff between policy-set size and worst-case regret. C3. KAPS scales to instances with larger MDPs and greater numbers of MDPs in the UMDP. C4. Each problem-specific component introduced in Section 5 contributes to the efficiency of KAPS. Our open-source1 Python implementation of KAPS and all the baseline methods were run on a laptop with 24GB RAM and an Apple M4 Pro chip. Benchmarks For our evaluation, we implement 6 kinds of UMDPs that are summarized below. Disaster Rescue is a minimax-regret benchmark used in prior work (Ahmed et al. 2013, 2017; Rigter, Lacerda, and Hawes 2021). Dynamic Power Management (D.P.M.) is adapted from an existing UMDP model (Andriushchenko et al. 2025b). Maintenance is based on an established maintenance MDP formulation (Amari, McLaughlin, and Pham 2006), to which we add uncertainty in the cost of labor and materials. Frozen Lake, Cliff Walking, and Taxi are adapted from the corresponding Gymnasium environments (Towers et al. 2025), to which we add uncertainty in, respectively, the hole layout, wind conditions, and passenger reliability. Complete UMDP specifications are provided in the supplemental material for reproducibility. Unless stated otherwise, experiments use the smallest instance of each benchmark listed in Section 6. 1

https://github.com/SUMI-lab/KAPS

C2: Small Policy Sets Give Low or No Regret Our formulation of the k-adaptable policy synthesis problem is motivated by settings in which the realized MDP can be observed before execution, but the number of policies that can be prepared or maintained is constrained. We therefore show that constrained policy-set sizes provide a useful tradeoff between using one policy for the entire UMDP and preparing a separate optimal policy for every MDP. For each benchmark, we run KAPS for policy-set sizes from k = 1 to k = |M|. Figure 2 reports the optimal minimax regrets, normalized by the regret obtained at k = 1. At k = |M|, the problem trivially results in zero regret by separating all MDPs and assigning their optimal policies. The largest reductions occur for the first few added policies. Moving from k = 1 to k = 2 eliminates regret for D.P.M. and Frozen Lake and substantially reduces it elsewhere; further increases in k can still further reduce regret, but give diminishing returns. Thus, k provides a meaningful tradeoff between the cost of maintaining additional policies and the benefit of adapting to the realized MDP. C3: KAPS Scales to Larger Instances We investigate whether KAPS can still solve instances to proven optimality as either the size of the underlying MDPs or the number of MDPs in the UMDP increases. We use the Maintenance

Relative regret

1

Relative regret

1

0

0

Maintenance

1

2

3

4

5

Cliff Walking

6

18 1

Disaster Rescue

2

3

4

D.P.M.

5

1 2 3 4 5 6

Frozen Lake

1 2 3 4 5 6 7 8 9 101112 1 2 3 4 5 6 7

Policies (k)

Policies (k)

Taxi

1 2 3 4 5 6

Policies (k)

Figure 2: Tradeoff between policy-set size k and proven optimal minimax regret across benchmarks, normalized by the regret of the best single policy solution (k=1) for each benchmark. Unfilled markers indicate zero regret. Runtime (s)

C1: KAPS Outperforms Existing Methods While no existing method directly addresses k-adaptable policy synthesis, the problem reduces to single-policy minimax-regret synthesis for k = 1, enabling a comparison with prior work. We compare KAPS at k = 1 against existing methods: • The exact MILP formulation of (Ahmed et al. 2013). • CEMR with 3-step-options (Ahmed et al. 2017). • CREG with 3-step-options (Rigter, Lacerda, and Hawes 2021). • Average MDP, optimizing the average of the MDPs. • Best MDP, evaluating optimal policies for the individual MDPs on the full UMDP, and using the best one. The Average and Best MDP heuristics were proposed in (Rigter, Lacerda, and Hawes 2021). Only the MILP and KAPS solve the problem exactly and can prove optimality; the remaining methods are inexact heuristics, or approximations. For all methods, we use their stationary policy versions, i.e., policies that only depend on the state, not on time. We run each method on the benchmark instances with a time limit of five minutes. Section 6 reports the obtained minimax regret, runtime, and whether optimality was proven. For timed-out runs, it reports the remaining optimality gap where available: (regbest −L)/ regbest , where L is the lower bound and regbest is the best known solution at timeout; the gap is zero when optimality is proven. The inexact methods occasionally recover an optimal solution, but often return policies with considerably higher worst-case regret. KAPS obtains the lowest reported regret, on 11 of the 13 instances. On the remaining two instances, the MILP obtains a regret lower by only 0.01. Among the exact methods, KAPS proves optimality on nine instances, compared with three for the MILP. Thus, for k = 1, KAPS is competitive with the best existing method (MILP) in solution quality and substantially more effective at proving optimality.

100

100

50

50

0

0 0

100 200 300 400 500

20

Number of states

Number of MDPs

40

60

80 100

Figure 3: Runtime required by KAPS to prove optimality on the Maintenance benchmark with k=2 when varying the number of states (left) and number of MDPs in the UMDP (right). The instances remain tractable even when scaled. benchmark, whose size can be varied systematically while retaining the same problem structure. We vary the number of states |S| from 6 to 501— corresponding to more fine-grained machine degradation levels—and the number of MDPs |M| from 5 to 100— corresponding to more random combinations of repair and replace costs. Other specifications of M remain fixed, and k = 2 is used throughout. Figure 3 reports the average runtimes (and 95% confidence intervals) over 10 seeds required by KAPS to prove optimality for each instance. Runtime initially grows gradually along both dimensions and increases more rapidly for the largest instances. Nevertheless, KAPS proves optimality for all tested instances within approximately 100 seconds, including MDPs with nearly 500 states and UMDPs containing 100 MDPs. C4: All Problem-Specific Components Contribute We assess whether the problem-specific components introduced in Section 5 improve efficiency over a generic BnB implementation, and whether their contributions are consistent across benchmarks. We perform cumulative ablations starting from a baseline that omits the bounding and incumbent heuristics. The baseline policy search branches on a uniformly random eligible state–action pair, whereas the partition search considers MDPs in input order. In both searches, the next node is selected uniformly at random from the queue. For the policy-specific components, we set k=1 and successively enable BoundPolicy, BranchPol-

Avg. MDP Instance

Best MDP

CEMR

CREG

MILP

KAPS

|S| |A| |M| regr. time opt. regr. time opt. regr. time opt. regr. time opt. regr. time opt. regr. time opt.

D.P.M. 18 Cliff Walking 35 Maintenance S 6 Maintenance M 51 Maintenance L 501 Disaster Rescue 32 Disaster Rescue L 100 Frozen Lake 4x4 16 Frozen Lake 5x5 25 Frozen Lake 6x6 36 Frozen Lake 7x7 49 Frozen Lake 8x8 64 Taxi 501

3 4 4 4 4 8 8 4 4 4 4 4 7

6 5.92 5 1.16 18 580 18 220 18 63.3 12 .58 20 3.33 7 1.00 5 .92 5 .92 5 .91 5 .91 6 35.4

<1 <1 <1 <1 <1 <1 <1 <1 <1 <1 <1 <1 <1

✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗

5.92 1.22 555 203 59.9 .49 1.58 1.00 .95 .91 .93 .92 21.3

<1 <1 <1 <1 1 <1 <1 <1 <1 <1 <1 <1 <1

✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗

31.5 12 .82 31 561 261 203 300 59.9 300 .87 300 3.56 300 1.00 <1 .97 2 .96 3 .96 3 .95 4 21.3 300

✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗

5.92 12 .66 1 555 300 203 300 59.9 300 .57 16 1.18 169 1.00 37 .91 14 .91 20 .93 53 .92 47 38.9 60

✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗

5.92 300 ✗ 5.92 <1 ✓ .66 300 ✗ .66 <1 ✓ 555 <1 ✓ 555 <1 ✓ 203 300 92.0% 203 <1 ✓ 59.9 300 97.8% 59.9 9 ✓ .56 300 ✗ .34 1 ✓ 9.28 300 ✗ 1.06 300 14.2% 1.00 <1 ✓ 1.00 <1 ✓ .83 202 ✓ .83 91 ✓ .69 300 4.3% .70 300 5.7% .87 300 14.9% .88 300 15.9% .84 300 22.6% .84 300 20.2% 21.3 300 ✗ 12.5 197 ✓

Table 1: Comparison of worst-case regret values, runtimes in seconds, and optimality gaps (✓ optimal, ✗ no bound, gap) of various methods from related work to KAPS with a runtime limit of 5 minutes on single policy optimization (k=1). MILP, CREG, and the Best MDP heuristic score well but are outperformed by KAPS. MILP is the only other method that can prove optimality, but KAPS’ optimality gaps are consistently tighter. Policy search (𝑘 = 1) Relative runtime

100x

10x

T/O

Partition search (𝑘 = 2) Cliff Walking Maintenance Disaster Rescue Frozen Lake

1x

ss ss ll) ne ll) ne ch ch nd nd No Bou ran Gue xt (a No Bou ran Gue xt (a + + e e + + +B +B +N +N

Figure 4: Runtime of the cumulative component ablations, normalized by the runtime of the full configuration for each benchmark. Timeout is set at 100×. The left panel adds policy-search components for listed benchmarks with k=1; the right panel adds partition-search components for benchmarks with k=2, with all policy-search components enabled. icy, GuessPolicy, and NextPolicy. For the partitionspecific components, we set k=2 and successively enable BoundPartition, BranchPartition, GuessPartition, and NextPartition, while keeping all policy-specific components enabled. Each step therefore measures the marginal contribution of a rule given those enabled before it. Runtimes are normalized by the runtime of the full algorithm, and runs exceeding 100× that runtime are treated as timeouts. We omit D.P.M. because its runtimes are too short to measure reliably, and Taxi because its runtime is too long without all components enabled. Figure 4 shows that all components improve runtime on at least one benchmark. Policy-search components are collectively essential, with GuessPolicy giving the broadest gains. In partition search, BranchPartition has the largest over-

all effect, while GuessPartition and NextPartition help on selected benchmarks. No partial configuration dominates, supporting the design choices of KAPS.

7

Conclusion and Outlook

Many sequential decision-making problems involve model uncertainty that is resolved only shortly before execution. Although this enables adaptation, policies may need to be prepared, communicated, practiced, validated, or approved in advance, limiting how many can be deployed. We introduced k-adaptable policy synthesis as a middle ground: prepare k policies in advance and select the most suitable one once the realized MDP is known. We formalized this tradeoff under a minimax-regret objective, proved the problem NP-hard, and proposed KAPS, an exact nested branch-andbound algorithm that jointly optimizes which MDPs share a policy and the policies themselves. Across our benchmarks, the first few additional policies capture much of the benefit of full adaptation. For k = 1, KAPS is competitive with the best existing method in solution quality and proves optimality substantially more often. Scaling and ablation experiments further show that our problem-specific components significantly reduce runtime and enable larger instances to be solved to optimality. Several directions remain for future work. As mentioned in Section 4, exploiting relationships between solutions for consecutive values of k could efficiently trace the Pareto front between policy-set size and minimax regret, allowing decision makers to choose their preferred tradeoff after solving. Improved partition branching and node selection could make runtime more reliable across UMDPs, while approximate or sampling-based variants could extend the approach to very large or continuously parameterized sets of MDPs. Industrial case studies could further assess the practical value of bounded policy adaptation.

References

Abate, A.; Badings, T.; De Giacomo, G.; and Fabiano, F. 2026. Best-effort policies for robust Markov decision processes. In AAAI, volume 40, 36120–36128. Ahmed, A.; Varakantham, P.; Adulyasak, Y.; and Jaillet, P. 2013. Regret based Robust Solutions for Uncertain Markov Decision Processes. In NeurIPS, volume 26. Ahmed, A.; Varakantham, P.; Lowalekar, M.; Adulyasak, Y.; and Jaillet, P. 2017. Sampling Based Approaches for Minimizing Regret in Uncertain Markov Decision Processes (MDPs). Journal of Artificial Intelligence Research, 59: 229– 264. Amari, S. V.; McLaughlin, L.; and Pham, H. 2006. Costeffective condition-based maintenance using Markov decision processes. In RAMS, 464–469. IEEE. Andriushchenko, R.; Češka, M.; Junges, S.; and Macák, F. 2025a. Policies Grow on Trees: Model Checking Families of MDPs. In ATVA, 51–75. Cham. ISBN 978-3-031-78750-8. Andriushchenko, R.; Češka, M.; Macák, F.; Junges, S.; and Katoen, J.-P. 2025b. An Oracle-Guided Approach to Constrained Policy Synthesis Under Uncertainty. Journal of Artificial Intelligence Research, 82: 433–469. Bertsimas, D.; and Caramanis, C. 2010. Finite Adaptability in Multistage Linear Optimization. IEEE Transactions on Automatic Control, 55(12): 2751–2766. Bordais, B.; and Raskin, J.-F. 2026. Multi-environment mdps with prior and universal semantics. In ICALP, 171–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik. Buchheim, C.; and Kurtz, J. 2017. Min–max–min robust combinatorial optimization. Mathematical Programming, 163(1-2): 1–23. El Ghaoui, L.; and Nilim, A. 2005. Robust solutions to markov decision problems with uncertain transition matrices. Operations Research, 53(5): 780–798. Hanasusanto, G. A.; Kuhn, D.; and Wiesemann, W. 2015. K -Adaptability in Two-Stage Robust Binary Programming. Operations Research, 63(4): 877–891. Iyengar, G. N. 2005. Robust dynamic programming. Mathematics of Operations Research, 30(2): 257–280. Luque-Cerpa, A.; Wang, M.; Carlsson, E.; Seshia, S. A.; Dubhashi, D.; and Torfah, H. 2026. Learning Contextual Runtime Monitors for Safe AI-Based Autonomy. In ICCPS, 130–141. Malaguti, E.; Monaci, M.; and Pruente, J. 2022. KAdaptability in Stochastic Optimization. Mathematical Programming, 196(1): 567–595. Meggendorfer, T.; Weininger, M.; and Wienhöft, P. 2025. Solving robust Markov decision processes: generic, reliable, efficient. In AAAI, volume 39, 26631–26641. Puterman, M. L. 2014. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons. Raskin, J.-F.; and Sankur, O. 2014. Multiple-Environment Markov Decision Processes. In FSTTCS, 531–543. Regan, K.; and Boutilier, C. 2011. Robust online optimization of reward-uncertain MDPs. In IJCAI, volume 22, 2165.

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. Schnitzer, Y.; Abate, A.; and Parker, D. 2026. Efficient solution and learning of robust factored MDPs. In AAAI, volume 40, 36369–36377. Sharma, A.; Harrison, J.; Tsao, M.; and Pavone, M. 2019. Robust and Adaptive Planning under Model Uncertainty. In ICAPS, volume 29, 410–418. Subramanyam, A.; Gounaris, C. E.; and Wiesemann, W. 2020. K-adaptability in two-stage mixed-integer robust optimization. Mathematical Programming Computation, 12(2): 193–224. Towers, M.; Kwiatkowski, A.; Terry, J.; Balis, J. U.; Cola, G. D.; Deleu, T.; Goulão, M.; Kallinteris, A.; Krimmel, M.; KG, A.; Perez-Vicente, R.; Pierré, A.; Schulhoff, S.; Tai, J. J.; Tan, H.; and Younis, O. G. 2025. Gymnasium: A Standard Interface for Reinforcement Learning Environments. In NeurIPS, volume 38. Datasets and Benchmarks Track. Wolff, E. M.; Topcu, U.; and Murray, R. M. 2012. Robust control of uncertain Markov decision processes with temporal logic specifications. In CDC, 3372–3379. IEEE. Xu, H.; and Mannor, S. 2009. Parametric regret in uncertain Markov decision processes. In CDC, 3606–3613. IEEE.

A

Proof of Theorem 1

We prove that k-adaptable policy synthesis with minimax regret (Problem 1) is an NP-hard problem, by showing that the established NP-hard problem 3-SAT is reducible to it. An illustrative example of the reduction is given in Figure 5. Theorem 1 (NP-hardness). Solving k-adaptable policy synthesis (Problem 1) is NP-hard, even for k = 1. Proof of Theorem 1. We reduce from 3-SAT. Let φ = C1 ∧ · · · ∧ Cm be a 3-CNF formula over variables X = {x1 , . . . , xn }. We construct a family of MDPs Mφ with one MDP Mj for each clause Cj . We then solve the k = 1 minimax regret problem on Mφ and answer that φ is satisfiable if and only if the optimal regret is 0. All MDPs share S = {s1 , . . . , sn } ∪ {ssat , sunsat } and A = {0, 1}. For a clause Cj , let χj (i, a) = 1{(xi ∈ Cj ∧ a = 1) ∨ (¬xi ∈ Cj ∧ a = 0)}, which is 1 exactly when assigning xi the truth value represented by action a satisfies a literal of Cj . The MDP Mj is deterministic. From a variable state si , if χj (i, a) = 1, the process moves to ssat . If χj (i, a) = 0, it moves to si+1 when i < n, and to sunsat when i = n. Both ssat and sunsat are absorbing. A reward is obtained only when entering ssat from a different state. A policy π defines a truth assignment τπ , where τπ (xi ) = π(si ) for all i ∈ {1, . . . , n}. We now show that for every clause Cj , Vjπ (s1 ) = 1 if and only if the assignment τπ satisfies Cj . First, suppose that τπ satisfies Cj . Then there exists an index i such that χj (i, π(si )) = 1. Let i⋆ be the smallest such index. For every ℓ < i⋆ , we have χj (ℓ, π(sℓ )) = 0, so the trajectory continues from sℓ to sℓ+1 . Hence the trajectory reaches si⋆ . Since χj (i⋆ , π(si⋆ )) = 1, the transition from si⋆ goes to ssat and yields reward 1. Therefore Vjπ (s1 ) = 1. Second, suppose Vjπ (s1 ) = 1. Then, the trajectory must transition from some variable state si to ssat . By construction, this implies χj (i, π(si )) = 1. Therefore a literal of Cj is true under τπ , so τπ satisfies Cj . For every MDP Mj , the optimal value from the initial state is Vj∗ (s1 ) = 1: since Cj contains at least one literal, one can choose the corresponding action at its variable state and reach ssat . Thus the regret Vj∗ (s1 ) − Vjπ (s1 ) = 0 if and only if Cj is satisfied by τπ . It follows that there exists a policy π with
max Vj∗ (s1 ) − Vjπ (s1 ) = 0 j∈{1,...,m}

if and only if there exists an assignment τ satisfying all clauses of φ. Hence the constructed k = 1 instance has optimal minimax regret 0 if and only if φ is satisfiable. The construction Mφ has m MDPs, each with n + 2 states and two actions, and is therefore polynomial in the size of φ. Thus, deciding whether the optimal k = 1 minimax regret is 0 is NP-hard.

B

Proof of Proposition 1

We briefly reiterate the definitions and notation relevant to this proof. An indexed collection P = (M1 , . . . , Mk ) is a size-k partition of the UMDP M if and only if k [

Mi = M.

i=1

For compactness, throughout this appendix let reg(M′ , π) := max ′ reg(M, π), and M ∈M

reg⋆ (M′ ) := min reg(M′ , π). π

For a partition P = (M1 , . . . , Mk ), let reg(P) :=

max i∈{1,...,k}

reg⋆ (Mi ).

Proposition 1 (Optimality Equivalence). The optimal value obtained by solving Problem 2 equals the optimal value obtained by solving Problem 1. Proof. Let P ⋆ = (M⋆1 , . . . , M⋆k ) minimize reg(P), and let πi⋆ be a minimax-regret policy for M⋆i . Construct the policy set Π⋆ := {π1⋆ , . . . , πk⋆ }. For every M ∈ M⋆i , the policy πi⋆ is available in Π⋆ , and therefore min j∈{1,...,k}

reg(M, πj⋆ ) ≤ reg(M, πi⋆ ).

Consequently, max

min

M ∈M j∈{1,...,k}

reg(M, πj⋆ ) ≤

max

max reg(M, πi⋆ )

i∈{1,...,k} M ∈M⋆ i ⋆

= reg(P ).

Now consider any feasible policy set Π = {π1 , . . . , πk }. Assign each M ∈ M to an index i(M ) ∈ arg min reg(M, πj ), j∈{1,...,k}

breaking ties arbitrarily, and define Mi := {M ∈ M | i(M ) = i}. The indexed subsets P = (M1 , . . . , Mk ) form a partition of M. By the definition of optimal regret, reg⋆ (Mi ) ≤ max reg(M, πi ). M ∈Mi

Since P ⋆ is an optimal partition, reg(P ⋆ ) ≤ reg(P) ≤ max

max reg(M, πi )

i∈{1,...,k} M ∈Mi

= max

min

M ∈M j∈{1,...,k}

reg(M, πj ).

Thus, the regret of Π⋆ is no greater than that of any feasible policy set, so Π⋆ is an optimal solution to Problem 1.

C1 = (a ∨ b ∨ c) M1

1

a

C2 = (¬a ∨ ¬b ∨ d)

1

1 b

0

c

0

0

d

0, 1

ssat

M2

sunsat

a

0 1

0 b

ssat

1 c

1

0, 1

d

0

sunsat

Figure 5: Reduction of the formula φ = (a ∨ b ∨ c) ∧ (¬a ∨ ¬b ∨ d) to a family of MDPs. Each MDP Mj corresponds to one clause Cj . A deterministic policy chooses action 1 (true) or 0 (false) at each variable state.

C

Proof of Theorem 2

Before proving the correctness of KAPS, we establish the correctness of its subprocedure PolicySearch (Alg. 2). For compactness, throughout this appendix let reg(M′ , π) := max ′ reg(M, π), and M ∈M

reg⋆ (M′ ) := min reg(M′ , π). π

For a partition P = (M1 , . . . , Mk ), let reg(P) :=

max i∈{1,...,k}

reg⋆ (Mi ) and

reg⋆ (P) := min reg(P). P

C.1

Correctness of PolicySearch

We first show that the subprocedure’s bounding rule is valid (Lemma 1) and that its branching rule correctly splits the represented policy space (Lemma 2). We introduce the following notation to reason about the set of policies represented by a node in the search procedure. For a policy-search node N , consisting of force and forbid rules,   π(s) = a ∀ force(s, a) ∈ N, ΠN := π : S → A . π(s) ̸= a ∀ forbid(s, a) ∈ N Lemma 1 (Validity of BoundPolicy). For any policysearch node N , BoundPolicy(N ) lower-bounds the regret of every policy in ΠN . Proof. By definition,
BoundPolicy(N ) = max ′ V ⋆ (M ) − VN⋆ (M ) . M ∈M

Take an arbitrary π ∈ ΠN . By definition of an optimum, for every M ∈ M′ we have VN⋆ (M ) ≥ V (π, M ). Therefore, V ⋆ (M ) − VN⋆ (M ) ≤ V ⋆ (M ) − V (π, M ). Since the inequality holds pointwise for every M ∈ M′ , taking the maximum over M ∈ M′ preserves it:

max ′ V ⋆ (M ) − VN⋆ (M ) ≤ max ′ V ⋆ (M ) − V (π, M ) M ∈M

M ∈M

BoundPolicy(N ) ≤ reg(M′ , π). Since π ∈ ΠN was arbitrary, the bound is valid for every policy represented by N .

Lemma 2 (Correctness of policy branching). Let N be a policy-search node, and let (s, a) be any state–action pair for which there exist π, π ′ ∈ ΠN such that π(s) = a and π ′ (s) ̸= a. Then the child nodes N ′ and N ′′ added in l. 14 satisfy ΠN ′ ∪ ΠN ′′ = ΠN ,

ΠN ′ ⊊ ΠN

and

ΠN ′′ ⊊ ΠN .

Proof. In l. 14 the nodes N ′ = N + force(s, a) and N ′′ = N + forbid(s, a) are created. Take an arbitrary π ∈ ΠN . If π(s) = a, then π ∈ ΠN ′ . Otherwise, π(s) ̸= a, and π ∈ ΠN ′′ . Thus, π ∈ ΠN ′ ∪ ΠN ′′ and ΠN ⊆ ΠN ′ ∪ ΠN ′′ . (4) Conversely, take π ∈ ΠN ′ . By construction, N ′ retains all restrictions of N and additionally requires π(s) = a. Therefore, every policy represented by N ′ is also represented by N , so ΠN ′ ⊆ ΠN . Similarly, N ′′ retains all restrictions of N and additionally requires π(s) ̸= a, yielding ΠN ′′ ⊆ ΠN . Thus, ΠN ′ ∪ ΠN ′′ ⊆ ΠN . (5) Combining Equations (4) and (5) gives ΠN ′ ∪ ΠN ′′ = ΠN . Finally, by assumption there exists π ′ ∈ ΠN with π ′ (s) ̸= a, so π ′ ∈ / ΠN ′ and ΠN ′ ⊊ ΠN . Likewise, there exists π ∈ ΠN with π(s) = a, so π ∈ / ΠN ′′ and ΠN ′′ ⊊ ΠN . Lemma 3 (Correctness of PolicySearch). If reg⋆ (M′ ) < regcutoff , PolicySearch in Alg. 2 returns a policy π that achieves reg⋆ (M′ ). Otherwise, it returns ⊥. Proof. First, we establish termination. The root node created in l. 1 represents all deterministic stationary policies. This set is finite because the state and action spaces are finite. By Lemma 2, each child represents a strict subset of the policies represented by its parent. By construction, BranchPolicy selects a state–action pair satisfying the premise of Lemma 2. Hence, each branching step removes at least one represented policy, so every root-to-leaf path has length at most |ΠN0 |−1. Since the search tree is binary and has finite depth, it contains finitely many nodes. The procedure therefore terminates. Suppose first that reg⋆ (M′ ) < regcutoff . Initially, U = regcutoff . By Lemma 2, branching preserves every policy represented by an expanded node. A node is left unexpanded only if BoundPolicy(N ) ≥ U in l. 9. By Lemma 1, no policy represented by such a node has regret strictly below U . Therefore, while U > reg⋆ (M′ ), at least one node in the

queue represents an optimal policy. Since the search terminates, either such a policy is eventually evaluated as a leaf in l. 6, or the incumbent is updated to the same optimal regret earlier by GuessPolicy. Thus, upon termination, the incumbent achieves reg⋆ (M′ ). Finally, suppose that reg⋆ (M′ ) ≥ regcutoff . No feasible policy has regret strictly below the initial value U = regcutoff . Since both incumbent-update conditions require a strict improvement, πbest remains equal to its initial value ⊥. Therefore, the procedure returns ⊥.

C.2

Correctness of KAPS

We now establish the analogous properties for the branchand-bound search over partitions done in KAPS (Alg. 1). We first show that BoundPartition is valid (Lemma 4) and that partition branching preserves all completions of a partial partition (Lemma 5). Together with Lemma 3, these properties are used to establish correctness of KAPS (Theorem 2). For a partition-search node N = (PN , Mremaining ), where PN = (M1 , . . . , Mk ), let PN denote the set of complete partitions extending PN :   Mi ⊆ M′i ∀i,         k   [ ′ ′ ′ . PN := (M1 , . . . , Mk ) Mi = M,     i=1       M′i ∩ M′j = ∅ ∀i ̸= j Lemma 4 (Validity of BoundPartition). For any partitionsearch node N , BoundPartition(N ) lower-bounds the regret of every partition in PN . Proof. By definition, BoundPartition takes the largest regret bound over all subsets of the current subsets that are stored in the cache: BoundPartition(N ) =

max

max reg⋆ (M′′ ).

i∈{1,...,k} M′′ ⊆Mi

Let P ′ = (M′1 , . . . , M′k ) ∈ PN be an arbitrary partition represented by N . For every subset M′′ considered above, we have M′′ ⊆ Mi ⊆ M′i . Therefore, reg⋆ (M′′ ) ≤ reg⋆ (M′i ) ≤ reg(P ′ ). The first inequality follows because enlarging the set of MDPs served by a single policy cannot decrease its optimal minimax regret, and the second follows from reg(P ′ ) =

max j∈{1,...,k}

reg⋆ (M′j ).

Thus, every quantity considered by BoundPartition lower-bounds reg(P ′ ). Taking their maximum preserves the inequality, so BoundPartition(N ) ≤ reg(P ). ′

Since P ∈ PN was arbitrary, the claim follows. ′

Lemma 5 (Correctness of partition branching). Let N be a partition-search node, and let N1 , . . . , Nr , with r ≤ k, be the children obtained by assigning the selected unassigned MDP to the eligible subsets. Then every partition in PN is represented by at least one child, possibly after relabeling its subsets.

Proof. Let M ∈ Mremaining be the MDP selected for branching, and let P ′ = (M′1 , . . . , M′k ) ∈ PN . Since P ′ is a partition of M, M belongs to exactly one subset, say M′i . Assigning M to Mi therefore yields a child that still represents P ′ . If assignments to equivalent empty subsets are omitted, this holds up to relabeling. Conversely, every child only adds an assignment to the partial partition represented by N . Thus, every partition represented by a child also belongs to PN . Theorem 2 (Correctness of KAPS). KAPS terminates and returns an optimal solution to Problem 1. Proof. The partition-search tree has depth at most |M|, since each branch assigns one previously unassigned MDP, and branching factor at most k, since there are at most k subsets to which that MDP can be assigned. Hence, the tree contains finitely many nodes. Each leaf invokes PolicySearch finitely many times, and every invocation terminates by Lemma 3. Therefore, KAPS terminates. The root represents every complete partition of M. By Lemma 5, branching preserves every represented partition. A node is pruned only if BoundPartition(N ) ≥ regbest . By Lemma 4, no partition represented by such a node can improve the incumbent. Thus, while regbest exceeds the optimal partition regret, some node in the queue represents an optimal partition. When such a partition reaches a leaf, every subset Mi satisfies reg⋆ (Mi ) < regbest . Hence, by Lemma 3, each call to PolicySearch returns a policy attaining reg⋆ (Mi ). The leaf is therefore evaluated at its true regret and updates the incumbent. Conversely, if a call returns ⊥, then some subset has optimal regret at least regbest , so the partition cannot improve the incumbent. Therefore, an optimal partition is eventually evaluated unless an equally good incumbent has already been found. Upon termination, regbest equals the minimum partition regret. By Proposition 1, the returned policies are optimal for Problem 1.

D

Benchmark Specifications

This appendix specifies the UMDPs used in the experiments. Unless stated otherwise, all unspecified transition probabilities are zero, rewards for transitions with zero probability are set to 0, and γ = 0.999. For benchmarks described through intermediate random outcomes, Ti is the transition distribution induced by those outcomes, and Ri (s, a, s′ ) is the expected transition reward conditional on reaching s′ .

D.1

Disaster Rescue

Disaster Rescue is based on a minimax-regret UMDP benchmark used in prior work (Ahmed et al. 2013, 2017; Rigter, Lacerda, and Hawes 2021). The benchmark is a UMDP M, where all MDPs share S = {0, . . . , 31}, µ(24) = 1,

A = {0, . . . , 7}, γ = 0.999.

The terminal state is 7. The actions are the eight compass directions, ordered clockwise starting with up.

Each MDP Mi is specified by two obstacle states and one swamp state. The first obstacle state is selected from O

(1)

= {0, 1, 2, 8, 9, 10, 16, 17, 18},

the second obstacle state from O(2) = {22, 23, 30, 31}, and the swamp state from W = {4, 5, 6, 12, 13, 14}. For non-terminal states, the intended compass direction is taken with probability 0.8, while the two neighboring compass directions are each taken with probability 0.1. Moves that leave the grid are clipped to the nearest grid cell. If the resulting cell is not an obstacle, the transition enters that cell. If the resulting cell is an obstacle, the transition enters the obstacle with probability 0.05 and otherwise remains in the current state. The terminal state is absorbing. The reward function is shared in form but depends on the swamp location of Mi . Entering a non-swamp state has reward −0.5. Entering the swamp state has reward sampled from [−2, −1]. The terminal state has reward 0 for all actions and next states.

D.2

Dynamic Power Management

Dynamic Power Management is adapted from an existing UMDP model for constrained policy synthesis (Andriushchenko et al. 2025b). The benchmark is the UMDP M = {M (λ, e) : (λ, e) ∈ {0.10, 0.25, 0.45} × {0.8, 1.6}}. All MDPs share

D.3

Maintenance Scheduling is based on a condition-based maintenance MDP formulation (Amari, McLaughlin, and Pham 2006), to which we add uncertainty in repair and replacement costs. The benchmark is the UMDP M = {M (crepair , creplace ) : (crepair , creplace ) ∈ {0.5, 1.7, 2.9} × {1, 2, 3, 4, 5, 6}}. All MDPs share S = {0, . . . , 5}, A = {wait, service, repair, replace}, µ(0) = 1, γ = 0.999. State 0 is healthy and state 5 is failed. The transition kernel is shared by all MDPs. For s, s′ ∈ S, T (s′ | s, wait) = 0.65 1{s′ = s}+ 0.35 1{s′ = min{s + 1, 5}}, T (s′ | s, service) = 0.88 1{s′ = s}+ 0.12 1{s′ = min{s + 1, 5}}, T (s′ | s, repair) = 0.75 1{s′ = 0}+ 0.25 1{s′ = s}, T (s′ | s, replace) = 1{s′ = 0}. The operating cost is  cop (s) =

q ′ = min{5, q − b + x}. The transition probability Ti ((q ′ , a) | (q, m), a) is the total probability of all pairs (x, b) that yield this value of q ′ . Rewards are negative costs. For an outcome (x, b), define ℓ = 1{x = 1 and q − b = 5}, and ci (q, m, a, x, b) = ei c(a)(1+0.05q)+0.4 1{a ̸= m}+12.0 ℓ, where c(sleep) = 0.2, c(idle) = 1.0, and c(active) = 3.0. The reward Ri ((q, m), a, (q ′ , a)) is the negative expected value of ci (q, m, a, x, b) over all outcomes (x, b) that lead to q′ .

0.1 + 0.5s 8.0

if s < 5, if s = 5.

For Mi = M (crepair,i , creplace,i ), the reward function is Ri (s, wait, s′ ) = −cop (s),

S = {0, . . . , 5} × {sleep, idle, active}, A = {sleep, idle, active}, µ((0, idle)) = 1, γ = 0.999. An MDP Mi = M (λi , ei ) differs only in the requestarrival probability λi and the energy-price multiplier ei . For a state (q, m) and action a, the next mode is a. A request arrives with probability λi . If a = active and q > 0, one queued request is processed with probability 0.9; otherwise no request is processed. If x ∈ {0, 1} denotes arrival and b ∈ {0, 1} denotes service, the next queue length is

Maintenance Scheduling

Ri (s, service, s′ ) = − cop (s) + 0.4 ,
Ri (s, repair, s′ ) = − cop (s) + crepair,i , Ri (s, replace, s′ ) = −creplace,i .

D.4

Frozen Lake

Frozen Lake is adapted from the corresponding Gymnasium environment (Towers et al. 2025), with uncertainty in the hole layout. The benchmark is the UMDP M = {M (Hj ) : j = 0, . . . , 6}, where Hj ⊆ S is the set of hole states in M (Hj ). States are indexed by s = x + 4y,

x, y ∈ {0, . . . , 3}.

All MDPs share S = {0, . . . , 15}, A = {left, down, right, up}, µ(0) = 1, γ = 0.999. The goal state is 15. For non-terminal states, transitions follow the slippery Frozen Lake dynamics: with probability 1/3 the agent moves in the selected direction, and with probability 1/3 each it moves in one of the two perpendicular directions. Moves

that leave the grid keep the agent in the same state. Hole states and the goal state are absorbing. The reward function is shared by all MDPs: Rj (s, a, s′ ) = 1{s′ = 15 and s ̸= 15}. The hole sets are M (H0 ) M (H1 ) M (H2 ) M (H3 ) M (H4 ) M (H5 ) M (H6 )

: : : : : : :

H0 = {13, 14}, H1 = {10, 11}, H2 = {3, 9}, H3 = {2, 7}, H4 = {4, 5}, H5 = {6, 12}, H6 = {11, 14}.

D.6

Taxi

Taxi is adapted from Gymnasium Taxi-v4 (Towers et al. 2025), with weather-dependent dynamics, passenger reliability, hazard costs, and a skip action. The benchmark is the UMDP M = {Mi }6i=1 . All MDPs share the Taxi-v4 state encoding s = enc(r, c, p, d), where r, c ∈ {0, . . . , 4} are the taxi row and column, p ∈ {0, . . . , 4} is the passenger location, and d ∈ {0, . . . , 3} is the destination. We add one absorbing skip state, indexed by 500, so S = {0, . . . , 500}. The action space is A = {south, north, east, west, pickup, dropoff, skip}.

D.5

Cliff Walking

Cliff Walking is adapted from the corresponding Gymnasium environment (Towers et al. 2025), with uncertainty in wind conditions. The benchmark is the UMDP

All MDPs share µ(enc(4, 0, 0, 1)) = 1, The hazard cells are

M = {M (w) : w ∈ {calm, north, east, south, west}}. All MDPs share a 5 × 7 grid with states indexed by x ∈ {0, . . . , 6},

s = x + 7y,

y ∈ {0, . . . , 4}.

The shared MDP components are S = {0, . . . , 34}, A = {up, right, down, left}, µ(14) = 1, γ = 0.999.

H = {(1, 2), (2, 2), (3, 2)}. For actions a ̸= skip, the transition kernel of Mi is the Gymnasium Taxi-v4 kernel with is_rainy = true,

Obstacle states and the goal state are absorbing. The shared movement function move(s, d) returns the state reached by moving one cell from s in direction d, with moves clipped at the grid boundary and moves into O replaced by staying in s. An MDP Mi = M (wi ) differs only in the wind direction wi . For non-absorbing states, the selected action is applied first: s̄ = move(s, a). If wi = calm, then Ti (s′ | s, a) = 1{s′ = s̄}. Otherwise, the wind is applied after the action with probability 0.25: Ti (s′ | s, a) = 0.75 1{s′ = s̄}+0.25 1{s′ = move(s̄, wi )}. The reward function is shared by all MDPs and depends only on the next state:  0 if s′ = 20, Ri (s, a, s′ ) = −1 otherwise, with reward 0 for self-loops in absorbing states.

fickle_passenger = true,

and MDP-specific rainy movement probability ρi and ficklepassenger probability ϕi . The skip action deterministically moves to the absorbing skip state:

The goal state is 20, and the obstacle states are O = {10, 17, 24}.

γ = 0.999.

Ti (500 | s, skip) = 1

for all s ̸= 500.

Successful dropoff states and the skip state are absorbing with reward 0. Rewards are obtained by remapping the Gymnasium Taxi rewards. For a ̸= skip, the standard Taxi reward −1 is mapped to −cstep,i , the reward 20 is mapped to rdel,i , and the penalty −10 is mapped to −10. Transitions into a hazard cell receive an additional penalty chaz,i . The skip action has reward 0. The six MDPs are Name

i 1 2 3 4 5 6

ρi

clear_stable 0.98 rainy_stable 0.75 stormy_stable 0.55 clear_disrupted 0.98 rainy_disrupted 0.75 stormy_disrupted 0.55

E

ϕi

cstep,i

rdel,i

chaz,i

0.0 0.0 0.0 0.5 0.5 0.5

1.0 1.2 1.5 1.0 1.2 1.5

25 25 25 35 35 35

0 4 10 0 4 10

Additional Experimental Results

The main paper includes results (Section 6) on a comparison between KAPS and MILP for k = 1, both limited to a runtime of five minutes. Table 2 contains additional measurements on the same experiments, at runtimes of one and twenty seconds. These measurements provided no additional insight and were omitted from the main paper.

1s runtime MILP

20s MILP

KAPS

Instance

regret ↓

opt. regret

D.P.M. Cliff Walking Maintenance S Maintenance M Maintenance L Disaster Rescue Disaster Rescue L Frozen Lake 4x4 Frozen Lake 5x5 Frozen Lake 6x6 Frozen Lake 7x7 Frozen Lake 8x8 Taxi

5.92 ✗ .81 ✗ 555.4 ✓ 203.0 ✗ 2578.5 ✗ 45.1 ✗ 494.6 ✗ 1.00 ✓ .87 17.2% .84 ✗ .91 31.9% .91 50.5% 21.3 ✗

5.92 .66 555.4 203.0 63.3 .34 1.41 1.00 .85 .84 .88 .90 21.3

opt. regret ✓ ✓ ✓ ✓ ✗ ✓ 61.0% ✓ 8.2% 26.2% 15.9% 31.1% 65.4%

5.92 .66 555.4 203.0 60.1 4.53 37.25 1.00 .84 .74 .87 .89 21.3

300s MILP

KAPS opt. regret

✗ ✗ ✓ 98.4% ✗ ✗ ✗ ✓ 6.0% 21.6% 16.1% 34.8% ✗

5.92 .66 555.4 203.0 59.9 .34 1.22 1.00 .84 .74 .88 .90 17.2

opt. regret ✓ ✓ ✓ ✓ ✓ ✓ 32.0% ✓ 4.8% 10.8% 15.9% 25.6% 57.2%

5.92 .66 555.4 203.0 59.9 .56 9.53 1.00 .83 .70 .87 .84 21.3

KAPS opt. regret

✗ ✗ ✓ 92.0% 97.8% ✗ ✗ ✓ ✓ 5.7% 14.9% 23.8% ✗

opt.

5.92 ✓ .66 ✓ 555.4 ✓ 203.0 ✓ 59.9 ✓ .34 ✓ 1.06 14.2% 1.00 ✓ .83 ✓ .70 5.7% .88 15.9% .84 20.2% 12.5 ✓

Table 2: Comparison between KAPS and the exact MILP method when solving uncertain MDPs for a single robust policy. KAPS achieves high-quality solutions and bounds within 1 second of runtime and eventually proves optimality for most scenarios, except larger Disaster Rescue and Frozen Lake instances. Given 300 seconds of runtime, MILP achieves similar scores across many scenarios but performs significantly worse at proving optimality.

Related documents

• D2PPO: Diffusion Policy Policy Optimization with Dispersive Loss#158761
• Finite-memory strategies in POMDPs with long-run average objectives#1066575
• Beyond Importance Sampling: Rejection-Gated Policy Optimization#19038
• Model-Based Learning of Near-Optimal Finite-Window Policies in POMDPs#670543
• Model-Based Learning of Near-Optimal Finite-Window Policies in POMDPs#668478