論文の概要: Howard's Policy Iteration is Subexponential for Deterministic Markov Decision Problems with Rewards of Fixed Bit-size and Arbitrary Discount Factor

• arxiv url: http://arxiv.org/abs/2505.00795v1
• Date: Thu, 01 May 2025 18:50:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-05 17:21:19.79825
• Title: Howard's Policy Iteration is Subexponential for Deterministic Markov Decision Problems with Rewards of Fixed Bit-size and Arbitrary Discount Factor
• Title（参考訳）: ハワードの政策反復は、固定ビットサイズと任意割当因子の逆算を伴う決定論的マルコフ決定問題の亜指数である
• Authors: Dibyangshu Mukherjee, Shivaram Kalyanakrishnan,
• Abstract要約: Howard's Policy Iteration (HPI) はマルコフ決定問題(MDP)を解くための古典的なアルゴリズムである。 HPI は "greedy" スイッチングルールを使用して、任意の非最適ポリシーから支配ポリシーに更新し、最適なポリシーが見つかるまで反復する。 60年以上前に導入されたにもかかわらず、HPIのランニング時間に関する最もよく知られている上限は、州数で指数関数的である。
• 参考スコア（独自算出の注目度）: 5.887651395076199
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Howard's Policy Iteration (HPI) is a classic algorithm for solving Markov Decision Problems (MDPs). HPI uses a "greedy" switching rule to update from any non-optimal policy to a dominating one, iterating until an optimal policy is found. Despite its introduction over 60 years ago, the best-known upper bounds on HPI's running time remain exponential in the number of states -- indeed even on the restricted class of MDPs with only deterministic transitions (DMDPs). Meanwhile, the tightest lower bound for HPI for MDPs with a constant number of actions per state is only linear. In this paper, we report a significant improvement: a subexponential upper bound for HPI on DMDPs, which is parameterised by the bit-size of the rewards, while independent of the discount factor. The same upper bound also applies to DMDPs with only two possible rewards (which may be of arbitrary size).
• Abstract（参考訳）: Howard's Policy Iteration (HPI) はマルコフ決定問題(MDP)を解決するための古典的なアルゴリズムである。 HPI は "greedy" スイッチングルールを使用して、任意の非最適ポリシーから支配ポリシーに更新し、最適なポリシーが見つかるまで反復する。 60年以上前に導入されたにもかかわらず、HPIのランニング時間に関する最もよく知られている上限は、州数において指数関数的であり、実際、決定論的遷移(DMDP)のみを持つ制限されたMDPのクラスでさえも指数的である。 一方、状態当たりのアクション数が一定であるMPPに対するHPIの最も狭い下限は線形である。 本稿では,報酬のビットサイズによってパラメータ化されるDMDP上のHPIのサブ指数上限を,割引係数に依存しない形で,大幅に改善したことを報告する。 同じ上限は2つの報酬しか持たないDMDPにも適用される(これは任意の大きさであるかもしれない)。

関連論文リスト

• On the Global Convergence of Policy Gradient in Average Reward Markov Decision Processes [50.68789924454235]
  我々は、平均報酬マルコフ決定過程(MDP)の文脈における政策勾配の最初の有限時間大域収束解析を示す。 我々の分析によると、ポリシー勾配は、$Oleft(frac1Tright)$のサブリニアレートで最適ポリシーに収束し、$Oleft(log(T)right)$ regretに変換され、$T$は反復数を表す。
  論文  参考訳（メタデータ） (2024-03-11T15:25:03Z)
• Solving Long-run Average Reward Robust MDPs via Stochastic Games [6.183091173390457]
  ロバストマルコフ決定過程(RMDP)は、各遷移に単一の確率値ではなく不確実性集合を割り当てる。 我々は、有限状態およびアクション空間を持つ長期平均報酬ターンベースのゲームに還元可能であることを示す。 本稿では、長期平均ポリトピックRMDPを解くための新しいポリシー反復アルゴリズムであるRobust Polytopic Policy Iteration(RPPI)を提案する。
  論文  参考訳（メタデータ） (2023-12-21T15:00:06Z)
• Model-Free, Regret-Optimal Best Policy Identification in Online CMDPs [17.62509045102346]
  本稿では,CMDP(Constrained Markov Decision Processs)における最適ポリシー識別問題について考察する。 私たちは、モデルフリーで、後悔の少ないアルゴリズムに興味を持ち、確率の高いほぼ最適なポリシーを特定しています。 オンラインCMDPのサブ線形後悔と制約違反を伴う既存のモデルフリーアルゴリズムでは、最適ポリシーに対する収束保証は提供されない。
  論文  参考訳（メタデータ） (2023-09-27T04:33:09Z)
• Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs [107.28031292946774]
  無限水平割引マルコフ決定過程(拘束型MDP)の最適ポリシの計算問題について検討する。 我々は, 最適制約付きポリシーに反復的に対応し, 非漸近収束性を持つ2つの単一スケールポリシーに基づく原始双対アルゴリズムを開発した。 我々の知る限り、この研究は制約付きMDPにおける単一時間スケールアルゴリズムの非漸近的な最後の収束結果となる。
  論文  参考訳（メタデータ） (2023-06-20T17:27:31Z)
• Twice Regularized Markov Decision Processes: The Equivalence between Robustness and Regularization [64.60253456266872]
  マルコフ決定プロセス(MDP)は、変化または部分的に知られているシステムのダイナミクスを扱うことを目的としている。 規則化されたMDPは、時間的複雑さを損なうことなく、ポリシー学習の安定性を高める。 ベルマン作用素は、収束と一般化を保証する計画と学習スキームを導出することができる。
  論文  参考訳（メタデータ） (2023-03-12T13:03:28Z)
• Softmax Policy Gradient Methods Can Take Exponential Time to Converge [60.98700344526674]
  Softmax Policy gradient(PG)メソッドは、現代の強化学習におけるポリシー最適化の事実上の実装の1つです。 ソフトマックス PG 法は、$mathcalS|$ および $frac11-gamma$ の観点から指数時間で収束できることを実証する。
  論文  参考訳（メタデータ） (2021-02-22T18:56:26Z)
• RL for Latent MDPs: Regret Guarantees and a Lower Bound [74.41782017817808]
  後期マルコフ決定過程(LMDP)における強化学習における後悔問題の検討 LMDPにおいて、M$可能なMDPのセットからMDPをランダムに描画するが、選択したMDPの同一性はエージェントに明らかにしない。 鍵となるリンクは、MDPシステムの力学の分離の概念であることを示す。
  論文  参考訳（メタデータ） (2021-02-09T16:49:58Z)

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

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