Fugu-MT 論文翻訳(概要): Adversarial Bandits Robust to $S$-Switch Regret

論文の概要: Adversarial Bandits Robust to $S$-Switch Regret

arxiv url: http://arxiv.org/abs/2205.14839v1
Date: Mon, 30 May 2022 03:57:46 GMT
ステータス: 処理完了
システム内更新日: 2022-05-31 14:06:21.576054
Title: Adversarial Bandits Robust to $S$-Switch Regret
Title（参考訳）: 反逆バンド、S$-Switchレグレットにロバスト
Authors: Jung-hun Kim, Se-Young Yun
Abstract要約: 我々は、未知の$S$に対してベストアームを切り替える回数の$S$で、敵の盗賊問題を研究する。まず,基本的な OMD を用いたマスタベースアルゴリズムを提案し,$tildeO(S1/2K 1/3T2/3)$を達成した。我々は,OMDの適応学習率を用いて損失推定器の分散を制御し,$tildeO(minmathbbE[sqrtSKTrho_T(hdagger)],SsqrtKTを実現することを提案する。
参考スコア（独自算出の注目度）: 12.335698325757491
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We study the adversarial bandit problem under $S$ number of switching best arms for unknown $S$. For handling this problem, we adopt the master-base framework using the online mirror descent method (OMD). We first provide a master-base algorithm with basic OMD, achieving $\tilde{O}(S^{1/2}K^{1/3}T^{2/3})$. For improving the regret bound with respect to $T$, we propose to use adaptive learning rates for OMD to control variance of loss estimators, and achieve $\tilde{O}(\min\{\mathbb{E}[\sqrt{SKT\rho_T(h^\dagger)}],S\sqrt{KT}\})$, where $\rho_T(h^\dagger)$ is a variance term for loss estimators.
Abstract（参考訳）: 我々は、未知の$S$に対してベストアームを切り替える回数$S$で、敵の盗賊問題を研究する。この問題に対処するために,オンラインミラー降下法(OMD)を用いたマスタベースフレームワークを採用する。まず、基本omdを持つマスターベースアルゴリズムを提供し、$\tilde{o}(s^{1/2}k^{1/3}t^{2/3}) を得る。損失推定器の分散を制御するために、OMDの適応学習率を用いて、損失推定器の分散を制御し、$\tilde{O}(\min\{\mathbb{E}[\sqrt{SKT\rho_T(h^\dagger)}],S\sqrt{KT}\})$($\rho_T(h^\dagger)$は損失推定器の分散項である。

関連論文リスト

Stochastic Bandits Robust to Adversarial Attacks [33.278131584647745]
本稿では,敵攻撃に対して頑健なマルチアームバンディットアルゴリズムについて検討する。我々は、攻撃予算の知識の有無に関わらず、このモデルの2つのケースを調査する。我々は、加法的あるいは乗法的な$C$依存項を持つ後悔境界を持つ2種類のアルゴリズムを考案する。
論文参考訳（メタデータ） (2024-08-16T17:41:35Z)
Accelerated Variance-Reduced Forward-Reflected Methods for Root-Finding Problems [8.0153031008486]
そこで本研究では,Nesterovの高速前方反射法と分散還元法を新たに提案し,根絶問題の解法を提案する。我々のアルゴリズムは単ループであり、ルートフィリング問題に特化して設計された非バイアス分散還元推定器の新たなファミリーを利用する。
論文参考訳（メタデータ） (2024-06-04T15:23:29Z)
Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。 G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
論文参考訳（メタデータ） (2024-01-14T14:14:19Z)
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)
Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs [72.40181882916089]
我々のアルゴリズムが $tildeObig((d+log (|mathcalS|2 |mathcalA|))sqrtKbig)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping is linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|mathcalS|$ and $|mathcalA|$ is the standardities of the state and action space。
論文参考訳（メタデータ） (2023-05-15T05:37:32Z)
Revisiting Weighted Strategy for Non-stationary Parametric Bandits [82.1942459195896]
本稿では,非定常パラメトリックバンディットの重み付け戦略を再考する。より単純な重みに基づくアルゴリズムを生成する改良された分析フレームワークを提案する。我々の新しいフレームワークは、他のパラメトリックバンディットの後悔の限界を改善するのに使える。
論文参考訳（メタデータ） (2023-03-05T15:11:14Z)
Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs [111.75736569611159]
線形混合MDPのための計算効率のよい初めての地平線フリーアルゴリズムを提案する。我々のアルゴリズムは、未知の遷移力学に対する重み付き最小二乗推定器に適応する。これにより、$sigma_k2$'sが知られているときに、この設定で最もよく知られたアルゴリズムも改善される。
論文参考訳（メタデータ） (2022-05-23T17:59:18Z)
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)
Variance-Aware Confidence Set: Variance-Dependent Bound for Linear Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
論文参考訳（メタデータ） (2021-01-29T18:57:52Z)
Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
論文参考訳（メタデータ） (2020-03-04T07:36:38Z)

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