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

approximate linear programming for decentralized policy iteration in cooperative multi-agent Markov decision processes

引用

SYSTEMS & CONTROL LETTERS 2025年 196卷

作者： Mandal, Lakshmi Lakshminarayanan, Chandrashekar Bhatnagar, Shalabh Indian Inst Sci Dept Comp Sci & Automat Bangalore 560012 India Indian Inst Technol Madras Dept Comp Sci & Engn Chennai 600036 India

In this work, we consider a 'cooperative' multi-agent Markov decision process (MDP) involving m ( > 1) agents. At each decision epoch, all the m agents independently select actions in order to minimize a common long-term cost objective. In the policy iteration process of multi-agent setup, the number of actions grows exponentially with the number of agents, incurring huge computational costs. Thus, recent works consider decentralized policy improvement, where each agent improves its decisions unilaterally, assuming that the decisions of the other agents are fixed. However, exact value functions are considered in the literature, which is computationally expensive for a large number of agents with high dimensional state-action space. Thus, we propose approximate decentralized policy iteration algorithms, using approximate linear programming with function approximation to compute the approximate value function for decentralized policy improvement. Further, we consider (both) cooperative multi-agent finite and infinite horizon discounted MDPs and propose suitable algorithms in each case. Moreover, we provide theoretical guarantees for our algorithms and also demonstrate their advantages over existing state-of-the-art algorithms in the literature.

关键词： Markov decision process Cooperative multi-agent systems approximate linear programming Policy iteration

来源：评论

学校读者我要写书评

暂无评论

approximate linear programming for a queueing control problem

引用

COMPUTERS & OPERATIONS RESEARCH 2024年 169卷

作者： Samiedaluie, Saied Zhang, Dan Zhang, Rui Univ Alberta Alberta Sch Business Edmonton AB Canada Univ Colorado Leeds Sch Business Boulder CO 80309 USA

Admission decisions for loss systems accessed by multiple customer classes are a classical queueing control problem with a wide variety of applications. When a server is available, the decision is whether to admit an arriving customer and collect a lump-sum revenue. The system can be modeled as a continuous-time infinite-horizon dynamic program, but suffers from the curse of dimensionality when different customer classes have different service rates. We use approximate linear programming to solve the problem under three approximation architectures: affine, separable piecewise linear and finite affine. The finite affine approximation is a recently proposed generalization of the affine approximation, which allows for non-stationary parameters. For both affine and finite affine approximations, we derive equivalent, but more compact, formulations that can be efficiently solved. We propose a column generation algorithm for the separable piecewise linear approximation. Our numerical results show that the finite affine approximation can obtain the tightest bounds for 75% of the instances among the three approximations. Especially, when the number of servers is large and/or the load on the system is high, the finite affine approximation always achieves the tightest bounds. Regarding policy performance, the finite affine approximation has the best performance on average compared to the other two approximations and the achievable performance region method (Bertsimaset al., 1994, Kumar and Kumar, 1994). Furthermore, the finite affine approximation is 4 to 5 orders of magnitude faster than the achievable performance region method and the separable piecewise linear approximation for large-scale instances. Therefore, considering bounds, policy performance, and computational efficiency, the finite affine approximation emerges as a competitive approximation architecture for the class of problems studied here.

关键词： Dynamic programming Queues approximate linear programming Admission

来源：评论

学校读者我要写书评

暂无评论

Revisiting approximate linear programming: Constraint-Violation Learning with Applications to Inventory Control and Energy Storage

引用

MANAGEMENT SCIENCE 2020年第4期66卷 1544-1562页

作者： Lin, Qihang Nadarajah, Selvaprabu Soheili, Negar Univ Iowa Tippie Coll Business Iowa City IA 52242 USA Univ Illinois Coll Business Adm Chicago IL 60607 USA

approximate linear programs (ALPs) are well-known models for computing value function approximations (VFAs) of intractable Markov decision processes (MDPs). VFAs from ALPs have desirable theoretical properties, define an operating policy, and provide a lower bound on the optimal policy cost. However, solving ALPs near-optimally remains challenging, for example, when approximating MDPs with nonlinear cost functions and transition dynamics or when rich basis functions are required to obtain a good VFA. We address this tension between theory and solvability by proposing a convex saddle-point reformulation of an ALP that includes as primal and dual variables, respectively, a vector of basis function weights and a constraint violation density function over the state-action space. To solve this reformulation, we develop a proximal stochastic mirror descent (PSMD) method that learns regions of high ALP constraint violation via its dual update. We establish that PSMD returns a near-optimal ALP solution and a lower bound on the optimal policy cost in a finite number of iterations with high probability. We numerically compare PSMD with several benchmarks on inventory control and energy storage applications. We find that the PSMD lower bound is tighter than a perfect information bound. In contrast, the constraint-sampling approach to solve ALPs may not provide a lower bound, and applying row generation to tackle ALPs is not computationally viable. PSMD policies outperform problem-specific heuristics and are comparable or better than the policies obtained using constraint sampling. Overall, our ALP reformulation and solution approach broadens the applicability of approximate linear programming.

关键词： approximate linear programming approximate dynamic programming stochastic gradient descent Inventory control energy storage

来源：评论

学校读者我要写书评

暂无评论

Network-Based approximate linear programming for Discrete Optimization

引用

OPERATIONS RESEARCH 2020年第6期68卷 1767-1786页

作者： Nadarajah, Selvaprabu Cire, Andre A. Univ Illinois Coll Business Adm Chicago IL 60607 USA Univ Toronto Scarborough Dept Management Toronto ON M1C 1A4 Canada Rotman Sch Management Toronto ON M1C 1A4 Canada

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 number of constraints-a well-known issue when employing approximate linear programming. We sidestep this issue by using a clique-based graph representation to design a network ALP restriction that admits a polynomial-time solvable extended formulation, which we show to also deliver a weakly better bound than individual networks. We execute a computational study on a challenging bilinear problem arising in marketing analytics and a routing application encountered in the preemptive maintenance of energy or city-owned assets. When used within a branch-and-bound scheme, the network ALP restriction significantly outperforms in both solution quality and time the following benchmarks: a state-of-the-art mathematical programming solver, a generic aggregation/disaggregation scheme applied to a single network, and a heuristic that chooses the best bound among individual networks.

关键词： discrete optimization approximate linear programming state-space aggregation networks dynamic programming

来源：评论

学校读者我要写书评

暂无评论

Relationship between least squares Monte Carlo and approximate linear programming

引用

OPERATIONS RESEARCH LETTERS 2017年第5期45卷 409-414页

作者： Nadarajah, Selvaprabu Secomandi, Nicola Univ Illinois Coll Business Adm 601 South Morgan St Chicago IL 60607 USA Carnegie Mellon Univ Tepper Sch Business 5000 Forbes Ave Pittsburgh PA 15213 USA

Least squares Monte Carlo (LSM) is commonly used to manage and value early or multiple exercise financial or real options. Recent research in this area has started applying approximate linear programming (ALP) and its relaxations, which aim at addressing a possible ALP drawback. We show that regress-later LSM is itself an ALP relaxation that potentially corrects this ALP shortcoming. Our analysis consolidates two streams of research and supports using this LSM version rather than ALP on the considered models. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Markov decision processes approximate dynamic programming Least squares Monte Carlo approximate linear programming Financial and real options Energy storage

来源：评论

学校读者我要写书评

暂无评论

Efficient approximate linear programming for factored MDPs

引用

INTERNATIONAL JOURNAL OF approximate REASONING 2015年 63卷 101-121页

作者： Chen, Feng Cheng, Qiang Dong, Jianwu Yu, Zhaofei Wang, Guojun Xu, Wenli Tsinghua Univ Dept Automat Ctr Brain Inspired Comp Res Beijing 100084 Peoples R China Beijing Key Lab Secur Big Data Proc & Applicat Beijing Peoples R China Nanjing Res Inst Elect Technol Nanjing Jiangsu Peoples R China Nanjing Univ Sch Management & Engn Nanjing 210008 Jiangsu Peoples R China

Factored Markov Decision Processes (MDPs) provide a compact representation for modeling sequential decision making problems with many variables. approximate linear programming (LP) is a prominent method for solving factored MDPs. However, it cannot be applied to models with large treewidth due to the exponential number of constraints. This paper proposes a novel and efficient approximate method to represent the exponentially many constraints. We construct an augmented junction graph from the factored MDP, and represent the constraints using a set of cluster constraints and separator constraints, where the cluster constraints play the role of reducing the number of constraints, and the separator constraints enforce the consistency of neighboring clusters so as to improve the accuracy. In the case where the junction graph is tree-structured, our method provides an equivalent representation to the original constraints. In other cases, our method provides a good trade-off between computation and accuracy. Experimental results on different models show that our algorithm performs better than other approximate linear programming algorithms on computational cost or expected reward. (C) 2015 Elsevier Inc. All rights reserved.

关键词： Factored MDPs approximate linear programming Junction graph Cluster constraints

来源：评论

学校读者我要写书评

暂无评论

approximate linear programming for Average Cost MDPs

引用

MATHEMATICS OF OPERATIONS RESEARCH 2013年第3期38卷 535-544页

作者： Veatch, Michael H. Gordon Coll Dept Math Wenham MA 01984 USA

We consider the linear programming approach to approximate dynamic programming with an average cost objective and a finite state space. Using a Lagrangian form of the linear program (LP), the average cost error is shown to be a multiple of the best fit differential cost error. This result is analogous to previous error bounds for a discounted cost objective. Second, bounds are derived for average cost error and performance of the policy generated from the LP that involve the mixing time of the Markov decision process (MDP) under this policy or the optimal policy. These results improve on a previous performance bound involving mixing times.

关键词： approximate dynamic programming average cost Markov decision processes approximate linear programming

来源：评论

学校读者我要写书评

暂无评论

Self-Guided approximate linear Programs: Randomized Multi-Shot Approximation of Discounted Cost Markov Decision Processes

引用

MANAGEMENT SCIENCE 2025年第4期71卷 iv-vi, 2751-3636页

作者： Pakiman, Parshan Nadarajah, Selvaprabu Soheili, Negar Lin, Qihang Univ Illinois Coll Business Adm Chicago IL 60607 USA Univ Iowa Tippie Coll Business Iowa City IA 52242 USA

approximate linear programs (ALPs) are well-known models based on value function approximations (VFAs) to obtain policies and lower bounds on the optimal policy cost of discounted-cost Markov decision processes (MDPs). Formulating an ALP requires (i) basis functions, the linear combination of which defines the VFA, and (ii) a state relevance distribution, which determines the relative importance of different states in the ALP objective for the purpose of minimizing VFA error. Both of these choices are typically heuristic;basis function selection relies on domain knowledge, whereas the state-relevance distribution is specified using the frequency of states visited by a baseline policy. We propose a self-guided sequence of ALPs that embeds random basis functions obtained via inexpensive sampling and uses the known VFA from the previous iteration to guide VFA computation in the current iteration. In other words, this sequence takes multiple shots randomly approximating the MDP value function with VFA-based guidance between consecutive approximation attempts. Self-guided ALPs mitigate domain knowledge during basis function selection and the impact of the state-relevance-distribution choice, thus reducing the ALP implementation burden. We establish high-probability error bounds on the VFAs from this sequence and show that a worst-case measure of policy performance improved. We find that these favorable implementation and theoretical properties translate to encouraging numerical results on perishable inventory control and options pricing applications, where self-guided ALP policies improve upon policies from problem-specific methods. More broadly, our research takes a meaningful step toward application-agnostic policies and bounds for MDPs.

关键词： approximate linear programming random features Markov decision processes approximate dynamic programming reinforcement learning inventory control options pricing

来源：评论

学校读者我要写书评

暂无评论

Efficient compact linear programs for network revenue management

引用

OPTIMIZATION LETTERS 2023年第2期17卷 437-451页

作者： Laumer, Simon Univ Zurich Dept Business Adm Plattenstr 14 CH-8032 Zurich Switzerland

We are concerned with computing bid prices in network revenue management using approximate linear programming. It is well-known that affine value function approximations yield bid prices which are not sensitive to remaining capacity. The analytic reduction to compact linear programs allows the efficient computation of such bid prices. On the other hand, capacity-dependent bid prices can be obtained using separable piecewise linear value function approximations. Even though compact linear programs have been derived for this case also, they are still computationally much more expensive compared to using affine functions. We propose compact linear programs requiring substantially smaller computing times while, simultaneously, significantly improving the performance of capacity-independent bid prices. This simplification is achieved by taking into account remaining capacity only if it becomes scarce. Although our proposed linear programs are relaxations of the unreduced approximate linear programs, we conjecture equivalence and provide according numerical support. We measure the quality of an approximation by the difference between the expected performance of an induced policy and the corresponding theoretical upper bound. Using this paradigm in numerical experiments, we demonstrate the competitiveness of our proposed linear programs.

关键词： Network revenue management approximate dynamic programming approximate linear programming Reductions

来源：评论

学校读者我要写书评

暂无评论

Cyclic Cleaning Scheduling of Industrial Boiler Based on Steepest Descent approximate linear programming

引用

IFAC Proceedings Volumes 2013年第13期46卷 478-483页

作者： Yan Zhaoyang Ma Xin Gao Dong Liu Pingping Zhang Beike College of Information Science and Technology Beijing University of Chemical Technology Beijing China

In this paper, the planning for the multi-period cleaning of an industrial boiler is formulated as a mixed-integer nonlinear program (MINLP). The objective function accounted for both the cost of fuel consumption and boiler cleaning & maintenance costs. And a subsection method was proposed for solving the MINLP problem using the steepest descent approximate linear programming (SDALP), which exhibits the advantages of the approximate linear programming (ALP) algorithm, such as easy implementation and convenient solution, and then introduces the principle of purposeful search and rapid convergence via the steepest descent method. This new method can eliminate the negative effect of the subjective step restriction and reduction coefficient, improve the convergence speed, and enhance the solution accuracy. The computation time for the method was proportional to the number of periods, and global solution of the MINLP was guaranteed. At last, the effectiveness of the proposed method was illustrated with an example.

关键词： cyclic cleaning of industrial boiler scheduling algorithm steepest descent approximate linear programming mixed-integer nonlinear programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：