論文の概要: Taming Infinity one Chunk at a Time: Concisely Represented Strategies in One-Counter MDPs

• arxiv url: http://arxiv.org/abs/2503.00788v1
• Date: Sun, 02 Mar 2025 08:32:17 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-05 19:13:43.829375
• Title: Taming Infinity one Chunk at a Time: Concisely Represented Strategies in One-Counter MDPs
• Title（参考訳）: 一度に無限大に挑戦する: ワンカウンタのMDPにおける簡潔に表現された戦略
• Authors: Michal Ajdarów, James C. A. Main, Petr Novotný, Mickael Randour,
• Abstract要約: 無限のMDPのクラスについて研究する:1カウンタMDP(OC-MDP) 目標状態(状態到達性)と目標状態(反値ゼロ)の2つの特徴的目的を考察する。 間隔におけるカウンター値の(おそらく無限)分割に基づく簡潔に表現された戦略の2つの自然なクラスを導入する。
• 参考スコア（独自算出の注目度）: 2.7262923206583136
• License:
• Abstract: Markov decision processes (MDPs) are a canonical model to reason about decision making within a stochastic environment. We study a fundamental class of infinite MDPs: one-counter MDPs (OC-MDPs). They extend finite MDPs via an associated counter taking natural values, thus inducing an infinite MDP over the set of configurations (current state and counter value). We consider two characteristic objectives: reaching a target state (state-reachability), and reaching a target state with counter value zero (selective termination). The synthesis problem for the latter is not known to be decidable and connected to major open problems in number theory. Furthermore, even seemingly simple strategies (e.g., memoryless ones) in OC-MDPs might be impossible to build in practice (due to the underlying infinite configuration space): we need finite, and preferably small, representations. To overcome these obstacles, we introduce two natural classes of concisely represented strategies based on a (possibly infinite) partition of counter values in intervals. For both classes, and both objectives, we study the verification problem (does a given strategy ensure a high enough probability for the objective?), and two synthesis problems (does there exist such a strategy?): one where the interval partition is fixed as input, and one where it is only parameterized. We develop a generic approach based on a compression of the induced infinite MDP that yields decidability in all cases, with all complexities within PSPACE.
• Abstract（参考訳）: マルコフ決定プロセス(MDP)は確率的環境における意思決定を推論する標準的なモデルである。 我々は、無限のMDPの基本クラスである1-counter MDP(OC-MDP)を研究する。 有限の MDP を、関連するカウンタが自然な値を取ることによって拡張し、構成の集合(現在の状態とカウンタ値)上で無限の MDP を誘導する。 目標状態(状態到達可能性)と、対向値ゼロ(選択終了)の目標状態(選択終了)の2つの特徴的目的を考察する。 後者の合成問題は決定可能であることは知られておらず、数論における主要な開問題と結びついている。 さらに、OC-MDPの一見単純な戦略(例えば、メモリレス戦略)でさえ(基礎となる無限の構成空間のために)実際に構築することは不可能かもしれない。 これらの障害を克服するために、インターバルにおけるカウンター値の(おそらく無限)分割に基づいて、簡潔に表現された戦略の2つの自然なクラスを導入する。 両クラスおよび両目的に対して、検証問題(与えられた戦略が目的に対して十分高い確率を保証するか?)と、2つの合成問題(そのような戦略が存在するか?)について検討する。 我々は、PSPACE内のすべての複雑さを持つ全てのケースにおいて決定可能性をもたらす、誘導無限MDPの圧縮に基づく汎用的なアプローチを開発する。

関連論文リスト

• Solving Robust Markov Decision Processes: Generic, Reliable, Efficient [3.789219860006095]
  マルコフ決定プロセス(MDP)は確率の存在下でのシーケンシャルな意思決定のための確立されたモデルである。 我々は、汎用的で信頼性があり、効率的なRMDPを解くためのフレームワークを提供する。 我々のプロトタイプ実装は、既存のツールよりも桁違いに優れている。
  論文  参考訳（メタデータ） (2024-12-13T14:55:48Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• Twice Regularized Markov Decision Processes: The Equivalence between Robustness and Regularization [64.60253456266872]
  マルコフ決定プロセス(MDP)は、変化または部分的に知られているシステムのダイナミクスを扱うことを目的としている。 規則化されたMDPは、時間的複雑さを損なうことなく、ポリシー学習の安定性を高める。 ベルマン作用素は、収束と一般化を保証する計画と学習スキームを導出することができる。
  論文  参考訳（メタデータ） (2023-03-12T13:03:28Z)
• B$^3$RTDP: A Belief Branch and Bound Real-Time Dynamic Programming Approach to Solving POMDPs [17.956744635160568]
  我々は,Belief Branch and Bound RTDP (B$3$RTDP) と呼ぶRTDP-Belアルゴリズムの拡張を提案する。 我々のアルゴリズムは有界値関数表現を使い、これを2つの新しい方法で活用する。 B$3$RTDPは、既知のPOMDP問題に対する最先端のSARSOP解法よりも少ない時間で大きなリターンが得られることを実証的に実証した。
  論文  参考訳（メタデータ） (2022-10-22T21:42:59Z)
• Near-Optimal Sample Complexity Bounds for Constrained MDPs [25.509556551558834]
  減算CMDPにおける準最適政策を学習するために,サンプルの複雑さを極小値と下位値で表す。 CMDPの学習は,少ない制約違反を許す場合と同等に容易であるが,制約違反を要求しない場合には本質的に困難であることを示す。
  論文  参考訳（メタデータ） (2022-06-13T15:58:14Z)
• A Fully Polynomial Time Approximation Scheme for Constrained MDPs and Stochastic Shortest Path under Local Transitions [2.512827436728378]
  我々は,(C)C-MDPの構造,特に局所遷移を伴う重要な変種について検討した。 本研究では,(C)C-MDPの最適決定性ポリシを(ほぼ)計算する完全時間近似手法を提案する。
  論文  参考訳（メタデータ） (2022-04-10T22:08:33Z)
• Under-Approximating Expected Total Rewards in POMDPs [68.8204255655161]
  我々は、部分的に観測可能なマルコフ決定プロセス(POMDP)において、ゴール状態に達するための最適な総報酬を考える。 我々は、MILP(mixed-integer linear programming)を用いて、そのような最小限の確率シフトを見つけ、実験により、我々の手法がかなりうまく拡張可能であることを示す。
  論文  参考訳（メタデータ） (2022-01-21T16:43:03Z)
• A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs [117.82903457289584]
  有限水平マルコフ決定過程(MDPs)における新たな問題依存的下界を導出する。 我々の下界は一般の場合よりもかなり小さく、最小の作用ギャップでスケールしないことが示される。 この最後の結果($poly(H)$の条件で、$H$は地平線である)は、楽観的なアルゴリズムのポリシーギャップに基づいて、後悔の意を表すことによって達成可能であることを示す。
  論文  参考訳（メタデータ） (2021-06-24T13:46:09Z)
• Modular Deep Reinforcement Learning for Continuous Motion Planning with Temporal Logic [59.94347858883343]
  本稿では,マルコフ決定過程(MDP)をモデルとした自律動的システムの運動計画について検討する。 LDGBA と MDP の間に組込み製品 MDP (EP-MDP) を設計することである。 モデルフリー強化学習(RL)のためのLDGBAベースの報酬形成と割引スキームは、EP-MDP状態にのみ依存する。
  論文  参考訳（メタデータ） (2021-02-24T01:11:25Z)
• RL for Latent MDPs: Regret Guarantees and a Lower Bound [74.41782017817808]
  後期マルコフ決定過程(LMDP)における強化学習における後悔問題の検討 LMDPにおいて、M$可能なMDPのセットからMDPをランダムに描画するが、選択したMDPの同一性はエージェントに明らかにしない。 鍵となるリンクは、MDPシステムの力学の分離の概念であることを示す。
  論文  参考訳（メタデータ） (2021-02-09T16:49:58Z)

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

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