論文の概要: Adaptive Regret for Bandits Made Possible: Two Queries Suffice
- arxiv url: http://arxiv.org/abs/2401.09278v1
- Date: Wed, 17 Jan 2024 15:32:04 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-18 15:23:42.784951
- Title: Adaptive Regret for Bandits Made Possible: Two Queries Suffice
- Title（参考訳）: バンディットに対する適応的後悔:2つのクエリで十分
- Authors: Zhou Lu, Qiuyi Zhang, Xinyi Chen, Fred Zhang, David Woodruff, Elad
Hazan
- Abstract要約: 我々は、強い適応的後悔という厳密な概念の下で、クエリと後悔の最適包帯アルゴリズムを与える。
驚いたことに、1ラウンドあたり2つのクエリで$tildeO(sqrtn|I|)$ Adaptive Bandit Learner(StABL)を達成できる。
- 参考スコア（独自算出の注目度）: 26.769372199571002
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Fast changing states or volatile environments pose a significant challenge to
online optimization, which needs to perform rapid adaptation under limited
observation. In this paper, we give query and regret optimal bandit algorithms
under the strict notion of strongly adaptive regret, which measures the maximum
regret over any contiguous interval $I$. Due to its worst-case nature, there is
an almost-linear $\Omega(|I|^{1-\epsilon})$ regret lower bound, when only one
query per round is allowed [Daniely el al, ICML 2015]. Surprisingly, with just
two queries per round, we give Strongly Adaptive Bandit Learner (StABL) that
achieves $\tilde{O}(\sqrt{n|I|})$ adaptive regret for multi-armed bandits with
$n$ arms. The bound is tight and cannot be improved in general. Our algorithm
leverages a multiplicative update scheme of varying stepsizes and a carefully
chosen observation distribution to control the variance. Furthermore, we extend
our results and provide optimal algorithms in the bandit convex optimization
setting. Finally, we empirically demonstrate the superior performance of our
algorithms under volatile environments and for downstream tasks, such as
algorithm selection for hyperparameter optimization.
- Abstract（参考訳）: 高速な変化状態や揮発性環境は、限られた観測の下で迅速な適応を行う必要があるオンライン最適化に重大な課題をもたらす。
本稿では,連続区間$i$ に対して最大後悔を計測する,強い適応的後悔という厳密な概念の下で,クエリと後悔の最適バンディットアルゴリズムを与える。
最悪の場合の性質のため、[Daniely el al, ICML 2015] 1ラウンドあたりのクエリしか許可されていない場合、ほとんど線形の$\Omega(|I|^{1-\epsilon})$ regret lower boundがある。
驚いたことに、1ラウンドに2つのクエリしか持たないStrongly Adaptive Bandit Learner (StABL)が$\tilde{O}(\sqrt{n|I|})$Adaptive regret for multi-armed bandits with $n$ arms。
境界は厳密であり、一般には改善できない。
本アルゴリズムは,様々な段数の乗法的更新方式と慎重に選択された観測分布を利用して分散を制御する。
さらに,この結果を拡張し,bandit convex最適化設定において最適なアルゴリズムを提供する。
最後に,過パラメータ最適化のためのアルゴリズム選択などの下流タスクにおいて,揮発性環境下でのアルゴリズムの優れた性能を実証する。
関連論文リスト
- Second Order Methods for Bandit Optimization and Control [34.51425758864638]
我々は,大規模な凸関数に対して,このアルゴリズムが最適($kappa$-2020と呼ぶ凸関数の観点で)となることを示す。
また,メモリを用いたオンライン凸最適化への2次帯域幅アルゴリズムの適用について検討した。
論文 参考訳（メタデータ） (2024-02-14T04:03:38Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive
Regret Bounds [27.92755687977196]
本稿では,2つの階層の環境に適応する線形帯域幅アルゴリズムを提案する。
高いレベルでは、提案アルゴリズムは様々な種類の環境に適応する。
提案アルゴリズムは、最適動作に対する累積損失のすべてに依存する、データ依存の後悔境界を有する。
論文 参考訳（メタデータ） (2023-02-24T00:02:24Z) - Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement
Learning: Adaptivity and Computational Efficiency [90.40062452292091]
本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。
我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。
また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-21T00:17:24Z) - ANACONDA: An Improved Dynamic Regret Algorithm for Adaptive
Non-Stationary Dueling Bandits [20.128001589147512]
本研究では,非定常デュエル帯域の問題について検討し,この問題に対する適応的動的後悔アルゴリズムを提案する。
ほぼ最適の $tildeO(sqrtStexttCW T)$ dynamic regret bound を示します。
論文 参考訳（メタデータ） (2022-10-25T20:26:02Z) - Efficient and Optimal Algorithms for Contextual Dueling Bandits under
Realizability [59.81339109121384]
我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。
提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
論文 参考訳（メタデータ） (2021-11-24T07:14:57Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z) - Lazy OCO: Online Convex Optimization on a Switching Budget [34.936641201844054]
我々は、オンライン凸最適化の変形について研究し、プレイヤーは、T$ラウンドを通して、最大$S$で決定を切り替えることを許されている。
離散的な決定セットの事前の作業や、より最近の連続的な設定では、適応的な逆数でのみ、同様の問題が解決されている。
論文 参考訳（メタデータ） (2021-02-07T14:47:19Z) - Lenient Regret for Multi-Armed Bandits [72.56064196252498]
エージェントが順番に行動を選択し、その行動に対する報酬を観察するマルチアーマッド・バンディット(MAB)問題を考察する。
アルゴリズムの大多数は、後悔、すなわち最高の行動の報酬とエージェントの行動の累積的な差を最小化しようとするが、この基準は望ましくない結果をもたらすかもしれない。
我々は、いくつかの$epsilon$よりも小さな最適性ギャップを無視した、より寛大で寛大で後悔すべき基準を提案する。
論文 参考訳（メタデータ） (2020-08-10T08:30:52Z) - Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。
いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。
文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
論文 参考訳（メタデータ） (2020-07-07T09:00:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。