論文の概要: On the complexity of All $\varepsilon$-Best Arms Identification
- arxiv url: http://arxiv.org/abs/2202.06280v1
- Date: Sun, 13 Feb 2022 10:54:52 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-16 08:16:43.378319
- Title: On the complexity of All $\varepsilon$-Best Arms Identification
- Title（参考訳）: All $\varepsilon$-Best Arms Identificationの複雑さについて
- Authors: Aymen Al Marjani, Tom\'a\v{s} Koc\'ak, Aur\'elien Garivier
- Abstract要約: ガウスの報酬を持つ有限の多腕バンディットにおいて、$varepsilon$-optimal armsを全て識別する問題を考える。
我々は,$varepsilon$-good arms w.h.p の集合を同定し,期待されるサンプルの複雑さの観点から最適性($delta$が 0 になるとき)を享受するトラック・アンド・ストップアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 2.1485350418225244
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the problem introduced by \cite{Mason2020} of identifying all the
$\varepsilon$-optimal arms in a finite stochastic multi-armed bandit with
Gaussian rewards. In the fixed confidence setting, we give a lower bound on the
number of samples required by any algorithm that returns the set of
$\varepsilon$-good arms with a failure probability less than some risk level
$\delta$. This bound writes as $T_{\varepsilon}^*(\mu)\log(1/\delta)$, where
$T_{\varepsilon}^*(\mu)$ is a characteristic time that depends on the vector of
mean rewards $\mu$ and the accuracy parameter $\varepsilon$. We also provide an
efficient numerical method to solve the convex max-min program that defines the
characteristic time. Our method is based on a complete characterization of the
alternative bandit instances that the optimal sampling strategy needs to rule
out, thus making our bound tighter than the one provided by \cite{Mason2020}.
Using this method, we propose a Track-and-Stop algorithm that identifies the
set of $\varepsilon$-good arms w.h.p and enjoys asymptotic optimality (when
$\delta$ goes to zero) in terms of the expected sample complexity. Finally,
using numerical simulations, we demonstrate our algorithm's advantage over
state-of-the-art methods, even for moderate values of the risk parameter.
- Abstract（参考訳）: 我々は,gaussian rewardsを用いた有限確率的多腕バンディットにおいて,$\varepsilon$-optimal arms を同定する \cite{mason2020} によって導入された問題を考察する。
固定された信頼設定では、あるリスクレベル$\delta$よりも低い失敗確率で$\varepsilon$-goodのセットを返すアルゴリズムが必要とするサンプルの数に低い境界を与える。
この境界は$T_{\varepsilon}^*(\mu)\log(1/\delta)$と書き、$T_{\varepsilon}^*(\mu)$は平均報酬のベクトル$\mu$と精度パラメータ$\varepsilon$に依存する特性時間である。
また,特徴時間を定義する凸最大値プログラムの効率的な数値計算法も提案する。
提案手法は, 最適サンプリング戦略を除外する必要がある代替バンディットインスタンスの完全キャラクタリゼーションに基づいており, 境界を<cite{mason2020} によって提供されるものよりも厳密にする。
この手法を用いて,$\varepsilon$-good arms w.h.p のセットを同定し,期待されるサンプル複雑性の観点から漸近的最適性($\delta$ が 0 になるとき)を楽しむトラック・アンド・ストップアルゴリズムを提案する。
最後に, 数値シミュレーションを用いて, リスクパラメータの適度な値であっても, 最先端手法に対するアルゴリズムの優位性を実証する。
関連論文リスト
- Robust Sparse Regression with Non-Isotropic Designs [4.964650614497048]
2つの敵が同時に存在するときの疎線形回帰を効率的に計算可能な推定器を設計する手法を開発した。
2つの敵が存在する場合の重み付き設計に適した重み付きハマー損失の新しい解析法を提案する。
論文 参考訳（メタデータ） (2024-10-31T13:51:59Z) - Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits [55.957560311008926]
そこで本研究では,各文脈の平均値によって腕の質を計測するPSLBモデルを提案する。
PS$varepsilon$BAI$+$は、$varepsilon$-optimal armを、確率$ge 1-delta$と最小限のサンプルで識別することが保証される。
論文 参考訳（メタデータ） (2024-10-10T06:15:42Z) - Asymptotically Optimal Pure Exploration for Infinite-Armed Bandits [4.811176167998627]
我々は、未知の分布から生じる無限に多くのバンドイットアームを用いて純粋探索を研究する。
私たちのゴールは、平均的な報酬が1-delta$の1つの高品質なアームを、最高の$eta$-fraction of armsの1つとして$varepsilon$内で効率的に選択することにあります。
論文 参考訳（メタデータ） (2023-06-03T04:00:47Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳（メタデータ） (2022-12-01T15:57:58Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Bandits with many optimal arms [68.17472536610859]
最適アームの割合は$p*$、最適アームとサブ最適化アームの間の最小平均ギャップは$Delta$と書きます。
我々は,累積的後悔設定と最良腕識別設定の両方において最適な学習率を特徴付ける。
論文 参考訳（メタデータ） (2021-03-23T11:02:31Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Explicit Best Arm Identification in Linear Bandits Using No-Regret
Learners [17.224805430291177]
線形パラメータ化マルチアームバンドにおけるベストアーム識別の問題について検討する。
そこで本研究では,この問題を解決するために,明示的に実装可能かつ証明可能な順序-最適サンプル-複雑度アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-13T05:00:01Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳（メタデータ） (2020-06-06T13:34:41Z) - Optimal $\delta$-Correct Best-Arm Selection for Heavy-Tailed
Distributions [2.2940141855172036]
我々は、$delta$-correctアルゴリズムを用いて、最大平均値を持つものを識別する問題を考察する。
$delta$-correctアルゴリズムの下位境界はよく知られている。
我々は,下界の$delta$-correctアルゴリズムを提案し,$delta$を0に還元する。
論文 参考訳（メタデータ） (2019-08-24T05:31:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。