1 Introduction↩︎

Combinatorial optimization (CO) problems arise across diverse industrial domains, but they are notoriously challenging to solve. In CO (e.g., traveling salesman problems; TSP), the massive discrete solution space often leads to NP-hardness. Furthermore, CO problems in practical scenarios often involve computationally expensive objective functions to evaluate (e.g., a black-box function), introducing significant restrictions on the problem-solving process. Even though solving CO problems with expensive objective functions is frequently found in various fields like drug discovery or hardware design, it has numerous challenges.

Recent advances in deep reinforcement learning (DRL) have drawn significant attention as an alternative way to solving CO problems. Various studies have demonstrated remarkable achievements across broad domains, including routing [1]–[3], scheduling [4], [5], and material design [6]–[8]. Especially in constructive methods, where a solution is sequentially built from an empty set, it is beneficial to guarantee feasibility to practical constraints using a masking strategy. Note that in the constructive method, a policy generates a trajectory, and the reward is evaluated in a terminal state, i.e., episodic rewards.

DRL methods generally leverage extensive samples to enhance training stability, assuming reward evaluation is affordable. However, in practice, reward computation can be costly due to several factors: (1) objective functions often cannot be defined analytically, requiring computationally intensive simulations for evaluation, such as in black-box optimization; or (2) objective functions may be analytically defined but still demand additional computation, such as solving another optimization problem (e.g., bi-level optimization). For instance, in molecular optimization, evaluating designed molecules in real-world scenarios involves costly assessments, such as wet lab experiments [9]. In this regard, reducing the number of reward evaluations is significantly beneficial. This discrepancy raises a straightforward research question: How can we enhance the sample efficiency of DRL methods for a broad spectrum of CO problems and methods?

This paper proposes a simple yet effective add-on method, symmetric replay training (SRT), which is a generic method that leverages the solution-symmetric nature of combinatorial space. In DRL for CO, multiple action sequences (i.e., action trajectories) can be mapped to a single combinatorial solution, and the reward is defined on the terminal state (i.e., solution). Previous studies have tried to consider the symmetries in CO, but they utilize numerous samples [2], [10] or assume the specific method [11] or problem [12]. To effectively utilize symmetries in CO, we suggest a decomposed training process in two steps: reward-maximizing training and symmetric replay training. The two-step training also allows efficient exploration in the vast action trajectory space.

Reward-maximizing training is conducted with a conventional DRL algorithm, which involves the exploration of the high-rewarded action trajectories over the entire action space. Subsequently, symmetric replay training bootstraps the policy to explore symmetric regions without additional reward evaluation, leading to improved sample efficiency. In detail, the high-rewarded action trajectories obtained in the previous step are symmetrically transformed, and then the policy is trained to imitate these symmetric action trajectories. As illustrated in 1, the symmetric replay training promotes the exploration of under-explored regions containing trajectories equivariant to the high-rewarded trajectories collected from reward-maximizing training.

The two decomposed training steps, reward-maximizing and symmetric replay training, are effectively inter-operated: one seeks the high-reward samples, while the other recycles the explored samples to explore symmetric regions for free. Symmetric replay training strategically leverages previously high-rewarded trajectories without necessitating additional reward evaluation. Our policy is trained to maximize the likelihood of high-rewarded trajectories in the symmetric region, encouraging exploration of under-explored areas. Additionally, replaying symmetric trajectories incorporates symmetric priors, relieving the overfitting of replay training. Since the policy perceives these symmetric trajectories as heterogeneous, SRT is advantageous in scaling up the replay loop to further utilize collected samples before re-interacting with the environment.

For a better comprehension of symmetric replay training, this paper explores three straightforward strategies: (1) maximum entropy, (2) adversarial, and (3) importance sampling transformations. They provide theoretical and empirical insights for SRT. Note that the maximum entropy transformation is primarily adopted since it is a generic approach with low computational complexity while effectively improving sample efficiency in various tasks.

We empirically demonstrate that symmetric replay training consistently improves the sample efficiency by plugging it into various DRL methods with simple implementation. The experimental results show that plugging our method into the state-of-the-art DRL method can achieve superior performance in hardware design optimization and sample-efficient molecular optimization by adding it to the competitive DRL method. Here is a highlight of our contribution:

1. We propose a generic method, symmetric replay training (SRT), which enhances the sample efficiency of various DRL methods for CO. The proposed method is empirically demonstrated as simple yet effective, by consistently improving various DRL methods, both on-policy and off-policy, in various tasks.

2. We investigate various symmetric transformation strategies for replay training, offering both theoretical and empirical perspectives that could benefit future efforts in SRT-like replay training approaches.

3. We conduct comprehensive experiments with a broad range of DRL methods and various CO tasks. We benchmark the DRL methods from on-policy to off-policy methods across various tasks from classical TSP to practical hardware design optimization, which can contribute to DRL for CO communities.

2 Related Works↩︎

2.1 Symmetries in DRL for CO↩︎

Several works have been studied to utilize the symmetric nature of combinatorial optimization. Representatively, the Policy Optimization for Multiple Optima [2] and Symmetric Neural Combinatorial Optimization [10] are proposed. These methods sample multiple trajectories from a single problem by forcing \(N\) heterogeneous starting point based on the TSP’s cyclic symmetries [2] or giving symmetric input noise to make wide exploration [10]. Importantly, they use symmetries to effectively evaluate the REINFORCE baseline, which stabilizes training by effectively reducing the variance. However, they associate extensive reward evaluation, while ours does not require additional sample evaluations to utilize symmetries. Furthermore, the results in 10.7 demonstrate that SRT can further improve the sample efficiency of these methods. The improvements come from the difference that they take account of symmetries in input space, while ours utilize symmetries in output (action trajectories) space.

Separately, Generative Flow Networks [8], which represents the combinatorial space in CO problems with a directed acyclic graph, were proposed. We discuss the relationship with GFlowNet in 4.4.

2.2 Data Augmentation↩︎

The symmetric transformation shares a similar concept with data augmentation techniques, such as cropping [13], [14], noise injection [13], [15], and Mixup [15], [16], all of which can contribute to improved sample efficiency. However, most data augmentation methods focus on continuous space. Notably, recent efforts have been made to adapt data augmentation NLP tasks [17]–[20]. One of the key ideas is to obtain informative samples while keeping the semantics of original sentences, [21], [22]. Notably, [20] introduces a learnable augmentation policy that constructs difficult but not too different samples (DND). As our symmetric transformation preserves the solutions by utilizing the nature of CO tasks, augmenting trajectories does not lose semantics. Note that the adversarial transformation is designed to find difficult samples akin to DND.

In CO, [12] presented a label-preserving augmentation in contrastive learning for the Boolean satisfiability problem. Additionally, [11] utilized augmentation, including flipping, in supervised learning for the TSP. Lastly, [23] suggested an additional loss term using symmetrically augmented data in hardware design. These works suggested data augmentation based on symmetries, which is integrated into a specific learning framework. On the other hand, our paper introduces a generic method to enhance diverse DRL methods across various domains. We empirically show that the separated MLE training of SRT is also beneficial compared to data augmentation training; see 10.3. Note that SRT uses imitation loss, which allows training with augmented trajectories without introducing importance weights, even in on-policy DRL.

2.3 Replay Ratio Scaling↩︎

Increasing the number of replay loops is highly related to scaling up the replay ratio, which means the number of parameter updates per environment interaction [24]–[26]. Replay ratio is also known as update-to-data (UTD) ratio [27], [28]. Although the benefits of replay ratio scaling are limited, it has demonstrated improved performance, particularly on well-tuned algorithms [27]–[29]. Recently, [26] achieved better replay ratio scaling with parameter reset strategy by mitigating the loss of ability to generalize on model-free RL. Most replay ratio scaling approaches assume the utilization of replay training, thus off-policy training, and propose how to further increase replay ratio by preventing overfitting or primacy biases [26], [30]. On the other hand, we propose a new replay method both for off-policy and on-policy training in CO. Though SRT demonstrates that it can increase replay ratio less suffering from overfitting, other replay ratio scaling approaches like periodic resetting policy parameters or sophisticated design for experience buffer can be incorporated to enhance sample efficiency further.

We provide further related works in 11.

3 Background↩︎

Our method aims to improve the sample efficiency of deep reinforcement learning for solving combinatorial optimization with expensive reward function. Specifically, we consider combinatorial optimization as maximization of the black-box function \(f(x)\) over a discrete set \(\mathcal{X}\), i.e., \[\max_{x \in \mathcal{X}}f(x).\] To solve this problem, we formulate the construction and evaluation of the solution as a Markov decision process (MDP). In the MDP, we let each state \(s\) describe a subsequence of the action trajectory with problem context \(\boldsymbol{c}\), i.e., \(s_t = \{(a_1, \ldots, a_{t-1}), \boldsymbol{c}\}\). The initial state corresponds to an empty, i.e., \(s_1=\{ \emptyset, \boldsymbol{c}\}\), and the final state corresponds to a complete sequence of actions, i.e., \(s_{T}= \{\vec{a}, \boldsymbol{c}\}\), giving a solution \(x\). Then, a policy \(\pi(s'|s )\) decides a transition between states, \(s \rightarrow s'\), by selecting an action \(a\) to be updated to the incomplete solution described by the state \(s\). We assume that the transition is deterministic, meaning that the next state is determined by a specific transition function.

We further impose two conditions on the MDP that exploit the prior knowledge about combinatorial optimization problems considered in this work. First, we assume the reward is episodic, i.e., given a terminated action-state trajectory associated with a solution \(x\), the reward \(R(s_{T}) = f(x)\) and \(R(s_{t})=0\) for \(t < T\). Note that the \(s_{T}\) contains the action sequence \(\vec{a}\), giving a solution \(x\). The next condition is that the action space \(\mathcal{A}_{t}\) at each state \(s_{t}\) only consists of actions that generate a valid solution.

4 Methodology↩︎

Our method, symmetric replay training (SRT), is an add-on method that improves the sample efficiency of DRL for CO by replaying the symmetrically transformed solution. The key idea is to utilize the symmetric natures of CO to generate different trajectories, which induce the same solutions, i.e., solution-preserving transformation; no additional reward evaluations are required as the solution remains unchanged. SRT enhances sample efficiency in two ways: (1) by recycling once-evaluated samples via replay training and (2) by stimulating the exploration of under-explored regions via symmetric trajectories.

Our method repeats the following two policy update loops:

Step A:

Reward-maximizing training. Train the (factorized) policy using a conventional episodic reinforcement learning algorithm.

Step B:

Symmetric replay training

1. Collect high-rewarded trajectories from Step A.

2. Randomly sample trajectories using symmetric transformation policy.

3. Train the policy by imitating the symmetric trajectories.

Intuitively, our Step A is designed to encourage the policy to exploit high-reward samples via reinforcement learning. Then, Step B aims to promote exploration of the symmetric space by imitating the collected high-reward samples with symmetric transformation. Note that the strategies for collecting high-reward samples are flexibly employed according to tasks or DRL methods, such as greedy rollout, reward-prioritized sampling, or top-\(K\) selection.

4.1 Reward-maximizing Training↩︎

Reward-maximizing training corresponds to the original training of deep reinforcement learning (DRL) methods. For simplicity, this step is illustrated using the example of REINFORCE, a widely used DRL algorithm for CO [1], [10], [31]. In reward-maximizing training, the policy \(\pi_\theta\) is trained for a given trajectory \(\tau=(s_1, \ldots, s_T)\) using the loss function defined as follows: \[\begin{align} \mathcal{L}_{\text{RM}} = (R(x) - b) \log \pi_\theta (\tau), \\ where\pi_{\theta}(\tau) = \prod_{t=1}^{T-1} \pi_{\theta}(s_{t+1}|s_t). \end{align}\] Here, \(b\) is a baseline that does not depend on \(x\). It is worth emphasizing that the model and training method in reward-maximizing training are not restricted. Thus, our method allows the application of various DRL methods as a base.

4.2 Symmetric Replay Training↩︎

4.2.1 Symmetric transformation policy↩︎

The symmetric trajectory policy \(p(\tau_{\rightarrow x}|x)\) is a probabilistic distribution that samples symmetric trajectories \(\tau_{\rightarrow x}\), which have an identical terminal state (i.e., an identical solution \(x\)). For example, in the traveling salesman problem (TSP), a representative CO problem, shifting the starting points gives the same solution. In the case of TSP with four cities, the sequences 1-2-3-4-1 and 3-4-1-2-3 represent the identical Hamiltonian cycle \(x\).

For a better comprehensive understanding of the symmetric transformation policy, we investigate possible choices of \(p(\tau_{\rightarrow x}|x)\): maximum entropy, adversarial, and importance sampling transformations.

4.2.1.1 Maximum entropy transformation policy.

By setting \(p(\tau_{\rightarrow x}|x)\) as a uniform distribution, we can achieve the maximum entropy for the training policy \(\pi_\theta(\cdot)\); see 1 in 4.3 for theoretical analysis. Notably, the uniform distribution stands out for its simplicity and \(\mathcal{O}(1)\) sampling cost (e.g., in TSP, a symmetric trajectory is determined by simply choosing the starting point and direction), easily applicable to various tasks. Therefore, we adopt the maximum entropy policy as a default for our experiments.

4.2.1.2 Adversarial transformation policy.

An alternative option is to sample a trajectory that has the minimum log-likelihood under \(\pi_\theta(\tau)\). Formally, symmetric trajectories are selected as follows: \[\min_{\tau \in \mathcal{T}_{\rightarrow x}} \log \pi(\tau),\] where \(\mathcal{T}_{\rightarrow x}\) denotes a set of all trajectories that give a solution \(x\). In the case of TSP, where the number of symmetric trajectories is \(2N\), where \(N\) is the problem size, the sampling cost is \(\mathcal{O}(N)\).

4.2.1.3 Importance sampling transformation policy.

The last option is to sample trajectories based on importance weights, which are set inversely proportional to the log-likelihood. Formally, symmetric trajectories are sampled from \[p(\tau_{\rightarrow x}|x) \propto e^{-\beta\log \pi_\theta(\tau_{\rightarrow x})}.\] Here, \(\beta\) is an inverse temperature, a tunable hyperparameter. Intuitively, it becomes the maximum entropy transformation as \(\beta \rightarrow 0\), and the adversarial transformation as \(\beta \rightarrow \infty\); refer to 7.2 for formal proof. Therefore, having \(0 < \beta < \infty\) can be considered a compromised approach between the maximum entropy and adversarial transformations. Note that evaluating the importance weight requires \(\mathcal{O}(N)\) computations in TSP.

4.2.2 Symmetric replay training↩︎

The symmetric replay training involves maximum likelihood estimation of \(\tau_{\rightarrow x}\) sampled from \(p(\tau_{\rightarrow x}|x)\). The symmetric replay training loss function is derived as follows: \[\label{eq:ssd95loss} \mathcal{L}_{\text{SRT}}(x) = - \mathbb{E}_{p(\tau_{\rightarrow x}|x)}[\log \pi_{\theta}(\tau_{\rightarrow x})]\tag{1}\] The SRT loss function is formulated to maximize the log-likelihood of the symmetric trajectories. To adjust the scale of the loss function, we introduce a scaling coefficient. Roughly, \(\alpha\) is set to make \(\mathcal{L}_{\text{SRT}}\) 10 or 100 times smaller than \(\mathcal{L}_{\text{RM}}\). Note that the high-reward samples are obtained by greedy rollout or selecting Top-\(K\) samples in the mini-batch, and so on.

Our symmetric replay training significantly benefits from additionally exploring the high-rewarded regions on the symmetric space for free. Moreover, we can explore regions that are likely to have higher rewards but are far from the current regions, since the symmetric action trajectory may have a significant edit distance from the original trajectory.¹

4.3 Interplay of Reward-maximizing and Symmetric Replay Training↩︎

This subsection presents an analysis of the interplay between two iterative steps: reward-maximizing training and symmetric replay training. First, we begin with introducing a theorem about the maximization of policy entropy.

Proof. See 7.1 for the entire proof.

In 1, the policy entropy \(\mathcal{H}(\pi_{\theta}(\tau))\) is decomposed into two distinct components: the entropy associated with the solution exploration policy, denoted as \(\mathcal{H}(p(x))\), and the entropy for the symmetric transformation policy, expressed as \(\mathbb{E}_{x \sim p(x)} \mathcal{H}(p(\tau_{\rightarrow x}|x))\). This decomposition offers an intuitive illustration of our two-step learning process. In particular, maximizing the second entropy term encourages the search of various symmetric spaces while preserving high-reward solutions. We achieve this by employing uniform symmetric transformation, represented as \(p(\tau_{\rightarrow x}|x) = U(\tau_{\rightarrow x}|x)\). This approach enables us to maximize entropy exploration within the symmetric space, facilitating a more comprehensive search of potential solutions.

4.4 Relationship with GFlowNets↩︎

Our symmetric transformation policy \(p(\tau_{\rightarrow x}|x)\) is similar to GFlowNet’s backward policy \(P_B(s_t|s_{t+1})\) where both assume the multiple possible (partial) trajectories that leads to identical states: i.e., directed acyclic graph (DAG)-like MDP. While GFlowNets trains policy using a balanced objective with \(P_B\), such as trajectory balance [32], which is known to give slow learning signals when trajectory length is large [33], our method makes direct credit assignment into a trajectory drawn from \(p(\tau_{\rightarrow x}|x)\), which gives faster learning signals. Accordingly, our method significantly improves GFlowNets training efficiency by using our periodic replay training of maximum likelihood estimation in experiments on three tasks.

5 Experiments↩︎

This section presents experiments with three distinct settings: a synthetics scenario and two real-world scenarios of hardware design and sample-efficient molecular optimization. For the synthetic setting, we employ traveling salesman problems (TSP), the widely studied CO problems, for precise analyses of the proposed method. We also provide the experiments on other CO problems in 10.7.

In the subsequent sections, we validate the effectiveness of our method in real-world applications. Firstly, we conduct experiments focused on hardware design optimization, particularly addressing the Decap Placement Problem (DPP), a widely recognized problem within the hardware design domain [34]–[36]. Furthermore, we extend our experiments to the Practical Molecular Optimization (PMO) benchmark [9], a well-established benchmark for sample-efficient molecular optimization. All data and codes are available at https://github.com/kaist-silab/symmetric_replay.

5.1 Synthetic Setting: Traveling Salesman Problems↩︎

In general, CO problems have closed forms of objective functions, which means the reward evaluations are not expensive. However, we conduct experiments on the TSP synthetic dataset assuming that the number of computing objective function values is limited; this allows more controlled experiments and more precise analysis.

5.1.0.1 Tasks.

Traveling salesman problems (TSP) aim to minimize the distance of a tour that visits all customers and returns to the starting point. In TSP, the distance between consequent customers is defined as an Euclidean distance. The auto-regressive policy starts from an empty tour and constructs the (partial) tour by iteratively selecting the next visit. In TSP, a solution denotes a cycle (i.e., a route) without a designated starting point. Thus, symmetric trajectories are obtained by cyclically shifting \(k\) positions to the left or right. Furthermore, in TSP with Euclidean distance, the reversed order of visiting sequence also gives a symmetric action trajectory. We set the maximum reward calls as 2M.

5.1.0.2 Experimental setting.

Our experiments are conducted with AM architecture from [1]. We employ various RL methods, including policy gradient with actor-critic [31], policy gradient with greedy rollout [1], Proximal Policy Optimization [37], and a Generative Flow Network [8], and additionally implement SRT on top of the DRL methods to enhance sample efficiency. Note that GFlowNet is an off-policy method. We basically follow the hyperparameter configuration used in AM. For additional parameters of PPO and GFlowNet, we systematically evaluate several combinations to identify the most optimal configuration. The details about implementations are provided in 8. We measure the average costs on the validation dataset over the number of reward calls (\(K\)) in training with four independent random seeds. In symmetric replay training, we gather confidence trajectories from the up-to-date policy via greedy rollout, assuming that the greedy solution gives a relatively high reward trajectory.

5.1.0.3 Does SRT improve sample efficiency?

As illustrated in 3 and detailed in 1, our approach consistently demonstrates enhanced sample efficiency across various DRL methods. Notably, A2C outperforms the other methods under conditions where the number of available training samples is limited, thereby resulting in the best performance when combined with SRT. The most substantial improvement facilitated by SRT is observed in the case of GFlowNet, where a cost reduction of 3.76% is achieved when the sample size \(K=100\text{K}\). In PG-Rollout, a 1.53% cost reduction is realized with SRT when \(K=2\text{M}\).

5.1.0.4 Overfitting in replay training.

In this section, we investigate the extent to which symmetric replay training can increase the number of replay loops without encountering issues of overfitting. To assess the effectiveness of symmetric transformation in replay training, we perform the same experiments without symmetric transformation (the results are denoted as ‘Non-symmetric’ in 4). As illustrated in 4, our symmetric replay training successfully enhances sample efficiency up to replay loops 16. In contrast, non-symmetric replay training experiences diminished performance when reaching when the loop exceeds 8. This suggests that the symmetric transformation provides trajectories that induce the same solution but are distinctive from the policy’s perspective, contributing to mitigating overfitting from replaying the restricted set of repetitive trajectories.

5.1.0.5 Comparing different strategies of \(p(\tau_{\rightarrow x}|x)\).

We conduct experiments to compare different symmetric transformation policies. The difference of loglikelihood between symmetric trajectories is measured as follows: \[\frac{1}{|\mathcal{T}_{\rightarrow x}|} \sum_{\tau \in \mathcal{T}_{\rightarrow x}} \log \pi_\theta (\tau) - \min_{\tau \in \mathcal{T}_{\rightarrow x}} \log \pi_\theta (\tau)\] As illustrated in 5, the adversarial transformation effectively minimizes log-likelihood differences among symmetric trajectories, thereby enhancing sample efficiency. Despite its effectiveness, the adversarial transformation might not be unavailable when the analytical knowledge of symmetric trajectories is not accessible. On the other hand, the maximum entropy transformation is a more generic approach, so it is advantageous for practical scenarios.

5.1.0.6 Additional experiments.

We provide the experimental results to verify the effectiveness of each choice by ablating the components. Moreover, we compare SRT with experience replay. Ours shows superior performance by not introducing importance weight, leading to low variance and allowing replay training of on-policy methods like A2C. All results are provided in 10.

5.2 Hardware Design Optimization↩︎

5.2.0.1 Tasks.

We employ decoupling capacitor placement problems (DPP), which constitute a fundamental optimization challenge in hardware design. In the context of hardware devices like CPUs and GPUs, a decoupling capacitor (decap) is a critical component responsible for reducing power noises along the power distribution network (PDN). The primary objective of DPP is to identify the optimal arrangement for placing these decaps to maximize the power integrity (PI) objective, which involves computationally expensive evaluations. We tackle two distinct DPP tasks: the chip-package PDN [34] and the High Bandwidth Memory (HBM) PDN [38] with 15K limited reward calls. These two tasks exhibit variations in their PI landscapes, presenting unique challenges. In DPP, permuting the decision orders of decap yields symmetric trajectories.

5.2.0.2 Experimental setting.

We employ a Device Transformer [23] as our base neural architecture, originally designed for offline DPP tasks. In an online optimization context involving interactions with the DPP environment, we integrate well-established DRL methods (A2C, PG, PPO, and GFlowNet) on DevFormer to maximize effectiveness. Similar to the experiment on TSP, we adjust hyperparameters by examining several combinations since DPP tasks have different reward scales. The details are provided in 8. Lastly, we use higher-than-average samples in the online batch as high-rewarded samples. To verify the effectiveness of our methods, SRT is built on these DRL methods to enhance sample efficiency and compare the resulting rewards.

5.2.0.3 Results.

Addressing DPP tasks proved challenging due to the limited online reward calls available. For instance, the PG-Rollout method exhibited high variances, making it less effective at exploring the DPP solution space. This challenge stems from the inherent symmetry of DPP, where multiple trajectories could lead to identical solutions. Conversely, GFlowNet models, incorporating structured bias to handle solution symmetries, showed improved performance compared to non-symmetric DRL methods like PPO. As demonstrated in 2 and 6, significant improvements are observed by applying SRT on top of these methods. The most considerable reward improvement is observed in A2C for chip-package PDN, at 30.54%. In the case of GFlowNet with SRT, exploring focused on the symmetric variants within the high-reward region enhances the sample efficiency by mitigating its underfitting. Notably, the wall-clock comparison results in 10.4 show that SRT effectively enhances performance by achieving significantly lower costs while maintaining similar or slightly increased runtime.

5.3 Practical Molecular Optimization Benchmark↩︎

5.3.0.1 Tasks.

We employ practical molecular optimization [9], whose reward evaluations are limited up to 10K, and the goal is achieving the highest score within the limited reward calls. PMO contains 23 tasks based on different score functions called Oracles; a task is a CO problem that maximizes the given score function, such as QED [39], DRD2 [6] and JNK3 [40]. For example, QED measures drug safety, while the others measure bioactivities against their corresponding disease targets. In de novo molecular optimization, molecules are represented as graphs or strings,² which have multiple ways for a single molecule.

5.3.0.2 Experimental setting.

We build SRT on the GFlowNet [8] and REINVENT [6]. REINVENT is the most competitive DRL method, and GFlowNet is beneficial to generate diverse candidates in the PMO benchmark. Note that REINVENT contains the online experience buffer, so we also collect the replay samples from the experience buffer with the same replay size. For GFlowNet, we set the replay size as the same as the sample batch size. The performance of the methods is evaluated based on the area under the curve (AUC) to consider a combination of optimization ability and sample efficiency. The AUC of the top 10 average performance is mainly reported since it is essential to find distinct molecular candidates to progress to later stages of development in drug discovery. Lastly, as a high-rewarded sample to replay, we gather Top-\(K\) samples from the entire pool of generated samples up to that point in training.

Results. As shown in 3, SRT significantly improves GFlowNet and REINVENT by achieving the enhanced AUC in 12 and 18 oracles out of 23, respectively, not only on average; the statistical analyses are provided in 10.5. Note that REINVENT is regarded as a state-of-the-art method in PMO, and SRT also improves 16 oracles out of 23 in the experiment of REINVENT with SMILES strings; see 10.6. In addition, 7 further demonstrates our method’s effectiveness by illustrating the average scores of the top 10 molecules in the JNK3 and isomer_c7h8n2o2 tasks, revealing a substantial enhancement in sample efficiency.

6 Conclusion↩︎

This study proposes a new approach, called symmetric replay training (SRT), to enhance the sample efficiency of DRL methods for practical combinatorial optimization problems. Our approach improves the sample efficiency by reusing the high-rewarded samples from the policy in the symmetric space, which helps explore new regions without additional reward computation. Replay training through symmetric transformations enhances the sample efficiency by effectively increasing the replay ratio while mitigating the adverse effects of overfitting. The proposed method is a generic add-on approach that can synergize with previously proposed constructive DRL methods across various CO problems. Since our method is conducted separately (in Step B), we do not introduce additional restrictions on training or alter the architecture of base DRL methods (in Step A). Another contribution of our method is the utilization of maximizing log-likelihood loss functions and separated training steps. Therefore, SRT does not introduce importance weight, which often leads to large variances, even when applied with on-policy methods. The extensive experiments verify that our method consistently enhances sample efficiency in various DRL methods in real-world benchmarks, like hardware design and molecular optimization.

Impact Statement↩︎

This research intersects reinforcement learning and combinatorial optimization, areas that inherently involve various industrial and social impacts. However, we believe that this work does not present any unique societal consequences that necessitate specific emphasis beyond those typically associated with these fields.

Acknowledgments↩︎

The authors are grateful to Haeyeon Kim for the help in implementing the hardware design simulator. This work was supported by the Institute of Information & communications Technology Planning & Evaluation (IITP) grant funded by the Korea government (MSIT) (2022-0-01032, Development of Collective Collaboration Intelligence Framework for Internet of Autonomous Things).

7 Proof for Theoretical Analysis in Section 3.2↩︎

7.1 Proof for 1↩︎

Consider \(\pi_{\theta}(\tau)\) as the distribution over the trajectory. Let \(\mathcal{T}_{x}\) denote the space of trajectories associated with the solution \(\boldsymbol{x}\). \[\begin{align} \mathcal{H}(\pi_{\theta}(\tau)) &= -\sum_{\tau \in\mathcal{T}}\pi_{\theta}(\tau) \log \pi_{\theta}(\tau)\\ &= -\sum_{\boldsymbol{x}\in\mathcal{X}}\sum_{\tau_{\rightarrow x} \in \mathcal{T}_{ x}}\pi_{\theta}(\tau) \log \pi_{\theta}(\tau)\\ &= -\sum_{\boldsymbol{x}\in\mathcal{X}}\sum_{\tau_{\rightarrow x} \in \mathcal{T}_{ x}}p(\tau_{\rightarrow x} | \boldsymbol{x}) p(\boldsymbol{x}) \left(\log p(\tau_{\rightarrow x} | \boldsymbol{x}) + \log p(\boldsymbol{x}) \right) \\ &= \mathcal{H}(p(\boldsymbol{x})) + \mathbb{E}_{\boldsymbol{x} \sim p(\boldsymbol{x})} \mathcal{H}(p(\tau_{\rightarrow x}|\boldsymbol{x})) \\ &\leq \mathcal{H}(p(\boldsymbol{x})) + \mathbb{E}_{\boldsymbol{x} \sim p(\boldsymbol{x})} \mathcal{H}(U(\tau_{\rightarrow x}|\boldsymbol{x})), \end{align}\] where \(U(\tau |\boldsymbol{x})\) is a uniform distribution over action-trajectories associated with the solution \(\boldsymbol{x}\). The third equality stems from the fact that \(\pi_{\theta}(\tau) = \pi_{\theta}(\tau, \boldsymbol{x})\) since \(\boldsymbol{x}\) is fixed given \(\tau\). One can show that the final upper-bound is the entropy of distribution obtained from replacing \(p(\tau|\boldsymbol{x})\) by \(U(\tau|\boldsymbol{x})\).

7.2 Extreme Case of Inverse Temperature in Boltzmann Distribution↩︎

Let the energy \(\mathcal{E}(\tau)\) be a log-likelihood of training policy: \(\mathcal{E}(\tau) = \log \pi_{\theta}(\tau)\). Then, statement 1 shows that our important sampling transformation becomes the adversarial transformation. Also, statement 2 shows that our important sampling transformation becomes the maximum entropy (i.e., uniform) transformation.

8 Implementation details↩︎

8.1 Pseudo-code for REINFORCE with SRT↩︎

In this section, we provide a pseudo-code in case of employing REINFORCE as a base DRL method in Step A.

There are various ways to collect high-reward samples in Step B. For example, \(\texttt{GreedyRollout}\) can be replaced with other strategies, such as reward-prioritized sampling or collecting Top-\(k\) samples.

8.2 Proximal policy optimization (PPO)↩︎

We use AM architecture [1] on TSP and Devformer architecture [23] on DPP for parameterizing compositional policy \(\pi(\boldsymbol{x}|s_1) = \prod_{t=1}^N \pi(a_t|s_t)\). Then, we implement based on the following equation as follows:

\[\begin{align} \mathcal{L}(\boldsymbol{x};s_1) &= \min \left[A(\boldsymbol{x};s_1) \frac{\pi(\boldsymbol{x}|s_1)}{\pi_{\text{old}}(\boldsymbol{x}|s_1)}, A(\boldsymbol{x};s_1) \text{clip}\left(\frac{\pi(\boldsymbol{x}|s_1)}{\pi_{\text{old}}(\boldsymbol{x}|s_1)}, 1-\epsilon, 1+\epsilon\right)\right], \\ A(\boldsymbol{x};s_1) &= R(\boldsymbol{x};s_1) - V(s_1), \end{align}\]

where \(R\) stands for reward function and \(V\) stands for value function. Since we implement PPO on compositional MDP setting, we train value function in the context of \(s_1\) by following actor-critic implementation of [1].

8.2.0.1 Hyperparameters.

We systematically investigate a range of hyperparameter combinations involving different baselines ([rollout, critic]), various values for clipping epsilon ([0.1, 0.2, 0.3]), and numbers of inner loops ([5, 10, 20]). Our observations reveal that the critic baseline consistently enhances training stability across all tasks, leading to reduced variation when modifying the training seeds. The best configurations for each task are provided in 4.

8.3 Generative flow network (GFlowNet)↩︎

Similar to the PPO implementation, we employ the Attention Model (AM) architecture [1] on the Traveling Salesman Problem (TSP), and the DevFormer architecture [23] on DPP, for parameterizing the compositional forward policy \(P_F(\tau|s_1) = \prod_{t=1}^N P_F(a_t|s_t)\). Subsequently, we configure the backward policy \(P_B\) as a uniform distribution for all possible parent nodes, following the methodology outlined in [32]. Lastly, we parameterize \(Z(s_1)\) using a two-layer perceptron with ReLU activation functions, where the number of hidden units matches the embedding dimension of the AM or DevFormer. This two-layer perceptron takes input from the mean of the encoded embedding vector obtained from the encoder of the AM or DevFormer and produces a scalar value to estimate the partition function.

To train the GFlowNet model, we use trajectory balance loss introduced in [32] as follows:

\[\mathcal{L}(\tau;s_1) = \left(\log \left(\frac{Z(s_1)P_F(\tau|s_1)}{e^{-\beta E(\boldsymbol{x};s_1)}P_B(\tau|s_1)}\right)\right)^2 \label{eq:tb}\tag{2}\]

The trajectory \(\tau\) includes a terminal state represented as \(\boldsymbol{x}\). Subsequently, we employ an on-policy optimization method to minimize 2 , with trajectories \(\tau\) sampled from the training policy \(P_F\). In this context, \(E(\boldsymbol{x};s_1)\) represents the energy, which is essentially the negative counterpart of the reward \(R(\boldsymbol{x};s_1)\). The hyperparameter \(\beta\) plays the role of temperature adjustment in this process.

8.3.0.1 Hyperparameters.

We explore a spectrum of hyperparameter combinations, varying \(\beta\) ([5, 10, 20]) and numbers of inner loops ([2, 5, 10]). The best configurations for each task are provided in 5.

9 Experimental details↩︎

9.1 Traveling salesman problems (TSP)↩︎

Since we employ the AM architecture, we use the same hyperparameters for the model architecture and training parameters except for the batch and epoch data sizes.³ Initially, the Attention Model (AM) employed a batch size of 512 and an epoch data size of 1,280,000. Notably, the evaluation of the greedy rollout baseline was conducted every epoch. When the number of available training samples is constrained, utilizing a smaller batch size and epoch data size becomes advantageous. Consequently, we adjusted these parameters to be 100 for batch size and 10,000 for epoch data size. In symmetric replay training (Step B), the scale coefficients are meticulously set to scale the SRT loss. As a rough guideline, we establish a coefficient that renders the SRT loss approximately 10 to 100 times smaller than the RL loss. Additionally, for the number of symmetric transformations (\(L\) in 1 ) is set as the number of inner loops. See 6 in details.

9.2 Decap placement problems (DPP)↩︎

Similar to the experiments on TSP, we follow the setting of DevFormer.⁴ We set the batch size as 100 and epoch data size as 600. Note that the maximum number of reward calls is set 15K,, a considerably smaller limit compared to TSP. Regarding the scale coefficient and the number of symmetric transformations, we maintain consistency with the principles applied in the TSP experiments as follows:

9.3 Practical molecular optimization (PMO)↩︎

We basically follow the experimental setting (e.g., batch size) in the practical molecular optimization (PMO) benchmark.⁵ In symmetric replay training, we utilize reward-prioritized sampling for the online buffer, which contains molecules generated during online learning. For the REINVENT, where the replay buffer is already incorporated, we set the number of replaying samples equal to the replay buffer size, i.e., 24, and the scale coefficient to 0.001. Regarding the GFlowNet method, we configure the number of replaying samples to match the batch size of 64. Furthermore, we set the scale coefficient to 1.0, given that the RL loss in GFlowNet is much higher compared to REINVENT.

10 Additional Experiments↩︎

10.1 Ablation study for the number of symmetric trajectories in SRT↩︎

We conducted the ablation study for varying sample width in replay training. ‘Non-symmetric’ denotes the replay training without symmetric transformation; thus, increased the number of trajectories gives duplicated samples. 9 shows that the symmetric replay training consistently gives better performance and robust to the choice of \(L\).

10.2 Comparison with Experience Replay on TSP50↩︎

We conduct comparative experiments with experience replay and ours using A2C on TSP50. This requires importance sampling weight as follows: \[\mathbb{E}_{\tau \sim \pi(\cdot|s_1)}R(\boldsymbol{x}) = \mathbb{E}_{\tau \sim q(\cdot|s_1)}\left[ \frac{\pi(\tau|s_1)}{q(\tau|s_1)}R(\boldsymbol{x}) \right] = \mathbb{E}_{\tau \sim q(\cdot|s_1)} \left[\prod_{t=1}^{T}\frac{\pi(s_{t+1}|s_t)}{q(s_{t+1}|s_t)}R(x)\right],\] where \(\pi(\cdot|s_1)\) and \(q(\cdot|s_1)\) are the training policy and behavior policy, respectively, and \(x\) is a solution (i.e., the terminal state).

The results show that the existing experience replay method can suffer from high variance because of importance sampling, leading to the degradation of performance. Note that the importance weights are required even without symmetric transformation when using on-policy training, like A2C. On the other hand, ours does not require the importance sampling weight since SRT uses imitation learning loss.

10.3 Comparison with Data Augmentation on TSP50↩︎

Without SRT, symmetric trajectories can be utilized like data augmentation. In this experiment, we train the policy both using sampled trajectories and symmetric (i.e., augmented) trajectories. When on-policy methods like A2C, the importance weights are required for symmetric trajectories similar to the previous section. The policy is updated only using the reward-maximizing loss \(\mathcal{L}_{\text{RM}}(\tau) + \mathcal{L}_{\text{RM}}(\tau'),\) where \(\tau' \sim p(\hat{\tau}_{\rightarrow x}|x)\). Here, \(\hat{\tau}\) is obtained greedy-rollout; see 8. The experiments are conducted with the A2C method on TSP with \(N=50\).

As depicted in 11 and 8, reward-maximizing training tends to seek one of minimizing cost or reducing differences of symmetric trajectories, not both. In the early stage of training, the cost tends to go higher because the sampled and augmented trajectories provide dis-aligned information, as the clearly increased average costs compared to the original A2C method (16.851 \(>>\) 6.780). From a certain point, the cost is decreased with a significant increase in the difference of log-likelihood. This implies that the symmetric nature of CO needs to be utilized carefully so as not to harm the performance of DRL methods, especially when on-policy learning is used.

10.4 Additional results on hardware design optimization↩︎

To verify the benefit of SRT, we also report the overall runtime (for 15K evaluations) of the hardware design optimization tasks as follows.

It is worth emphasizing that SRT is beneficial when the reward evaluation costs are more expensive than the additional costs from SRT. Furthermore, SRT allows GPU batch processing, resulting much smaller wall-clock runtime compared to reward evaluation with simulation. The results show that SRT effectively enhances performance by achieving significantly lower costs while maintaining similar or slightly increased runtime, which is negligible compared to the simulation time. We will include this result in the manuscript.

10.5 Statistical analysis on molecular optimization↩︎

We perform a t-test to compare the average AUC10 scores, setting the null hypothesis as \(\mu_{Base} = \mu_{SRT}\). The resulting p-values are 0.0045 and 0.0015 for REINVENT and GFlowNets, respectively. Thus, the statistical analysis indicates that SRT enhances sample efficiency significantly for both REINVENT and GFlowNets.

10.6 Additional results on molecular optimization↩︎

In this subsection, we provide the additional results of the black-box optimization method in the PMO benchmark. Gaussian process Bayesian optimization [42] and Graph Genetic Algorithm [43] are included. Note that GPBO employs Graph GA when optimizing the GP acquisition function. Though Graph GA demonstrates powerful performance, designing operators, such as crossover and mutation, greatly affects performance [44] Thus, careful algorithm design, which requires specific domain knowledge, is necessitated whenever there is a change in tasks. The results show that SRT outperforms other black-box optimization methods by improving the on-policy RL method, REINVENT.

Additionally, we apply our method on REINVENT with SMILES, the simplified molecular-input line-entry system [45], which is another string-based representation. It is worth mentioning that REINVENT-SMILES gives the best performance in practical molecular optimization benchmark [9]. Noticeably, the results in 11 demonstrate that our achieves improved performances on 16 out of 23 oracles compared to REINVENT-SMILES.

10.7 Experiments on various synthetic CO problems↩︎

The experiments in this section cover various sample-efficient tasks in Euclidean and non-Euclidean combinatorial optimization. Note that we assume the expensive black-box reward function in sample-efficient tasks. In Euclidean CO tasks, the features of variables, such as their two-dimensional coordinates, satisfy Euclidean conditions (e.g., cost coefficients are defined as Euclidean distances). On the other hand, non-Euclidean CO problems lack these constraints, necessitating the encoding of higher-dimensional data, such as a distance matrix.

10.7.1 Euclidean CO problems↩︎

10.7.1.1 Experimental settings.

We selected two representative routing tasks - the traveling salesman problem (TSP) and the capacitated vehicle routing problem (CVRP) with 50 and 100 customers. The CVRP assumes multiple salesmen (i.e., vehicles) with limited carrying capacity; thus, if the capacity is exceeded, the vehicle must return to the depot. For base DRL methods, we employ the best-performing DRL methods, AM for TSP and Sym-NCO for CVRP. We follow the reported hyperparameters for the model in their original paper.⁶

10.7.1.2 Results.

The results in 12 and 12 indicate that SRT consistently outperforms baseline methods in terms of achieving the lowest cost over the training budget. Note that ours employs the AM with critic baseline for TSP and Sym-NCO with the reduced number of augmentations for CVRP. As depicted in 12, the most significant improvement over the base DRL models is observed in TSP100, with a percentage decrease of 3.86%, and CVRP50, with a percentage decrease of 4.04%. While POMO and Sym-NCO consider the symmetric nature of CO, the required number of samples cancels out the benefits. In contrast, our method utilizes the symmetric pseudo-labels generated via the training policy for free, enabling the policy to explore the symmetric space without increasing the number of required samples. As a result, SRT successfully improves sample efficiency.

10.7.2 Non-Euclidean CO problems↩︎

10.7.2.1 Experimental settings.

Based on the work of [5], we have selected two benchmark tasks, namely the asymmetric TSP (ATSP) and flexible flow-shop scheduling problems (FSSP). The ATSP is non-Euclidean TSP where the distance matrix could be non-symmetric, i.e., \(\text{dist}(i,j) \neq \text{dist}(j,i)\), where \(i\) and \(j\) indicate cities. The FSSP is an important scheduling problem that assigns jobs to multiple machines to minimize total completion time. As a baseline, we employ Matrix Encoding Network (MatNet) proposed to solve non-Euclidean CO.⁷ We compare ours with two versions of MatNet: MatNet-Fixed and MatNet-Sampled. MatNet-Fixed, the original version, explores \(N\) heterogeneous starting points of trajectories, while MatNet-Sampled explores less than \(N\) number of multiple trajectories with sampling strategy.

Results. The superior performance of SRT over MatNet-Fixed and MatNet-Sampled is demonstrated in both 13 and 13. We employ MatNet-Sampled as a base DRL method for both tasks and use the same number of multi-starting in ours and MatNet-Sampled. Notably, SRT outperforms MatNet-Sampled by a significant margin in the case of ATSP, with a performance gap of about 12% at \(N=100, K=200\text{K}\), where SRT achieves 3.771 and MatNet-Sampled achieves 4.324.

11 Further related works↩︎

11.1 Deep reinforcement learning for combinatorial optimization↩︎

Deep reinforcement learning (DRL) has emerged as a promising methodology for solving combinatorial optimization. Especially by selecting actions sequentially, i.e., in a constructive way, DRL policies generate a combinatorial solution. This approach is beneficial to producing feasible solutions that satisfy the complex constraints of CO by restricting action space using a masking scheme [1]. The foundational work of [31] introduced the actor-critic method for training PointerNet [46] to solve TSP and the knapsack problem. Subsequently, several works were proposed to extend PointerNet into a Transformer-based model [1], [47] especially for routing problems. Building upon the success of the attention model [1], [2], and [10] suggested enhanced reinforcement learning techniques by employing a precise baseline for REINFORCE based on symmetries in CO problems. On the other hand, various works have been suggested to solve broader ranges of CO problems [4], [5], [35], [48]–[53]

Several studies have proposed to address challenges such as distributional shift and scalability [3], [54]–[60]. It is noteworthy that besides the constructive approach, there is another stream, the improvement heuristic style [61]–[65], though such studies fall outside our research scope. Our research goal is to enhance the sample efficiency of constructive DRL methods for CO; the sample efficiency has been comparatively less explored in contrast to issues such as distributional shift and scalability in DRL for CO literature. This study offers an orthogonal but generally applicable approach to existing works in the field.

11.2 Equivariant Deep Learning↩︎

Equivariant DRL has also been extensively studied in recent years [66]–[70]. This approach reduces search space by cutting out symmetric space using equivariant representation learning, such as employing equivariant neural networks [71]–[73]. Consequently, it leads to better generalization and sample efficiency. Being different from these approaches, we focus on handling symmetries in decision space by exploring the symmetric space without restrictions on network structure. Therefore, employing equivariant DRL methods with our method is available when guaranteeing equivariance is crucial.

11.3 Generative Flow Networks in Combinatorial Optimization↩︎

Genetic Flow Networks or GFlowNets [8] are suggested to sample discrete object \(x\) from the target energy distribution, where \(P(x) \propto e^{-\beta \mathcal{E}(x)}\). GFlowNets consider symmetric trajectories by modeling a sequential construction of combinatorial solutions as a flow on a directed acyclic graph, where each node corresponds to a state (a partial solution). GFlowNets have been employed to solve various CO problems, whether when the reward evaluations are expensive or not. [74] firstly proposed GFlowNets with flow matching loss, a temporal difference-like loss. The work of [74] is used to generate molecular graphs in de nove molecular optimization. Then, [75] introduced a model-based GFlowNet, called GFlowNet-AL, to generate biological sequences. In addition, [52] used GFlowNet to solve CO defined on graphs, like maximum independent set (MIS) problems.

On the other hand, several works have been proposed for better GFlowNet training, by introducing new loss functions [8], [32], [76], improved exploration strategies [77], [78], experience replaying [79], and credit assignment methods [80]–[83].

11.4 Black-box Combinatorial Optimization↩︎

Building on the great success of Bayesian optimization (BO) in black-box optimization [84]–[86], several works were suggested to apply BO to combinatorial decision. Combinatorial Bayesian optimization solves a bi-level optimization where the upper problem is surrogate regression, and the lower problem is acquisition optimization. In the context of combinatorial space, the acquisition optimization is modeled as quadratic integer programming problems, which is NP-hard [87], [88].

To address the NP-hardness of acquisition optimization, various techniques have been proposed, including continuous relaxation [89], sampling with simulated annealing [88], genetic algorithms [42], [90], and random walk explorer [91]. While these methods have demonstrated competitive performance in lower-dimensional tasks like neural architecture search (NAS), they often demand substantial computation time, particularly in molecular optimization tasks [9].

As mentioned in [88] and [9], one of the alternative approaches is to utilize a variational auto-encoder [92] to map the high-dimensional combinatorial space into “compact” continuous latent space to apply BO, like [93]. Though this approach has shown successful performance in molecular optimization, it also introduces variational error since VAE maximizes a lower bound of the likelihood, known as evidence lower bound (ELBO), not directly maximizes the likelihood.

References↩︎