-
作者：So, Anthony Man-Cho; Ye, Yinyu; Zhang, Jiawei
作者单位：Chinese University of Hong Kong; Stanford University; New York University
摘要：We consider the problem of finding a low-rank approximate solution to a system of linear equations in symmetric, positive semidefinite matrices, where the approximation quality of a solution is measured by its maximum relative deviation, both above and below, from the prescribed quantities. We show that a simple randomized polynomial-time procedure produces a low-rank solution that has provably good approximation qualities. Our result provides a unified treatment of and generalizes several wel...
-
作者：Vladimirsky, Alexander
作者单位：Cornell University
摘要：Stochastic shortest path (SSP) problems arise in a variety of discrete stochastic control contexts. An optimal solution to such a problem is typically computed using the value function, which can be found by solving the corresponding dynamic programming equations. In the deterministic case, these equations can be often solved by highly efficient label-setting methods (such as Dijkstra's and Dial's algorithms). In this paper we de. ne and study a class of multimode stochastic shortest path (MSS...
-
作者：Lugosi, Gabor; Mannor, Shie; Stoltz, Gilles
作者单位：ICREA; Pompeu Fabra University; Pompeu Fabra University; McGill University; Universite PSL; Ecole Normale Superieure (ENS); Centre National de la Recherche Scientifique (CNRS); Centre National de la Recherche Scientifique (CNRS); Hautes Etudes Commerciales (HEC) Paris
摘要：We propose simple randomized strategies for sequential decision ( or prediction) under imperfect monitoring, that is, when the decision maker ( forecaster) does not have access to the past outcomes but rather to a feedback signal. The proposed strategies are consistent in the sense that they achieve, asymptotically, the best-possible average reward among all fixed actions. It was Rustichini [Rustichini, A. 1999. Minimizing regret: The general case. Games Econom. Behav. 29 224-243] who first pr...
-
作者：Helmes, Kurt; Roehl, Stefan
作者单位：Humboldt University of Berlin
摘要：We present a formula for the corner points of the multidimensional Hausdorff polytopes and show how this result can be used to improve linear programming models for computing, e.g., moments of exit time distributions of diffusion processes. Specifically, we compute the mean exit time of two-dimensional Brownian motion from the unit square, as well as higher moments of the exit time of time-space Brownian motion, i.e., the two-dimensional process composed of a one-dimensional Wiener process and...
-
作者：Jennings, Otis B.
作者单位：Duke University
摘要：We consider two serial single-server stations in heavy traffic. There are two job types: All jobs visit station I and then station 2. Station 1 processes jobs in an exhaustive service or gated service fashion; station 2 uses an arbitrary nonidling service discipline. Neither station incurs switchover delays. We prove two heavy-traffic limit theorems (HTLT) for the diffusion-scaled, two-dimensional total workload process: one for when the first station implements exhaustive service and the othe...
-
作者：Eisenbrand, Friedrich; Shmonin, Gennady
作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
摘要：Parametric integer programming deals with a family of integer programs that is defined by the same constraint matrix but where the right-hand sides are points of a given polyhedron. The question is whether all these integer programs are feasible. Kannan showed that this can be checked in polynomial time if the number of variables in the integer programs is fixed and the polyhedron of right-hand sides has fixed affine dimension. In this paper, we extend this result by providing a polynomial alg...
-
作者：Belloni, Alexandre
作者单位：Duke University
摘要：where K is a n-dimensional convex set that contains the origin, parameters t > 0 and p > 0, and vertical bar vertical bar.vertical bar vertical bar is any norm. We also develop connections between these densities and geometric properties of K such as diameter, width of the recession cone, and others. Since f(t) is log-concave only if p >= 1, this framework also covers nonlog-concave densities. Moreover, we establish a new set inclusion characterization for convex sets. This leads to a new conc...
-
作者：Basu, Arnab; Bhattacharyya, Tirthankar; Borkar, Vivek S.
作者单位：Indian Institute of Management (IIM System); Indian Institute of Management Bangalore; Indian Institute of Science (IISC) - Bangalore; Tata Institute of Fundamental Research (TIFR)
摘要：A linear function approximation-based reinforcement learning algorithm is proposed for Markov decision processes with infinite horizon risk-sensitive cost. Its convergence is proved using the o.d.e. method for stochastic approximation. The scheme is also extended to continuous state space processes.
-
作者：Basescu, Vasile L.; Mitchell, John E.
作者单位：Rensselaer Polytechnic Institute
摘要：We analyze the problem of finding a point strictly interior to a bounded, convex, and fully dimensional set from a finite dimensional Hilbert space. We generalize the results obtained for the linear programming ( LP), semide finite programming (SDP), and second-order core programming (SOCP) cases. The cuts added by our algorithm are central and conic. In our analysis, we find an upper bound for the number of Newton steps required to compute an approximate analytic center. Also, we provide an u...
-
作者：von Stengel, Bernhard; Forges, Francoise
作者单位：University of London; London School Economics & Political Science; Universite PSL; Universite Paris-Dauphine
摘要：This paper defines the extensive-form correlated equilibrium (EFCE) for extensive games with perfect recall. The EFCE concept extends Aumann's strategic-form correlated equilibrium (CE). Before the game starts, a correlation device generates a move for each information set. This move is recommended to the player only when the player reaches the information set. In two-player perfect-recall extensive games without chance moves, the set of EFCE can be described by a polynomial number of consiste...
