Introduction
Standard Markov Decision Processes (MDPs) typically focus on minimizing expected costs, an approach known as "risk-neutral" optimization. While mathematically convenient, this framework often ignores the impact of rare but catastrophic events—a critical oversight for high-stakes autonomous systems like Mars rovers. In such environments, robots must not only navigate efficiently but also manage "tail risk" while adhering to strict resource constraints, such as limited fuel or communication budgets.
This paper introduces a unified framework for solving constrained risk-averse MDPs. By combining coherent risk measures with hard safety constraints, the authors provide a theoretically sound and computationally scalable method for synthesizing robust policies in uncertain environments.
Methodology
The core challenge in constrained risk-averse MDPs is the non-convex nature of the optimization problem when general risk measures are applied. The authors address this through a multi-step optimization framework:
- Lagrangian Formulation: The constrained problem is converted into an unconstrained "inf-sup" problem using Lagrange multipliers.
- Markov Risk Transition Mapping: By assuming risk measures satisfy a "Markov" property, the problem is decomposed into stage-wise decisions, enabling a Bellman-like recursive structure.
- Difference Convex Programming (DCP): The authors prove that the resulting optimization can be formulated as a Difference Convex Program—a class of problems where the objective and constraints are differences of two convex functions.
- DCCP Solver: The framework utilizes Disciplined Convex-Concave Programming (DCCP) to linearize concave components, finding local saddle points that provide a guaranteed lower bound to the optimal risk-averse value.
The framework specifically highlights two risk measures: Conditional Value-at-Risk (CVaR), which averages the worst-case outcomes, and Entropic Value-at-Risk (EVaR), a more conservative and computationally smoother measure.
Experimental Evaluation
The proposed method was evaluated using a simulated Mars rover navigation task set in the Eberswalde Crater. The environment consists of a grid-world (ranging from $10\times10$ to $20\times20$) where the rover must reach a goal while staying within a fuel budget and avoiding hazards.
To simulate real-world uncertainty, the environment includes "uncertain obstacles"—hazards that randomly shift position with a 20% probability. This forces the policy to account for potential state changes that a risk-neutral policy might ignore.
Results and Discussion
The study compared three policy types: Total Expectation (Risk-Neutral), CVaR, and EVaR. The results demonstrate that risk-averse policies significantly improve safety without violating resource constraints.
| Metric | Total Expectation | CVaR ($\epsilon=0.15$) | EVaR ($\epsilon=0.15$) |
|---|---|---|---|
| Failure Rate (20x20 grid) | 21% | 5% | 2% |
| Solve Time (s) | 1.6s | 10.5s | 6.6s |
As shown in the table, EVaR achieved the lowest failure rate, reducing catastrophic outcomes by a factor of ten compared to the risk-neutral baseline. Visually, the risk-averse policies exhibit distinct behaviors, steering the robot significantly further away from clusters of uncertain obstacles, even at the cost of a longer path.
Key insights from the evaluation include:
- EVaR Efficiency: Despite being more conservative, EVaR was often more computationally efficient to solve than CVaR, making it a strong candidate for real-time robotics.
- Safety Guarantees: The DCP approach provides a valid lower bound on the true risk-averse value, ensuring that the system does not dangerously underestimate potential hazards.
Conclusion and Future Work
This work provides a scalable optimization-based approach for robots operating under uncertainty and resource limits. While the current framework handles infinite-horizon problems with full observability, future research will focus on extending these methods to Partially Observable MDPs (POMDPs) to account for sensor noise and more complex mission specifications like Linear Temporal Logic.
Summary updated