Adaptive Policy Portfolios for Robust Markov Decisi... | AI Research

Adaptive Policy Portfolios for Robust Markov Decision Processes introduces a method to reduce the conservativeness of robust decision-making by using a set of policies rather than a single one. By synthesizing a finite collection of memoryless policies offline and selecting between them online as evidence about the environment accumulates, this approach balances the need for robust performance with the ability to adapt to specific, partially identifiable dynamics.

Addressing Robustness and Conservativeness

Robust Markov Decision Processes (RMDPs) typically optimize a policy against the worst-case transition dynamics within an uncertainty set. While this ensures safety, it often results in overly conservative behavior because the policy is dominated by the most difficult environments, even if those environments are unlikely or can be ruled out after deployment. The authors propose "adaptive policy portfolios" to mitigate this. Instead of committing to one policy, the system uses a portfolio of policies—each tailored to different regions of the uncertainty set—and a lightweight selector to choose the best-performing member based on observed evidence.

Measuring Portfolio Quality

The researchers use "robust regret" as the primary metric for evaluating these portfolios. Robust regret measures the loss of a portfolio member relative to the policy that would have been optimal if the true transition function were known. For a portfolio, this is defined as the maximum shortfall across all plausible environments, comparing the best member of the portfolio against the optimal policy for that specific environment. This provides an offline guarantee of performance that allows for runtime specialization.

Computational Complexity

The paper provides a complexity-theoretic analysis of the certification and synthesis of these portfolios. The authors establish that:

• Certifying a given portfolio is $\forall\mathbb{R}$-complete, even for deterministic portfolios in acyclic, $(s,a)$-rectangular RMDPs.

• Synthesizing a portfolio of a specific size is $\exists\forall\mathbb{R}$-complete for general rational polytopes.

• The single-policy case is already computationally hard, both combinatorially and algebraically.
  These findings indicate that finding an optimal portfolio is difficult, as the problems fall into high-level complexity classes within the theory of the reals. The authors note that these worst-case bounds rule out efficient general-purpose algorithms under standard assumptions.

Practical Construction and Limitations

Despite the theoretical complexity, the authors present an offline construction method that remains practical. This method involves discretizing the uncertainty into cells, computing a candidate policy for each cell, and evaluating these candidates against all cells. The resulting regret profiles are then clustered to fit the desired portfolio budget. At runtime, the system uses the UCB (Upper Confidence Bound) algorithm to select among the portfolio members as data is gathered.
The authors emphasize that while their approach offers a way to manage adaptation, it is limited by the inherent hardness of the underlying decision problems. Even with structural assumptions like rectangularity—which simplifies many RMDP problems—the need to evaluate multiple policies against a worst-case realization maintains a high level of computational difficulty.