論文の概要: Playing in the Dark: No-regret Learning with Adversarial Constraints

• arxiv url: http://arxiv.org/abs/2310.18955v1
• Date: Sun, 29 Oct 2023 09:55:41 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-31 15:16:07.459669
• Title: Playing in the Dark: No-regret Learning with Adversarial Constraints
• Title（参考訳）: 暗闇の中で演奏する: 敵対的制約による非回帰学習
• Authors: Abhishek Sinha and Rahul Vaze
• Abstract要約: 本稿では,従来のオンライン凸最適化(OCO)フレームワークの長期的制約を考慮した一般化について検討する。 我々は,任意のOCOポリシを用いて代理問題を解くことで,最適な性能境界を実現することができることを示す。 新たなリャプノフに基づく証明手法が提示され、後悔と特定の逐次不等式の間の関係を明らかにする。
• 参考スコア（独自算出の注目度）: 20.077237398506536
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We study a generalization of the classic Online Convex Optimization (OCO) framework by considering additional long-term adversarial constraints. Specifically, after an online policy decides its action on a round, in addition to a convex cost function, the adversary also reveals a set of $k$ convex constraints. The cost and the constraint functions could change arbitrarily with time, and no information about the future functions is assumed to be available. In this paper, we propose a meta-policy that simultaneously achieves a sublinear cumulative constraint violation and a sublinear regret. This is achieved via a black box reduction of the constrained problem to the standard OCO problem for a recursively constructed sequence of surrogate cost functions. We show that optimal performance bounds can be achieved by solving the surrogate problem using any adaptive OCO policy enjoying a standard data-dependent regret bound. A new Lyapunov-based proof technique is presented that reveals a connection between regret and certain sequential inequalities through a novel decomposition result. We conclude the paper by highlighting applications to online multi-task learning and network control problems.
• Abstract（参考訳）: オンライン凸最適化(oco)フレームワークの長期的制約を考慮した一般化について検討する。 具体的には、オンラインポリシーがラウンドでのアクションを決定すると、凸コスト関数に加えて、敵は一連の$k$凸制約も明らかにする。 コストと制約関数は時間とともに任意に変化する可能性があり、将来の機能に関する情報は得られないと仮定されている。 本稿では,sublinear cumulative constraints violation とsublinear regret を同時に達成するメタポリシーを提案する。 これは、サロゲートコスト関数の再帰的に構築されたシーケンスの標準oco問題に対する制約付き問題のブラックボックス還元によって達成される。 本稿では,標準データ依存の後悔境界を享受する任意の適応型ocoポリシーを用いてサロゲート問題を解くことで,最適性能境界を実現できることを示す。 新たな分解結果を通じて,後悔とある連続的不等式との関係を明らかにする新しいリアプノフに基づく証明手法を提案する。 本稿は、オンラインマルチタスク学習およびネットワーク制御問題への応用を強調して結論付ける。

関連論文リスト

• $O(\sqrt{T})$ Static Regret and Instance Dependent Constraint Violation for Constrained Online Convex Optimization [16.99491218081617]
  目的は、静的な後悔と累積的制約違反(CCV)を同時に最小化することである。 アルゴリズムは、$O(sqrtT)$と$mincV, O(sqrtTlog T)$のCCVの静的後悔を保証する。
  論文  参考訳（メタデータ） (2025-02-07T15:47:04Z)
• Projection-free Algorithms for Online Convex Optimization with Adversarial Constraints [10.047668792033033]
  本稿では,オンライン凸最適化(OCO)フレームワークの時間的逆制約による一般化について検討する。 この問題では、凸判定セットから実行可能な動作を選択した後、各ラウンドのコスト関数とともに凸制約関数を$X,$とする。 我々は,一ラウンドに1回,線形プログラム(LP)ソルバに1回コールする*プロジェクションフリー*オンラインポリシーを提案する。
  論文  参考訳（メタデータ） (2025-01-28T13:04:32Z)
• An Optimistic Algorithm for Online Convex Optimization with Adversarial Constraints [55.2480439325792]
  逆制約を伴うオンライン凸最適化(OCO)について検討する。 本稿では,損失関数と制約関数の予測にアルゴリズムがアクセス可能な設定に着目する。 以上の結果から,現在のO(sqrtT) $ regret と $ tildeO(sqrtT) $ cumulative constraint violation の改善が期待できることがわかった。
  論文  参考訳（メタデータ） (2024-12-11T03:06:42Z)
• Tight Bounds for Online Convex Optimization with Adversarial Constraints [16.99491218081617]
  COCOでは、そのラウンドのアクションを選択した後、学習者に凸コスト関数と凸制約関数を明らかにする。 我々は、オンラインポリシーが、制限的な仮定なしで、同時に$O(sqrtT)$ regretと$tildeO(sqrtT)$ CCVを達成できることを示します。
  論文  参考訳（メタデータ） (2024-05-15T12:37:03Z)
• Optimistic Safety for Online Convex Optimization with Unknown Linear Constraints [31.526232903811533]
  我々はOCO(Optimistically Safe OCO)と呼ぶアルゴリズムを導入し、そのアルゴリズムが$tildeO(sqrtT)$ regretと制約違反がないことを示す。 静的線形制約の場合、これは同じ仮定の下で、以前の最もよく知られた $tildeO(T2/3)$ regret よりも改善される。 時間的制約の場合、当社の作業は、$O(sqrtT)$ regretと$O(sqrtT)$ cumulative violationを示す既存の結果を補完します。
  論文  参考訳（メタデータ） (2024-03-09T04:01:39Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。 我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
  論文  参考訳（メタデータ） (2023-07-17T09:55:35Z)
• Offline Minimax Soft-Q-learning Under Realizability and Partial Coverage [100.8180383245813]
  オフライン強化学習(RL)のための値ベースアルゴリズムを提案する。 ソフトマージン条件下でのバニラQ関数の類似した結果を示す。 我々のアルゴリズムの損失関数は、推定問題を非線形凸最適化問題とラグランジフィケーションとしてキャストすることによって生じる。
  論文  参考訳（メタデータ） (2023-02-05T14:22:41Z)
• On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximation [80.86358123230757]
  本稿では,Bootstrapped and Constrained Pessimistic Value Iteration (BCP-VI) というアルゴリズムを提案する。 部分的なデータカバレッジの仮定の下で、BCP-VI は最適な Q-値関数に正のギャップがあるときに、オフライン RL に対して $tildemathcalO(frac1K)$ の高速レートを得る。 これらは、アダプティブデータからの線形関数近似を持つオフラインRLに対してそれぞれ、最初の$tildemathcalO(frac1K)$boundと絶対零部分最適境界である。
  論文  参考訳（メタデータ） (2022-11-23T18:50:44Z)
• Towards Painless Policy Optimization for Constrained MDPs [46.12526917024248]
  我々は、無限の地平線における政策最適化、$gamma$-discounted constrained Markov decision process (CMDP)について研究する。 我々の目標は、小さな制約違反で大きな期待された報酬を達成する政策を返却することである。 本稿では,任意のアルゴリズムに対して,報酬の準最適性と制約違反を拘束できる汎用的原始双対フレームワークを提案する。
  論文  参考訳（メタデータ） (2022-04-11T15:08:09Z)
• Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
  本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。 この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
  論文  参考訳（メタデータ） (2021-12-29T02:42:59Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。