1 September 2019 in Operations Research
Distributionally robust optimization has grown into one of the most popular approaches in addressing optimization under uncertainty. As its key ingredient, the ambiguity set specifies several types of distributional information about the ambiguous true distribution. In “Distributionally Robust Optimization with Infinitely Constrained Ambiguity Sets,” Z. Chen, M. Sim, and H. Xu contribute to the existing ambiguity sets in the literature, by proposing a new class of ambiguity sets that encompasses a potentially infinite number of expectation constraints. This class has the benefits of, among other things, a tighter approximation of stochastic independence that is ubiquitous in characterizing uncertainty. The authors propose an algorithm involving a greedy improvement procedure to solve the corresponding distributionally robust optimization problem. In their computational study, the authors are able to obtain significantly improved solutions using this algorithm.
5 January 2018 in IEEE Transactions on Automatic Control
We consider large-scale Markov decision processes (MDPs) with a time-consistent risk measure of variability in cost under the risk-aware MDP paradigm. Previous studies showed that risk-aware MDPs, based on a minimax approach to handling risk, can be solved using dynamic programming for small- to medium-sized problems. However, due to the “curse of dimensionality,” MDPs that model real-life problems are typically prohibitively large for such approaches. In this technical note, we employ an approximate dynamic programming approach and develop a family of simulation-based algorithms to approximately solve large-scale risk-aware MDPs with time-consistent risk measures. In parallel, we develop a unified convergence analysis technique to derive sample complexity bounds for this new family of algorithms.
1 February 2025 in Mathematics of Operations Research
We study the online saddle point problem, an online learning problem where at each iteration, a pair of actions needs to be chosen without knowledge of the current and future (convex-concave) payoff functions. The objective is to minimize the gap between the cumulative payoffs and the saddle point value of the aggregate payoff function, which we measure using a metric called saddle point regret (SP-Regret). The problem generalizes the online convex optimization framework, but here, we must ensure that both players incur cumulative payoffs close to that of the Nash equilibrium of the sum of the games. We propose an algorithm that achieves SP-Regret proportional to [ ] in the general case, and [ ] SP-Regret for the strongly convex-concave case. We also consider the special case where the payoff functions are bilinear and the decision sets are the probability simplex. In this setting, we are able to design algorithms that reduce the bounds on SP-Regret from a linear dependence in the dimension of the problem to a logarithmic one. We also study the problem under bandit feedback and provide an algorithm that achieves sublinear SP-Regret. We then consider an online convex optimization with knapsacks problem motivated by a wide variety of applications, such as dynamic pricing, auctions, and crowdsourcing. We relate this problem to the online saddle point problem and establish [ ] regret using a primal-dual algorithm.
7 February 2017 in Machine Learning
16 January 2019 in Journal of Optimization Theory and Applications