論文の概要: Improved Analysis of Robustness of the Tsallis-INF Algorithm to
Adversarial Corruptions in Stochastic Multiarmed Bandits
- arxiv url: http://arxiv.org/abs/2103.12487v1
- Date: Tue, 23 Mar 2021 12:26:39 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-24 14:07:09.947834
- Title: Improved Analysis of Robustness of the Tsallis-INF Algorithm to
Adversarial Corruptions in Stochastic Multiarmed Bandits
- Title（参考訳）: Tsallis-INFアルゴリズムの確率的マルチアームバンドの逆転破壊に対するロバスト性の改善
- Authors: Saeed Masoudian, Yevgeny Seldin
- Abstract要約: Zimmert and Seldin (2021) の Tsallis-INF アルゴリズムに対する後悔の境界を改善した。
特に、$C = Thetaleft(fracTlog Tlog T$)$の場合、$T$が時空である場合、乗算因子による改善を達成します。
また, time horizon 上の後悔の依存性を $log t$ から $log frac(k-1)t(sum_ineq i*frac1delta_ に改善する。
- 参考スコア（独自算出の注目度）: 12.462608802359936
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We derive improved regret bounds for the Tsallis-INF algorithm of Zimmert and
Seldin (2021). In the adversarial regime with a self-bounding constraint and
the stochastic regime with adversarial corruptions as its special case we
improve the dependence on corruption magnitude $C$. In particular, for $C =
\Theta\left(\frac{T}{\log T}\right)$, where $T$ is the time horizon, we achieve
an improvement by a multiplicative factor of $\sqrt{\frac{\log T}{\log\log T}}$
relative to the bound of Zimmert and Seldin (2021). We also improve the
dependence of the regret bound on time horizon from $\log T$ to $\log
\frac{(K-1)T}{(\sum_{i\neq i^*}\frac{1}{\Delta_i})^2}$, where $K$ is the number
of arms, $\Delta_i$ are suboptimality gaps for suboptimal arms $i$, and $i^*$
is the optimal arm. Additionally, we provide a general analysis, which allows
to achieve the same kind of improvement for generalizations of Tsallis-INF to
other settings beyond multiarmed bandits.
- Abstract（参考訳）: 我々は、Zimmert and Seldin (2021) の Tsallis-INF アルゴリズムの後悔境界を改善した。
自制的な制約のある敵対体制と、敵対的腐敗を伴う確率的体制において、我々は腐敗のマグニチュード$c$ の依存性を改善する。
特に、$C = \Theta\left(\frac{T}{\log T}\right)$の場合、$T$は時間地平線であり、Zimmert と Seldin (2021) の境界に対して$\sqrt{\frac{\log T}{\log\log T}}$の乗法係数によって改善される。
また、時間軸に束縛された後悔の依存性を、$\log t$ から $\log \frac{(k-1)t}{(\sum_{i\neq i^*}\frac{1}{\delta_i})^2}$ まで改善する。
さらに,Tsallis-INFを多腕包帯以外の設定に一般化する上で,同様の改良を実現するための一般解析も提供する。
関連論文リスト
- 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) - Best-of-Both-Worlds Linear Contextual Bandits [45.378265414553226]
本研究は, 対向汚職下での多武装盗賊問題の事例である$K$腕線形文脈盗賊の問題を考察する。
我々は,理論的保証のもと,双方の敵環境に有効な戦略を開発する。
両体制の理論的保証から,我々の戦略をBest-of-Both-Worlds (BoBW) RealFTRLと呼んでいる。
論文 参考訳（メタデータ） (2023-12-27T09:32:18Z) - Best-of-Both-Worlds Algorithms for Linear Contextual Bandits [11.94312915280916]
両世界のベスト・オブ・ワールドズ・アルゴリズムを$K$武器付き線形文脈包帯に対して検討する。
我々のアルゴリズムは、敵対的体制と敵対的体制の両方において、ほぼ最適の後悔の限界を提供する。
論文 参考訳（メタデータ） (2023-12-24T08:27:30Z) - Corruption-Robust Offline Reinforcement Learning with General Function
Approximation [60.91257031278004]
一般関数近似を用いたオフライン強化学習(RL)における劣化問題について検討する。
我々のゴールは、崩壊しないマルコフ決定プロセス(MDP)の最適方針に関して、このような腐敗に対して堅牢で、最適でないギャップを最小限に抑える政策を見つけることである。
論文 参考訳（メタデータ） (2023-10-23T04:07:26Z) - Tight Bounds for $\gamma$-Regret via the Decision-Estimation Coefficient [88.86699022151598]
任意の構造化バンディット問題に対する$gamma$-regretの統計的特徴を与える。
この$gamma$-regretは、関数クラス$mathcalF$上の構造化バンディット問題に現れる。
論文 参考訳（メタデータ） (2023-03-06T17:54:33Z) - 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) - Differentially Private Multi-Armed Bandits in the Shuffle Model [58.22098764071924]
シャッフルモデルにおけるマルチアームバンディット(MAB)問題に対して,$(varepsilon,delta)$-differentially privateアルゴリズムを提案する。
我々の上限は、集中モデルにおいて最もよく知られたアルゴリズムの後悔とほぼ一致し、局所モデルにおいて最もよく知られたアルゴリズムを著しく上回っている。
論文 参考訳（メタデータ） (2021-06-05T14:11:01Z) - Bandits with many optimal arms [68.17472536610859]
最適アームの割合は$p*$、最適アームとサブ最適化アームの間の最小平均ギャップは$Delta$と書きます。
我々は,累積的後悔設定と最良腕識別設定の両方において最適な学習率を特徴付ける。
論文 参考訳（メタデータ） (2021-03-23T11:02:31Z) - An Algorithm for Stochastic and Adversarial Bandits with Switching Costs [10.549307055348596]
そこで本研究では,マルチアームバンディットのスイッチングコストを考慮したアルゴリズムを提案し,そのアルゴリズムがアームを切り替える度に$lambda$を支払う。
私たちのアルゴリズムは、Zimmert and Seldin(2021)のTsallis-INFアルゴリズムの適応に基づいています。
論文 参考訳（メタデータ） (2021-02-19T11:03: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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。