論文の概要: Policy Iteration Is Not Strongly Polynomial for Deterministic Markov Decision Processes: The Price of Algorithmic Anarchy

• arxiv url: http://arxiv.org/abs/2609.40147v1
• Date: Wed, 30 Sep 2026 16:53:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-01 18:57:28.112675
• Title: Policy Iteration Is Not Strongly Polynomial for Deterministic Markov Decision Processes: The Price of Algorithmic Anarchy
• Title（参考訳）: 政策反復は決定論的マルコフ決定過程に強くは多義的ではない:アルゴリズム的アナキシーの価格
• Abstract要約: 決定論的割引決定プロセスに関するハワードの政策について、指数関数的反復を州数より低く設定する。 このことは、割引係数が入力の一部であるときにハワードのポリシー反復の強みを除外し、単純解法から指数関数的に分離する。
• 参考スコア（独自算出の注目度）: 14.695024781603037
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We establish an exponential iteration lower bound in the number of states for Howard's policy iteration on deterministic discounted Markov decision processes, with at most two actions per state. This rules out strong polynomiality of Howard's policy iteration when the discount factor is part of the input and yields an exponential separation from the simplex method with Dantzig's pivoting rule, which is proved to be strongly polynomial on this class. Even when each reward is restricted to logarithmic bit length, we obtain a stretched-exponential iteration lower bound. The gap between Howard's decentralized and simultaneous selfish improvements and Dantzig's coordinated selection of a single action with the largest gain across all states reveals a ``price'' of algorithmic anarchy.
• Abstract（参考訳）: 我々は、決定論的に割引されたマルコフ決定過程に対するハワードの政策反復に対する状態の数に対して指数的反復を低くし、1状態当たり少なくとも2つの作用を持つ。 このことは、割引係数が入力の一部であるときにハワードのポリシー反復の強い多項式性を除外し、ダンツィヒのピボット則(英語版)(Dantzig's pivoting rule)による単純解法から指数関数的に分離する。 各報酬が対数ビット長に制限されている場合でも、拡張された指数反復の低いバウンドが得られる。 ハワードの分散化と同時自己中心的な改善とダンツィヒの協調した一つの行動の選択のギャップは、アルゴリズム的アナキシーの '`price''' を明らかにしている。

関連論文リスト

• Strong and Compact Policies for Submodular Markov Decision Processes via LP-Based Submodular Orienteering [2.66418345185993]
  本稿では,Sherali-Adams階層とRound-or-Cutのアイデアを用いた,サブモジュール指向性のためのLPベースの新しいアルゴリズムを提案する。 我々の保証は、準多項式時間対数近似(submodular Orienteering)の既知の準多項式時間対数近似に匹敵する。
  論文  参考訳（メタデータ） (2026-09-14T13:26:08Z)
• Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Losses [0.8984888893275712]
  我々は、LogSumExpソフトマックスポリシーと呼ばれる新しいクラスのポリシーを導入し、実行します。 周期的ポリシーミキシングと正規化された二重更新という2つの新しいアルゴリズムコンポーネントは、被覆数と二重変数の両方を効果的に制御できる。
  論文  参考訳（メタデータ） (2026-05-12T05:02:02Z)
• Lower Bound on Howard Policy Iteration for Deterministic Markov Decision Processes [5.280329080592276]
  我々は、古典的な平均支払い(すなわち上限平均)の目的を考え、それは基本的で基本的な目的である。 Howardのポリシー反復アルゴリズムは、平均支払目的のDMDPを解く一般的な方法である。 入力サイズが$I$の場合、アルゴリズムは$tildeOmega(sqrtI)$ iterationsを必要とする。
  論文  参考訳（メタデータ） (2025-06-13T22:00:36Z)
• Howard's Policy Iteration is Subexponential for Deterministic Markov Decision Problems with Rewards of Fixed Bit-size and Arbitrary Discount Factor [5.887651395076199]
  Howard's Policy Iteration (HPI) はマルコフ決定問題(MDP)を解くための古典的なアルゴリズムである。 HPI は "greedy" スイッチングルールを使用して、任意の非最適ポリシーから支配ポリシーに更新し、最適なポリシーが見つかるまで反復する。 60年以上前に導入されたにもかかわらず、HPIのランニング時間に関する最もよく知られている上限は、州数で指数関数的である。
  論文  参考訳（メタデータ） (2025-05-01T18:50:10Z)
• Bridging the Gap between Newton-Raphson Method and Regularized Policy Iteration [13.166738075816493]
  規則化されたポリシー反復は、強い凸関数を持つベルマン方程式を滑らかにする条件において、標準ニュートン・ラフソン法と厳密に等価であることを示す。 正規化政策反復が大域的線形収束を持ち、そのレートが$gamma$ (discount factor)であることを証明する。 また、正規化ポリシー反復の修正版、すなわち有限ステップのポリシー評価はニュートン法と等価であり、ニュートンの反復式はトランカットされた反復で解かれることを示す。
  論文  参考訳（メタデータ） (2023-10-11T05:55:20Z)
• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。 我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。 また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-21T00:17:24Z)
• Efficient Algorithms for Planning with Participation Constraints [74.74967476995572]
  我々は[Zhang et al., 2022]に導入された参加制約を伴う計画の問題を考える。 この問題では、プリンシパルが決定プロセスのアクションを選択し、プリンシパルとエージェントの別々のユーティリティが生成される。 有限ホライズン設定では,これまでは$varepsilon$-approximationという付加値しか知られていなかった。
  論文  参考訳（メタデータ） (2022-05-16T15:47:41Z)
• Continuous-Time Fitted Value Iteration for Robust Policies [93.25997466553929]
  ハミルトン・ヤコビ・ベルマン方程式の解法は、制御、ロボティクス、経済学を含む多くの領域において重要である。 連続適合値反復(cFVI)とロバスト適合値反復(rFVI)を提案する。 これらのアルゴリズムは、多くの連続制御問題の非線形制御-アフィンダイナミクスと分離可能な状態とアクション報酬を利用する。
  論文  参考訳（メタデータ） (2021-10-05T11:33:37Z)
• Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning [85.50033812217254]
  アクター批判法はオフラインの強化学習に広く用いられているが、理論的にはそれほどよく理解されていない。 ペシミズムの原理を自然に取り入れた新しいオフラインアクター批判アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-08-19T17:27:29Z)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  マルコフ決定過程における純粋探索問題について検討する。 エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
  論文  参考訳（メタデータ） (2021-06-05T09:16:28Z)
• Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint [75.85952446237599]
  修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。 最適なデータ依存上界を導出する。 また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
  論文  参考訳（メタデータ） (2020-08-12T15:40:21Z)

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

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