# On Tractability, Complexity, and Mixed-Integer Convex Programming Representability of Distributionally Favorable Optimization

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 21 of its 59 references that are in the map.
- First posted on arXiv 31 Jan 2024.

## 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, 21 of 21)

- [Data-driven Distributionally Robust Optimization Using the Wasserstein Metric: Performance Guarantees and Tractable Reformulations](https://mlsanity.com/paper/1505.05116/) (2015)
- [Distributionally Robust Logistic Regression](https://mlsanity.com/paper/1509.09259/) (2015)
- [Data-driven Inverse Optimization with Imperfect Information](https://mlsanity.com/paper/1512.05489/) (2015)
- [Optimistic Distributionally Robust Optimization for Nonparametric Likelihood Approximation](https://mlsanity.com/paper/1910.10583/) (2019)
- [Calculating Optimistic Likelihoods Using (Geodesically) Convex Optimization](https://mlsanity.com/paper/1910.07817/) (2019)
- [Robust Bayesian Classification Using an Optimistic Score Ratio](https://mlsanity.com/paper/2007.04458/) (2020)
- [Distributionally Robust Optimization with Decision Dependent Ambiguity Sets](https://mlsanity.com/paper/1806.09215/) (2018)
- [Optimistic Distributionally Robust Policy Optimization](https://mlsanity.com/paper/2006.07815/) (2020)
- [Robust Optimization with Decision-Dependent Information Discovery](https://mlsanity.com/paper/2004.08490/) (2020)
- [Optimization under Decision-Dependent Uncertainty](https://mlsanity.com/paper/1611.07992/) (2016)
- [Optimistic Robust Optimization With Applications To Machine Learning](https://mlsanity.com/paper/1711.07511/) (2017)
- [On sample average approximation for two-stage stochastic programs without relatively complete recourse](https://mlsanity.com/paper/1912.13078/) (2019)
- [A data-driven approach to beating SAA out-of-sample](https://mlsanity.com/paper/2105.12342/) (2021)
- [Polyhedral approximation in mixed-integer convex optimization](https://mlsanity.com/paper/1607.03566/) (2016)
- [Mixed-integer convex representability](https://mlsanity.com/paper/1706.05135/) (2017)
- [Convex Mixed-Integer Nonlinear Programs Derived from Generalized Disjunctive Programming using Cones](https://mlsanity.com/paper/2109.09657/) (2021)
- [Two-Stage Robust Optimization with Decision Dependent Uncertainty](https://mlsanity.com/paper/2203.16484/) (2022)
- [Rockafellian Relaxation and Stochastic Optimization under Perturbations](https://mlsanity.com/paper/2204.04762/) (2022)
- [ALSO-X#: Better Convex Approximations for Distributionally Robust Chance Constrained Programs](https://mlsanity.com/paper/2302.01737/) (2023)
- [Stochastic Lipschitz Dynamic Programming](https://mlsanity.com/paper/1905.02290/) (2019)
- [A Unified Framework for Adjustable Robust Optimization with Endogenous Uncertainty](https://mlsanity.com/paper/2007.00247/) (2020)

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

- [Performative Learning Theory](https://mlsanity.com/paper/2602.04402/) (2026)

## Abstract (arXiv)

Distributionally Favorable Optimization (DFO) is an important framework for decision-making under uncertainty, with applications across fields such as reinforcement learning, online learning, robust statistics, chance-constrained programming, and two-stage stochastic optimization without relatively complete recourse. In contrast to the traditional Distributionally Robust Optimization (DRO) paradigm, DFO presents a unique challenge -- the application of the inner infimum operator often fails to retain the convexity. In light of this challenge, we study the tractability and complexity of DFO. We establish sufficient and necessary conditions for determining when DFO problems are tractable or intractable. Despite the typical nonconvex nature of DFO problems, our findings show that they are mixed-integer convex programming representable (MICP-R), thereby enabling solutions via standard optimization solvers. Finally, we numerically validate the efficacy of our MICP-R formulations.