論文の概要: Combinatorial Bandits without Total Order for Arms

• arxiv url: http://arxiv.org/abs/2103.02741v1
• Date: Wed, 3 Mar 2021 23:08:59 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-07 13:20:27.094973
• Title: Combinatorial Bandits without Total Order for Arms
• Title（参考訳）: 腕のトータルオーダーのない組合せバンディット
• Authors: Shuo Yang, Tongzheng Ren, Inderjit S. Dhillon, Sujay Sanghavi
• Abstract要約: セット依存報酬分布を捕捉し、武器の合計順序を仮定しない報酬モデルを提案する。 我々は、新しい後悔分析を開発し、$Oleft(frack2 n log Tepsilonright)$ gap-dependent regret boundと$Oleft(k2sqrtn T log Tright)$ gap-dependent regret boundを示す。
• 参考スコア（独自算出の注目度）: 52.93972547896022
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the combinatorial bandits problem, where at each time step, the online learner selects a size-$k$ subset $s$ from the arms set $\mathcal{A}$, where $\left|\mathcal{A}\right| = n$, and observes a stochastic reward of each arm in the selected set $s$. The goal of the online learner is to minimize the regret, induced by not selecting $s^*$ which maximizes the expected total reward. Specifically, we focus on a challenging setting where 1) the reward distribution of an arm depends on the set $s$ it is part of, and crucially 2) there is \textit{no total order} for the arms in $\mathcal{A}$. In this paper, we formally present a reward model that captures set-dependent reward distribution and assumes no total order for arms. Correspondingly, we propose an Upper Confidence Bound (UCB) algorithm that maintains UCB for each individual arm and selects the arms with top-$k$ UCB. We develop a novel regret analysis and show an $O\left(\frac{k^2 n \log T}{\epsilon}\right)$ gap-dependent regret bound as well as an $O\left(k^2\sqrt{n T \log T}\right)$ gap-independent regret bound. We also provide a lower bound for the proposed reward model, which shows our proposed algorithm is near-optimal for any constant $k$. Empirical results on various reward models demonstrate the broad applicability of our algorithm.
• Abstract（参考訳）: ここでは、各ステップで、オンライン学習者がアームセット $\mathcal{A}$ から size-$k$ サブセット $s$ を選択し、ここで $\left|\mathcal{A}\right| = n$ を選択し、選択されたセット $s$ で各アームの確率的報酬を観察します。 オンライン学習者の目標は、期待される総報酬を最大化する$s^*$を選択しないことによる後悔を最小限に抑えることである。 具体的には、(1) 腕の報酬分布が集合 $s$ に依存し、(2) 重要なことに、$\mathcal{A}$ の腕に対して \textit{no total order} が存在するという挑戦的な設定に焦点をあてる。 本稿では,セット依存の報酬分布をキャプチャし,腕の合計順序を仮定しない報酬モデルを提案する。 そこで本研究では,各アームに対してUCBを維持し,上-$k$UBBで腕を選択するアッパー信頼境界(UCB)アルゴリズムを提案する。 我々は新しい後悔分析を開発し、$o\left(\frac{k^2n \log t}{\epsilon}\right)$ gap-dependent regretboundと$o\left(k^2\sqrt{n t \log t}\right)$ gap-independent regretboundを示す。 また,提案した報奨モデルに対して,提案アルゴリズムは任意の定数$k$に対してほぼ最適であることを示す。 様々な報酬モデルに対する実験結果から,アルゴリズムの適用可能性を示す。

関連論文リスト

• A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
  我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。 誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。
  論文  参考訳（メタデータ） (2024-09-08T12:19:12Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Best-Arm Identification in Correlated Multi-Armed Bandits [9.180690233707645]
  本稿では,武器間の相関に関するドメイン知識を捉えた新しい相関バンディットフレームワークを提案する。 C-LUCBで得られた全サンプルは$mathcalOleft(sum_k in MathcalC logleft(frac1deltaright)$であり、通常の$mathcalOleft(sum_k in MathcalC logleft(frac1deltaright)$とは対照的である。
  論文  参考訳（メタデータ） (2021-09-10T15:41:07Z)
• Variance-Dependent Best Arm Identification [12.058652922228918]
  マルチアームバンディットゲームにおける最適な腕を特定する問題について検討する。 武器の報酬のギャップと分散を探索する適応アルゴリズムを提案する。 このアルゴリズムは2つの対数項に最適であることを示す。
  論文  参考訳（メタデータ） (2021-06-19T04:13:54Z)
• 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)
• Blocking Bandits [33.14975454724348]
  我々は、腕を弾くことで固定時間帯で使用できなくなる、新しいマルチアームバンディット・セッティングについて考察する。 全ての武器の報酬と遅延の事前知識により、累積報酬を最適化する問題は擬似多項式時間アルゴリズムを含まないことを示した。 我々は,このアルゴリズムに対して,$c log T + o(log T)$ cumulative regret を持つ UCB ベースのアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2019-07-27T20:42:01Z)

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

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