-
作者：Russo, Daniel
作者单位：Columbia University
摘要：This paper considers the optimal adaptive allocation of measurement effort for identifying the best among a finite set of options or designs. An experimenter sequentially chooses designs to measure and observes noisy signals of their quality with the goal of confidently identifying the best design after a small number of measurements. This paper proposes three simple and intuitive Bayesian algorithms for adaptively allocating measurement effort and formalizes a sense in which these seemingly n...
-
作者：Wang, Jinting; Wang, Zhongbin; Liu, Yunan
作者单位：Central University of Finance & Economics; Nankai University; Beijing Jiaotong University; North Carolina State University
摘要：In this article, we introduce a service grade differentiation policy for queueing models with customer retrials. We show that the average waiting time can be reduced through strategically allocating the rates of service and retrial times without needing additional service capacity. Countering to the intuition that higher service variability usually yields a larger delay, we show that the benefits of our simultaneous service-and-retrial differentiation policy outweigh the impact of the increase...
-
作者：Yang, Jiankui; Yao, David D.; Ye, Heng-Qing
作者单位：Beijing University of Posts & Telecommunications; Columbia University; Hong Kong Polytechnic University
摘要：The goal of this paper is to illustrate the optimality of reflection control in three different settings, to bring out their connections and to contrast their distinctions. First, we study the control of a Brownian motion with a negative drift, so as to minimize a long-run average cost objective. Weprove the optimality of the reflection control, which prevents the Brownian motion from dropping below a certain level by cancelling out from time to time part of the negative drift; and we show tha...
-
作者：Jiang, Daniel R.; Al-Kanj, Lina; Powell, Warren B.
作者单位：Pennsylvania Commonwealth System of Higher Education (PCSHE); University of Pittsburgh; Princeton University
摘要：Monte Carlo tree search (MCTS), most famously used in game-play artificial intelligence (e.g., the game of Go), is a well-known strategy for constructing approximate solutions to sequential decision problems. Its primary innovation is the use of a heuristic, known as a default policy, to obtain Monte Carlo estimates of downstream values for states in a decision tree. This information is used to iteratively expand the tree toward regions of states and actions that an optimal policy might visit....
-
作者：Xu, Kuang; Zhong, Yuan
作者单位：Stanford University; University of Chicago
摘要：We propose a general framework, dubbed stochastic processing under imperfect information, to study the impact of information constraints and memories on dynamic resource allocation. The framework involves a stochastic processing network (SPN) scheduling problem in which the scheduler may access the system state only through a noisy channel, and resource allocation decisions must be carried out through the interaction between an encoding policy (that observes the state) and allocation policy (t...
-
作者：Kleinert, Thomas; Labbe, Martine; Plein, Fraenk; Schmidt, Martin
作者单位：University of Erlangen Nuremberg; Universite Libre de Bruxelles; Universitat Trier
摘要：One of the most frequently used approaches to solve linear bilevel optimization problems consists in replacing the lower-level problem with its Karush-Kuhn-Tucker (KKT) conditions and by reformulating the KKT complementarity conditions using techniques from mixed-integer linear optimization. The latter step requires to determine some big-M constant in order to bound the lower level's dual feasible set such that no bilevel-optimal solution is cut off. In practice, heuristics are often used to f...
-
作者：Manshadi, Vahideh; Misra, Sidhant; Rodilitz, Scott
作者单位：Yale University; United States Department of Energy (DOE); Los Alamos National Laboratory
摘要：Motivated by viral marketing on social networks, we study the diffusion process of a new product on a network where each agent is connected to a random subset of others. The number of contacts (i.e., degree) varies across agents, and the firm knows the degree of each agent. Further, the firm can seed a fraction of the population and incurs a fixed cost per contact. Under any bounded degree distribution and for any target adoption proportion, we compute both the cost and the time it takes to re...
-
作者：Lei, Jinlong; Shanbhag, Uday, V
作者单位：Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park
摘要：The distributed computation of equilibria and optima has seen growing interest in a broad collection of networked problems. We consider the computation of Nash equilibria of convex stochastic noncooperative games characterized by a possibly non-convex potential function. Since any stationary point of the potential function is a Nash equilibrium, there is an equivalence between asynchronous best-response (BR) schemes applied on a noncooperative game and block-coordinate descent (BCD) schemes im...
-
作者：Nadarajah, Selvaprabu; Cire, Andre A.
作者单位：University of Illinois System; University of Illinois Chicago; University of Illinois Chicago Hospital; University of Toronto; University Toronto Scarborough; University of Toronto
摘要：We present relaxations for discrete optimization problems using approximate linear programs (ALPs) defined on multiple networks that represent different state-space aggregations. Our network ALP leverages information across these networks using a piecewise-constant value function approximation, and its optimistic bound is theoretically guaranteed to weakly improve upon the bounds from the individual networks used in its construction. Solving network ALPs is challenging because of its large num...
-
作者：Ma, Will; Simchi-Levi, David
作者单位：Columbia University; Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
摘要：Motivated by the dynamic assortment offerings and item pricings occurring in e-commerce, we study a general problem of allocating finite inventories to heterogeneous customers arriving sequentially. We analyze this problem under the framework of competitive analysis, where the sequence of customers is unknown and does not necessarily follow any pattern. Previous work in this area, studying online matching, advertising, and assortment problems, has focused on the case where each item can only b...
