論文の概要: Selective Sampling for Online Best-arm Identification
- arxiv url: http://arxiv.org/abs/2110.14864v1
- Date: Thu, 28 Oct 2021 03:02:08 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-29 15:40:14.766279
- Title: Selective Sampling for Online Best-arm Identification
- Title（参考訳）: オンラインベストアーム識別のための選択サンプリング
- Authors: Romain Camilleri, Zhihan Xiong, Maryam Fazel, Lalit Jain, Kevin
Jamieson
- Abstract要約: 潜在的なオプションのセットが与えられた場合、学習者は1-delta$以上の確率で計算することを目指している。
この研究の主な成果は、ラベル付きサンプルと停止時間の間のトレードオフを正確に特徴づけるものである。
我々のフレームワークは、以前の作業で改善されたバイナリ分類をキャプチャするのに十分な一般性を持っている。
- 参考スコア（独自算出の注目度）: 19.767267982167578
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This work considers the problem of selective-sampling for best-arm
identification. Given a set of potential options
$\mathcal{Z}\subset\mathbb{R}^d$, a learner aims to compute with probability
greater than $1-\delta$, $\arg\max_{z\in \mathcal{Z}} z^{\top}\theta_{\ast}$
where $\theta_{\ast}$ is unknown. At each time step, a potential measurement
$x_t\in \mathcal{X}\subset\mathbb{R}^d$ is drawn IID and the learner can either
choose to take the measurement, in which case they observe a noisy measurement
of $x^{\top}\theta_{\ast}$, or to abstain from taking the measurement and wait
for a potentially more informative point to arrive in the stream. Hence the
learner faces a fundamental trade-off between the number of labeled samples
they take and when they have collected enough evidence to declare the best arm
and stop sampling. The main results of this work precisely characterize this
trade-off between labeled samples and stopping time and provide an algorithm
that nearly-optimally achieves the minimal label complexity given a desired
stopping time. In addition, we show that the optimal decision rule has a simple
geometric form based on deciding whether a point is in an ellipse or not.
Finally, our framework is general enough to capture binary classification
improving upon previous works.
- Abstract（参考訳）: 本研究は,ベストアーム識別のための選択的サンプリングの問題を考える。
有望なオプションのセット$\mathcal{z}\subset\mathbb{r}^d$が与えられると、学習者は$\theta_{\ast}$が不明な場合に$-\delta$,$\arg\max_{z\in \mathcal{z}} z^{\top}\theta_{\ast}$という確率で計算することを目指している。
それぞれのタイムステップで、潜在的な測定値 $x_t\in \mathcal{X}\subset\mathbb{R}^d$ を IID に描画し、学習者は、x^{\top}\theta_{\ast}$ のノイズ測定を観測するか、あるいは、測定を控えて、ストリームにさらに情報のあるポイントが到着するのを待つかのいずれかを選択することができる。
したがって、学習者は、取得したラベル付きサンプルの数と、最高のアームを宣言してサンプリングを停止するのに十分な証拠を収集した時に、根本的なトレードオフに直面します。
この研究の主な結果は、ラベル付きサンプルと停止時間の間のトレードオフを正確に特徴付けし、所望の停止時間に対して最小のラベル複雑さを達成するアルゴリズムを提供する。
さらに, 最適決定規則は, 点が楕円型であるか否かを判断する上で, 単純な幾何学的形式を持つことを示す。
最後に、我々のフレームワークは、以前の作業で改善されるバイナリ分類をキャプチャするのに十分なほど一般的です。
関連論文リスト
- 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) - On the Sample Complexity of Representation Learning in Multi-task
Bandits with Global and Local structure [77.60508571062958]
マルチタスク・バンディット問題に対する最適アーム学習の複雑さについて検討した。
アームは2つのコンポーネントで構成されます。1つはタスク間で共有され(表現と呼ばれます)、もう1つはタスク固有のもの(予測器と呼ばれます)です。
サンプルの複雑さが下界に近づき、最大で$H(Glog(delta_G)+ Xlog(delta_H))$でスケールするアルゴリズムOSRL-SCを考案する。
論文 参考訳（メタデータ） (2022-11-28T08:40:12Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
既知の滑らかな関数 $f$ の値を未知の点 $boldsymbolmu in mathbbRn$ で推定する問題について検討する。
我々は、各座標の重要性に応じてサンプルを学習するインスタンス適応アルゴリズムを設計し、少なくとも1-delta$の確率で$epsilon$の正確な推定値である$f(boldsymbolmu)$を返す。
論文 参考訳（メタデータ） (2022-03-18T18:50:52Z) - On the complexity of All $\varepsilon$-Best Arms Identification [2.1485350418225244]
ガウスの報酬を持つ有限の多腕バンディットにおいて、$varepsilon$-optimal armsを全て識別する問題を考える。
我々は,$varepsilon$-good arms w.h.p の集合を同定し,期待されるサンプルの複雑さの観点から最適性($delta$が 0 になるとき)を享受するトラック・アンド・ストップアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-02-13T10:54:52Z) - PAC Best Arm Identification Under a Deadline [101.10352416022559]
我々は、$(epsilon, delta)$-PACベストアーム識別について研究し、意思決定者は、アームプル(サンプル)の数を最小化しながら、少なくとも1 - delta$の確率で最適なアームを識別しなければならない。
この作業では、決定者はT$ラウンドの期限が与えられ、各ラウンドで、どのアームを引っ張るか、何回引っ張るかを適応的に選ぶことができる。
本稿では,この設定のための新しいアルゴリズムであるElastic Batch Racing (EBR)を提案する。
論文 参考訳（メタデータ） (2021-06-06T19:48:32Z) - Pure Exploration with Structured Preference Feedback [25.894827160719526]
我々は、機能付きN$アームを含むサブセットワイドな選好フィードバックによる純粋探索の問題を考察する。
我々は,$tildeo (fracd2k delta2)$サンプル中の最良アームの検出を少なくとも1.99ドルで保証する2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-04-12T08:57:29Z) - Explicit Best Arm Identification in Linear Bandits Using No-Regret
Learners [17.224805430291177]
線形パラメータ化マルチアームバンドにおけるベストアーム識別の問題について検討する。
そこで本研究では,この問題を解決するために,明示的に実装可能かつ証明可能な順序-最適サンプル-複雑度アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-13T05:00:01Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳（メタデータ） (2020-06-04T17:51:00Z) - Breaking the Sample Size Barrier in Model-Based Reinforcement Learning
with a Generative Model [50.38446482252857]
本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。
最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。
対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
論文 参考訳（メタデータ） (2020-05-26T17:53:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。