Reinforcement-learning-based Algorithms for Optimization Problems and Applications to Inverse Problems

Chen Xu, Zhipeng Lü, Ye Zhang, Zhang, YearXiv 2023 · DOI · arXiv

Abstract

We design a new iterative algorithm, called REINFORCE-OPT, for solving a general type of optimization problems. This algorithm parameterizes the solution search rule and iteratively updates the parameter using a reinforcement learning (RL) algorithm resembling REINFORCE. To gain a deeper understanding of the RL-based methods, we show that REINFORCE-OPT essentially solves a stochastic version of the given optimization problem, and that under standard assumptions, the searching rule parameter almost surely converges to a locally optimal value. Experiments show that REINFORCE-OPT outperforms other optimization methods such as gradient descent, the genetic algorithm, and particle swarm optimization, via its ability to escape from locally optimal solutions and its robustness to the choice of initial values. With rigorous derivations, we formally introduce the use of reinforcement learning to deal with inverse problems. By choosing specific probability models for the action-selection rule, we can also connect our approach to the conventional methods of Tikhonov regularization and iterative regularization. We take non-linear integral equations and parameter-identification problems in partial differential equations as examples to show how reinforcement learning can be applied in solving non-linear inverse problems. The numerical experiments highlight the strong performance of REINFORCE-OPT, as well as its ability to quantify uncertainty in error estimates and identify multiple solutions for ill-posed inverse problems that lack solution stability and uniqueness.

Introduction

Optimization is the backbone of modern engineering, but real-world problems are rarely well-behaved. Two major hurdles persist in traditional approaches: non-convexity and ill-posed inverse problems. Gradient-based methods often get "trapped" in local minima, failing to find global solutions. In fields like medical imaging or spectroscopy, inverse problems—calculating hidden causes from noisy effects—are frequently "ill-posed," meaning solutions may not be unique or are highly sensitive to noise. While meta-heuristic algorithms and reinforcement learning (RL) have been used to tackle these, they often lack a rigorous mathematical foundation. This paper introduces REINFORCE-OPT, providing a theoretical bridge between RL and classical mathematical techniques like Tikhonov regularization.

REINFORCE-OPT: Methodology

The authors propose REINFORCE-OPT, which treats optimization as a Markov Decision Process (MDP). Instead of iteratively updating a single solution point $x$, the algorithm parameterizes a "search rule" (a policy) $\pi_\theta$. This policy—often represented by a neural network—suggests the next points to explore in the solution space.

The algorithm uses a variation of the REINFORCE algorithm to update the parameters $\theta$. The "reward" is the value of the objective function at the sampled points. A key contribution is the proof that REINFORCE-OPT essentially solves a stochastic, regularized version of the original problem. By choosing specific probability models for the search rule (like a Gaussian distribution), REINFORCE-OPT becomes mathematically equivalent to classical methods like Tikhonov regularization or Landweber iteration.

Mathematical notations for the REINFORCE-OPT framework (Part 1).

Experimental Evaluation

The paper evaluates the algorithm using a mix of synthetic benchmarks and complex physical simulations:

  • Synthetic Landscapes: 1D and 2D non-convex functions designed to trap local searchers.
  • Auto-convolution Equations: A 1D non-linear integral equation (discretized to 64 dimensions) commonly found in spectroscopy.
  • Liquid Chromatography PDE: A parameter-identification problem involving non-linear Partial Differential Equations (PDEs) to model chemical movement through a column, using a "bi-Langmuir" model with 8 parameters.

Key Results

  • Global Search Capability: In 2D non-convex tests, REINFORCE-OPT successfully escaped local minima where Gradient Descent failed.
  • High Dimensionality: The algorithm handled a 64-dimensional inverse problem effectively, exceeding the typical ~20-dimension limit of methods like Bayesian Optimization.
  • Accuracy in PDEs: In the liquid chromatography experiment, the algorithm identified parameters with $R^2$ scores above 91%, even with multiple possible solutions.
  • Superiority over Meta-heuristics: REINFORCE-OPT consistently outperformed Genetic Algorithms (GA), Particle Swarm Optimization (PSO), and Cross-Entropy methods, especially when the optimum lay outside the initial sampling region.

Discussion

REINFORCE-OPT leverages stochasticity as a tool. By learning a distribution of solutions rather than a single point, the algorithm can "jump" across valleys in the error landscape. This makes it robust to initialization; unlike GA or PSO, it finds global optima even from poor initial guesses. Furthermore, because the algorithm produces a probabilistic search rule, it enables built-in uncertainty quantification. Bootstrapping can generate confidence intervals, providing researchers with both a "best guess" and a measure of certainty. For ill-posed problems with multiple valid solutions, REINFORCE-OPT can identify different solution clusters, a significant advantage over standard supervised models.

Conclusion

While REINFORCE-OPT shows great promise, it faces the classic RL challenge of high variance due to Monte Carlo sampling. Future work will explore Actor-Critic methods to reduce variance and speed up convergence. Additionally, the framework's natural suitability for large-scale discrete optimization problems remains an area for further exploration.

Summary updated

Abstract

We design a new iterative algorithm, called REINFORCE-OPT, for solving a general type of optimization problems. This algorithm parameterizes the solution search rule and iteratively updates the parameter using a reinforcement learning (RL) algorithm resembling REINFORCE. To gain a deeper understanding of the RL-based methods, we show that REINFORCE-OPT essentially solves a stochastic version of the given optimization problem, and that under standard assumptions, the searching rule parameter almost surely converges to a locally optimal value. Experiments show that REINFORCE-OPT outperforms other optimization methods such as gradient descent, the genetic algorithm, and particle swarm optimization, via its ability to escape from locally optimal solutions and its robustness to the choice of initial values. With rigorous derivations, we formally introduce the use of reinforcement learning to deal with inverse problems. By choosing specific probability models for the action-selection rule, we can also connect our approach to the conventional methods of Tikhonov regularization and iterative regularization. We take non-linear integral equations and parameter-identification problems in partial differential equations as examples to show how reinforcement learning can be applied in solving non-linear inverse problems. The numerical experiments highlight the strong performance of REINFORCE-OPT, as well as its ability to quantify uncertainty in error estimates and identify multiple solutions for ill-posed inverse problems that lack solution stability and uniqueness.
BibTeX
@misc{xu2023reinforcement,
  author = {Chen Xu and Zhipeng Lü and Ye Zhang and Zhang, Ye},
  title = {{Reinforcement-learning-based Algorithms for Optimization Problems and Applications to Inverse Problems}},
  year = {2023},
  eprint = {2310.06711},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2310.06711},
}
Figure