检索结果-内蒙古大学图书馆

Structured threshold policies for dynamic sensor scheduling - A partially observed Markov decision process approach

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2007年第10期55卷 4938-4957页

作者： Krishnamurthy, Vikram Djonin, Dejan V. Univ British Columbia Dept Elect & Comp Engn Vancouver BC V6T 1Z4 Canada Univ British Columbia Dyaptive Syst Inc Dept Elect & Comp Engn Vancouver BC V6T 1Z4 Canada

We consider the optimal sensor scheduling problem formulated as a partially observed Markov decision process (POMDP). Due to operational constraints, at each time instant, the scheduler can dynamically select one out of a finite number of sensors and record a noisy measurement of an underlying Markov chain. The aim is to compute the optimal measurement scheduling policy, so as to minimize a cost function comprising of estimation errors and measurement costs. The formulation results in a nonstandard POMDP that is nonlinear in the information state. We give sufficient conditions on the cost function, dynamics of the Markov chain and observation probabilities so that the optimal scheduling policy has a threshold structure with respect to a monotone likelihood ratio (MLR) ordering. As a result, the computational complexity of implementing the optimal scheduling policy is inexpensive. We then present stochastic approximation algorithms for estimating the best linear MLR order threshold policy.

关键词： bayesian filtering monotone likelihood ratio (MLR) ordering partially observed Markov decision processes (POMDPs) sensor scheduling stochastic approximation algorithms stochastic dynamic programming threshold policies

来源：评论

学校读者我要写书评

暂无评论

Quasi-Newton smoothed functional algorithms for unconstrained and constrained simulation optimization

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2017年第3期66卷 533-556页

作者： Lakshmanan, K. Bhatnagar, Shalabh Amrita Sch Engn Dept Comp Sci & Engn Bangalore 560035 Karnataka India Indian Inst Sci Dept Comp Sci & Automat Bangalore 560012 Karnataka India

We propose a multi-time scale quasi-Newton based smoothed functional (QN-SF) algorithm for stochastic optimization both with and without inequality constraints. The algorithm combines the smoothed functional (SF) scheme for estimating the gradient with the quasi-Newton method to solve the optimization problem. Newton algorithms typically update the Hessian at each instant and subsequently (a) project them to the space of positive definite and symmetric matrices, and (b) invert the projected Hessian. The latter operation is computationally expensive. In order to save computational effort, we propose in this paper a quasi-Newton SF (QN-SF) algorithm based on the Broyden-Fletcher-Goldfarb-Shanno (BFGS) update rule. In Bhatnagar (ACM TModel Comput S. 18(1): 27-62, 2007), a Jacobi variant of Newton SF (JN-SF) was proposed and implemented to save computational effort. We compare our QN-SF algorithm with gradient SF (G-SF) and JN-SF algorithms on two different problems - first on a simple stochastic function minimization problem and the other on a problem of optimal routing in a queueing network. We observe from the experiments that the QN-SF algorithm performs significantly better than both G-SF and JN-SF algorithms on both the problem settings. Next we extend the QN-SF algorithm to the case of constrained optimization. In this case too, the QN-SF algorithm performs much better than the JN-SF algorithm. Finally we present the proof of convergence for the QN-SF algorithm in both unconstrained and constrained settings.

关键词： Simulation stochastic optimization stochastic approximation algorithms Smoothed functional algorithm Quasi-Newton methods Constrained optimization Multi-stage queueing networks

来源：评论

学校读者我要写书评

暂无评论

Optimal multi-layered congestion based pricing schemes for enhanced QoS

引用

COMPUTER NETWORKS 2012年第4期56卷 1249-1262页

作者： Vemu, Koteswara Rao Bhatnagar, Shalabh Hemachandra, N. Indian Inst Sci Dept Comp Sci & Automat Bangalore 560012 Karnataka India Indian Inst Technol Dept Ind Engn & Operat Res Bombay 400076 Maharashtra India

Pricing is an effective tool to control congestion and achieve quality of service (QoS) provisioning for multiple differentiated levels of service. In this paper, we consider the problem of pricing for congestion control in the case of a network of nodes with multiple queues and multiple grades of service. We present a closed-loop multi-layered pricing scheme and propose an algorithm for finding the optimal state dependent price levels for individual queues, at each node. This is different from most adaptive pricing schemes in the literature that do not obtain a closed-loop state dependent pricing policy. The method that we propose finds optimal price levels that are functions of the queue lengths at individual queues. Further, we also propose a variant of the above scheme that assigns prices to incoming packets at each node according to a weighted average queue length at that node. This is done to reduce frequent price variations and is in the spirit of the random early detection (RED) mechanism used in TCP/IP networks. We observe in our numerical results a considerable improvement in performance using both of our schemes over that of a recently proposed related scheme in terms of both throughput and delay performance. In particular, our first scheme exhibits a throughput improvement in the range of 67-82% among all routes over the above scheme. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Optimal multi-layered pricing Closed loop feedback policies SPSA stochastic approximation algorithms Disutility

来源：评论

学校读者我要写书评

暂无评论

Strong diffusion approximations for recursive stochastic algorithms

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 1997年第2期43卷 512-523页

作者： PezeshkiEsfahani, H Heunis, AJ UNIV WATERLOO DEPT ELECT & COMP ENGNWATERLOOON N2L 3G1CANADA

Lai and Robbins prove strong diffusion approximations for the Robbins-Monro stochastic approximation algorithm. We show that similar strong approximations hold for stochastic algorithms at the level of generality proposed in the monograph of Benveniste, Metivier, and Priouret, wherein algorithms with generally discontinous right-hand sides driven by conditionally Markovian data are considered. The relevance of our result is demonstrated on an estimation algorithm with a discontinuous right-hand side which is used in data communication.

关键词： stochastic approximation algorithms invariance principles diffusion approximations

来源：评论

学校读者我要写书评

暂无评论

Analysis of Gradient Descent Methods With Nondiminishing Bounded Errors

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2018年第5期63卷 1465-1471页

作者： Ramaswamy, Arunselvan Bhatnagar, Shalabh Indian Inst Sci Dept Comp Sci & Automat Bengaluru 560012 Karnataka India

The main aim of this paper is to provide an analysis of gradient descent (GD) algorithms with gradient errors that do not necessarily vanish, asymptotically. In particular, sufficient conditions are presented for both stability (almost sure boundedness of the iterates) and convergence of GD with bounded (possibly) nondiminishing gradient errors. In addition to ensuring stability, such an algorithm is shown to converge to a small neighborhood of the minimum set, which depends on the gradient errors. It is worth noting that the main result of this paper can be used to show that GD with asymptotically vanishing errors indeed converges to the minimum set. The results presented herein are not only more general when compared to previous results, but our analysis of GD with errors is new to the literature to the best of our knowledge. Our work extends the contributions of Mangasarian and Solodov, Bertsekas and Tsitsiklis, and Tadic and Doucet. Using our framework, a simple yet effective implementation of GD using simultaneous perturbation stochastic approximations, with constant sensitivity parameters, is presented. Another important improvement over many previous results is that there are no "additional" restrictions imposed on the step sizes. In machine learning applications where step sizes are related to learning rates, our assumptions, unlike those of other papers, do not affect these learning rates. Finally, we present experimental results to validate our theory.

关键词： Differential inclusions (DIs) gradient descent (GD) methods nondiminishing errors stability and convergence stochastic approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

stochastic optimization of discrete event systems simulation

引用

MICROELECTRONICS AND RELIABILITY 1996年第10期36卷 1357-1368页

作者： Arsham, H Information and Quantitative Sciences Robert G. Merrick School of Business University of Baltimore Baltimore MD 21201-5779 U.S.A.

The Score Function (SF) method has been proposed to estimate the gradient of a performance measure with respect to some continuous parameters in a stochastic system. In this paper we experiment with the use of this estimate in a stochastic approximation algorithm to perform a single-run optimization. The experiment is done on a simple M/M/1 queue. The performance measure involves the average system time per customer at steady-state, and the decision variable is the service rate. The optimal solution is easy to compute analytically, which facilitates the evaluation of the algorithm. Combined with appropriate variance reduction techniques, the method has been shown to be effective in the test problem. We study the algorithm's properties and examine the validity of the estimates based on this single run procedure by performing some experimental studies. Implementation ''details'' necessary for packaging this method with existing simulation software are provided. Finally, there is a set of recommended directions for future research. Copyright (C) 1996 Elsevier Science Ltd

关键词： optimization of queueing and reliability models stochastic approximation algorithms score function method gradient estimation variance reduction Monte-Carlo experiments

来源：评论

学校读者我要写书评

暂无评论

Optimization Over Time-Varying Networks and Unbounded Information Delays

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2022年第8期67卷 4131-4137页

作者： Ramaswamy, Arunselvan Redder, Adrian Quevedo, Daniel E. Paderborn Univ Dept Comp Sci D-33098 Paderborn Germany Paderborn Univ Dept Comp Sci Comp Networks Grp D-33098 Paderborn Germany Queensland Univ Technol Sch Elect Engn & Robot Brisbane Qld 4000 Australia

Solving optimization problems in multiagent systems involves information exchange between agents. The obtained solutions should be robust to information delays and errors that arise from an unreliable wireless network, which typically connects the multiagent system. In today's large-scale dynamic Internet of Things style multiagent scenarios, the network topology changes and evolves over time. In this article, we present a simple distributed gradient-based optimization framework and an associated algorithm. Convergence to a minimum of a given objective is shown under mild conditions on the network topology and objective. A key feature of our approach is that we merely assume that the messages sent reach the intended receiver, possibly delayed, with some positive probability. To the best of authors' knowledge, ours is the first analysis under such weak general network conditions. We also discuss in detail the verifiability of the assumptions involved. This article also makes a technical contribution in terms of the allowed class of objective functions. Specifically, we present an analysis wherein the objective function is such that its sample-gradient is merely locally Lipschitz continuous. The theory developed herein is supported by empirical results.

关键词： Optimization Network topology Clocks Wireless networks Delays Topology stochastic processes Age-of-information (AoI) approximate distributed gradient methods distributed optimization stochastic approximation algorithms time-varying communication network topologies unbounded stochastic communication delays

来源：评论

学校读者我要写书评

暂无评论

On Information Distortions in Online Ratings

引用

OPERATIONS RESEARCH 2018年第3期66卷 597-610页

作者： Besbes, Omar Scarsini, Marco Columbia Univ Grad Sch Business New York NY 10027 USA LUISS Dipartimento Econ & Finanza I-00197 Rome Italy

Consumer reviews and ratings of products and services have become ubiquitous on the Internet. This paper analyzes, given the sequential nature of reviews and the limited feedback of such past reviews, the information content they communicate to future customers. We consider a model with heterogeneous customers who buy a product of unknown quality and we focus on two different informational settings. In the first setting, customers observe the whole history of past reviews. In the second one they only observe the sample mean of past reviews. We examine under which conditions, in each setting, customers can recover the true quality of the product based on the feedback they observe. In the case of total monitoring, if consumers adopt a fully rational Bayesian updating paradigm, then they asymptotically learn the unknown quality. With access to only the sample mean of past reviews, inference becomes intricate for customers and it is not clear if, when, and how social learning can take place. We first analyze the setting when customers interpret the mean as the proxy of quality. We show that in the long run, the sample mean of reviews stabilizes and, in general, customers overestimate the underlying quality of the product. We establish properties of the bias, stemming from the selection associated with observing only reviews of customers who purchase. Then, we show the existence of a simple non-Bayesian quality mference rule that leads to social learning when all customers use such a rule. The results point to the strong information content of even limited statistics of past reviews as long as customers have minimal sophistication.

关键词： online reviews quality inference sequential analysis social learning Bayesian updating stochastic approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Optimal Threshold Policies for Multivariate POMDPs in Radar Resource Management

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2009年第10期57卷 3954-3969页

作者： Krishnamurthy, Vikram Djonin, Dejan V. Univ British Columbia Dept Elect & Comp Engn Vancouver BC V6T 1Z4 Canada

This paper deals with the management of multimode sensors such as multifunction radars. We consider the problems of multitarget radar scheduling formulated as multivariate partially observed Markov decision process (POMDPs). The aim is to compute the scheduling policy to determine which target to choose and how long to continue with this choice so as to minimize a cost function. We give sufficient conditions on the cost function, dynamics of the Markov chain target and observation probabilities so that the optimal scheduling policy has a threshold structure with respect to the multivariate TP2 ordering. This implies that the optimal parameterized policy can be estimated efficiently. We then present stochastic approximation algorithms for estimating the best multilinear threshold policy.

关键词： Bayesian sensor scheduling multitarget tracking radar resource management stochastic approximation algorithms threshold policies totally positive (TP2) ordering

来源：评论

学校读者我要写书评

暂无评论

Stability of stochastic approximations With "Controlled Markov" Noise and Temporal Difference Learning

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2019年第6期64卷 2614-2620页

作者： Ramaswamy, Arunselvan Bhatnagar, Shalabh Indian Inst Sci Dept Comp Sci & Automat Bangalore 560012 Karnataka India Paderborn Univ Deparment Elect Engn & Informat Technol D-33908 Paderborn Germany Indian Inst Sci Robert Bosch Ctr Cyber Phys Syst Bangalore 560012 Karnataka India

We are interested in understanding stability (almost sure boundedness) of stochastic approximation algorithms (SAs) driven by a "controlled Markov" process. Analyzing this class of algorithms is important, since many reinforcement learning (RL) algorithms can be cast as SAs driven by a "controlled Markov" process. In this paper, we present easily verifiable sufficient conditions for stability and convergence of SAs driven by a "controlled Markov" process. Many RL applications involve continuous state spaces. While our analysis readily ensures stability for such continuous state applications, traditional analyses do not. As compared to literature, our analysis presents a two-fold generalization: 1) the Markov process may evolve in a continuous state space and 2) the process need not be ergodic under any given stationary policy. Temporal difference (TD) learning is an important policy evaluation method in RL. The theory developed herein, is used to analyze generalized TD(0), an important variant of TD. Our theory is also used to analyze a TD formulation of supervised learning for forecasting problems.

关键词： "Controlled Markov" noise convergence reinforcement learning (RL) stability stochastic approximation algorithms supervised learning TD(0) temporal difference (TD) learning

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：