論文の概要: Generalized Bandit Regret Minimizer Framework in Imperfect Information
Extensive-Form Game
- arxiv url: http://arxiv.org/abs/2203.05920v4
- Date: Fri, 18 Aug 2023 14:16:12 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-22 01:48:06.436087
- Title: Generalized Bandit Regret Minimizer Framework in Imperfect Information
Extensive-Form Game
- Title（参考訳）: 不完全な情報集約型ゲームにおける一般化帯域制限最小化フレームワーク
- Authors: Linjian Meng, Yang Gao
- Abstract要約: 我々は,IIEGのダイナミクスを知らない対話型バンディットフィードバック設定の問題点を考察する。
NEを学習するには、後悔最小化器は、全フィードバック損失勾配$ellt$ by $v(zt)$を推定し、後悔を最小化する。
モデルフリーであり、$O(sqrtX B/T+sqrtY C/T)$から$O()$までの最良の収束率を大幅に向上させる。
- 参考スコア（独自算出の注目度）: 9.933208900617174
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Regret minimization methods are a powerful tool for learning approximate Nash
equilibrium (NE) in two-player zero-sum imperfect information extensive-form
games (IIEGs). We consider the problem in the interactive bandit-feedback
setting where we don't know the dynamics of the IIEG. In general, only the
interactive trajectory and the reached terminal node value $v(z^t)$ are
revealed. To learn NE, the regret minimizer is required to estimate the
full-feedback loss gradient $\ell^t$ by $v(z^t)$ and minimize the regret. In
this paper, we propose a generalized framework for this learning setting. It
presents a theoretical framework for the design and the modular analysis of the
bandit regret minimization methods. We demonstrate that the most recent bandit
regret minimization methods can be analyzed as a particular case of our
framework. Following this framework, we describe a novel method SIX-OMD to
learn approximate NE. It is model-free and extremely improves the best existing
convergence rate from the order of $O(\sqrt{X B/T}+\sqrt{Y C/T})$ to $O(\sqrt{
M_{\mathcal{X}}/T} +\sqrt{ M_{\mathcal{Y}}/T})$. Moreover, SIX-OMD is
computationally efficient as it needs to perform the current strategy and
average strategy updates only along the sampled trajectory.
- Abstract（参考訳）: レグレット最小化法は、2プレイヤーゼロサム不完全情報広義ゲーム(IIEG)における近似ナッシュ均衡(NE)を学習するための強力なツールである。
我々は,IIEGのダイナミクスを知らない対話型バンディットフィードバック設定における問題を考察する。
一般に、対話的軌道と到達した終端ノード値$v(z^t)$のみを明らかにする。
neを学ぶには、完全フィードバック損失勾配 $\ell^t$ by $v(z^t)$ を推定し、後悔を最小限に抑える必要がある。
本稿では,この学習設定のための一般化フレームワークを提案する。
これは、バンディット後悔最小化法の設計とモジュラー解析のための理論的枠組みを示す。
我々は、最新のbandit regretの最小化手法を、フレームワークの特定のケースとして分析できることを実証する。
この枠組みに従って、近似NEを学習するための新しいSIX-OMD法について述べる。
モデルフリーであり、$O(\sqrt{X B/T}+\sqrt{Y C/T})$から$O(\sqrt{M_{\mathcal{X}}/T} +\sqrt{M_{\mathcal{Y}}/T})$までの最良の収束率を大幅に改善する。
さらに、SIX-OMDは、サンプリングされた軌道に沿ってのみ現在の戦略と平均戦略更新を実行する必要があるため、計算的に効率的である。
関連論文リスト
- Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。
最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
論文 参考訳（メタデータ） (2023-07-25T15:42:11Z) - Borda Regret Minimization for Generalized Linear Dueling Bandits [65.09919504862496]
本稿では,ボルダスコアが最も高い項目を識別することを目的とした,デュエルバンディットに対するボルダ後悔最小化問題について検討する。
本稿では,多くの既存モデルをカバーする一般化線形デュエルバンドモデルのリッチクラスを提案する。
我々のアルゴリズムは$tildeO(d2/3 T2/3)$ regretを達成し、これも最適である。
論文 参考訳（メタデータ） (2023-03-15T17:59:27Z) - Revisiting Weighted Strategy for Non-stationary Parametric Bandits [82.1942459195896]
本稿では,非定常パラメトリックバンディットの重み付け戦略を再考する。
より単純な重みに基づくアルゴリズムを生成する改良された分析フレームワークを提案する。
我々の新しいフレームワークは、他のパラメトリックバンディットの後悔の限界を改善するのに使える。
論文 参考訳（メタデータ） (2023-03-05T15:11:14Z) - Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaR [58.40575099910538]
本研究は,リスク許容度が$tau$のCVaR(Conditional Value at Risk)の目的に着目し,リスクに敏感な強化学習(RL)について検討する。
ミニマックスCVaRの後悔率は$Omega(sqrttau-1AK)$で、$A$はアクションの数、$K$はエピソード数である。
我々は,このアルゴリズムが連続性仮定の下で$widetilde O(tau-1sqrtSAK)$の最適後悔を達成し,一般に近似することを示す。
論文 参考訳（メタデータ） (2023-02-07T02:22:31Z) - Horizon-Free and Variance-Dependent Reinforcement Learning for Latent
Markov Decision Processes [62.90204655228324]
我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。
我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
論文 参考訳（メタデータ） (2022-10-20T21:32:01Z) - Expected Worst Case Regret via Stochastic Sequential Covering [14.834625066344582]
我々は、既知のミニマックス後悔を一般化し包含する、予想される最悪のミニマックス後悔の概念を導入する。
そのようなミニマックスの後悔に対して、我々は上大域シーケンシャル被覆という新しい概念を通じて厳密な境界を確立する。
対数損失と一般に混合可能な損失に対する最小限の後悔に対する厳密な境界を確立することで,本手法の有効性を実証する。
論文 参考訳（メタデータ） (2022-09-09T17:31:46Z) - The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret
and Policy Switches [84.54669549718075]
漸進的強化学習(RL)における後悔の最小化問題について検討する。
一般関数クラスと一般モデルクラスで学ぶことに集中する。
対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
論文 参考訳（メタデータ） (2022-03-03T02:55:55Z) - Minimax Regret for Stochastic Shortest Path with Adversarial Costs and
Known Transition [37.6975819766632]
我々は、敵対コストと既知の移行で最短経路問題を研究します。
ミニマックスの後悔は,全情報設定と盗聴フィードバック設定に対して$widetildeO(sqrtDTstar K)$および$widetildeO(sqrtDTstar SA K)$であることを示す。
論文 参考訳（メタデータ） (2020-12-07T20:55:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。