論文の概要: Value Iteration with Guessing for Markov Chains and Markov Decision Processes

• arxiv url: http://arxiv.org/abs/2505.06769v1
• Date: Sat, 10 May 2025 22:24:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-13 20:21:49.032067
• Title: Value Iteration with Guessing for Markov Chains and Markov Decision Processes
• Title（参考訳）: マルコフ連鎖とマルコフ決定過程の誘導による値反復
• Authors: Krishnendu Chatterjee, Mahdi JafariRaviz, Raimundo Saona, Jakub Svoboda,
• Abstract要約: 確率システムの標準モデルとして、マルコフ連鎖(MC)とマルコフ決定過程(MDP)がある。 これらの問題に対して広く研究されているアルゴリズム的アプローチは、ベルマン更新と呼ばれる局所的な更新を反復的に適用するValue Ittheoretical (VI) である。 ほぼ線形時間前処理アルゴリズムを提案し、その後、推測値とともに、VI はベルマン更新を指数的に多く要求するのみである。
• 参考スコア（独自算出の注目度）: 5.0710622093569055
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: Two standard models for probabilistic systems are Markov chains (MCs) and Markov decision processes (MDPs). Classic objectives for such probabilistic models for control and planning problems are reachability and stochastic shortest path. The widely studied algorithmic approach for these problems is the Value Iteration (VI) algorithm which iteratively applies local updates called Bellman updates. There are many practical approaches for VI in the literature but they all require exponentially many Bellman updates for MCs in the worst case. A preprocessing step is an algorithm that is discrete, graph-theoretical, and requires linear space. An important open question is whether, after a polynomial-time preprocessing, VI can be achieved with sub-exponentially many Bellman updates. In this work, we present a new approach for VI based on guessing values. Our theoretical contributions are twofold. First, for MCs, we present an almost-linear-time preprocessing algorithm after which, along with guessing values, VI requires only subexponentially many Bellman updates. Second, we present an improved analysis of the speed of convergence of VI for MDPs. Finally, we present a practical algorithm for MDPs based on our new approach. Experimental results show that our approach provides a considerable improvement over existing VI-based approaches on several benchmark examples from the literature.
• Abstract（参考訳）: 確率システムの標準的なモデルとして、マルコフ連鎖(MC)とマルコフ決定過程(MDP)がある。 制御および計画問題に対するそのような確率的モデルに対する古典的な目的は、到達可能性と確率的最短経路である。 これらの問題に対して広く研究されているアルゴリズム的アプローチは、ベルマン更新と呼ばれる局所的な更新を反復的に適用する値反復(VI)アルゴリズムである。 VI には多くの実践的なアプローチがあるが、最悪の場合、これらはすべて指数関数的に多くの MC のベルマン更新を必要とする。 前処理ステップは離散的でグラフ理論的なアルゴリズムであり、線形空間を必要とする。 重要なオープンな疑問は、多項式時間前処理の後、VI がベルマンの更新回数を減らして達成できるかどうかである。 本研究では, 推定値に基づいて, VI に対する新しいアプローチを提案する。 私たちの理論的貢献は2倍です。 まず, MCに対して, ほぼ線形時間前処理アルゴリズムを提案する。 第2に,MPPに対するVIの収束速度を改良した解析法を提案する。 最後に,我々の新しいアプローチに基づくMDPの実践的アルゴリズムを提案する。 実験結果から,本手法は既存のVIベースの手法に比べて,いくつかのベンチマーク例においてかなり改善されていることがわかった。

関連論文リスト

• Recursive Learning of Asymptotic Variational Objectives [49.69399307452126]
  一般状態空間モデル(英: General State-space Model, SSM)は、統計機械学習において広く用いられ、時系列データに対して最も古典的な生成モデルの一つである。 オンラインシーケンシャルIWAE(OSIWAE)は、潜在状態の推測のためのモデルパラメータとマルコフ認識モデルの両方のオンライン学習を可能にする。 このアプローチは、最近提案されたオンライン変分SMC法よりも理論的によく確立されている。
  論文  参考訳（メタデータ） (2024-11-04T16:12:37Z)
• Two-Step Q-Learning [0.0]
  そこで本研究では,重要でない2段階のQ-ラーニングアルゴリズムを提案する。 数値実験により、2段階のQ-ラーニングとそのスムーズな変形の優れた性能が示された。
  論文  参考訳（メタデータ） (2024-07-02T15:39:00Z)
• Parameterized Projected Bellman Operator [64.129598593852]
  近似値反復(英: Approximate value iteration, AVI)は、強化学習(RL)のためのアルゴリズムの一群である。 本稿ではベルマン作用素の近似版を学習する新しい代替手法を提案する。 逐次決定問題に対するPBO学習のための最適化問題を定式化する。
  論文  参考訳（メタデータ） (2023-12-20T09:33:16Z)
• Variational Inference for Neyman-Scott Processes [1.4467794332678536]
  Neyman-Scottプロセス(NSP)は、クラスタ階層のモデルポイントや時間イベントに、さまざまな分野に適用されている。 NSPに対する第1変分推論 (VI) アルゴリズムを開発し、適切な変分後点過程分布の2つの例を示す。
  論文  参考訳（メタデータ） (2023-03-07T07:32:10Z)
• Learning noisy-OR Bayesian Networks with Max-Product Belief Propagation [12.326502890179105]
  変分推論は、複雑な潜在構造を持つノイズやBNを学習するために提案された主要な手法である。 複雑な潜在構造を持つ雑音やBNを学習するための代替アルゴリズムとして,並列最大積を提案する。
  論文  参考訳（メタデータ） (2023-01-31T21:00:26Z)
• Formal guarantees for heuristic optimization algorithms used in machine learning [6.978625807687497]
  グラディエント・Descent(SGD)とその変種は、大規模最適化機械学習(ML)問題において支配的な手法となっている。 本稿では,いくつかの凸最適化手法の形式的保証と改良アルゴリズムの提案を行う。
  論文  参考訳（メタデータ） (2022-07-31T19:41:22Z)
• Making Linear MDPs Practical via Contrastive Representation Learning [101.75885788118131]
  マルコフ決定過程(MDP)における次元性の呪いに、低ランク表現を利用することで対処することが一般的である。 本稿では,効率的な表現学習を可能にしつつ,正規化を自動的に保証する線形MDPの代替的定義について考察する。 いくつかのベンチマークにおいて、既存の最先端モデルベースおよびモデルフリーアルゴリズムよりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-07-14T18:18:02Z)
• Graph Signal Restoration Using Nested Deep Algorithm Unrolling [85.53158261016331]
  グラフ信号処理は、センサー、社会交通脳ネットワーク、ポイントクラウド処理、グラフネットワークなど、多くのアプリケーションにおいてユビキタスなタスクである。 凸非依存型深部ADMM(ADMM)に基づく2つの復元手法を提案する。 提案手法のパラメータはエンドツーエンドでトレーニング可能である。
  論文  参考訳（メタデータ） (2021-06-30T08:57:01Z)
• Simple and optimal methods for stochastic variational inequalities, I: operator extrapolation [9.359939442911127]
  まず,決定論的変分不等式(VI)問題を解決するための演算子外挿法を提案する。 次に、演算子外挿法(SOE)を導入し、その最適収束挙動を異なる不等式 VI 問題を解くために確立する。
  論文  参考訳（メタデータ） (2020-11-05T17:20:19Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。