論文の概要: Thompson Sampling for (Combinatorial) Pure Exploration
- arxiv url: http://arxiv.org/abs/2206.09150v1
- Date: Sat, 18 Jun 2022 08:45:43 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-26 07:10:11.583701
- Title: Thompson Sampling for (Combinatorial) Pure Exploration
- Title（参考訳）: thompson sampling for (combinatorial) pure exploration (英語)
- Authors: Siwei Wang, Jun Zhu
- Abstract要約: 既存の純粋な探索の方法は、主に腕集合の上位信頼境界の和$S$を用いて、上位信頼境界の$S$を表す。
上位信頼境界の代わりに独立したランダムサンプルを用いるトンプソンサンプリング(TS)を提案する。
TS-Explore では、アームセット$S$の独立したランダムサンプルの和は、高い確率で$S$の厳密な上限を超えることはない。
- 参考スコア（独自算出の注目度）: 45.602801991116245
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Existing methods of combinatorial pure exploration mainly focus on the UCB
approach. To make the algorithm efficient, they usually use the sum of upper
confidence bounds within arm set $S$ to represent the upper confidence bound of
$S$, which can be much larger than the tight upper confidence bound of $S$ and
leads to a much higher complexity than necessary, since the empirical means of
different arms in $S$ are independent. To deal with this challenge, we explore
the idea of Thompson Sampling (TS) that uses independent random samples instead
of the upper confidence bounds, and design the first TS-based algorithm
TS-Explore for (combinatorial) pure exploration. In TS-Explore, the sum of
independent random samples within arm set $S$ will not exceed the tight upper
confidence bound of $S$ with high probability. Hence it solves the above
challenge, and achieves a lower complexity upper bound than existing efficient
UCB-based algorithms in general combinatorial pure exploration. As for pure
exploration of classic multi-armed bandit, we show that TS-Explore achieves an
asymptotically optimal complexity upper bound.
- Abstract（参考訳）: 既存の組合せ純粋探索法は主に UCB アプローチに焦点を当てている。
アルゴリズムを効率よくするために、彼らは通常、アームセット内の上限値の和$S$を使い、S$の上限値よりもはるかに大きい$S$を表現し、S$の異なるアームの実証的な手段が独立であることから、必要以上に複雑になる。
この課題に対処するために、上位信頼境界の代わりに独立したランダムサンプルを用いたトンプソンサンプリング(TS)のアイデアを探求し、(組合せ)純粋探索のためのTS-Exploreアルゴリズムを設計する。
TS-Explore では、アームセット$S$の独立したランダムサンプルの和は、高い確率で$S$の厳密な上限を超えることはない。
したがって、上記の課題を解決し、一般的な組合せ純粋探索において、既存の効率的な UCB ベースのアルゴリズムよりも低い複雑性上限を達成する。
古典的マルチアームバンディットの純粋探索については、TS-Exploreが漸近的に最適な複雑性上限を達成することを示す。
関連論文リスト
- Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - Finite-Time Regret of Thompson Sampling Algorithms for Exponential
Family Multi-Armed Bandits [88.21288104408556]
本研究では,指数関数族バンドイットに対するトンプソンサンプリング (TS) アルゴリズムの遺残について検討する。
最適な腕の過小評価を避けるために,新しいサンプリング分布を用いたトンプソンサンプリング(Expulli)を提案する。
論文 参考訳（メタデータ） (2022-06-07T18:08:21Z) - Mean-based Best Arm Identification in Stochastic Bandits under Reward
Contamination [80.53485617514707]
本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。
具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
論文 参考訳（メタデータ） (2021-11-14T21:49:58Z) - Contextual Combinatorial Volatile Bandits via Gaussian Processes [10.312968200748116]
利用可能なベースアームのセットとそのコンテキストによるコンテキスト的バンディット問題を考える。
我々は,カーネル上信頼境界(O'CLOK-UCB)を用いた最適組合せ学習と最適化というアルゴリズムを提案する。
両アルゴリズムが従来のUTBベースのアルゴリズムを現実的な設定で大幅に上回っていることを実験的に示す。
論文 参考訳（メタデータ） (2021-10-05T18:02:10Z) - Thompson Sampling for Unimodal Bandits [21.514495320038712]
本稿では, 半順序の腕に対して期待される報酬が一様であるアンフンモダル・バンディットに対するトンプソンサンプリングアルゴリズムを提案する。
ガウスの報酬に対して、我々のアルゴリズムの後悔は$mathcalO(log T)$であり、標準的なトンプソンサンプリングアルゴリズムよりもはるかに優れている。
論文 参考訳（メタデータ） (2021-06-15T14:40:34Z) - Combinatorial Pure Exploration with Bottleneck Reward Function and its
Extension to General Reward Functions [13.982295536546728]
ボトルネック報酬関数 (CPE-B) を用いたコンビネーションピュア探索問題について, 一定の信頼性と固定予算設定の下で検討する。
固定信頼と固定バジェットのアルゴリズムを両立させ,固定信頼設定のサンプル複雑性を低く設定する。
さらに、CPE-Bを一般報酬関数(CPE-G)に拡張し、非自明なサンプル複雑性を持つ一般非線形報酬関数に対する最初の固定信頼アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-02-24T06:47:51Z) - Statistical Efficiency of Thompson Sampling for Combinatorial
Semi-Bandits [56.31950477139053]
半帯域フィードバック(CMAB)を用いたマルチアームバンディットの検討
我々は Combinatorial Thompson Smpling Policy (CTS) の変種を解析する。
この最終結果は,Y Combinatorial Bandit Policy (ESCB) の効率的なサンプリングに代わるものだ。
論文 参考訳（メタデータ） (2020-06-11T17:12:11Z) - MOTS: Minimax Optimal Thompson Sampling [89.2370817955411]
トンプソンサンプリングがミニマックス下限の$Omega(sqrtKT)$と$K$の武器付きバンディット問題に一致するかどうかという未解決の問題のままである。
我々は,各タイミングで選択した腕のサンプリングインスタンスを適応的にクリップするMOTSと呼ばれるトンプソンサンプリングの変種を提案する。
我々は、この単純なトンプソンサンプリングの変種が、有限時間地平線に対して$O(sqrtKT)$のミニマックス最適後悔境界と、$T$が無限に近づくときのガウス報酬に対する最適後悔境界を達成することを証明した。
論文 参考訳（メタデータ） (2020-03-03T21:24:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。