An Actor-Critic Method for Simulation-Based Optimization

Simulation-based optimization problems arise in various disciplines such as computer science, economics, and so on. In general, an simulation-based optimization problem consists of maximizing (minimizing) a score (cost) function by choosing appropriate designs from an allowed set, and can be typically formulated as

where $x$ is a design from the allowed set $X$ defined by the constraints $f_{i}(x)\leq 0,~{}i=1,2,\cdots,m$, and $f_{0}(\cdot)$ is the objective function, which is usually computationally expensive and can be queried only for limited times. The design $x$ can either be a scalar or vector depending on the problem.

There are various works to deal with different cases of (1), e.g., convex optimization deals with the case that all of $f_{i}(\cdot),~{}i=1,2,\cdots,m$ and $-f_{0}(\cdot)$ are convex ( [1]), and deep learning deals with the case that $f_{0}(\cdot)$ is totally or partially calculated by Neural Networks (NNs). However, in both above two cases, the operation rules are designed and utilized during the optimization process, e.g., convex optimization utilizes the gradient or second gradient of $f_{0}(\cdot)$, and deep learning requires the gradient to all parameters of the NNs. Thus these methods are not suited for simulation-based optimization, where the gradient message cannot be obtained explicitly.

In order to address the issues brought by the “incomplete” objective functions, researchers propose to “reconstruct” it with a controllable surrogate model, which is usually a predictive model constructed by fitting the existing input-output pairs. Since that a certain deviation between the surrogate model and the true simulation model $f_{0}(\cdot)$ cannot be avoided, related methods are usually designed to alternate between updating the surrogate model and the sampling distribution. For example, in Bayesian Optimization (BO, [2]), the Gaussian Process (GP, [3]) serves as the surrogate model, and the updating process alternates between proposing the best design with the acquisition function constructed with the surrogate model and updating the surrogate model with the latest input-output pair. BO has the advantage of high efficiency, but there are some technical difficulties, e.g., finding the design $x$ with the highest score on the acquisition function is non-trivial, especially in high dimensional cases. The acquisition function is a predictive model, which can only predict the performance on any $x\in\mathcal{X}$, rather than generating the best design $x^{*}$, which is essential in many real tasks, such as identifying the best parameters for controlling the robots. In these cases, beyond the surrogate model, a generative model must be equipped to identify the best design $x^{*}$.

The generative model generates a distribution over $\mathcal{X}$, which controls the sampling process. Therefore, the sampling distribution can be bridged to a stochastic control problem ( [4]), which adjusts the sampling distribution basing on previous information to reach higher expected score on the simulation model $f_{0}(\cdot)$. The generative model is commonly used in AC-based RL, e.g., DDPG ( [5]), TD3 ( [6]) and SAC ( [7]). It is also termed as “actor” in AC framework, which generates a distribution over the action space (similar as the design space in simulation-based optimization) for each system state (more details can be found in papers mentioned above).

In this work, we also consider the simulation-based optimization problem, where the operation rule of the simulation model $f(\cdot)$ cannot be utilized in the optimizing process. Similar as BO, a surrogate model will be used to predict the scores on untested designs. In order to overcome the difficulty of finding the global optimal of the acquisition function, which is usually highly non-linear, we also introduce a generative model in our framework. Therefore, our methods inherit the framework of AC in RL area. The framework here is especially similar to that of SAC, which is the state-of-art RL algorithm. The predictive model is termed as critic, which predicts $\hat{y}\approx f_{0}(x)$ for each $x\in\mathcal{X}$, and the generative model is termed as actor, which will be updated to reach higher expected score on $f_{0}(\cdot)$. Each iteration starts with generating designs by the actor. These designs will be scored by the simulation model, and the obtained input-output pairs will be used to update the critic. The final step is updating the actor with the latest critic.

The contributions of this paper are mainly as follows:

1) Two AC-based algorithms are designed to solve the simulation-based optimization problem, where design space can be either continuous or discrete;

2) We take two high dimensional tasks, adversarial attack and RL, as examples to show the application on real tasks, and the results show that the proposed algorithms can successfully find satisfying solutions, even in the high dimensional cases;

3) Compared with existing RL methods, e.g., Dynamic Programming (DP, [8]), Q-learning ( [9]), DDPG, and SAC, which are motivated by optimizing the policy itself, the proposed algorithms offer a new perspective to robot control of reinforcing the policy through optimizing the policy generating process. Besides, the induced methods can be deployed in an off-policy fashion and avoid the problem of sparse and delayed reward.

Let us begin with introducing the problem of interest and the Actor-Critic (AC) framework extensively used in Reinforcement Learning (RL) technology.

Let us introduce the methodology of solving (2) with AC framework. The cases where $\mathcal{X}$ is continuous and discrete will be separately considered.

We use NNs to construct the actor and critic (Fig. 1). The actor takes a random noise (or constant) as input to capture the multi-modal (or single-modal) distributions, and the critic takes the design $x$ as input and outputs a predicted score.

The actor and critic are updated iteratively. Each iteration starts with generating a feasible design $x$ and getting its score $y=f(x)$ by querying the simulation model $f(\cdot)$. The $(x,y)$ pair will be stored in a replay buffer $\mathcal{D}$. Then a mini-batch $\mathcal{B}_{q}$ will be sampled from $\mathcal{D}$ to update the critic by minimizing the loss function:

with one step of gradient descent:

Finally, the actor will be updated with the latest critic.

A stochastic actor is used to generate designs, and in each iteration, the sampling distribution will be updated to improve the expected score. In order to reduce the risk of falling into local optimal, we use entropy regularization to reach the trade-off between exploitation and exploration. The updating rule of the actor will be studied for continuous and discrete design space respectively.

In this section, we will start from a toy example, with which some intuitive interpretation of Algorithm 1 and 2 will be given. Then we design some complex tasks, e.g., adversarial attack and reinforcement learning, to show the effectiveness of the proposed algorithms in large-scale systems.

Firstly, we choose the probability density function of a Gaussian Mixture Model (GMM) as the toy example:

and the parameters are set as $w_{1}=0.51$, $w_{2}=0.49$, $\mu_{1}=-0.7$, $\mu_{2}=0.7$, $\sigma_{1}=0.6$, $\sigma_{2}=0.6$.

We launch Algorithm 1 and the results are shown in Fig. 2. It can be found that the sampling distribution gradually converges to the optimal area as $\alpha$ decreases, which means by setting an appropriate $\alpha$ to controls the strength of the entropy regularization, satisfying designs can be drawn from the final actor. To analysis the effect of entropy regularization, $\alpha$ is set as $10^{-1}$, $10^{-2}$, and $10^{-3}$ respectively. Compared with smaller $\alpha$ in Fig. 2(b) and Fig. 2(c), the actor in Fig. 2(a) generates almost an uniform distribution, which means that the entropy regularization has a greater impact on the objective in (9). Besides, since the samples distribute more evenly over the allowed set, the predicted scores are close to the ground truth almost everywhere. With $\alpha$ decreasing, the sampling distribution narrows to the optimal area (Fig. 2(b) and Fig. 2(c)), which means that the actor can generate satisfying designs. However, the samples concentrate in some areas, which leads to worse performance of the critic in other areas, as illustrated in Fig. 2(c). We also test the performance of a deterministic actor, as in DDPG ( [5]), where the actor only generates a deterministic design, rather than a distribution over the design space. The final design falls into the local optimal more easily, as illustrated in Fig. 2(d). In real implementation, we usually set a larger $\alpha$ in the initial phase, and decrease it step by step. In this way, the sampling distribution can converge to the neighbor area of the global optimal, while avoiding falling into local optimal.

The simulation model (24) is modified to test Algorithm 2 by converting the design space $\mathcal{X}$ to a discrete set. The results are shown in Fig. 3. It can be found that by decreasing the strength of entropy regularization, the sampling distribution gradually converges to the optimal area. We also compare the effect of the entropy regularization by setting $\alpha$ as $10^{-1}$, $10^{-2}$, and $\alpha=10^{-3}$. When a larger $\alpha$ is chosen, e.g., $\alpha=10^{-1}$ in Fig. 3(a), the actor generates nearly uniform distribution. When decreasing it, the learned distribution gradually converges to designs with higher scores, as in Fig. 3(b) and Fig. 3(c). However, if $\alpha$ is set too small, the actor may fall into local optimal, as illustrated in Fig. 3(d). Therefore, in real implementation, we also set a bigger $\alpha$ in the initial phase and decrease it step by step as in the continuous case. Furthermore, it can be found that the distribution $P^{\theta}(\cdot)$ generated by the actor is very close to the optimal one $P^{*}(\cdot)$, which validates the theoretical analysis.

After the toy examples, we design more complex tasks to validate the proposed algorithms.

The first task is abstracted from adversarial attack tasks. In these tasks, we need to generate samples to “cheat” some NNs, which are trained to recognize the objects in the input pictures. In this experiment, we train a classifier to recognize digital numbers with the public data set MNIST. The classifier $D(\cdot)$ takes an image $x^{\prime}$ as input and generates a distribution over $Y=\{0,1,2,\cdots,9\}$, which denotes the confidence of classifying the digital image to corresponding value. For the convenience of later representation, the distribution is denoted as $D(x^{\prime})\in R^{10}$ and $D(x^{\prime},i),i\in Y$ denotes the confidence of classifying the image $x^{\prime}\in R^{W\times H}$ into $i$, where by slight abuse of notations, here the $W$ and $H$ are the size of images. In the adversarial attack tasks, we need to generate some fake images to enhance the data set and train a more robust classifier.

In order to generate the fake images, we construct the following simulation model:

where $x\in R^{(W\times H)}$ and $r(\cdot)$ is the resizing operator converting the input vector to the appropriate shape. The linear mapping $\frac{x+1}{2}$ converts the value range from $(-1,1)$ to $(0,1)$, which is the same as the images in the date set. Then by solving the optimization problem (2), the actor can generate fake images which can mislead the classifier to believe it as $i$. We choose $i=1$ in our experiments. The learning curve is illustrated in Fig. 4(a), where we can find that within $1000$ episodes (only 1 sample is evaluated by $f(\cdot)$ in each episode), the average confidence reaches over $0.95$. Before the $500$-th episode, the average confidence is close to $0$, which may be caused by the low-accuracy critic. After the $500$-th episode, the score increases gradually, which means both the actor and critic are improved. One of the images generated by the final actor is shown in Fig. 4(b). It is just some noise from the viewpoint of humans, but the classifier tends to predict it as the digital number “1”.

Another type of fake images are also preferred, which remain the features of the initial digital number, but mislead the classifier to make wrong decisions by adding some special noise. In order to generate these images, we construct following simulation model:

where the operator $c$ clips the input variables to $[0,1]$, and $\delta$ is a small constant controlling the noise level, which is set as $0.2$ in our experiment. Besides, $x_{j}$ is an image from the initial data set, whose label is $j$. In this case, the simulation-based optimization problem (2) tends to find special noise by adding which the classifier will wrongly classify the image from $j$ to $i$.

The result is shown in Fig. 5. After about $2000$ episodes, the actor can generate noise “special” enough to mislead the classifier. We present the noisy image at episodes $0$, $1500$, and $3000$. All of these images remain the features of “6” in the viewpoint of humans, but the classifier will be “cheated” to make wrong decisions.

Finally, we apply Algorithm 1 to a more complex task, i.e., RL task. In typical policy-based and AC-based RL algorithms, the policy is parameterized by $\zeta$ and generates action corresponding to each state. In existing RL methods, the parameter $\zeta$ is adjusted by Policy Gradient (PG) algorithms, as in TRPO ( [11]), PPO( [12]), or Deterministic Policy Gradient (DPG) algorithms, as in DDPG ( [5]) and TD3 ( [6]), to reach higher accumulated reward. While in this work, we directly treat the task as a simulation-based model, where $\zeta$ is a concrete design. We take the “CartPole-v0” environment ( [13]) in Fig. 6(a) as example and deploy Algorithm 1 to it. The result is shown in Fig. 6(b), where we can find that the policy (generated design) is successfully reinforced to reach higher score. Although existing methods in RL area have better performance in these RL tasks, our methods offer a new perspective to robot control, which may be helpful to solve the problem of sparse and delayed reward widely existing in RL problems.

We design these examples to show the application of our proposed methods, as well as validate their performance on large-scale problems. The results will be further concluded in the next section.

In this work, we consider the simulation-based optimization problem of selecting the best design with a computationally expensive evaluation model. The sampling process is bridged to the policy optimization problem and solved under the AC framework, where the critic serves as the surrogate model predicting the scores of untested designs, and the actor encodes the sampling distribution. We propose algorithms to update the actor and critic for continuous and discrete design space respectively, and design experiments to validate their effectiveness, as well as explain the applications. The results show that our methods can successfully find satisfying designs and avoid falling into the local optimal to a certain extent. We note that in the experiment of the RL task, we offer a new perspective to robot control of optimizing the policy generating process, rather than optimizing the policy itself. This may be helpful to solve the problem of sparse and delayed reward in existing works. The new perspective will also be studied in future work. Another direction that will be researched in the future is adjusting the hyper-parameter $\alpha$ automatically, as in [14].