From Optimization to Control: Quasi Policy Iteration

• URL: http://arxiv.org/abs/2311.11166v2
• Date: Sun, 13 Oct 2024 18:03:23 GMT
• Title: From Optimization to Control: Quasi Policy Iteration
• Authors: Mohammad Amin Sharifi Kolarijani, Peyman Mohajerin Esfahani,
• Abstract summary: We introduce a novel control algorithm coined as quasi-policy iteration (QPI) QPI is based on a novel approximation of the "Hessian" matrix in the policy iteration algorithm by exploiting two linear structural constraints specific to MDPs. It exhibits an empirical convergence behavior similar to policy iteration with a very low sensitivity to the discount factor.
• Score: 3.4376560669160394
• License:
• Abstract: Recent control algorithms for Markov decision processes (MDPs) have been designed using an implicit analogy with well-established optimization algorithms. In this paper, we review this analogy across four problem classes with a unified solution characterization allowing for a systematic transformation of algorithms from one domain to the other. In particular, we identify equivalent optimization and control algorithms that have already been pointed out in the existing literature, but mostly in a scattered way. With this unifying framework in mind, we adopt the quasi-Newton method from convex optimization to introduce a novel control algorithm coined as quasi-policy iteration (QPI). In particular, QPI is based on a novel approximation of the "Hessian" matrix in the policy iteration algorithm by exploiting two linear structural constraints specific to MDPs and by allowing for the incorporation of prior information on the transition probability kernel. While the proposed algorithm has the same computational complexity as value iteration, it interestingly exhibits an empirical convergence behavior similar to policy iteration with a very low sensitivity to the discount factor.

Related papers

• Deterministic Trajectory Optimization through Probabilistic Optimal Control [3.2771631221674333]
  We propose two new algorithms for discrete-time deterministic finite-horizon nonlinear optimal control problems. Both algorithms are inspired by a novel theoretical paradigm known as probabilistic optimal control. We show that the application of this algorithm results in a fixed point of probabilistic policies that converge to the deterministic optimal policy.
  arXiv  Detail & Related papers  (2024-07-18T09:17:47Z)
• On Linear Convergence of PI Consensus Algorithm under the Restricted Secant Inequality [5.35599092568615]
  This paper considers solving distributed optimization problems in peer-to-peer multi-agent networks. By using the proportional-integral (PI) control strategy, various algorithms with fixed stepsize have been developed.
  arXiv  Detail & Related papers  (2023-09-30T15:54:52Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms. Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability. We propose a method for accelerating cutting-plane algorithms via reinforcement learning.
  arXiv  Detail & Related papers  (2023-07-17T20:11:56Z)
• Stochastic Ratios Tracking Algorithm for Large Scale Machine Learning Problems [0.7614628596146599]
  We propose a novel algorithm for adaptive step length selection in the classical SGD framework. Under reasonable conditions, the algorithm produces step lengths in line with well-established theoretical requirements. We show that the algorithm can generate step lengths comparable to the best step length obtained from manual tuning.
  arXiv  Detail & Related papers  (2023-05-17T06:22:11Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  We exploit between first-order algorithms for constrained optimization and non-smooth systems to design a new class of accelerated first-order algorithms. An important property of these algorithms is that constraints are expressed in terms of velocities instead of sparse variables.
  arXiv  Detail & Related papers  (2023-02-01T08:50:48Z)
• Reinforcement Learning with Unbiased Policy Evaluation and Linear Function Approximation [11.345796608258434]
  We provide performance guarantees for a variant of simulation-based policy iteration for controlling Markov decision processes. We analyze two algorithms; the first algorithm involves a least squares approach where a new set of weights associated with feature vectors is obtained via at least squares at each iteration. The second algorithm involves a two-time-scale approximation algorithm taking several steps of gradient descent towards the least squares solution.
  arXiv  Detail & Related papers  (2022-10-13T20:16:19Z)
• Adaptive First- and Second-Order Algorithms for Large-Scale Machine Learning [3.0204520109309843]
  We consider first- and second-order techniques to address continuous optimization problems in machine learning. In the first-order case, we propose a framework of transition from semi-deterministic to quadratic regularization methods. In the second-order case, we propose a novel first-order algorithm with adaptive sampling and adaptive step size.
  arXiv  Detail & Related papers  (2021-11-29T18:10:00Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  We consider the task of minimizing the sum of smooth and strongly convex functions stored in a decentralized manner across the nodes of a communication network. We design two optimal algorithms that attain these lower bounds. We corroborate the theoretical efficiency of these algorithms by performing an experimental comparison with existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-06-08T15:54:44Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  Maximum a posteriori (MAP) inference in discrete-valued random fields is a fundamental problem in machine learning. Due to the difficulty of this problem, linear programming (LP) relaxations are commonly used to derive specialized message passing algorithms. We present randomized methods for accelerating these algorithms by leveraging techniques that underlie classical accelerated gradient.
  arXiv  Detail & Related papers  (2020-07-01T18:43:32Z)
• A Dynamical Systems Approach for Convergence of the Bayesian EM Algorithm [59.99439951055238]
  We show how (discrete-time) Lyapunov stability theory can serve as a powerful tool to aid, or even lead, in the analysis (and potential design) of optimization algorithms that are not necessarily gradient-based. The particular ML problem that this paper focuses on is that of parameter estimation in an incomplete-data Bayesian framework via the popular optimization algorithm known as maximum a posteriori expectation-maximization (MAP-EM) We show that fast convergence (linear or quadratic) is achieved, which could have been difficult to unveil without our adopted S&C approach.
  arXiv  Detail & Related papers  (2020-06-23T01:34:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.