論文の概要: 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ポリシーを用いてサロゲート問題を解くことで,最適性能境界を実現できることを示す。
新たな分解結果を通じて,後悔とある連続的不等式との関係を明らかにする新しいリアプノフに基づく証明手法を提案する。
本稿は、オンラインマルチタスク学習およびネットワーク制御問題への応用を強調して結論付ける。
関連論文リスト
- Projection-Free Online Convex Optimization with Stochastic Constraints [0.0]
我々は制約付きオンライン凸最適化のためのプロジェクションフリーアルゴリズムを開発した。
各種設定に対してサブ線形後悔と制約違反境界を推定する。
我々は、制約違反を減らして、後悔と同じ成長をすることができることを証明している。
論文 参考訳(メタデータ) (2023-05-02T11:27:34Z) - Offline Minimax Soft-Q-learning Under Realizability and Partial Coverage [100.8180383245813]
オフライン強化学習(RL)のための値ベースアルゴリズムを提案する。
ソフトマージン条件下でのバニラQ関数の類似した結果を示す。
我々のアルゴリズムの損失関数は、推定問題を非線形凸最適化問題とラグランジフィケーションとしてキャストすることによって生じる。
論文 参考訳(メタデータ) (2023-02-05T14:22:41Z) - A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。
目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。
本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
論文 参考訳(メタデータ) (2022-09-15T16:59:19Z) - Augmented Lagrangian Methods for Time-varying Constrained Online Convex
Optimization [1.662966122370634]
オンライン凸最適化(OCO)と時間的損失と制約関数について検討する。
まず,時間変動関数制約OCOのためのモデルベース拡張ラグランジアン法(MALM)のクラスを開発する。
提案アルゴリズムの効率性を示すために, 制約OCOのいくつかの例について数値計算を行った。
論文 参考訳(メタデータ) (2022-05-19T14:03:25Z) - Conservative Distributional Reinforcement Learning with Safety
Constraints [22.49025480735792]
安全探索は、期待される長期コストが制約されるマルコフ決定問題とみなすことができる。
従来の非政治アルゴリズムは、制約付き最適化問題をラグランジアン緩和手法を導入して、対応する制約なしの双対問題に変換する。
本稿では,ポストリオ政策最適化による保守的分布最大化という,非政治的強化学習アルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-01-18T19:45:43Z) - Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for
Online Convex Optimization [93.71361250701075]
本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。
この結果が本質的な難易度に適応するのは, 既往の結果よりも厳密であり, 最悪の場合, 同一の値が保証されるためである。
論文 参考訳(メタデータ) (2021-12-29T02:42:59Z) - Successive Convex Approximation Based Off-Policy Optimization for
Constrained Reinforcement Learning [12.523496806744946]
本稿では,一般的な制約付き強化学習問題の解法として,凸近似に基づくオフポリティ最適化(SCAOPO)アルゴリズムを提案する。
時変状態分布と非政治学習によるバイアスにもかかわらず、実現可能な初期点を持つSCAOPOはカルーシュ=クーン=タッカー点に確実に収束することができる。
論文 参考訳(メタデータ) (2021-05-26T13:52:39Z) - Delay-Tolerant Constrained OCO with Application to Network Resource
Allocation [44.67787270821051]
マルチスロットフィードバック遅延によるオンライン凸最適化(OCO)を検討します。
エージェントは、時間変動凸損失関数の蓄積を最小限に抑えるために、一連のオンライン決定を行う。
情報フィードバックと意思決定の更新の非同期性に取り組むために,二重正規化による新たな制約ペナルティを用いた遅延耐性制約OCOを提案する。
論文 参考訳(メタデータ) (2021-05-09T19:32:33Z) - Non-stationary Online Learning with Memory and Non-stochastic Control [71.14503310914799]
我々は,過去の決定に依拠する損失関数を許容するメモリを用いたオンライン凸最適化(OCO)の問題について検討する。
本稿では,非定常環境に対してロバストなアルゴリズムを設計するための性能指標として,動的ポリシーの後悔を紹介する。
我々は,時間的地平線,非定常度,メモリ長といった面で,最適な動的ポリシーの後悔を確実に享受するメモリ付きOCOの新しいアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-02-07T09:45:15Z) - On Lower Bounds for Standard and Robust Gaussian Process Bandit
Optimization [55.937424268654645]
有界ノルムを持つ関数のブラックボックス最適化問題に対するアルゴリズム非依存な下界を考える。
本稿では, 単純さ, 汎用性, エラー確率への依存性の向上など, 後悔の下位境界を導出するための新しい証明手法を提案する。
論文 参考訳(メタデータ) (2020-08-20T03:48:14Z) - Dynamic Regret of Convex and Smooth Functions [93.71361250701075]
非定常環境におけるオンライン凸最適化について検討する。
パフォーマンス指標として動的後悔を選択します。
本研究では, 滑らかさを活かして, 動的後悔をさらに高めることが可能であることを示す。
論文 参考訳(メタデータ) (2020-07-07T14:10:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。