Mathematics of Operations Research

最新文章

• Exploration Noise for Learning Linear-Quadratic Mean Field Games AI翻译
  作者：Delarue, Francois; Vasileiadis, Athanasios
  作者单位：Universite Cote d'Azur; Centre National de la Recherche Scientifique (CNRS)
  摘要：The goal of this paper is to demonstrate that common noise may serve as an exploration noise for learning the solution of a mean field game. This concept is here exemplified through a toy linear-quadratic model, for which a suitable form of common noise has already been proven to restore existence and uniqueness. We here go one step further and prove that the same form of common noise may force the convergence of the learning algorithm called fictitious play, and this without any further poten...
• Fast Convergence of Frank-Wolfe Algorithms on Polytopes AI翻译
  作者：Wirth, Elias; Pena, Javier; Pokutta, Sebastian
  作者单位：Technical University of Berlin; Carnegie Mellon University; Zuse Institute Berlin
  摘要：We provide a template to derive affine-invariant convergence rates for the following popular versions of the Frank-Wolfe algorithm on polytopes: vanilla Frank-Wolfe, Frank-Wolfe with away steps, Frank-Wolfe with blended pairwise steps, and Frank-Wolfe with in-face directions. Our template shows how the convergence rates follow from two affine-invariant properties of the problem, namely, error bound and extended curvature. These properties depend solely on the polytope and objective function bu...
• Generalized Eluder Coefficient: A Unified Framework for Interactive Decision Making in Markov Decision Processes, Partially Observable Markov Decision Processes, and Beyond AI翻译
  作者：Zhong, Han; Xiong, Wei; Zheng, Sirui; Wang, Liwei; Wang, Zhaoran; Yang, Zhuoran; Zhang, Tong
  作者单位：Peking University; University of Illinois System; University of Illinois Urbana-Champaign; Northwestern University; Peking University; Yale University
  摘要：We study sample-efficient reinforcement learning (RL) under the general framework of interactive decision making, which includes the Markov decision process, partially observable Markov decision process, and predictive state representation (PSR) as special cases. We propose a novel complexity measure, the generalized eluder coefficient (GEC), which characterizes the fundamental trade-off between exploration and exploitation in online interactive decision making in the context of function appro...
• Learning Nonparametric Choice Models with Discrete Fourier Analysis AI翻译
  作者：Song, Haoyu; Nguyen, Hai; Nguyen, Thanh
  作者单位：Purdue University System; Purdue University; National University of Singapore; Purdue University System; Purdue University
  摘要：Nonparametric choice models offer broad applicability and robustness. However, the exponentially large parameter space leads practitioners to use heuristics for estimation. We introduce an alternative approach to modeling and estimating nonparametric choice models using discrete Fourier analysis. We demonstrate that any choice function can be approximated with a small number of Fourier parameters. Our sample-efficient, active-learning algorithms, without requiring an explicit model description...
• Many-Server Asymptotics for Join-the-Shortest-Queue in the Super-Halfin-Whitt Scaling Window AI翻译
  作者：Zhao, Zhisheng; Banerjee, Sayan; Mukherjee, Debankur
  作者单位：University System of Georgia; Georgia Institute of Technology; University of North Carolina; University of North Carolina Chapel Hill; University of North Carolina School of Medicine
  摘要：Join-the-shortest queue (JSQ) is a classical benchmark for the performance of parallel-server queueing systems because of its strong optimality properties. Recently, there has been significant progress in understanding its large-system asymptotic behavior. In this paper, we analyze the JSQ policy in the super-Halfin-Whitt scaling window when load per server scales with the system size N as lim(->infinity) (1 - ) = for is an element of (1/2, 1) and > 0. We establish that the centered and scaled...
• Improved Bounds for Single-Nomination Impartial Selection AI翻译
  作者：Cembrano, Javier; Fischer, Felix; Klimm, Max
  作者单位：Max Planck Society; Technical University of Berlin; University of London; Queen Mary University London
  摘要：A randomized selection mechanism returns a probability distribution over individuals based on mutual nominations among them; it is impartial if the selection probability of each individual is independent of the nominations they cast and alpha-optimal if the expected number of nominations received by the selected individual is always at least alpha times that received by any individual. When individuals can cast multiple nominations, the permutation mechanism is 1/2-optimal, and this is the bes...
• Tightness Without Counterexamples: A New Approach and New Results for Prophet Inequalities AI翻译
  作者：Jiang, Jiashuo; Ma, Will; Zhang, Jiawei
  作者单位：Hong Kong University of Science & Technology; Columbia University; New York University
  摘要：Prophet inequalities consist of many beautiful statements that establish tight performance ratios between online and offline allocation algorithms. Typically, tightness is established by constructing an algorithmic guarantee and a worst-case instance separately, whose bounds match as a result of some ingenuity. In this paper, we instead formulate the construction of the worst-case instance as an optimization problem, which directly finds the tight ratio without needing to construct two bounds ...
• Upper Bounds for All and Max-Gain Policy Iteration Algorithms on Deterministic MDPs AI翻译
  作者：Goenka, Ritesh; Gupta, Eashan; Khyalia, Sushil; Kalyanakrishnan, Shivaram
  作者单位：University of Oxford; University of Illinois System; University of Illinois Urbana-Champaign; Carnegie Mellon University; Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Bombay
  摘要：Policy iteration (PI) is a widely used family of algorithms to compute optimal policies for Markov decision problems (MDPs). Howard's [Howard RA (1960) Dynamic Programming and Markov Processes (MIT Press, Cambridge, MA)] PI is one of the most commonly used algorithms from this family. Despite its popularity, theoretical analysis of the running-time complexity of Howard's PI has remained elusive. For n-state, two-action MDPs, the best known lower and upper bounds are ohm(n) and O(2n/n) iteratio...
• Join-the-Shortest Queue with Abandonment: Critically Loaded and Heavily Overloaded Regimes AI翻译
  作者：Jhunjhunwala, Prakirt R.; Zubeldia, Martin; Maguluri, Siva Theja
  作者单位：Columbia University; University of Minnesota System; University of Minnesota Twin Cities; University System of Georgia; Georgia Institute of Technology
  摘要：We consider a load-balancing system composed of a fixed number of singleserver queues operating under the well-known join-the-shortest queue policy and where jobs/customers are impatient and abandon if they do not receive service after some (random) amount of time. In this setting, we characterize the centered and appropriately scaled steady-state queue-length distribution (hereafter referred to as limiting distribution) in the limit as the abandonment rate goes to zero at the same time as the...
• Well-Posedness and Sensitivity Analysis of a Fluid Model for Multiclass Many-Server Queues with Abandonment Under Global FCFS Discipline AI翻译
  作者：Kang, Weining
  作者单位：University System of Maryland; University of Maryland Baltimore County
  摘要：In this paper, under mild conditions on the arrival, service, and patience time distributions, we establish the well-posedness of the fluid model of a multiclass manyserver queueing model with differentiated service and patience times operated under the global FCFS service discipline. In particular, the well-posedness of the fluid model is established through the study of the existence and uniqueness of fixed points of a certain functional map of Volterra type. In addition, by showing a local ...