論文の概要: Algorithm Design and Stronger Guarantees for the Improving Multi-Armed Bandits Problem

• arxiv url: http://arxiv.org/abs/2511.10619v1
• Date: Fri, 14 Nov 2025 02:00:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-14 22:53:22.959516
• Title: Algorithm Design and Stronger Guarantees for the Improving Multi-Armed Bandits Problem
• Title（参考訳）: マルチアーマッド帯域問題の改善のためのアルゴリズム設計とより強力な保証
• Authors: Avrim Blum, Marten Garicano, Kavya Ravichandran, Dravyansh Sharma,
• Abstract要約: 増え続ける研究は、多少悲観的な最悪の保証があるにもかかわらず、盗賊を改善するためのアルゴリズムを設計してきた。 本研究では,2つの新しいパラメータ化された帯域幅アルゴリズム群を提案し,オフラインデータを用いて各家族から近最適アルゴリズムを学習する際のサンプル複雑性を限定する。 この家系から適切に選択されたアルゴリズムがより強力な保証を達成できることを示し、アーム報酬曲線が凹凸の強さに関連する追加特性を満たすとき、$k$に最適に依存することを示す。
• 参考スコア（独自算出の注目度）: 15.511904255232814
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The improving multi-armed bandits problem is a formal model for allocating effort under uncertainty, motivated by scenarios such as investing research effort into new technologies, performing clinical trials, and hyperparameter selection from learning curves. Each pull of an arm provides reward that increases monotonically with diminishing returns. A growing line of work has designed algorithms for improving bandits, albeit with somewhat pessimistic worst-case guarantees. Indeed, strong lower bounds of $Ω(k)$ and $Ω(\sqrt{k})$ multiplicative approximation factors are known for both deterministic and randomized algorithms (respectively) relative to the optimal arm, where $k$ is the number of bandit arms. In this work, we propose two new parameterized families of bandit algorithms and bound the sample complexity of learning the near-optimal algorithm from each family using offline data. The first family we define includes the optimal randomized algorithm from prior work. We show that an appropriately chosen algorithm from this family can achieve stronger guarantees, with optimal dependence on $k$, when the arm reward curves satisfy additional properties related to the strength of concavity. Our second family contains algorithms that both guarantee best-arm identification on well-behaved instances and revert to worst case guarantees on poorly-behaved instances. Taking a statistical learning perspective on the bandit rewards optimization problem, we achieve stronger data-dependent guarantees without the need for actually verifying whether the assumptions are satisfied.
• Abstract（参考訳）: マルチアームバンディット問題の改善は、新しい技術への研究の取り組み、臨床試験の実行、学習曲線からのハイパーパラメータ選択などのシナリオによって動機づけられた、不確実性の下での努力を割り当てるための正式なモデルである。 アームの各プルは、リターンの減少とともに単調に増加する報酬を提供する。 増え続ける研究は、多少悲観的な最悪の保証があるにもかかわらず、盗賊を改善するためのアルゴリズムを設計してきた。 実際、$Ω(k)$と$Ω(\sqrt{k})$乗法近似係数の強い下界は、最適アームに対して決定論的およびランダム化されたアルゴリズム(つまり、$k$はバンド型アームの数)の両方で知られている。 本研究では,2つの新しいパラメータ化された帯域幅アルゴリズム群を提案し,オフラインデータを用いて各家族から近最適アルゴリズムを学習する際のサンプル複雑性を限定する。 私たちが定義する最初のファミリーは、前の作業から最適なランダム化アルゴリズムを含む。 この家系から適切に選択されたアルゴリズムがより強力な保証を達成できることを示し、アーム報酬曲線が凹凸の強さに関連する追加特性を満たすとき、$k$に最適に依存することを示す。 第2のファミリーには、善良なインスタンスにおける最高の武器識別を保証するアルゴリズムと、劣悪なインスタンスにおける最悪のケース保証に戻すアルゴリズムが含まれています。 バンディットの最適化問題に対する統計的学習の観点から、仮定が満たされているかどうかを実際に検証することなく、より強力なデータ依存保証を実現する。

関連論文リスト

• Optimal Multi-Fidelity Best-Arm Identification [65.23078799972188]
  バンディットのベストアーム識別において、アルゴリズムは、できるだけ早く特定の精度で、最高平均報酬の腕を見つけることを任務とする。 マルチフィデリティのベストアーム識別について検討し、低コストで低いフィデリティ(正確な平均推定値を持たない)で腕をサンプリングすることを選択できる。 この問題に対処するためのいくつかの方法が提案されているが、その最適性は、特に最適な腕を特定するのに必要な総コストのゆるやかな下限のため、未解決のままである。
  論文  参考訳（メタデータ） (2024-06-05T08:02:40Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)
• Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
  サンプルの複雑さが既知のインスタンス固有の下界と一致する単純なアルゴリズムを考案する。 既存のベストアーム識別戦略とは異なり、我々のアルゴリズムは武器の数に依存しない停止規則を用いる。
  論文  参考訳（メタデータ） (2020-06-29T14:25:51Z)
• On Regret with Multiple Best Arms [12.315392649501101]
  バンディット設定における複数のベスト/ニア最適アームの存在に関する後悔問題について検討する。 我々の目標は、問題の未知の硬さに自動的に適応できるアルゴリズムを設計することです。
  論文  参考訳（メタデータ） (2020-06-26T04:01:46Z)
• Corralling Stochastic Bandit Algorithms [54.10645564702416]
  相関アルゴリズムの後悔は、最も報酬の高い腕を含む最高のアルゴリズムの後悔よりも悪くはないことを示す。 最高報酬と他の報酬の差は、最高報酬と他の報酬の差に依存することを示す。
  論文  参考訳（メタデータ） (2020-06-16T15:33:12Z)
• Bandit algorithms to emulate human decision making using probabilistic distortions [20.422725678982726]
  報奨分布に歪んだ確率を持つ2つの多重武装バンディット問題を定式化する。 以上のような後悔の最小化の問題と、マルチアームバンディットのための最高の腕識別フレームワークについて考察する。
  論文  参考訳（メタデータ） (2016-11-30T17:37:51Z)

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

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