論文の概要: Linear programming-based solution methods for constrained POMDPs
- arxiv url: http://arxiv.org/abs/2206.14081v1
- Date: Tue, 28 Jun 2022 15:22:24 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-29 13:38:45.581143
- Title: Linear programming-based solution methods for constrained POMDPs
- Title（参考訳）: 制約付きPOMDPに対する線形プログラミングに基づく解法
- Authors: Can Kavaklioglu, Robert Helmeczi, Mucahit Cevik
- Abstract要約: 制約付き部分観測可能なマルコフ決定過程(CPOMDP)は、様々な実世界の現象をモデル化するために用いられている。
我々は、CPOMDPの近似ポリシーを生成するために、グリッドベースの近似と線形プログラミング(LP)モデルを組み合わせる。
- 参考スコア（独自算出の注目度）: 0.5156484100374059
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Constrained partially observable Markov decision processes (CPOMDPs) have
been used to model various real-world phenomena. However, they are notoriously
difficult to solve to optimality, and there exist only a few approximation
methods for obtaining high-quality solutions. In this study, we use grid-based
approximations in combination with linear programming (LP) models to generate
approximate policies for CPOMDPs. We consider five CPOMDP problem instances and
conduct a detailed numerical study of both their finite and infinite horizon
formulations. We first establish the quality of the approximate unconstrained
POMDP policies through a comparative analysis with exact solution methods. We
then show the performance of the LP-based CPOMDP solution approaches for
varying budget levels (i.e., cost limits) for different problem instances.
Finally, we show the flexibility of LP-based approaches by applying
deterministic policy constraints, and investigate the impact that these
constraints have on collected rewards and CPU run time. Our analysis
demonstrates that LP models can effectively generate approximate policies for
both finite and infinite horizon problems, while providing the flexibility to
incorporate various additional constraints into the underlying model.
- Abstract（参考訳）: 制約付き部分可観測マルコフ決定過程(cpomdps)は、様々な実世界の現象をモデル化するために用いられる。
しかし、それらは最適性への解決が難しいことで知られており、高品質な解を得るための近似法はわずかしかない。
本研究では,CPOMDPの近似ポリシを生成するために,グリッドベースの近似と線形プログラミング(LP)モデルを組み合わせる。
5つのCPOMDP問題を考慮し、それらの有限および無限の地平線定式化の詳細な数値的研究を行う。
まず, 厳密な解法との比較分析により, ほぼ制約のないPOMDPポリシーの質を確立する。
次に、異なる問題インスタンスに対する様々な予算レベル(コスト制限)に対して、LPベースのCPOMDPソリューションアプローチの性能を示す。
最後に、決定論的ポリシー制約を適用してLPベースのアプローチの柔軟性を示し、これらの制約が収集された報酬やCPU実行時間に与える影響を検討する。
解析により,LPモデルが有限な地平線問題と無限の地平線問題の両方に対する近似ポリシーを効果的に生成できることが示されている。
関連論文リスト
- Landscape of Policy Optimization for Finite Horizon MDPs with General State and Action [10.219627570276689]
我々は、一般的な状態と空間を持つマルコフ決定過程のクラスのためのフレームワークを開発する。
勾配法は非漸近条件で大域的最適ポリシーに収束することを示す。
その結果,多周期インベントリシステムにおける最初の複雑性が確立された。
論文 参考訳（メタデータ） (2024-09-25T17:56:02Z) - Deterministic Policy Gradient Primal-Dual Methods for Continuous-Space Constrained MDPs [82.34567890576423]
我々は,非漸近収束を伴う最適決定主義政策を求めるための決定主義的政策勾配原始双対法を開発した。
D-PGPDの一次-双対反復は、最適正則化原始-双対にサブ線形速度で収束することが証明された。
我々の知る限り、これは連続空間制約型MDPに対する決定論的ポリシー探索法を提案する最初の研究であると思われる。
論文 参考訳（メタデータ） (2024-08-19T14:11:04Z) - Towards Instance-Optimality in Online PAC Reinforcement Learning [28.156332484814616]
そこで本研究では,PACの同定に要するサンプルの複雑さに対する最初のインスタンス依存下限について提案する。
我々は、citeWagenmaker22linearMDPのPEDELアルゴリズムのサンプル複雑さがこの下界に近づいたことを実証する。
論文 参考訳（メタデータ） (2023-10-31T19:26:36Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - Reinforcement Learning Methods for Wordle: A POMDP/Adaptive Control
Approach [0.3093890460224435]
我々は、新しい強化学習手法を用いて、人気のあるWordleパズルの解法に対処する。
Wordleパズルでは、比較的控えめな計算コストで最適に近いオンラインソリューション戦略が得られる。
論文 参考訳（メタデータ） (2022-11-15T03:46:41Z) - Optimality Guarantees for Particle Belief Approximation of POMDPs [55.83001584645448]
部分的に観測可能なマルコフ決定プロセス(POMDP)は、現実の意思決定と制御の問題に対する柔軟な表現を提供する。
POMDPは、特に状態と観測空間が連続的またはハイブリッドである場合、解決するのが非常に難しい。
本稿では,これらのアルゴリズムが使用する粒子フィルタリング手法の近似誤差を特徴付ける理論を提案する。
論文 参考訳（メタデータ） (2022-10-10T21:11:55Z) - Multi-Objective Policy Gradients with Topological Constraints [108.10241442630289]
本稿では, PPOアルゴリズムの簡単な拡張により, TMDPにおけるポリシー勾配に対する新しいアルゴリズムを提案する。
シミュレーションと実ロボットの両方の目的を任意に並べた実世界の多目的ナビゲーション問題に対して,これを実証する。
論文 参考訳（メタデータ） (2022-09-15T07:22:58Z) - Nearly Optimal Latent State Decoding in Block MDPs [74.51224067640717]
エピソードブロック MDP では、意思決定者は少数の潜在状態から生成される豊富な観測やコンテキストにアクセスすることができる。
まず、固定動作ポリシーに基づいて生成されたデータに基づいて、潜時状態復号関数を推定することに興味がある。
次に、報酬のないフレームワークにおいて、最適に近いポリシーを学習する問題について研究する。
論文 参考訳（メタデータ） (2022-08-17T18:49:53Z) - Solving Multistage Stochastic Linear Programming via Regularized Linear
Decision Rules: An Application to Hydrothermal Dispatch Planning [77.34726150561087]
AdaSO(Adaptive least absolute shrinkage and selection operator)に基づく線形決定規則(LDR)の新しい正規化手法を提案する。
実験により、MSLPを解くために古典的な非正規化LDRを使用する場合、過度に適合する脅威は無視できないことが示された。
LHDP問題に対しては、非正規化ベンチマークと比較して、提案したフレームワークの次の利点を強調した。
論文 参考訳（メタデータ） (2021-10-07T02:36:14Z) - Risk-Averse Decision Making Under Uncertainty [18.467950783426947]
不確実性条件下での意思決定は、マルコフ決定プロセス(MDP)または部分的に観測可能なMDP(POMDP)を介して記述することができる。
本稿では、動的コヒーレントリスク対策の観点から、MDPとPMDPのポリシーを目的と制約で設計する問題について考察する。
論文 参考訳（メタデータ） (2021-09-09T07:52:35Z) - Strengthening Deterministic Policies for POMDPs [5.092711491848192]
我々は、時間論理制約の形で洗練された仕様をサポートする新しいMILP符号化を提供する。
我々は、メモリベースの決定を包含するために、POMDPの事前処理を採用する。
提案手法の利点は, 計算的トラクタビリティを損なうことなく, 簡単な決定論的政策を強化する柔軟性と, 任意に多くの仕様の証明可能な満足度を強制する能力である。
論文 参考訳（メタデータ） (2020-07-16T14:22:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。