論文の概要: Online DR-Submodular Maximization with Stochastic Cumulative Constraints
- arxiv url: http://arxiv.org/abs/2005.14708v3
- Date: Fri, 21 May 2021 14:45:10 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-26 23:15:07.396759
- Title: Online DR-Submodular Maximization with Stochastic Cumulative Constraints
- Title（参考訳）: 確率的累積制約を伴うオンラインdr-submodular maximization
- Authors: Prasanna Sanjay Raut, Omid Sadeghi and Maryam Fazel
- Abstract要約: 線形長期制約を伴うオンライン連続DR-サブモジュラーを考える。
オンラインラグランジアンFrank-Wolfe (OLFW) アルゴリズムは、この種のオンライン問題を解く。
- 参考スコア（独自算出の注目度）: 17.660958043781154
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we consider online continuous DR-submodular maximization with
linear stochastic long-term constraints. Compared to the prior work on online
submodular maximization, our setting introduces the extra complication of
stochastic linear constraint functions that are i.i.d. generated at each round.
To be precise, at step $t\in\{1,\dots,T\}$, a DR-submodular utility function
$f_t(\cdot)$ and a constraint vector $p_t$, i.i.d. generated from an unknown
distribution with mean $p$, are revealed after committing to an action $x_t$
and we aim to maximize the overall utility while the expected cumulative
resource consumption $\sum_{t=1}^T \langle p,x_t\rangle$ is below a fixed
budget $B_T$. Stochastic long-term constraints arise naturally in applications
where there is a limited budget or resource available and resource consumption
at each step is governed by stochastically time-varying environments. We
propose the Online Lagrangian Frank-Wolfe (OLFW) algorithm to solve this class
of online problems. We analyze the performance of the OLFW algorithm and we
obtain sub-linear regret bounds as well as sub-linear cumulative constraint
violation bounds, both in expectation and with high probability.
- Abstract（参考訳）: 本稿では,線形確率的長期制約を伴うオンライン連続型dr-submodular maximizationについて考察する。
オンラインサブモジュラー最大化に関する先行研究と比較して,各ラウンド毎に生成される確率的線形制約関数の余分な複雑化を導入する。
正確には、ステップ $t\in\{1,\dots,T\}$、DR-部分モジュラーユーティリティ関数 $f_t(\cdot)$、および未知の分布から生成される制約ベクトル $p_t$、すなわち平均$p$をコミットした後に明らかにし、期待される累積リソース消費 $\sum_{t=1}^T \langle p,x_t\rangle$ は固定予算 $B_T$ 以下である。
確率的な長期的制約は、利用可能な予算やリソースが限られているアプリケーションで自然に生じ、各ステップにおけるリソース消費は確率的に時間的に変化する環境によって管理される。
本稿では,オンラインラグランジアン・フランク・ウルフ(olfw)アルゴリズムを提案する。
我々はolfwアルゴリズムの性能解析を行い, 期待値と確率値の両方において, サブ線形後悔値およびサブリニア累積制約違反値を求める。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。
本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T14:37:21Z) - Online Convex Optimization with Stochastic Constraints: Zero Constraint
Violation and Bandit Feedback [0.0]
本稿では,O(sqrtT)$期待後悔とゼロ制約違反を保証できるドリフト・プラス・ペナルティアルゴリズムの変種を提案する。
我々のアルゴリズムは、バニラドリフト・プラス・ペナルティ法とは対照的に、時間地平線の長さが$T$である。
論文 参考訳（メタデータ） (2023-01-26T18:04:26Z) - Rectified Pessimistic-Optimistic Learning for Stochastic Continuum-armed
Bandit with Constraints [4.879346089164413]
ブラックボックスの報酬関数 $f(x)$ を、連続空間上のブラックボックス制約関数 $g(x)leq 0$ に最適化する。
本稿では,楽観的かつ悲観的なGPバンディット学習を取り入れたペナルティベース手法であるRectified Pessimistic-Optimistic Learning framework (RPOL)を提案する。
論文 参考訳（メタデータ） (2022-11-27T04:28:16Z) - 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) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Provably Efficient Model-Free Constrained RL with Linear Function
Approximation [4.060731229044571]
我々は,大規模システムにおいても,サブリニア後悔とサブリニア制約違反を実現するための,最初のモデルフリーシミュレータフリーアルゴリズムを開発した。
本結果は,標準LSVI-UCBアルゴリズムの新たな適応により達成される。
論文 参考訳（メタデータ） (2022-06-23T17:54:31Z) - 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) - Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
制約付きマルコフ決定過程(CMDP)を用いた安全強化学習(SRL)問題について検討する。
本稿では,関数近似設定において,安全な探索を行うCMDPの効率の良いオンラインポリシー最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-03-01T17:47:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。