論文の概要: Lower Bound on Howard Policy Iteration for Deterministic Markov Decision Processes

• arxiv url: http://arxiv.org/abs/2506.12254v1
• Date: Fri, 13 Jun 2025 22:00:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-17 17:28:45.603999
• Title: Lower Bound on Howard Policy Iteration for Deterministic Markov Decision Processes
• Title（参考訳）: 決定論的マルコフ決定過程のハワード政策反復に関する下限
• Authors: Ali Asadi, Krishnendu Chatterjee, Jakob de Raaij,
• Abstract要約: 我々は、古典的な平均支払い(すなわち上限平均)の目的を考え、それは基本的で基本的な目的である。 Howardのポリシー反復アルゴリズムは、平均支払目的のDMDPを解く一般的な方法である。 入力サイズが$I$の場合、アルゴリズムは$tildeOmega(sqrtI)$ iterationsを必要とする。
• 参考スコア（独自算出の注目度）: 5.280329080592276
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Deterministic Markov Decision Processes (DMDPs) are a mathematical framework for decision-making where the outcomes and future possible actions are deterministically determined by the current action taken. DMDPs can be viewed as a finite directed weighted graph, where in each step, the controller chooses an outgoing edge. An objective is a measurable function on runs (or infinite trajectories) of the DMDP, and the value for an objective is the maximal cumulative reward (or weight) that the controller can guarantee. We consider the classical mean-payoff (aka limit-average) objective, which is a basic and fundamental objective. Howard's policy iteration algorithm is a popular method for solving DMDPs with mean-payoff objectives. Although Howard's algorithm performs well in practice, as experimental studies suggested, the best known upper bound is exponential and the current known lower bound is as follows: For the input size $I$, the algorithm requires $\tilde{\Omega}(\sqrt{I})$ iterations, where $\tilde{\Omega}$ hides the poly-logarithmic factors, i.e., the current lower bound on iterations is sub-linear with respect to the input size. Our main result is an improved lower bound for this fundamental algorithm where we show that for the input size $I$, the algorithm requires $\tilde{\Omega}(I)$ iterations.
• Abstract（参考訳）: 決定論的マルコフ決定過程(英: Deterministic Markov Decision Processes、DMDP)は、現在の行動によって結果と将来の行動が決定的に決定される意思決定のための数学的枠組みである。 DMDPは有限方向重み付きグラフと見なすことができ、各ステップでコントローラは外側のエッジを選択する。 目的はDMDPの実行(または無限軌跡)における可測関数であり、目的の値はコントローラが保証できる最大累積報酬(または重量)である。 我々は、古典的な平均支払い(すなわち上限平均)の目的を考え、それは基本的で基本的な目的である。 Howardのポリシー反復アルゴリズムは、平均支払目的のDMDPを解く一般的な方法である。 ハワードのアルゴリズムは実際はよく機能するが、実験的な研究が示唆しているように、最もよく知られた上限は指数関数であり、現在の下限は以下の通りである: 入力サイズ$I$の場合、アルゴリズムは$\tilde{\Omega}(\sqrt{I})$イテレーションを必要とする。 我々の主な結果は、入力サイズが$I$の場合、アルゴリズムは$\tilde{\Omega}(I)$ iterationsを必要としていることを示す、この基本アルゴリズムの低境界の改善である。

関連論文リスト

• Model-Free, Regret-Optimal Best Policy Identification in Online CMDPs [17.62509045102346]
  本稿では,CMDP(Constrained Markov Decision Processs)における最適ポリシー識別問題について考察する。 私たちは、モデルフリーで、後悔の少ないアルゴリズムに興味を持ち、確率の高いほぼ最適なポリシーを特定しています。 オンラインCMDPのサブ線形後悔と制約違反を伴う既存のモデルフリーアルゴリズムでは、最適ポリシーに対する収束保証は提供されない。
  論文  参考訳（メタデータ） (2023-09-27T04:33:09Z)
• Bayesian Learning of Optimal Policies in Markov Decision Processes with Countably Infinite State-Space [0.0]
  離散時間可算状態空間マルコフ決定過程の族を最適に制御する問題について検討する。 動的サイズのエピソードを用いたトンプソンサンプリングに基づくアルゴリズムを提案する。 提案アルゴリズムは, 近似最適制御アルゴリズムの開発に応用可能であることを示す。
  論文  参考訳（メタデータ） (2023-06-05T03:57:16Z)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。 本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T14:37:21Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximation [107.54516740713969]
  本研究は,RL(Human-in-the-loop reinforcement learning)を軌道的嗜好で検討する。 各ステップで数値的な報酬を受ける代わりに、エージェントは人間の監督者から軌道上のペアよりも優先される。 一般関数近似を用いたPbRLの楽観的モデルベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-05-23T09:03:24Z)
• Provably Efficient Model-Free Algorithm for MDPs with Peak Constraints [38.2783003051101]
  本稿では,有限地平線における全報酬の最大化と,各エポックにおける制約を確率1で満たすため,エージェントがポリシーを選択する,制約付きマルコフ決定プロセス(PCMDP)について考察する。 そこで本研究では,PCMDP問題を制約のない問題に変換するモデルフリーアルゴリズムを提案し,Q-ラーニングに基づくアプローチを適用した。
  論文  参考訳（メタデータ） (2020-03-11T23:23:29Z)
• Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
  制約付きマルコフ決定過程(CMDP)を用いた安全強化学習(SRL)問題について検討する。 本稿では,関数近似設定において,安全な探索を行うCMDPの効率の良いオンラインポリシー最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-03-01T17:47:03Z)
• Differentially Quantized Gradient Methods [53.3186247068836]
  微分量子化グラディエントDescence (DQ-GD) が$maxsigma_mathrmGD, rhon 2-R$の線形収縮係数を得ることを示す。 あるクラス内のアルゴリズムは$maxsigma_mathrmGD, 2-R$よりも早く収束できない。
  論文  参考訳（メタデータ） (2020-02-06T20:40:53Z)

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

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