論文の概要: Tight Rates for Bandit Control Beyond Quadratics
- arxiv url: http://arxiv.org/abs/2410.00993v1
- Date: Tue, 1 Oct 2024 18:35:08 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-04 23:49:57.046813
- Title: Tight Rates for Bandit Control Beyond Quadratics
- Title（参考訳）: 四面体を超える帯域制御のためのタイトレート
- Authors: Y. Jennifer Sun, Zhou Lu,
- Abstract要約: 目的を達成するアルゴリズムを開発する。
tildeO(T)$ は帯域非確率な滑らかな摂動関数に対する最適制御である。
私たちの主な貢献は、目的を達成するアルゴリズムです。
tildeO(T)$はメモリなしでBandit Convex(BCO)の最適制御である。
- 参考スコア（独自算出の注目度）: 2.961909021941052
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Unlike classical control theory, such as Linear Quadratic Control (LQC), real-world control problems are highly complex. These problems often involve adversarial perturbations, bandit feedback models, and non-quadratic, adversarially chosen cost functions. A fundamental yet unresolved question is whether optimal regret can be achieved for these general control problems. The standard approach to addressing this problem involves a reduction to bandit convex optimization with memory. In the bandit setting, constructing a gradient estimator with low variance is challenging due to the memory structure and non-quadratic loss functions. In this paper, we provide an affirmative answer to this question. Our main contribution is an algorithm that achieves an $\tilde{O}(\sqrt{T})$ optimal regret for bandit non-stochastic control with strongly-convex and smooth cost functions in the presence of adversarial perturbations, improving the previously known $\tilde{O}(T^{2/3})$ regret bound from (Cassel and Koren, 2020. Our algorithm overcomes the memory issue by reducing the problem to Bandit Convex Optimization (BCO) without memory and addresses general strongly-convex costs using recent advancements in BCO from (Suggala et al., 2024). Along the way, we develop an improved algorithm for BCO with memory, which may be of independent interest.
- Abstract（参考訳）: 線形二次制御(LQC)のような古典的な制御理論とは異なり、現実世界の制御問題は極めて複雑である。
これらの問題は、しばしば敵の摂動、盗賊のフィードバックモデル、および非四角形で反対に選択されたコスト関数を含む。
根本的な未解決の問題は、これらの一般的な制御問題に対して最適な後悔が達成できるかどうかである。
この問題に対処する標準的なアプローチは、メモリによる帯域の凸最適化を減らすことである。
帯域設定では、メモリ構造と非二次損失関数のために、低分散の勾配推定器を構築することが困難である。
本稿では,この問題に対する肯定的な回答を提供する。
我々の主な貢献は、強凸でスムーズなコスト関数を持つ非確率的制御を逆の摂動が存在する場合に、$\tilde{O}(\sqrt{T})$最適後悔を達成するアルゴリズムであり、これまで知られていた$\tilde{O}(T^{2/3})$後悔境界(Cassel and Koren, 2020)の改善である。
提案アルゴリズムは,BCOの最近の進歩(Suggala et al , 2024)を用いて,メモリを使用せずにBandit Convex Optimization (BCO) に問題を還元し,メモリの問題を克服する。
その過程で,BCO をメモリ付きで改良したアルゴリズムを開発した。
関連論文リスト
- Second Order Methods for Bandit Optimization and Control [34.51425758864638]
我々は,大規模な凸関数に対して,このアルゴリズムが最適($kappa$-2020と呼ぶ凸関数の観点で)となることを示す。
また,メモリを用いたオンライン凸最適化への2次帯域幅アルゴリズムの適用について検討した。
論文 参考訳（メタデータ） (2024-02-14T04:03:38Z) - Optimal Rates for Bandit Nonstochastic Control [18.47192040293437]
既知システムと未知システムの両方に対して最適な後悔(対数要因まで)を達成できる帯域幅LQRとLQGのアルゴリズムを提案する。
提案手法の中心的な構成要素は,メモリを用いたバンドベックス最適化のための新しい手法であり,これは独立した関心事である。
論文 参考訳（メタデータ） (2023-05-24T17:02:30Z) - Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear
Contextual Bandits and Markov Decision Processes [59.61248760134937]
本稿では,$tildeO(sqrtT+zeta)$を後悔するアルゴリズムを提案する。
提案アルゴリズムは、最近開発された線形文脈帯域からの不確実性重み付き最小二乗回帰に依存する。
本稿では,提案アルゴリズムをエピソディックなMDP設定に一般化し,まず汚職レベル$zeta$への付加的依存を実現する。
論文 参考訳（メタデータ） (2022-12-12T15:04:56Z) - Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regression [65.8785736964253]
本稿では,線形制約付きコンテキスト帯域(CBwLC)について考察する。これは,アルゴリズムが全消費の線形制約を受ける複数のリソースを消費するコンテキスト帯域の変種である。
この問題はknapsacks (CBwK) を用いてコンテキスト的帯域幅を一般化し、制約のパッケージ化とカバー、および正および負のリソース消費を可能にする。
本稿では,回帰オラクルに基づくCBwLC(CBwK)のアルゴリズムについて述べる。このアルゴリズムは単純で,計算効率が良く,統計的に最適である。
論文 参考訳（メタデータ） (2022-11-14T16:08:44Z) - Optimal Contextual Bandits with Knapsacks under Realizibility via
Regression Oracles [14.634964681825197]
我々は,knapsacks (CBwK) 問題を用いてコンテキスト的帯域幅について検討し,各行動がランダムな報酬をもたらす一方で,ベクトル形式のランダムなリソース消費を犠牲にしている。
本稿では,CBwKをオンライン回帰に還元することで,CBwKの汎用的かつ最適なアルゴリズムフレームワークを提案する。
論文 参考訳（メタデータ） (2022-10-21T09:28:53Z) - A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian
Process Bandits [118.22458816174144]
そこで本稿では,エポックで動作するロバストな除去型アルゴリズムを提案し,探索と頻繁な切替を併用して,小さなアクションサブセットを選択し,各アクションを複数タイミングで実行する。
我々のアルゴリズムであるGP Robust Phased Elimination (RGP-PE) は、探索とエクスプロイトによる汚職に対するロバストネスのバランスに成功している。
GPバンディット設定におけるロバスト性の最初の実証的研究を行い,アルゴリズムが様々な敵攻撃に対してロバストであることを示す。
論文 参考訳（メタデータ） (2022-02-03T21:19:36Z) - Efficient and Optimal Algorithms for Contextual Dueling Bandits under
Realizability [59.81339109121384]
我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。
提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
論文 参考訳（メタデータ） (2021-11-24T07:14:57Z) - Dynamic Regret Minimization for Control of Non-stationary Linear
Dynamical Systems [18.783925692307054]
本稿では,$tildemathcalO(sqrtST)$を最適にリセットするアルゴリズムを提案する。
本アルゴリズムの要点は適応的非定常性検出戦略であり,最近開発されたコンテキスト多重武装バンドイット問題に対するアプローチに基づいている。
論文 参考訳（メタデータ） (2021-11-06T01:30:51Z) - 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) - Bandit Linear Control [0.0]
ノイズ, 逆選択コスト, および帯域フィードバックの下で既知の線形力学系を制御することの問題点を考察する。
我々は,強い凸とスムーズなコストのために,時間的地平線の平方根で成長する後悔を得る,新しい効率的アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-07-01T21:12:19Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。