論文の概要: Second Order Methods for Bandit Optimization and Control
- arxiv url: http://arxiv.org/abs/2402.08929v1
- Date: Wed, 14 Feb 2024 04:03:38 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-15 16:55:21.818798
- Title: Second Order Methods for Bandit Optimization and Control
- Title（参考訳）: バンディット最適化と制御のための二階法
- Authors: Arun Suggala, Y. Jennifer Sun, Praneeth Netrapalli, Elad Hazan
- Abstract要約: 我々は,大規模な凸関数に対して,このアルゴリズムが最適($kappa$-2020と呼ぶ凸関数の観点で)となることを示す。
また,メモリを用いたオンライン凸最適化への2次帯域幅アルゴリズムの適用について検討した。
- 参考スコア（独自算出の注目度）: 37.70434692823672
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Bandit convex optimization (BCO) is a general framework for online decision
making under uncertainty. While tight regret bounds for general convex losses
have been established, existing algorithms achieving these bounds have
prohibitive computational costs for high dimensional data.
In this paper, we propose a simple and practical BCO algorithm inspired by
the online Newton step algorithm. We show that our algorithm achieves optimal
(in terms of horizon) regret bounds for a large class of convex functions that
we call $\kappa$-convex. This class contains a wide range of practically
relevant loss functions including linear, quadratic, and generalized linear
models. In addition to optimal regret, this method is the most efficient known
algorithm for several well-studied applications including bandit logistic
regression.
Furthermore, we investigate the adaptation of our second-order bandit
algorithm to online convex optimization with memory. We show that for loss
functions with a certain affine structure, the extended algorithm attains
optimal regret. This leads to an algorithm with optimal regret for bandit
LQR/LQG problems under a fully adversarial noise model, thereby resolving an
open question posed in \citep{gradu2020non} and \citep{sun2023optimal}.
Finally, we show that the more general problem of BCO with (non-affine)
memory is harder. We derive a $\tilde{\Omega}(T^{2/3})$ regret lower bound,
even under the assumption of smooth and quadratic losses.
- Abstract（参考訳）: bandit convex optimization (bco) は不確実性下でのオンライン意思決定のための一般的なフレームワークである。
一般凸損失に対する厳密な後悔境界が確立されている一方で、これらの境界を達成する既存のアルゴリズムは高次元データに対する計算コストを禁ずる。
本稿では,オンラインニュートンステップアルゴリズムにヒントを得た,シンプルで実用的なBCOアルゴリズムを提案する。
我々は,このアルゴリズムが,$\kappa$-convexと呼ぶ凸関数の大規模なクラスに対して最適な(水平方向の)後悔境界を実現することを示す。
このクラスは、線形、二次、一般化された線形モデルを含む、幅広い実用的な損失関数を含む。
最適後悔に加えて、この手法はバンドロジスティック回帰を含むいくつかのよく研究されたアプリケーションにとって最も効率的なアルゴリズムである。
さらに,2次バンディットアルゴリズムのオンライン凸最適化への適応について検討した。
特定のアフィン構造を持つ損失関数に対しては,拡張アルゴリズムが最適後悔が得られることを示す。
これにより、完全に逆方向の雑音モデルの下でのLQR/LQG問題に対する最適な後悔を伴うアルゴリズムが導かれ、それによって \citep{gradu2020non} と \citep{sun2023optimal} で表されるオープンな疑問が解決される。
最後に、(非アフィン)メモリによるbcoのより一般的な問題は困難であることを示す。
滑らかで二次的な損失の仮定の下でも、$\tilde{\Omega}(T^{2/3})$ regret lower bound を導出する。
関連論文リスト
- Best-of-Both-Worlds Policy Optimization for CMDPs with Bandit Feedback [34.7178680288326]
Stradi et al.(2024) は、マルコフ決定過程に制約のある最初のベスト・オブ・ボス・ワールドズ・アルゴリズムを提案した。
本稿では,CMDPにおける帯域幅フィードバックを用いたベスト・オブ・ワールドズ・アルゴリズムを提案する。
本アルゴリズムは政策最適化手法に基づいており, 占有率に基づく手法よりも効率的である。
論文 参考訳（メタデータ） (2024-10-03T07:44:40Z) - Riemannian Projection-free Online Learning [5.918057694291832]
プロジェクション操作は、オンライン勾配降下(OGD)のような最適化アルゴリズムにおける重要な要素である。
これは高次元の設定における計算上の制限や、不条件の制約セットを扱う際に悩まされる。
本稿では,曲面空間上でのオンライン測地線凸最適化において,線形後悔の保証を得る手法を提案する。
論文 参考訳（メタデータ） (2023-05-30T18:22:09Z) - Projection-free Adaptive Regret with Membership Oracles [31.422532403048738]
ほとんどの反復アルゴリズムは凸集合への射影の計算を必要とし、計算コストがかかる。
GK22による最近の研究は、フランク・ウルフのアプローチに基づく射影自由アルゴリズムによる準線形適応的後悔の保証を与えた。
我々はMhammedi22にインスパイアされた異なる手法に基づくプロジェクションフリーなアルゴリズムを提案し、プロジェクションをセットメンバーシップ計算で置き換える。
論文 参考訳（メタデータ） (2022-11-22T23:53:06Z) - Efficient and Optimal Algorithms for Contextual Dueling Bandits under
Realizability [59.81339109121384]
我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。
提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
論文 参考訳（メタデータ） (2021-11-24T07:14:57Z) - Adapting to Misspecification in Contextual Bandits [82.55565343668246]
我々は、$varepsilon$-misspecified contextual banditsに対して、新しいオラクル効率アルゴリズム群を導入する。
我々は、未知の不特定値に対して最適な$O(dsqrtT + varepsilonsqrtdT)$ regret boundを達成する最初のアルゴリズムを得る。
論文 参考訳（メタデータ） (2021-07-12T21:30:41Z) - Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。
我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。
標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
論文 参考訳（メタデータ） (2021-07-09T16:04:24Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z) - Efficient Optimistic Exploration in Linear-Quadratic Regulators via
Lagrangian Relaxation [107.06364966905821]
線形2次レギュレータ(LQR)設定における探索・探索ジレンマについて検討した。
有限 MDP に対する楽観的アルゴリズムで用いられる拡張値反復アルゴリズムに着想を得て,Oulq の楽観的最適化を緩和することを提案する。
我々は、少なくとも$Obig(log (1/epsilon)big)$ Riccati方程式を解くことで、$epsilon$-OptimisticControllerを効率的に計算できることを示した。
論文 参考訳（メタデータ） (2020-07-13T16:30:47Z) - Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
基本アルゴリズムを選択できるメタアルゴリズムを開発した。
基本アルゴリズムの1つが$O(sqrtT)$後悔している場合でも、一般的には$Omega(sqrtT)$後悔よりも良いものを得ることはできません。
論文 参考訳（メタデータ） (2020-03-03T18:46:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。