論文の概要: Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints
- arxiv url: http://arxiv.org/abs/2405.16118v1
- Date: Sat, 25 May 2024 08:09:36 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-29 01:00:23.534598
- Title: Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints
- Title（参考訳）: 確率的・対角的制約のある帯域における最小2次元法を超えて
- Authors: Martino Bernasconi, Matteo Castiglioni, Andrea Celli, Federico Fusco,
- Abstract要約: 我々は,学習者が任意の長期制約を満たすことなく報酬を最大化することを目的とした,knapsacks問題によるバンディットの一般化に対処する。
私たちのゴールは、双方の制約の下で機能するベスト・オブ・ザ・ワールドのアルゴリズムを設計することです。
- 参考スコア（独自算出の注目度）: 29.514323697659613
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We address a generalization of the bandit with knapsacks problem, where a learner aims to maximize rewards while satisfying an arbitrary set of long-term constraints. Our goal is to design best-of-both-worlds algorithms that perform optimally under both stochastic and adversarial constraints. Previous works address this problem via primal-dual methods, and require some stringent assumptions, namely the Slater's condition, and in adversarial settings, they either assume knowledge of a lower bound on the Slater's parameter, or impose strong requirements on the primal and dual regret minimizers such as requiring weak adaptivity. We propose an alternative and more natural approach based on optimistic estimations of the constraints. Surprisingly, we show that estimating the constraints with an UCB-like approach guarantees optimal performances. Our algorithm consists of two main components: (i) a regret minimizer working on \emph{moving strategy sets} and (ii) an estimate of the feasible set as an optimistic weighted empirical mean of previous samples. The key challenge in this approach is designing adaptive weights that meet the different requirements for stochastic and adversarial constraints. Our algorithm is significantly simpler than previous approaches, and has a cleaner analysis. Moreover, ours is the first best-of-both-worlds algorithm providing bounds logarithmic in the number of constraints. Additionally, in stochastic settings, it provides $\widetilde O(\sqrt{T})$ regret \emph{without} Slater's condition.
- Abstract（参考訳）: 我々は,学習者が任意の長期制約を満たすことなく報酬を最大化することを目的とした,knapsacks問題によるバンディットの一般化に対処する。
我々のゴールは、確率的制約と対角的制約の両方の下で最適に動作するベスト・オブ・ザ・ワールドのアルゴリズムを設計することである。
従来の研究は原始双対法によってこの問題に対処し、いくつかの厳密な仮定、すなわちスレーターの条件、および逆条件では、スレーターのパラメータの下位境界の知識を仮定するか、あるいは弱適応性を必要とするような原始的および二重後悔最小化に強い要件を課す。
本稿では,制約の楽観的な推定に基づく,より自然なアプローチを提案する。
驚いたことに、UCBのようなアプローチで制約を見積もると、最適な性能が保証される。
アルゴリズムは2つの主成分から構成される。
i) \emph{moving strategy set} で作業する後悔の最小化器と
(ii) 前回のサンプルの楽観的な重み付き実験平均として実現可能な集合の推定。
このアプローチの鍵となる課題は、確率的および対角的制約の異なる要件を満たす適応重みを設計することである。
我々のアルゴリズムは従来の手法よりもはるかに単純で、よりクリーンな分析ができる。
さらに,制約数における境界対数性を備えた世界最強のアルゴリズムは,本アルゴリズムが初めてである。
さらに確率的設定では、$\widetilde O(\sqrt{T})$ regret \emph{without} Slater の条件を提供する。
関連論文リスト
- No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization [26.415300249303748]
本研究は, 一次アルゴリズムと双対アルゴリズムを弱適応化させることにより, 制約のサブ線形違反を回避可能であることを示す。
最初のケースでは、アルゴリズムがサブ線形後悔を保証することを示し、後者の場合、厳密な競合比を$rho/(1+rho)$とする。
この結果から,線形制約付き文脈帯域問題に対する新たな結果が得られる。
論文 参考訳（メタデータ） (2024-05-10T16:22:33Z) - Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates
and Practical Features [79.39965431772626]
Frank-Wolfe (FW) 法は、構造化制約による最適化問題の解法として一般的な手法である。
有限サム勾配の最小化のためのアルゴリズムの2つの新しい変種を示す。
論文 参考訳（メタデータ） (2023-04-23T20:05:09Z) - A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。
目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。
本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
論文 参考訳（メタデータ） (2022-09-15T16:59:19Z) - On Kernelized Multi-Armed Bandits with Constraints [16.102401271318012]
一般に未知の報酬関数と一般未知の制約関数を併用した帯域幅問題について検討する。
本稿では,アルゴリズムの性能解析のための一般的なフレームワークを提案する。
本稿では,数値実験により提案アルゴリズムの優れた性能を示す。
論文 参考訳（メタデータ） (2022-03-29T14:02:03Z) - Concave Utility Reinforcement Learning with Zero-Constraint Violations [43.29210413964558]
本稿では,凸制約を伴うCURL(Concave utility reinforcement Learning)の問題点について考察する。
制約違反をゼロにするモデルベース学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-12T06:13:33Z) - Near-Optimal High Probability Complexity Bounds for Non-Smooth
Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
既存の非滑らか凸最適化法は、負のパワーまたは対数的な信頼度に依存する境界の複雑さを持つ。
クリッピングを用いた2つの勾配法に対して, 新たなステップサイズルールを提案する。
論文 参考訳（メタデータ） (2021-06-10T17:54:21Z) - Constraint-Handling Techniques for Particle Swarm Optimization
Algorithms [0.0]
人口ベースの手法は、従来の方法よりもはるかに複雑な問題を含む、さまざまな問題に対処することができる。
本研究の目的は,アルゴリズムに汎用的な設定を組み込んだPSOに適したCHTを開発し,比較することである。
論文 参考訳（メタデータ） (2021-01-25T01:49:10Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳（メタデータ） (2020-10-23T09:12:47Z) - On Lower Bounds for Standard and Robust Gaussian Process Bandit
Optimization [55.937424268654645]
有界ノルムを持つ関数のブラックボックス最適化問題に対するアルゴリズム非依存な下界を考える。
本稿では, 単純さ, 汎用性, エラー確率への依存性の向上など, 後悔の下位境界を導出するための新しい証明手法を提案する。
論文 参考訳（メタデータ） (2020-08-20T03:48:14Z) - Structure Adaptive Algorithms for Stochastic Bandits [22.871155520200773]
構造化多武装バンディット問題のクラスにおける報酬最大化について検討する。
平均的な武器の報酬は、与えられた構造的制約を満たす。
我々は、反復的なサドルポイントソルバを用いて、インスタンス依存の低バウンドからのアルゴリズムを開発する。
論文 参考訳（メタデータ） (2020-07-02T08:59:54Z) - The Simulator: Understanding Adaptive Sampling in the
Moderate-Confidence Regime [52.38455827779212]
エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。
適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。
我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
論文 参考訳（メタデータ） (2017-02-16T23:42:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。