論文の概要: Online Nonsubmodular Minimization with Delayed Costs: From Full
Information to Bandit Feedback
- arxiv url: http://arxiv.org/abs/2205.07217v1
- Date: Sun, 15 May 2022 08:27:12 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-17 16:51:28.414552
- Title: Online Nonsubmodular Minimization with Delayed Costs: From Full
Information to Bandit Feedback
- Title（参考訳）: 遅延コストを伴うオンラインサブモジュラーでない最小化:フル情報からバンディットフィードバックへ
- Authors: Tianyi Lin and Aldo Pacchiano and Yaodong Yu and Michael I. Jordan
- Abstract要約: 我々は,オンラインおよび近似的オンライン帯域勾配勾配アルゴリズムのいくつかの変種に対する後悔の保証を,特別な構造を持つ非部分モジュラ関数のクラスに焦点をあてる。
我々は,決定の選択と帰属費用の受け取りの遅れが無拘束である場合でも,エージェントの完全な情報と盗賊のフィードバック設定に対する後悔の限界を導出する。
- 参考スコア（独自算出の注目度）: 98.7678704343537
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Motivated by applications to online learning in sparse estimation and
Bayesian optimization, we consider the problem of online unconstrained
nonsubmodular minimization with delayed costs in both full information and
bandit feedback settings. In contrast to previous works on online unconstrained
submodular minimization, we focus on a class of nonsubmodular functions with
special structure, and prove regret guarantees for several variants of the
online and approximate online bandit gradient descent algorithms in static and
delayed scenarios. We derive bounds for the agent's regret in the full
information and bandit feedback setting, even if the delay between choosing a
decision and receiving the incurred cost is unbounded. Key to our approach is
the notion of $(\alpha, \beta)$-regret and the extension of the generic convex
relaxation model from~\citet{El-2020-Optimal}, the analysis of which is of
independent interest. We conduct and showcase several simulation studies to
demonstrate the efficacy of our algorithms.
- Abstract（参考訳）: 疎度推定およびベイズ最適化におけるオンライン学習への応用により、全情報と包括的フィードバック設定の両方において遅延コストを伴う制約のない非部分的最小化の問題を考える。
オンライン非拘束サブモジュラー最小化に関するこれまでの研究とは対照的に、特別な構造を持つ非モジュラー関数のクラスに注目し、静的および遅延シナリオにおけるオンラインおよび近似オンラインバンディット勾配降下アルゴリズムのいくつかの変種に対する後悔の保証を証明する。
我々は,決定の選択と請求費用の受け取りの遅延が無制限であっても,情報とバンディットのフィードバック設定におけるエージェントの後悔の限界を導出する。
このアプローチの鍵となるのは、$(\alpha, \beta)$-regret の概念と ~\citet{El-2020-Optimal} からの一般凸緩和モデルの拡張である。
我々は,アルゴリズムの有効性を示すために,いくつかのシミュレーション研究を行った。
関連論文リスト
- Contextual Linear Optimization with Bandit Feedback [35.692428244561626]
文脈線形最適化(CLO)は、ランダムコスト係数の不確実性を低減するために予測的文脈特徴を用いる。
我々は,帯域幅フィードバックを用いたCLOのためのオフライン学習アルゴリズムのクラスについて検討する。
IERMに対する高速な後悔境界を示し、不特定モデルクラスと最適化推定の柔軟な選択を可能にする。
論文 参考訳（メタデータ） (2024-05-26T13:27:27Z) - Improved Regret for Efficient Online Reinforcement Learning with Linear
Function Approximation [69.0695698566235]
線形関数近似による強化学習と,コスト関数の逆変化について検討した。
本稿では,未知のダイナミクスと帯域幅フィードバックの一般設定に挑戦する,計算効率のよいポリシ最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T17:26:39Z) - Distributed Online Non-convex Optimization with Composite Regret [31.53784277195043]
本稿では,分散オンライン一般損失に対する新たなネットワーク後悔を伴う,新たな複合後悔を提案する。
我々の知る限り、オンラインの非線形学習における最初の後悔である。
論文 参考訳（メタデータ） (2022-09-21T04:16:33Z) - Augmented Lagrangian Methods for Time-varying Constrained Online Convex
Optimization [1.662966122370634]
オンライン凸最適化(OCO)と時間的損失と制約関数について検討する。
まず,時間変動関数制約OCOのためのモデルベース拡張ラグランジアン法(MALM)のクラスを開発する。
提案アルゴリズムの効率性を示すために, 制約OCOのいくつかの例について数値計算を行った。
論文 参考訳（メタデータ） (2022-05-19T14:03:25Z) - Smoothed Online Convex Optimization Based on Discounted-Normal-Predictor [68.17855675511602]
円滑なオンライン凸最適化(SOCO)のためのオンライン予測戦略について検討する。
提案アルゴリズムは,各区間の切替コストで適応的後悔を最小限に抑えることができることを示す。
論文 参考訳（メタデータ） (2022-05-02T08:48:22Z) - Smoothed Online Combinatorial Optimization Using Imperfect Predictions [27.201074566335222]
本研究では,不完全な予測モデルが利用できる場合のスムーズなオンライン最適化問題について検討する。
有限時間地平線計画に予測を用いることで, 全体の予測不確かさと追加の切り替えコストに依存して, 後悔を招くことを示す。
本アルゴリズムは,合成オンライン分散ストリーミング問題において,他のベースラインと比較して,累積的後悔度が大幅に向上したことを示す。
論文 参考訳（メタデータ） (2022-04-23T02:30:39Z) - Pessimistic Q-Learning for Offline Reinforcement Learning: Towards
Optimal Sample Complexity [51.476337785345436]
有限水平マルコフ決定過程の文脈におけるQ-ラーニングの悲観的変種について検討する。
ほぼ最適サンプル複雑性を実現するために,分散再現型悲観的Q-ラーニングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-02-28T15:39:36Z) - Online Allocation with Two-sided Resource Constraints [44.5635910908944]
我々は,要求が順次到着する,リソース制約の低いオンラインアロケーション問題を考える。
提案手法では, リクエスト全体を知るオフライン問題に対して, 1-O (fracepsilonalpha-epsilon)$-competitive ratioを求めるアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-12-28T02:21:06Z) - Online Markov Decision Processes with Aggregate Bandit Feedback [74.85532145498742]
本稿では,オンライン有限水平マルコフ決定過程の新たな変種について検討する。
各エピソードにおいて、学習者は、エピソードの選択した方針によって実現された軌道に沿って蓄積された損失を被り、総括的盗聴フィードバックを観察する。
我々の主な結果は計算効率のよいアルゴリズムで、$O(sqrtK)$ regret for this set, where $K$ is the number of episodes。
論文 参考訳（メタデータ） (2021-01-31T16:49:07Z) - Upper Confidence Primal-Dual Reinforcement Learning for CMDP with
Adversarial Loss [145.54544979467872]
マルコフ決定過程(CMDP)に対するオンライン学習の検討
本稿では,遷移モデルから標本化した軌跡のみを必要とする,新しいEmphupper confidence primal-dualアルゴリズムを提案する。
我々の分析では、ラグランジュ乗算過程の新たな高確率ドリフト解析を、高信頼強化学習の記念後悔解析に組み入れている。
論文 参考訳（メタデータ） (2020-03-02T05:02:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。