論文の概要: Adapting to Delays and Data in Adversarial Multi-Armed Bandits
- arxiv url: http://arxiv.org/abs/2010.06022v1
- Date: Mon, 12 Oct 2020 20:53:52 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-08 06:34:47.618120
- Title: Adapting to Delays and Data in Adversarial Multi-Armed Bandits
- Title（参考訳）: 敵対的多腕バンディットにおける遅延とデータへの適応
- Authors: Andr\'as Gy\"orgy, Pooria Joulani
- Abstract要約: 決定時に利用可能な情報のみを用いてステップサイズを調整するExp3アルゴリズムの変種を分析する。
我々は、観測された(最悪の場合ではなく)遅延や損失のシーケンスに適応する後悔の保証を得る。
- 参考スコア（独自算出の注目度）: 7.310043452300736
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the adversarial multi-armed bandit problem under delayed
feedback. We analyze variants of the Exp3 algorithm that tune their step-size
using only information (about the losses and delays) available at the time of
the decisions, and obtain regret guarantees that adapt to the observed (rather
than the worst-case) sequences of delays and/or losses. First, through a
remarkably simple proof technique, we show that with proper tuning of the step
size, the algorithm achieves an optimal (up to logarithmic factors) regret of
order $\sqrt{\log(K)(TK + D)}$ both in expectation and in high probability,
where $K$ is the number of arms, $T$ is the time horizon, and $D$ is the
cumulative delay. The high-probability version of the bound, which is the first
high-probability delay-adaptive bound in the literature, crucially depends on
the use of implicit exploration in estimating the losses. Then, following
Zimmert and Seldin [2019], we extend these results so that the algorithm can
"skip" rounds with large delays, resulting in regret bounds of order
$\sqrt{TK\log(K)} + |R| + \sqrt{D_{\bar{R}}\log(K)}$, where $R$ is an arbitrary
set of rounds (which are skipped) and $D_{\bar{R}}$ is the cumulative delay of
the feedback for other rounds. Finally, we present another, data-adaptive
(AdaGrad-style) version of the algorithm for which the regret adapts to the
observed (delayed) losses instead of only adapting to the cumulative delay
(this algorithm requires an a priori upper bound on the maximum delay, or the
advance knowledge of the delay for each decision when it is made). The
resulting bound can be orders of magnitude smaller on benign problems, and it
can be shown that the delay only affects the regret through the loss of the
best arm.
- Abstract（参考訳）: 遅延フィードバック下での対向型多腕バンディット問題を考える。
決定時に利用可能な情報(損失や遅延について)のみを用いてステップサイズを調整したExp3アルゴリズムの変種を分析し、観測された(最悪のケースではなく)遅延や損失のシーケンスに適応した後悔の保証を得る。
まず、非常に単純な証明手法により、ステップサイズの適切なチューニングにより、アルゴリズムは、期待値と高い確率値の両方において、$k$がアーム数、$t$がタイムホライズン、$d$が累積遅延の両方において、最適な(対数係数まで)後悔を実現できることを示す。
文献における最初の高確率遅延適応境界である高確率バージョンは、損失を推定する暗黙の探索の使用に大きく依存する。
すると、zimmert と seldin [2019] に続いて、これらの結果を拡張して、アルゴリズムが大きな遅延でラウンドをスキップできるようにし、その結果、$\sqrt{tk\log(k)} + |r| + \sqrt{d_{\bar{r}}\log(k)}$、ただし $r$ は任意のラウンドの集合(スキップされる)であり、$d_{\bar{r}}$ は他のラウンドに対するフィードバックの累積遅延である。
最後に、累積遅延にのみ適応する代わりに、後悔が観測された(遅延)損失に適応する(このアルゴリズムは、最大遅延の事前の上限または各決定の遅延の事前知識を必要とする)アルゴリズムの別のデータ適応型(アデグラード型)バージョンを提案する。
結果として得られる境界は、良質な問題では桁違いに小さくなり、遅れは最善の腕を失うことで後悔にしか影響しないことを示すことができる。
関連論文リスト
- Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling [73.5602474095954]
マルコフサンプリングの遅延更新による近似スキームの非漸近的性能について検討した。
我々の理論的な発見は、幅広いアルゴリズムの遅延の有限時間効果に光を当てた。
論文 参考訳（メタデータ） (2024-02-19T03:08:02Z) - 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) - A Best-of-both-worlds Algorithm for Bandits with Delayed Feedback with Robustness to Excessive Delays [24.998122268199797]
本稿では,フィードバックが可変に遅延するバンディットのためのベスト・オブ・ボス・ワールドス・アルゴリズムを提案する。
我々のアルゴリズムは任意の過剰な遅延を許容し、$T$をオーダーすることができる。
論文 参考訳（メタデータ） (2023-08-21T12:17:40Z) - Non-stationary Online Convex Optimization with Arbitrary Delays [50.46856739179311]
本稿では,非定常環境における遅延オンライン凸最適化(OCO)について検討する。
まず, 遅延勾配の勾配降下ステップを, 到着順に応じて行う単純なアルゴリズム, DOGDを提案する。
DOGDが達成した動的後悔境界を$O(sqrtbardT(P_T+1))$に削減する改良アルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-05-20T07:54:07Z) - Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement
Learning: Adaptivity and Computational Efficiency [90.40062452292091]
本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。
我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。
また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-21T00:17:24Z) - Nonstochastic Bandits and Experts with Arm-Dependent Delays [17.272515865592542]
遅延が時間と腕に依存するような遅延環境で,非確率的な盗賊や専門家について検討する。
私たちの分析では、ドリフトに縛られた小説にヒンジを付け、1ラウンドのルックアヘッドを与えられた場合、アルゴリズムがどれだけの精度で実行できるかを測定しました。
論文 参考訳（メタデータ） (2021-11-02T13:36:11Z) - Procrastinated Tree Search: Black-box Optimization with Delayed, Noisy,
and Multi-fidelity Feedback [11.064341598231195]
ブラックボックス最適化問題では,評価やシミュレーションオラクルのフィードバックによってのみ機能にアクセス可能な未知の目的関数を最大化することを目的としている。
ProCrastinated Tree Search (PCTS) と呼ばれる階層的楽観木探索(HOO)の汎用的拡張を提案する。
我々は,PCTSの遅延,雑音,多面的フィードバックによる後悔を定量化する汎用的証明手法を提案する。
論文 参考訳（メタデータ） (2021-10-14T08:55:41Z) - Distributed stochastic optimization with large delays [59.95552973784946]
大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。
DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
論文 参考訳（メタデータ） (2021-07-06T21:59:49Z) - Stochastic Multi-Armed Bandits with Unrestricted Delay Distributions [54.25616645675032]
アルゴリズムが受信したフィードバックにランダムな遅延を伴うマルチアーマッド・バンドイット(MAB)問題について検討する。
報酬非依存の遅延設定は、報酬非依存の遅延設定と、報酬非依存の遅延設定に依存する可能性がある。
私たちの主な貢献は、それぞれの設定でほぼ最適に後悔するアルゴリズムです。
論文 参考訳（メタデータ） (2021-06-04T12:26:06Z) - Online Strongly Convex Optimization with Unknown Delays [30.931538196386672]
オンライン凸最適化の問題点を未知の遅延で検討する。
まず、OGDの遅延変形を強凸関数に拡張する。
我々は、$d$が最大遅延である$O(dlog T)$のより良い後悔の境界を確立します。
論文 参考訳（メタデータ） (2021-03-21T10:16:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。