論文の概要: Robust PAC Learning of Concurrent Stochastic Games

• arxiv url: http://arxiv.org/abs/2609.04189v1
• Date: Thu, 03 Sep 2026 17:58:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-04 18:28:39.199143
• Title: Robust PAC Learning of Concurrent Stochastic Games
• Title（参考訳）: 同時確率ゲームにおけるロバストPAC学習
• Abstract要約: 本稿では,移行不確実性を伴う汎用並列ゲーム(CSG)のための,最初の確率近似学習フレームワークを提案する。 我々のアルゴリズムは、遷移カーネル上のデータ駆動の$L1$信頼セットを維持し、ロバストなCSGを解き、社会的に最適な$varepsilon$-NEを計算する。 重要なことに、平衡の存在に関する原則的推論を可能にするナッシュマージンの特徴付けを導入する。
• 参考スコア（独自算出の注目度）: 3.2964666213105587
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce the first Probably Approximately Correct (PAC) learning framework for general-sum concurrent stochastic games (CSGs) with transition uncertainty, while addressing the challenge of Nash equilibrium (NE) existence. Our algorithm maintains data-driven $L^1$ confidence sets over transition kernels and solves a robust CSG to compute a social-welfare optimal $\varepsilon$-NE, using a robust MDP-based exploration mechanism to drive joint state-action coverage. Crucially, we introduce a Nash margin characterisation that enables principled reasoning about equilibrium existence: the framework either returns an $\varepsilon$-approximate NE whose social-welfare value is $\varepsilon$-close to optimal, or provides a sound certificate that no exact NE exists. Under a minimum reachability condition $p_{\mathrm{reach}}>0$ over relevant state-action pairs, the algorithm terminates after a polynomial number of trajectory samples, with sample complexity $\widetilde{O}\left( {R_{\max}^2 H^4 |S|^2 |A| / (p_{\mathrm{reach}} \varepsilon^2)} \right)$. Empirical results on benchmark CSGs demonstrate near-optimal performance, correct handling of equilibrium (non-)existence, and sample complexity consistent with theory.
• Abstract（参考訳）: 本稿では,Nash equilibrium (NE) の存在の課題に対処しつつ,遷移不確実性を伴う汎用並列確率ゲーム(CSG)のための最初の確率近似学習フレームワークを提案する。 提案アルゴリズムは,データ駆動型$L^1$信頼セットをトランジションカーネル上で維持し,ロバストなCSGを用いてソーシャルウェルフェア最適$\varepsilon$-NEを計算する。 重要な点として、平衡存在についての原則的推論を可能にするナッシュ・マージンの特徴付けを導入する。このフレームワークは、社会的ウェルフェア値が$\varepsilon$-close である$\varepsilon$-approximate NEを返すか、正確なNEが存在しないサウンド証明書を提供する。 最小到達性条件 $p_{\mathrm{reach}}>0$ は関連する状態-作用対に対して、このアルゴリズムは、サンプル複雑性 $\widetilde{O}\left( {R_{\max}^2 H^4 |S|^2 |A| / (p_{\mathrm{reach}} \varepsilon^2)} \right)$ の多項式数で終了する。 ベンチマークCSGの実験的結果は、ほぼ最適性能、平衡(非存在)の正しいハンドリング、および理論と整合したサンプル複雑性を示す。

関連論文リスト

• An Argmax Principle for Sum-of-Squares Relaxations on the Sphere [42.540924632302925]
  単位球面上の最適化問題の総和緩和を解析するためのargmax原理を開発する。 私たちの指導原則は、最大値が丸みを帯びた候補であることです。
  論文  参考訳（メタデータ） (2026-08-03T17:58:00Z)
• A Near-optimal SQ Lower Bound for Smoothed Agnostic Learning of Boolean Halfspaces [0.0]
  半空間の平滑化学習の複雑性について,KM25のモデルにおける一様限界の下で検討した。
  論文  参考訳（メタデータ） (2026-05-04T08:53:40Z)
• Beyond Isotonization: Scalable Non-Crossing Quantile Estimation via Neural Networks for Student Growth Percentiles [0.0]
  学生成長パーセンタイル(SGP)は、アメリカ合衆国の国家評価システムで広く採用されており、独立した量子レグレッションとポストホック補正が採用されている。 我々は、このアプローチが基本的な方法論上の矛盾を含んでいることを実証する: 独立に見積もられた、潜在的に交差する量子化の間には、単調性が必要である。 ニューラルネットワークを用いたマルチクエンタイル回帰(NNQR)を実用的な代替手段として提案する。
  論文  参考訳（メタデータ） (2025-10-25T19:39:07Z)
• Can SGD Handle Heavy-Tailed Noise? [6.111519084375339]
  Gradient Descent (SGD) は大規模最適化のための機械学習プロジェクトであるが、重尾雑音下での理論的挙動は理解されていない。 このような悪条件下でSGDが確実に成功できるかどうかを精査する。
  論文  参考訳（メタデータ） (2025-08-06T20:09:41Z)
• Accelerating Nash Learning from Human Feedback via Mirror Prox [36.04055906691423]
  オンラインNLHFアルゴリズムであるNash Mirror Prox(mathtNash-MP$)を導入する。 我々の理論的解析により、ナッシュ-MPは、$beta$-regularized Nash平衡に対して、最終点の線形収束を示すことが証明された。 また,Nash-MPは,利用可能性ギャップと対数確率の半ノルムの均一性に対して,最終等級の線形収束を示すことを示した。
  論文  参考訳（メタデータ） (2025-05-26T09:17:32Z)
• Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under $(L_0, L_1)$-Smoothness [74.18546828528298]
  SignSGD with Majority Votingは,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappaka ppakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa -1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappappapa-1right,Kappaを用いて,複雑性の全範囲で堅牢に動作することを示す。
  論文  参考訳（メタデータ） (2025-02-11T19:54:11Z)
• Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits [49.96531901205305]
  我々は$f$-divergence-regularized offline policy learningを分析する。 逆Kullback-Leibler (KL) の発散に対して、単極集中性の下での最初の$tildeO(epsilon-1)$サンプル複雑性を与える。 これらの結果は,$f$-divergence-regularized policy learningの包括的理解に向けて大きな一歩を踏み出したものと考えられる。
  論文  参考訳（メタデータ） (2025-02-09T22:14:45Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。 本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
  論文  参考訳（メタデータ） (2024-04-29T15:04:07Z)
• Achieving the Asymptotically Optimal Sample Complexity of Offline Reinforcement Learning: A DRO-Based Approach [36.88301225561535]
  オフライン強化学習は、アクティブな探索なしに、事前に収集されたデータセットから学習することを目的としている。 既存のアプローチでは、不確実性に対する悲観的なスタンスを採用し、探索されていない状態-作用対の報酬を、保守的に値関数を推定する。 分散ロバスト最適化(DRO)に基づくアプローチはこれらの課題にも対処でき、漸近的に最小限の最適化であることを示す。
  論文  参考訳（メタデータ） (2023-05-22T17:50:18Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。 我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
  論文  参考訳（メタデータ） (2022-12-01T15:57:58Z)
• DASHA: Distributed Nonconvex Optimization with Communication Compression, Optimal Oracle Complexity, and No Client Synchronization [77.34726150561087]
  我々は,分散最適化問題に対する新しい手法であるDASHAを開発し,解析する。 MARINAとは異なり、新しいDASHAとDASHA-MVRは圧縮ベクターのみを送信し、ノードを同期しないため、学習をより実用的なものにしている。
  論文  参考訳（メタデータ） (2022-02-02T20:10:40Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。 Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
  論文  参考訳（メタデータ） (2020-06-04T17:51:00Z)

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

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