Fugu-MT 論文翻訳(概要): Tracking Most Severe Arm Changes in Bandits

論文の概要: Tracking Most Severe Arm Changes in Bandits

arxiv url: http://arxiv.org/abs/2112.13838v1
Date: Mon, 27 Dec 2021 18:59:05 GMT
ステータス: 処理完了
システム内更新日: 2021-12-28 15:52:55.727507
Title: Tracking Most Severe Arm Changes in Bandits
Title（参考訳）: バンドの腕の重度変化の追跡
Authors: Joe Suk and Samory Kpotufe
Abstract要約: 我々は、$tildeO(sqrtT)ll tildeO(sqrtLT)ll tildeO(sqrtT)ll tildeO(sqrtT)ll tildeO(sqrtT)ll tildeO(sqrtT)ll tildeO(sqrtT)ll tildeO(sqrtT)ll tildeO(sqrtT)ll tildeO(sqrtT)ll tildeO(sqrtT)ll
参考スコア（独自算出の注目度）: 12.29762518277676
License: http://creativecommons.org/licenses/by/4.0/
Abstract: In bandits with distribution shifts, one aims to automatically detect an unknown number $L$ of changes in reward distribution, and restart exploration when necessary. While this problem remained open for many years, a recent breakthrough of Auer et al. (2018, 2019) provide the first adaptive procedure to guarantee an optimal (dynamic) regret $\sqrt{LT}$, for $T$ rounds, with no knowledge of $L$. However, not all distributional shifts are equally severe, e.g., suppose no best arm switches occur, then we cannot rule out that a regret $O(\sqrt{T})$ may remain possible; in other words, is it possible to achieve dynamic regret that optimally scales only with an unknown number of severe shifts? This unfortunately has remained elusive, despite various attempts (Auer et al., 2019, Foster et al., 2020). We resolve this problem in the case of two-armed bandits: we derive an adaptive procedure that guarantees a dynamic regret of order $\tilde{O}(\sqrt{\tilde{L} T})$, where $\tilde L \ll L$ captures an unknown number of severe best arm changes, i.e., with significant switches in rewards, and which last sufficiently long to actually require a restart. As a consequence, for any number $L$ of distributional shifts outside of these severe shifts, our procedure achieves regret just $\tilde{O}(\sqrt{T})\ll \tilde{O}(\sqrt{LT})$. Finally, we note that our notion of severe shift applies in both classical settings of stochastic switching bandits and of adversarial bandits.
Abstract（参考訳）: 分布シフトを伴う帯域幅において、報酬分布の変化の未知数$L$を自動的に検出し、必要に応じて探索を再開することを目的としている。この問題は長年公にされてきたが、最近の Auer et al. (2018, 2019) のブレークスルーは、$L$の知識のない$T$ラウンドに対して最適(動的)後悔$\sqrt{LT}$を保証するための最初の適応手順を提供する。しかし、全ての分布シフトが等しく深刻であるわけではない、例えば、最高のアームスイッチが起こらないと仮定すると、後悔の$O(\sqrt{T})$が引き続き可能であると断定することはできない。様々な試み(auer et al., 2019, foster et al., 2020)にもかかわらず、このことはあいまいなままである。ここでは、$\tilde {O}(\sqrt{\tilde{L} T})$で、$\tilde L \ll L$は、未知の数の深刻なベストアーム変更をキャプチャする。その結果、これらの厳しいシフト以外の分布シフトの任意の数$L$に対して、我々の手順は単に$\tilde{O}(\sqrt{T})\ll \tilde{O}(\sqrt{LT})$である。最後に,重度シフトの概念は,確率的スイッチングバンディットと逆バンディットの両方の古典的な設定に適用できる点に留意する。

関連論文リスト

Adaptive Smooth Non-Stationary Bandits [0.8158530638728501]
我々は、報酬がスムーズに変化する、$Kの非定常バンディットモデルについて研究する。一般に、すべての$K,beta,lambda$に対してminimax動的後悔率を確立します。また,非定常帯域におけるギャップ依存的後悔率の高速化についても検討した。
論文参考訳（メタデータ） (2024-07-11T16:37:15Z)
Discounted Thompson Sampling for Non-Stationary Bandit Problems [13.656518163592349]
NS-MAB(Non-stationary multi-armed bandit)問題も最近注目されている。非定常条件の両方に対処するため,ガウシアン先行値を用いたディスカウントトンプソンサンプリング(DS-TS)を提案する。我々のアルゴリズムは、トンプソンサンプリングに割引係数を組み込むことにより、変化に順応的に適応する。
論文参考訳（メタデータ） (2023-05-18T05:29:52Z)
Smooth Non-Stationary Bandits [49.19728527803684]
本研究では、各アームの平均報酬シーケンスを$beta$-H"older関数に埋め込むことができる非定常包帯問題について検討する。スムース(つまり$betage 2$)と非スムース(つまり$beta=1$)との最初の分離は、$tilde O(k4/5 T3/5)$ regret on any $k$-armed, $2-H"older instanceでポリシーを提示することで示します。
論文参考訳（メタデータ） (2023-01-29T06:03:20Z)
Variance-Aware Sparse Linear Bandits [64.70681598741417]
余分な線形包帯に対する最悪のミニマックスは$widetildeThetaleft(sqrtdTright)$である。ノイズがなく、アクションセットが単位球面である良性設定では、ディビジョン・アンド・コンカーを使用して、$widetildemathcal O(1)$ regretを達成することができる。我々は,任意の分散対応線形帯域幅アルゴリズムを分散対応線形帯域幅アルゴリズムに変換する汎用フレームワークを開発した。
論文参考訳（メタデータ） (2022-05-26T15:55:44Z)
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)
A New Look at Dynamic Regret for Non-Stationary Stochastic Bandits [11.918230810566945]
本研究では,学習過程において各腕の報酬統計が数回変化しうる非定常的マルチアームバンディット問題について検討する。我々は、$K$の武器付きバンディット問題において、ほぼ最適の$widetilde O(sqrtK N(S+1))$ dynamic regretを実現する方法を提案する。
論文参考訳（メタデータ） (2022-01-17T17:23:56Z)
The best of both worlds: stochastic and adversarial episodic MDPs with unknown transition [49.78053380710322]
我々は,エピソードT$でマルコフ決定過程を学習する上で,両世界の最良の問題を考える。最近の[Jin and Luo, 2020]による研究は、固定遷移が分かっているときにこの目標を達成する。本研究では,同じFollow-the-Regularized-Leader(textFTRL$)フレームワークを新しいテクニックのセットと組み合わせることで,この問題を解決する。
論文参考訳（メタデータ） (2021-06-08T05:46:35Z)
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)
Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Case [29.99619764839178]
敵の費用と未知の遷移を伴う最短経路問題に対して,大きな進展をみせている。具体的には、全情報設定を後悔する$widetildeO(sqrtS3A2DT_star K)を実現するアルゴリズムを開発する。私たちはまた、最も難しい組み合わせとして、敵のコストによる盗聴フィードバックと未知の移行を最初に検討しています。
論文参考訳（メタデータ） (2021-02-10T06:33:04Z)
Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文参考訳（メタデータ） (2020-06-17T22:32:19Z)
Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transition [38.28925339231888]
我々は,世界最良保証付きの最初のアルゴリズムを開発した。損失が逆ならば、$mathcalO(log T)$ regretを達成します。より一般的には、中間設定で $tildemathcalO(sqrtC)$ regret を達成する。
論文参考訳（メタデータ） (2020-06-10T01:59:34Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。