論文の概要: Blocking Bandits

• arxiv url: http://arxiv.org/abs/1907.11975v2
• Date: Mon, 29 Jul 2024 23:06:12 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-31 23:24:35.030268
• Title: Blocking Bandits
• Title（参考訳）: 閉塞帯
• Authors: Soumya Basu, Rajat Sen, Sujay Sanghavi, Sanjay Shakkottai,
• Abstract要約: 我々は、腕を弾くことで固定時間帯で使用できなくなる、新しいマルチアームバンディット・セッティングについて考察する。 全ての武器の報酬と遅延の事前知識により、累積報酬を最適化する問題は擬似多項式時間アルゴリズムを含まないことを示した。 我々は,このアルゴリズムに対して,$c log T + o(log T)$ cumulative regret を持つ UCB ベースのアルゴリズムを設計する。
• 参考スコア（独自算出の注目度）: 33.14975454724348
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider a novel stochastic multi-armed bandit setting, where playing an arm makes it unavailable for a fixed number of time slots thereafter. This models situations where reusing an arm too often is undesirable (e.g. making the same product recommendation repeatedly) or infeasible (e.g. compute job scheduling on machines). We show that with prior knowledge of the rewards and delays of all the arms, the problem of optimizing cumulative reward does not admit any pseudo-polynomial time algorithm (in the number of arms) unless randomized exponential time hypothesis is false, by mapping to the PINWHEEL scheduling problem. Subsequently, we show that a simple greedy algorithm that plays the available arm with the highest reward is asymptotically $(1-1/e)$ optimal. When the rewards are unknown, we design a UCB based algorithm which is shown to have $c \log T + o(\log T)$ cumulative regret against the greedy algorithm, leveraging the free exploration of arms due to the unavailability. Finally, when all the delays are equal the problem reduces to Combinatorial Semi-bandits providing us with a lower bound of $c' \log T+ \omega(\log T)$.
• Abstract（参考訳）: そこで本研究では,腕の演奏によって固定時間帯では使用できない,確率的マルチアームバンディットの設定について考察する。 このモデルでは、腕を頻繁に再利用するのは望ましくない(例:繰り返し同じ製品を推奨する)、あるいは不可能(例:マシンでのジョブスケジューリングの計算)といった状況がモデル化されます。 PINWHEELスケジューリング問題にマッピングすることで、すべてのアームの報酬と遅延に関する事前の知識により、ランダム化された指数時間仮説が偽でない限り、累積報酬を最適化する問題は擬似多項式時間アルゴリズム(アーム数)を含まないことを示した。 その後、利用可能なアームを最も高い報酬で演奏する単純な欲求アルゴリズムは、漸近的に$(1-1/e)$Optimicalであることを示す。 報酬が不明な場合、この不適切性による武器の自由探索を生かし、greedyアルゴリズムに対して$c \log T + o(\log T)$累積後悔を持つ UCB ベースのアルゴリズムを設計する。 最後に、全ての遅延が等しくなると、問題は、$c' \log T+ \omega(\log T)$の低い境界を持つ Combinatorial Semi-banditsに還元される。

関連論文リスト

• A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
  我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。 誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。
  論文  参考訳（メタデータ） (2024-09-08T12:19:12Z)
• Replicability is Asymptotically Free in Multi-armed Bandits [45.729105054410745]
  この仕事の動機は、再現可能な機械学習の需要の増加にある。 特に、高い確率で、アルゴリズムのアクション列がデータセットに固有のランダム性の影響を受けないように、複製可能なアルゴリズムを考える。
  論文  参考訳（メタデータ） (2024-02-12T03:31:34Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Adversarial Sleeping Bandit Problems with Multiple Plays: Algorithm and Ranking Application [7.0717496233701365]
  本稿では,オンラインレコメンデーションシステムのコンテキストにおいて,複数のプレイの問題で睡眠帯域を効率的に解決するアルゴリズムを提案する。 提案アルゴリズムは、単腕選択のための睡眠帯域幅アルゴリズムを拡張し、$bigO(kN2sqrtTlog T)$で理論的性能を達成することを保証している。
  論文  参考訳（メタデータ） (2023-07-27T00:11:59Z)
• Continuous Time Bandits With Sampling Costs [17.412117389855222]
  連続時間マルチアームバンディット問題 (CTMAB) を考えると, 学習者は任意の間隔で何回でもアームをサンプリングし, サンプルからランダムな報酬を得ることができる。 サンプリング周波数の関数として、大きな報酬を得ることとサンプリングコストをもたらすことにはトレードオフがある。 目的は後悔を最小限に抑える学習アルゴリズムを設計することであり、これはオラクルのポリシーと学習アルゴリズムの報酬の差として定義される。
  論文  参考訳（メタデータ） (2021-07-12T10:00:35Z)
• 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)
• Adaptive Algorithms for Multi-armed Bandit with Composite and Anonymous Feedback [32.62857394584907]
  複合および匿名フィードバックによるマルチアームバンディット(MAB)問題を研究する。 本稿では,逆の場合と非逆の場合の適応アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-12-13T12:25:41Z)

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

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