# Distributionally Robust Optimization with Markovian Data

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 51 references that are in the map.
- First posted on arXiv 12 Jun 2021.

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

- [Data-driven Distributionally Robust Optimization Using the Wasserstein Metric: Performance Guarantees and Tractable Reformulations](https://mlsanity.com/paper/1505.05116/) (2015)
- [Statistics of Robust Optimization: A Generalized Empirical Likelihood Approach](https://mlsanity.com/paper/1610.03425/) (2016)
- [Wasserstein Distributionally Robust Optimization: Theory and Applications in Machine Learning](https://mlsanity.com/paper/1908.08729/) (2019)
- [Data-Driven Robust Optimization](https://mlsanity.com/paper/1401.0212/) (2013)
- [Distributionally Robust Optimization and Generalization in Kernel Methods](https://mlsanity.com/paper/1905.10943/) (2019)
- [Convergence Rate of Frank-Wolfe for Non-Convex Objectives](https://mlsanity.com/paper/1607.00345/) (2016)
- [Distributionally Robust Bayesian Optimization](https://mlsanity.com/paper/2002.09038/) (2020)
- [Efficiently Solving MDPs with Stochastic Mirror Descent](https://mlsanity.com/paper/2008.12776/) (2020)
- [Stochastic Frank-Wolfe Methods for Nonconvex Optimization](https://mlsanity.com/paper/1607.08254/) (2016)
- [Distributional Robustness and Regularization in Reinforcement Learning](https://mlsanity.com/paper/2003.02894/) (2020)
- [From Data to Decisions: Distributionally Robust Optimization is Optimal](https://mlsanity.com/paper/1704.04118/) (2017)
- [A Pareto Dominance Principle for Data-Driven Optimization](https://mlsanity.com/paper/2010.06606/) (2020)
- [Distributionally Robust Optimization with Correlated Data from Vector Autoregressive Processes](https://mlsanity.com/paper/1909.03433/) (2019)

## Built on by (most cited first, 4 of 4)

- [Policy Gradient Algorithms for Robust MDPs with Non-Rectangular Uncertainty Sets](https://mlsanity.com/paper/2305.19004/) (2023)
- [Wasserstein Distributionally Robust Optimization with Wasserstein Barycenters](https://mlsanity.com/paper/2203.12136/) (2022)
- [Towards Optimal Offline Reinforcement Learning](https://mlsanity.com/paper/2503.12283/) (2025)
- [Wasserstein Distributionally Robust Multiclass Support Vector Machine](https://mlsanity.com/paper/2409.08409/) (2024)

## Abstract (arXiv)

We study a stochastic program where the probability distribution of the uncertain problem parameters is unknown and only indirectly observed via finitely many correlated samples generated by an unknown Markov chain with d states. We propose a data-driven distributionally robust optimization model to estimate the problem's objective function and optimal solution. By leveraging results from large deviations theory, we derive statistical guarantees on the quality of these estimators. The underlying worst-case expectation problem is nonconvex and involves mathcal O(d2) decision variables. Thus, it cannot be solved efficiently for large d. By exploiting the structure of this problem, we devise a customized Frank-Wolfe algorithm with convex direction-finding subproblems of size mathcal O(d). We prove that this algorithm finds a stationary point efficiently under mild conditions. The efficiency of the method is predicated on a dimensionality reduction enabled by a dual reformulation. Numerical experiments indicate that our approach has better computational and statistical properties than the state-of-the-art methods.