-
作者：Jin, Chi; Liu, Qinghua; Wang, Yuanhao; Yu, Tiancheng
作者单位：Princeton University; Princeton University; Massachusetts Institute of Technology (MIT)
摘要：A major challenge of multiagent reinforcement learning (MARL) is the curse of multiagents, where the size of the joint action space scales exponentially with the number of agents. This remains to be a bottleneck for designing efficient MARL algorithms, even in a basic scenario with finitely many states and actions. This paper resolves this challenge for the model of episodic Markov games. We design a new class of fully decentralized algorithms-V-learning, which provably learns Nash equilibria ...
-
作者：Nie, Jiawang; Yang, Zi
作者单位：University of California System; University of California San Diego; State University of New York (SUNY) System; University at Albany, SUNY
摘要：The multi-objective optimization is to optimize several objective functions over a common feasible set. Because the objectives usually do not share a common optimizer, people often consider (weakly) Pareto points. This paper studies multi-objective optimization problems that are given by polynomial functions. First, we study the geometry for (weakly) Pareto values and represent Pareto front as the boundary of a convex set. Linear scalarization problems (LSPs) and Chebyshev scalarization proble...
-
作者：Beideman, Calvin; Chandrasekaran, Karthekeyan; Wang, Weihang
作者单位：University of Illinois System; University of Illinois Urbana-Champaign
摘要：We consider the problem of enumerating optimal solutions for two hypergraph k-partitioning problems, namely, HYPERGRAPH-k-CUT and MINMAX-HYPERGRAPH-k-PARTITION. The input in hypergraph k-partitioning problems is a hypergraph G = (V, E) with positive hyperedge costs along with a fixed positive integer k. The goal is to find a partition of V into k nonempty parts (V1, V2, ..., Vk)-known as a k-partition-so as to minimize an objective of interest. (1) If the objective of interest is the maximum c...
-
作者：Kong, Siyu; Lewis, A. S.
作者单位：Cornell University
摘要：We study the impact of nonconvexity on the complexity of nonsmooth optimization, emphasizing objectives such as piecewise linear functions, which may not be weakly convex. We focus on a dimension-independent analysis, slightly modifying a 2020 black-box algorithm of Zhang-Lin-Jegelka-Sra-Jadbabaie that approximates an e-stationary point of any directionally differentiable Lipschitz objective using O(e-4) calls to a specialized subgradient oracle and a randomized line search. Seeking by contras...
-
作者：Chen, Xi; Kroer, Christian; Kumar, Rachitesh
作者单位：Columbia University
摘要：Budget constraints are ubiquitous in online advertisement auctions. To manage these constraints and smooth out the expenditure across auctions, the bidders (or the platform on behalf of them) often employ pacing: each bidder is assigned a pacing multiplier between zero and one, and her bid on each item is multiplicatively scaled down by the pacing multiplier. This naturally gives rise to a game in which each bidder strategically selects a multiplier. The appropriate notion of equilibrium in th...
-
作者：Basu, Ranojoy; Mukherjee, Conan
作者单位：Indian Institute of Management (IIM System); Indian Institute of Management Udaipur (IIMU); Indian Institute of Management (IIM System); Indian Institute of Management Calcutta
摘要：We consider direct mechanisms to sell heterogeneous objects when buyers have private additive valuations and nonunit demand. We completely characterize the class of strategy-proof and agent sovereign mechanisms that satisfy a local side-flatness condition. Further, we introduce a notion of continuity up to utility and show that any such mechanism allocating all objects at all profiles is continuous and anonymous only if it is efficient. We find that the only mechanism satisfying these properti...
-
作者：Pradhan, Somnath; Yueksel, Serdar
作者单位：Queens University - Canada
摘要：In control theory, typically a nominal model is assumed based on which an optimal control is designed and then applied to an actual (true) system. This gives rise to the problem of performance loss because of the mismatch between the true and assumed models. A robustness problem in this context is to show that the error because of the mismatch between a true and an assumed model decreases to zero as the assumed model approaches the true model. We study this problem when the state dynamics of t...
-
作者：Zhang, Penghe; Xiu, Naihua; Luo, Ziyan
作者单位：Beijing Jiaotong University
摘要：We consider the problem of minimizing the sum of a smooth function and a composition of a zero-one loss function with a linear operator, namely the zero-one composite optimization problem (0/1-COP). It has a vast body of applications, including the support vector machine (SVM), calcium dynamics fitting (CDF), one-bit compressive sensing (1-bCS), and so on. However, it remains challenging to design a globally convergent algorithm for the original model of 0/1-COP because of the nonconvex and di...
-
作者：Gast, Nicolas; Gaujal, Bruno; Yan, Chen
作者单位：Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); INRAE
摘要：We provide a framework to analyze control policies for the restless Markovian bandit model under both finite and infinite time horizons. We show that when the population of arms goes to infinity, the value of the optimal control policy converges to the solution of a linear program (LP). We provide necessary and sufficient conditions for a generic control policy to be (i) asymptotically optimal, (ii) asymptotically optimal with square root convergence rate, and (iii) asymptotically optimal with...
-
作者：Agrawal, Priyank; Balkanski, Eric; Gkatzelis, Vasilis; Ou, Tingting; Tan, Xizhi
作者单位：Columbia University; Drexel University
摘要：In this work, we introduce an alternative model for the design and analysis of strategyproof mechanisms that is motivated by the recent surge of work in learning augmented algorithms. Aiming to complement the traditional worst-case analysis approach in computer science, this line of work has focused on the design and analysis of algorithms that are enhanced with machine-learned predictions. The algorithms can use the predictions as a guide to inform their decisions, aiming to achieve much stro...
