論文の概要: PAC Learning in Turn-Based Stochastic Games with Reachability Objectives: A Decentralized Private Approach via Expected Conditional Distance
- arxiv url: http://arxiv.org/abs/2607.14877v1
- Date: Thu, 16 Jul 2026 11:48:58 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-17 17:01:33.086087
- Title: PAC Learning in Turn-Based Stochastic Games with Reachability Objectives: A Decentralized Private Approach via Expected Conditional Distance
- Title（参考訳）: リーチ可能性を考慮したターンベース確率ゲームにおけるPAC学習:期待された条件距離による分散型私的アプローチ
- Abstract要約: 到達可能性(Reachability)は最も基本的な論理的目的であるが、強化学習環境では学習が難しいことが知られている。
ターンベースゲーム(TBSG)では、2人の敵プレイヤーが有限状態空間上で相互作用する。
この研究は、TBSGの分散的およびプライベートな情報学習において、リーチビリティの目標を持つ最初の肯定的な結果である。
- 参考スコア（独自算出の注目度）: 7.5294643377975765
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Reachability is the most fundamental logical objective, yet it is notoriously difficult to learn in reinforcement learning settings: even for Markov decision processes, PAC learning of reachability is impossible without additional assumptions. This difficulty also holds in turn-based stochastic games (TBSGs), where two adversarial players interact on a finite state space. In this work, we consider turn-based stochastic games with reachability objectives. For such settings, adversarial learning, in which players are adversarial even in the learning phase, is impossible. Therefore, the goal is to consider learning, in which both players learn the unknown model together. In this spirit, previous literature on PAC learning in TBSGs considers (a)~public information shared by both players; and (b)~centralized learning, which means that players share the same learning algorithm. In this work, our contribution is two-fold. First, we relax these strong assumptions and ensure learning: (i)~with private information not shared with the other player; and (ii)~decentralized learning where the players do not share the same learning algorithm. To the best of our knowledge, this work is the first positive result for decentralized and private information learning of TBSGs with reachability objectives. Second, we introduce a game-theoretic generalization of the Expected Conditional Distance (ECD) parameter, which measures the expected length of reaching the target set. We establish a polynomial-sample complexity bound with respect to the number of states, actions, ECD parameter, and inverses of error tolerance and failure probability.
- Abstract（参考訳）: 到達可能性(Reachability)は最も基本的な論理的目的であるが、強化学習環境では学習が困難であることが知られている:マルコフの決定プロセスにおいて、PACによる到達可能性の学習は追加の仮定なしでは不可能である。
この難しさは、ターンベースの確率ゲーム(TBSGs)でもあり、2人の敵プレイヤーが有限状態空間上で相互作用する。
本研究では,リーチビリティを目標としたターン型確率ゲームについて考察する。
このような設定では、学習フェーズにおいてもプレイヤーが対戦する敵学習は不可能である。
したがって、両方のプレイヤーが未知のモデルを一緒に学習する学習を考えることが目的である。
TBSGにおけるPAC学習に関する過去の文献
(a)~両プレーヤーが共有する公開情報、及び
すなわち、プレイヤーは同じ学習アルゴリズムを共有していることを意味する。
この作業では、私たちの貢献は2倍になります。
まず、これらの強い仮定を緩和し、学習を確実にする。
(i)~他のプレーヤと共有されていないプライベート情報、及び
(ii) - プレイヤーが同じ学習アルゴリズムを共有しない分散学習。
我々の知る限りでは、この研究はTBSGの分散的およびプライベートな情報学習において、リーチビリティの目標を持つ最初の肯定的な結果である。
第2に,期待条件距離(ECD)パラメータのゲーム理論的一般化を導入する。
本研究では, 状態数, 動作数, ECDパラメータ, エラー耐性および故障確率の逆数に関して, 多項式サンプルの複雑性を確立する。
関連論文リスト
- Learning Conditional Averages [52.361762722359366]
本稿では,PACフレームワークにおける条件平均学習の問題を紹介する。
ターゲットのコンセプトそのものを学ぶのではなく、各インスタンスの平均ラベルをその周辺で予測することが目標だ。
より一般的には、PAC学習をいくつかのドメインで発生する学習タスクをキャプチャする設定に拡張する。
論文 参考訳（メタデータ） (2026-02-12T13:20:29Z) - Confounding Robust Deep Reinforcement Learning: A Causal Approach [53.63254824501714]
本稿では,DQN(Deep Q-Network)に基づいて,観測データのバイアスの解消に頑健な新しい強化学習アルゴリズムを提案する。
提案手法は,12個のAtariゲームに対して適用され,観察された動作および目標ポリシーへの入力がミスマッチおよび観測されていない共同創設者が存在するすべてのゲームにおいて,標準DQNを一貫して支配していることがわかった。
論文 参考訳（メタデータ） (2025-10-24T02:58:01Z) - The Dimension of Self-Directed Learning [18.701165230774325]
本研究では,2進環境と多進環境の両方において,自己指向型学習の複雑さについて検討する。
我々は,任意の概念クラスに対して,自己指向型学習ミスバウンドを正確に特徴付ける次元である$SDdim$を開発する。
自己指向型学習モデルとオフラインシーケンス学習モデルを中心に,学習可能性のギャップをいくつも示している。
論文 参考訳（メタデータ） (2024-02-20T21:59:41Z) - Neural Population Learning beyond Symmetric Zero-sum Games [52.20454809055356]
我々はNuPL-JPSROという,スキルの伝達学習の恩恵を受けるニューラル集団学習アルゴリズムを導入し,ゲームの粗相関(CCE)に収束する。
本研究は, 均衡収束型集団学習を大規模かつ汎用的に実施可能であることを示す。
論文 参考訳（メタデータ） (2024-01-10T12:56:24Z) - Accelerate Multi-Agent Reinforcement Learning in Zero-Sum Games with
Subgame Curriculum Learning [65.36326734799587]
ゼロサムゲームのための新しいサブゲームカリキュラム学習フレームワークを提案する。
エージェントを以前に訪れた状態にリセットすることで、適応的な初期状態分布を採用する。
我々は,2乗距離をNE値に近似するサブゲーム選択指標を導出する。
論文 参考訳（メタデータ） (2023-10-07T13:09:37Z) - Decentralized model-free reinforcement learning in stochastic games with
average-reward objective [1.9852463786440127]
本アルゴリズムは,次数$T3/4$のサブ線形高確率後悔と次数$T2/3$のサブ線形高確率後悔を実現する。
本アルゴリズムは,従来の手法に比べて計算量が少なく,メモリスペースも少ない。
論文 参考訳（メタデータ） (2023-01-13T15:59:53Z) - Independent and Decentralized Learning in Markov Potential Games [3.549868541921029]
マルチエージェント強化学習ダイナミクスについて検討し、無限水平割引マルコフポテンシャルゲームにおけるその挙動を解析する。
我々は、プレイヤーがゲームパラメータを知らない、コミュニケーションやコーディネートができない、独立的で分散的な設定に焦点を当てる。
論文 参考訳（メタデータ） (2022-05-29T07:39:09Z) - Impartial Games: A Challenge for Reinforcement Learning [0.0]
我々は,AlphaZeroスタイルの強化学習アルゴリズムが,公平なゲームに適用した場合,重要かつ基本的な課題に直面することを示す。
その結果,AlphaZeroスタイルのエージェントはチャンピオンレベルのプレーを達成できるが,ボードサイズが大きくなるにつれて学習の進歩は著しく低下することがわかった。
これらの結果は、AlphaZeroスタイルのアルゴリズムの攻撃に対する脆弱性に関するより広範な懸念と一致している。
論文 参考訳（メタデータ） (2022-05-25T14:02:02Z) - Learning Equilibria in Matching Markets from Bandit Feedback [139.29934476625488]
不確実性の下で安定した市場成果を学習するためのフレームワークとアルゴリズムを開発する。
私たちの研究は、大規模なデータ駆動の市場において、いつ、どのように安定したマッチングが生じるかを明らかにするための第一歩を踏み出します。
論文 参考訳（メタデータ） (2021-08-19T17:59:28Z) - Decentralized Q-Learning in Zero-sum Markov Games [33.81574774144886]
ゼロサムマルコフゲームにおけるマルチエージェント強化学習(MARL)について検討した。
我々は、合理的かつ収束的な、根本的に非結合なQ-ラーニングダイナミクスを初めて開発する。
この分散環境における鍵となる課題は、エージェントの観点から学習環境の非定常性である。
論文 参考訳（メタデータ） (2021-06-04T22:42:56Z) - Independent Policy Gradient Methods for Competitive Reinforcement
Learning [62.91197073795261]
2つのエージェントによる競争強化学習環境における独立学習アルゴリズムに対するグローバル・非漸近収束保証を得る。
本研究は,両選手がタンデムで政策勾配法を実行すると,学習率を2回ルールに従えば,その政策はゲームの最小均衡に収束することを示す。
論文 参考訳（メタデータ） (2021-01-11T23:20:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。