論文の概要: $ε$-Optimally Solving Zero-Sum POSGs

• arxiv url: http://arxiv.org/abs/2406.00054v1
• Date: Wed, 29 May 2024 08:34:01 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-06 08:53:00.420038
• Title: $ε$-Optimally Solving Zero-Sum POSGs
• Title（参考訳）: ε$-Optimally Solving Zero-Sum POSGs
• Authors: Erwan Escudie, Matthia Sabatelli, Jilles Dibangoye,
• Abstract要約: ゼロサム部分観測可能なゲームの解法は、元のゲームを「占有マルコフゲーム」と呼ばれる新しいゲームに埋め込む。 本稿では、この制限を克服するために、最適値関数の新たな一様連続性特性を利用する。
• 参考スコア（独自算出の注目度）: 4.424170214926035
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A recent method for solving zero-sum partially observable stochastic games (zs-POSGs) embeds the original game into a new one called the occupancy Markov game. This reformulation allows applying Bellman's principle of optimality to solve zs-POSGs. However, improving a current solution requires solving a linear program with exponentially many potential constraints, which significantly restricts the scalability of this approach. This paper exploits the optimal value function's novel uniform continuity properties to overcome this limitation. We first construct a new operator that is computationally more efficient than the state-of-the-art update rules without compromising optimality. In particular, improving a current solution now involves a linear program with an exponential drop in constraints. We then also show that point-based value iteration algorithms utilizing our findings improve the scalability of existing methods while maintaining guarantees in various domains.
• Abstract（参考訳）: ゼロサム部分可観測確率ゲーム (zs-POSGs) の解法は、元のゲームを占領マルコフゲームと呼ばれる新しいゲームに埋め込む。 この再構成により、zs-POSGを解くためにベルマンの最適性原理を適用することができる。 しかし、現在のソリューションを改善するには、指数関数的に多くの潜在的な制約を持つ線形プログラムを解く必要があり、このアプローチのスケーラビリティを著しく制限する。 本稿では、この制限を克服するために、最適値関数の新たな一様連続性特性を利用する。 まず、最適性を損なうことなく、最新の更新ルールよりも計算効率の良い新しい演算子を構築する。 特に、現在の解を改善するには、指数関数的な制約の減少を伴う線形プログラムが必要となる。 また,各領域における保証を維持しつつ,既存の手法のスケーラビリティを向上させる点ベースの値反復アルゴリズムについても示す。

関連論文リスト

• A Penalty-Based Guardrail Algorithm for Non-Decreasing Optimization with Inequality Constraints [1.5498250598583487]
  伝統的な数学的プログラミングの解法は制約付き最小化問題を解くのに長い計算時間を必要とする。 ペナルティに基づくガードレールアルゴリズム(PGA)を提案する。
  論文  参考訳（メタデータ） (2024-05-03T10:37:34Z)
• Improving Sample Efficiency of Model-Free Algorithms for Zero-Sum Markov Games [66.2085181793014]
  モデルフリーのステージベースQ-ラーニングアルゴリズムはモデルベースアルゴリズムと同じ$H$依存の最適性を享受できることを示す。 本アルゴリズムは,楽観的値関数と悲観的値関数のペアとして参照値関数を更新するキーとなる新しい設計を特徴とする。
  論文  参考訳（メタデータ） (2023-08-17T08:34:58Z)
• Strictly Low Rank Constraint Optimization -- An Asymptotically $\mathcal{O}(\frac{1}{t^2})$ Method [5.770309971945476]
  最適解における空間性を促進するために,テキスト規則化を用いた非テキスト・非滑らかな問題のクラスを提案する。 我々のアルゴリズムは、滑らかな凸問題に対する一階法に対するネステロフの最適収束と全く同じ$Ofrac(t2)$の特異収束を達成することができることを示す。
  論文  参考訳（メタデータ） (2023-07-04T16:55:41Z)
• Optimizing NOTEARS Objectives via Topological Swaps [41.18829644248979]
  本稿では,候補アルゴリズムの集合に有効な手法を提案する。 内部レベルでは、対象が与えられた場合、オフ・ザ・アート制約を利用する。 提案手法は,他のアルゴリズムのスコアを大幅に改善する。
  論文  参考訳（メタデータ） (2023-05-26T21:49:37Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Learning to Optimize with Stochastic Dominance Constraints [103.26714928625582]
  本稿では,不確実量を比較する問題に対して,単純かつ効率的なアプローチを開発する。 我々はラグランジアンの内部最適化をサロゲート近似の学習問題として再考した。 提案したライト-SDは、ファイナンスからサプライチェーン管理に至るまで、いくつかの代表的な問題において優れた性能を示す。
  論文  参考訳（メタデータ） (2022-11-14T21:54:31Z)
• Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time Guarantees [56.848265937921354]
  逆強化学習(IRL)は報酬関数と関連する最適ポリシーを回復することを目的としている。 IRLの多くのアルゴリズムは本質的にネスト構造を持つ。 我々は、報酬推定精度を損なわないIRLのための新しいシングルループアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-10-04T17:13:45Z)
• A framework for bilevel optimization that enables stochastic and global variance reduction algorithms [17.12280360174073]
  双レベル最適化は、他の関数のarg最小値を含む値関数を最小化する問題である。 本稿では, 内部問題の解, 線形系の解, 主変数を同時に発展させる新しい枠組みを提案する。 我々のフレームワークにおけるSAGAアルゴリズムの適応であるSABAは$O(frac1T)$収束率を持ち、Polyak-Lojasciewicz仮定の下で線形収束を達成することを示した。
  論文  参考訳（メタデータ） (2022-01-31T18:17:25Z)
• HSVI fo zs-POSGs using Concavity, Convexity and Lipschitz Properties [8.80899367147235]
  いくつかのケースでは、最適値関数へのアプローチとして、POMDとDec-MDを評価します。 このアプローチは部分的に観測可能なゲーム(s-POSG)でも成功したが、一般には凹凸特性が知られているにもかかわらず失敗した。 我々はこれらの特性に基づいて、有界近似器と効率的な更新および選択演算子の原型凸性を導出する。
  論文  参考訳（メタデータ） (2021-10-25T13:38:21Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Logistic Q-Learning [87.00813469969167]
  MDPにおける最適制御の正規化線形プログラミング定式化から導いた新しい強化学習アルゴリズムを提案する。 提案アルゴリズムの主な特徴は,広範に使用されているベルマン誤差の代わりとして理論的に音声として機能する,政策評価のための凸損失関数である。
  論文  参考訳（メタデータ） (2020-10-21T17:14:31Z)

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

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