論文の概要: Fixed-Confidence Best Arm Identification with Decreasing Variance
- arxiv url: http://arxiv.org/abs/2502.07199v1
- Date: Tue, 11 Feb 2025 02:47:20 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-12 14:08:26.157306
- Title: Fixed-Confidence Best Arm Identification with Decreasing Variance
- Title（参考訳）: 可変化を考慮した固定信頼度ベストアーム識別
- Authors: Tamojeet Roychowdhury, Kota Srinivas Reddy, Krishna P Jagannathan, Sharayu Moharir,
- Abstract要約: 腕の報酬の変動を時間的に減少させるマルチアームバンディットにおけるベストアーム識別の問題に焦点をあてる。
学習者によるコストは、最適な腕を特定するのに必要な時間の重み付けされた和としてモデル化される。
- 参考スコア（独自算出の注目度）: 12.018304940341793
- License:
- Abstract: We focus on the problem of best-arm identification in a stochastic multi-arm bandit with temporally decreasing variances for the arms' rewards. We model arm rewards as Gaussian random variables with fixed means and variances that decrease with time. The cost incurred by the learner is modeled as a weighted sum of the time needed by the learner to identify the best arm, and the number of samples of arms collected by the learner before termination. Under this cost function, there is an incentive for the learner to not sample arms in all rounds, especially in the initial rounds. On the other hand, not sampling increases the termination time of the learner, which also increases cost. This trade-off necessitates new sampling strategies. We propose two policies. The first policy has an initial wait period with no sampling followed by continuous sampling. The second policy samples periodically and uses a weighted average of the rewards observed to identify the best arm. We provide analytical guarantees on the performance of both policies and supplement our theoretical results with simulations which show that our polices outperform the state-of-the-art policies for the classical best arm identification problem.
- Abstract（参考訳）: 本稿では,確率的マルチアームバンディットにおけるベストアーム識別の問題に焦点をあてる。
固定された手段と時間とともに減少する分散を持つガウス確率変数としてアーム報酬をモデル化する。
学習者が獲得したコストは、学習者が最適な腕を特定するのに必要な時間と、学習者が終了前に収集した武器のサンプルの数とを重み付けした和としてモデル化される。
このコスト関数の下では、学習者は、特に最初のラウンドでは、すべてのラウンドで腕をサンプリングしないインセンティブがある。
一方,サンプリングを行わない場合,学習者の終了時間が増加し,コストも増大する。
このトレードオフは新たなサンプリング戦略を必要とする。
我々は2つの方針を提案する。
第1のポリシーは、サンプリングを伴わずに最初の待ち時間を持ち、続いて連続サンプリングを行う。
第2のポリシーは定期的にサンプリングされ、最高の腕を特定するために観察された報酬の重み付け平均を使用する。
我々は,両政策のパフォーマンスに関する解析的保証を提供し,従来のベストアーム識別問題に対して,我々の警察が最先端の政策より優れていることを示すシミュレーションで理論結果を補完する。
関連論文リスト
- Optimal Best Arm Identification with Fixed Confidence in Restless Bandits [66.700654953613]
本研究は,有限個の腕を持つレスレス・マルチアーム・バンディット・セッティングにおけるベスト・アーム識別について検討する。
各アームによって生成された離散時間データは、共通の有限状態空間で値を取る同質マルコフ連鎖を形成する。
その結果,あるマルコフ決定過程の長期的挙動の追跡とその状態-行動的訪問比率が,逆および達成可能性境界を解析するための重要な要素であることが示唆された。
論文 参考訳（メタデータ） (2023-10-20T10:04:05Z) - Thompson Exploration with Best Challenger Rule in Best Arm
Identification [66.33448474838342]
本稿では,バンドイットフレームワークにおける固定信頼度最良腕識別問題について検討する。
我々は、トンプソンサンプリングと、ベストチャレンジャールールとして知られる計算効率の良いアプローチを組み合わせた新しいポリシーを提案する。
論文 参考訳（メタデータ） (2023-10-01T01:37:02Z) - Pure Exploration under Mediators' Feedback [63.56002444692792]
マルチアームバンディット(Multi-armed bandits)は、各インタラクションステップにおいて、学習者が腕を選択し、報酬を観察する、シーケンシャルな意思決定フレームワークである。
本稿では,学習者が仲介者の集合にアクセスできるシナリオについて考察する。
本稿では,学習者には仲介者の方針が知られていると仮定して,最適な腕を発見するための逐次的意思決定戦略を提案する。
論文 参考訳（メタデータ） (2023-08-29T18:18:21Z) - Budgeted Multi-Armed Bandits with Asymmetric Confidence Intervals [0.9831489366502302]
予算的マルチアーマッド・バンドイット(MAB)問題について検討し、プレイヤーが期待できない報酬とコストでK$アームから選択する。
非対称な信頼区間を用いた新しいアッパー信頼境界(UCB)サンプリングポリシーである$omega$-UCBを提案する。
これらの間隔は、サンプル平均とランダム変数の境界との間の距離でスケールし、報酬コスト比をより正確かつ厳密に推定する。
論文 参考訳（メタデータ） (2023-06-12T12:35:16Z) - Covariance Adaptive Best Arm Identification [0.0]
ゴールは、腕のプル数を最小化しながら、最低でも1-$delta$の確率で腕を最も平均的な報酬で識別することである。
武器を頼りにでき、報酬を同時にサンプリングできる、より柔軟なシナリオを提案する。
この枠組みは、患者と薬物の類似性から根底にある相関関係が示唆される臨床試験など、様々な応用に関係している。
論文 参考訳（メタデータ） (2023-06-05T06:57:09Z) - Top Two Algorithms Revisited [14.783452541904365]
トップ2のアルゴリズムは、トンプソンサンプリングの多腕バンディットモデルにおける最高の腕識別への適応として現れた。
本稿では,トップ2手法の一般解析を行い,リーダーの望ましい特性,挑戦者,および腕の(おそらくは非パラメトリックな)分布を同定する。
提案手法は,トンプソンサンプリングから受け継いだリーダの選択に使用されるサンプリングステップを,他の選択に置き換えることができることを示す。
論文 参考訳（メタデータ） (2022-06-13T09:03:24Z) - Best Arm Identification in Restless Markov Multi-Armed Bandits [85.55466536537293]
マルチアームバンディット環境における最適な腕を特定することの問題点について検討する。
決定エンティティは、上限誤差確率を条件として、ベストアームのインデックスをできるだけ早く見つけることを希望する。
このポリシーは、$R$に依存する上限を達成し、$Rtoinfty$として単調に増加しないことを示す。
論文 参考訳（メタデータ） (2022-03-29T04:58:04Z) - Algorithms for Adaptive Experiments that Trade-off Statistical Analysis
with Reward: Combining Uniform Random Assignment and Reward Maximization [50.725191156128645]
トンプソンサンプリングのようなマルチアームバンディットアルゴリズムは適応的な実験を行うのに利用できる。
統計的解析のための一様ランダム化の利点を組み合わせた2つのアルゴリズムを探索する2つのアーム実験のシミュレーションを提案する。
論文 参考訳（メタデータ） (2021-12-15T22:11:58Z) - Asymptotically Optimal Bandits under Weighted Information [10.939683083130616]
エージェントが各ラウンドで複数のアームを演奏できるマルチアームバンディット装置における後悔の問題について検討する。
本稿では,Thompson-Sampling ベースの戦略を提案する。この戦略は,各腕が最高の腕であるという後続の信念として,パワープロファイルを設計する。
論文 参考訳（メタデータ） (2021-05-28T21:28:44Z) - Quantile Bandits for Best Arms Identification [10.294977861990203]
多腕バンディットにおける最適な腕識別タスクの変種について検討する。
リスクと逆の意思決定の問題によって動機づけられた当社の目標は、固定予算内で最高の$tau$-quantileの値を持つ、$m$の武器のセットを特定することです。
論文 参考訳（メタデータ） (2020-10-22T09:58:54Z) - Robustness Guarantees for Mode Estimation with an Application to Bandits [131.21717367564963]
平均ではなく報酬分布のモードを値とするマルチアームバンディットの理論を導入する。
我々は,我々のアルゴリズムが逆雑音列による腕の摂動に頑健であることを示すシミュレーションで示す。
論文 参考訳（メタデータ） (2020-03-05T21:29:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。