-
作者：Adamczyk, Marek; Sviridenko, Maxim; Ward, Justin
作者单位：Sapienza University Rome; Yahoo! Inc; University of Warwick
摘要：In a stochastic probing problem we are given a universe E, and a probability that each element e in E is active. We determine if an element is active by probing it, and whenever a probed element is active, we must permanently include it in our solution. Moreover, throughout the process we need to obey inner constraints on the set of elements taken into the solution, and outer constraints on the set of all probed elements. All previous algorithmic results in this framework have considered only ...
-
作者：Scherrer, Bruno
作者单位：Inria
摘要：Given a Markov decision process (MDP) with n states and a total number m of actions, we study the number of iterations needed by policy iteration (PI) algorithms to converge to the optimal gamma-discounted policy. We consider two variations of PI: Howard's PI that changes the actions in all states with a positive advantage, and Simplex-PI that only changes the action in the state with maximal advantage. We show that Howard's PI terminates after at most O((nm/(1-gamma))log(1/(1-gamma))) iterati...
-
作者：Mannor, Shie; Mebel, Ofir; Xu, Huan
作者单位：Technion Israel Institute of Technology; Alphabet Inc.; Google Incorporated; National University of Singapore
摘要：Markov decision processes are a common tool for modeling sequential planning problems under uncertainty. In almost all realistic situations, the system model cannot be perfectly known and must be approximated or estimated. Thus, we consider Markov decision processes under parameter uncertainty, which effectively adds a second layer of uncertainty. Most previous studies restrict to the case that uncertainties among different states are uncoupled, which leads to conservative solutions. On the ot...
-
作者：Tran, Ngoc Mai
作者单位：University of Texas System; University of Texas Austin
摘要：In the context of pairwise comparison ranking, we show that HodgeRank (row geometric mean), is the limit of Perron Rank (ranking with principal eigenvector) as a certain parameter k goes to 0. This result provides a novel mathematical link between two important pairwise ranking methods. It complements the known result that as k approaches infinity, Perron Rank converges to Tropical Rank. Thus, these three pairwise ranking methods belong to the same parametrized family. Our proof technique is u...
-
作者：Blanchet, Adrien; Carlier, Guillaume
作者单位：Universite de Toulouse; Universite Toulouse 1 Capitole; Toulouse School of Economics; Universite PSL; Universite Paris-Dauphine
摘要：We study a class of games with a continuum of players for which a Cournot-Nash equilibria can be obtained by the minimisation of some cost related to optimal transport. This cost is not convex in the usual sense, in general, but it turns out to have hidden strict convexity properties in many relevant cases. This enables us to obtain new uniqueness results and a characterisation of equilibria in terms of some partial differential equations, a simple numerical scheme in dimension one as well as ...
-
作者：Bauschke, Heinz H.; Hare, Warren L.; Moursi, Walaa M.
作者单位：University of British Columbia; Egyptian Knowledge Bank (EKB); Mansoura University
摘要：The problem of finding a minimizer of the sum of two convex functions-or, more generally, that of finding a zero of the sum of two maximally monotone operators-is of central importance in variational analysis. Perhaps the most popular method of solving this problem is the Douglas-Rachford splitting method. Surprisingly, little is known about the range of the Douglas-Rachford operator. In this paper, we set out to study this range systematically. We prove that for 3* monotone operators a very p...
-
作者：Wang, Bin; Wang, Ruodu
作者单位：Beijing Technology & Business University; University of Waterloo
摘要：Many optimization problems in probabilistic combinatorics and mass transportation impose fixed marginal constraints. A natural and open question in this field is to determine all possible distributions of the sum of random variables with given marginal distributions; the notion of joint mixability is introduced to address this question. A tuple of univariate distributions is said to be jointly mixable if there exist random variables, with respective distributions, such that their sum is a cons...
-
作者：Charpentier, Arthur; Galichon, Alfred; Henry, Marc
作者单位：University of Quebec; University of Quebec Montreal; Universite de Rennes; Institut d'Etudes Politiques Paris (Sciences Po); New York University; Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park
摘要：We revisit Machina's local utility as a tool to analyze attitudes to multivariate risks. We show that for nonexpected utility maximizers choosing between multivariate prospects, aversion to multivariate mean preserving increases in risk is equivalent to the concavity of the local utility functions, thereby generalizing Machina's result [Machina M (1982) Expected utility analysis without the independence axiom. Econometrica 50:277-323]. To analyze comparative risk attitudes within the multivari...
-
作者：Haskell, William B.; Jain, Rahul; Kalathil, Dileep
作者单位：National University of Singapore; University of Southern California; University of Southern California; University of Southern California; University of California System; University of California Berkeley
摘要：We propose empirical dynamic programming algorithms for Markov decision processes. In these algorithms, the exact expectation in the Bellman operator in classical value iteration is replaced by an empirical estimate to get empirical value iteration (EVI). Policy evaluation and policy improvement in classical policy iteration are also replaced by simulation to get empirical policy iteration (EPI). Thus, these empirical dynamic programming algorithms involve iteration of a random operator, the e...
-
作者：Li, Xiaoou; Liu, Jingchen; Xu, Gongjun
作者单位：Columbia University; University of Minnesota System; University of Minnesota Twin Cities
摘要：We develop asymptotic approximations for the tail probabilities of integrals of lognormal random fields. We consider the asymptotic regime that the variance of the random field converges to zero. Under this setting, the integral converges to its limiting value. This analysis is of interest in considering short-term portfolio risk analysis (such as daily performance), for which the variances of log-returns could be as small as a few percent.
