論文の概要: Bounded Memory Adversarial Bandits with Composite Anonymous Delayed Feedback

• arxiv url: http://arxiv.org/abs/2204.12764v1
• Date: Wed, 27 Apr 2022 08:32:35 GMT
• ステータス: 処理完了
• システム内更新日: 2022-04-28 13:10:22.176068
• Title: Bounded Memory Adversarial Bandits with Composite Anonymous Delayed Feedback
• Title（参考訳）: 複合匿名遅延フィードバックを用いた境界メモリ逆バンディット
• Authors: Zongqi Wan, Xiaoming Sun, Jialin Zhang
• Abstract要約: 複合匿名遅延フィードバックを用いた対向帯域幅問題について検討した。 この設定では、アクションの損失は$d$コンポーネントに分割され、アクションが選択された後に連続してラウンドが分散される。 損失シーケンスがメモリ境界である場合でも,$Omega(T)$疑似後悔が発生することを示す。
• 参考スコア（独自算出の注目度）: 10.179145161000315
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the adversarial bandit problem with composite anonymous delayed feedback. In this setting, losses of an action are split into $d$ components, spreading over consecutive rounds after the action is chosen. And in each round, the algorithm observes the aggregation of losses that come from the latest $d$ rounds. Previous works focus on oblivious adversarial setting, while we investigate the harder non-oblivious setting. We show non-oblivious setting incurs $\Omega(T)$ pseudo regret even when the loss sequence is bounded memory. However, we propose a wrapper algorithm which enjoys $o(T)$ policy regret on many adversarial bandit problems with the assumption that the loss sequence is bounded memory. Especially, for $K$-armed bandit and bandit convex optimization, we have $\mathcal{O}(T^{2/3})$ policy regret bound. We also prove a matching lower bound for $K$-armed bandit. Our lower bound works even when the loss sequence is oblivious but the delay is non-oblivious. It answers the open problem proposed in \cite{wang2021adaptive}, showing that non-oblivious delay is enough to incur $\tilde{\Omega}(T^{2/3})$ regret.
• Abstract（参考訳）: 複合匿名遅延フィードバックによる逆バンディット問題について検討した。 この設定では、アクションの損失は$d$コンポーネントに分割され、アクションが選択された後に連続するラウンドに展開される。 そして各ラウンドにおいて、アルゴリズムは最新の$d$ラウンドからの損失の集計を観察する。 先行研究は、難易度の高い敵の設定に焦点をあて、難易度の高い非公開設定を調査する。 損失シーケンスがメモリ境界である場合でも、非公開設定が$\Omega(T)$疑似後悔を引き起こすことを示す。 しかし,損失シーケンスがメモリ境界であるという仮定で,多くの逆バンディット問題に対して,$o(T)$ポリシーを後悔するラッパーアルゴリズムを提案する。 特に、$k$-armed banditとbandit convexの最適化には、$\mathcal{o}(t^{2/3})$ policy regret boundがあります。 また、$K$-armed banditの一致した下限も証明する。 我々の下限は、損失シーケンスが不明確だが遅延は未公表である場合でも機能する。 これは \cite{wang2021adaptive} で提案された開問題に答え、非公約遅延が$\tilde{\Omega}(T^{2/3})$ regret を発生させるのに十分であることを示す。

関連論文リスト

• Adversarial Combinatorial Bandits with Switching Costs [55.2480439325792]
  本稿では,各ラウンドで選択したアームのスイッチに対して,切替コストが$lambda$の逆帯域問題について検討する。 ミニマックスの後悔とそれにアプローチするための設計アルゴリズムの限界を低くする。
  論文  参考訳（メタデータ） (2024-04-02T12:15:37Z)
• 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)
• Complete Policy Regret Bounds for Tallying Bandits [51.039677652803675]
  政策後悔は、適応的な敵に対してオンライン学習アルゴリズムのパフォーマンスを測定するという、よく確立された概念である。 我々は,不完全な政策後悔を効果的に最小化できる敵の制限について検討する。 我々は、$tildemathcalO(mKsqrtT)$の完全なポリシーを後悔するアルゴリズムを提供し、$tildemathcalO$表記は対数要素だけを隠す。
  論文  参考訳（メタデータ） (2022-04-24T03:10:27Z)
• Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits [99.86860277006318]
  本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。 Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。 この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
  論文  参考訳（メタデータ） (2022-02-12T21:55:44Z)
• Non-Stationary Dueling Bandits [8.298716599039501]
  我々は、非定常デュエルバンディット問題をK$アームで研究し、タイムホライズメント$T$は、固定セグメント$M$からなる。 蓄積した後悔を最小限に抑えるため、学習者は各定常セグメントのコンドルチェットの勝者をできるだけ頻繁に選ぶ必要がある。 我々は、M$やT$の知識を必要とせず、非定常ケースに対する後悔の意を示す。
  論文  参考訳（メタデータ） (2022-02-02T09:57:35Z)
• No Discounted-Regret Learning in Adversarial Bandits with Delays [40.670563413892154]
  アルゴリズムが「割引なし」の場合、予想される遊びの割引エルゴジック分布が粗相関平衡(CCE)の集合に収束することを示した。 ゼロサムゲームでは、Nash平衡のセットに収束する割引エルゴディック平均のプレイには、ディスカウントレグレットが十分ではないことを示します。
  論文  参考訳（メタデータ） (2021-03-08T05:15:31Z)
• Adversarial Dueling Bandits [85.14061196945599]
  本稿では,反逆デュエルバンドにおける後悔の問題を紹介する。 学習者は、繰り返し一対のアイテムを選択し、このペアに対する相対的な二項利得フィードバックのみを観察しなければならない。 我々の主な成果は、EmphBorda-winnerの1組の$K$アイテムと比較して、T$ラウンド後悔するアルゴリズムです。
  論文  参考訳（メタデータ） (2020-10-27T19:09:08Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)

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

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