Interval Markov Decision Processes with Continuous Action-Spaces

1. Problem Statement

The paper addresses a critical gap in the control synthesis of uncertain stochastic systems using Interval Markov Decision Processes (IMDPs).

• Context: IMDPs are finite-state models where transition probabilities are not known precisely but are bounded within intervals. They are widely used for robust control synthesis (maximizing rewards under worst-case uncertainty).
• Limitation: Existing algorithms for IMDPs assume a discrete action space. In many real-world control applications, the action space is continuous (e.g., steering angles, thrust levels).
• Current Workarounds & Flaws:
  1. Discretization: Discretizing the continuous action space leads to an exponential explosion in complexity (curse of dimensionality) and often yields suboptimal solutions without guaranteed bounds.
  2. Heuristics: Using non-convex optimization heuristics lacks formal guarantees of optimality.
• Objective: The authors introduce continuous-action IMDPs (caIMDPs), where transition probability bounds are functions of the continuous action variables. The goal is to develop an exact, efficient value iteration algorithm to synthesize optimal policies that maximize the pessimistic expected cumulative reward (robust control) without discretizing the action space.

2. Methodology

The core of the methodology involves reformulating the value iteration step for caIMDPs to transform a difficult non-convex max-min problem into a set of tractable maximization problems.

A. Problem Formulation

The robust control problem is defined as finding a policy $\pi$ that maximizes the reward against the worst-case adversary $\xi$ (which selects the transition probability distribution within the allowed intervals):
$$\max_{\pi} \min_{\xi} \mathbb{E} \left[ \sum_{i=0}^N \gamma^i R(q_i) \right]$$
The value iteration update equation (Bellman equation) for caIMDPs involves solving the following max-min problem for each state $q$:
$$V_{k-1}(q) = R(q) + \gamma \max_{a \in A} \min_{p \in \Gamma_{q,a}} \sum_{q'} p(q') V_k(q')$$
where $A$ is the continuous action set and $\Gamma_{q,a}$ is the set of feasible probability distributions defined by lower ($\check{P}$) and upper ($\hat{P}$) bounds.

B. Decomposition via Duality (The Main Theoretical Contribution)

The authors prove that the inner minimization (over probability distributions $p$) can be solved using Lagrange duality.

1. Dual Transformation: The original max-min problem is transformed into a single maximization problem involving Lagrange multipliers.
2. Decomposition (Theorem 3.2): By exploiting the structure of the dual problem and sorting the value function vector $V_k$ in descending order, the authors show that the complex max-min problem is equivalent to solving $|Q|$ simpler maximization problems (where $|Q|$ is the number of states).
   • Let the sorted value vector be $V_k(q_1) \ge V_k(q_2) \ge \dots \ge V_k(q_{|Q|})$.
   • The optimal value is found by solving $|Q|$ separate problems of the form:
     $$\max_{a \in A} \left( \sum_{i=1}^{j-1} (V_k(q_i) - V_k(q_j)) \check{P}(q, a, q_i) + \sum_{i=j+1}^{|Q|} (V_k(q_i) - V_k(q_j)) \hat{P}(q, a, q_i) + V_k(q_j) \right)$$
     for each $j \in \{1, \dots, |Q|\}$.

C. Tractability Conditions

The paper identifies specific conditions on the action set $A$ and the transition bounds ($\check{P}, \hat{P}$) under which these $|Q|$ maximization problems become computationally efficient:

1. Linear Case: If $A$ is a polytope and bounds are linear in $a$, the problems are Linear Programs (LPs).
   • Insight: The optimal action lies on the vertices of $A$. Thus, synthesizing over a discrete IMDP with actions = vertices of $A$ is sufficient for optimality.
2. Concave/Convex Case: If $A$ is convex, $\check{P}$ is concave, and $\hat{P}$ is convex, the problems are Convex Programs (CPs). Standard convex solvers can be used.
3. Convex/Concave Case: If $A$ is a polytope, $\check{P}$ is convex, and $\hat{P}$ is concave, the problem is maximizing a convex function over a polytope. The optimum lies at the vertices.

3. Key Contributions

1. Introduction of caIMDPs: Formal definition of IMDPs with continuous action spaces where transition bounds depend on actions.
2. Exact Reformulation: Proof that the value iteration max-min step can be decomposed into $|Q|$ independent maximization problems, avoiding the need for heuristics or blind discretization.
3. Efficient Algorithms: Identification of three specific cases (Linear, Concave/Convex, Convex/Concave) where the synthesis problem is solvable via standard LP or CP solvers with guaranteed optimality.
4. Vertex Optimality Insight: Demonstration that in linear and convex/concave cases, checking only the vertices of the action polytope is sufficient to find the global optimum, effectively bridging continuous and discrete synthesis.
5. Suboptimality Bounds: Discussion on how caIMDPs can be used as abstractions for continuous stochastic systems, providing lower and upper bounds on the true optimal reward to quantify suboptimality.

4. Results

The authors validated their approach using a numerical example:

• Setup: A caIMDP with 25 states and a 3-dimensional continuous action space (a cylinder). Transition bounds were concave/convex.
• Comparison:
  • caIMDP Solution: Solved via Convex Programming.
  • Discrete Approximation: Solved by sampling $s$ actions from the continuous space and solving the resulting discrete IMDP.
• Findings:
  • The caIMDP solution provided the true optimal reward ($0\%$ suboptimality).
  • Discrete approximations were significantly suboptimal. Even with 125 sampled actions (5 points per dimension), the suboptimality was ~4.32%.
  • Computation Time: Solving the caIMDP took ~2.2 seconds, comparable to solving a discrete IMDP with only 27 actions (3 points per dimension), which had a suboptimality of ~5.17%.
• Conclusion: The caIMDP approach is not only the only way to achieve true optimality but is also computationally efficient compared to high-resolution discretization.

5. Significance

• Theoretical Advancement: This work removes the restrictive assumption of discrete action spaces in IMDP literature, enabling the application of robust control synthesis to high-dimensional continuous systems.
• Practical Impact: It provides a rigorous framework for control synthesis in robotics, autonomous vehicles, and process control where actions are naturally continuous and system dynamics are uncertain.
• Computational Efficiency: By reducing the problem to standard convex/linear programming, it leverages mature optimization tools, making robust control scalable to higher dimensions where previous heuristic methods failed or were too slow.
• Abstraction Framework: It offers a pathway to abstract complex stochastic systems into caIMDPs while maintaining formal guarantees on the quality of the synthesized policy.

In summary, the paper bridges the gap between uncertain model-based control and continuous action spaces, providing a mathematically rigorous and computationally tractable solution for robust policy synthesis.