Optimizing Minimax Regret in Uncertain MDPs with Small Sets of Policies

• URL: http://arxiv.org/abs/2608.02509v1
• Date: Mon, 03 Aug 2026 17:08:02 GMT
• Title: Optimizing Minimax Regret in Uncertain MDPs with Small Sets of Policies
• Abstract summary: Sequential decision-making in real-world applications often involves uncertainty about the environment's model.<n>We introduce $k$-adaptable policy synthesis, which optimize such a set of $k$ policies under a minimax-regret objective.<n> Experiments across various UMDP benchmarks show that the largest reduction in regret consistently occurs when increasing from one to two policies.
• Score: 14.779869341263456
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 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.

Related papers

• Multi-Environment POMDPs: Discrete Model Uncertainty Under Partial Observability [29.63953552645502]
  Multi-environment POMDPs (ME-POMDPs) extend standard POMDPs with discrete model uncertainty.<n>We show that ME-POMDPs can be generalized to POMDPs with sets of initial beliefs.<n>We then devise exact and approximate (point-based) algorithms to compute robust policies for AB-POMDPs.
  arXiv  Detail & Related papers  (2025-10-27T18:24:11Z)
• Prescribe-then-Select: Adaptive Policy Selection for Contextual Stochastic Optimization [4.154714580436713]
  We propose a modular framework that first constructs a library of feasible candidate policies and then learns a meta-policy to select the best policy.<n>We implement the meta-policy using ensembles of Optimal Policy Trees trained via cross-validation on the training set, making policy choice entirely data-driven.<n>All the code to reproduce the results can be found at https://anonymous.4open.science/r/Prescribe-then-Select-TMLR.
  arXiv  Detail & Related papers  (2025-09-09T23:56:16Z)
• Best-Effort Policies for Robust Markov Decision Processes [69.60742680559788]
  We study the common generalization of Markov decision processes (MDPs) with sets of transition probabilities, known as robust MDPs (RMDPs)<n>We call such a policy an optimal robust best-effort (ORBE) policy.<n>We prove that ORBE policies always exist, characterize their structure, and present an algorithm to compute them with a small overhead compared to standard robust value iteration.
  arXiv  Detail & Related papers  (2025-08-11T09:18:34Z)
• Learning Deterministic Policies with Policy Gradients in Constrained Markov Decision Processes [59.27926064817273]
  We introduce an exploration-agnostic algorithm, called C-PG, which enjoys global last-iterate convergence guarantees under domination assumptions.<n>We empirically validate both the action-based (C-PGAE) and parameter-based (C-PGPE) variants of C-PG on constrained control tasks.
  arXiv  Detail & Related papers  (2025-06-06T10:29:05Z)
• Convergence of Policy Mirror Descent Beyond Compatible Function Approximation [66.4260157478436]
  We develop theoretical PMD general policy classes where we strictly assume a weaker variational dominance and obtain convergence to the best-in-class policy.<n>Our main notion leverages a novel notion induced by the local norm induced by the occupancy- gradient measure.
  arXiv  Detail & Related papers  (2025-02-16T08:05:46Z)
• Near-Optimal Policy Identification in Robust Constrained Markov Decision Processes via Epigraph Form [26.01796404477275]
  This paper presents the first algorithm guaranteed to identify a near-optimal policy in a robust constrained MDP (RCMDP)<n>An optimal policy minimizes cumulative cost while satisfying constraints in the worst-case scenario across a set of environments.
  arXiv  Detail & Related papers  (2024-08-29T06:37:16Z)
• Constraint-Generation Policy Optimization (CGPO): Nonlinear Programming for Policy Optimization in Mixed Discrete-Continuous MDPs [21.246169498568342]
  CGPO provides bounded policy error guarantees over an infinite range of initial states for many DC-MDPs with expressive nonlinear dynamics.<n>CGPO can generate worst-case state trajectories to diagnose policy deficiencies and provide counterfactual explanations of optimal actions.<n>We experimentally demonstrate the applicability of CGPO across various domains, including inventory control, management of a water reservoir system, and physics control.
  arXiv  Detail & Related papers  (2024-01-20T07:12:57Z)
• Recursively-Constrained Partially Observable Markov Decision Processes [13.8724466775267]
  We show that C-POMDPs violate the optimal substructure property over successive decision steps. Online re-planning in C-POMDPs is often ineffective due to the inconsistency resulting from this violation. We introduce the Recursively-Constrained POMDP, which imposes additional history-dependent cost constraints on the C-POMDP.
  arXiv  Detail & Related papers  (2023-10-15T00:25:07Z)
• Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs [107.28031292946774]
  We study the problem of computing an optimal policy of an infinite-horizon discounted Markov decision process (constrained MDP) We develop two single-time-scale policy-based primal-dual algorithms with non-asymptotic convergence of their policy iterates to an optimal constrained policy. To the best of our knowledge, this work appears to be the first non-asymptotic policy last-iterate convergence result for single-time-scale algorithms in constrained MDPs.
  arXiv  Detail & Related papers  (2023-06-20T17:27:31Z)
• Efficient Policy Iteration for Robust Markov Decision Processes via Regularization [49.05403412954533]
  Robust decision processes (MDPs) provide a framework to model decision problems where the system dynamics are changing or only partially known. Recent work established the equivalence between texttts rectangular $L_p$ robust MDPs and regularized MDPs, and derived a regularized policy iteration scheme that enjoys the same level of efficiency as standard MDPs. In this work, we focus on the policy improvement step and derive concrete forms for the greedy policy and the optimal robust Bellman operators.
  arXiv  Detail & Related papers  (2022-05-28T04:05:20Z)
• Risk-Averse Decision Making Under Uncertainty [18.467950783426947]
  A large class of decision making under uncertainty problems can be described via Markov decision processes (MDPs) or partially observable MDPs (POMDPs) In this paper, we consider the problem of designing policies for MDPs and POMDPs with objectives and constraints in terms of dynamic coherent risk measures.
  arXiv  Detail & Related papers  (2021-09-09T07:52:35Z)
• CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guarantee [61.176159046544946]
  In safe reinforcement learning (SRL) problems, an agent explores the environment to maximize an expected total reward and avoids violation of certain constraints. This is the first-time analysis of SRL algorithms with global optimal policies.
  arXiv  Detail & Related papers  (2020-11-11T16:05:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.