論文の概要: Weighted mesh algorithms for general Markov decision processes: Convergence and tractability
- arxiv url: http://arxiv.org/abs/2407.00388v1
- Date: Sat, 29 Jun 2024 10:08:23 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-04 03:25:29.421197
- Title: Weighted mesh algorithms for general Markov decision processes: Convergence and tractability
- Title（参考訳）: 一般的なマルコフ決定プロセスのための重み付きメッシュアルゴリズム:収束性とトラクタビリティ
- Authors: Denis Belomestny, John Schoenmakers,
- Abstract要約: 離散時間有限水平マルコフ決定過程(MDP)に対するメッシュ型アプローチを提案する。
非有界な状態空間に対して、このアルゴリズムは、複雑性がある次元独立な$cgeq2$を持つ$epsilonc$であるという意味で「半有理」である。
- 参考スコア（独自算出の注目度）: 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.
- Abstract（参考訳）: 離散時間有限ホリゾンマルコフ決定過程(MDP)を扱うメッシュ型アプローチを導入し、ユークリッド空間の有限部分集合と無限部分集合を包含する状態空間と作用空間を特徴付ける。
特に、有界状態および作用空間に対して、我々のアルゴリズムは、ノヴァクとウォズニアコフスキーの意味での計算複雑性を達成し、時間的地平線における多項式である。
非有界な状態空間の場合、このアルゴリズムは、ある次元が独立な$c\geq2$に比例して$\epsilon^{-c}$となり、精度が$\epsilon$となる。
提案手法は, 有限地平線MDPと一様サンプリングをコンパクトな状態空間で扱うRustによるランダム化手法のフレーバーを持つ。
しかし、このアプローチは、有限地平線と一般的な遷移分布によるシミュレーション手順により本質的に異なるものであり、非有界状態空間を包含するという意味ではより一般的なものである。
提案アルゴリズムの有効性を示すために,LQG制御問題に基づくイラストを提供している。
関連論文リスト
- Convergence and complexity of block majorization-minimization for constrained block-Riemannian optimization [18.425648833592312]
ブロック化最小化(BMM)は、非排他的部分空間推定のための単純な反復勾配である。
我々の分析はユークリッドの制約を明示的に用いている。
論文 参考訳（メタデータ） (2023-12-16T05:40:19Z) - GRAPE optimization for open quantum systems with time-dependent
decoherence rates driven by coherent and incoherent controls [77.34726150561087]
グラディエントアセンセントパルス工学(GRAPE)法は量子制御の最適化に広く用いられている。
我々は、コヒーレント制御と非コヒーレント制御の両方によって駆動されるオープン量子系の目的関数を最適化するために、GRAPE法を採用する。
状態-状態遷移問題に対する数値シミュレーションによりアルゴリズムの効率を実証する。
論文 参考訳（メタデータ） (2023-07-17T13:37:18Z) - Complexity of Block Coordinate Descent with Proximal Regularization and
Applications to Wasserstein CP-dictionary Learning [1.4010916616909743]
正規化(BCD-PR)によるGauss-Sdel型ブロック座標の導出について検討する。
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) 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) W(W) W(W) W) W(W) W(W) W(W)
論文 参考訳（メタデータ） (2023-06-04T17:52:49Z) - Markovian Sliced Wasserstein Distances: Beyond Independent Projections [51.80527230603978]
我々は、射影方向にマルコフ構造を課す新しいSW距離の族、Markovian sliced Wasserstein (MSW) 距離を導入する。
フロー,色移動,深部生成モデルなどの様々な応用において,従来のSW変種との距離を比較し,MSWの良好な性能を示す。
論文 参考訳（メタデータ） (2023-01-10T01:58:15Z) - Computationally Efficient PAC RL in POMDPs with Latent Determinism and
Conditional Embeddings [97.12538243736705]
大規模部分観測可能決定プロセス(POMDP)の関数近似を用いた強化学習に関する研究
我々のアルゴリズムは、大規模POMDPに確実にスケールする。
論文 参考訳（メタデータ） (2022-06-24T05:13:35Z) - Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
ヒルベルト空間全体の部分空間への発展を制限する混合作用素を構築するための枠組みを提案する。
我々は,「ワンホット」状態の部分空間を保存するために設計された「XY」ミキサーを,多くの計算基底状態によって与えられる部分空間の一般の場合に一般化する。
我々の分析は、現在知られているよりもCXゲートが少ない"XY"ミキサーのトロタライズも有効である。
論文 参考訳（メタデータ） (2022-03-11T17:19:26Z) - Bounds on quantum evolution complexity via lattice cryptography [0.0]
量子論における可積分運動とカオス運動の差は、対応する進化作用素の複雑さによって表される。
ここでの複雑性は、時間依存進化作用素とユニタリ群内の原点の間の最短測地線距離として理解されている。
論文 参考訳（メタデータ） (2022-02-28T16:20:10Z) - Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable
Approach for Continuous Markov Random Fields [53.31927549039624]
断片的な離散化は既存の離散化問題と矛盾しないことを示す。
この理論を2つの画像のマッチング問題に適用する。
論文 参考訳（メタデータ） (2021-07-13T12:31:06Z) - Local optimization on pure Gaussian state manifolds [63.76263875368856]
ボソニックおよびフェルミオンガウス状態の幾何学に関する洞察を利用して、効率的な局所最適化アルゴリズムを開発する。
この手法は局所幾何学に適応した降下勾配の概念に基づいている。
提案手法を用いて、任意の混合ガウス状態の精製の絡み合いを計算するのにガウス浄化が十分であるという予想の数値的および解析的証拠を収集する。
論文 参考訳（メタデータ） (2020-09-24T18:00:36Z) - Entanglement marginal problems [0.0]
絡み合いの限界問題は、多くの還元密度行列が全体分離可能な量子状態と互換性があるかどうかを決定することである。
完全分離可能な拡張を許容する量子状態境界の集合の半定値プログラミング緩和の階層性を提案する。
我々の結果は、1次元の翻訳不変系や余剰対称性を持つ高次元など無限のシステムにまで拡張される。
論文 参考訳（メタデータ） (2020-06-16T10:48:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。