論文の概要: Rank-One Modified Value Iteration

• arxiv url: http://arxiv.org/abs/2505.01828v2
• Date: Sun, 25 May 2025 13:03:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-27 14:32:54.551622
• Title: Rank-One Modified Value Iteration
• Title（参考訳）: Rank-one Modified Value Iteration
• Authors: Arman Sharifi Kolarijani, Tolga Ok, Peyman Mohajerin Esfahani, Mohamad Amin Sharif Kolarijani,
• Abstract要約: マルコフ決定過程の計画と学習問題を解決するための新しいアルゴリズムを提案する。 提案アルゴリズムは、計画と学習の両問題に対して、一階アルゴリズムとそれらの高速化バージョンを一貫して上回っていることを示す。
• 参考スコア（独自算出の注目度）: 3.04988705714342
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: In this paper, we provide a novel algorithm for solving planning and learning problems of Markov decision processes. The proposed algorithm follows a policy iteration-type update by using a rank-one approximation of the transition probability matrix in the policy evaluation step. This rank-one approximation is closely related to the stationary distribution of the corresponding transition probability matrix, which is approximated using the power method. We provide theoretical guarantees for the convergence of the proposed algorithm to optimal (action-)value function with the same rate and computational complexity as the value iteration algorithm in the planning problem and as the Q-learning algorithm in the learning problem. Through our extensive numerical simulations, however, we show that the proposed algorithm consistently outperforms first-order algorithms and their accelerated versions for both planning and learning problems.
• Abstract（参考訳）: 本稿ではマルコフ決定過程の計画と学習問題を解決するための新しいアルゴリズムを提案する。 提案アルゴリズムは、ポリシー評価ステップにおける遷移確率行列のランク1近似を用いて、ポリシー反復型更新に従う。 このランクワン近似は、電力法を用いて近似した対応する遷移確率行列の定常分布と密接に関連している。 本稿では,提案アルゴリズムを,計画問題における値反復アルゴリズムと同じレートと計算量で最適(アクション-)値関数に収束させることを理論的に保証し,学習問題におけるQ-ラーニングアルゴリズムとして提供する。 しかし,より広範な数値シミュレーションにより,提案アルゴリズムは,計画問題と学習問題の両方において,一階アルゴリズムとその高速化バージョンを一貫して上回っていることを示す。

関連論文リスト

• Deterministic Trajectory Optimization through Probabilistic Optimal Control [3.2771631221674333]
  離散時間決定論的有限水平非線形最適制御問題に適した2つのアルゴリズムについて論じる。 どちらのアルゴリズムも、確率論的最適制御(probabilistic optimal control)と呼ばれる新しい理論パラダイムから導出することができる。 アルゴリズムの主な利点は、反復よりも探索と搾取のバランスを改善することである。
  論文  参考訳（メタデータ） (2024-07-18T09:17:47Z)
• From Optimization to Control: Quasi Policy Iteration [3.4376560669160394]
  準政治反復(QPI)と呼ばれる新しい制御アルゴリズムを提案する。 QPIは、政策反復アルゴリズムにおける「ヘシアン」行列の新たな近似に基づいて、MDPに特有の2つの線形構造制約を利用する。 これは、割引係数に対する感度が極めて低い政策反復と同様の実証的な収束挙動を示す。
  論文  参考訳（メタデータ） (2023-11-18T21:00:14Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Stochastic Ratios Tracking Algorithm for Large Scale Machine Learning Problems [0.7614628596146599]
  古典的なSGDフレームワークにおける適応的なステップ長選択のための新しいアルゴリズムを提案する。 妥当な条件下では、アルゴリズムは十分に確立された理論的な要件に従ってステップ長を生成する。 このアルゴリズムは,手動チューニングから得られる最良ステップ長に匹敵するステップ長を生成することができることを示す。
  論文  参考訳（メタデータ） (2023-05-17T06:22:11Z)
• First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems [88.58409977434269]
  非線形一般化ナッシュ均衡問題(NGNEP)における平衡計算の問題を考える。 我々の貢献は、2次ペナルティ法と拡張ラグランジアン法に基づく2つの単純な一階アルゴリズムフレームワークを提供することである。 これらのアルゴリズムに対する漸近的理論的保証を提供する。
  論文  参考訳（メタデータ） (2022-04-07T00:11:05Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Average-Reward Off-Policy Policy Evaluation with Function Approximation [66.67075551933438]
  平均報酬MDPの関数近似によるオフポリシ政策評価を検討する。 ブートストラップは必要であり、オフポリシ学習とFAと一緒に、致命的なトライアドをもたらす。 そこで本研究では,勾配型tdアルゴリズムの成功を再現する2つの新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-08T00:43:04Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。 この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。 古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
  論文  参考訳（メタデータ） (2020-07-01T18:43:32Z)
• Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization [71.03797261151605]
  適応性は現代最適化理論において重要であるが、研究されていない性質である。 提案アルゴリズムは,PL目標に対して既存のアルゴリズムよりも優れた性能を保ちながら,PL目標に対して最適な収束性を実現することを実証した。
  論文  参考訳（メタデータ） (2020-02-13T05:42:27Z)

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

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