論文の概要: Stopping Criteria for Value Iteration on Concurrent Stochastic Reachability and Safety Games

• arxiv url: http://arxiv.org/abs/2505.21087v1
• Date: Tue, 27 May 2025 12:13:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-28 17:05:58.630932
• Title: Stopping Criteria for Value Iteration on Concurrent Stochastic Reachability and Safety Games
• Title（参考訳）: 同時確率的到達性と安全ゲームにおける価値反復の停止基準
• Authors: Marta Grobelna, Jan Křetínský, Maximilian Weininger,
• Abstract要約: 到達性と安全性を目標としたグラフ上でのゼロサム並列ゲーム(CSG)について検討する。 実際には、値 (VI) は他のアプローチよりも優れており、最も実装された方法である。 CSG に対して有界(つまり区間) VI を提供し、標準 VI をオーバー近似の収束列で補完する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: We consider two-player zero-sum concurrent stochastic games (CSGs) played on graphs with reachability and safety objectives. These include degenerate classes such as Markov decision processes or turn-based stochastic games, which can be solved by linear or quadratic programming; however, in practice, value iteration (VI) outperforms the other approaches and is the most implemented method. Similarly, for CSGs, this practical performance makes VI an attractive alternative to the standard theoretical solution via the existential theory of reals. VI starts with an under-approximation of the sought values for each state and iteratively updates them, traditionally terminating once two consecutive approximations are $\epsilon$-close. However, this stopping criterion lacks guarantees on the precision of the approximation, which is the goal of this work. We provide bounded (a.k.a. interval) VI for CSGs: it complements standard VI with a converging sequence of over-approximations and terminates once the over- and under-approximations are $\epsilon$-close.
• Abstract（参考訳）: 我々は,到達性と安全性を目標としたグラフ上での2プレイヤーゼロサム同時確率ゲーム (CSG) について検討する。 マルコフ決定過程やターンベースの確率ゲームのような退化クラスは線形あるいは二次計画法で解けるが、実際には値反復(VI)は他の手法よりも優れ、最も実装された方法である。 同様に、CSGに対して、この実用的な性能は、VI を実数の存在論的理論による標準理論解の魅力的な代替となる。 VIは、各状態に対する要求値の過小評価から始まり、繰り返し更新する。 しかし、この停止基準は近似の精度の保証に欠けており、これはこの研究の目的である。 標準 VI をオーバー近似の収束列で補完し、オーバー近似とアンダー近似が$\epsilon$-close となると終了する。

関連論文リスト

• Towards Continual Learning Desiderata via HSIC-Bottleneck Orthogonalization and Equiangular Embedding [55.107555305760954]
  本稿では,レイヤワイドパラメータのオーバーライトや決定境界の歪みに起因する,概念的にシンプルで効果的な手法を提案する。 提案手法は,ゼロの指数バッファと1.02倍の差が絶対的に優れていても,競争精度が向上する。
  論文  参考訳（メタデータ） (2024-01-17T09:01:29Z)
• Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods [25.831462008050387]
  グラディエント・Descent(SGD)アルゴリズムは、実際の性能が良く、理論的な理解が欠如していることから、人々の関心を喚起している。 有限収束がより広い合成最適化や非ユークリッドノルムに証明可能な拡張が可能かどうかはまだ不明である。
  論文  参考訳（メタデータ） (2023-12-13T21:41:06Z)
• Stopping Criteria for Value Iteration on Stochastic Games with Quantitative Objectives [0.0]
  マルコフ決定過程(MDP)とゲーム(SG)の古典的解法は価値(VI)である 本稿では、SG 上での VI の停止基準を、全報酬と平均ペイオフで提供し、これらの設定で最初にアルゴリズムを出力する。
  論文  参考訳（メタデータ） (2023-04-19T19:09:55Z)
• HSVI can solve zero-sum Partially Observable Stochastic Games [7.293053431456775]
  2-player 0-sum不完全なゲームを解くための最先端の手法は、線形プログラミングや動的後悔の最小化に依存している。 本稿では,線形プログラミングや反復的手法に依存した手法を補完する,有望なアプローチの新たなファミリーを提案する。
  論文  参考訳（メタデータ） (2022-10-26T11:41:57Z)
• Solving Constrained Variational Inequalities via an Interior Point Method [88.39091990656107]
  制約付き変分不等式(cVI)問題を解くためのインテリアポイントアプローチを開発する。 本稿では,2種類の問題においてACVIの収束保証を提供する。 この設定における以前の作業とは異なり、ACVIは制約が自明でない場合にcVIを解く手段を提供する。
  論文  参考訳（メタデータ） (2022-06-21T17:55:13Z)
• Robust and Adaptive Temporal-Difference Learning Using An Ensemble of Gaussian Processes [70.80716221080118]
  本稿では、時間差学習(TD)による政策評価の世代的視点について考察する。 OS-GPTDアプローチは、状態-逆ペアのシーケンスを観測することにより、与えられたポリシーの値関数を推定するために開発された。 1つの固定カーネルに関連する限られた表現性を緩和するために、GP前の重み付けアンサンブル(E)を用いて代替のスキームを生成する。
  論文  参考訳（メタデータ） (2021-12-01T23:15:09Z)
• HSVI fo zs-POSGs using Concavity, Convexity and Lipschitz Properties [8.80899367147235]
  いくつかのケースでは、最適値関数へのアプローチとして、POMDとDec-MDを評価します。 このアプローチは部分的に観測可能なゲーム(s-POSG)でも成功したが、一般には凹凸特性が知られているにもかかわらず失敗した。 我々はこれらの特性に基づいて、有界近似器と効率的な更新および選択演算子の原型凸性を導出する。
  論文  参考訳（メタデータ） (2021-10-25T13:38:21Z)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  本稿では,SGDA と SCO の最終的な収束保証として,期待されるコヒーレンシティ条件を導入し,その利点を説明する。 定常的なステップサイズを用いた場合、両手法の線形収束性を解の近傍に証明する。 我々の収束保証は任意のサンプリングパラダイムの下で保たれ、ミニバッチの複雑さに関する洞察を与える。
  論文  参考訳（メタデータ） (2021-06-30T18:32:46Z)
• Higher Performance Visual Tracking with Dual-Modal Localization [106.91097443275035]
  Visual Object Tracking (VOT)は、堅牢性と正確性の両方に同期性を必要とする。 ONRによるロバストなローカリゼーション抑制器とOFCによるターゲットセンターへの正確なローカリゼーションにより、ターゲットローカリゼーションのためのデュアルモーダルフレームワークを提案します。
  論文  参考訳（メタデータ） (2021-03-18T08:47:56Z)
• Stopping Criteria for, and Strong Convergence of, Stochastic Gradient Descent on Bottou-Curtis-Nocedal Functions [0.0]
  勾配Descent法(SGD)の停止基準は、非サイズ関数の解析にしばしば用いられる。 我々は,非サイズの関数とボットゥー・ノッセダル関数を解析するのに使用できる基準を開発する。 我々の研究の結果、我々の研究は新たな適応的なステップスキームの開発に利用できる。
  論文  参考訳（メタデータ） (2020-04-01T14:44:43Z)
• Bottom-Up Temporal Action Localization with Mutual Regularization [107.39785866001868]
  TALの最先端の解決策は、3つの行動指示相のフレームレベルの確率を評価することである。 学習手順を相互に規則化するための2つの規則化用語を導入する。 実験は2つの人気のTALデータセット、THUMOS14とActivityNet1.3で行われている。
  論文  参考訳（メタデータ） (2020-02-18T03:59:13Z)

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

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