🤖 AI

Adaptive Policy Portfolios for Robust Markov Decision Processes

This paper introduces adaptive policy portfolios as a less conservative alternative to standard robust Markov decision processes for environments with partially identifiable dynamics, while establishing that both certifying and synthesizing such portfolios are computationally intractable problems ( $\forall\mathbb{R}$ -complete and $\exists\forall\mathbb{R}$ -complete, respectively) and presenting an offline construction method amenable to runtime specialization.

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

Published 2026-08-19

📖 5 min read🧠 Deep dive

CC BY 4.0

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

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of artificial intelligence, machines often learn to make decisions by simulating countless possible futures. Imagine a robot navigating a room, or a software agent managing a power grid. To do this well, they rely on a mathematical framework that predicts how their actions will change the world. However, these predictions are never perfect. The real world is messy, and the data used to build these models often contains gaps or errors. When an AI acts on a flawed model, it can make catastrophic mistakes. To handle this, researchers developed a method called robust decision-making. Instead of betting on a single, most-likely outcome, the AI plans for the worst-case scenario within a range of possibilities. It asks, "What is the absolute worst thing that could happen if I take this action, and how can I survive it?" This approach guarantees safety, but it comes with a heavy price: the AI becomes overly cautious. It might refuse to act or choose a mediocre path just to avoid a tiny chance of disaster, even if that disaster is highly unlikely.

This paper explores a smarter middle ground for artificial intelligence facing uncertainty. The researchers, working from universities in Belgium and the Netherlands, propose a system that does not force the AI to commit to a single, rigid plan. Instead, they suggest preparing a small, curated collection of different strategies beforehand. Think of it as a pilot carrying a flight plan for clear skies, another for heavy turbulence, and a third for a sudden storm. The pilot does not know which weather will arrive, but they have the right plan ready for each. In the language of the researchers, this is an "adaptive policy portfolio." The system synthesizes these different strategies offline, calculating the best move for various potential realities. Then, once the system is deployed, it watches the environment unfold. As it gathers evidence about what is actually happening, it switches to the strategy that fits best. This allows the AI to be safe without being paralyzed by fear of the worst case.

The team tested this idea on two distinct challenges. The first was a simulation of a data center, where a controller must manage temperature, humidity, and a queue of computer jobs. The system did not know exactly how effective its cooling fans were or how much heat the outside air would bring in. The second challenge involved a drone flying through a three-dimensional grid, battling uncertain wind gusts and the risk of its motors failing. In both cases, the researchers built a library of strategies, each optimized for a specific combination of wind strength or cooling efficiency. They then used a simple, fast algorithm to pick the best strategy from the library as the drone flew or the data center ran. The results were striking. By using a portfolio of just a few strategies, the system reduced its mistakes dramatically compared to using a single, overly cautious plan. With a small library of ten strategies, the drone's errors dropped to nearly zero, and the data center controller kept the environment stable with minimal energy waste.

However, the paper also reveals a significant limitation. While the practical method works well, the researchers proved that finding the perfect set of strategies is mathematically impossible to solve efficiently for complex problems. They showed that the task of certifying whether a given set of strategies is good enough, or finding the absolute best set, belongs to a class of problems that are incredibly difficult for computers to solve. Even in simplified versions of the problem, the complexity is so high that no fast, general-purpose algorithm can exist to solve it for every case. This means that while the researchers can build a very good, practical system, they cannot guarantee it is the absolute best possible one. The difficulty arises because the system must account for every possible way the environment could behave, and the interactions between different strategies create a web of possibilities that grows too large to untangle completely.

The study concludes that this approach offers a powerful, certifiable way to adapt to uncertainty. It bridges the gap between a rigid, single plan and the impossible task of planning for every conceivable future simultaneously. The researchers demonstrated that by accepting a small, manageable set of options, an AI can remain robust against unknowns while still performing nearly as well as if it knew the future. The trade-off is that the system must spend time preparing these options in advance, and the online selection process takes a little time to identify the right one. Yet, the experiments showed that this cost is small compared to the gains in performance. The work provides a clear path forward for building AI systems that are both safe and effective, acknowledging that while we cannot solve every mathematical puzzle perfectly, we can construct tools that are good enough to handle the real world.

Technical Summary: Adaptive Policy Portfolios for Robust Markov Decision Processes

Problem Statement

Robust Markov Decision Processes (RMDPs) address sequential decision-making under uncertainty by optimizing a policy against a set of plausible transition functions (an uncertainty set $U$ ). The standard approach seeks a single policy that maximizes the worst-case value. However, this often leads to overly conservative behavior, as the policy is dominated by the most difficult environments in $U$ , even if those environments are unlikely or quickly ruled out by observation.

While Robust Regret minimization offers an alternative by minimizing the shortfall relative to the optimal policy for a specific realization, it still commits to a single policy for every possible environment. This fails to exploit online evidence to identify which model governs the environment.

This paper proposes Adaptive Policy Portfolios: a finite set of memoryless randomized policies synthesized offline, paired with a lightweight online selector. The portfolio aims to minimize Robust Regret, defined as the worst-case loss of the best portfolio member relative to the policy that would have been optimal had the true environment been known. The goal is to achieve a controlled form of adaptation where the online selection occurs over a finite, pre-validated set of policies.

Methodology

Theoretical Framework

The authors analyze the computational complexity of two core subproblems:

Certification: Given a specific portfolio $\Pi$ , determine if its robust regret is below a threshold $t$ .
Synthesis: Construct a portfolio of size at most $k$ that minimizes robust regret.

The analysis utilizes the hierarchy of the Theory of the Reals ( $\exists\mathbb{R}, \forall\mathbb{R}, \exists\forall\mathbb{R}$ ) and the Square-Root-Sum (SQRS) problem. The paper distinguishes between general (non-rectangular) uncertainty and $(s, a)$ -rectangular uncertainty (where uncertainty at one state-action pair is independent of others).

Key theoretical mechanisms include:

Lift Construction: A transformation that converts a policy comparison problem into a regret certification problem by making a reference policy optimal in every realization via a "bonus" action.
Restriction Transformation: A method to constrain synthesized policies to specific action sets by making disallowed actions "ruinous" (leading to a sink with high negative reward), ensuring the minimization stays within the desired class.
Hardness Reductions: The paper constructs RMDPs that encode polynomial non-positivity, Boolean satisfiability (UNSAT/SAT), and square-root sums to establish lower bounds.

Practical Construction

Despite the theoretical intractability, the authors propose an offline construction pipeline:

Discretization: The uncertainty parameter space is divided into cells.
Candidate Generation: An optimal policy is computed for the midpoint of each cell.
Evaluation: Each candidate is robustly evaluated against all cells to generate a "regret profile" (a vector of regrets across the parameter space).
Clustering: K-means clustering is applied to these profiles to select a subset of $k$ policies that best cover the space.
Online Deployment: The Upper Confidence Bound (UCB) algorithm is used at runtime to select the best portfolio member as observations accumulate, treating portfolio members as bandit arms.

Key Contributions

Introduction of Adaptive Policy Portfolios: The paper formalizes adaptive policy portfolios as a finite, certifiable form of adaptation for RMDPs, bridging the gap between committing to a single robust policy and full belief-state planning.
Complexity Classification:
- Certification: Proved to be $\forall\mathbb{R}$ -complete for deterministic portfolios in acyclic $(s, a)$ -rectangular RMDPs. This holds even though rectangularity usually simplifies RMDPs; the pointwise maximum over portfolio members reintroduces the necessary quantifier alternation.
- Synthesis: Proved to be $\exists\forall\mathbb{R}$ -complete for bounded portfolios under general rational polytopic uncertainty.
- Single-Policy Case: The minimal robust regret for a single policy is shown to be hard for various levels of the hierarchy, including coNP-hard, coSQRS-hard, and $\forall\mathbb{R}$ -hard, depending on the uncertainty structure (rectangular vs. general) and the presence of cycles.
Identification of Hardness Sources: The paper isolates the structural sources of computational hardness:
- Boolean Hardness: Arises from uncertain transitions shared by both policies.
- Square-Root Sum Hardness: Arises when shared uncertain choices lie on cycles.
- Algebraic Hardness: Arises from the optimization over the policy space itself.
Empirical Validation: A prototype implementation demonstrates that portfolios constructed via discretization and clustering significantly reduce empirical robust regret compared to single policies, with the regret dropping sharply as the portfolio size increases.

Results

Theoretical Results

The complexity landscape is summarized in Table 1 of the paper:

Certifying a given policy is $\forall\mathbb{R}$ -complete in general and coNP-hard (and coSQRS-hard) even in restricted acyclic rectangular cases.
Certifying a given portfolio is $\forall\mathbb{R}$ -complete even for deterministic portfolios in acyclic rectangular RMDPs.
Synthesizing a single randomized policy is $\forall\mathbb{R}$ -hard in general and NP/coNP/SQRS-hard in rectangular cases.
Synthesizing a bounded portfolio is $\exists\forall\mathbb{R}$ -complete in general. Under rectangular uncertainty, the problem is hard even for $k=1$ .

These results imply that efficient general-purpose algorithms for exact synthesis or certification are unlikely to exist under standard complexity assumptions.

Experimental Results

The authors evaluated the approach on two benchmarks: a Datacenter Climate Control problem and a UAV Control problem in a 3D grid.

Regret Reduction: Empirical robust regret decreased significantly as the portfolio size $K$ increased. For example, in the UAV-Large benchmark, regret dropped from 0.126 ( $K=1$ ) to 0.003 ( $K=10$ ).
Online Identification: Using UCB, the system successfully identified the best portfolio member in a fixed but unknown environment. While the fraction of runs identifying the exact best member decreased as $K$ grew (due to more near-ties), the regret of the recommended arm relative to the best member remained minimal. This indicates that even if the exact best member is not identified, the selected member is nearly as good.

Significance and Claims

The paper claims that adaptive policy portfolios offer a finite and certifiable middle ground between the excessive conservatism of single robust policies and the intractability of full belief-state planning (e.g., Bayes-adaptive MDPs).

The authors emphasize that while the worst-case complexity bounds are high (ruling out efficient exact algorithms), the practical offline construction yields portfolios with substantially lower empirical regret. The work provides a rigorous theoretical foundation for understanding why these problems are hard (linking them to the Theory of Reals and SQRS) and demonstrates that a simple discretization and clustering approach is effective in practice.

The paper concludes that the gap between the theoretical hardness and practical utility remains an open area, particularly regarding bounded synthesis under rectangular uncertainty and the precise complexity of single-policy minimal regret. The proposed method allows for runtime specialization without the computational overhead of online belief updates.