論文の概要: Optimal Batched Best Arm Identification
- arxiv url: http://arxiv.org/abs/2310.14129v1
- Date: Sat, 21 Oct 2023 22:55:50 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-25 01:44:13.690342
- Title: Optimal Batched Best Arm Identification
- Title（参考訳）: 最適バッチ最適腕識別法
- Authors: Tianyuan Jin, Yu Yang, Jing Tang, Xiaokui Xiao, Pan Xu
- Abstract要約: バッチ化されたベストアーム識別(BBAI)問題について検討し、学習者のゴールは、ポリシーをできるだけ少なく変更しながら、最適なアームを識別することである。
特に、ある小さな定数$delta>0$に対して、確率1-delta$の最良のアームを見つけることを目指している。
本稿では,Tri-BBAIアルゴリズムとOpt-BBAIアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 31.794242669480106
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the batched best arm identification (BBAI) problem, where the
learner's goal is to identify the best arm while switching the policy as less
as possible. In particular, we aim to find the best arm with probability
$1-\delta$ for some small constant $\delta>0$ while minimizing both the sample
complexity (total number of arm pulls) and the batch complexity (total number
of batches). We propose the three-batch best arm identification (Tri-BBAI)
algorithm, which is the first batched algorithm that achieves the optimal
sample complexity in the asymptotic setting (i.e., $\delta\rightarrow 0$) and
runs only in at most $3$ batches. Based on Tri-BBAI, we further propose the
almost optimal batched best arm identification (Opt-BBAI) algorithm, which is
the first algorithm that achieves the near-optimal sample and batch complexity
in the non-asymptotic setting (i.e., $\delta>0$ is arbitrarily fixed), while
enjoying the same batch and sample complexity as Tri-BBAI when $\delta$ tends
to zero. Moreover, in the non-asymptotic setting, the complexity of previous
batch algorithms is usually conditioned on the event that the best arm is
returned (with a probability of at least $1-\delta$), which is potentially
unbounded in cases where a sub-optimal arm is returned. In contrast, the
complexity of Opt-BBAI does not rely on such an event. This is achieved through
a novel procedure that we design for checking whether the best arm is
eliminated, which is of independent interest.
- Abstract（参考訳）: バッチ化されたベストアーム識別(BBAI)問題について検討し、学習者のゴールは、ポリシーを可能な限り変更しながら最適なアームを特定することである。
特に、サンプルの複雑さ(アームプルの総数)とバッチの複雑さ(バッチの総数)を最小化しながら、いくつかの小さな定数$\delta>0$に対して、確率1-\delta$の最適なアームを見つけることを目指している。
3-batch best arm identification (tri-bbai)アルゴリズムを提案する。これは漸近的な設定($\delta\rightarrow 0$)で最適なサンプル複雑性を達成する最初のバッチアルゴリズムであり、最大3ドルのバッチでのみ実行される。
さらに,Tri-BBAIをベースとしたOpt-BBAIアルゴリズムを提案する。このアルゴリズムは,非漸近的条件(例えば$\delta>0$は任意に固定される)において,ほぼ最適に近いサンプルとバッチの複雑さを達成するアルゴリズムであり,Tri-BBAIと同じバッチとサンプルの複雑さを,$\delta$が0の傾向にある場合に楽しむ。
さらに、非漸近的な設定では、前回のバッチアルゴリズムの複雑さは、最善のアームが返される(少なくとも1-\delta$の確率を持つ)場合に、通常条件付けされる。
対照的に、Ops-BBAIの複雑さはそのようなイベントに依存しない。
これは、最高の腕が取り除かれているかどうかをチェックするために設計する新しい手順によって達成されます。
関連論文リスト
- Optimal Multi-Fidelity Best-Arm Identification [65.23078799972188]
バンディットのベストアーム識別において、アルゴリズムは、できるだけ早く特定の精度で、最高平均報酬の腕を見つけることを任務とする。
マルチフィデリティのベストアーム識別について検討し、低コストで低いフィデリティ(正確な平均推定値を持たない)で腕をサンプリングすることを選択できる。
この問題に対処するためのいくつかの方法が提案されているが、その最適性は、特に最適な腕を特定するのに必要な総コストのゆるやかな下限のため、未解決のままである。
論文 参考訳（メタデータ） (2024-06-05T08:02:40Z) - Optimal Top-Two Method for Best Arm Identification and Fluid Analysis [15.353009236788262]
最適な腕識別問題に対する最適トップ2型アルゴリズムを提案する。
提案アルゴリズムは$delta rightarrow 0$として最適であることを示す。
論文 参考訳（メタデータ） (2024-03-14T06:14:07Z) - lil'HDoC: An Algorithm for Good Arm Identification under Small Threshold
Gap [4.666048091337632]
グッドアーム識別(GAI)は、単一の学習者が良い腕と特定されるとすぐに腕を出力する純粋探索バンディット問題である。
本稿では,腕の期待報酬と与えられた閾値との距離を参考に,小さな閾値ギャップ下でのGAI問題に焦点を当てた。
我々は,HDoCアルゴリズムの総サンプリング複雑性を大幅に改善するLil'HDoCと呼ばれる新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-01-29T04:21:47Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - 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) - Mean-based Best Arm Identification in Stochastic Bandits under Reward
Contamination [80.53485617514707]
本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。
具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
論文 参考訳（メタデータ） (2021-11-14T21:49:58Z) - Bandits with many optimal arms [68.17472536610859]
最適アームの割合は$p*$、最適アームとサブ最適化アームの間の最小平均ギャップは$Delta$と書きます。
我々は,累積的後悔設定と最良腕識別設定の両方において最適な学習率を特徴付ける。
論文 参考訳（メタデータ） (2021-03-23T11:02:31Z) - 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) - An Optimal Elimination Algorithm for Learning a Best Arm [37.18327505953403]
古典的な問題である$(epsilon,delta)$-PAC学習をベストアームとみなす。
本稿では,$(epsilon,delta)$-PAC学習を最適なアームとして提案する。
論文 参考訳（メタデータ） (2020-06-20T20:21:33Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。