論文の概要: Scale-Free Adversarial Multi-Armed Bandit with Arbitrary Feedback Delays
- arxiv url: http://arxiv.org/abs/2110.13400v1
- Date: Tue, 26 Oct 2021 04:06:51 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-28 06:10:01.275713
- Title: Scale-Free Adversarial Multi-Armed Bandit with Arbitrary Feedback Delays
- Title（参考訳）: 任意フィードバック遅延を有するスケールフリーの多元帯域
- Authors: Jiatai Huang, Yan Dai, Longbo Huang
- Abstract要約: 制限のないフィードバック遅延を伴う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。
- 参考スコア（独自算出の注目度）: 21.94728545221709
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: We consider the Scale-Free Adversarial Multi Armed Bandit (MAB) problem with
unrestricted feedback delays. In contrast to the standard assumption that all
losses are $[0,1]$-bounded, in our setting, losses can fall in a general
bounded interval $[-L, L]$, unknown to the agent before-hand. Furthermore, the
feedback of each arm pull can experience arbitrary delays. We propose an
algorithm named \texttt{SFBanker} for this novel setting, which combines a
recent banker online mirror descent technique and elaborately designed doubling
tricks. We show that \texttt{SFBanker} achieves $\mathcal
O(\sqrt{K(D+T)}L)\cdot {\rm polylog}(T, L)$ total regret, where $T$ is the
total number of steps and $D$ is the total feedback delay. \texttt{SFBanker}
also outperforms existing algorithm for non-delayed (i.e., $D=0$) scale-free
adversarial MAB problem instances. We also present a variant of
\texttt{SFBanker} for problem instances with non-negative losses (i.e., they
range in $[0, L]$ for some unknown $L$), achieving an $\tilde{\mathcal
O}(\sqrt{K(D+T)}L)$ total regret, which is near-optimal compared to the
$\Omega(\sqrt{KT}+\sqrt{D\log K}L)$ lower-bound ([Cesa-Bianchi et al., 2016]).
- Abstract（参考訳）: 制限のないフィードバック遅延を伴うMAB(Scale-Free Adversarial Multi Armed Bandit)問題を考える。
すべての損失が$[0,1]$-boundedであるという標準的な仮定とは対照的に、我々の設定では、損失は一般に有界な区間$[-L, L]$に落ちる可能性がある。
さらに、各アームプルのフィードバックは任意の遅延を経験できる。
本稿では,近年のバンカーのオンラインミラー降下手法と,精巧に設計された二重化手法を組み合わせた新しい設定法を提案する。
すると、\textt{sfbanker} は$\mathcal o(\sqrt{k(d+t)}l)\cdot {\rm polylog}(t, l)$ total regret となり、ここで$t$ はステップの総数、$d$ は総フィードバック遅延となる。
\texttt{SFBanker} は、非遅延(すなわち$D=0$)スケールフリーのMAB問題インスタンスに対して、既存のアルゴリズムよりも優れている。
また、非負の損失を持つ問題インスタンスに対する \textt{sfbanker} の変種(例えば、いくつかの未知の $l$ に対して $[0, l]$ の範囲)を示し、$\tilde{\mathcal o}(\sqrt{k(d+t)}l)$ total regret が $\omega(\sqrt{kt}+\sqrt{d\log k}l)$ lower-bound ([cesa-bianchi et al., 2016]) とほぼ最適である。
関連論文リスト
- Batched Stochastic Bandit for Nondegenerate Functions [8.015503209312786]
本稿では,非退化関数に対するバッチ帯域学習問題について検討する。
本稿では,非退化関数に対するバッチバンドイット問題をほぼ最適に解くアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-05-09T12:50:16Z) - LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Bandits [38.41164102066483]
本研究では、独立かつ同一に分散したコンテキストを持つ線形文脈帯域問題について考察する。
提案アルゴリズムは、Tsallisエントロピーを持つFollow-The-Regularized-Leaderに基づいており、$alpha$-textual-Con (LC)-Tsallis-INFと呼ばれている。
論文 参考訳（メタデータ） (2024-03-05T18:59:47Z) - 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) - Federated Linear Bandits with Finite Adversarial Actions [20.1041278044797]
我々は、M$のクライアントが中央サーバと通信し、線形文脈の帯域幅問題を解決するための連合線形帯域幅モデルについて検討する。
逆有限作用集合のユニークな問題に対処するため、FedSupLinUCBアルゴリズムを提案する。
我々は、FedSupLinUCBが$tildeO(sqrtd T)$の完全後悔を達成したことを証明している。
論文 参考訳（メタデータ） (2023-11-02T03:41:58Z) - A Best-of-Both-Worlds Algorithm for Bandits with Delayed Feedback [25.68113242132723]
本稿では,Zimmert と Seldin [2020] のアルゴリズムを,フィードバックの遅れによる逆方向の多重武装バンディットに対して修正したチューニングを行う。
我々は,時間的遅れのある設定において,ほぼ最適の相反的後悔の保証を同時に達成する。
また,任意の遅延の場合に対するアルゴリズムの拡張も提案する。
論文 参考訳（メタデータ） (2022-06-29T20:49:45Z) - 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) - On Submodular Contextual Bandits [92.45432756301231]
作用が基底集合の部分集合であり、平均報酬が未知の単調部分モジュラ函数によってモデル化されるような文脈的包帯の問題を考える。
Inverse Gap Weighting 戦略により,提案アルゴリズムは推定関数の局所的最適度を効率よくランダム化することを示す。
論文 参考訳（メタデータ） (2021-12-03T21:42:33Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-20T04:29:18Z) - Thresholded Lasso Bandit [70.17389393497125]
Thresholded Lasso banditは、報酬関数を定義するベクトルとスパースサポートを推定するアルゴリズムである。
一般には $mathcalO( log d + sqrtT )$ や $mathcalO( log d + sqrtT )$ としてスケールする非漸近的後悔の上界を確立する。
論文 参考訳（メタデータ） (2020-10-22T19:14:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。