論文の概要: Reductive MDPs: A Perspective Beyond Temporal Horizons

• arxiv url: http://arxiv.org/abs/2205.07338v1
• Date: Sun, 15 May 2022 17:22:52 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-17 14:01:06.180383
• Title: Reductive MDPs: A Perspective Beyond Temporal Horizons
• Title（参考訳）: 減量型MDP : 時間的ホライズンズを超えた展望
• Authors: Thomas Spooner, Rui Silva, Joshua Lockhart, Jason Long, Vacslav Glukhov
• Abstract要約: 一般決定過程(MDP)の解法は計算的に難しい問題である。 力学が特定のドリフト条件を満たす一般的な状態-作用空間を解くこと。 帰納的マルコフSSPに間に合うように最適なポリシーを復元できることが示されている。
• 参考スコア（独自算出の注目度）: 5.459797813771498
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Solving general Markov decision processes (MDPs) is a computationally hard problem. Solving finite-horizon MDPs, on the other hand, is highly tractable with well known polynomial-time algorithms. What drives this extreme disparity, and do problems exist that lie between these diametrically opposed complexities? In this paper we identify and analyse a sub-class of stochastic shortest path problems (SSPs) for general state-action spaces whose dynamics satisfy a particular drift condition. This construction generalises the traditional, temporal notion of a horizon via decreasing reachability: a property called reductivity. It is shown that optimal policies can be recovered in polynomial-time for reductive SSPs -- via an extension of backwards induction -- with an efficient analogue in reductive MDPs. The practical considerations of the proposed approach are discussed, and numerical verification provided on a canonical optimal liquidation problem.
• Abstract（参考訳）: 一般マルコフ決定過程(MDP)の解法は計算的に難しい問題である。 一方、有限ホライズン MDP の解法は、よく知られた多項式時間アルゴリズムで高度に抽出可能である。 なぜこの極端な格差を引き起こすのか、また、これらの対向する複雑度の間に問題が存在するのか? 本稿では,特定のドリフト条件を満たす一般状態空間に対する確率的最短経路問題(SSP)のサブクラスを特定し,解析する。 この構成は、到達可能性の減少を通じて、伝統的な時間的水平線の概念を一般化する。 退行誘導の延長を通じて、還元的SSPに対する多項式時間で最適ポリシーを復元できることが示され、還元的MDPの効率的な類似性が示される。 提案手法の実用的考察と, 正準最適流動化問題に基づく数値検証について検討した。

関連論文リスト

• The regret lower bound for communicating Markov Decision Processes [15.108805347673401]
  我々は、エルゴード的マルコフ決定過程(MDPs)を超えて、後悔の少ない境界を延長する。 我々の下限は、一貫した学習エージェントに必要な爆発的振る舞いを再考する。 これら2つの爆発的・共同探索的行動は,航法制約に絡み合っていることを示す。
  論文  参考訳（メタデータ） (2025-01-22T16:56:42Z)
• Weighted mesh algorithms for general Markov decision processes: Convergence and tractability [0.9940462449990576]
  離散時間有限水平マルコフ決定過程(MDP)に対するメッシュ型アプローチを提案する。 非有界な状態空間に対して、このアルゴリズムは、複雑性がある次元独立な$cgeq2$を持つ$epsilonc$であるという意味で「半有理」である。
  論文  参考訳（メタデータ） (2024-06-29T10:08:23Z)
• High Rank Path Development: an approach of learning the filtration of stochastic processes [6.245824251614165]
  そこで我々は,HRPCFD(High Rank PCF Distance)と呼ばれる新しい尺度を導入する。 そして、そのようなHRPCFDは、データからHRPCFDを訓練し、HRPCF-GANを構築するための効率的なアルゴリズムを設計できるように、多くの好意的な解析特性を許容していることを示す。 仮説テストと生成モデルの両方に関する数値実験は、いくつかの最先端手法と比較して、我々のアプローチのアウトパフォーマンスを検証している。
  論文  参考訳（メタデータ） (2024-05-23T13:20:47Z)
• Towards Instance-Optimality in Online PAC Reinforcement Learning [28.156332484814616]
  そこで本研究では,PACの同定に要するサンプルの複雑さに対する最初のインスタンス依存下限について提案する。 我々は、citeWagenmaker22linearMDPのPEDELアルゴリズムのサンプル複雑さがこの下界に近づいたことを実証する。
  論文  参考訳（メタデータ） (2023-10-31T19:26:36Z)
• Provably Efficient UCB-type Algorithms For Learning Predictive State Representations [55.00359893021461]
  逐次決定問題は、予測状態表現(PSR)によってモデル化された低ランク構造が認められる場合、統計的に学習可能である 本稿では,推定モデルと実モデル間の全変動距離を上限とする新しいボーナス項を特徴とする,PSRに対する最初のUCB型アプローチを提案する。 PSRに対する既存のアプローチとは対照的に、UCB型アルゴリズムは計算的トラクタビリティ、最優先の準最適ポリシー、モデルの精度が保証される。
  論文  参考訳（メタデータ） (2023-07-01T18:35:21Z)
• Multi-Objective Policy Gradients with Topological Constraints [108.10241442630289]
  本稿では, PPOアルゴリズムの簡単な拡張により, TMDPにおけるポリシー勾配に対する新しいアルゴリズムを提案する。 シミュレーションと実ロボットの両方の目的を任意に並べた実世界の多目的ナビゲーション問題に対して,これを実証する。
  論文  参考訳（メタデータ） (2022-09-15T07:22:58Z)
• The Geometry of Memoryless Stochastic Policy Optimization in Infinite-Horizon POMDPs [0.0]
  我々は、無限水平部分観測可能な決定プロセスにおいて、最高のメモリレスポリシーを見つけるという問題を考察する。 本研究では, 減算された状態-作用周波数と予測累積報酬が政策の関数であり, その度合いは部分観測可能性の度合いによって決定されることを示す。
  論文  参考訳（メタデータ） (2021-10-14T14:42:09Z)
• Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable Approach for Continuous Markov Random Fields [53.31927549039624]
  断片的な離散化は既存の離散化問題と矛盾しないことを示す。 この理論を2つの画像のマッチング問題に適用する。
  論文  参考訳（メタデータ） (2021-07-13T12:31:06Z)
• A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs [117.82903457289584]
  有限水平マルコフ決定過程(MDPs)における新たな問題依存的下界を導出する。 我々の下界は一般の場合よりもかなり小さく、最小の作用ギャップでスケールしないことが示される。 この最後の結果($poly(H)$の条件で、$H$は地平線である)は、楽観的なアルゴリズムのポリシーギャップに基づいて、後悔の意を表すことによって達成可能であることを示す。
  論文  参考訳（メタデータ） (2021-06-24T13:46:09Z)
• Identification of Unexpected Decisions in Partially Observable Monte-Carlo Planning: a Rule-Based Approach [78.05638156687343]
  本稿では,POMCPポリシーをトレースを検査して分析する手法を提案する。 提案手法は, 政策行動の局所的特性を探索し, 予期せぬ決定を識別する。 我々は,POMDPの標準ベンチマークであるTigerに対するアプローチと,移動ロボットナビゲーションに関する現実の問題を評価した。
  論文  参考訳（メタデータ） (2020-12-23T15:09:28Z)
• Free Energy Wells and Overlap Gap Property in Sparse PCA [81.64027805404483]
  我々は「ハード」体制におけるスパースPCA問題(主成分分析)の変種について検討する。 問題に自然に関連付けられた様々なギブズ測度に対する自由エネルギー井戸の深さの有界性を示す。 我々は、オーバーラップギャップ特性(OGP)がハードレジームの重要な部分を占めていることを証明した。
  論文  参考訳（メタデータ） (2020-06-18T17:18:02Z)

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

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