論文の概要: HSVI fo zs-POSGs using Concavity, Convexity and Lipschitz Properties

• arxiv url: http://arxiv.org/abs/2110.14529v1
• Date: Mon, 25 Oct 2021 13:38:21 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-28 14:01:24.934333
• Title: HSVI fo zs-POSGs using Concavity, Convexity and Lipschitz Properties
• Title（参考訳）: 凹凸, 凸凸およびリプシッツ特性を用いたHSVIfo zs-POSG
• Authors: Aur\'elien Delage, Olivier Buffet, Jilles Dibangoye
• Abstract要約: いくつかのケースでは、最適値関数へのアプローチとして、POMDとDec-MDを評価します。 このアプローチは部分的に観測可能なゲーム(s-POSG)でも成功したが、一般には凹凸特性が知られているにもかかわらず失敗した。 我々はこれらの特性に基づいて、有界近似器と効率的な更新および選択演算子の原型凸性を導出する。
• 参考スコア（独自算出の注目度）: 8.80899367147235
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Dynamic programming and heuristic search are at the core of state-of-the-art solvers for sequential decision-making problems. In partially observable or collaborative settings (\eg, POMDPs and Dec-POMDPs), this requires 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 failed in the general case despite known concavity and convexity properties, which only led to heuristic algorithms with poor convergence guarantees. We overcome this issue, leveraging on these properties to derive bounding approximators and efficient update and selection operators, before deriving a prototypical solver inspired by HSVI that provably converges to an $\epsilon$-optimal solution in finite time, and which we empirically evaluate. This opens the door to a novel family of promising approaches complementing those relying on linear programming or iterative methods.
• Abstract（参考訳）: 動的プログラミングとヒューリスティック探索は、逐次的意思決定問題の最先端解法の中核にある。 部分的に観測可能あるいは協調的な設定(\eg, POMDPs, Dec-POMDPs)では、最適な値関数のバウンディング(凸)近似と同様に、完全に観測可能な問題を誘導する適切な統計学を導入する必要がある。 このアプローチは、2-player zero-sum partial observable stochastic games (zs-posg) のいくつかのサブクラスでも成功したが、一般的なケースでは、既知の凸性と凸性にもかかわらず失敗した。 我々は,これらの性質を利用して境界近似器と効率的な更新・選択演算子を導出し,hsvi に触発された原型的解法を導出し,有限時間で $\epsilon$-optimal 解に収束し,経験的に評価する。 これは、線形プログラミングや反復的メソッドに依存する人たちを補完する、有望なアプローチの新たなファミリーへの扉を開く。

関連論文リスト

• $ε$-Optimally Solving Zero-Sum POSGs [4.424170214926035]
  ゼロサム部分観測可能なゲームの解法は、元のゲームを「占有マルコフゲーム」と呼ばれる新しいゲームに埋め込む。 本稿では、この制限を克服するために、最適値関数の新たな一様連続性特性を利用する。
  論文  参考訳（メタデータ） (2024-05-29T08:34:01Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。 これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
  論文  参考訳（メタデータ） (2023-02-02T10:37:23Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。 提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-12-19T14:48:54Z)
• HSVI can solve zero-sum Partially Observable Stochastic Games [7.293053431456775]
  2-player 0-sum不完全なゲームを解くための最先端の手法は、線形プログラミングや動的後悔の最小化に依存している。 本稿では,線形プログラミングや反復的手法に依存した手法を補完する,有望なアプローチの新たなファミリーを提案する。
  論文  参考訳（メタデータ） (2022-10-26T11:41:57Z)
• Efficient semidefinite bounds for multi-label discrete graphical models [6.226454551201676]
  このようなモデルにおける主要なクエリの1つは、Posteri(MAP)ネットワークのコストに関するSDPWCSP関数を特定することである。 従来の二重化制約手法と,行ごとの更新に基づく専用SDP/Monteiroスタイルの手法を検討する。
  論文  参考訳（メタデータ） (2021-11-24T13:38:34Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57: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)
• Linear-Time Probabilistic Solutions of Boundary Value Problems [27.70274403550477]
  我々は、Gauss--Markov を前もって導入し、特に BVP に調整する。 これにより、線形時間で解の後方分布を計算し、よく確立された非確率的手法に匹敵する品質とコストで計算することができる。
  論文  参考訳（メタデータ） (2021-06-14T21:19:17Z)
• Near-Optimal High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 既存の非滑らか凸最適化法は、負のパワーまたは対数的な信頼度に依存する境界の複雑さを持つ。 クリッピングを用いた2つの勾配法に対して, 新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
  無限水平マルコフ決定過程(MDP)における最適政策学習の問題を考える。 リプシッツ連続関数を用いた凸プログラミング問題に対してミラー・ディクセントの変種が提案されている。 このアルゴリズムを一般の場合において解析し,提案手法の動作中に誤差を蓄積しない収束率の推定値を得る。
  論文  参考訳（メタデータ） (2021-02-27T19:28:39Z)
• Provably Convergent Working Set Algorithm for Non-Convex Regularized Regression [0.0]
  本稿では、収束保証付き非正則正規化器のためのワーキングセットアルゴリズムを提案する。 その結果,ブロックコーディネートや勾配ソルバの完全解法と比較して高い利得を示した。
  論文  参考訳（メタデータ） (2020-06-24T07:40:31Z)

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

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