論文の概要: Understanding Curriculum Learning in Policy Optimization for Online Combinatorial Optimization

• arxiv url: http://arxiv.org/abs/2202.05423v3
• Date: Fri, 3 Nov 2023 21:12:09 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-08 02:08:04.339051
• Title: Understanding Curriculum Learning in Policy Optimization for Online Combinatorial Optimization
• Title（参考訳）: オンラインコンビネート最適化のための政策最適化におけるカリキュラム学習の理解
• Authors: Runlong Zhou, Zelin He, Yuandong Tian, Yi Wu, Simon S. Du
• Abstract要約: 本稿では,オンラインCO問題に対するポリシー最適化手法に関する最初の体系的研究について述べる。 我々は、オンラインCO問題は、潜在マルコフ決定過程(LMDP)として自然に定式化でき、自然政策勾配(NPG)に収束することを示す。 さらに,本理論はカリキュラム学習の利点を解説し,強力なサンプリングポリシーを見出すことができ,流通シフトを低減できることを示した。
• 参考スコア（独自算出の注目度）: 66.35750142827898
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Over the recent years, reinforcement learning (RL) starts to show promising results in tackling combinatorial optimization (CO) problems, in particular when coupled with curriculum learning to facilitate training. Despite emerging empirical evidence, theoretical study on why RL helps is still at its early stage. This paper presents the first systematic study on policy optimization methods for online CO problems. We show that online CO problems can be naturally formulated as latent Markov Decision Processes (LMDPs), and prove convergence bounds on natural policy gradient (NPG) for solving LMDPs. Furthermore, our theory explains the benefit of curriculum learning: it can find a strong sampling policy and reduce the distribution shift, a critical quantity that governs the convergence rate in our theorem. For a canonical online CO problem, the Best Choice Problem (BCP), we formally prove that distribution shift is reduced exponentially with curriculum learning even if the curriculum is a randomly generated BCP on a smaller scale. Our theory also shows we can simplify the curriculum learning scheme used in prior work from multi-step to single-step. Lastly, we provide extensive experiments on the Best Choice Problem, Online Knapsack, and AdWords to verify our findings.
• Abstract（参考訳）: 近年,強化学習(rl)は,特にカリキュラム学習と組み合わせることで,組合せ最適化(co)問題に対して有望な結果が示され始めている。 実験的な証拠が現れたにもかかわらず、rlがなぜ助けるかについての理論的な研究はまだ初期段階にある。 本稿では,オンラインco問題に対するポリシー最適化手法に関する最初の体系的研究を行う。 オンラインCO問題は, 遅延マルコフ決定過程 (LMDP) として自然に定式化でき, LMDP を解くための自然政策勾配 (NPG) に収束することを示す。 さらに,本理論はカリキュラム学習の利点を解説し,この定理の収束率を決定する重要な量である,強いサンプリングポリシーを見つけ,分布シフトを減少させることができる。 正規オンラインCO問題であるベストチョイス問題(BCP)では,カリキュラムがランダムに生成されたBCPであっても,カリキュラムの学習によって分布シフトが指数関数的に減少することが正式に証明される。 また,本理論は,先行研究で用いられるカリキュラム学習を,多段階から一段階に単純化できることを示す。 最後に、Best Choice Problem、Online Knapsack、AdWordsに関する広範な実験を行い、その結果を確認します。

関連論文リスト

• Efficient Imitation Learning with Conservative World Models [54.52140201148341]
  報酬機能のない専門家によるデモンストレーションから政策学習の課題に取り組む。 純粋な強化学習ではなく、微調整問題として模倣学習を再構成する。
  論文  参考訳（メタデータ） (2024-05-21T20:53:18Z)
• Offline Imitation Learning from Multiple Baselines with Applications to Compiler Optimization [17.729842629392742]
  我々は,Kベースラインポリシーで収集した一連のトラジェクトリを与えられる強化学習問題について検討する。 目標は、状態空間全体におけるベースラインの最高の組み合わせと同様に、機能するポリシーを学ぶことです。
  論文  参考訳（メタデータ） (2024-03-28T14:34:02Z)
• How Can LLM Guide RL? A Value-Based Approach [68.55316627400683]
  強化学習(Reinforcement Learning, RL)は、将来の行動方針をフィードバックで改善することにより、シーケンシャルな意思決定問題の事実上の標準的実践となった。 大規模言語モデル(LLM)の最近の発展は、言語理解と生成において印象的な能力を示したが、探索と自己改善能力に欠けていた。 我々はLINVITというアルゴリズムを開発し、LLMガイダンスを値ベースRLの正規化因子として組み込んで学習に必要なデータ量を大幅に削減する。
  論文  参考訳（メタデータ） (2024-02-25T20:07:13Z)
• Graph Q-Learning for Combinatorial Optimization [44.8086492019594]
  グラフニューラルネットワーク(GNN)は,グラフデータの予測と推論の問題を解くのに有効であることが示されている。 本稿では,GNNを組合せ最適化問題に適用できることを示す。
  論文  参考訳（メタデータ） (2024-01-11T01:15:28Z)
• Projected Off-Policy Q-Learning (POP-QL) for Stabilizing Offline Reinforcement Learning [57.83919813698673]
  Projected Off-Policy Q-Learning (POP-QL) は、政治外のサンプルを同時に重み付け、分散を防止し、価値近似誤差を減らすためにポリシーを制約する新しいアクタ批判アルゴリズムである。 我々の実験では、POP-QLは標準ベンチマーク上での競合性能を示すだけでなく、データ収集ポリシーがかなり最適化されていないタスクにおいて競合するメソッドよりも優れています。
  論文  参考訳（メタデータ） (2023-11-25T00:30:58Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。 我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。 本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
  論文  参考訳（メタデータ） (2023-10-08T23:39:38Z)
• Realistic Unsupervised CLIP Fine-tuning with Universal Entropy Optimization [101.08992036691673]
  本稿では,未知のクラスにおける配布外サンプルの存在を考慮し,教師なしの微調整シナリオについて考察する。 特に,分布外検出と既知のクラスに関連するインスタンスの認識を同時に強化することに注力する。 我々はUniversal Entropy Optimization(UEO)と呼ばれるシンプルで効率的で効果的なアプローチを提案する。
  論文  参考訳（メタデータ） (2023-08-24T16:47:17Z)
• Provably Efficient Offline Goal-Conditioned Reinforcement Learning with General Function Approximation and Single-Policy Concentrability [11.786486763236104]
  ゴール条件強化学習(ゴール条件強化学習、GCRL)とは、様々な目標を達成するための汎用スキルの学習である。 オフラインのGCRLは、トレーニングタスクを実行するために純粋にコンパイル済みのデータセットのみを必要とする。 修正されたオフラインGCRLアルゴリズムは、一般関数近似と単一政治集中性の両方で有効であることを示す。
  論文  参考訳（メタデータ） (2023-02-07T22:04:55Z)
• Unsupervised Learning for Combinatorial Optimization Needs Meta-Learning [14.86600327306136]
  最適化のための教師なし学習(CO)の一般的なフレームワークは、出力がCOの目的を直接最適化することで問題解決をもたらすニューラルネットワーク(NN)を訓練することである。 本研究では,COにおける教師なし学習の新たな目的について提案する。この学習の目的は,直接的な解決策を与えるのではなく,将来の問題インスタンスの優れた初期化を探すことである。 微調整前のモデルが与える初期解だけでも, 様々な評価条件下では, ベースラインを著しく上回る結果が得られます。
  論文  参考訳（メタデータ） (2023-01-08T22:14:59Z)
• SOLO: Search Online, Learn Offline for Combinatorial Optimization Problems [4.777801093677586]
  我々は,機械スケジューリングやルーティング,割当てといった実世界のアプリケーションで問題を研究する。 RL(Reinforcement Learning)とプランニングを組み合わせた手法を提案する。 この方法は、オフラインでも、オンラインでも、問題のコンポーネントが事前に分かっておらず、むしろ意思決定プロセス中に現れるような、問題の変種にも等しく適用することができる。
  論文  参考訳（メタデータ） (2021-04-04T17:12:24Z)

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

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