論文の概要: Understanding Curriculum Learning in Policy Optimization for Solving
Combinatorial Optimization Problems
- arxiv url: http://arxiv.org/abs/2202.05423v1
- Date: Fri, 11 Feb 2022 03:17:15 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-14 15:12:29.120397
- Title: Understanding Curriculum Learning in Policy Optimization for Solving
Combinatorial Optimization Problems
- Title(参考訳): 組合せ最適化問題の解法における政策最適化におけるカリキュラム学習の理解
- Authors: Runlong Zhou, Yuandong Tian, Yi Wu, Simon S. Du
- Abstract要約: 本稿では,CO問題解決のための政策最適化手法に関する最初の体系的研究について述べる。
我々は,CO 問題を潜在マルコフ決定過程 (LMDP) として自然に定式化することができ,LMDP の解法として自然政策勾配 (NPG) に収束することを示した。
また,本理論は,先行研究で用いられるカリキュラムの学習方法を,複数段階から1段階まで単純化できることを示唆している。
- 参考スコア(独自算出の注目度): 62.60305771489385
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Over the recent years, reinforcement learning (RL) has shown impressive
performance in finding strategic solutions for game environments, and recently
starts to show promising results in solving combinatorial optimization (CO)
problems, inparticular 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 solving CO problems. We show that 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 combinatorial problem, Secretary Problem, we formally prove
that distribution shift is reduced exponentially with curriculum learning. 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 Secretary Problem and Online Knapsack to empirically verify our findings.
- Abstract(参考訳): 近年、強化学習(RL)は、ゲーム環境における戦略的ソリューションの発見において、目覚ましい性能を示しており、特にカリキュラム学習と組み合わせて学習を容易にする場合、組合せ最適化(CO)問題を解く上で有望な結果を示し始めている。
実験的な証拠が現れたにもかかわらず、rlがなぜ助けるかについての理論的な研究はまだ初期段階にある。
本稿では,co問題を解くためのポリシー最適化手法に関する最初の体系的研究を行う。
我々は,CO 問題を潜在マルコフ決定過程 (LMDP) として自然に定式化することができ,LMDP の解法として自然政策勾配 (NPG) に収束することを示した。
さらに,本理論はカリキュラム学習の利点を解説し,この定理の収束率を決定する重要な量である,強いサンプリングポリシーを見つけ,分布シフトを減少させることができる。
正統的な組合せ問題である書記官問題では,カリキュラム学習によって分布シフトが指数関数的に減少することが正式に証明される。
また,本理論は,先行研究で用いられるカリキュラム学習を,多段階から一段階に単純化できることを示す。
最後に,秘書問題とオンライン・ナップサックに関する広範な実験を行い,その結果を実証的に検証する。
関連論文リスト
- 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) - 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) - Learning-Augmented Algorithms for Online Linear and Semidefinite
Programming [9.849604820019394]
Semidefinite Programming (SDP) は線形および二次的に制約されたプログラミングを一般化する統一フレームワークである。
SDPをカバーするための制約がオンラインに届くと、最適解を近似するためには、既知の不可能な結果が存在する。
予測器が正確であれば、これらの不可能な結果を効率よく回避し、最適解に対する定数係数近似を達成できることが示される。
論文 参考訳(メタデータ) (2022-09-21T19:16:29Z) - Curriculum Offline Imitation Learning [72.1015201041391]
オフラインの強化学習タスクでは、エージェントは、環境とのさらなるインタラクションなしに、事前にコンパイルされたデータセットから学ぶ必要がある。
我々は,適応的な近隣政策を模倣する経験的選択戦略を,より高いリターンで活用するテキストカリキュラムオフライン学習(COIL)を提案する。
連続制御ベンチマークでは、COILを模倣ベースとRLベースの両方の手法と比較し、混合データセット上で平凡な振る舞いを学ぶことを避けるだけでなく、最先端のオフラインRL手法と競合することを示します。
論文 参考訳(メタデータ) (2021-11-03T08:02:48Z) - A Bi-Level Framework for Learning to Solve Combinatorial Optimization on
Graphs [91.07247251502564]
本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。
このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
論文 参考訳(メタデータ) (2021-06-09T09:18:18Z) - SOLO: Search Online, Learn Offline for Combinatorial Optimization
Problems [4.777801093677586]
我々は,機械スケジューリングやルーティング,割当てといった実世界のアプリケーションで問題を研究する。
RL(Reinforcement Learning)とプランニングを組み合わせた手法を提案する。
この方法は、オフラインでも、オンラインでも、問題のコンポーネントが事前に分かっておらず、むしろ意思決定プロセス中に現れるような、問題の変種にも等しく適用することができる。
論文 参考訳(メタデータ) (2021-04-04T17:12:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。