論文の概要: A Lyapunov-Based Methodology for Constrained Optimization with Bandit Feedback

• arxiv url: http://arxiv.org/abs/2106.05165v1
• Date: Wed, 9 Jun 2021 16:12:07 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-10 20:48:19.464419
• Title: A Lyapunov-Based Methodology for Constrained Optimization with Bandit Feedback
• Title（参考訳）: 帯域フィードバックを用いた制約付き最適化のためのリアプノフ法
• Authors: Semih Cayci, Yilin Zheng, Atilla Eryilmaz
• Abstract要約: 各アクションが未知の関節分布からランダムな報酬、コスト、ペナルティを返す問題を考える。 我々は、$tt LyOn$という新しい低複雑さアルゴリズムを提案し、$O(sqrtBlog B)$ regretと$O(log B/B)$ constraint-violationを達成することを証明した。 計算コストの低い$tt LyOn$は、Lyapunovをベースとしたアルゴリズム設計手法が制約付き帯域最適化問題の解決に有効であることを示唆している。
• 参考スコア（独自算出の注目度）: 22.17503016665027
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In a wide variety of applications including online advertising, contractual hiring, and wireless scheduling, the controller is constrained by a stringent budget constraint on the available resources, which are consumed in a random amount by each action, and a stochastic feasibility constraint that may impose important operational limitations on decision-making. In this work, we consider a general model to address such problems, where each action returns a random reward, cost, and penalty from an unknown joint distribution, and the decision-maker aims to maximize the total reward under a budget constraint $B$ on the total cost and a stochastic constraint on the time-average penalty. We propose a novel low-complexity algorithm based on Lyapunov optimization methodology, named ${\tt LyOn}$, and prove that it achieves $O(\sqrt{B\log B})$ regret and $O(\log B/B)$ constraint-violation. The low computational cost and sharp performance bounds of ${\tt LyOn}$ suggest that Lyapunov-based algorithm design methodology can be effective in solving constrained bandit optimization problems.
• Abstract（参考訳）: オンライン広告、契約採用、および無線スケジューリングを含む幅広いアプリケーションにおいて、コントローラは、各アクションによってランダムに消費される利用可能なリソースに対する厳格な予算制約と、意思決定に重要な運用上の制限を課す確率的可能性制約によって制約される。 本研究では、各アクションが未知の共同分布からランダムな報酬、コスト、ペナルティを返し、意思決定者は、総コストにb$、時間平均ペナルティに確率的制約を課す予算制約の下で、総報酬を最大化することを目的としている。 我々は、Lyapunov最適化手法に基づく新しい低複雑さアルゴリズムである${\tt LyOn}$を提案し、それが$O(\sqrt{B\log B})$ regretおよび$O(\log B/B)$ constraint-violationを達成することを証明した。 計算コストの低い${\tt LyOn}$の急激な性能境界は、リアプノフに基づくアルゴリズム設計手法が制約付き帯域最適化問題を解くのに有効であることを示唆している。

関連論文リスト

• Best-of-Both-Worlds Policy Optimization for CMDPs with Bandit Feedback [34.7178680288326]
  Stradi et al.(2024) は、マルコフ決定過程に制約のある最初のベスト・オブ・ボス・ワールドズ・アルゴリズムを提案した。 本稿では,CMDPにおける帯域幅フィードバックを用いたベスト・オブ・ワールドズ・アルゴリズムを提案する。 本アルゴリズムは政策最適化手法に基づいており, 占有率に基づく手法よりも効率的である。
  論文  参考訳（メタデータ） (2024-10-03T07:44:40Z)
• Multi-Agent Bayesian Optimization with Coupled Black-Box and Affine Constraints [21.38692458445459]
  ブラックボックス制約と既知のアフィン制約を結合した分散マルチエージェントベイズ最適化の問題について検討する。 単一エージェントの場合と同様の後悔/違反境界を実現するアルゴリズムが提案されている。
  論文  参考訳（メタデータ） (2023-10-02T08:07:36Z)
• Provably Efficient Model-Free Algorithms for Non-stationary CMDPs [10.930095238723327]
  非定常制約マルコフ決定過程におけるモデルフリー強化学習アルゴリズムについて検討した。 非定常環境では、累積変動が一定の変動予算を超えない限り、報酬、ユーティリティ関数、遷移カーネルは時間とともに任意に変化する。 本稿では,非定常CMDPに対するサブ線形後悔と制約違反をゼロとする,モデルフリーでシミュレータフリーなRLアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-03-10T06:33:38Z)
• Quantization for decentralized learning under subspace constraints [61.59416703323886]
  エージェントがサブスペース制約を最小化するために個々のコスト関数を持つ分散最適化問題を考察する。 本稿では,エージェントが確率化量子化器を用いて推定値を圧縮する適応分散型戦略を提案し,検討する。 この分析は、量子化ノイズのいくつかの一般的な条件下では、平均二乗誤差と平均ビットレートの両方で戦略が安定であることを示している。
  論文  参考訳（メタデータ） (2022-09-16T09:38:38Z)
• A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
  我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。 目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。 本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
  論文  参考訳（メタデータ） (2022-09-15T16:59:19Z)
• Algorithm for Constrained Markov Decision Process with Linear Convergence [55.41644538483948]
  エージェントは、そのコストに対する複数の制約により、期待される累積割引報酬を最大化することを目的としている。 エントロピー正規化ポリシーとベイダの二重化という2つの要素を統合した新しい双対アプローチが提案されている。 提案手法は(線形速度で)大域的最適値に収束することが示されている。
  論文  参考訳（メタデータ） (2022-06-03T16:26:38Z)
• Penalized Proximal Policy Optimization for Safe Reinforcement Learning [68.86485583981866]
  本稿では、等価な制約のない問題の単一最小化により、煩雑な制約付きポリシー反復を解決するP3Oを提案する。 P3Oは、コスト制約を排除し、クリップされたサロゲート目的による信頼領域制約を除去するために、単純なyet効果のペナルティ関数を利用する。 P3Oは,一連の制約された機関車作業において,報酬改善と制約満足度の両方に関して,最先端のアルゴリズムより優れていることを示す。
  論文  参考訳（メタデータ） (2022-05-24T06:15:51Z)
• Online Allocation with Two-sided Resource Constraints [44.5635910908944]
  我々は,要求が順次到着する,リソース制約の低いオンラインアロケーション問題を考える。 提案手法では, リクエスト全体を知るオフライン問題に対して, 1-O (fracepsilonalpha-epsilon)$-competitive ratioを求めるアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-12-28T02:21:06Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)

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

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