論文の概要: Banker Online Mirror Descent: A Universal Approach for Delayed Online
Bandit Learning
- arxiv url: http://arxiv.org/abs/2301.10500v2
- Date: Sat, 27 May 2023 05:45:41 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-31 02:07:15.933781
- Title: Banker Online Mirror Descent: A Universal Approach for Delayed Online
Bandit Learning
- Title（参考訳）: Banker Online Mirror Descent: 遅延オンラインバンド学習のためのユニバーサルアプローチ
- Authors: Jiatai Huang, Yan Dai, Longbo Huang
- Abstract要約: Banker Online Mirror Descent (Banker-OMD) は、オンライン学習文学における古典的オンラインミラー・ディッセンス(OMD)技法を一般化する新しいフレームワークである。
遅延フィードバックを伴う2つの重要なバンディット学習シナリオに適用することで,textttBanker-OMDのパワーを実証する。
textttBanker-OMDは、$widetildemathcal O(sqrt KL(sqrt T+sqrt D))を達成した最初の遅延スケールフリー逆数MABアルゴリズムをもたらす
- 参考スコア（独自算出の注目度）: 22.18577284185939
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: We propose Banker Online Mirror Descent (Banker-OMD), a novel framework
generalizing the classical Online Mirror Descent (OMD) technique in the online
learning literature. The Banker-OMD framework almost completely decouples
feedback delay handling and the task-specific OMD algorithm design, thus
facilitating the design of new algorithms capable of efficiently and robustly
handling feedback delays. Specifically, it offers a general methodology for
achieving $\widetilde{\mathcal O}(\sqrt{T} + \sqrt{D})$-style regret bounds in
online bandit learning tasks with delayed feedback, where $T$ is the number of
rounds and $D$ is the total feedback delay. We demonstrate the power of
\texttt{Banker-OMD} by applications to two important bandit learning scenarios
with delayed feedback, including delayed scale-free adversarial Multi-Armed
Bandits (MAB) and delayed adversarial linear bandits. \texttt{Banker-OMD} leads
to the first delayed scale-free adversarial MAB algorithm achieving
$\widetilde{\mathcal O}(\sqrt{K}L(\sqrt T+\sqrt D))$ regret and the first
delayed adversarial linear bandit algorithm achieving $\widetilde{\mathcal
O}(\text{poly}(n)(\sqrt{T} + \sqrt{D}))$ regret. As a corollary, the first
application also implies $\widetilde{\mathcal O}(\sqrt{KT}L)$ regret for
non-delayed scale-free adversarial MABs, which is the first to match the
$\Omega(\sqrt{KT}L)$ lower bound up to logarithmic factors and can be of
independent interest.
- Abstract（参考訳）: オンライン学習文献における古典的オンラインミラー・ディクセント(OMD)技法を一般化した新しいフレームワークであるバンクラーオンライン・ミラー・ディクセント(Banker Online Mirror Descent, Banker-OMD)を提案する。
Banker-OMDフレームワークは、フィードバック遅延処理とタスク固有のOMDアルゴリズム設計をほぼ完全に分離し、フィードバック遅延を効率的にかつ堅牢に処理できる新しいアルゴリズムの設計を容易にする。
具体的には、遅延フィードバックを伴うオンラインバンディット学習タスクにおける、$\widetilde{\mathcal O}(\sqrt{T} + \sqrt{D})$スタイルの後悔境界を達成するための一般的な方法論を提供する。
遅延フィードバックを伴う2つの重要なバンディット学習シナリオに対して,mab (scale-free adversarial multi-armed bandit) と遅延線形バンディット (delayed adversarial linear bandit) を応用して, \texttt{banker-omd} のパワーを実証した。
\texttt{banker-omd} は、$\widetilde{\mathcal o}(\sqrt{k}l(\sqrt t+\sqrt d)) を達成する最初の遅延スケールフリーな逆向き mab アルゴリズムと$\widetilde{\mathcal o}(\text{poly}(n)(\sqrt{t} + \sqrt{d})$ regret を達成する最初の遅延逆向きバンディットアルゴリズムに繋がる。
結論として、最初の応用は、非遅延スケール自由逆数 MAB に対して $\widetilde{\mathcal O}(\sqrt{KT}L)$ regret を意味し、これは $\Omega(\sqrt{KT}L)$ lower を対数的因子に限定して、独立な関心を持つことができる。
関連論文リスト
- Beyond $\mathcal{O}(\sqrt{T})$ Regret: Decoupling Learning and Decision-making in Online Linear Programming [7.518108920887426]
本稿では,LP双対問題が一定の誤差境界条件を示す場合に,$mathcalO ( sqrtT )$の結果を改善するための一般的な枠組みを確立する。
連続的なサポート設定において,1次学習アルゴリズムが$o(sqrtT )$後悔し,非退化仮定以外の有限サポート設定において$mathcalO (log T)$後悔することを示す。
論文 参考訳（メタデータ） (2025-01-06T04:57:44Z) - Federated Combinatorial Multi-Agent Multi-Armed Bandits [79.1700188160944]
本稿では,Banditを用いたオンライン最適化に適したフェデレーション学習フレームワークを提案する。
この設定では、エージェントのアームサブセットは、個々のアーム情報にアクセスせずにこれらのサブセットに対するノイズの多い報酬を観察し、特定の間隔で協力して情報を共有することができる。
論文 参考訳（メタデータ） (2024-05-09T17:40:09Z) - 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) - Complete Policy Regret Bounds for Tallying Bandits [51.039677652803675]
政策後悔は、適応的な敵に対してオンライン学習アルゴリズムのパフォーマンスを測定するという、よく確立された概念である。
我々は,不完全な政策後悔を効果的に最小化できる敵の制限について検討する。
我々は、$tildemathcalO(mKsqrtT)$の完全なポリシーを後悔するアルゴリズムを提供し、$tildemathcalO$表記は対数要素だけを隠す。
論文 参考訳（メタデータ） (2022-04-24T03:10:27Z) - Corralling a Larger Band of Bandits: A Case Study on Switching Regret
for Linear Bandits [99.86860277006318]
本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。
Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。
この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
論文 参考訳（メタデータ） (2022-02-12T21:55:44Z) - 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) - Banker Online Mirror Descent [25.927810369879175]
Banker-OMDは、オンライン学習アルゴリズム設計において古典的オンラインミラー・ディフレッシュ(OMD)技法を一般化する新しいフレームワークである。
遅延フィードバックを伴う3つの重要なバンディットシナリオに適用可能なバンクアOMDを実演する。
特に、最初の遅延逆線形バンドイットアルゴリズムは、$tildeO(textpoly(n)(sqrtT + sqrtD))$ regretとなる。
論文 参考訳（メタデータ） (2021-06-16T16:57:05Z) - Online Markov Decision Processes with Aggregate Bandit Feedback [74.85532145498742]
本稿では,オンライン有限水平マルコフ決定過程の新たな変種について検討する。
各エピソードにおいて、学習者は、エピソードの選択した方針によって実現された軌道に沿って蓄積された損失を被り、総括的盗聴フィードバックを観察する。
我々の主な結果は計算効率のよいアルゴリズムで、$O(sqrtK)$ regret for this set, where $K$ is the number of episodes。
論文 参考訳（メタデータ） (2021-01-31T16:49:07Z) - Adapting to Delays and Data in Adversarial Multi-Armed Bandits [7.310043452300736]
決定時に利用可能な情報のみを用いてステップサイズを調整するExp3アルゴリズムの変種を分析する。
我々は、観測された(最悪の場合ではなく)遅延や損失のシーケンスに適応する後悔の保証を得る。
論文 参考訳（メタデータ） (2020-10-12T20:53:52Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。