論文の概要: No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization
- arxiv url: http://arxiv.org/abs/2405.06575v1
- Date: Fri, 10 May 2024 16:22:33 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-13 15:18:23.361027
- Title: No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization
- Title（参考訳）: 適応レグレット最小化による一般制約付き帯域
- Authors: Martino Bernasconi, Matteo Castiglioni, Andrea Celli,
- Abstract要約: 本研究は, 一次アルゴリズムと双対アルゴリズムを弱適応化させることにより, 制約のサブ線形違反を回避可能であることを示す。
最初のケースでは、アルゴリズムがサブ線形後悔を保証することを示し、後者の場合、厳密な競合比を$rho/(1+rho)$とする。
この結果から,線形制約付き文脈帯域問題に対する新たな結果が得られる。
- 参考スコア（独自算出の注目度）: 26.415300249303748
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In the bandits with knapsacks framework (BwK) the learner has $m$ resource-consumption (packing) constraints. We focus on the generalization of BwK in which the learner has a set of general long-term constraints. The goal of the learner is to maximize their cumulative reward, while at the same time achieving small cumulative constraints violations. In this scenario, there exist simple instances where conventional methods for BwK fail to yield sublinear violations of constraints. We show that it is possible to circumvent this issue by requiring the primal and dual algorithm to be weakly adaptive. Indeed, even in absence on any information on the Slater's parameter $\rho$ characterizing the problem, the interplay between weakly adaptive primal and dual regret minimizers yields a "self-bounding" property of dual variables. In particular, their norm remains suitably upper bounded across the entire time horizon even without explicit projection steps. By exploiting this property, we provide best-of-both-worlds guarantees for stochastic and adversarial inputs. In the first case, we show that the algorithm guarantees sublinear regret. In the latter case, we establish a tight competitive ratio of $\rho/(1+\rho)$. In both settings, constraints violations are guaranteed to be sublinear in time. Finally, this results allow us to obtain new result for the problem of contextual bandits with linear constraints, providing the first no-$\alpha$-regret guarantees for adversarial contexts.
- Abstract（参考訳）: knapsacksフレームワーク(BwK)の帯域内では、学習者はリソース消費(パッケージング)の制約が$m$である。
我々は、学習者が一般的な長期的制約の集合を持つBwKの一般化に焦点をあてる。
学習者の目標は累積報酬を最大化し、同時に最小限の累積制約違反を達成することである。
このシナリオでは、BwKの従来の手法が制約のサブ線形違反を生じさせない単純な例が存在する。
原始アルゴリズムと双対アルゴリズムを弱適応化させることにより,この問題を回避することができることを示す。
実際、問題を特徴づけるスレーターのパラメータ $\rho$ の情報がないとしても、弱適応的原始最小値と双対後悔最小値の間の相互作用は双対変数の「自己有界な」性質をもたらす。
特に、それらのノルムは、明示的な射影ステップがなくても、時間的地平線全体にわたって好適に上界を保っている。
この特性を利用することで、確率的および対角的な入力に対して、両世界の最良の保証を提供する。
第1のケースでは,アルゴリズムがサブ線形後悔を保証することを示す。
後者の場合、厳密な競合比は$\rho/(1+\rho)$とする。
どちらの設定でも、制約違反は時間内にサブリニアになることが保証される。
最後に,線形制約付き文脈的包帯問題に対する新たな結果を得ることができ,対数的文脈に対する最初のNo-$$\alpha$-regret保証を提供する。
関連論文リスト
- Rate-Preserving Reductions for Blackwell Approachability [72.03309261614991]
Abernethy et al. (2011) はブラックウェルのアプローチ可能性と非回帰学習が等価であることを示した。
一般化された後悔最小化の例に対して、いかなるアプローチ可能性のインスタンスも厳格に削減できることが示される。
論文 参考訳（メタデータ） (2024-06-10T23:23:52Z) - Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints [29.514323697659613]
我々は,学習者が任意の長期制約を満たすことなく報酬を最大化することを目的とした,knapsacks問題によるバンディットの一般化に対処する。
私たちのゴールは、双方の制約の下で機能するベスト・オブ・ザ・ワールドのアルゴリズムを設計することです。
論文 参考訳（メタデータ） (2024-05-25T08:09:36Z) - Analyzing and Improving Greedy 2-Coordinate Updates for
Equality-Constrained Optimization via Steepest Descent in the 1-Norm [12.579063422860072]
我々は,この問題に対する2座標更新と,1ノルムにおける等式制約付き急降下との接続を利用する。
次に、サポートベクトルマシン双対問題において生じるような、和制約と有界制約の両方で最小化を検討する。
論文 参考訳（メタデータ） (2023-07-03T17:27:18Z) - 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) - A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。
目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。
本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
論文 参考訳（メタデータ） (2022-09-15T16:59:19Z) - Non-stationary Bandits with Knapsacks [6.2006721306998065]
非定常環境におけるクナプサック(BwK)による包帯問題について検討する。
我々は、この問題の上下境界を導出するために、非定常対策を両方採用する。
論文 参考訳（メタデータ） (2022-05-25T01:22:36Z) - On Kernelized Multi-Armed Bandits with Constraints [16.102401271318012]
一般に未知の報酬関数と一般未知の制約関数を併用した帯域幅問題について検討する。
本稿では,アルゴリズムの性能解析のための一般的なフレームワークを提案する。
本稿では,数値実験により提案アルゴリズムの優れた性能を示す。
論文 参考訳（メタデータ） (2022-03-29T14:02:03Z) - On Lower Bounds for Standard and Robust Gaussian Process Bandit
Optimization [55.937424268654645]
有界ノルムを持つ関数のブラックボックス最適化問題に対するアルゴリズム非依存な下界を考える。
本稿では, 単純さ, 汎用性, エラー確率への依存性の向上など, 後悔の下位境界を導出するための新しい証明手法を提案する。
論文 参考訳（メタデータ） (2020-08-20T03:48:14Z) - Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。
いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。
文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
論文 参考訳（メタデータ） (2020-07-07T09:00:57Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。