🤖 machine learning

Robust Parameter Learning for Uncertain MDPs

This paper proposes a robust parameter learning framework for uncertain Markov decision processes that utilizes parametric MDPs to capture algebraic dependencies between transitions, thereby generating tighter, dependency-aware PAC uncertainty models through a hierarchy of sound polytopic approximations.

Original authors: Yannik Schnitzer, Alessandro Abate, David Parker

Published 2026-05-05

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Yannik Schnitzer, Alessandro Abate, David Parker

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

Imagine you are trying to teach a robot how to navigate a maze, but you don't have a perfect map. You only have a notebook of observations from the robot's past attempts. Sometimes it bumps into walls; sometimes it finds the exit.

The Problem: The "Independent Guess" Trap
Traditionally, when researchers try to build a safe plan for a robot with an unknown map, they treat every single turn in the maze as a separate, isolated guess.

The Old Way: They look at "Turn Left" and say, "Based on my notes, there's a 40% to 60% chance this works." Then they look at "Turn Right" and say, "There's a 30% to 50% chance this works." They treat these two numbers as if they have nothing to do with each other.
The Flaw: In reality, the maze isn't random. Maybe the whole maze is slippery, or maybe the robot's wheels are slightly worn out. These "hidden factors" affect every turn at the same time. If the robot slips on a left turn, it's likely to slip on a right turn too. By ignoring these hidden connections, the old methods end up drawing a massive, fuzzy safety net around the robot's possible paths. This makes the robot overly cautious, refusing to move because the "uncertainty" looks too huge.

The Solution: The "Master Key" Approach
The authors of this paper propose a smarter way to learn from the robot's data. Instead of guessing the probability of every single turn independently, they assume there is a Parametric MDP (pMDP).

Think of this as a Master Key (or a set of hidden dials) that controls the entire maze.

Instead of guessing the chance of "Turn Left" and "Turn Right" separately, they guess the settings of the Master Key.
Maybe Dial 1 controls how slippery the floor is, and Dial 2 controls how strong the wind is.
The chance of turning left depends on the floor slipperiness. The chance of turning right also depends on the floor slipperiness.

How It Works: Projecting the Shadow

Gather Data: They watch the robot move and record how often it succeeds or fails.
Create a "Shadow" Map: Instead of just drawing a box around the success rate of "Turn Left," they use the math of the Master Key to project those observations onto the Dials.
- Analogy: Imagine you are trying to figure out the shape of a 3D object by looking at its shadow on a wall. If you see the shadow is narrow, you know the object can't be wide. The authors do this in reverse: they take the "shadows" (the observed success rates of turns) and project them back onto the "object" (the hidden Dials).
The Result: This creates a much tighter, more accurate map of what the hidden Dials could be. Because they know the Dials control everything at once, they can rule out impossible combinations. For example, if the data says the floor is slippery, they know all turns are slippery, so they don't have to assume the robot might be lucky on the next turn.

The Challenge: Solving the Puzzle
The new map they create is mathematically complex. It's not a simple box; it's a weird, multi-sided shape (like a crumpled piece of paper) that is very hard for computers to solve quickly.

The Fix: The authors built a "hierarchy" of simpler shapes (like smooth, rectangular boxes) that wrap around this complex shape.
They offer different sizes of these boxes:
- Tightest Box: Very accurate but takes a long time to compute.
- Looser Box: Faster to compute but slightly less precise.
- This lets users choose the balance between speed and accuracy.

The Outcome: Smarter, Safer Robots
When they tested this on benchmarks like a Mars rover navigating a rocky terrain or a glider flying through wind currents:

Tighter Estimates: Their method produced uncertainty estimates that were orders of magnitude tighter than the old methods. The "safety net" was much smaller, meaning the robot didn't have to be as paranoid.
Better Policies: Because the uncertainty was smaller, the robot could find better, more efficient paths to its goal while still being mathematically guaranteed to be safe.
Speed: Even with the complex math, their "hierarchy" of approximations allowed them to solve these problems efficiently.

In a Nutshell
The paper teaches us that when learning from data, we shouldn't treat every event as an isolated coin flip. By recognizing that hidden factors (like weather or mechanical wear) link events together, we can use a "Master Key" model to learn much faster and build much better plans. It's the difference between guessing the weather in every city independently versus realizing that if it's raining in London, it's likely raining in Paris too.

Technical Summary: Robust Parameter Learning for Uncertain MDPs

Problem Statement

Learning-based verification of Markov Decision Processes (MDPs) with unknown transition probabilities often relies on Uncertain MDPs (UMDPs) to synthesize robust policies. Standard approaches, such as Interval MDPs (IMDPs), learn confidence intervals for each transition probability independently. However, in many practical systems, transition probabilities are not independent; they are coupled through shared latent quantities (e.g., common failure rates, environmental conditions, or reliability parameters). Treating these transitions as independent ignores structural dependencies, leading to overly conservative uncertainty sets and suboptimal robust policies.

Existing methods like "parameter tying" can handle cases where transitions share exactly the same parametric expression, but they fail to capture dependencies between transitions governed by different but related expressions over a shared parameter space. The core problem addressed is how to learn a UMDP that respects the algebraic dependencies of a known Parametric MDP (pMDP) structure while providing Probably Approximately Correct (PAC) guarantees on the inclusion of the true system.

Methodology

The authors propose a framework that lifts statistical uncertainty from individual transition frequencies to the parameter space of a known pMDP. The methodology proceeds in three main stages:

1. Projection of Statistical Uncertainty

Given a known pMDP $M_\Theta$ and a set of transition samples, the approach first computes standard confidence intervals for the empirical transition frequencies. Instead of treating these as independent constraints, the method projects these intervals into the pMDP's parameter space $\Theta$ .

For each distinct parametric expression $f \in \Lambda$ , a confidence interval $[l_f, u_f]$ is derived.
The uncertainty region $U$ is defined as the set of all parameter instantiations $v \in D$ that satisfy $l_f \leq f[v] \leq u_f$ for all $f \in \Lambda$ .
This region $U$ induces a UMDP where the uncertainty set contains all transition kernels consistent with some $v \in U$ . Theorem 1 establishes that with probability $1-\delta$ , the true parameter instantiation lies within $U$ , ensuring the induced UMDP contains the true system.

2. Handling Computational Intractability

The induced uncertainty set $U$ is generally non-rectangular (coupled) and defined by polynomial constraints, making robust policy synthesis (solving the robust Bellman equations) NP-hard. To address this, the authors propose a hierarchy of sound rectangular relaxations (over-approximations) that preserve the PAC guarantee while enabling tractable synthesis:

Rectangular Relaxation ( $P_R(U)$ ): Projects the coupled set $U$ onto each state-action pair independently. The environment can choose a different worst-case instantiation for each state-action pair. This reduces the inner optimization to a Linear Program (LP) but may be loose.
Expression-wise Projection ( $P_\Lambda(U)$ ): Aggregates information across all transitions to compute tighter bounds for each parametric expression $f$ by solving LPs over $U$ . This yields an IMDP with significantly tighter intervals than standard learning, solvable via bisection.
Parameter-wise Projection ( $P_\Theta(U)$ ): Projects $U$ onto the individual parameter dimensions to form a hyperrectangle bounding $U$ . This is computationally cheaper but can be looser than expression-wise projection.

3. Linearization and Edge Cases

Polynomial Constraints: When transition probabilities are non-linear (polynomial) functions of parameters, the authors employ McCormick envelopes to construct a linear outer approximation of the feasible region. They integrate Optimization-Based Bound Tightening (OBBT) to iteratively refine variable bounds, ensuring the linear relaxation remains tight.
Feasibility: The authors note that the induced region $U$ may be empty if the learned intervals are jointly inconsistent with the parametric structure (indicating potential model misspecification). They provide a statistical interpretation for this and a fallback mechanism to standard interval learning if $U$ is empty.
Extensions: The framework extends to other uncertainty classes, such as $L_1$ -balls and ellipsoids, by adapting the projection and relaxation techniques (e.g., using Second-Order Cone Programs for ellipsoids).

Key Contributions

Parametric Projection: A novel method to project statistical confidence sets from transition frequencies into the parameter space of a pMDP, capturing algebraic dependencies between transitions that independent interval learning misses.
Hierarchy of Relaxations: The proposal of a sound inclusion hierarchy of rectangular relaxations ( $P_I \supseteq P_\Lambda(U) \supseteq P_R(U) \supseteq P_U$ ) that allows users to trade off between computational efficiency and the tightness of the uncertainty estimates.
Tractable Synthesis: The integration of McCormick envelopes and OBBT to handle non-linear parametric structures, enabling the use of standard robust value iteration on the relaxed models.
Formal Guarantees: The approach maintains PAC guarantees on the performance of synthesized robust policies, ensuring that the true system is contained within the learned model with high confidence.

Experimental Results

The authors implemented their approach in the PRISM model checker and evaluated it on benchmarks including Aircraft collision avoidance, Betting games, Mars rover navigation, and Gliders.

Tightness: The proposed methods, particularly the expression-wise projection ( $P_\Lambda(U)$ ), yielded substantially tighter uncertainty estimates compared to classical interval-based learning (with parameter tying). In several cases, the relative gap between the certified lower and upper bounds was reduced by orders of magnitude (e.g., from a gap of 1.88 to 0.10 in the Betting Game).
Efficiency: While the most precise rectangular relaxation ( $P_R(U)$ ) is computationally expensive for high-dimensional parameter spaces, the expression-wise projection ( $P_\Lambda(U)$ ) achieved similar tightness to $P_R(U)$ in many instances with computational costs comparable to the baseline.
Online Learning: In online learning scenarios (where policies guide data collection), the proposed methods improved sample efficiency, achieving stronger performance guarantees with fewer trajectories compared to baseline approaches.

Significance and Claims

The paper claims that by exploiting the algebraic structure of pMDPs, it is possible to move beyond the "independent transition" assumption of standard UMDP learning. The primary significance lies in obtaining less conservative robust policies and tighter performance guarantees from the same amount of data.

The authors emphasize that their approach does not require new sampling mechanisms; it is agnostic to the data collection process. Instead, it offers a more sophisticated post-processing and synthesis framework that leverages known structural dependencies. The work demonstrates that respecting these dependencies is crucial for effective robust learning, particularly in systems where global parameters (like channel reliability or environmental conditions) couple local dynamics. The paper concludes that this framework provides a practical path to robust policy synthesis for complex, uncertain systems with formal PAC guarantees.