論文の概要: HSVI can solve zero-sum Partially Observable Stochastic Games

• arxiv url: http://arxiv.org/abs/2210.14640v1
• Date: Wed, 26 Oct 2022 11:41:57 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-27 14:42:19.234613
• Title: HSVI can solve zero-sum Partially Observable Stochastic Games
• Title（参考訳）: HSVIはゼロサム部分観測確率ゲームを解くことができる
• Authors: Aur\'elien Delage, Olivier Buffet, Jilles S. Dibangoye, Abdallah Saffidine
• Abstract要約: 2-player 0-sum不完全なゲームを解くための最先端の手法は、線形プログラミングや動的後悔の最小化に依存している。 本稿では,線形プログラミングや反復的手法に依存した手法を補完する,有望なアプローチの新たなファミリーを提案する。
• 参考スコア（独自算出の注目度）: 7.293053431456775
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: State-of-the-art methods for solving 2-player zero-sum imperfect information games rely on linear programming or regret minimization, though not on dynamic programming (DP) or heuristic search (HS), while the latter are often at the core of state-of-the-art solvers for other sequential decision-making problems. In partially observable or collaborative settings (e.g., POMDPs and Dec- POMDPs), DP and HS require introducing an appropriate statistic that induces a fully observable problem as well as bounding (convex) approximators of the optimal value function. This approach has succeeded in some subclasses of 2-player zero-sum partially observable stochastic games (zs- POSGs) as well, but how to apply it in the general case still remains an open question. We answer it by (i) rigorously defining an equivalent game to work with, (ii) proving mathematical properties of the optimal value function that allow deriving bounds that come with solution strategies, (iii) proposing for the first time an HSVI-like solver that provably converges to an $\epsilon$-optimal solution in finite time, and (iv) empirically analyzing it. This opens the door to a novel family of promising approaches complementing those relying on linear programming or iterative methods.
• Abstract（参考訳）: 2-player 0-sumの不完全な情報ゲームを解決する最先端の手法はリニアプログラミングや後悔の最小化に依存しているが、動的プログラミング(DP)やヒューリスティック検索(HS)には依存しない。 部分的に観測可能あるいは協調的な設定(例えば、POMDPやDecPOMDP)では、DPとHSは最適な値関数のバウンディング(凸)近似と同様に、完全に観測可能な問題を誘導する適切な統計学を導入する必要がある。 このアプローチは、2-プレーヤ 0-sum の部分可観測確率ゲーム (zs- POSGs) のサブクラスにも成功したが、一般の場合でもどのように適用すればよいかはまだ未解決のままである。 私たちは答えます (i)これと同等のゲームを厳格に定義すること。 (ii)解戦略に付随する境界を導出できる最適値関数の数学的性質を証明すること。 (iii) 有限時間で$\epsilon$-optimal解に確実に収束するhsviライクな解法を初めて提案すること、及び (iv)経験的に分析する。 これは、線形プログラミングや反復的メソッドに依存する人たちを補完する、有望なアプローチの新たなファミリーへの扉を開く。

関連論文リスト

• $ε$-Optimally Solving Zero-Sum POSGs [4.424170214926035]
  ゼロサム部分観測可能なゲームの解法は、元のゲームを「占有マルコフゲーム」と呼ばれる新しいゲームに埋め込む。 本稿では、この制限を克服するために、最適値関数の新たな一様連続性特性を利用する。
  論文  参考訳（メタデータ） (2024-05-29T08:34:01Z)
• Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features [79.39965431772626]
  Frank-Wolfe (FW) 法は、構造化制約による最適化問題の解法として一般的な手法である。 有限サム勾配の最小化のためのアルゴリズムの2つの新しい変種を示す。
  論文  参考訳（メタデータ） (2023-04-23T20:05:09Z)
• Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms [66.8634598612777]
  ナッシュ均衡(NE)はマルチプレイヤーゲームにおいて全てのプレイヤーに受け入れられることを示す。 また、一般理論から一歩ずつ一方的に利益を得ることはできないことも示している。
  論文  参考訳（メタデータ） (2023-01-19T11:36:50Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。 提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-12-19T14:48:54Z)
• HSVI fo zs-POSGs using Concavity, Convexity and Lipschitz Properties [8.80899367147235]
  いくつかのケースでは、最適値関数へのアプローチとして、POMDとDec-MDを評価します。 このアプローチは部分的に観測可能なゲーム(s-POSG)でも成功したが、一般には凹凸特性が知られているにもかかわらず失敗した。 我々はこれらの特性に基づいて、有界近似器と効率的な更新および選択演算子の原型凸性を導出する。
  論文  参考訳（メタデータ） (2021-10-25T13:38:21Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
  無限水平マルコフ決定過程(MDP)における最適政策学習の問題を考える。 リプシッツ連続関数を用いた凸プログラミング問題に対してミラー・ディクセントの変種が提案されている。 このアルゴリズムを一般の場合において解析し,提案手法の動作中に誤差を蓄積しない収束率の推定値を得る。
  論文  参考訳（メタデータ） (2021-02-27T19:28:39Z)
• Provably Efficient Policy Gradient Methods for Two-Player Zero-Sum Markov Games [95.70078702838654]
  本論文では,自然政策グラディエントアルゴリズムの自然拡張について検討する。 我々は,サンプル数,反復数,集中係数,近似誤差の観点から,アルゴリズムの性能を徹底的に評価する。
  論文  参考訳（メタデータ） (2021-02-17T17:49:57Z)
• On Satisficing in Quantitative Games [30.53498001438171]
  本研究は,割引コストモデルを用いた2プレイヤーグラフゲームにおける満足度問題を定義し,検討する。 最適化問題と同様に数値手法で満足度を解くことができるが、この手法は最適化よりも説得力のある利点を示さない。
  論文  参考訳（メタデータ） (2021-01-06T07:47:13Z)
• Provably Convergent Working Set Algorithm for Non-Convex Regularized Regression [0.0]
  本稿では、収束保証付き非正則正規化器のためのワーキングセットアルゴリズムを提案する。 その結果,ブロックコーディネートや勾配ソルバの完全解法と比較して高い利得を示した。
  論文  参考訳（メタデータ） (2020-06-24T07:40:31Z)
• On the Impossibility of Global Convergence in Multi-Loss Optimization [10.081768261298098]
  所望の収束特性が任意のアルゴリズムに対して同時に保持できないことを証明する。 我々の結果は、それぞれのアルゴリズムよりも、満足のいく結果のないゲームの存在と関係がある。 ML実践者にとって、高次元ゲームにそのような振る舞いが生じるかどうかは、未解決の問題である。
  論文  参考訳（メタデータ） (2020-05-26T12:11:18Z)

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

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