論文の概要: An Algorithm for Stochastic and Adversarial Bandits with Switching Costs
- arxiv url: http://arxiv.org/abs/2102.09864v1
- Date: Fri, 19 Feb 2021 11:03:51 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-22 13:36:17.669038
- Title: An Algorithm for Stochastic and Adversarial Bandits with Switching Costs
- Title（参考訳）: スイッチングコストを考慮した確率的および対向的帯域のアルゴリズム
- Authors: Chlo\'e Rouyer, Yevgeny Seldin, Nicol\`o Cesa-Bianchi
- Abstract要約: そこで本研究では,マルチアームバンディットのスイッチングコストを考慮したアルゴリズムを提案し,そのアルゴリズムがアームを切り替える度に$lambda$を支払う。
私たちのアルゴリズムは、Zimmert and Seldin(2021)のTsallis-INFアルゴリズムの適応に基づいています。
- 参考スコア（独自算出の注目度）: 10.549307055348596
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose an algorithm for stochastic and adversarial multiarmed bandits
with switching costs, where the algorithm pays a price $\lambda$ every time it
switches the arm being played. Our algorithm is based on adaptation of the
Tsallis-INF algorithm of Zimmert and Seldin (2021) and requires no prior
knowledge of the regime or time horizon. In the oblivious adversarial setting
it achieves the minimax optimal regret bound of $O\big((\lambda K)^{1/3}T^{2/3}
+ \sqrt{KT}\big)$, where $T$ is the time horizon and $K$ is the number of arms.
In the stochastically constrained adversarial regime, which includes the
stochastic regime as a special case, it achieves a regret bound of
$O\left(\big((\lambda K)^{2/3} T^{1/3} + \ln T\big)\sum_{i \neq i^*}
\Delta_i^{-1}\right)$, where $\Delta_i$ are the suboptimality gaps and $i^*$ is
a unique optimal arm. In the special case of $\lambda = 0$ (no switching
costs), both bounds are minimax optimal within constants. We also explore
variants of the problem, where switching cost is allowed to change over time.
We provide experimental evaluation showing competitiveness of our algorithm
with the relevant baselines in the stochastic, stochastically constrained
adversarial, and adversarial regimes with fixed switching cost.
- Abstract（参考訳）: スイッチングコストがかかる確率的・対向的マルチアームバンドのアルゴリズムを提案し,腕のスイッチングを行うたびに,アルゴリズムは$\lambda$を支払う。
私たちのアルゴリズムは、Zimmert and Seldin(2021)のTsallis-INFアルゴリズムの適応に基づいています。
不可解な逆転設定では、$O\big((\lambda K)^{1/3}T^{2/3} + \sqrt{KT}\big)$の最小最適リコール境界を達成し、ここで$T$は時空であり、$K$は腕の数である。
確率論的に制約された逆数制では、特別の場合として確率的体制を含むが、この規則は、$O\left(\big(\big((\lambda K)^{2/3} T^{1/3} + \ln T\big)\sum_{i \neq i^*} \Delta_i^{-1}\right)$、$\Delta_i$は準最適ギャップであり、$i^*$は一意の最適アームである。
特別な場合、$\lambda = 0$ (スイッチングコストなし) では、両方の境界は定数内で最小最適である。
また、スイッチングコストの経時変化が許される問題の変種についても検討します。
本稿では, 確率的, 確率的に制約された逆数, および, 固定的な切替コストを伴う逆数系におけるアルゴリズムの競争性を示す実験的な評価を行う。
関連論文リスト
- Adversarial Combinatorial Bandits with Switching Costs [55.2480439325792]
本稿では,各ラウンドで選択したアームのスイッチに対して,切替コストが$lambda$の逆帯域問題について検討する。
ミニマックスの後悔とそれにアプローチするための設計アルゴリズムの限界を低くする。
論文 参考訳（メタデータ） (2024-04-02T12:15:37Z) - 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) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - Better Best of Both Worlds Bounds for Bandits with Switching Costs [37.71741656687868]
本稿では,2021年にRouryer,Seldin,Cesa-Bianchiらにより,スイッチングコストを伴うバンディットのベスト・オブ・ザ・ワールドス・アルゴリズムについて検討した。
本稿では, 極小最小の最小残差を$mathcalO(T2/3)$で同時に達成する, 驚くほど単純かつ効果的に導入する。
論文 参考訳（メタデータ） (2022-06-07T08:22:56Z) - 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) - Improved Analysis of Robustness of the Tsallis-INF Algorithm to
Adversarial Corruptions in Stochastic Multiarmed Bandits [12.462608802359936]
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_ に改善する。
論文 参考訳（メタデータ） (2021-03-23T12:26:39Z) - Bandits with many optimal arms [68.17472536610859]
最適アームの割合は$p*$、最適アームとサブ最適化アームの間の最小平均ギャップは$Delta$と書きます。
我々は,累積的後悔設定と最良腕識別設定の両方において最適な学習率を特徴付ける。
論文 参考訳（メタデータ） (2021-03-23T11:02:31Z) - Near-Optimal Algorithms for Differentially Private Online Learning in a Stochastic Environment [7.4288915613206505]
本研究では,バンディットとフルインフォメーションの両方のフィードバックの下で,オンライン学習環境における個人差分問題について検討する。
差分的な私的盗賊に対しては、UTBとトンプソンサンプリングに基づくアルゴリズムを同時に提案し、最適な$O左(sum_j: Delta_j>0 fracln(T)min leftDelta_j, epsilon right)$ minimax lower boundとする。
同じ差分プライベートなフル情報設定に対しては、$epsilon$-differentially も提示する。
論文 参考訳（メタデータ） (2021-02-16T02:48:16Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。