論文の概要: Stopping Criteria for Value Iteration on Stochastic Games with Quantitative Objectives

• arxiv url: http://arxiv.org/abs/2304.09930v1
• Date: Wed, 19 Apr 2023 19:09:55 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-21 15:15:42.949279
• Title: Stopping Criteria for Value Iteration on Stochastic Games with Quantitative Objectives
• Title（参考訳）: 量的対象を持つ確率ゲームにおける値反復の停止基準
• Authors: Jan K\v{r}et\'insk\'y, Tobias Meggendorfer, Maximilian Weininger
• Abstract要約: マルコフ決定過程(MDP)とゲーム(SG)の古典的解法は価値(VI)である 本稿では、SG 上での VI の停止基準を、全報酬と平均ペイオフで提供し、これらの設定で最初にアルゴリズムを出力する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A classic solution technique for Markov decision processes (MDP) and stochastic games (SG) is value iteration (VI). Due to its good practical performance, this approximative approach is typically preferred over exact techniques, even though no practical bounds on the imprecision of the result could be given until recently. As a consequence, even the most used model checkers could return arbitrarily wrong results. Over the past decade, different works derived stopping criteria, indicating when the precision reaches the desired level, for various settings, in particular MDP with reachability, total reward, and mean payoff, and SG with reachability. In this paper, we provide the first stopping criteria for VI on SG with total reward and mean payoff, yielding the first anytime algorithms in these settings. To this end, we provide the solution in two flavours: First through a reduction to the MDP case and second directly on SG. The former is simpler and automatically utilizes any advances on MDP. The latter allows for more local computations, heading towards better practical efficiency. Our solution unifies the previously mentioned approaches for MDP and SG and their underlying ideas. To achieve this, we isolate objective-specific subroutines as well as identify objective-independent concepts. These structural concepts, while surprisingly simple, form the very essence of the unified solution.
• Abstract（参考訳）: マルコフ決定過程(MDP)と確率ゲーム(SG)の古典的な解法は、価値反復(VI)である。 優れた実用性能のため、この近似手法は一般的には正確な手法よりも好まれるが、結果の不正確性に関する実践的な限界は近年まで与えられなかった。 その結果、最もよく使われるモデルチェッカーでさえ、任意に間違った結果を返すことができた。 過去10年間で、様々な作業が停止基準を導出し、その精度が望ましいレベルに達したとき、特にリーチビリティ、総報酬、平均支払、到達性を備えたSGといった様々な設定で示していた。 本稿では、SG 上での VI の停止基準を、全報酬と平均ペイオフで提供し、これらの設定で最初にアルゴリズムを出力する。 この目的のために、我々は、まず、MDPケースへの還元と、SG上で直接的に2つのフレーバーの解を提供する。 前者は単純で、自動的にMDPの進歩を利用する。 後者はより局所的な計算を可能にし、より実用的な効率を目指しています。 我々のソリューションは、前述のMDPとSGのアプローチとその基盤となるアイデアを統一する。 これを実現するため、目的固有のサブルーチンを分離し、目的に依存しない概念を識別する。 これらの構造的概念は驚くほど単純であるが、統一ソリューションの本質を形作っている。

関連論文リスト

• Learning Algorithms for Verification of Markov Decision Processes [20.5951492453299]
  マルコフ決定過程(MDP)の検証に学習アルゴリズムを適用するための一般的な枠組みを提案する。 提案するフレームワークは,検証における中核的な問題である確率的到達性に重点を置いている。
  論文  参考訳（メタデータ） (2024-03-14T08:54:19Z)
• Rethinking Model Selection and Decoding for Keyphrase Generation with Pre-trained Sequence-to-Sequence Models [76.52997424694767]
  キーフレーズ生成(英: Keyphrase Generation, KPG)は、NLPにおける長年の課題である。 Seq2seq 事前訓練言語モデル (PLM) は KPG に転換期を迎え、有望な性能改善をもたらした。 本稿では, PLM に基づく KPG におけるモデル選択と復号化戦略の影響について, 系統解析を行った。
  論文  参考訳（メタデータ） (2023-10-10T07:34:45Z)
• Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environments [48.96971760679639]
  マルコフ決定過程(MDP)の分散依存的後悔境界について検討する。 環境の微細な分散特性を特徴付けるための2つの新しい環境規範を提案する。 モデルに基づく手法では、MVPアルゴリズムの変種を設計する。 特に、この境界は極小かつ決定論的 MDP に対して同時に最適である。
  論文  参考訳（メタデータ） (2023-01-31T06:54:06Z)
• PAC Statistical Model Checking of Mean Payoff in Discrete- and Continuous-Time MDP [0.34410212782758043]
  我々は,未知のMDPにおいて,平均ペイオフをほぼ正確に計算する最初のアルゴリズムを提供する。 状態空間に関する知識は一切必要とせず、最小遷移確率の低い境界のみである。 提案アルゴリズムは, ほぼ正しいPAC境界を提供するだけでなく, 標準ベンチマークで実験を行うことにより, その実用性を実証する。
  論文  参考訳（メタデータ） (2022-06-03T09:13:27Z)
• Under-Approximating Expected Total Rewards in POMDPs [68.8204255655161]
  我々は、部分的に観測可能なマルコフ決定プロセス(POMDP)において、ゴール状態に達するための最適な総報酬を考える。 我々は、MILP(mixed-integer linear programming)を用いて、そのような最小限の確率シフトを見つけ、実験により、我々の手法がかなりうまく拡張可能であることを示す。
  論文  参考訳（メタデータ） (2022-01-21T16:43:03Z)
• Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processes [13.908826484332282]
  そこで我々は,コストの抑えられたマルコフ決定プロセス問題を解決するために,オンライン・プリマル・デュアル・アクター・クリティカル法について検討した。 本稿では,CMDP問題の解法として,オンライン・プリマル・デュアル・アクター・クリティカル法の有限時間複雑性を初めて検討した。
  論文  参考訳（メタデータ） (2021-10-21T18:05:40Z)
• Rethinking Counting and Localization in Crowds:A Purely Point-Based Framework [59.578339075658995]
  そこで本稿では,共同クラウドカウントと個別ローカライゼーションのための純粋にポイントベースのフレームワークを提案する。 我々は、P2PNet(Point to Point Network)と呼ばれる、このフレームワークの下で直感的なソリューションを設計する。
  論文  参考訳（メタデータ） (2021-07-27T11:41:50Z)
• A Retrospective Approximation Approach for Smooth Stochastic Optimization [0.2867517731896504]
  グラディエント(グラディエント、英: Gradient、SG)とは、最適化(SO)問題をスムーズ(ノンフィクション)な目標値で解くための補足的反復手法である。
  論文  参考訳（メタデータ） (2021-03-07T16:29:36Z)
• Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
  無限水平マルコフ決定過程(MDP)における最適政策学習の問題を考える。 リプシッツ連続関数を用いた凸プログラミング問題に対してミラー・ディクセントの変種が提案されている。 このアルゴリズムを一般の場合において解析し,提案手法の動作中に誤差を蓄積しない収束率の推定値を得る。
  論文  参考訳（メタデータ） (2021-02-27T19:28:39Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)

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

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