論文の概要: Optimal Algorithms for Range Searching over Multi-Armed Bandits
- arxiv url: http://arxiv.org/abs/2105.01390v1
- Date: Tue, 4 May 2021 09:52:16 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-05 12:45:10.165614
- Title: Optimal Algorithms for Range Searching over Multi-Armed Bandits
- Title（参考訳）: マルチアーマッド帯域幅探索のための最適アルゴリズム
- Authors: Siddharth Barman, Ramakrishnan Krishnamurthy, Saladi Rahul
- Abstract要約: 本稿では,マルチアームバンディット(MAB)のレンジ探索問題について検討する。
サンプル効率のよいアルゴリズムを開発し、高い確率で、与えられた間隔内で準最適腕を求める。
私たちの結果は、MAB設定における幾何学的構成、特に打撃集合の重要性を強調します。
- 参考スコア（独自算出の注目度）: 17.800612821499612
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper studies a multi-armed bandit (MAB) version of the range-searching
problem. In its basic form, range searching considers as input a set of points
(on the real line) and a collection of (real) intervals. Here, with each
specified point, we have an associated weight, and the problem objective is to
find a maximum-weight point within every given interval.
The current work addresses range searching with stochastic weights: each
point corresponds to an arm (that admits sample access) and the point's weight
is the (unknown) mean of the underlying distribution. In this MAB setup, we
develop sample-efficient algorithms that find, with high probability,
near-optimal arms within the given intervals, i.e., we obtain PAC (probably
approximately correct) guarantees. We also provide an algorithm for a
generalization wherein the weight of each point is a multi-dimensional vector.
The sample complexities of our algorithms depend, in particular, on the size of
the optimal hitting set of the given intervals.
Finally, we establish lower bounds proving that the obtained sample
complexities are essentially tight. Our results highlight the significance of
geometric constructs -- specifically, hitting sets -- in our MAB setting.
- Abstract（参考訳）: 本稿では,マルチアームバンディット(MAB)のレンジ探索問題について検討する。
基本形において、範囲探索は(実数直線上の)点の集合と(実数)区間の集まりを入力として考える。
ここで、各特定の点について、関連する重みを持ち、問題の目的は、与えられた間隔ごとに最大重み点を見つけることである。
現在の作業は、確率的な重みで範囲探索に対処している: 各ポイントは(サンプルアクセスを認める)アームに対応し、ポイントの重みは基礎となる分布の(未知の)平均である。
このmab設定では、与えられた間隔内で高い確率で最適に近いアーム、すなわちpac保証(おそらくほぼ正しい)を求めるサンプル効率のよいアルゴリズムを開発する。
また,各点の重みが多次元ベクトルである一般化のためのアルゴリズムも提供する。
アルゴリズムのサンプルの複雑さは、特に与えられた区間の最適打撃集合のサイズに依存する。
最後に、得られたサンプルの複雑さが本質的に密であることを示す下界を確立する。
私たちの結果は、MAB設定における幾何学的構成、特に打撃集合の重要性を強調します。
関連論文リスト
- Optimistic Query Routing in Clustering-based Approximate Maximum Inner Product Search [9.01394829787271]
クラスタリングに基づく最大内部積探索(MIPS)におけるルーティングの問題について検討する。
最大内積を楽観的に推定するために,各シャード内の内積分布のモーメントを組み込んだ新しい枠組みを提案する。
論文 参考訳（メタデータ） (2024-05-20T17:47:18Z) - Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳（メタデータ） (2023-12-19T13:17:43Z) - Computing Star Discrepancies with Numerical Black-Box Optimization
Algorithms [56.08144272945755]
我々は,L_infty$星差分問題に対する8つの一般的な数値ブラックボックス最適化アルゴリズムを比較した。
使用済みのソルバは、ほとんどのケースで非常にひどいパフォーマンスを示します。
我々は、最先端の数値ブラックボックス最適化手法が問題のグローバルな構造を捉えるのに失敗していると疑っている。
論文 参考訳（メタデータ） (2023-06-29T14:57:56Z) - Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and
Optimal Algorithms [64.10576998630981]
最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。
ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。
本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
論文 参考訳（メタデータ） (2023-06-21T17:03:22Z) - An Optimal Algorithm for the Real-Valued Combinatorial Pure Exploration
of Multi-Armed Bandit [65.268245109828]
多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。
既存のR-CPE-MABの手法は、いわゆるトランスダクティブ線形帯域の特殊な場合と見なすことができる。
本稿では,差分探索アルゴリズム (CombGapE) を提案する。
論文 参考訳（メタデータ） (2023-06-15T15:37:31Z) - Approximating a RUM from Distributions on k-Slates [88.32814292632675]
与えられた分布を平均で最もよく近似するRUMを求める一般化時間アルゴリズムを求める。
我々の理論的結果は、実世界のデータセットに効果的でスケール可能なものを得るという、実践的な結果も得られます。
論文 参考訳（メタデータ） (2023-05-22T17:43:34Z) - Beyond the Best: Estimating Distribution Functionals in Infinite-Armed
Bandits [40.71199236098642]
無限武装バンディット問題では、各アームの平均報酬は未知の分布からサンプリングされる。
我々は、最大以上の分布関数の一般的なクラスを検討し、オフラインとオンラインの両方で統一されたメタアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-11-01T18:20:10Z) - Mean-based Best Arm Identification in Stochastic Bandits under Reward
Contamination [80.53485617514707]
本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。
具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
論文 参考訳（メタデータ） (2021-11-14T21:49:58Z) - Approximating a Target Distribution using Weight Queries [25.392248158616862]
本稿では,データセットの例を反復的に選択し,対応する重み付けクエリを実行する対話型アルゴリズムを提案する。
我々は,アルゴリズムが検出した再重み付けと,最も達成可能な再重み付けとの間の全変動距離に依存する近似を導出する。
論文 参考訳（メタデータ） (2020-06-24T11:17:43Z) - An Empirical Process Approach to the Union Bound: Practical Algorithms
for Combinatorial and Linear Bandits [34.06611065493047]
本稿では、信頼度と予算設定の固定化において、純探索線形帯域問題に対する近似アルゴリズムを提案する。
サンプルの複雑性がインスタンスの幾何でスケールし、アームの数に縛られた明示的な結合を避けるアルゴリズムを提供する。
また,固定予算設定における線形帯域幅に対する最初のアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-21T00:56:33Z) - Registration of multi-view point sets under the perspective of
expectation-maximization [31.028202531810386]
我々は、期待最大化(EM)の観点から、新しい多視点登録手法を提案する。
提案手法は、いくつかのベンチマークデータセットでテストされ、最先端のアルゴリズムと比較される。
論文 参考訳（メタデータ） (2020-02-18T10:04:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。