論文の概要: On Bellman's Optimality Principle for zs-POSGs

• arxiv url: http://arxiv.org/abs/2006.16395v1
• Date: Mon, 29 Jun 2020 21:23:10 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-15 14:56:39.272174
• Title: On Bellman's Optimality Principle for zs-POSGs
• Title（参考訳）: zs-POSGに対するベルマンの最適原理について
• Authors: Olivier Buffet, Jilles Dibangoye, Aur\'elien Delage, Abdallah Saffidine, Vincent Thomas
• Abstract要約: 多くの非自明な逐次決定問題はベルマンの最適性原理に頼って効率よく解決される。 2-player 0-sum の部分観測可能なゲーム (zs-POSGs) にどのように適用できるかを示す。 HSVIアルゴリズムのバージョンは、有限時間で$epsilon$-Nash平衡を証明できる。
• 参考スコア（独自算出の注目度）: 9.650892609919811
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many non-trivial sequential decision-making problems are efficiently solved by relying on Bellman's optimality principle, i.e., exploiting the fact that sub-problems are nested recursively within the original problem. Here we show how it can apply to (infinite horizon) 2-player zero-sum partially observable stochastic games (zs-POSGs) by (i) taking a central planner's viewpoint, which can only reason on a sufficient statistic called occupancy state, and (ii) turning such problems into zero-sum occupancy Markov games (zs-OMGs). Then, exploiting the Lipschitz-continuity of the value function in occupancy space, one can derive a version of the HSVI algorithm (Heuristic Search Value Iteration) that provably finds an $\epsilon$-Nash equilibrium in finite time.
• Abstract（参考訳）: 多くの非自明なシーケンシャルな意思決定問題はベルマンの最適性原理、すなわち、サブプロブレムが元の問題の中に再帰的に入れ替わるという事実を利用して効率的に解決される。 ここでは、2-player 0-sum part observable stochastic game (zs-POSGs) に対してどのように適用できるかを示す。 (一)中心計画者の視点をとれば、占有状態という十分な統計を理由付けることができる。 (2)そのような問題をゼロサム占有マルコフゲーム(zs-OMGs)に変換する。 次に、占有空間における値関数のリプシッツ連続性を利用して、有限時間で$\epsilon$-Nash平衡を証明できるHSVIアルゴリズム(Huristic Search Value Iteration)のバージョンを導出することができる。

関連論文リスト

• $ε$-Optimally Solving Zero-Sum POSGs [4.424170214926035]
  ゼロサム部分観測可能なゲームの解法は、元のゲームを「占有マルコフゲーム」と呼ばれる新しいゲームに埋め込む。 本稿では、この制限を克服するために、最適値関数の新たな一様連続性特性を利用する。
  論文  参考訳（メタデータ） (2024-05-29T08:34:01Z)
• HSVI can solve zero-sum Partially Observable Stochastic Games [7.293053431456775]
  2-player 0-sum不完全なゲームを解くための最先端の手法は、線形プログラミングや動的後悔の最小化に依存している。 本稿では,線形プログラミングや反復的手法に依存した手法を補完する,有望なアプローチの新たなファミリーを提案する。
  論文  参考訳（メタデータ） (2022-10-26T11:41:57Z)
• Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization [94.19177623349947]
  非滑らかな非最適化問題は、機械学習とビジネス製造に現れる。 2つのコア課題は、有限収束を保証する効率的な方法の開発を妨げる。 GFMとSGFMの2相版も提案され, 改良された大規模評価結果が得られた。
  論文  参考訳（メタデータ） (2022-09-12T06:53:24Z)
• Learning Two-Player Mixture Markov Games: Kernel Function Approximation and Correlated Equilibrium [157.0902680672422]
  非線形関数近似を用いた2プレイヤーゼロサムマルコフゲームにおけるナッシュ平衡の学習について検討する。 双対性ギャップを最小化してナッシュ均衡を求める新しいオンライン学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-10T14:21:54Z)
• Regularized Gradient Descent Ascent for Two-Player Zero-Sum Markov Games [16.09467599829253]
  本研究では,2プレーヤゼロサムゲームにおけるナッシュ平衡を求める問題について検討する。 我々の主な貢献は、正規化パラメータの適切な選択の下で、勾配が元の非正規化問題のナッシュ平衡に傾くことを示すことである。
  論文  参考訳（メタデータ） (2022-05-27T03:24:12Z)
• HSVI fo zs-POSGs using Concavity, Convexity and Lipschitz Properties [8.80899367147235]
  いくつかのケースでは、最適値関数へのアプローチとして、POMDとDec-MDを評価します。 このアプローチは部分的に観測可能なゲーム(s-POSG)でも成功したが、一般には凹凸特性が知られているにもかかわらず失敗した。 我々はこれらの特性に基づいて、有界近似器と効率的な更新および選択演算子の原型凸性を導出する。
  論文  参考訳（メタデータ） (2021-10-25T13:38:21Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。 我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。 MRP のサブクラスに対する minimax の下位境界を証明する。
  論文  参考訳（メタデータ） (2021-09-24T14:48:20Z)
• Low-Complexity Algorithm for Restless Bandits with Imperfect Observations [1.4542411354617986]
  我々は、強化学習と最適化において幅広い応用分野を見出す、レスレス・バンディット問題の一類を考察する。 我々は,観測誤差を伴う一般的なレスト・バンディット・モデルに容易に適用可能な,高い性能を実現する低複雑性アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-08-09T05:01:19Z)
• A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm for Bilevel Optimization [112.59170319105971]
  問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。 MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
  論文  参考訳（メタデータ） (2021-02-15T07:10:33Z)
• Learning Near Optimal Policies with Low Inherent Bellman Error [115.16037976819331]
  エピソード強化学習における近似線形作用値関数を用いた探索問題について検討する。 我々は,検討した設定に対して最適な統計率を達成するアルゴリズムを用いて,Emphbatch仮定のみを用いて探索を行うことが可能であることを示す。
  論文  参考訳（メタデータ） (2020-02-29T02:02:40Z)
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
  非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。 特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
  論文  参考訳（メタデータ） (2020-02-10T23:23:04Z)

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

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