Monte Carlo Policy Gradient Method for Binary Optimization
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.
Code (1)
Tasks
Combinatorial OptimizationDiversityStochastic OptimizationSimilar Papers 제목 키워드 기반
Monte-Carlo Tree Search for Policy Optimization
Gradient-based methods are often used for policy optimization in deep reinforcement learning, despite being vulnerable to local optima and saddle points. Although gradient-free methods (e.g., genetic algorithms or evolut…
Deep Reinforcement Learningreinforcement-learningReinforcement LearningReinforcement Learning (RL)Policy Learning and Evaluation with Randomized Quasi-Monte Carlo
Reinforcement learning constantly deals with hard integrals, for example when computing expectations in policy evaluation and policy iteration. These integrals are rarely analytically solvable and typically estimated wit…
continuous-controlContinuous ControlPolicy Gradient MethodsReinforcement Learning (RL)Deep Bayesian Quadrature Policy Optimization
We study the problem of obtaining accurate policy gradient estimates using a finite number of samples. Monte-Carlo methods have been the default choice for policy gradient estimation, despite suffering from high variance…
continuous-controlContinuous ControlPolicy Gradient MethodsMarkov Chain Monte Carlo Policy Optimization
Discovering approximately optimal policies in domains is crucial to applying reinforcement learning (RL) in many real-world scenarios, which is termed as policy optimization. By viewing the policy optimization from the p…
continuous-controlContinuous Controlreinforcement-learningReinforcement Learning (RL)+1Adaptive Correlated Monte Carlo for Contextual Categorical Sequence Generation
Sequence generation models are commonly refined with reinforcement learning over user-defined metrics. However, high gradient variance hinders the practical use of this method. To stabilize this method, we adapt to conte…
Image CaptioningProgram SynthesisReinforcement Learning