論文の概要: Graph-Based Reductions for Parametric and Weighted MDPs
- arxiv url: http://arxiv.org/abs/2305.05739v1
- Date: Tue, 9 May 2023 19:33:43 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-11 15:35:22.685751
- Title: Graph-Based Reductions for Parametric and Weighted MDPs
- Title（参考訳）: パラメトリックおよび重み付きMDPのグラフベース削減
- Authors: Kasper Engelen, Guillermo A. P\'erez, and Shrisha Rao
- Abstract要約: パラメトリックマルコフ決定過程における到達性低下の複雑さについて検討する。
計算複雑性の観点では、p が q よりも悪くないかを決定することは coETR 完全である。
- 参考スコア（独自算出の注目度）: 3.1542695050861544
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the complexity of reductions for weighted reachability in parametric
Markov decision processes. That is, we say a state p is never worse than q if
for all valuations of the polynomial indeterminates it is the case that the
maximal expected weight that can be reached from p is greater than the same
value from q. In terms of computational complexity, we establish that
determining whether p is never worse than q is coETR-complete. On the positive
side, we give a polynomial-time algorithm to compute the equivalence classes of
the order we study for Markov chains. Additionally, we describe and implement
two inference rules to under-approximate the never-worse relation and
empirically show that it can be used as an efficient preprocessing step for the
analysis of large Markov decision processes.
- Abstract（参考訳）: パラメトリックマルコフ決定過程における重み付き到達可能性の低減の複雑さについて検討する。
すなわち、多項式のすべての評価値が不定となるとき、状態 p が q よりも悪いことはないと言うのは、p から到達可能な最大期待重量が q から同じ値より大きい場合である。
計算複雑性の観点では、p が q よりも悪くないかを決定することは coETR 完全である。
正の側では、マルコフ連鎖の研究する順序の同値類を計算する多項式時間アルゴリズムを与える。
さらに,never-worse関係をほぼ満たさない2つの推論ルールを記述・実装し,大規模マルコフ決定過程の解析に効率的な前処理ステップとして使用できることを示す。
関連論文リスト
- Performative Reinforcement Learning with Linear Markov Decision Process [14.75815792682734]
提案手法がマルコフ決定過程の報酬と遷移の両方に影響を及ぼすような表現的強化学習の設定について検討する。
大規模MDPの主要な理論モデルであるEmphlinear Markov決定過程を一般化する。
論文 参考訳（メタデータ） (2024-11-07T23:04:48Z) - On additive error approximations to #BQP [0.34089646689382486]
我々は、#BQPとして知られる数え上げクラスの量子一般化に対する加法近似について研究する。
まず,#BQP問題に対する加算近似を,対応する検証回路における証人量子ビット数の誤差指数に近似する効率的な量子アルゴリズムが存在することを示す。
論文 参考訳（メタデータ） (2024-11-04T20:51:20Z) - Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
問題入力から問題出力までの完全な量子回路レベルのアルゴリズム記述を提供する。
アルゴリズムの実行に必要な論理量子ビットの数と非クリフォードTゲートの量/深さを報告する。
論文 参考訳（メタデータ） (2022-11-22T18:54:48Z) - Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
制約付き非線形最適化問題のオンライン統計的推測を考察する。
これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
論文 参考訳（メタデータ） (2022-05-27T00:34:03Z) - Computing the quantum guesswork: a quadratic assignment problem [6.445605125467573]
従来の計算手法は、半定値の標準的なプログラミング技術に基づいていた。
確率分布が均一な量子ビットアンサンブルの量子推定処理を計算すれば、よりクワッドラティックなスピードアップがもたらされることを示す。
例として、正則および準正則なクォービット状態集合の推理を計算する。
論文 参考訳（メタデータ） (2021-12-03T01:24:57Z) - Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
マルコフ決定過程における純粋探索問題について検討する。
エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
論文 参考訳（メタデータ） (2021-06-05T09:16:28Z) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。
また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
論文 参考訳（メタデータ） (2020-11-19T10:00:54Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - Provably Efficient Model-Free Algorithm for MDPs with Peak Constraints [38.2783003051101]
本稿では,有限地平線における全報酬の最大化と,各エポックにおける制約を確率1で満たすため,エージェントがポリシーを選択する,制約付きマルコフ決定プロセス(PCMDP)について考察する。
そこで本研究では,PCMDP問題を制約のない問題に変換するモデルフリーアルゴリズムを提案し,Q-ラーニングに基づくアプローチを適用した。
論文 参考訳（メタデータ） (2020-03-11T23:23:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。