論文の概要: Stochastic Submodular Bandits with Delayed Composite Anonymous Bandit Feedback
- arxiv url: http://arxiv.org/abs/2303.13604v2
- Date: Wed, 22 Jan 2025 01:44:07 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-01-23 16:52:20.771736
- Title: Stochastic Submodular Bandits with Delayed Composite Anonymous Bandit Feedback
- Title（参考訳）: 複合匿名帯域フィードバックが遅れた確率的部分モジュラバンド
- Authors: Mohammad Pedramfar, Vaneet Aggarwal,
- Abstract要約: 本稿では,過度な(期待している)報酬と全帯域遅延フィードバックを伴うマルチアームバンドの問題について検討する。
遅延したフィードバックは過去のアクションからの報酬のコンポーネントで構成されており、サブコンポーネント間で未知の分割がある。
提案アルゴリズムは,合成匿名フィードバックの遅延により,他の全帯域アプローチより優れていることを示す。
- 参考スコア（独自算出の注目度）: 33.38582292895673
- License:
- Abstract: This paper investigates the problem of combinatorial multiarmed bandits with stochastic submodular (in expectation) rewards and full-bandit delayed feedback, where the delayed feedback is assumed to be composite and anonymous. In other words, the delayed feedback is composed of components of rewards from past actions, with unknown division among the sub-components. Three models of delayed feedback: bounded adversarial, stochastic independent, and stochastic conditionally independent are studied, and regret bounds are derived for each of the delay models. Ignoring the problem dependent parameters, we show that regret bound for all the delay models is $\tilde{O}(T^{2/3} + T^{1/3} \nu)$ for time horizon $T$, where $\nu$ is a delay parameter defined differently in the three cases, thus demonstrating an additive term in regret with delay in all the three delay models. The considered algorithm is demonstrated to outperform other full-bandit approaches with delayed composite anonymous feedback.
- Abstract（参考訳）: 本稿では,確率的部分モジュラー(期待される)報酬と全帯域遅延フィードバックとの組合せ型マルチアームバンドの問題について検討し,遅延フィードバックは複合的かつ匿名であると仮定する。
言い換えれば、遅延したフィードバックは過去の行動からの報酬の構成要素で構成されており、サブコンポーネント間で未知の分割がある。
遅延フィードバックの3つのモデル:有界逆数、確率独立性、確率独立性、および確率独立性について検討し、各遅延モデルに対して後悔境界を導出する。
問題依存パラメータを無視すると、全ての遅延モデルに対する後悔は$\tilde{O}(T^{2/3} + T^{1/3} \nu)$ for time horizon $T$, where $\nu$ is a delay parameters different in the three case, so demonstrated an additive term in regret in delay in all three delay model。
提案アルゴリズムは,合成匿名フィードバックの遅延により,他の全帯域アプローチより優れていることを示す。
関連論文リスト
- Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling [73.5602474095954]
マルコフサンプリングの遅延更新による近似スキームの非漸近的性能について検討した。
我々の理論的な発見は、幅広いアルゴリズムの遅延の有限時間効果に光を当てた。
論文 参考訳（メタデータ） (2024-02-19T03:08:02Z) - 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) - Adversarial Bandits with Multi-User Delayed Feedback: Theory and
Application [17.64363983613468]
我々は,マルチユーザ遅延フィードバックを用いた逆MAB問題を定式化し,修正されたEXP3アルゴリズム MUD-EXP3 を設計する。
本稿では,複数のユーザからの遅延フィードバック結果について考察し,内部分布に制限を加えることなく検討する。
論文 参考訳（メタデータ） (2023-10-17T12:08:15Z) - A Best-of-both-worlds Algorithm for Bandits with Delayed Feedback with Robustness to Excessive Delays [24.998122268199797]
本稿では,フィードバックが可変に遅延するバンディットのためのベスト・オブ・ボス・ワールドス・アルゴリズムを提案する。
我々のアルゴリズムは任意の過剰な遅延を許容し、$T$をオーダーすることができる。
論文 参考訳（メタデータ） (2023-08-21T12:17:40Z) - A Unified Analysis of Nonstochastic Delayed Feedback for Combinatorial
Semi-Bandits, Linear Bandits, and MDPs [18.199326045904996]
オンライン学習のためのFTRL(Follow The Regularized Leader)の新たな分析結果を得た。
我々の新しい後悔分解は、FTRLが正則化器のヘシアンに穏やかな仮定の下で複数のラウンドで安定であることを示している。
論文 参考訳（メタデータ） (2023-05-15T13:21:50Z) - Online Nonsubmodular Minimization with Delayed Costs: From Full
Information to Bandit Feedback [98.7678704343537]
我々は,オンラインおよび近似的オンライン帯域勾配勾配アルゴリズムのいくつかの変種に対する後悔の保証を,特別な構造を持つ非部分モジュラ関数のクラスに焦点をあてる。
我々は,決定の選択と帰属費用の受け取りの遅れが無拘束である場合でも,エージェントの完全な情報と盗賊のフィードバック設定に対する後悔の限界を導出する。
論文 参考訳（メタデータ） (2022-05-15T08:27:12Z) - Stochastic Multi-Armed Bandits with Unrestricted Delay Distributions [54.25616645675032]
アルゴリズムが受信したフィードバックにランダムな遅延を伴うマルチアーマッド・バンドイット(MAB)問題について検討する。
報酬非依存の遅延設定は、報酬非依存の遅延設定と、報酬非依存の遅延設定に依存する可能性がある。
私たちの主な貢献は、それぞれの設定でほぼ最適に後悔するアルゴリズムです。
論文 参考訳（メタデータ） (2021-06-04T12:26:06Z) - Stochastic bandits with arm-dependent delays [102.63128271054741]
我々は、単純なUCBベースのアルゴリズムであるPatentBanditsを提案する。
問題に依存しない境界も問題に依存しない境界も、性能の低い境界も提供します。
論文 参考訳（メタデータ） (2020-06-18T12:13:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。