論文の概要: Variance-Dependent Best Arm Identification
- arxiv url: http://arxiv.org/abs/2106.10417v3
- Date: Sat, 27 May 2023 07:30:09 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-31 04:46:25.215546
- Title: Variance-Dependent Best Arm Identification
- Title（参考訳）: 可変依存型ベストアーム識別
- Authors: Pinyan Lu, Chao Tao, Xiaojin Zhang
- Abstract要約: マルチアームバンディットゲームにおける最適な腕を特定する問題について検討する。
武器の報酬のギャップと分散を探索する適応アルゴリズムを提案する。
このアルゴリズムは2つの対数項に最適であることを示す。
- 参考スコア（独自算出の注目度）: 12.058652922228918
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the problem of identifying the best arm in a stochastic multi-armed
bandit game. Given a set of $n$ arms indexed from $1$ to $n$, each arm $i$ is
associated with an unknown reward distribution supported on $[0,1]$ with mean
$\theta_i$ and variance $\sigma_i^2$. Assume $\theta_1 > \theta_2 \geq \cdots
\geq\theta_n$. We propose an adaptive algorithm which explores the gaps and
variances of the rewards of the arms and makes future decisions based on the
gathered information using a novel approach called \textit{grouped median
elimination}. The proposed algorithm guarantees to output the best arm with
probability $(1-\delta)$ and uses at most $O \left(\sum_{i = 1}^n
\left(\frac{\sigma_i^2}{\Delta_i^2} + \frac{1}{\Delta_i}\right)(\ln \delta^{-1}
+ \ln \ln \Delta_i^{-1})\right)$ samples, where $\Delta_i$ ($i \geq 2$) denotes
the reward gap between arm $i$ and the best arm and we define $\Delta_1 =
\Delta_2$. This achieves a significant advantage over the variance-independent
algorithms in some favorable scenarios and is the first result that removes the
extra $\ln n$ factor on the best arm compared with the state-of-the-art. We
further show that $\Omega \left( \sum_{i = 1}^n \left(
\frac{\sigma_i^2}{\Delta_i^2} + \frac{1}{\Delta_i} \right) \ln \delta^{-1}
\right)$ samples are necessary for an algorithm to achieve the same goal,
thereby illustrating that our algorithm is optimal up to doubly logarithmic
terms.
- Abstract（参考訳）: 確率的マルチアームバンディットゲームにおいて,最適な腕を特定する問題について検討する。
一組の$n$ arms が$$から$n$ にインデックスされた場合、各 arm $i$ は$[0,1]$ と平均$\theta_i$ と分散 $\sigma_i^2$ でサポートされている未知の報酬分布に関連付けられる。
\theta_1 > \theta_2 \geq \cdots \geq\theta_n$ と仮定する。
本稿では,武器の報酬のギャップと分散を探索する適応アルゴリズムを提案し,新しいアプローチであるtextit{grouped central elimination} を用いて,収集した情報に基づいて今後の決定を行う。
提案アルゴリズムは、確率$(1-\delta)$でベストアームを出力することを保証し、最大$O \left(\sum_{i = 1}^n \left(\frac{\sigma_i^2}{\Delta_i^2} + \frac{1}{\Delta_i}\right)(\ln \delta^{-1} + \ln \ln \Delta_i^{-1})\right)$サンプルを使用する。
これはいくつかの好都合なシナリオにおいて分散非依存アルゴリズムよりも大きな利点を達成し、最高の腕に余分な$\ln n$因子を取り除く最初の結果である。
さらに、$\Omega \left( \sum_{i = 1}^n \left( \frac{\sigma_i^2}{\Delta_i^2} + \frac{1}{\Delta_i} \right) \ln \delta^{-1} \right)$サンプルは同じ目的を達成するためにアルゴリズムに必要であることを示す。
関連論文リスト
- Optimal Streaming Algorithms for Multi-Armed Bandits [28.579280943038555]
ストリーミングBAI問題では,最大報酬が1-delta$の確率でアームを識別することが目的である。
我々は,O(log Delta-1)$パス内で,ほぼインスタンス依存の最適なサンプル複雑性を実現するシングルアームメモリアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-10-23T12:54:04Z) - A/B Testing and Best-arm Identification for Linear Bandits with
Robustness to Non-stationarity [28.068960555415014]
非定常環境下での線形包帯の固定予算ベストアーム識別問題について検討する。
アルゴリズムは、可能な限り高い確率で最適な腕 $x* := argmax_xinmathcalXxtopsum_t=1Ttheta_t$ を正しく識別することを目的としている。
論文 参考訳（メタデータ） (2023-07-27T19:03:36Z) - Asymptotically Optimal Pure Exploration for Infinite-Armed Bandits [4.811176167998627]
我々は、未知の分布から生じる無限に多くのバンドイットアームを用いて純粋探索を研究する。
私たちのゴールは、平均的な報酬が1-delta$の1つの高品質なアームを、最高の$eta$-fraction of armsの1つとして$varepsilon$内で効率的に選択することにあります。
論文 参考訳（メタデータ） (2023-06-03T04:00:47Z) - Variance-Aware Sparse Linear Bandits [64.70681598741417]
余分な線形包帯に対する最悪のミニマックスは$widetildeThetaleft(sqrtdTright)$である。
ノイズがなく、アクションセットが単位球面である良性設定では、ディビジョン・アンド・コンカーを使用して、$widetildemathcal O(1)$ regretを達成することができる。
我々は,任意の分散対応線形帯域幅アルゴリズムを分散対応線形帯域幅アルゴリズムに変換する汎用フレームワークを開発した。
論文 参考訳（メタデータ） (2022-05-26T15:55:44Z) - Approximate Top-$m$ Arm Identification with Heterogeneous Reward
Variances [11.555138461092177]
この問題の最悪のサンプルの複雑さは$Thetaleft(sum_i = 1n fracsigma_i2epsilon2 lnfrac1delta + sum_i in Gm fracsigma_j2epsilon2 textEnt(sigma2_Gr) right)$$$$$Gm, Gl, Grである。
論文 参考訳（メタデータ） (2022-04-11T16:41:33Z) - Differentially Private Multi-Armed Bandits in the Shuffle Model [58.22098764071924]
シャッフルモデルにおけるマルチアームバンディット(MAB)問題に対して,$(varepsilon,delta)$-differentially privateアルゴリズムを提案する。
我々の上限は、集中モデルにおいて最もよく知られたアルゴリズムの後悔とほぼ一致し、局所モデルにおいて最もよく知られたアルゴリズムを著しく上回っている。
論文 参考訳（メタデータ） (2021-06-05T14:11:01Z) - Bandits with many optimal arms [68.17472536610859]
最適アームの割合は$p*$、最適アームとサブ最適化アームの間の最小平均ギャップは$Delta$と書きます。
我々は,累積的後悔設定と最良腕識別設定の両方において最適な学習率を特徴付ける。
論文 参考訳（メタデータ） (2021-03-23T11:02:31Z) - Combinatorial Bandits without Total Order for Arms [52.93972547896022]
セット依存報酬分布を捕捉し、武器の合計順序を仮定しない報酬モデルを提案する。
我々は、新しい後悔分析を開発し、$Oleft(frack2 n log Tepsilonright)$ gap-dependent regret boundと$Oleft(k2sqrtn T log Tright)$ gap-dependent regret boundを示す。
論文 参考訳（メタデータ） (2021-03-03T23:08:59Z) - Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
我々は、腕の総数が膨大であることができるトップ$ k$極端な文脈的包帯問題を研究します。
まず,Inverse Gap Weighting戦略を用いて,非極端に実現可能な設定のアルゴリズムを提案する。
我々のアルゴリズムは、$O(ksqrt(A-k+1)T log (|mathcalF|T))$である。
論文 参考訳（メタデータ） (2021-02-15T19:10:52Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。