論文の概要: Thompson Exploration with Best Challenger Rule in Best Arm Identification

• arxiv url: http://arxiv.org/abs/2310.00539v1
• Date: Sun, 1 Oct 2023 01:37:02 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-05 03:38:57.639940
• Title: Thompson Exploration with Best Challenger Rule in Best Arm Identification
• Title（参考訳）: ベストアーム識別におけるベストチャレンジャールールを用いたトンプソン探究
• Authors: Jongyeong Lee, Junya Honda, Masashi Sugiyama
• Abstract要約: 本稿では,バンドイットフレームワークにおける固定信頼度最良腕識別問題について検討する。 我々は、トンプソンサンプリングと、ベストチャレンジャールールとして知られる計算効率の良いアプローチを組み合わせた新しいポリシーを提案する。
• 参考スコア（独自算出の注目度）: 66.33448474838342
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper studies the fixed-confidence best arm identification (BAI) problem in the bandit framework in the canonical single-parameter exponential models. For this problem, many policies have been proposed, but most of them require solving an optimization problem at every round and/or are forced to explore an arm at least a certain number of times except those restricted to the Gaussian model. To address these limitations, we propose a novel policy that combines Thompson sampling with a computationally efficient approach known as the best challenger rule. While Thompson sampling was originally considered for maximizing the cumulative reward, we demonstrate that it can be used to naturally explore arms in BAI without forcing it. We show that our policy is asymptotically optimal for any two-armed bandit problems and achieves near optimality for general $K$-armed bandit problems for $K\geq 3$. Nevertheless, in numerical experiments, our policy shows competitive performance compared to asymptotically optimal policies in terms of sample complexity while requiring less computation cost. In addition, we highlight the advantages of our policy by comparing it to the concept of $\beta$-optimality, a relaxed notion of asymptotic optimality commonly considered in the analysis of a class of policies including the proposed one.
• Abstract（参考訳）: 本稿では,標準単パラメータ指数モデルにおけるバンドイットフレームワークにおける固定信頼度ベストアーム識別(BAI)問題について検討する。 この問題については、多くのポリシーが提案されているが、その多くは各ラウンドの最適化問題を解くことが必要であり、ガウスモデルに制限されているものを除いて少なくとも一定回数はアームを探索せざるを得ない。 これらの制限に対処するために,トンプソンサンプリングと最良挑戦則として知られる計算効率の良いアプローチを組み合わせた新しい方針を提案する。 トンプソンサンプリングはもともと累積報酬の最大化を目的としていたが,BAIの腕を強制せずに自然に探索できることを示した。 我々は,両腕バンディット問題に対して漸近的に最適であり,一般の$K$武器バンディット問題に対して$K\geq 3$に対してほぼ最適であることを示す。 それにもかかわらず,数値実験では,計算コストを削減しつつ,サンプル複雑性の観点からの漸近的最適政策と比較し,競合性能を示す。 さらに,提案手法を含む政策のクラス分析においてよく考慮される漸近的最適性の概念である$\beta$-optimalityの概念と比較することで,我々の政策の利点を強調する。

関連論文リスト

• Optimal Multi-Fidelity Best-Arm Identification [65.23078799972188]
  バンディットのベストアーム識別において、アルゴリズムは、できるだけ早く特定の精度で、最高平均報酬の腕を見つけることを任務とする。 マルチフィデリティのベストアーム識別について検討し、低コストで低いフィデリティ(正確な平均推定値を持たない)で腕をサンプリングすることを選択できる。 この問題に対処するためのいくつかの方法が提案されているが、その最適性は、特に最適な腕を特定するのに必要な総コストのゆるやかな下限のため、未解決のままである。
  論文  参考訳（メタデータ） (2024-06-05T08:02:40Z)
• Oracle-Efficient Reinforcement Learning for Max Value Ensembles [7.404901768256101]
  大または無限の状態空間における強化学習(RL)は、理論上、実験的に困難である。 この作業では、$textitmax-following Policy$と競合することを目指しています。 我々の主な成果は、構成ポリシーのみにアクセスすると、最大フォローポリシーと競合する効率的なアルゴリズムである。
  論文  参考訳（メタデータ） (2024-05-27T01:08:23Z)
• Theoretical guarantees on the best-of-n alignment policy [110.21094183592358]
  基本方針と最良$n$ポリシーのKL分散は、$log (n) - (n-1)/n.$と等しいことを示す。 KLの発散に対する新しい推定器を提案し、いくつかの例を通して厳密な近似を与えることを実証的に示す。
  論文  参考訳（メタデータ） (2024-01-03T18:39:13Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Restless Bandits with Average Reward: Breaking the Uniform Global Attractor Assumption [12.471848976031904]
  基本的な目標は、腕の数($N$)が大きくなるにつれて、最適性のギャップを小さくするポリシーを効率的に計算することである。 既存の最適性に関する結果は、すべて一様大域的誘引特性(UGAP)に依存している。 我々は,任意の単一武器のポリシーを元の$N$武器の問題に対するポリシーに変換する,汎用的なシミュレーションベースのフレームワークを提案する。
  論文  参考訳（メタデータ） (2023-05-31T21:26:43Z)
• Estimating Optimal Policy Value in General Linear Contextual Bandits [50.008542459050155]
  多くのバンドイット問題において、政策によって達成可能な最大報酬は、前もって不明であることが多い。 我々は,最適政策が学習される前に,サブ線形データ構造における最適政策値を推定する問題を考察する。 V*$で問題依存上界を推定する,より実用的で効率的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-19T01:09:24Z)
• Restless Bandits with Many Arms: Beating the Central Limit Theorem [25.639496138046546]
  有限ホライズン・レスト・ブレイディット(有限ホライズン・レスト・ブレイディット)は、レコメンデーターシステム、アクティブラーニング、収益管理、その他多くの分野で重要な役割を果たしている。 最適ポリシーは、原理的には動的プログラミングを用いて計算できるが、計算に必要なスケールは腕数$N$で指数関数的にスケールする。 最適性ギャップが$O(1)$である流体プライオリティポリシと呼ばれる、非退化条件と、実用的に計算可能な新しいポリシーのクラスを特徴付ける。
  論文  参考訳（メタデータ） (2021-07-25T23:27:12Z)
• Thompson Sampling for Unimodal Bandits [21.514495320038712]
  本稿では, 半順序の腕に対して期待される報酬が一様であるアンフンモダル・バンディットに対するトンプソンサンプリングアルゴリズムを提案する。 ガウスの報酬に対して、我々のアルゴリズムの後悔は$mathcalO(log T)$であり、標準的なトンプソンサンプリングアルゴリズムよりもはるかに優れている。
  論文  参考訳（メタデータ） (2021-06-15T14:40:34Z)
• MOTS: Minimax Optimal Thompson Sampling [89.2370817955411]
  トンプソンサンプリングがミニマックス下限の$Omega(sqrtKT)$と$K$の武器付きバンディット問題に一致するかどうかという未解決の問題のままである。 我々は,各タイミングで選択した腕のサンプリングインスタンスを適応的にクリップするMOTSと呼ばれるトンプソンサンプリングの変種を提案する。 我々は、この単純なトンプソンサンプリングの変種が、有限時間地平線に対して$O(sqrtKT)$のミニマックス最適後悔境界と、$T$が無限に近づくときのガウス報酬に対する最適後悔境界を達成することを証明した。
  論文  参考訳（メタデータ） (2020-03-03T21:24:39Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。