論文の概要: Sleeping Combinatorial Bandits

• arxiv url: http://arxiv.org/abs/2106.01624v1
• Date: Thu, 3 Jun 2021 06:49:44 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-04 16:05:03.393545
• Title: Sleeping Combinatorial Bandits
• Title（参考訳）: Sleeping Combinatorial Bandits
• Authors: Kumar Abhishek, Ganesh Ghalme, Sujit Gujar, Yadati Narahari
• Abstract要約: 睡眠帯域設定においてよく知られたCUCBアルゴリズムを適用し,それをCSUCBと呼ぶ。 穏やかな条件下では、CSUCBアルゴリズムが$O(sqrtT log (T)$ instance-dependent regret guaranteeを達成することを証明します。 我々の結果は極めて一般的なものであり、非付加的な報酬関数、揮発性アームの可用性、引くべきベースアームの変動数など、実用的な応用によって生じる一般的な環境下で維持されます。
• 参考スコア（独自算出の注目度）: 15.004764451770441
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: In this paper, we study an interesting combination of sleeping and combinatorial stochastic bandits. In the mixed model studied here, at each discrete time instant, an arbitrary \emph{availability set} is generated from a fixed set of \emph{base} arms. An algorithm can select a subset of arms from the \emph{availability set} (sleeping bandits) and receive the corresponding reward along with semi-bandit feedback (combinatorial bandits). We adapt the well-known CUCB algorithm in the sleeping combinatorial bandits setting and refer to it as \CSUCB. We prove -- under mild smoothness conditions -- that the \CSUCB\ algorithm achieves an $O(\log (T))$ instance-dependent regret guarantee. We further prove that (i) when the range of the rewards is bounded, the regret guarantee of \CSUCB\ algorithm is $O(\sqrt{T \log (T)})$ and (ii) the instance-independent regret is $O(\sqrt[3]{T^2 \log(T)})$ in a general setting. Our results are quite general and hold under general environments -- such as non-additive reward functions, volatile arm availability, a variable number of base-arms to be pulled -- arising in practical applications. We validate the proven theoretical guarantees through experiments.
• Abstract（参考訳）: 本稿では,睡眠と複合確率バンディットの興味深い組み合わせについて検討する。 ここで研究した混合モデルでは、各離散時間インスタントに、任意の \emph{availability set} が固定された \emph{base} arms から生成される。 アルゴリズムは \emph{availability set} (sleeping bandits) からアームのサブセットを選択し、セミバンドフィードバック (combintorial bandits) とともに対応する報酬を受け取ることができる。 睡眠複合バンドレート設定においてよく知られたCUCBアルゴリズムを適用し,それを \CSUCB と呼ぶ。 我々は、緩やかな滑らかさ条件の下で、 \CSUCB\アルゴリズムが$O(\log (T))$インスタンス依存後悔保証を達成することを証明した。 さらに、(i)報酬の範囲が有界であるとき、 \CSUCB\アルゴリズムの後悔保証は$O(\sqrt{T \log (T)})$であり、(ii)インスタンスに依存しない後悔は$O(\sqrt[3]{T^2 \log(T)})$である。 私たちの結果は極めて一般的で、非加減報酬関数、揮発性アームアベイラビリティ、プルするベースアームの可変数といった一般的な環境下で保持されています。 実証された理論的保証を実験により検証する。

関連論文リスト

• Fast UCB-type algorithms for stochastic bandits with heavy and super heavy symmetric noise [45.60098988395789]
  マルチアームバンディットのためのUCB型アルゴリズムを構築するための新しいアルゴリズムを提案する。 報酬の対称雑音の場合、$O(log TsqrtKTlog T)$ regret bound を $Oleft の代わりに達成できることを示す。
  論文  参考訳（メタデータ） (2024-02-10T22:38:21Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Combinatorial Neural Bandits [10.463365653675694]
  学習エージェントが各ラウンドでアームのサブセットを選択し、そのスコアに応じて選択したアームのフィードバックを受け取るというコンテキスト的盗聴問題を考える。 アルゴリズムを提案する: Combinatorial Neural UCB(textttCN-UCB)と Combinatorial Thompson Sampling(textttCN-TS$)。
  論文  参考訳（メタデータ） (2023-05-31T23:27:58Z)
• Communication-Constrained Bandits under Additive Gaussian Noise [111.06688156723018]
  クライアントが学習者にコミュニケーション制約のあるフィードバックを提供する分散マルチアームバンディットについて検討する。 我々は、この下限を小さな加法係数にマッチさせるマルチフェーズ帯域幅アルゴリズム、$mathtUEtext-UCB++$を提案する。
  論文  参考訳（メタデータ） (2023-04-25T09:31:20Z)
• Optimal Algorithms for Latent Bandits with Cluster Structure [50.44722775727619]
  本稿では,複数のユーザが存在するクラスタ構造を持つ潜伏包帯問題と関連するマルチアーム包帯問題とを考察する。 本稿では,潜伏クラスタ構造を利用して$widetildeO(sqrt(mathsfM+mathsfN)mathsfTの最小限の後悔を提供するLATTICEを提案する。
  論文  参考訳（メタデータ） (2023-01-17T17:49:04Z)
• Contextual Combinatorial Volatile Bandits via Gaussian Processes [10.312968200748116]
  利用可能なベースアームのセットとそのコンテキストによるコンテキスト的バンディット問題を考える。 我々は,カーネル上信頼境界(O'CLOK-UCB)を用いた最適組合せ学習と最適化というアルゴリズムを提案する。 両アルゴリズムが従来のUTBベースのアルゴリズムを現実的な設定で大幅に上回っていることを実験的に示す。
  論文  参考訳（メタデータ） (2021-10-05T18:02:10Z)
• 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)
• 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)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)
• Improved Sleeping Bandits with Stochastic Actions Sets and Adversarial Rewards [59.559028338399855]
  我々は,行動セットと敵意の報酬を伴って睡眠中の盗賊の問題を考察する。 本稿では,EXP3にインスパイアされた新しい計算効率のよいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-04-14T00:41:26Z)

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

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