論文の概要: Adversarial Combinatorial Bandits with Switching Costs

• arxiv url: http://arxiv.org/abs/2404.01883v1
• Date: Tue, 2 Apr 2024 12:15:37 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-03 16:38:36.488157
• Title: Adversarial Combinatorial Bandits with Switching Costs
• Title（参考訳）: スイッチングコストを考慮したアベレーティブバンド
• Authors: Yanyan Dong, Vincent Y. F. Tan,
• Abstract要約: 本稿では,各ラウンドで選択したアームのスイッチに対して,切替コストが$lambda$の逆帯域問題について検討する。 ミニマックスの後悔とそれにアプローチするための設計アルゴリズムの限界を低くする。
• 参考スコア（独自算出の注目度）: 55.2480439325792
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the problem of adversarial combinatorial bandit with a switching cost $\lambda$ for a switch of each selected arm in each round, considering both the bandit feedback and semi-bandit feedback settings. In the oblivious adversarial case with $K$ base arms and time horizon $T$, we derive lower bounds for the minimax regret and design algorithms to approach them. To prove these lower bounds, we design stochastic loss sequences for both feedback settings, building on an idea from previous work in Dekel et al. (2014). The lower bound for bandit feedback is $ \tilde{\Omega}\big( (\lambda K)^{\frac{1}{3}} (TI)^{\frac{2}{3}}\big)$ while that for semi-bandit feedback is $ \tilde{\Omega}\big( (\lambda K I)^{\frac{1}{3}} T^{\frac{2}{3}}\big)$ where $I$ is the number of base arms in the combinatorial arm played in each round. To approach these lower bounds, we design algorithms that operate in batches by dividing the time horizon into batches to restrict the number of switches between actions. For the bandit feedback setting, where only the total loss of the combinatorial arm is observed, we introduce the Batched-Exp2 algorithm which achieves a regret upper bound of $\tilde{O}\big((\lambda K)^{\frac{1}{3}}T^{\frac{2}{3}}I^{\frac{4}{3}}\big)$ as $T$ tends to infinity. In the semi-bandit feedback setting, where all losses for the combinatorial arm are observed, we propose the Batched-BROAD algorithm which achieves a regret upper bound of $\tilde{O}\big( (\lambda K)^{\frac{1}{3}} (TI)^{\frac{2}{3}}\big)$.
• Abstract（参考訳）: 本研究では,各ラウンドにおける各選択アームのスイッチングに対して,スイッチングコストが$\lambda$の対向組合せ帯域幅の問題について,バンド幅フィードバックと半帯域幅フィードバックの設定の両方を考慮して検討した。 基本アームが$K$、時間水平が$T$の曖昧な逆向きの場合、ミニマックスの後悔とそれにアプローチするための設計アルゴリズムの低い境界を導出する。 これらの下限を証明するため、Dekel et al (2014) の以前の研究から得られたアイデアに基づいて、両方のフィードバック設定に対する確率的損失列を設計する。 バンドイットフィードバックの低いバウンダリは$ \tilde{\Omega}\big( (\lambda K)^{\frac{1}{3}}\big)$であるが、半バンドイットフィードバックのバウンダリは$ \tilde{\Omega}\big( (\lambda K I)^{\frac{1}{3}}\big)$である。 これらの下位境界にアプローチするために、時間軸をバッチに分割してバッチ内で動作するアルゴリズムを設計し、アクション間のスイッチ数を制限する。 組合せアームの総損失のみが観測されるバンドイットフィードバック設定に対しては、$T$が無限大になる傾向にあるような、$\tilde{O}\big((\lambda K)^{\frac{1}{3}}T^{\frac{2}{3}}I^{\frac{4}{3}}\big)$の後悔の上界を達成するBatched-Exp2アルゴリズムを導入する。 組み合わせアームのすべての損失が観測される半帯域フィードバック設定では、Batched-BROADアルゴリズムが$\tilde{O}\big( (\lambda K)^{\frac{1}{3}} (TI)^{\frac{2}{3}}\big)$の償却上限を達成する。

関連論文リスト

• Adversarial Multi-dueling Bandits [0.4467766778351321]
  対戦型多段バンディットにおける後悔の問題について紹介する。 このような嗜好フィードバックから学習するための新しいアルゴリズム MiDEX (Multi Dueling EXP3) を導入する。
  論文  参考訳（メタデータ） (2024-06-18T10:28:12Z)
• Improved Regret for Bandit Convex Optimization with Delayed Feedback [50.46856739179311]
  遅延フィードバックを伴うバンド凸最適化(BCO)。 我々は,新しいアルゴリズムを開発し,一般にO(sqrtnT3/4+sqrtdT)$の後悔境界を満足していることを証明する。 提案アルゴリズムは,強い凸関数に対して$O((nT)2/3log/3T+dlog T)$に制限された後悔を改善することができることを示す。
  論文  参考訳（メタデータ） (2024-02-14T13:08:26Z)
• Borda Regret Minimization for Generalized Linear Dueling Bandits [65.09919504862496]
  本稿では,ボルダスコアが最も高い項目を識別することを目的とした,デュエルバンディットに対するボルダ後悔最小化問題について検討する。 本稿では,多くの既存モデルをカバーする一般化線形デュエルバンドモデルのリッチクラスを提案する。 我々のアルゴリズムは$tildeO(d2/3 T2/3)$ regretを達成し、これも最適である。
  論文  参考訳（メタデータ） (2023-03-15T17:59:27Z)
• Better Best of Both Worlds Bounds for Bandits with Switching Costs [37.71741656687868]
  本稿では,2021年にRouryer,Seldin,Cesa-Bianchiらにより,スイッチングコストを伴うバンディットのベスト・オブ・ザ・ワールドス・アルゴリズムについて検討した。 本稿では, 極小最小の最小残差を$mathcalO(T2/3)$で同時に達成する, 驚くほど単純かつ効果的に導入する。
  論文  参考訳（メタデータ） (2022-06-07T08:22:56Z)
• Rotting Infinitely Many-armed Bandits [33.26370721280417]
  我々は$Omega(maxvarrho2/3T,sqrtT)$ worst-case regret lower bound ここで$T$は地平線時間であることを示す。 適応 UCB インデックスと適応しきい値を用いて $varrho$ の値を知らないアルゴリズムを実現することができる。
  論文  参考訳（メタデータ） (2022-01-31T03:07:17Z)
• 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)
• An Algorithm for Stochastic and Adversarial Bandits with Switching Costs [10.549307055348596]
  そこで本研究では,マルチアームバンディットのスイッチングコストを考慮したアルゴリズムを提案し,そのアルゴリズムがアームを切り替える度に$lambda$を支払う。 私たちのアルゴリズムは、Zimmert and Seldin(2021)のTsallis-INFアルゴリズムの適応に基づいています。
  論文  参考訳（メタデータ） (2021-02-19T11:03:51Z)
• 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 Dueling Bandits [85.14061196945599]
  本稿では,反逆デュエルバンドにおける後悔の問題を紹介する。 学習者は、繰り返し一対のアイテムを選択し、このペアに対する相対的な二項利得フィードバックのみを観察しなければならない。 我々の主な成果は、EmphBorda-winnerの1組の$K$アイテムと比較して、T$ラウンド後悔するアルゴリズムです。
  論文  参考訳（メタデータ） (2020-10-27T19:09:08Z)

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

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