論文の概要: Optimistic Safety for Linearly-Constrained Online Convex Optimization
- arxiv url: http://arxiv.org/abs/2403.05786v1
- Date: Sat, 9 Mar 2024 04:01:39 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-13 12:19:57.233579
- Title: Optimistic Safety for Linearly-Constrained Online Convex Optimization
- Title（参考訳）: 線形制約付きオンライン凸最適化の最適安全性
- Authors: Spencer Hutchinson, Tianyi Chen, Mahnoosh Alizadeh
- Abstract要約: 我々は、プレイヤーがノイズの多いフィードバックを受け、常に満たさなければならない静的線形制約の問題を考える。
楽観的安全性の新たな設計パラダイムを活用することで,この問題に対して, $tildemathcalO(sqrtT)$ regret というアルゴリズムを提案する。
我々は,アルゴリズムがこのような設定で同じ後悔の保証を享受しており,期待する制約に反することはないことを示す。
- 参考スコア（独自算出の注目度）: 35.43232638653937
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The setting of online convex optimization (OCO) under unknown constraints has
garnered significant attention in recent years. In this work, we consider a
version of this problem with static linear constraints that the player receives
noisy feedback of and must always satisfy. By leveraging our novel design
paradigm of optimistic safety, we give an algorithm for this problem that
enjoys $\tilde{\mathcal{O}}(\sqrt{T})$ regret. This improves on the previous
best regret bound of $\tilde{\mathcal{O}}(T^{2/3})$ while using only slightly
stronger assumptions of independent noise and an oblivious adversary. Then, by
recasting this problem as OCO under time-varying stochastic linear constraints,
we show that our algorithm enjoys the same regret guarantees in such a setting
and never violates the constraints in expectation. This contributes to the
literature on OCO under time-varying stochastic constraints, where the
state-of-the-art algorithms enjoy $\tilde{\mathcal{O}}(\sqrt{T})$ regret and
$\tilde{\mathcal{O}}(\sqrt{T})$ violation when the constraints are convex and
the player receives full feedback. Additionally, we provide a version of our
algorithm that is more computationally efficient and give numerical experiments
comparing it with benchmark algorithms.
- Abstract（参考訳）: 未知の制約下でのオンライン凸最適化(OCO)の設定は近年大きな注目を集めている。
本研究では,プレイヤーが無音のフィードバックを受け取り,常に満たさなければならない静的線形制約を伴うこの問題を考察する。
楽観的安全性の新たな設計パラダイムを活用することで,この問題に対して, $\tilde{\mathcal{O}}(\sqrt{T})$ regret を満足するアルゴリズムを提供する。
これにより$\tilde{\mathcal{O}}(T^{2/3})$の過去の最良後悔境界は改善されるが、独立雑音のわずかに強い仮定と不愉快な逆数のみを使用する。
そして,時間的確率線形制約の下でこの問題をOCOとして再キャストすることにより,我々のアルゴリズムはそのような設定で同じ後悔の保証を享受し,期待する制約に反することはないことを示す。
これはocoの時間的制約の下での文献に寄与し、最先端のアルゴリズムは$\tilde{\mathcal{o}}(\sqrt{t})$ regret と $\tilde{\mathcal{o}}(\sqrt{t})$ violation を享受する。
さらに、より計算効率の良いアルゴリズムのバージョンを提供し、ベンチマークアルゴリズムと比較した数値実験を行う。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Optimal Algorithms for Online Convex Optimization with Adversarial Constraints [16.99491218081617]
COCOでは、そのラウンドのアクションを選択した後、学習者に凸コスト関数と凸制約関数を明らかにする。
我々は、オンラインポリシーが、制限的な仮定なしで、同時に$O(sqrtT)$ regretと$tildeO(sqrtT)$ CCVを達成できることを示します。
論文 参考訳（メタデータ） (2023-10-29T09:55:41Z) - Online Convex Optimization with Stochastic Constraints: Zero Constraint
Violation and Bandit Feedback [0.0]
本稿では,O(sqrtT)$期待後悔とゼロ制約違反を保証できるドリフト・プラス・ペナルティアルゴリズムの変種を提案する。
我々のアルゴリズムは、バニラドリフト・プラス・ペナルティ法とは対照的に、時間地平線の長さが$T$である。
論文 参考訳（メタデータ） (2023-01-26T18:04:26Z) - Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization [88.0031283949404]
多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。
提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
論文 参考訳（メタデータ） (2022-12-19T14:48:54Z) - 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) - Lazy Lagrangians with Predictions for Online Learning [24.18464455081512]
オンライン凸最適化における時間的差分制約による一般的な問題について考察する。
Follow-The-Regularized-Leaderイテレーションと予測適応動的ステップを組み合わせることで、新しい原始双対アルゴリズムを設計する。
我々の研究は、この制約されたOCO設定のためのFTRLフレームワークを拡張し、各最先端のグレディベースのソリューションより優れています。
論文 参考訳（メタデータ） (2022-01-08T21:49:10Z) - Concave Utility Reinforcement Learning with Zero-Constraint Violations [43.29210413964558]
本稿では,凸制約を伴うCURL(Concave utility reinforcement Learning)の問題点について考察する。
制約違反をゼロにするモデルベース学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-12T06:13:33Z) - Regret and Cumulative Constraint Violation Analysis for Online Convex
Optimization with Long Term Constraints [24.97580261894342]
本稿では,長期的制約を伴うオンライン凸最適化について考察する。
新たなアルゴリズムが最初に提案され、静的後悔のために$mathcalO(Tmaxc,1-c)$bound、累積制約違反のために$mathcalO(T(1-c)/2)$boundを達成する。
論文 参考訳（メタデータ） (2021-06-09T15:18:06Z) - Efficient Optimistic Exploration in Linear-Quadratic Regulators via
Lagrangian Relaxation [107.06364966905821]
線形2次レギュレータ(LQR)設定における探索・探索ジレンマについて検討した。
有限 MDP に対する楽観的アルゴリズムで用いられる拡張値反復アルゴリズムに着想を得て,Oulq の楽観的最適化を緩和することを提案する。
我々は、少なくとも$Obig(log (1/epsilon)big)$ Riccati方程式を解くことで、$epsilon$-OptimisticControllerを効率的に計算できることを示した。
論文 参考訳（メタデータ） (2020-07-13T16:30:47Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z) - Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
制約付きマルコフ決定過程(CMDP)を用いた安全強化学習(SRL)問題について検討する。
本稿では,関数近似設定において,安全な探索を行うCMDPの効率の良いオンラインポリシー最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-03-01T17:47:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。