論文の概要: Minimax-Optimal Policy Regret in Partially Observable Markov Games

• arxiv url: http://arxiv.org/abs/2606.02363v1
• Date: Mon, 01 Jun 2026 15:11:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-02 21:34:32.377434
• Title: Minimax-Optimal Policy Regret in Partially Observable Markov Games
• Title（参考訳）: 部分観測可能なマルコフゲームにおけるミニマックス最適ポリシーレグレット
• Authors: Raman Arora,
• Abstract要約: 本研究では,部分的に観察可能な環境下での逐次的意思決定を,戦略的かつ適応的な相手に対して検討する。 固定問題パラメータに対して,エポックベースの楽観的最大値類似アルゴリズムが$tildeO(sqrtT)$ポリシー後悔を達成することを証明した。
• 参考スコア（独自算出の注目度）: 33.134190121767816
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study sequential decision-making in partially observable environments against strategic, adaptive opponents, modeled as partially observable Markov games (POMGs). The central challenge is to learn latent dynamics from partial observations while facing an adversary whose behavior depends on the learner's strategy, making standard regret notions inadequate. We prove that an epoch-based optimistic maximum-likelihood algorithm achieves $\tilde{O}(\sqrt{T})$ policy regret for fixed problem parameters, with explicit dependence on the horizon, adversary memory, confidence radius, and the aggregate Eluder dimension of the observable-operator class. The algorithm selects one policy per geometrically growing epoch using confidence sets built cumulatively from past data, which keeps the cost of comparing adversary responses across policies logarithmic in $T$. We also prove a lower bound matching the $\sqrt{T}$ and aggregate-Eluder-dimension dependence, up to problem-dependent and logarithmic factors. Finally, we extend the framework to horizon-adaptive guarantees and adversaries with geometric fading memory.
• Abstract（参考訳）: 我々は,部分的に観測可能な環境において,部分的に観測可能なマルコフゲーム (POMG) としてモデル化された,戦略的かつ適応的な相手に対して逐次意思決定を行う。 中心的な課題は、学習者の戦略に依存している相手に直面しながら、部分的な観察から潜伏ダイナミクスを学習することであり、標準的な後悔の概念は不十分である。 固定問題パラメータに対して,エポック型楽観的最大値類似アルゴリズムが$\tilde{O}(\sqrt{T})$ポリシー後悔を達成することを証明した。 このアルゴリズムは、過去のデータから累積的に構築された信頼セットを用いて、幾何学的に成長するエポック毎に1つのポリシーを選択する。 また、$\sqrt{T}$とアグリゲート・ユーラダー次元依存性を、問題依存および対数的因子に一致する低い有界性を証明する。 最後に,このフレームワークを,幾何学的暗視メモリを備えた水平適応型保証や敵に拡張する。

関連論文リスト

• Revisiting Weighted Strategy for Non-stationary Parametric Bandits and MDPs [56.246783503873225]
  本稿では,非定常パラメトリックバンディットの重み付け戦略を再考する。 本稿では,ウィンドウ/リスタートベースアルゴリズムと同様に,より単純な重みに基づくアルゴリズムを提案する。 我々のフレームワークは、他のパラメトリックバンディットの後悔の限界を改善するのに使える。
  論文  参考訳（メタデータ） (2026-01-03T04:50:21Z)
• Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback [61.49239204705301]
  本研究では,有限水平マルコフ決定過程(MDP)におけるオンライン学習について,包括的包括的包括的フィードバックモデルを用いて検討する。 本研究は, オンライン最短経路問題の近年の進展に触発された, 占領対策, 自己拘束技術, 新たな損失推定器の組合せに依拠する。
  論文  参考訳（メタデータ） (2025-10-20T02:28:08Z)
• Adversarial learning for nonparametric regression: Minimax rate and adaptive estimation [3.244945627960733]
  逆数$L_risks と $1 leq leq infty$ の最小収束率を確立し、極大最適性を達成する部分的局所推定器を提案する。 我々は、対数係数の中で、非対数クラスと対数クラスの広い範囲で最適な速度を達成することが示されるデータ駆動適応推定器を構築する。
  論文  参考訳（メタデータ） (2025-06-02T02:38:47Z)
• Near-Optimal Dynamic Regret for Adversarial Linear Mixture MDPs [63.47351876442425]
  本研究は,完全情報フィードバックの下で,相変わらずの相変わらずの線形混合MDPについて検討した。 本稿では,占領率に基づく手法と政策に基づく手法の利点を組み合わせた新しいアルゴリズムを提案する。 我々のアルゴリズムは$widetildemathcalO(d sqrtH3 K + sqrtHK(H + barP_K$)$ dynamic regret, ここで$d$は特徴次元である。
  論文  参考訳（メタデータ） (2024-11-05T13:55:52Z)
• Efficient and Sharp Off-Policy Evaluation in Robust Markov Decision Processes [44.974100402600165]
  意思決定プロセス(MDP)に対する最良パラメトリックかつ最悪の摂動の評価について検討する。 我々は、元のMDPからの遷移観測を用いて、それらが同一または異なるポリシーの下で生成されるかのどちらかを判断する。 我々の推定器はウォルドの信頼区間を用いた統計的推測も行う。
  論文  参考訳（メタデータ） (2024-03-29T18:11:49Z)
• Local and adaptive mirror descents in extensive-form games [37.04094644847904]
  我々は,ゼロサム不完全な情報ゲーム (IIG) において,軌道フィードバックを用いて$epsilon$-Optimal戦略を学習する方法を研究する。 我々は、プレイヤーが時間とともにポリシーを更新する固定サンプリングアプローチを検討するが、与えられた固定サンプリングポリシーによって観察される。 このアプローチは高い確率で$tildemathcalO(T-1/2)$の収束率を保証し、ゲームパラメータにほぼ最適に依存することを示す。
  論文  参考訳（メタデータ） (2023-09-01T09:20:49Z)
• Autoregressive Bandits [58.46584210388307]
  本稿では,オンライン学習環境であるAutoregressive Banditsを提案する。 報酬プロセスの軽微な仮定の下では、最適ポリシーを便利に計算できることが示される。 次に、新しい楽観的後悔最小化アルゴリズム、すなわちAutoRegressive Upper Confidence Bound (AR-UCB)を考案し、$widetildemathcalO left( frac(k+1)3/2sqrtnT (1-G)のサブ線形後悔を被る。
  論文  参考訳（メタデータ） (2022-12-12T21:37:36Z)
• Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-Regret Learning in Markov Games [95.10091348976779]
  我々はマルコフゲームにおいて、非定常的でおそらく敵対的な相手と遊べる単一のエージェントを制御する分散ポリシー学習について研究する。 我々は、新しいアルゴリズム、アンダーラインデ集中型アンダーラインハイプラインRpolicy munderlineIrror deunderlineScent (DORIS)を提案する。 DORISは、一般的な関数近似の文脈で$sqrtK$-regretを達成する。
  論文  参考訳（メタデータ） (2022-06-03T14:18:05Z)
• Making Non-Stochastic Control (Almost) as Easy as Stochastic [27.736345095024276]
  より一般的な非確率的制御モデルにおいても、同じ後悔率が達成可能であることを示す。 学習者にとってダイナミクスが不明な場合に、最適な$widetildemathcalO(sqrtT)$ regretを得る。
  論文  参考訳（メタデータ） (2020-06-10T16:00:14Z)

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

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