Primal-Dual Algorithms for Optimization with Stochastic Dominance
Primal-Dual Algorithms for Optimization with Stochastic Dominance
复制标题
DOI：
10.1137/141001251
复制
发表时间：
2017-01
期刊：
影响因子：
--
通讯作者：
W. Haskell;J. Shanthikumar;Z. Shen
中科院分区：
文献类型：
--
作者：
W. Haskell;J. Shanthikumar;Z. Shen
随机优势是随机变量之间的成对比较，是随机优化中表达风险规避的有效工具。在本文中，我们开发了一族原始-对偶算法，用于随机优势约束优化问题。首先，我们开发了一个离线原始-对偶算法，并将其最优性间隙作为迭代次数的函数。然后，我们将该算法扩展到在线设置，其中每个决策时期只有一个随机样本。我们给出了概率界的最优间隙在此设置。这种技术也产生了一个在线算法的随机优势约束的多臂土匪部分反馈。本文最后讨论了一个具有鲁棒随机优势约束的批学习问题的对偶方法。
Stochastic dominance, a pairwise comparison between random variables, is an effective tool for expressing risk aversion in stochastic optimization. In this paper, we develop a family of primal-dual algorithms for optimization problems with stochastic dominance-constraints. First, we develop an offline primal-dual algorithm and bound its optimality gap as a function of the number of iterations. Then, we extend this algorithm to the online setting where only one random sample is given in each decision epoch. We give probabilistic bounds on the optimality gap in this setting. This technique also yields an online algorithm for the stochastic dominance-constrained multiarmed bandit with partial feedback. The paper concludes by discussing a dual approach for a batch learning problem with robust stochastic dominance constraints.