論文の概要: Learning to Cover: Online Learning and Optimization with Irreversible Decisions

• arxiv url: http://arxiv.org/abs/2406.14777v1
• Date: Thu, 20 Jun 2024 23:00:25 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-24 15:12:21.119926
• Title: Learning to Cover: Online Learning and Optimization with Irreversible Decisions
• Title（参考訳）: カバーする学習: 不可能な決定によるオンライン学習と最適化
• Authors: Alexandre Jacquillat, Michael Lingzhi Li,
• Abstract要約: 後悔は$Thetaleft(mfrac12cdotfrac11-2-Tright)$で半直線的に成長するので、指数関数的に$Theta(sqrtm)$に収束する。 これらの調査結果は、限定的なオンライン学習と最適化の利点を浮き彫りにしている。
• 参考スコア（独自算出の注目度）: 50.5775508521174
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We define an online learning and optimization problem with irreversible decisions contributing toward a coverage target. At each period, a decision-maker selects facilities to open, receives information on the success of each one, and updates a machine learning model to guide future decisions. The goal is to minimize costs across a finite horizon under a chance constraint reflecting the coverage target. We derive an optimal algorithm and a tight lower bound in an asymptotic regime characterized by a large target number of facilities $m\to\infty$ but a finite horizon $T\in\mathbb{Z}_+$. We find that the regret grows sub-linearly at a rate $\Theta\left(m^{\frac{1}{2}\cdot\frac{1}{1-2^{-T}}}\right)$, thus converging exponentially fast to $\Theta(\sqrt{m})$. We establish the robustness of this result to the learning environment; we also extend it to a more complicated facility location setting in a bipartite facility-customer graph with a target on customer coverage. Throughout, constructive proofs identify a policy featuring limited exploration initially for learning purposes, and fast exploitation later on for optimization purposes once uncertainty gets mitigated. These findings underscore the benefits of limited online learning and optimization, in that even a few rounds can provide significant benefits as compared to a no-learning baseline.
• Abstract（参考訳）: 我々は、カバー範囲の目標に寄与する不可逆的な決定を伴うオンライン学習と最適化の問題を定義する。 各期間に、意思決定者は、オープンする施設を選択し、それぞれの成功に関する情報を受け取り、将来の決定を導くために機械学習モデルを更新する。 目標は、カバーターゲットを反映するチャンス制約の下で、有限地平線を越えたコストを最小限にすることである。 我々は、最適なアルゴリズムと漸近的な状態における厳密な下界を導出し、多数の施設を対象とする$m\to\infty$を特徴付けるが、有限地平線$T\in\mathbb{Z}_+$を導出する。 後悔は$\Theta\left(m^{\frac{1}{2}\cdot\frac{1}{1-2^{-T}}}\right)$で半直線的に成長し、指数的に$\Theta(\sqrt{m})$に収束する。 我々は、この結果の堅牢性を学習環境に確立し、また、顧客カバレッジを目標とした、二部構成の施設-顧客グラフにおける、より複雑な施設配置にまで拡張する。 建設的証明は、最初は学習目的のために限られた探索を特徴とする政策を特定し、後に不確実性が緩和されたときに最適化目的のために高速な搾取を行う。 これらの調査結果は、限定的なオンライン学習と最適化の利点を浮き彫りにしている。

関連論文リスト

• Learning to Optimize for Mixed-Integer Non-linear Programming [20.469394148261838]
  混合整数非NLPプログラム(MINLP)はエネルギーシステムや輸送など様々な領域で発生するが、解決は困難である。 機械学習の最近の進歩は、最適化のための学習として知られる領域において、顕著な成功をもたらしている。 勾配を保ちながら整数出力を生成する2つの異なる補正層を提案する。
  論文  参考訳（メタデータ） (2024-10-14T20:14:39Z)
• Can Learned Optimization Make Reinforcement Learning Less Difficult? [70.5036361852812]
  学習の最適化が強化学習の難しさを克服するのに役立つかどうかを検討する。 本稿では, 塑性, 探索および非定常性のための学習最適化手法(OPEN)を用いて, 入力特性と出力構造がこれらの困難に対して予め提案された情報によって通知される更新規則をメタラーニングする。
  論文  参考訳（メタデータ） (2024-07-09T17:55:23Z)
• Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning with Linear Function Approximation [16.871660060209674]
  本研究では, 線形関数近似を用いた展開効率向上強化学習(RL)の課題を, 遠近自由探索条件下で検討する。 我々は,最大$widetildeO(fracd2H5epsilon2)$ trajectoriesを$H$デプロイメント内で収集し,$epsilon$-Optimal Policyを任意の(おそらくはデータに依存した)報酬関数の選択に対して識別するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-10-03T03:48:26Z)
• A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
  我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。 目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。 本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
  論文  参考訳（メタデータ） (2022-09-15T16:59:19Z)
• Offline Stochastic Shortest Path: Learning, Evaluation and Towards Optimality [57.91411772725183]
  本稿では,状態空間と動作空間が有限である場合のオフライン最短経路問題について考察する。 オフラインポリシ評価(OPE)とオフラインポリシ学習タスクの両方を扱うための,シンプルな値ベースアルゴリズムを設計する。 これらの単純なアルゴリズムの解析は、極小値に近い最悪のケース境界を示唆する強いインスタンス依存境界をもたらす。
  論文  参考訳（メタデータ） (2022-06-10T07:44:56Z)
• Online Learning with Knapsacks: the Best of Both Worlds [54.28273783164608]
  オンライン学習の課題として,意思決定者が,リソース制約の有限セットに違反することなく,期待する報酬を最大化したい,という課題を提起する。 当社のフレームワークは,意思決定者がそのエビデンスを柔軟かつコスト論的に扱えるようにします。
  論文  参考訳（メタデータ） (2022-02-28T12:10:48Z)
• Adaptive Multi-Goal Exploration [118.40427257364729]
  我々は、AdaGoalが$epsilon$-optimal goal-conditioned policyを学習する目的を達成するためにどのように使えるかを示す。 AdaGoalは、ゴール条件の深い強化学習のための既存の手法の高レベルなアルゴリズム構造に固定されている。
  論文  参考訳（メタデータ） (2021-11-23T17:59:50Z)
• Contextual Inverse Optimization: Offline and Online Learning [3.6739949215165164]
  オフラインとオンラインのコンテキスト最適化の問題について,フィードバック情報を用いて検討する。 我々は後悔を最小限に抑えることを目指しており、これは我々の損失と全知の託宣によって引き起こされた損失との違いとして定義される。
  論文  参考訳（メタデータ） (2021-06-26T13:09:52Z)
• Refined approachability algorithms and application to regret minimization with global costs [0.38073142980732994]
  ブラックウェルのアプローチ可能性 (Blackwell's approachability) は、2人のプレイヤー、すなわち意思決定者(Decision Maker)と環境(Environment)がベクター価値のペイオフで繰り返しゲームをする枠組みである。 我々は、ブラックウェルのアプローチ可能性のために、正規化リーダアルゴリズム(FTRL)のクラスを構築し、分析する。 この柔軟性により、これらのアルゴリズムを適用して、様々なオンライン学習問題への関心度を極力最小化することができる。
  論文  参考訳（メタデータ） (2020-09-08T15:54:08Z)
• Unsupervised Deep Learning for Optimizing Wireless Systems with Instantaneous and Statistic Constraints [29.823814915538463]
  我々は、教師なしのディープラーニングを用いて、瞬時的制約と統計的制約の両方で、双方の問題を解決する統一的な枠組みを確立する。 教師なし学習は、最適政策の違反確率と近似精度の観点から教師あり学習より優れていることを示す。
  論文  参考訳（メタデータ） (2020-05-30T13:37:14Z)

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

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