論文の概要: Online Nonsubmodular Optimization with Delayed Feedback in the Bandit Setting
- arxiv url: http://arxiv.org/abs/2508.00523v1
- Date: Fri, 01 Aug 2025 11:00:19 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-08-04 18:08:53.843637
- Title: Online Nonsubmodular Optimization with Delayed Feedback in the Bandit Setting
- Title（参考訳）: 帯域設定における遅延フィードバックを用いたオンライン非モジュラー最適化
- Authors: Sifan Yang, Yuanyu Wan, Lijun Zhang,
- Abstract要約: 帯域幅設定における遅延フィードバックによるオンライン非モジュール最適化について検討する。
本稿では,一点勾配推定器を用いた新しいDBGD-NF法を提案する。
また,ブロック更新機構を用いてDBGD-NFを拡張し,遅延と帯域幅フィードバックの結合効果を分離する。
- 参考スコア（独自算出の注目度）: 22.208290858529672
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate the online nonsubmodular optimization with delayed feedback in the bandit setting, where the loss function is $\alpha$-weakly DR-submodular and $\beta$-weakly DR-supermodular. Previous work has established an $(\alpha,\beta)$-regret bound of $\mathcal{O}(nd^{1/3}T^{2/3})$, where $n$ is the dimensionality and $d$ is the maximum delay. However, its regret bound relies on the maximum delay and is thus sensitive to irregular delays. Additionally, it couples the effects of delays and bandit feedback as its bound is the product of the delay term and the $\mathcal{O}(nT^{2/3})$ regret bound in the bandit setting without delayed feedback. In this paper, we develop two algorithms to address these limitations, respectively. Firstly, we propose a novel method, namely DBGD-NF, which employs the one-point gradient estimator and utilizes all the available estimated gradients in each round to update the decision. It achieves a better $\mathcal{O}(n\bar{d}^{1/3}T^{2/3})$ regret bound, which is relevant to the average delay $\bar{d} = \frac{1}{T}\sum_{t=1}^T d_t\leq d$. Secondly, we extend DBGD-NF by employing a blocking update mechanism to decouple the joint effect of the delays and bandit feedback, which enjoys an $\mathcal{O}(n(T^{2/3} + \sqrt{dT}))$ regret bound. When $d = \mathcal{O}(T^{1/3})$, our regret bound matches the $\mathcal{O}(nT^{2/3})$ bound in the bandit setting without delayed feedback. Compared to our first $\mathcal{O}(n\bar{d}^{1/3}T^{2/3})$ bound, it is more advantageous when the maximum delay $d = o(\bar{d}^{2/3}T^{1/3})$. Finally, we conduct experiments on structured sparse learning to demonstrate the superiority of our methods.
- Abstract（参考訳）: 損失関数は$\alpha$-weakly DR-submodularと$\beta$-weakly DR-supermodularである。
以前の研究は$(\alpha,\beta)$-regret bound of $\mathcal{O}(nd^{1/3}T^{2/3})$を確立した。
しかし、その後悔は最大の遅延に依存するため、不規則な遅延に敏感である。
さらに、遅延項の積が遅延項の積であることと、遅延フィードバックを伴わない帯域設定において後悔の意を表す$\mathcal{O}(nT^{2/3})が成立していることから、遅延とバンドイットフィードバックの効果を区別する。
本稿では,これらの制約に対処する2つのアルゴリズムについて述べる。
まず,DBGD-NFという1点勾配推定器を用い,各ラウンドで利用可能な勾配を全て利用して決定を更新する手法を提案する。
これは平均遅延 $\bar{d} = \frac{1}{T}\sum_{t=1}^T d_t\leq d$ に関係している。
次に,DBGD-NFをブロック更新機構を用いて拡張し,遅延と盗聴フィードバックの連関効果を分離し,$\mathcal{O}(n(T^{2/3} + \sqrt{dT})$ regret boundを満足する。
d = \mathcal{O}(T^{1/3})$ のとき、我々の後悔の限界は、遅延したフィードバックを伴わずに、バンドレート設定で$\mathcal{O}(nT^{2/3})$ の値と一致する。
最初の $\mathcal{O}(n\bar{d}^{1/3}T^{2/3})$bound と比較すると、最大遅延 $d = o(\bar{d}^{2/3}T^{1/3})$ がより有利である。
最後に,本手法の優位性を示すため,構造化スパース学習の実験を行った。
関連論文リスト
- Reinforcement Learning from Adversarial Preferences in Tabular MDPs [62.73758165845971]
我々は,敵対的嗜好を持つエピソードマルコフ決定プロセス(MDP)の新たな枠組みを導入する。
PbMDP では、標準的なエピソード MDP とは異なり、学習者は2つの候補アーム間の好みを観察する。
我々は、既知遷移の下で、T2/3$という残差境界を達成するアルゴリズムを開発する。
論文 参考訳（メタデータ） (2025-07-15T20:19:32Z) - Capacity-Constrained Online Learning with Delays: Scheduling Frameworks and Regret Trade-offs [60.7808741738461]
我々は,遅れたフィードバックのために,過去のラウンドを同時に追跡できる回数を制限する,斬新な「透明さ」の下で,難解な遅延を伴うオンライン学習について研究する。
我々のアルゴリズムは、全てのキャパシティレベルにおいてミニマックスの後悔を達成し、性能は最適以下のキャパシティで優雅に低下する。
論文 参考訳（メタデータ） (2025-03-25T17:20:39Z) - 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) - Nearly Minimax Optimal Submodular Maximization with Bandit Feedback [12.28389976959093]
我々は、最大$f(S_*)$と$|S_*| = k$との近似について学習者の後悔を最小限に抑える。
この作業では、$tildeOmega(min_L le k(T2/3 + sqrtn choose k - LT)$ のようにスケールするこの設定に対して、最初の minimax lower bound を確立する。
わずかに制限されたアルゴリズムクラスに対して、$tildeOmega(min_L)の強い後悔の低い境界を証明する。
論文 参考訳（メタデータ） (2023-10-27T20:19:03Z) - Borda Regret Minimization for Generalized Linear Dueling Bandits [65.09919504862496]
本稿では,ボルダスコアが最も高い項目を識別することを目的とした,デュエルバンディットに対するボルダ後悔最小化問題について検討する。
本稿では,多くの既存モデルをカバーする一般化線形デュエルバンドモデルのリッチクラスを提案する。
我々のアルゴリズムは$tildeO(d2/3 T2/3)$ regretを達成し、これも最適である。
論文 参考訳（メタデータ） (2023-03-15T17:59:27Z) - Smooth Non-Stationary Bandits [49.19728527803684]
本研究では、各アームの平均報酬シーケンスを$beta$-H"older関数に埋め込むことができる非定常包帯問題について検討する。
スムース(つまり$betage 2$)と非スムース(つまり$beta=1$)との最初の分離は、$tilde O(k4/5 T3/5)$ regret on any $k$-armed, $2-H"older instanceでポリシーを提示することで示します。
論文 参考訳（メタデータ） (2023-01-29T06:03:20Z) - A Best-of-Both-Worlds Algorithm for Bandits with Delayed Feedback [25.68113242132723]
本稿では,Zimmert と Seldin [2020] のアルゴリズムを,フィードバックの遅れによる逆方向の多重武装バンディットに対して修正したチューニングを行う。
我々は,時間的遅れのある設定において,ほぼ最適の相反的後悔の保証を同時に達成する。
また,任意の遅延の場合に対するアルゴリズムの拡張も提案する。
論文 参考訳（メタデータ） (2022-06-29T20:49:45Z) - Projection-free Online Learning with Arbitrary Delays [38.13351554274417]
我々は、オンラインFrank-Wolfe (OFW)アルゴリズムとオンラインスムーズプロジェクションフリー (OSPF) アルゴリズムを遅延設定に一般化する。
新たな解析により,OW と OSPF は非遅延環境ではOW と OSPF と同じ後悔を味わうことが明らかとなった。
論文 参考訳（メタデータ） (2022-04-11T09:26:24Z) - On Submodular Contextual Bandits [92.45432756301231]
作用が基底集合の部分集合であり、平均報酬が未知の単調部分モジュラ函数によってモデル化されるような文脈的包帯の問題を考える。
Inverse Gap Weighting 戦略により,提案アルゴリズムは推定関数の局所的最適度を効率よくランダム化することを示す。
論文 参考訳（メタデータ） (2021-12-03T21:42:33Z) - Scale-Free Adversarial Multi-Armed Bandit with Arbitrary Feedback Delays [21.94728545221709]
制限のないフィードバック遅延を伴うMAB(Scale-Free Adversarial Multi Armed Bandit)問題を考える。
textttSFBankerは$mathcal O(sqrtK(D+T)L)cdot rm polylog(T, L)$ total regret, where $T$ is the total number of steps, $D$ is the total feedback delay。
論文 参考訳（メタデータ） (2021-10-26T04:06:51Z) - Adapting to Delays and Data in Adversarial Multi-Armed Bandits [7.310043452300736]
決定時に利用可能な情報のみを用いてステップサイズを調整するExp3アルゴリズムの変種を分析する。
我々は、観測された(最悪の場合ではなく)遅延や損失のシーケンスに適応する後悔の保証を得る。
論文 参考訳（メタデータ） (2020-10-12T20:53:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。