論文の概要: DART: aDaptive Accept RejecT for non-linear top-K subset identification

• arxiv url: http://arxiv.org/abs/2011.07687v1
• Date: Mon, 16 Nov 2020 02:10:06 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-24 23:40:03.103611
• Title: DART: aDaptive Accept RejecT for non-linear top-K subset identification
• Title（参考訳）: dart: 非線形top-kサブセット識別のためのadaptive accept reject
• Authors: Mridul Agarwal, Vaneet Aggarwal, Christopher J. Quinn, Abhishek Umrawal
• Abstract要約: 我々は、各ステップでN$アームからK$を選択するという盗賊問題を考える。 本稿では,各アームのフィードバックや報酬関数の線形性を必要としない新しいアルゴリズムを提案する。 我々のアルゴリズムであるaDaptive Accept RejecT (DART)は、良好な腕を逐次見つけ、信頼境界に基づいて悪い腕を除去する。
• 参考スコア（独自算出の注目度）: 34.68931784199599
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the bandit problem of selecting $K$ out of $N$ arms at each time step. The reward can be a non-linear function of the rewards of the selected individual arms. The direct use of a multi-armed bandit algorithm requires choosing among $\binom{N}{K}$ options, making the action space large. To simplify the problem, existing works on combinatorial bandits {typically} assume feedback as a linear function of individual rewards. In this paper, we prove the lower bound for top-$K$ subset selection with bandit feedback with possibly correlated rewards. We present a novel algorithm for the combinatorial setting without using individual arm feedback or requiring linearity of the reward function. Additionally, our algorithm works on correlated rewards of individual arms. Our algorithm, aDaptive Accept RejecT (DART), sequentially finds good arms and eliminates bad arms based on confidence bounds. DART is computationally efficient and uses storage linear in $N$. Further, DART achieves a regret bound of $\tilde{\mathcal{O}}(K\sqrt{KNT})$ for a time horizon $T$, which matches the lower bound in bandit feedback up to a factor of $\sqrt{\log{2NT}}$. When applied to the problem of cross-selling optimization and maximizing the mean of individual rewards, the performance of the proposed algorithm surpasses that of state-of-the-art algorithms. We also show that DART significantly outperforms existing methods for both linear and non-linear joint reward environments.
• Abstract（参考訳）: 私たちは、各時間ステップで$n$ armsから$k$を選択するというバンディットの問題を考えています。 報酬は、選択された個々の腕の報酬の非線形機能である。 マルチアームのbanditアルゴリズムを直接使用するには、$\binom{n}{k}$オプションを選択する必要がある。 問題を単純化するため、既存の組合せバンディットの作品は、フィードバックを個々の報酬の線形関数として想定している。 本稿では,上位$K$サブセット選択の下位境界を,潜在的に相関した報酬を持つ帯域フィードバックで証明する。 本稿では,個別のアームフィードバックや報酬関数の線形性を必要としない組合せ設定のための新しいアルゴリズムを提案する。 さらに,本アルゴリズムは個々の腕の報酬に相関する。 我々のアルゴリズムであるaDaptive Accept RejecT (DART)は、良好な腕を逐次見つけ、信頼境界に基づいて悪い腕を取り除く。 DARTは計算効率が良く、容量は$N$で線形である。 さらに、DART は、時間的地平線に対して $\tilde{\mathcal{O}}(K\sqrt{KNT})$ の後悔境界を達成する。 クロスセールス最適化と個人報酬の平均値の最大化の問題に適用した場合,提案アルゴリズムの性能は最先端のアルゴリズムを上回る。 また,DARTは線形および非線形の連接報酬環境において既存手法よりも優れていた。

関連論文リスト

• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• PopArt: Efficient Sparse Regression and Experimental Design for Optimal Sparse Linear Bandits [29.097522376094624]
  そこで我々はPopArtと呼ばれる単純で効率的なスパース線形推定法を提案する。 我々は, 粗い線形バンディットアルゴリズムを導出し, 美術品の状態に対する後悔の上界の改善を享受する。
  論文  参考訳（メタデータ） (2022-10-25T19:13:20Z)
• Nearly Minimax Algorithms for Linear Bandits with Shared Representation [86.79657561369397]
  我々は、次元が$d$で、それぞれ$T$のラウンドで$M$リニアバンディットをプレイする設定を考え、これらの$M$リニアバンディットタスクは共通の$k(ll d)$次元リニア表現を共有する。 我々は$widetildeOleft(dsqrtkMT + kMsqrtTright)$ regret boundsを達成する新しいアルゴリズムを考案した。
  論文  参考訳（メタデータ） (2022-03-29T15:27:13Z)
• Combinatorial Bandits without Total Order for Arms [52.93972547896022]
  セット依存報酬分布を捕捉し、武器の合計順序を仮定しない報酬モデルを提案する。 我々は、新しい後悔分析を開発し、$Oleft(frack2 n log Tepsilonright)$ gap-dependent regret boundと$Oleft(k2sqrtn T log Tright)$ gap-dependent regret boundを示す。
  論文  参考訳（メタデータ） (2021-03-03T23:08:59Z)
• 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)
• Adversarial Combinatorial Bandits with General Non-linear Reward Functions [29.775097827244853]
  既知の非線形報酬関数を用いて対向性バンディットを研究し、対向性線形バンディットに関する既存の研究を延長する。 我々は、$N$の腕と$K$の腕のサブセットが$T$の期間のそれぞれで選択されている場合、ミニマックスの最適な後悔は$widetildeTheta_d(Nd T)$報酬関数が$dK$の$d$度であり、$ta_K(sqrtK T)$報酬関数が低度ではない場合です。
  論文  参考訳（メタデータ） (2021-01-05T00:56:27Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)

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

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