Weighted mesh algorithms for general Markov decision processes: Convergence and tractability

• URL: http://arxiv.org/abs/2407.00388v1
• Date: Sat, 29 Jun 2024 10:08:23 GMT
• Title: Weighted mesh algorithms for general Markov decision processes: Convergence and tractability
• Authors: Denis Belomestny, John Schoenmakers,
• Abstract summary: We introduce a mesh-type approach for tackling discrete-time, finite-horizon Markov Decision Processes (MDPs) For unbounded state space the algorithm is "semi-tractable" in the sense that the complexity is $epsilonc$ with some dimension independent $cgeq2$.
• Score: 0.9940462449990576
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce a mesh-type approach for tackling discrete-time, finite-horizon Markov Decision Processes (MDPs) characterized by state and action spaces that are general, encompassing both finite and infinite (yet suitably regular) subsets of Euclidean space. In particular, for bounded state and action spaces, our algorithm achieves a computational complexity that is tractable in the sense of Novak and Wozniakowski, and is polynomial in the time horizon. For unbounded state space the algorithm is "semi-tractable" in the sense that the complexity is proportional to $\epsilon^{-c}$ with some dimension independent $c\geq2$, for achieving an accuracy $\epsilon$, and polynomial in the time horizon with degree linear in the underlying dimension. As such the proposed approach has some flavor of the randomization method by Rust which deals with infinite horizon MDPs and uniform sampling in compact state space. However, the present approach is essentially different due to the finite horizon and a simulation procedure due to general transition distributions, and more general in the sense that it encompasses unbounded state space. To demonstrate the effectiveness of our algorithm, we provide illustrations based on Linear-Quadratic Gaussian (LQG) control problems.

Related papers

• Convergence and complexity of block majorization-minimization for constrained block-Riemannian optimization [20.128697661112618]
  Blockization-minimization (BMM) is a simple iterative gradient for non-exhaustive subspace estimation. Our analysis makes explicit use of Euclidian constraints.
  arXiv  Detail & Related papers  (2023-12-16T05:40:19Z)
• GRAPE optimization for open quantum systems with time-dependent decoherence rates driven by coherent and incoherent controls [77.34726150561087]
  The GRadient Ascent Pulse Engineering (GRAPE) method is widely used for optimization in quantum control. We adopt GRAPE method for optimizing objective functionals for open quantum systems driven by both coherent and incoherent controls. The efficiency of the algorithm is demonstrated through numerical simulations for the state-to-state transition problem.
  arXiv  Detail & Related papers  (2023-07-17T13:37:18Z)
• Complexity of Block Coordinate Descent with Proximal Regularization and Applications to Wasserstein CP-dictionary Learning [1.4010916616909743]
  We consider the block coordinate descent of Gauss-Sdel type with regularization (BCD-PR) We show that an W(W(W(W(W(W(W(W(W(W(W(W(W(W(W(W(W(W(W(W(W(W(W(W(W(W(W(W(W(W(W(W(
  arXiv  Detail & Related papers  (2023-06-04T17:52:49Z)
• Markovian Sliced Wasserstein Distances: Beyond Independent Projections [51.80527230603978]
  We introduce a new family of SW distances, named Markovian sliced Wasserstein (MSW) distance, which imposes a first-order Markov structure on projecting directions. We compare distances with previous SW variants in various applications such as flows, color transfer, and deep generative modeling to demonstrate the favorable performance of MSW.
  arXiv  Detail & Related papers  (2023-01-10T01:58:15Z)
• Computationally Efficient PAC RL in POMDPs with Latent Determinism and Conditional Embeddings [97.12538243736705]
  We study reinforcement learning with function approximation for large-scale Partially Observable Decision Processes (POMDPs) Our algorithm provably scales to large-scale POMDPs.
  arXiv  Detail & Related papers  (2022-06-24T05:13:35Z)
• Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
  We present a framework for constructing mixing operators that restrict the evolution to a subspace of the full Hilbert space. We generalize the "XY"-mixer designed to preserve the subspace of "one-hot" states to the general case of subspaces given by a number of computational basis states. Our analysis also leads to valid Trotterizations for "XY"-mixer with fewer CX gates than is known to date.
  arXiv  Detail & Related papers  (2022-03-11T17:19:26Z)
• Bounds on quantum evolution complexity via lattice cryptography [0.0]
  We address the difference between integrable and chaotic motion in quantum theory as manifested by the complexity of the corresponding evolution operators. Complexity is understood here as the shortest geodesic distance between the time-dependent evolution operator and the origin within the group of unitaries.
  arXiv  Detail & Related papers  (2022-02-28T16:20:10Z)
• Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable Approach for Continuous Markov Random Fields [53.31927549039624]
  We show that a piecewise discretization preserves better contrast from existing discretization problems. We apply this theory to the problem of matching two images.
  arXiv  Detail & Related papers  (2021-07-13T12:31:06Z)
• Local optimization on pure Gaussian state manifolds [63.76263875368856]
  We exploit insights into the geometry of bosonic and fermionic Gaussian states to develop an efficient local optimization algorithm. The method is based on notions of descent gradient attuned to the local geometry. We use the presented methods to collect numerical and analytical evidence for the conjecture that Gaussian purifications are sufficient to compute the entanglement of purification of arbitrary mixed Gaussian states.
  arXiv  Detail & Related papers  (2020-09-24T18:00:36Z)
• Entanglement marginal problems [0.0]
  entanglement marginal problem consists of deciding whether a number of reduced density matrices are compatible with an overall separable quantum state. We propose hierarchies of semidefinite programming relaxations of the set of quantum state marginals admitting a fully separable extension. Our results even extend to infinite systems, such as translation-invariant systems in 1D, as well as higher spatial dimensions with extra symmetries.
  arXiv  Detail & Related papers  (2020-06-16T10:48:56Z)

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.