論文の概要: Improved Regret for Bandit Convex Optimization with Delayed Feedback
- arxiv url: http://arxiv.org/abs/2402.09152v2
- Date: Sun, 23 Jun 2024 15:12:02 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-26 02:01:18.153369
- Title: Improved Regret for Bandit Convex Optimization with Delayed Feedback
- Title（参考訳）: 遅延フィードバックによるバンド凸最適化のレグレットの改善
- Authors: Yuanyu Wan, Chang Yao, Mingli Song, Lijun Zhang,
- Abstract要約: 遅延フィードバックを伴うバンド凸最適化(BCO)。
我々は,新しいアルゴリズムを開発し,一般にO(sqrtnT3/4+sqrtdT)$の後悔境界を満足していることを証明する。
提案アルゴリズムは,強い凸関数に対して$O((nT)2/3log/3T+dlog T)$に制限された後悔を改善することができることを示す。
- 参考スコア（独自算出の注目度）: 50.46856739179311
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate bandit convex optimization (BCO) with delayed feedback, where only the loss value of the action is revealed under an arbitrary delay. Let $n,T,\bar{d}$ denote the dimensionality, time horizon, and average delay, respectively. Previous studies have achieved an $O(\sqrt{n}T^{3/4}+(n\bar{d})^{1/3}T^{2/3})$ regret bound for this problem, whose delay-independent part matches the regret of the classical non-delayed bandit gradient descent algorithm. However, there is a large gap between its delay-dependent part, i.e., $O((n\bar{d})^{1/3}T^{2/3})$, and an existing $\Omega(\sqrt{\bar{d}T})$ lower bound. In this paper, we illustrate that this gap can be filled in the worst case, where $\bar{d}$ is very close to the maximum delay $d$. Specifically, we first develop a novel algorithm, and prove that it enjoys a regret bound of $O(\sqrt{n}T^{3/4}+\sqrt{dT})$ in general. Compared with the previous result, our regret bound is better for $d=O((n\bar{d})^{2/3}T^{1/3})$, and the delay-dependent part is tight in the worst case. The primary idea is to decouple the joint effect of the delays and the bandit feedback on the regret by carefully incorporating the delayed bandit feedback with a blocking update mechanism. Furthermore, we show that the proposed algorithm can improve the regret bound to $O((nT)^{2/3}\log^{1/3}T+d\log T)$ for strongly convex functions. Finally, if the action sets are unconstrained, we demonstrate that it can be simply extended to achieve an $O(n\sqrt{T\log T}+d\log T)$ regret bound for strongly convex and smooth functions.
- Abstract（参考訳）: 遅延フィードバックを伴う帯域幅凸最適化(BCO)について検討し,任意の遅延の下で動作の損失値のみを明らかにする。
n,T,\bar{d}$ はそれぞれ次元、時間的地平線、平均遅延を表す。
従来の研究は、この問題に対して$O(\sqrt{n}T^{3/4}+(n\bar{d})^{1/3}T^{2/3})$ regret boundを達成した。
しかし、その遅延依存部分、すなわち$O((n\bar{d})^{1/3}T^{2/3})$と既存の$Omega(\sqrt{\bar{d}T})$下界との間には大きなギャップがある。
本稿では、このギャップを$\bar{d}$が最大遅延$d$に非常に近い最悪のケースで埋めることができることを示す。
具体的には、まず新しいアルゴリズムを開発し、一般に$O(\sqrt{n}T^{3/4}+\sqrt{dT})$の後悔境界を楽しんでいることを証明する。
前の結果と比較すると、我々の後悔境界は$d=O((n\bar{d})^{2/3}T^{1/3})$の方が良い。
一番の考え方は、遅延の連関効果と、遅延の連関フィードバックをブロック更新機構に注意深く組み込むことで、後悔に対する包括フィードバックとを分離することである。
さらに,提案アルゴリズムは,強い凸関数に対して$O((nT)^{2/3}\log^{1/3}T+d\log T)$に制限された後悔を改善することができることを示す。
最後に、作用集合が非制約であれば、強凸かつ滑らかな函数に対して、$O(n\sqrt{T\log T}+d\log T)$ regret bound を達成するために単純に拡張できることが示される。
関連論文リスト
- Adversarial Combinatorial Bandits with Switching Costs [55.2480439325792]
本稿では,各ラウンドで選択したアームのスイッチに対して,切替コストが$lambda$の逆帯域問題について検討する。
ミニマックスの後悔とそれにアプローチするための設計アルゴリズムの限界を低くする。
論文 参考訳（メタデータ） (2024-04-02T12:15:37Z) - Non-stationary Online Convex Optimization with Arbitrary Delays [50.46856739179311]
本稿では,非定常環境における遅延オンライン凸最適化(OCO)について検討する。
まず, 遅延勾配の勾配降下ステップを, 到着順に応じて行う単純なアルゴリズム, DOGDを提案する。
DOGDが達成した動的後悔境界を$O(sqrtbardT(P_T+1))$に削減する改良アルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-05-20T07:54:07Z) - Improved High-Probability Regret for Adversarial Bandits with
Time-Varying Feedback Graphs [62.52390282012508]
我々は、T$ラウンド以上の時間変化フィードバックグラフを持つ、敵対的な$K$武器付きバンディットに対する高い確率的後悔境界について検討する。
提案アルゴリズムは,高い確率で最適に後悔する$widetildemathcalO((sum_t=1Talpha_t)1/2+max_tin[T]alpha_t]$を達成するアルゴリズムを開発した。
また,弱可観測グラフに対する最適高確率残差を求めるアルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-10-04T04:36:15Z) - A Best-of-Both-Worlds Algorithm for Bandits with Delayed Feedback [25.68113242132723]
本稿では,Zimmert と Seldin [2020] のアルゴリズムを,フィードバックの遅れによる逆方向の多重武装バンディットに対して修正したチューニングを行う。
我々は,時間的遅れのある設定において,ほぼ最適の相反的後悔の保証を同時に達成する。
また,任意の遅延の場合に対するアルゴリズムの拡張も提案する。
論文 参考訳（メタデータ） (2022-06-29T20:49:45Z) - 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) - 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) - Online Convex Optimization with Continuous Switching Constraint [78.25064451417082]
連続的なスイッチング制約を伴うオンライン凸最適化の問題を紹介する。
強い凸関数の場合、後悔境界は$O(log T)$ for $S=Omega(log T)$、$O(minT/exp(S)+S,T)$ for $S=O(log T)$に改善できることを示す。
論文 参考訳（メタデータ） (2021-03-21T11:43: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) - Adapting to Delays and Data in Adversarial Multi-Armed Bandits [7.310043452300736]
決定時に利用可能な情報のみを用いてステップサイズを調整するExp3アルゴリズムの変種を分析する。
我々は、観測された(最悪の場合ではなく)遅延や損失のシーケンスに適応する後悔の保証を得る。
論文 参考訳（メタデータ） (2020-10-12T20:53:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。