論文の概要: Better Best of Both Worlds Bounds for Bandits with Switching Costs
- arxiv url: http://arxiv.org/abs/2206.03098v1
- Date: Tue, 7 Jun 2022 08:22:56 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-08 15:41:35.365732
- Title: Better Best of Both Worlds Bounds for Bandits with Switching Costs
- Title（参考訳）: バンディットと交換コストの両世界のバウンドの良さ
- Authors: Idan Amir, Guy Azov, Tomer Koren, Roi Livni
- Abstract要約: 本稿では,2021年にRouryer,Seldin,Cesa-Bianchiらにより,スイッチングコストを伴うバンディットのベスト・オブ・ザ・ワールドス・アルゴリズムについて検討した。
本稿では, 極小最小の最小残差を$mathcalO(T2/3)$で同時に達成する, 驚くほど単純かつ効果的に導入する。
- 参考スコア（独自算出の注目度）: 37.71741656687868
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study best-of-both-worlds algorithms for bandits with switching cost,
recently addressed by Rouyer, Seldin and Cesa-Bianchi, 2021. We introduce a
surprisingly simple and effective algorithm that simultaneously achieves
minimax optimal regret bound of $\mathcal{O}(T^{2/3})$ in the oblivious
adversarial setting and a bound of $\mathcal{O}(\min\{\log
(T)/\Delta^2,T^{2/3}\})$ in the stochastically-constrained regime, both with
(unit) switching costs, where $\Delta$ is the gap between the arms. In the
stochastically constrained case, our bound improves over previous results due
to Rouyer et al., that achieved regret of $\mathcal{O}(T^{1/3}/\Delta)$. We
accompany our results with a lower bound showing that, in general,
$\tilde{\Omega}(\min\{1/\Delta^2,T^{2/3}\})$ regret is unavoidable in the
stochastically-constrained case for algorithms with $\mathcal{O}(T^{2/3})$
worst-case regret.
- Abstract（参考訳）: 本稿では,2021年にRouryer,Seldin,Cesa-Bianchiらにより,スイッチングコストを伴うバンディットのベスト・オブ・ワールドスアルゴリズムについて検討した。
両腕を切り替える(単位)スイッチングコストの両面において、両腕の両腕の間隙を$\Delta$とすると、両腕の両腕を交互に制限した状態において$\mathcal{O}(T^{2/3})$と$\mathcal{O}(\min\{\log (T)/T^{2/3}\})$を同時に達成する、驚くほど単純で効果的なアルゴリズムを導入する。
確率的に制約された場合、我々の境界は、$\mathcal{O}(T^{1/3}/\Delta)$を後悔したRoyerらによる以前の結果よりも改善される。
一般に、$\tilde{\Omega}(\min\{1/\Delta^2,T^{2/3}\})$ regretは、$\mathcal{O}(T^{2/3})$ worst-case regretを持つアルゴリズムの確率的に制約されたケースでは避けられない。
関連論文リスト
- Adversarial Combinatorial Bandits with Switching Costs [55.2480439325792]
本稿では,各ラウンドで選択したアームのスイッチに対して,切替コストが$lambda$の逆帯域問題について検討する。
ミニマックスの後悔とそれにアプローチするための設計アルゴリズムの限界を低くする。
論文 参考訳（メタデータ） (2024-04-02T12:15:37Z) - 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) - Best-of-Both-Worlds Algorithms for Linear Contextual Bandits [11.94312915280916]
両世界のベスト・オブ・ワールドズ・アルゴリズムを$K$武器付き線形文脈包帯に対して検討する。
我々のアルゴリズムは、敵対的体制と敵対的体制の両方において、ほぼ最適の後悔の限界を提供する。
論文 参考訳（メタデータ） (2023-12-24T08:27:30Z) - Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback [30.337826346496385]
線形マルコフ決定過程におけるオンライン強化学習について,敵対的損失と帯域幅フィードバックを用いて検討した。
既存の手法と比較して、後悔性能を向上させるアルゴリズムを2つ導入する。
論文 参考訳（メタデータ） (2023-10-17T19:43:37Z) - Tight Regret Bounds for Single-pass Streaming Multi-armed Bandits [3.5955736977697073]
K$アームと$T$トライアルを持つシングルパス設定では、$o(K)$メモリを持つ任意のアルゴリズムに対して、後悔の少ない$Omega(T2/3)$が証明されている。
本稿では,o(K)$メモリを持つアルゴリズムに対して,Omega(K/3log/3(T))$に制限された後悔の低減を図る。
提案アルゴリズムはベンチマーク均一探索アルゴリズムを大きなマージンで一貫して上回り、時には後悔を最大70%削減することを示した。
論文 参考訳（メタデータ） (2023-06-03T22:41:44Z) - Borda Regret Minimization for Generalized Linear Dueling Bandits [65.09919504862496]
本稿では,ボルダスコアが最も高い項目を識別することを目的とした,デュエルバンディットに対するボルダ後悔最小化問題について検討する。
本稿では,多くの既存モデルをカバーする一般化線形デュエルバンドモデルのリッチクラスを提案する。
我々のアルゴリズムは$tildeO(d2/3 T2/3)$ regretを達成し、これも最適である。
論文 参考訳（メタデータ） (2023-03-15T17:59:27Z) - 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) - An Algorithm for Stochastic and Adversarial Bandits with Switching Costs [10.549307055348596]
そこで本研究では,マルチアームバンディットのスイッチングコストを考慮したアルゴリズムを提案し,そのアルゴリズムがアームを切り替える度に$lambda$を支払う。
私たちのアルゴリズムは、Zimmert and Seldin(2021)のTsallis-INFアルゴリズムの適応に基づいています。
論文 参考訳（メタデータ） (2021-02-19T11:03:51Z) - Adversarial Dueling Bandits [85.14061196945599]
本稿では,反逆デュエルバンドにおける後悔の問題を紹介する。
学習者は、繰り返し一対のアイテムを選択し、このペアに対する相対的な二項利得フィードバックのみを観察しなければならない。
我々の主な成果は、EmphBorda-winnerの1組の$K$アイテムと比較して、T$ラウンド後悔するアルゴリズムです。
論文 参考訳（メタデータ） (2020-10-27T19:09:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。