# Transition Uncertainties in Constrained Markov Decision Models: A Robust Optimization Approach

arXiv: https://arxiv.org/abs/2503.12238 · HTML: https://mlsanity.com/paper/2503.12238/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 4 of its 23 references that are in the map.
- First posted on arXiv 15 Mar 2025.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 4 of 4)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Robust Constrained Reinforcement Learning](https://mlsanity.com/paper/2209.06866/) (2022)
- [A Unified Theory of Robust and Distributionally Robust Optimization via the Primal-Worst-Equals-Dual-Best Principle](https://mlsanity.com/paper/2105.00760/) (2021)
- [On the convex formulations of robust Markov decision processes](https://mlsanity.com/paper/2209.10187/) (2022)

## Abstract (arXiv)

We examine a constrained Markov decision process under uncertain transition probabilities, with the uncertainty modeled as deviations from observed transition probabilities. We construct the uncertainty set associated with the deviations using polyhedral and second-order cone constraints and employ a robust optimization framework. We demonstrate that each inner optimization problem of the robust model can be equivalently transformed into a second-order cone programming problem. Using strong duality arguments, we show that the resulting robust problem can be equivalently reformulated into a second-order cone programming problem with bilinear constraints. In the numerical experiments, we study a machine replacement problem and explore potential sources of uncertainty in the transition probabilities. We examine how the optimal values and solutions differ as we vary the feasible region of the uncertainty set, considering only polyhedral constraints and a combination of polyhedral and second-order cone constraints. Furthermore, we analyze the impact of the number of states, the discount factor, and variations in the feasible region of the uncertainty set on the optimal values.