論文の概要: On the Problem of Best Arm Retention

• arxiv url: http://arxiv.org/abs/2504.11866v1
• Date: Wed, 16 Apr 2025 08:41:20 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-17 14:38:25.610287
• Title: On the Problem of Best Arm Retention
• Title（参考訳）: ベストアーム保持問題について
• Authors: Houshuang Chen, Yuchen He, Chihao Zhang,
• Abstract要約: BAR(Best Arm Retention)の問題について検討し、最近マルチアームバンディットのストリーミングアルゴリズムに応用されている。 まず,異なる基準下でのBAR問題の純粋探索と,特定の制約による後悔の最小化について検討する。
• 参考スコア（独自算出の注目度）: 2.9772441757190746
• License:
• Abstract: This paper presents a comprehensive study on the problem of Best Arm Retention (BAR), which has recently found applications in streaming algorithms for multi-armed bandits. In the BAR problem, the goal is to retain $m$ arms with the best arm included from $n$ after some trials, in stochastic multi-armed bandit settings. We first investigate pure exploration for the BAR problem under different criteria, and then minimize the regret with specific constraints, in the context of further exploration in streaming algorithms. - We begin by revisiting the lower bound for the $(\varepsilon,\delta)$-PAC algorithm for Best Arm Identification (BAI) and adapt the classical KL-divergence argument to derive optimal bounds for $(\varepsilon,\delta)$-PAC algorithms for BAR. - We further study another variant of the problem, called $r$-BAR, which requires the expected gap between the best arm and the optimal arm retained is less than $r$. We prove tight sample complexity for the problem. - We explore the regret minimization problem for $r$-BAR and develop algorithm beyond pure exploration. We conclude with a conjecture on the optimal regret in this setting.
• Abstract（参考訳）: 本稿では,BAR(Best Arm Retention)問題に関する包括的研究を行い,近年,マルチアームバンディットのストリーミングアルゴリズムの応用が報告されている。 BARの問題は、いくつかのトライアルの後、確率的なマルチアームのバンディット設定で、最高のアームで$m$を保持できるようにすることである。 まず,BAR問題に対する異なる基準下での純粋探索について検討し,ストリーミングアルゴリズムのさらなる探索の文脈において,特定の制約を伴って後悔を最小限に抑える。 -BARの$(\varepsilon,\delta)$-PACアルゴリズムの下位境界を再検討し、古典的なKL分割引数をBARの$(\varepsilon,\delta)$-PACアルゴリズムの最適境界の導出に適応させることから始める。 さらに、最適な腕と最適な腕の間のギャップが$r$未満であるような問題を$r$-BARという別の変種について研究する。 私たちはその問題に対して厳密なサンプルの複雑さを証明した。 -$r$-BARに対する後悔の最小化問題を探求し、純粋な探索を超えてアルゴリズムを開発する。 この設定における最適な後悔についての予想で締めくくります。

関連論文リスト

• Breaking the $\log(1/Δ_2)$ Barrier: Better Batched Best Arm Identification with Adaptive Grids [28.547030766096956]
  ほぼ最適なサンプル複雑性を実現するアルゴリズムを導入し、インスタンスに敏感なバッチ複雑性を特徴とする。 我々は、この枠組みを線形包帯におけるバッチ化されたベストアーム識別の問題に拡張し、同様の改善を実現する。
  論文  参考訳（メタデータ） (2025-01-29T01:40:36Z)
• Optimal Multi-Fidelity Best-Arm Identification [65.23078799972188]
  バンディットのベストアーム識別において、アルゴリズムは、できるだけ早く特定の精度で、最高平均報酬の腕を見つけることを任務とする。 マルチフィデリティのベストアーム識別について検討し、低コストで低いフィデリティ(正確な平均推定値を持たない)で腕をサンプリングすることを選択できる。 この問題に対処するためのいくつかの方法が提案されているが、その最適性は、特に最適な腕を特定するのに必要な総コストのゆるやかな下限のため、未解決のままである。
  論文  参考訳（メタデータ） (2024-06-05T08:02:40Z)
• Multi-Fidelity Multi-Armed Bandits Revisited [46.19926456682379]
  我々は,MF-MAB(Multi-fidelity multi-armed bandit)問題の拡張であるMF-MAB(Multi-fidelity multi-armed bandit)について検討した。 MF-MABは、各アームを異なるコスト(忠実さ)と観察精度で引っ張ることができる。
  論文  参考訳（メタデータ） (2023-06-13T13:19:20Z)
• Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Arms [59.8188496313214]
  半帯域 (CMAB) について検討し, 半帯域 (CMAB) におけるバッチサイズ (K$) の依存性の低減に着目した。 まず,確率的に引き起こされるアーム(CMAB-T)を用いたCMABの設定に対して,分散を考慮した信頼区間を持つBCUCB-Tアルゴリズムを提案する。 次に,独立アームを用いた非トリガ型CMABの設定に対して,TPVM条件の非トリガ型を利用したSESCBアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-31T13:09:39Z)
• Bandits with many optimal arms [68.17472536610859]
  最適アームの割合は$p*$、最適アームとサブ最適化アームの間の最小平均ギャップは$Delta$と書きます。 我々は,累積的後悔設定と最良腕識別設定の両方において最適な学習率を特徴付ける。
  論文  参考訳（メタデータ） (2021-03-23T11:02:31Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。 一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-20T04:29:18Z)
• Upper Confidence Bounds for Combining Stochastic Bandits [52.10197476419621]
  バンディットアルゴリズムを結合する簡単な手法を提案する。 私たちのアプローチは、個々のbanditアルゴリズムのそれぞれを、より高いレベルのn$-armed bandit問題のアームとして扱う"meta-ucb"手順に基づいています。
  論文  参考訳（メタデータ） (2020-12-24T05:36:29Z)
• Lenient Regret for Multi-Armed Bandits [72.56064196252498]
  エージェントが順番に行動を選択し、その行動に対する報酬を観察するマルチアーマッド・バンディット(MAB)問題を考察する。 アルゴリズムの大多数は、後悔、すなわち最高の行動の報酬とエージェントの行動の累積的な差を最小化しようとするが、この基準は望ましくない結果をもたらすかもしれない。 我々は、いくつかの$epsilon$よりも小さな最適性ギャップを無視した、より寛大で寛大で後悔すべき基準を提案する。
  論文  参考訳（メタデータ） (2020-08-10T08:30:52Z)
• The Unreasonable Effectiveness of Greedy Algorithms in Multi-Armed Bandit with Many Arms [10.662105162882526]
  本研究は,Emphmany-armed regimeにおける$k$-armed bandit問題について考察する。 以上の結果から,多腕の環境下での強欲なアルゴリズムには,新たなエフェフリー探索法が有用であることが示唆された。
  論文  参考訳（メタデータ） (2020-02-24T08:59:34Z)

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

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