論文の概要: Monte Carlo Policy Gradient Method for Binary Optimization

• arxiv url: http://arxiv.org/abs/2307.00783v1
• Date: Mon, 3 Jul 2023 07:01:42 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-05 14:06:13.907183
• Title: Monte Carlo Policy Gradient Method for Binary Optimization
• Title（参考訳）: 二元最適化のためのモンテカルロ政策勾配法
• Authors: Cheng Chen, Ruitao Chen, Tianyou Li, Ruichen Ao and Zaiwen Wen
• Abstract要約: パラメータ化されたポリシー分布に従って二項解をサンプリングする新しい確率モデルを開発する。 離散空間におけるコヒーレント探索には、並列マルコフ・チェイン・モンテカルロ法(MCMC)を用いる。 政策勾配法を期待する定常点への収束性を確立する。
• 参考スコア（独自算出の注目度）: 3.742634130733923
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Binary optimization has a wide range of applications in combinatorial optimization problems such as MaxCut, MIMO detection, and MaxSAT. However, these problems are typically NP-hard due to the binary constraints. We develop a novel probabilistic model to sample the binary solution according to a parameterized policy distribution. Specifically, minimizing the KL divergence between the parameterized policy distribution and the Gibbs distributions of the function value leads to a stochastic optimization problem whose policy gradient can be derived explicitly similar to reinforcement learning. For coherent exploration in discrete spaces, parallel Markov Chain Monte Carlo (MCMC) methods are employed to sample from the policy distribution with diversity and approximate the gradient efficiently. We further develop a filter scheme to replace the original objective function by the one with the local search technique to broaden the horizon of the function landscape. Convergence to stationary points in expectation of the policy gradient method is established based on the concentration inequality for MCMC. Numerical results show that this framework is very promising to provide near-optimal solutions for quite a few binary optimization problems.
• Abstract（参考訳）: バイナリ最適化は、MaxCut、MIMO検出、MaxSATのような組合せ最適化問題に幅広い応用がある。 しかし、これらの問題は一般に二項制約のためNPハードである。 パラメータ化されたポリシー分布に従ってバイナリソリューションをサンプリングする新しい確率モデルを開発した。 具体的には、パラメータ化ポリシ分布と関数値のギブス分布とのKL分散を最小化することで、強化学習と明確に類似したポリシ勾配を導出できる確率的最適化問題を導出する。 離散空間におけるコヒーレントな探索のために、パラレルマルコフ連鎖モンテカルロ(mcmc)法を用いて、多様性のあるポリシー分布をサンプル化し、勾配を効率的に近似する。 さらに,関数ランドスケープの地平線を拡大する局所探索手法を用いて,元の目的関数を置き換えるフィルタ手法を開発した。 MCMCの濃度不等式に基づいて, 政策勾配法を期待する定常点の収束性を確立した。 数値的な結果は、このフレームワークが、非常に少数のバイナリ最適化問題に対して、ほぼ最適のソリューションを提供することを非常に約束していることを示している。

関連論文リスト

• Landscape of Policy Optimization for Finite Horizon MDPs with General State and Action [10.219627570276689]
  我々は、一般的な状態と空間を持つマルコフ決定過程のクラスのためのフレームワークを開発する。 勾配法は非漸近条件で大域的最適ポリシーに収束することを示す。 その結果,多周期インベントリシステムにおける最初の複雑性が確立された。
  論文  参考訳（メタデータ） (2024-09-25T17:56:02Z)
• Diffusion Stochastic Optimization for Min-Max Problems [33.73046548872663]
  楽観的勾配法はミニマックス最適化問題に対処するのに有用である。 従来のバージョンでは大きなバッチサイズが必要であり,Samevareps-generativeOGOGと呼ばれる新しい定式化を導入,解析する。
  論文  参考訳（メタデータ） (2024-01-26T01:16:59Z)
• 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)
• Moreau Envelope ADMM for Decentralized Weakly Convex Optimization [55.2289666758254]
  本稿では,分散最適化のための乗算器の交互方向法(ADMM)の近位変種を提案する。 数値実験の結果,本手法は広く用いられている手法よりも高速かつ堅牢であることが示された。
  論文  参考訳（メタデータ） (2023-08-31T14:16:30Z)
• Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs [107.28031292946774]
  無限水平割引マルコフ決定過程(拘束型MDP)の最適ポリシの計算問題について検討する。 我々は, 最適制約付きポリシーに反復的に対応し, 非漸近収束性を持つ2つの単一スケールポリシーに基づく原始双対アルゴリズムを開発した。 我々の知る限り、この研究は制約付きMDPにおける単一時間スケールアルゴリズムの非漸近的な最後の収束結果となる。
  論文  参考訳（メタデータ） (2023-06-20T17:27:31Z)
• Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policies [115.86431674214282]
  我々は、無限水平割引マルコフ決定過程を考察し、自然政策勾配(NPG)とQ-NPG法の収束率を対数線形ポリシークラスで検討する。 両手法が線形収束率と $mathcalO (1/epsilon2)$サンプル複雑度を, 単純で非適応的な幾何的に増加するステップサイズを用いて達成できることを示す。
  論文  参考訳（メタデータ） (2022-10-04T06:17:52Z)
• Distributed Policy Gradient with Variance Reduction in Multi-Agent Reinforcement Learning [7.4447396913959185]
  本稿では,協調型マルチエージェント強化学習(MARL)における分散ポリシ勾配について検討する。 通信ネットワーク上のエージェントは、すべてのエージェントのローカルリターンの平均を最大化するための最適なポリシーを見つけることを目的としている。
  論文  参考訳（メタデータ） (2021-11-25T08:07:30Z)
• Efficient semidefinite bounds for multi-label discrete graphical models [6.226454551201676]
  このようなモデルにおける主要なクエリの1つは、Posteri(MAP)ネットワークのコストに関するSDPWCSP関数を特定することである。 従来の二重化制約手法と,行ごとの更新に基づく専用SDP/Monteiroスタイルの手法を検討する。
  論文  参考訳（メタデータ） (2021-11-24T13:38:34Z)
• Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
  無限水平マルコフ決定過程(MDP)における最適政策学習の問題を考える。 リプシッツ連続関数を用いた凸プログラミング問題に対してミラー・ディクセントの変種が提案されている。 このアルゴリズムを一般の場合において解析し,提案手法の動作中に誤差を蓄積しない収束率の推定値を得る。
  論文  参考訳（メタデータ） (2021-02-27T19:28:39Z)
• Policy Gradient Methods for the Noisy Linear Quadratic Regulator over a Finite Horizon [3.867363075280544]
  線形2次レギュレータ(LQR)問題における最適ポリシーを見つけるための強化学習法について検討する。 我々は、有限時間地平線と弱い仮定の下での状態ダイナミクスの設定に対する大域的線形収束を保証する。 基礎となるダイナミクスのモデルを仮定し、データに直接メソッドを適用する場合の結果を示す。
  論文  参考訳（メタデータ） (2020-11-20T09:51:49Z)
• GACEM: Generalized Autoregressive Cross Entropy Method for Multi-Modal Black Box Constraint Satisfaction [69.94831587339539]
  本稿では,マスク付き自己回帰ニューラルネットワークを用いて解空間上の均一分布をモデル化するクロスエントロピー法(CEM)を提案する。 我々のアルゴリズムは複雑な解空間を表現でき、様々な異なる解領域を追跡できる。
  論文  参考訳（メタデータ） (2020-02-17T20:21:20Z)

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

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