論文の概要: Improved Regret for Bandit Convex Optimization with Delayed Feedback
- arxiv url: http://arxiv.org/abs/2402.09152v1
- Date: Wed, 14 Feb 2024 13:08:26 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-15 15:35:13.529127
- Title: Improved Regret for Bandit Convex Optimization with Delayed Feedback
- Title（参考訳）: 遅延フィードバックによるバンド凸最適化のレグレットの改善
- Authors: Yuanyu Wan and Chang Yao and Mingli Song and Lijun Zhang
- Abstract要約: 本稿では,遅延した帯域幅のフィードバックをブロッキング更新機構によって注意深く活用する,新たなアルゴリズムを開発した。
制約のない作用集合を持つ特別な場合、それは強凸かつ滑らかな函数に対して$O(sqrtTlog T+dlog T)$の後悔境界を達成するために単純に拡張することができる。
- 参考スコア（独自算出の注目度）: 55.13328423837296
- 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.
Previous studies have established a regret bound of $O(T^{3/4}+d^{1/3}T^{2/3})$
for this problem, where $d$ is the maximum delay, by simply feeding delayed
loss values to the classical bandit gradient descent (BGD) algorithm. In this
paper, we develop a novel algorithm to enhance the regret, which carefully
exploits the delayed bandit feedback via a blocking update mechanism. Our
analysis first reveals that the proposed algorithm can decouple the joint
effect of the delays and bandit feedback on the regret, and improve the regret
bound to $O(T^{3/4}+\sqrt{dT})$ for convex functions. Compared with the
previous result, our regret matches the $O(T^{3/4})$ regret of BGD in the
non-delayed setting for a larger amount of delay, i.e., $d=O(\sqrt{T})$,
instead of $d=O(T^{1/4})$. Furthermore, we consider the case with strongly
convex functions, and prove that the proposed algorithm can enjoy a better
regret bound of $O(T^{2/3}\log^{1/3}T+d\log T)$. Finally, we show that in a
special case with unconstrained action sets, it can be simply extended to
achieve a regret bound of $O(\sqrt{T\log T}+d\log T)$ for strongly convex and
smooth functions.
- Abstract（参考訳）: 遅延フィードバックを伴う帯域幅凸最適化(BCO)について検討し,任意の遅延の下で動作の損失値のみを明らかにする。
これまでの研究では、古典的帯域勾配勾配(BGD)アルゴリズムに遅延損失値を単純に供給することで、$d$が最大遅延である問題に対して$O(T^{3/4}+d^{1/3}T^{2/3})の後悔境界を確立している。
本稿では,ブロッカー更新機構により遅延したバンディットフィードバックを慎重に活用し,後悔感を高める新しいアルゴリズムを開発した。
解析の結果,提案アルゴリズムは遅延の結合効果と後悔に対する包括的フィードバックを分離し,凸関数に対して$O(T^{3/4}+\sqrt{dT})$に制限された後悔を改善することができることがわかった。
以前の結果と比較すると、我々の後悔は、BGD の非遅延設定である $d=O(\sqrt{T})$ に一致し、$d=O(T^{1/4})$ の代わりに $d=O(T^{1/4})$ となる。
さらに、凸関数が強い場合を考え、提案アルゴリズムが$O(T^{2/3}\log^{1/3}T+d\log T)$のより良い後悔境界を享受できることを示す。
最後に、制約のない作用集合を持つ特別な場合において、強凸かつ滑らかな函数に対して$O(\sqrt{T\log T}+d\log T)$の後悔境界を達成するように簡単に拡張できることを示す。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。