論文の概要: Nearly-tight Approximation Guarantees for the Improving Multi-Armed Bandits Problem
- arxiv url: http://arxiv.org/abs/2404.01198v1
- Date: Mon, 1 Apr 2024 15:55:45 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-03 21:55:47.491497
- Title: Nearly-tight Approximation Guarantees for the Improving Multi-Armed Bandits Problem
- Title（参考訳）: マルチアーマッド帯域問題改善のためのニアタイト近似保証
- Authors: Avrim Blum, Kavya Ravichandran,
- Abstract要約: この問題の例としては、$k$のアームがあり、それぞれの報酬関数は凹凸であり、腕が引き抜かれた回数の関数が増加する。
任意のランダム化オンラインアルゴリズムに対して、最適報酬に対して少なくとも$Omega(sqrtk)$近似係数を負わなければならない事例が存在することを示す。
次に、この仮定を余分な$O(sqrtk log k)$近似係数のコストで除去する方法を示し、全体的な$O(sqrtk)を達成する。
- 参考スコア（独自算出の注目度）: 10.994427113326996
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We give nearly-tight upper and lower bounds for the improving multi-armed bandits problem. An instance of this problem has $k$ arms, each of whose reward function is a concave and increasing function of the number of times that arm has been pulled so far. We show that for any randomized online algorithm, there exists an instance on which it must suffer at least an $\Omega(\sqrt{k})$ approximation factor relative to the optimal reward. We then provide a randomized online algorithm that guarantees an $O(\sqrt{k})$ approximation factor, if it is told the maximum reward achievable by the optimal arm in advance. We then show how to remove this assumption at the cost of an extra $O(\log k)$ approximation factor, achieving an overall $O(\sqrt{k} \log k)$ approximation relative to optimal.
- Abstract（参考訳）: 改良されたマルチアームバンディット問題に対して,上と下の境界をほぼ8つ与える。
この問題の例としては、$k$のアームがあり、それぞれの報酬関数は凹凸であり、腕が引き抜かれた回数の関数が増加する。
任意のランダム化オンラインアルゴリズムに対して、最適報酬に対して少なくとも$\Omega(\sqrt{k})$近似係数を負わなければならない事例が存在することを示す。
次に、あらかじめ最適なアームで達成可能な最大報酬が与えられると、$O(\sqrt{k})$近似係数を保証するランダム化オンラインアルゴリズムを提供する。
次に、この仮定を余分な$O(\log k)$近似係数のコストで除去する方法を示し、全体的な$O(\sqrt{k} \log k)$近似を最適に対して達成する。
関連論文リスト
- Optimal Top-Two Method for Best Arm Identification and Fluid Analysis [15.353009236788262]
最適な腕識別問題に対する最適トップ2型アルゴリズムを提案する。
提案アルゴリズムは$delta rightarrow 0$として最適であることを示す。
論文 参考訳（メタデータ） (2024-03-14T06:14:07Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - On the complexity of All $\varepsilon$-Best Arms Identification [2.1485350418225244]
ガウスの報酬を持つ有限の多腕バンディットにおいて、$varepsilon$-optimal armsを全て識別する問題を考える。
我々は,$varepsilon$-good arms w.h.p の集合を同定し,期待されるサンプルの複雑さの観点から最適性($delta$が 0 になるとき)を享受するトラック・アンド・ストップアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-02-13T10:54:52Z) - Bandits with many optimal arms [68.17472536610859]
最適アームの割合は$p*$、最適アームとサブ最適化アームの間の最小平均ギャップは$Delta$と書きます。
我々は,累積的後悔設定と最良腕識別設定の両方において最適な学習率を特徴付ける。
論文 参考訳（メタデータ） (2021-03-23T11:02:31Z) - Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
我々は、腕の総数が膨大であることができるトップ$ k$極端な文脈的包帯問題を研究します。
まず,Inverse Gap Weighting戦略を用いて,非極端に実現可能な設定のアルゴリズムを提案する。
我々のアルゴリズムは、$O(ksqrt(A-k+1)T log (|mathcalF|T))$である。
論文 参考訳（メタデータ） (2021-02-15T19:10:52Z) - 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) - Lenient Regret for Multi-Armed Bandits [72.56064196252498]
エージェントが順番に行動を選択し、その行動に対する報酬を観察するマルチアーマッド・バンディット(MAB)問題を考察する。
アルゴリズムの大多数は、後悔、すなわち最高の行動の報酬とエージェントの行動の累積的な差を最小化しようとするが、この基準は望ましくない結果をもたらすかもしれない。
我々は、いくつかの$epsilon$よりも小さな最適性ギャップを無視した、より寛大で寛大で後悔すべき基準を提案する。
論文 参考訳（メタデータ） (2020-08-10T08:30:52Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。