論文の概要: 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)$の後悔境界を達成するように簡単に拡張できることを示す。
関連論文リスト
- Non-stationary Online Convex Optimization with Arbitrary Delays [55.13328423837296]
本稿では,非定常環境における遅延オンライン凸最適化(OCO)について検討する。
まず, 遅延勾配の勾配降下ステップを, 到着順に応じて行う単純なアルゴリズム, DOGDを提案する。
DOGDが達成した動的後悔境界を$O(sqrtbardT(P_T+1))$に削減する改良アルゴリズムを開発した。
論文 参考訳(メタデータ) (2023-05-20T07:54:07Z) - Borda Regret Minimization for Generalized Linear Dueling Bandits [65.09919504862496]
本稿では,ボルダスコアが最も高い項目を識別することを目的とした,デュエルバンディットに対するボルダ後悔最小化問題について検討する。
本稿では,多くの既存モデルをカバーする一般化線形デュエルバンドモデルのリッチクラスを提案する。
我々のアルゴリズムは$tildeO(d2/3 T2/3)$ regretを達成し、これも最適である。
論文 参考訳(メタデータ) (2023-03-15T17:59:27Z) - Near-Optimal Algorithms for Private Online Optimization in the
Realizable Regime [74.52487417350221]
オンライン学習の問題は,ゼロロスソリューションが存在する,実現可能な環境において考慮する。
そこで我々は,ほぼ最適の後悔境界を求める新たなDPアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-02-27T21:19:24Z) - 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) - Nonstochastic Bandits with Composite Anonymous Feedback [41.38921728211769]
本研究では,アクションの損失が直ちにプレイヤーに請求されない非確率的バンディット設定について検討する。
各ラウンドの最後にプレイヤーが観測した瞬間的な損失は、これまでプレイされたアクションの多くの損失成分の合計である。
論文 参考訳(メタデータ) (2021-12-06T08:44:04Z) - 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) - Online Strongly Convex Optimization with Unknown Delays [30.931538196386672]
オンライン凸最適化の問題点を未知の遅延で検討する。
まず、OGDの遅延変形を強凸関数に拡張する。
我々は、$d$が最大遅延である$O(dlog T)$のより良い後悔の境界を確立します。
論文 参考訳(メタデータ) (2021-03-21T10:16:15Z) - Adapting to Delays and Data in Adversarial Multi-Armed Bandits [7.310043452300736]
決定時に利用可能な情報のみを用いてステップサイズを調整するExp3アルゴリズムの変種を分析する。
我々は、観測された(最悪の場合ではなく)遅延や損失のシーケンスに適応する後悔の保証を得る。
論文 参考訳(メタデータ) (2020-10-12T20:53:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。