論文の概要: A Unifying Framework for Online Optimization with Long-Term Constraints
- arxiv url: http://arxiv.org/abs/2209.07454v1
- Date: Thu, 15 Sep 2022 16:59:19 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-16 13:39:07.706712
- Title: A Unifying Framework for Online Optimization with Long-Term Constraints
- Title（参考訳）: 長期制約を伴うオンライン最適化のための統一フレームワーク
- Authors: Matteo Castiglioni, Andrea Celli, Alberto Marchesi, Giulia Romano,
Nicola Gatti
- Abstract要約: 我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。
目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。
本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
- 参考スコア（独自算出の注目度）: 62.35194099438855
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study online learning problems in which a decision maker has to take a
sequence of decisions subject to $m$ long-term constraints. The goal of the
decision maker is to maximize their total reward, while at the same time
achieving small cumulative constraints violation across the $T$ rounds. We
present the first best-of-both-world type algorithm for this general class of
problems, with no-regret guarantees both in the case in which rewards and
constraints are selected according to an unknown stochastic model, and in the
case in which they are selected at each round by an adversary. Our algorithm is
the first to provide guarantees in the adversarial setting with respect to the
optimal fixed strategy that satisfies the long-term constraints. In particular,
it guarantees a $\rho/(1+\rho)$ fraction of the optimal reward and sublinear
regret, where $\rho$ is a feasibility parameter related to the existence of
strictly feasible solutions. Our framework employs traditional regret
minimizers as black-box components. Therefore, by instantiating it with an
appropriate choice of regret minimizers it can handle the full-feedback as well
as the bandit-feedback setting. Moreover, it allows the decision maker to
seamlessly handle scenarios with non-convex rewards and constraints. We show
how our framework can be applied in the context of budget-management mechanisms
for repeated auctions in order to guarantee long-term constraints that are not
packing (e.g., ROI constraints).
- Abstract（参考訳）: 我々は,意思決定者が長期的制約を課した一連の意思決定を行なわなければならないオンライン学習問題について検討する。
意思決定者の目標は、合計報酬を最大化すると同時に、t$ラウンド全体にわたる小さな累積制約違反を実現することだ。
本稿では,この一般的な問題に対して,未知の確率モデルに基づいて報酬と制約が選択される場合と,各ラウンドで敵が選択する場合の両方において,最良な両世界型アルゴリズムを提案する。
本アルゴリズムは, 長期的制約を満たす最適固定戦略に対して, 敵設定で保証を提供する最初のアルゴリズムである。
特に、$\rho/(1+\rho)$の最適報酬とサブ線形後悔の分数を保証するが、$\rho$は厳密に実現可能な解の存在に関連する実現可能性パラメータである。
当社のフレームワークでは、従来の後悔の最小化をブラックボックスコンポーネントとして採用しています。
したがって、後悔の最小化の適切な選択でインスタンス化することで、フルフィードバックとバンディットフィードバックの設定を処理できる。
さらに、意思決定者は非凸報酬と制約でシナリオをシームレスに処理できる。
私たちのフレームワークは、パッケージ化されていない長期的制約(ROI制約など)を保証するために、繰り返しオークションの予算管理メカニズムの文脈でどのように適用できるかを示します。
関連論文リスト
- Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints [29.514323697659613]
我々は,学習者が任意の長期制約を満たすことなく報酬を最大化することを目的とした,knapsacks問題によるバンディットの一般化に対処する。
私たちのゴールは、双方の制約の下で機能するベスト・オブ・ザ・ワールドのアルゴリズムを設計することです。
論文 参考訳（メタデータ） (2024-05-25T08:09:36Z) - No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization [26.415300249303748]
本研究は, 一次アルゴリズムと双対アルゴリズムを弱適応化させることにより, 制約のサブ線形違反を回避可能であることを示す。
最初のケースでは、アルゴリズムがサブ線形後悔を保証することを示し、後者の場合、厳密な競合比を$rho/(1+rho)$とする。
この結果から,線形制約付き文脈帯域問題に対する新たな結果が得られる。
論文 参考訳（メタデータ） (2024-05-10T16:22:33Z) - Online Learning under Budget and ROI Constraints via Weak Adaptivity [57.097119428915796]
制約付きオンライン学習問題に対する既存の原始双対アルゴリズムは、2つの基本的な仮定に依存している。
このような仮定は、標準の原始双対テンプレートを弱適応的後悔最小化器で与えることによって、どのように回避できるのかを示す。
上記の2つの前提が満たされていない場合に保証される、世界の最高の保証を証明します。
論文 参考訳（メタデータ） (2023-02-02T16:30:33Z) - Algorithm for Constrained Markov Decision Process with Linear
Convergence [55.41644538483948]
エージェントは、そのコストに対する複数の制約により、期待される累積割引報酬を最大化することを目的としている。
エントロピー正規化ポリシーとベイダの二重化という2つの要素を統合した新しい双対アプローチが提案されている。
提案手法は(線形速度で)大域的最適値に収束することが示されている。
論文 参考訳（メタデータ） (2022-06-03T16:26:38Z) - Online Learning with Knapsacks: the Best of Both Worlds [54.28273783164608]
オンライン学習の課題として,意思決定者が,リソース制約の有限セットに違反することなく,期待する報酬を最大化したい,という課題を提起する。
当社のフレームワークは,意思決定者がそのエビデンスを柔軟かつコスト論的に扱えるようにします。
論文 参考訳（メタデータ） (2022-02-28T12:10:48Z) - Safe Online Bid Optimization with Return-On-Investment and Budget
Constraints subject to Uncertainty [87.81197574939355]
最適化問題と学習問題の両方について検討する。
我々は、潜在的に線形な数の制約違反を犠牲にして、サブ線形後悔を保証するアルゴリズム、すなわちGCBを提供する。
より興味深いことに、我々はGCB_safe(psi,phi)というアルゴリズムを提供し、サブ線形擬似回帰と安全性w.h.p.の両方を、耐性 psi と phi を受け入れるコストで保証する。
論文 参考訳（メタデータ） (2022-01-18T17:24:20Z) - A Lyapunov-Based Methodology for Constrained Optimization with Bandit
Feedback [22.17503016665027]
各アクションが未知の関節分布からランダムな報酬、コスト、ペナルティを返す問題を考える。
我々は、$tt LyOn$という新しい低複雑さアルゴリズムを提案し、$O(sqrtBlog B)$ regretと$O(log B/B)$ constraint-violationを達成することを証明した。
計算コストの低い$tt LyOn$は、Lyapunovをベースとしたアルゴリズム設計手法が制約付き帯域最適化問題の解決に有効であることを示唆している。
論文 参考訳（メタデータ） (2021-06-09T16:12:07Z) - On Lower Bounds for Standard and Robust Gaussian Process Bandit
Optimization [55.937424268654645]
有界ノルムを持つ関数のブラックボックス最適化問題に対するアルゴリズム非依存な下界を考える。
本稿では, 単純さ, 汎用性, エラー確率への依存性の向上など, 後悔の下位境界を導出するための新しい証明手法を提案する。
論文 参考訳（メタデータ） (2020-08-20T03:48:14Z) - Model-Free Algorithm and Regret Analysis for MDPs with Long-Term
Constraints [38.2783003051101]
本稿では,制約付き最適化とQ-ラーニングの概念を用いて,長期制約付きCMDPのアルゴリズムを提案する。
本研究は, 長期的制約を伴うMDPの遺残分析における最初の結果であり, 遷移確率はアプリオリではないことに留意する。
論文 参考訳（メタデータ） (2020-06-10T17:19:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。