論文の概要: Epsilon-Nash Equilibria in History-Dependent SA-MDPs
- arxiv url: http://arxiv.org/abs/2609.18829v1
- Date: Wed, 16 Sep 2026 15:35:31 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-20 08:55:53.872977
- Title: Epsilon-Nash Equilibria in History-Dependent SA-MDPs
- Title（参考訳）: 歴史依存型SA-MDPにおけるEpsilon-Nash平衡
- Abstract要約: 状態適応決定プロセス(観察ゲームとしてのSA-MD)について検討した。
エージェントとエージェントの両方に戦略を適応させることで、履歴が結果を変えることができることを示す。
ベンチマークをテストして、より大きく、より現実的なベンチマークにスケールすることを示します。
- 参考スコア（独自算出の注目度）: 1.8758513283358527
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study state-adversarial Markov decision processes (SA-MDP) as a game of observation-space attacks: at each step, an agent selects an action from a received observation while an adversary$\unicode{x2014}$who knows the true state the agent is in$\unicode{x2014}$chooses a perturbed observation within a state-dependent proximity set. While existing work focuses on Markovian policies, we develop a solution concept and computational approach for SA-MDPs under history dependence. This is motivated by results showing that history dependence can materially change equilibrium outcomes and can force both the agent and the adversary to adapt their strategies. First, we prove the non-existence of universal (agnostic of the initial state distribution) history-dependent equilibrium policies. In response to this finding, our main result presents the first algorithmic route to computing $ε$-approximations of initial-state dependent equilibria. We do so by reducing SA-MDPs to a strategically equivalent constrained zero-sum one-sided partially observable stochastic game. We conclude by testing our algorithm on small analytically verifiable games and showing it scales to larger, more realistic benchmarks, including Atari Freeway rollouts with a 12-period ahead horizon.
- Abstract（参考訳）: 各ステップにおいて、エージェントは受信した観察からアクションを選択し、相手の$\unicode{x2014}$はエージェントが$\unicode{x2014}$chooses a perturbed observed in a state-dependent dependency set。
既存の研究はマルコフ政策に重点を置いているが、歴史依存下でのSA-MDPの解の概念と計算手法を開発する。
これは、歴史依存が均衡の結果を物質的に変化させ、エージェントと敵の両方に戦略を適応させ得ることを示す結果によって動機づけられる。
まず、普遍的(初期状態分布に依存しない)履歴依存均衡政策の非存在を証明する。
この発見に応えて、我々の主な結果は初期状態依存平衡の$ε$-approximationsを計算するための最初のアルゴリズム的経路を示す。
我々は、SA-MDPを戦略的に等価な制約付きゼロサム一辺部分可観測確率ゲームに還元する。
解析的に検証可能な小さなゲームでアルゴリズムをテストし、Atari Freewayのロールアウトを含むより大規模で現実的なベンチマークにスケールすることを示した。
関連論文リスト
- High-Probability Nash Regret for Decentralized Learning in Markov $α$-Potential Games: Episodic and Fully Online Asynchronous Algorithms with Applications to Markov Congestion Games [2.6397379133308214]
我々は,Markov$$-potentialゲームにおけるNash equilibria(NE)の分散学習について,帯域フィードバック下で検討した。
我々は,KL計画の自然政策勾配(NPG)アルゴリズムを,サンプリング中のフリーズポリシを備えたエピソード設定と,プレイヤーがタイムステップ毎に1つの実効的なコストサンプルを受信する完全オンライン設定の2つの設定で開発する。
論文 参考訳（メタデータ） (2026-09-14T03:06:51Z) - Evaluating AI Investment Strategies [0.0]
我々は、観測可能な入力と出力のみからブラックボックスのアルゴリズム決定を監査する問題について検討する。
厳密な条件下では、動的ポリシーの累積的表現は、コストベクトルとポリシーの決定の間の周期毎の共分散の和と等しい。
我々は、そのアイデンティティがコストと平均偏見のないマルコフポリシーの真下にあることを証明し、非定常および時変ケースに対する閉形式バイアス補正を導出し、割引された水平アナログを確立する。
論文 参考訳（メタデータ） (2026-06-07T19:16:50Z) - Independent Learning of Nash Equilibria in Partially Observable Markov Potential Games with Decoupled Dynamics [8.784438985280092]
部分的に観測可能なマルコフゲーム(POMG)におけるナッシュ均衡学習の研究
本研究では,各プレイヤーが自身の行動や観察のみを観察し,コミュニケーションを伴わない独立学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2026-05-07T14:56:56Z) - Score-Repellent Monte Carlo: Toward Efficient Non-Markovian Sampler with Constant Memory in General State Spaces [48.37754141688874]
本稿では,スコアと状態表現の次元である$Rd$のスコア評価の実行平均で履歴を要約するフレームワークを提案する。
この歴史は指数的なスコア傾きによって代理対象に変換され、歴史に基づく反発の大きさを制御する際の反発の強さを表す$$がインデックス付けされる。
連続目標モデルと離散エネルギーベースモデルの実験では、メモリ使用率を$O(d)$に抑えつつ、推定値の分散とモードカバレッジを改善した。
論文 参考訳（メタデータ） (2026-04-24T18:39:50Z) - Learning Markov Decision Processes under Fully Bandit Feedback [7.462282493793144]
強化学習における標準的な前提は、エージェントが関連する決定プロセス(MDP)において、訪れた状態-行動ペアをすべて観察するということである。
我々は,$widetildeO(sqrtT)$ regretのエピソードMDPに対して,最初の効率的な帯域幅学習アルゴリズムを提供する。
論文 参考訳（メタデータ） (2026-02-02T16:03:24Z) - Statistical Tractability of Off-policy Evaluation of History-dependent Policies in POMDPs [11.829110453985228]
大規模な観測空間を有する部分観測可能決定プロセス(POMDP)における外部政治評価(OPE)について検討する。
我々は,歴史に依存したポリシーのモデルフリーなOPEに対して,いくつかの設定で情報理論の難しさを証明した。
自然モデルに基づくマルコフアルゴリズムにより、いくつかの硬さを回避できることが示される。
論文 参考訳（メタデータ） (2025-03-03T03:29:05Z) - Model-free Methods for Event History Analysis and Efficient Adjustment (PhD Thesis) [55.2480439325792]
この論文は、モデルフリーの観点から統一された統計学への独立した貢献のシリーズである。
第1章では、機械学習から予測技術を活用する柔軟なメソッドを定式化するために、モデルフリーの視点をどのように利用できるか、詳しく説明している。
第2章では、あるプロセスの進化が他のプロセスに直接影響されるかどうかを記述した地域独立の概念を研究している。
論文 参考訳（メタデータ） (2025-02-11T19:24:09Z) - Sequential Manipulation Against Rank Aggregation: Theory and Algorithm [119.57122943187086]
脆弱なデータ収集プロセスに対するオンライン攻撃を活用します。
ゲーム理論の観点からは、対決シナリオは分布的に堅牢なゲームとして定式化される。
提案手法は,ランクアグリゲーション手法の結果を逐次的に操作する。
論文 参考訳（メタデータ） (2024-07-02T03:31:21Z) - Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
マルコフ決定過程における純粋探索問題について検討する。
エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
論文 参考訳（メタデータ） (2021-06-05T09:16:28Z) - Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games [78.65798135008419]
一般的なゲームでStackelberg平衡を効率的に学習する方法は、サンプルから非常にオープンなままです。
本稿では,2プレーヤターンベース汎用ゲームにおけるStackelberg平衡のサンプル効率学習に関する理論的研究を開始する。
論文 参考訳（メタデータ） (2021-02-23T05:11:07Z) - Off-policy Evaluation in Infinite-Horizon Reinforcement Learning with
Latent Confounders [62.54431888432302]
無限水平エルゴードマルコフ決定過程におけるOPE問題について考察する。
我々は、状態と行動の潜在変数モデルのみを考慮すれば、政策値が政治外のデータから特定できることを示す。
論文 参考訳（メタデータ） (2020-07-27T22:19:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。