Parallel Stochastic Mirror Descent for MDPs

• URL: http://arxiv.org/abs/2103.00299v1
• Date: Sat, 27 Feb 2021 19:28:39 GMT
• Title: Parallel Stochastic Mirror Descent for MDPs
• Authors: Daniil Tiapkin, Fedor Stonyakin, Alexander Gasnikov
• Abstract summary: We consider the problem of learning the optimal policy for infinite-horizon Markov decision processes (MDPs) Some variant of Mirror Descent is proposed for convex programming problems with Lipschitz-continuous functionals. We analyze this algorithm in a general case and obtain an estimate of the convergence rate that does not accumulate errors during the operation of the method.
• Score: 72.75921150912556
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of learning the optimal policy for infinite-horizon Markov decision processes (MDPs). For this purpose, some variant of Stochastic Mirror Descent is proposed for convex programming problems with Lipschitz-continuous functionals. An important detail is the ability to use inexact values of functional constraints. We analyze this algorithm in a general case and obtain an estimate of the convergence rate that does not accumulate errors during the operation of the method. Using this algorithm, we get the first parallel algorithm for average-reward MDPs with a generative model. One of the main features of the presented method is low communication costs in a distributed centralized setting.

Related papers

• The Stochastic Conjugate Subgradient Algorithm For Kernel Support Vector Machines [1.738375118265695]
  This paper proposes an innovative method specifically designed for kernel support vector machines (SVMs) It not only achieves faster iteration per iteration but also exhibits enhanced convergence when compared to conventional SFO techniques. Our experimental results demonstrate that the proposed algorithm not only maintains but potentially exceeds the scalability of SFO methods.
  arXiv  Detail & Related papers  (2024-07-30T17:03:19Z)
• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  We consider the problem of optimizing second-order smooth and strongly convex functions where the algorithm is only accessible to noisy evaluations of the objective function it queries. We provide the first tight characterization for the rate of the minimax simple regret by developing matching upper and lower bounds.
  arXiv  Detail & Related papers  (2024-06-28T02:56:22Z)
• Stochastic Mirror Descent for Large-Scale Sparse Recovery [13.500750042707407]
  We discuss an application of quadratic Approximation to statistical estimation of high-dimensional sparse parameters. We show that the proposed algorithm attains the optimal convergence of the estimation error under weak assumptions on the regressor distribution.
  arXiv  Detail & Related papers  (2022-10-23T23:23:23Z)
• Efficient Global Planning in Large MDPs via Stochastic Primal-Dual Optimization [12.411844611718958]
  We show that our method outputs a near-optimal policy after a number of queries to the generative model. Our method is computationally efficient and comes with the major advantage that it outputs a single softmax policy that is compactly represented by a low-dimensional parameter vector.
  arXiv  Detail & Related papers  (2022-10-21T15:49:20Z)
• Efficient semidefinite bounds for multi-label discrete graphical models [6.226454551201676]
  One of the main queries on such models is to identify the SDPWCSP Function on Cost of a Posteri (MAP) Networks. We consider a traditional dualized constraint approach and a dedicated dedicated SDP/Monteiro style method based on row-by-row updates.
  arXiv  Detail & Related papers  (2021-11-24T13:38:34Z)
• Efficient semidefinite-programming-based inference for binary and multi-class MRFs [83.09715052229782]
  We propose an efficient method for computing the partition function or MAP estimate in a pairwise MRF. We extend semidefinite relaxations from the typical binary MRF to the full multi-class setting, and develop a compact semidefinite relaxation that can again be solved efficiently using the solver.
  arXiv  Detail & Related papers  (2020-12-04T15:36:29Z)
• Logistic Q-Learning [87.00813469969167]
  We propose a new reinforcement learning algorithm derived from a regularized linear-programming formulation of optimal control in MDPs. The main feature of our algorithm is a convex loss function for policy evaluation that serves as a theoretically sound alternative to the widely used squared Bellman error.
  arXiv  Detail & Related papers  (2020-10-21T17:14:31Z)
• 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)
• A Multi-Agent Primal-Dual Strategy for Composite Optimization over Distributed Features [52.856801164425086]
  We study multi-agent sharing optimization problems with the objective function being the sum of smooth local functions plus a convex (possibly non-smooth) coupling function.
  arXiv  Detail & Related papers  (2020-06-15T19:40:24Z)

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.