論文の概要: Near-Optimal Pure Exploration in Matrix Games: A Generalization of
Stochastic Bandits & Dueling Bandits
- arxiv url: http://arxiv.org/abs/2310.16252v2
- Date: Mon, 27 Nov 2023 21:33:05 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-30 13:40:21.089472
- Title: Near-Optimal Pure Exploration in Matrix Games: A Generalization of
Stochastic Bandits & Dueling Bandits
- Title（参考訳）: マトリックスゲームにおける準最適純粋探索:確率帯域とデュエル帯域の一般化
- Authors: Arnab Maiti, Ross Boczar, Kevin Jamieson, Lillian J. Ratliff
- Abstract要約: ノイズを伴う2プレーヤゼロサム行列ゲームにおいて,純粋戦略ナッシュ均衡(PSNE)を同定する際のサンプル複雑性について検討した。
計算の複雑さは, 最大ログ係数に一致し, 最適に近いアルゴリズムが見つかる。
また,PSNEを同定する問題は,マルチアームバンディットやデュエルバンディットにおける純粋探索の問題も一般化する。
- 参考スコア（独自算出の注目度）: 21.49682459678413
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the sample complexity of identifying the pure strategy Nash
equilibrium (PSNE) in a two-player zero-sum matrix game with noise. Formally,
we are given a stochastic model where any learner can sample an entry $(i,j)$
of the input matrix $A\in[-1,1]^{n\times m}$ and observe $A_{i,j}+\eta$ where
$\eta$ is a zero-mean 1-sub-Gaussian noise. The aim of the learner is to
identify the PSNE of $A$, whenever it exists, with high probability while
taking as few samples as possible. Zhou et al. (2017) presents an
instance-dependent sample complexity lower bound that depends only on the
entries in the row and column in which the PSNE lies. We design a near-optimal
algorithm whose sample complexity matches the lower bound, up to log factors.
The problem of identifying the PSNE also generalizes the problem of pure
exploration in stochastic multi-armed bandits and dueling bandits, and our
result matches the optimal bounds, up to log factors, in both the settings.
- Abstract（参考訳）: ノイズのある2人のゼロサムマトリクスゲームにおいて,純粋戦略ナッシュ均衡(psne)を同定するサンプル複雑性について検討した。
形式的には、任意の学習者が入力行列 $A\in[-1,1]^{n\times m}$ のエントリ $(i,j)$ をサンプリングして、$A_{i,j}+\eta$ を観測できる確率モデルが与えられる。
学習者の目標は、a$のpsneをいつでも識別することであり、可能な限り少数のサンプルを採取しながら高い確率で識別することである。
Zhou et al. (2017) は、PSNE が成り立つ行と列のエントリにのみ依存する、インスタンス依存のサンプル複雑性の下界を示す。
サンプルの複雑さをログ係数まで下界にマッチさせる近似アルゴリズムを設計する。
psneを識別する問題は、確率的多腕バンディットとデュエルバンディットにおける純粋な探索の問題も一般化し、この結果は、両方の設定において、ログ係数まで、最適境界に一致する。
関連論文リスト
- Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity [14.396304498754688]
私たちは、$(lambda, beta)$-sparsityをダブした、空白という新しい概念を示します。
また、最適な$(lambda, beta)$-sparsity条件に適応する適応アルゴリズムを示す。
論文 参考訳（メタデータ） (2024-10-01T13:45:55Z) - Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。
我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
論文 参考訳（メタデータ） (2024-06-18T08:54:04Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - Information-Computation Tradeoffs for Learning Margin Halfspaces with
Random Classification Noise [50.64137465792738]
ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。
我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
論文 参考訳（メタデータ） (2023-06-28T16:33:39Z) - Sample Complexity Bounds for Learning High-dimensional Simplices in
Noisy Regimes [5.526935605535376]
ノイズの多いサンプルから単純さを学習するために、サンプルの複雑さが結びついているのがわかります。
我々は、$mathrmSNRgeOmegaleft(K1/2right)$ である限り、ノイズのないシステムのサンプルの複雑さは、ノイズのないケースのそれと同じ順序であることを示す。
論文 参考訳（メタデータ） (2022-09-09T23:35:25Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Optimal Online Generalized Linear Regression with Stochastic Noise and
Its Application to Heteroscedastic Bandits [88.6139446295537]
一般化線形モデルの設定におけるオンライン一般化線形回帰の問題について検討する。
ラベルノイズに対処するため、古典的追従正規化リーダ(FTRL)アルゴリズムを鋭く解析する。
本稿では,FTRLに基づくアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-02-28T08:25:26Z) - Breaking the Moments Condition Barrier: No-Regret Algorithm for Bandits
with Super Heavy-Tailed Payoffs [27.636407641546914]
実験的な中央値列の経験的平均を計算し,確率変数を推定する,新しい頑健な統計推定器を提案する。
非常に重みのある雑音であっても, 後悔の限界がほぼ最適であることを示す。
論文 参考訳（メタデータ） (2021-10-26T17:30:44Z) - Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal
Sample Complexity [67.02490430380415]
モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。
また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
論文 参考訳（メタデータ） (2020-07-15T03:25:24Z) - Explicit Best Arm Identification in Linear Bandits Using No-Regret
Learners [17.224805430291177]
線形パラメータ化マルチアームバンドにおけるベストアーム識別の問題について検討する。
そこで本研究では,この問題を解決するために,明示的に実装可能かつ証明可能な順序-最適サンプル-複雑度アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-13T05:00:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。