# On the Importance of Reward Design in Reinforcement Learning-based Dynamic Algorithm Configuration: A Case Study on OneMax with (1+(L,L))-GA

Tai Nguyen, Phong Le, André Biedenkapp, Carola Doerr, Nguyen Dang

► To cite this version:

Tai Nguyen, Phong Le, André Biedenkapp, Carola Doerr, Nguyen Dang. On the Importance of Reward Design in Reinforcement Learning-based Dynamic Algorithm Configuration: A Case Study on OneMax with (1+(L,L))-GA. GECCO '25: Genetic and Evolutionary Computation Conference, Jul 2025, Malaga, Spain. pp.1162-1171, 10.1145/3712256.3726395. hal-05171390

HAL Id: hal-05171390

https://hal.science/hal-05171390v1

Submitted on 19 Jul 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# On the Importance of Reward Design in Reinforcement Learning-based Dynamic Algorithm Configuration: A Case Study on OneMax with $(1+(\lambda,\lambda))$-GA

Tai Nguyen

University of St Andrews
St Andrews, United Kingdom
Sorbonne Université, CNRS, LIP6
Paris, France

Phong Le

University of St Andrews
St Andrews, United Kingdom

André Biedenkapp

University of Freiburg
Freiburg, Germany

Carola Doerr

Sorbonne Université, CNRS, LIP6
Paris, France

Nguyen Dang

University of St Andrews
St Andrews, United Kingdom

## Abstract

Dynamic Algorithm Configuration (DAC) has garnered significant attention in recent years, particularly in the prevalence of machine learning and deep learning algorithms. Numerous studies have leveraged the robustness of decision-making in Reinforcement Learning (RL) to address the optimization challenges associated with algorithm configuration. However, making an RL agent work properly is a non-trivial task, especially in reward design, which necessitates a substantial amount of handcrafted knowledge based on domain expertise. In this work, we study the importance of reward design in the context of DAC via a case study on controlling the population size of the $(1 + (\lambda, \lambda))$-GA optimizing OneMax. We observed that a poorly designed reward can hinder the RL agent's ability to learn an optimal policy because of a lack of exploration, leading to both scalability and learning divergence issues. To address those challenges, we propose the application of a reward shaping mechanism to facilitate enhanced exploration of the environment by the RL agent. Our work not only demonstrates the ability of RL in dynamically configuring the $(1 + (\lambda, \lambda))$-GA, but also confirms the advantages of reward shaping in the scalability of RL agents across various sizes of OneMax problems.

## CCS Concepts

* Computing methodologies → Randomized search.

## 1 Introduction

Evolutionary algorithms (EAs) are well-established optimization approaches, used to solve broad range of problems in various application domains every day. A key factor of EAs' wide adoption in practice is the possibility to adjust their search behavior to very different problem characteristics. To benefit from this versatility, the exposed parameters of an EA need to be suitably configured. Since this tuning task requires substantial problem expertise if done by hand, researchers have developed automated algorithm configuration (AC) tools to support the user by automating this process [28]. AC tools such as IRACE [39] and SMAC [38] are today quite well established and broadly used, especially in academic contexts, with undeniable success in various application domains [48].

Dynamic algorithm configuration (DAC) extends automated algorithm configuration by adapting parameters during optimization

runtime rather than using fixed values throughout. While modern evolution strategies like CMA-ES [27] utilize control mechanisms based on current-run data, DAC aims to learn optimal parameter settings across multiple problem instances through transfer learning. Initially explored in [33] and then in [2, 3, 13, 29, 31, 45, 47, 50, 60], the problem of learning control policies through a dedicated training process was formally introduced as DAC in [1, 8].

Given the large success of reinforcement learning (RL) [55] in similar settings where one wishes to control state-specific actions, such as in games [41, 51, 62], robotics [5, 25, 36], or otherwise complex physical systems [16, 30], it seems natural to address the DAC problem with RL approaches. In fact, the study [50] previously employed a double DQN method to determine the selection of mutation strategies in differential evolution. Recently, a multi-agent RL approach was used to control multiple parameters of a multi-objective evolutionary algorithm [63].

Despite all successes, a number of recent studies also highlight the difficulty of solving DAC problems. Using theory-inspired benchmarks with a known ground truth, the analysis in [9] revealed that a naïve application of RL to DAC settings can be fairly limited, with unfavorable performance in settings of merely moderate complexity. An alternative approach to address DAC problems via sequential algorithm configuration using IRACE [39] was suggested in [14]. However, this approach requires substantial computational overhead, and its usefulness for more complex settings remains to be demonstrated. The so-called GPS strategy [35], used in [49] to control the step-size of CMA-ES, requires itself a complex configuration process, causing significant overhead.

**Our Contributions.** We revisit the DAC problem of configuring the $\lambda$ parameter of the $(1+(\lambda,\lambda))$-GA for optimizing ONEMAX instances, as introduced in [14], but address with an RL approach. Specifically, we investigate DDQN [58], a widely used deep RL algorithm in both general RL research and DAC applications. Our initial experiments in Section 3 reveal that a naïve implementation faces several challenges, including scalability issues across different problem sizes and significant divergence during learning.

We show that these issues arise from a naïve reward function design (Section 4). To address this, we propose a scaling mechanism to mitigate the impact of problem dimensionality on the reward
function. Although effective for small- to medium-sized problems, this approach is insufficient for larger-scale problems.

We identify *under-exploration* as the root cause of both scalability and divergence issues (Section 5) and show that the widely used ε-greedy exploration [56] in RL is insufficient to solve this issue.

In Section 6, we resolve under-exploration and mitigate both scalability and divergence issues by adopting a simple method known as *reward shifting* [54], which adds a bias term to the original reward. Additionally, we propose an adaptive mechanism to automatically adjust the bias for reward shifting to avoid time-consuming manual tuning of this parameter. Using this, our trained RL policies consistently outperform a well-known theory-derived policy for the same benchmark [19] across all problem sizes studied. Finally, in Section 7, we demonstrate that RL policies trained with our adaptive reward shifting can achieve a speed increase of several orders of magnitude to reach the performance of the theory-derived policy compared to the DAC method based on IRACE proposed in [14].

All source code and data are publicly available at [24].

## 2 Background

DAC problems are modelled as Markov Decision processes (MDPs) [6]. An MDP $\mathcal{M}$ is a tuple $(\mathcal{S}, \mathcal{A}, \mathcal{T}, \mathcal{R})$ with state space $\mathcal{S}$, action space $\mathcal{A}$, transition function $\mathcal{T}: \mathcal{S} \times \mathcal{A} \times \mathcal{S} \to [0, 1]$, and reward function $\mathcal{R}: \mathcal{S} \times \mathcal{A} \to \mathbb{R}$. The transition function gives the probability of reaching a successor state $s'$ when playing action $a$ in the current state $s$, thus describing the dynamics of the system. The reward function further indicates if such a transition between states is desirable or if it should be avoided and is crucial for learning processes that aim to learn policies that are able to solve the MDP. In order to describe instance-dependent dynamics and enable learning across multiple instances $i \sim \mathcal{I}$, DAC problems are described as contextual MDPs (cMDPs) [26]. Contextual MDPs extend the MDP formalism through the use of *contextual information* that describes how rewards and transitions differ for different instances while sharing action and state spaces. Consequently, a cMDP $\mathcal{M} = \{M_i\}_{i \in \mathcal{I}}$ is a collection of MDPs with shared state and action spaces, but with individual transition and reward functions.

In DAC, a state space represents the algorithm's behavior through its internal statistics during execution, providing necessary context. The action space encompasses all potential parameter configurations. While transition and reward functions are typically unknown and complex to approximate, RL has proven effective for DAC [1]. During offline learning, an RL agent interacts with the algorithm being tuned across multiple episodes, each terminating at a goal state or step limit. The agent observes the current state $s_t$, selects action $a_t$, transitions to state $s_{t+1}$, and receives reward $r_{t+1}$. These interactions enable the agent to evaluate states and determine an optimal policy $\pi: \mathcal{S} \to \mathcal{A}$ maximizing expected rewards. Though some RL variants learn transition functions for direct policy search, modern approaches are typically model-free, focusing on learning state-action values $Q: \mathcal{S} \times \mathcal{A} \to \mathbb{R}$.

Q-learning [61], one of the most widely adopted approaches, aims to learn a Q-function that associates each state-action pair with its expected cumulative future reward when taking action $a$ in state $s$. This function is learned through error correction principles. For a given state $s_t$ and action $a_t$, the corresponding Q-value

**Algorithm 1:** The $(1+(\lambda, \lambda))$-GA with state space $\mathcal{S}$, discrete portfolio $\mathcal{K} := \{2^i | 2^i \le n \land i \in [0..k-1]\}$, and parameter control policy $\pi: \mathcal{S} \to \mathcal{K}$, maximizing a function $f: \{0, 1\}^n \to \mathbb{R}$. $[\lambda] := [\lambda]$ if $\lambda - [\lambda] < 0.5$, else $[\lambda]$.

1. $x \leftarrow$ a sample from $\{0, 1\}^n$ chosen uniformly at random;
2. **for** $t \in \mathbb{N}$ **do**
3. &nbsp;&nbsp;&nbsp;&nbsp; $s \leftarrow$ current state of the algorithm;
4. &nbsp;&nbsp;&nbsp;&nbsp; $\lambda = \pi(s)$;
5. &nbsp;&nbsp;&nbsp;&nbsp; $p = [\lambda]/n$; and $c = 1/[\lambda]$;
6. **Mutation phase:**
7. &nbsp;&nbsp;&nbsp;&nbsp; Sample $\ell$ from $\text{Bin}_{>0}(n, p)$;
8. &nbsp;&nbsp;&nbsp;&nbsp; **for** $i = 1, \dots, [\lambda]$ **do** $x^{(i)} \leftarrow \text{flip}_\ell(x)$; Evaluate $f(x^{(i)})$;
9. &nbsp;&nbsp;&nbsp;&nbsp; Choose $x' \in \{x^{(1)}, \dots, x^{([\lambda])}\}$ with $f(x') = \max\{f(x^{(1)}), \dots, f(x^{([\lambda])})\}$ u.a.r.;
10. **Crossover phase:**
11. &nbsp;&nbsp;&nbsp;&nbsp; **for** $i = 1, \dots, [\lambda]$ **do**
12. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $y^{(i)} \leftarrow \text{cross}_c(x, x')$;
13. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **if** $y^{(i)} \notin \{x, x'\}$ **then** evaluate $f(y^{(i)})$;
14. &nbsp;&nbsp;&nbsp;&nbsp; Choose $y' \in \{y^{(1)}, \dots, y^{([\lambda])}\}$ with $f(y') = \max\{f(y^{(1)}), \dots, f(y^{([\lambda])})\}$ u.a.r.;
15. **Selection and update step:**
16. &nbsp;&nbsp;&nbsp;&nbsp; **if** $f(y') > f(x')$ **then** $y \leftarrow y'$ **else** $y \leftarrow x'$;
17. &nbsp;&nbsp;&nbsp;&nbsp; **if** $f(y) \ge f(x)$ **then** $x \leftarrow y$;

$Q(s_t, a_t)$ is updated using temporal differences (TD). A temporal difference describes the prediction error of a Q-function with respect to an observed true reward $r_t$ as $TD(s_t, a_t) = r_t + \gamma \max_{a \in \mathcal{A}} Q(s_{t+1}, \cdot) - Q(s_t, a_t)$, where $\gamma$ is the *discounting factor* that determines how strongly to weigh future rewards in the prediction. For example, with $\gamma = 0$, the temporal difference would describe the error in predicting immediate rewards without the influence of potential future rewards. The estimate of the Q value can then simply be updated using temporal differences as $Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha TD(s_t, a_t)$ with $\alpha$ giving the *learning rate*. A policy can then be defined by only using the learned Q-function as $\pi(s) = \arg \max_{a \in \mathcal{A}} Q(s, \cdot)$. To ensure that the state space is sufficiently explored during learning, it is common to employ $\epsilon$-greedy exploration, where with probability $\epsilon$ an action $a_t$ is replaced with a random choice.

Mnih [41] introduced deep Q-networks (DQN) which models the Q-function using a neural network and demonstrated its effectiveness in learning Q-functions for complex, high-dimensional state spaces, such as video game frames. However, Van Hasselt et al. [58] identified that using a single network for action selection and value prediction when computing the temporal difference often creates training instabilities due to value overestimation. They proposed to address this issue by using two copies of the network weights: one for selecting the maximizing action and another for value prediction. The second set of weights remains static for brief periods before being updated with the values of the first set. This double deep Q-network (DDQN) typically reduces overestimation bias and thereby stabilizes learning. This advantage has also helped establish DDQN as one of the most widely used solution approaches in DAC.

DACBench [21] provides a standardized collection of DAC problems, including both artificial benchmarks abstracting algorithm
runs and real-world benchmarks from various AI domains. The complexity of DAC problems makes establishing ground truth difficult beyond artificial cases, limiting DACBench's capability to evaluate learned policies on real algorithms. This limitation was highlighted when Benjamins et al. [7] found that cross-instance policies unexpectedly outperformed instance-specific policies designed as performance upper bounds, potentially due to local optima. This underscores the need for ground-truth benchmarks to better understand DAC solutions. While new artificial benchmarks continue emerging [such as, 10], theory-inspired DAC benchmarks [9, 14] offer a promising middle ground, using theoretical insights from parameter control to provide optimality ground truth while maintaining real algorithm runs. The LEADINGONES benchmark [9] demonstrated this utility by revealing DDQN-based approaches' effectiveness in learning optimal policies for small action spaces while showing limitations with increased dimensionality.

In [14], the ONEMAX-DAC benchmark was introduced. Here, the goal is to control the parameter $\lambda$ of the $(1+(\lambda,\lambda))$-GA (Algorithm 1) optimizing instances of the ONEMAX problem $\{f_z : \{0,1\}^n \to \mathbb{R}, x \mapsto \sum_{i=1}^n x_i = z_i\}$, also known as 2-color Mastermind. The parameter $\lambda$ determines the population size of the mutation and crossover phase, the mutation rate $p$, and the crossover bias $c$. Optimally controlling $\lambda$ as a function of the current-best fitness is a well-studied problem in the theory community, for which a policy for configuring $\lambda \in \mathbb{R}$ resulting in asymptotically optimal linear expected optimization time was derived as $\pi_{\text{cont}}(x) := \sqrt{n/(n-f(x))}$ [19, 20]. The study of ONEMAX-DAC in [14] highlighted the difficulty of this benchmark. Although a tailor-made approach based on IRACE was able to find policies that performed on par with theoretical policies, its blackbox and “cascading” nature makes it highly sample inefficient.

## 3 DDQN for Solving ONEMAX-DAC

Compared to black-box DAC approaches, such as those based on IRACE, deep-RL algorithms, especially off-policy algorithms like DDQN, are expected to be much more sample-efficient, since the learned policies can be updated *during* every episode. This property makes DDQN and similar approaches appealing for DAC scenarios where each solution evaluation is expensive. However, deep-RL is commonly known to be difficult to use [see, e.g., 44]. In this section, we investigate the learning ability of DDQN on the ONEMAX-DAC benchmark. We will show that a naïve application of this commonly used deep-RL algorithm with a straightforward reward function results in limited learning ability. This motivates our study on reward function design in the next sections.

**Action Space.** As DDQN is designed to work with a discrete action space, we discretize the ONEMAX-DAC benchmark action space. For a given problem size $n$, we define the set of possible $\lambda$ values that the RL agent can choose from as $\{2^l | 2^l \le n, i \in [0.. \lfloor \log_2 n \rfloor]\}$. With this new action space, we define the following discretized version $\pi_{\text{disc}}(x)$ of the theory-derived policy: for a given solution $x$, we choose the $\lambda$ value from the set that is the closest to $\pi_{\text{cont}}(x)$.

Figure 1 shows that the difference in performance between $\pi_{\text{cont}}$ and $\pi_{\text{disc}}$ is marginal (and not statistically significant according to a paired t-test with a confidence level of 99%). Therefore, an

<figure><img src="image_2.png" /><figcaption>Figure 1: theory-derived policy, its discretized version, and the optimal policy for $f(x) \ge n/2$ with $n = 50$ (left); their average runtimes across 4 problem sizes over 1,000 runs (right).</figcaption></figure>

RL agent using this discretized action space should be able to find a policy that is at least competitive with the theory-derived one. Additionally, there is a gap between the optimal policy ($\pi_{\text{opt}}$) [14] and $\pi_{\text{cont}}$ across all problem sizes. Therefore, we aim to propose an RL-based approach to produce a policy closer to $\pi_{\text{opt}}$.

**State Space.** Following both theoretical and empirical work on the benchmark [14, 18], we only consider the state space defined by the quality (“fitness”) of the current-best solution; in the absence of ground-truth, more complex state spaces are left for future work.

**Reward Function.** The aim of the ONEMAX-DAC benchmark is to find a policy that minimises the runtime of the $(1+(\lambda,\lambda))$-GA algorithm, i.e., the number of solution evaluations until the algorithm reaches the optimal solution. Therefore, an obvious component of the reward function is the number of solution evaluations at each time step (i.e., iteration) of the algorithm.

Additionally, to reduce time collecting samples from bad policies during the learning, following [9], we impose a cutoff time on each run of the $(1+(\lambda,\lambda))$-GA algorithm, allowing an episode to be terminated even before an optimal ONEMAX solution is reached. To distinguish the performance between runs terminated due to the cutoff time, denoting by $E_t$ the total number of solution evaluations at time step $t$, and by $\Delta f_t = f(x_t) - f(x_{t-1})$ the fitness improvement between $t$ and $t-1$, we define the reward function as:

$$r_t = \Delta f_t - E_t \qquad (1)$$

**Baseline Policies.** We consider three baseline policies in our study, including the theory-derived policy $\pi_{\text{cont}}(x)$, its discretized version $\pi_{\text{disc}}(x)$, and the (near) optimal policy $\pi_{\text{opt}}(x)$ from [14].

**Experimental Setup.** We train DDQN on four ONEMAX problem sizes $\{50, 100, 200, 300\}$. For each size, we repeat each RL training 10 times using a budget of 500,000 training steps. The training used a machine equipped with two dual-socket Intel® Xeon® E5-2695 v4 CPUs (2.10 GHz), each with a maximum of 72 threads. We use a single thread for training and parallelize 20 threads for evaluation. A cutoff time of $0.8n^2$, sufficiently larger than the optimal linear running time, is imposed on each episode during the training.

Following [9], we adopt a default hyperparameter configuration of DDQN with $\epsilon$-greedy exploration and $\epsilon = 0.2$. The replay buffer size is set to 1 million transitions. At the beginning of the training process, we sample 10,000 transitions uniformly at random and add them to the replay buffer before learning begins. The Adam optimiser [32] is used for the training process with a (mini-)batch size of 2,048 and a learning rate of 0.001. To update the Q-network, we adopt a discount factor of 0.99 and use the soft target update
<figure><img src="image_3.png" /><figcaption>Figure 2: Top row: example DDQN learning curves on $n = 100$ using original (left) and scaled (right) reward functions, with $\pi_{\text{disc}}$ as the baseline policy. Green dots indicate hitting points (details in Section 3). Bottom row: average performance across 10 learning curves on $n = 50$ (left) and $n = 100$ (right).</figcaption></figure>

mechanism with $\tau = 0.01$ to synchronise the online policy and the target policy [37].

**Performance Metrics.** To study the learning performance of each RL training, we record the learned policies at every 2,000 training steps and evaluate each of them with 100 different random seeds. We then measure the performance of each RL training via three complementary metrics: (1) Best policy's performance (ERT and gap): evaluate top 5 policies across 1000 random seeds, select the best performer, and compute its expected runtime (ERT) and gap relative to baseline policy's ERT; (2) Area Under the Curve (AUC): difference between the learning curve and the baseline performance of $\pi_{\text{disc}}(x)$ in Figure 2 (top row), where the curve points represent the average runtime of the current policy across 100 seeds; (3) Hitting rate (HR): ratio $n_h/n_e$ of policies with runtime within $\mu \pm 0.25\sigma$ of the baseline policy (where $\mu$, $\sigma$ are the ERT and standard deviation) [9], with hitting points $n_h$ shown as green dots in Figure 2 and $n_e$ the total number of evaluations. We aim to minimise ERT (gap) and AUC, while maximising HR.

**Naïve Rewards Fail to Scale.** Figure 3 (left plot) depicts the gap of the best-learned policy to $\pi_{\text{disc}}$ across 10 RL runs using the reward function defined in Equation (1). The blue box plots highlight the limitation in the DDQN learning scalability: Although the agent can find policies of reasonable quality in the smallest problem size of $n = 50$, the gap increases significantly with $n$. From $n = 200$ onward, the agent is no longer able to get close to the baseline during the whole learning process.

**Naïve Rewards Induce Learning Divergence.** Figure 2 (top left) shows an example of a DDQN learning curve on $n = 100$ where the agent is able to find a good policy at the beginning but then starts to diverge and stagnate until the end of the learning process. This behaviour is further demonstrated in the bottom row of Figure 2, where we show the agent's average ERT (blue lines). The agent consistently diverges in the later part of the training

<figure><img src="image_4.png" /><figcaption>Figure 3: DDQN performance (as gap to $\pi_{\text{disc}}$ and AUC) using original and scaled reward functions.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Figure 4: DDQN performance (as HR across different training periods) using original and scaled reward functions.</figcaption></figure>

process across all RL runs on both problem sizes. This issue makes the RL agent incapable of exploiting knowledge of well-performing policies, likely leaving a user with a far-from-optimal policy at the end of the training process, especially when we have a limited budget and cannot afford thorough evaluations to select the best-performing policy.

## 4 Reward Scaling

In the previous section, we have shown two learning limitations of DDQN on the ONEMAX-DAC benchmark. In this section, we study the impact of reward scaling on DDQN learning performance. Our study is inspired by the fact that the original reward function $r_t = \Delta f_t - E_t$ is significantly influenced by the selected action. More concretely, from Algorithm 1, we can infer that $E_t \approx 2\lambda$. To maximise the returns, the agent would be biased towards choosing actions that minimise $E_t$, resulting in a bias towards choosing smaller $\lambda$ values. In fact, we see that during the divergence period, the agent gets stuck consistently in policies that dominantly select $\lambda = 1$ (the smallest $\lambda$ in our action space) across the entire state space. Moreover, the wide variance between the values of $\lambda$ in the portfolio poses a significant challenge for the agent to learn its behavior from its environment. There is a need to limit the reward range, where the normalization mechanism is proved as a simple yet effective solution. The normalization process enhances the Q-network's ability to discover the appropriate parameters $\theta$ much more efficiently [53, 59]. More specifically, to mitigate the variance scaling of $\lambda$ in the portfolio as the problem size increases, we scale the original reward function by the problem size: $r_t = (\Delta f_t - E_t)/n$. The scaled reward value thus ranges from $\frac{-2\max(\lambda)}{n}$ to $\frac{(n-1)}{n}$.

As shown in Table 1, the original reward function performs well in the small problem size of 50. However, it becomes ineffective for the larger problem sizes. A similar observation is also made in the reward scaling, which are very promising for two smaller problem
<table><caption>**Table 1:** Comparison of ERT (and its standard deviation) among theory-derived policies, RL-based DAC with two designed reward functions (top), and the optimal policy (bottom) across four problem dimensions. Bold values indicate the best ERT among theory-derived and RL-based policies.</caption><thead><tr><th></th><th colspan="4">ERT(↓)</th></tr><tr><th></th><th>n = 50</th><th>n = 100</th><th>n = 200</th><th>n = 300</th></tr></thead><tbody><tr><td>π<sub>cont</sub></td><td>272.39(76.40)</td><td><strong>582.62</strong>(118.45)</td><td><strong>1233.38</strong>(193.01)</td><td><strong>1883.42</strong>(252.22)</td></tr><tr><td>π<sub>disc</sub></td><td>274.02(74.49)</td><td>593.44(128.13)</td><td>1248.88(195.01)</td><td>1889.45(251.95)</td></tr><tr><td>r = Δf - E</td><td>271.38(91.16)</td><td>643.67(184.91)</td><td>1409.01(305.43)</td><td>2500.03(591.56)</td></tr><tr><td>r = (Δf - E)/n</td><td><strong>255.24</strong>(78.06)</td><td>583.64(139.03)</td><td>1364.49(276.65)</td><td>2077.52(338.43)</td></tr><tr><td>π<sub>opt</sub></td><td>246.39(71.13)</td><td>531.27(110.09)</td><td>1121.71(177.79)</td><td>1725.01(224.35)</td></tr></tbody></table>

sizes, $n \in \{50, 100\}$, but gradually becomes poor for larger problem sizes. Figure 3 shows that the scaling mechanism can help slightly in the cases of $n \in \{200, 300\}$ by examining the gap percentage relative to the discrete theory. In particular, the reward scaling function performs exceptionally well compared to the conventional reward function. Looking at the problem size of $n = 100$, which is highly competitive with the performance of both theory-derived policies. However, Figure 2 reveals its ERT diverge significantly and the best expected runtimes reported in the Table 1 for the reward scaling come from the early phases of learning.

We used a heat map to provide an overview of HR across 10 RL runs. We analyze three distinct phases of the training process: the entire duration (0%-100%), the latter half (50%-100%), and the last quarter (75%-100%). By segmenting these periods, the heatmap helps identify potential divergence points. In an ideal scenario, where the RL agent progressively learns from the environment, we expect a consistent growth in the HR across all three phases. As shown in Figure 4, the smallest problem size achieves HR of 1 for all three periods, as the difference between good and poor policies in this setting is minimal. We thus need to analyze larger problems to gain a clearer understanding of the landscape.

Generally, reward scaling effectively addresses scalability, particularly in the setting of problem size $n = 100$, where the agent discovers several good policies at the outset, achieving HR@($0\%-100\%$) = 0.29 compared to 0.05 with the original reward function. However, these HRs begin to decline over time, indicating the occurrence of divergence in both the original and scaled reward functions. More concretely, the heatmap for $n = 100$ under the scaled reward function reveals that HRs decrease over the three analyzed periods: HR@($0\% - 100\%$) = 0.29, HR@($50\% - 100\%$) = 0.18, and HR@($75\% - 100\%$) = 0.09. A similar observation is evident in the heatmap for the conventional reward signal. For problems of size $n = 200$ and $n = 300$, the divergence issue becomes more severe, as no green dots (HR = 0) are observed in all periods.

## 5 An Under-exploration Issue

Learning with the original reward and the scaled reward functions is challenged by the divergence problem. As shown in Figure 2, the RL agent tends to require more runtimes when more training is given, in contrast to our expectation. We conjecture that the agent lacks the ability to discover more rewarding actions. We call this issue divergence-stagnation: the learned RL agent fails to find

<figure><img src="image_6.png" /><figcaption>**Figure 5:** Example of the pairwise difference for two reward functions with problem size 100.</figcaption></figure>

effective actions during the exploration phase, leading to the agent being trapped in a suboptimal policy or a collection of poor policies.

To understand how the learned RL agent gets trapped in poor policies, we examine how the policy changes during RL training for both original and scaled reward functions for $n = 100$. We use a pairwise difference between two consecutive evaluated policies: $D(\pi_t, \pi_{t-1}) = \sum_{s \in S} 1[\pi_t(s) \neq \pi_{t-1}(s)]$, where $S$ is the full set of environment states, while $t$ and $\pi$ are the current evaluation iteration and the corresponding policy, respectively. A higher pairwise difference value indicates high variety in RL training. We generally expect a large number of changes in the beginning, indicating that the agent is exploring. Later, the policy change is expected to decrease over time for learning convergence and stability.

Learning with the original reward function (shown in Figure 5) however lacks changes in the beginning: its pairwise difference is always stably close to zero. This explains why, in Figure 2, the agent struggles to decrease runtime and finally stagnates. Learning with the scaled reward function, on the other hand, follows our expected pattern, which is why it performs better in Figure 2. Nevertheless, the fact that it still can not overcome the divergence-stagnation challenge suggests that the agent does not explore the environment enough. We thus look for an effective solution to encourage exploration during learning.

**Random Exploration.** In the literature, a popular choice to encourage exploration in learning is $\epsilon$-greedy [56]. We tried various values of $\epsilon \in \{0.2, 0.3, 0.4, 0.5\}$ for the problem $n = 100$, using the DDQN setting described in Section 3. The top row in Figure 6 shows that the evaluated ERT still diverges until the end of the training budget, despite some slight improvements over the default setting ($\epsilon = 0.2$). For instance, learning with the original reward function achieves the best HR when $\epsilon = 0.3$, still the HR never exceeds 0.1 (middle row in Figure 6). We believe that the simple $\epsilon$-greedy strategy, which only explores the action space uniformly randomly, does not effectively improve exploration, as we can see in the bottom row in Figure 6 that the pairwise difference curves of different $\epsilon$ values are barely indistinguishable. This motivates our next study on employing a more sophisticated mechanism for improving exploration in deep-RL, namely reward shifting [54].

## 6 Reward Shifting

Several studies [4, 15, 43, 52] have revealed that relying solely on the $\epsilon$-greedy strategy is inadequate to address the issue of under-exploration. These studies suggest more systematic approaches that
<figure><img src="image_7.png" /><figcaption>Figure 6: $\epsilon$-greedy with various $\epsilon$ values on $n = 100$, applied on DDQN with original (left) and scaled (right) reward functions.</figcaption></figure>

encourage agents to prioritize visiting specific states, thereby improving exploration. Reward shaping [34, 42, 46] is a robust strategy in addressing the exploration challenge in training [17, 23, 40, 54]. The idea is to incorporate an external reward factor, $R' = R + F$ where $F$ is a shaping function, into the original reward $R$. The external factor not only assists in stabilizing the training process but also accelerates the convergence of the RL algorithm. The stabilization arises from a sufficient trade-off between exploitation and exploration. Reward shaping can accelerate training because the agent needs to minimize the number of steps within an episode [12]. If the agent takes unnecessary steps, the cumulative reward becomes more negative, reducing the overall reward.

The effectiveness of reward shaping in addressing the hard exploration challenge lies in the fact that the Q-network is trained under the assumption of *optimistic initialization* [11, 22, 57]. The values of the Q-network are initialized with optimistically high values: $\hat{Q}_0(s, a; \theta) \ge \max_{a'} Q^*(s, a') \forall (s, a)$, where $\hat{Q}_0(\cdot)$ represents the Q-values of the approximate network at the initial step and $Q^*(\cdot)$ is the true optimal Q-values. During the training, the trained Q-network gradually relaxes to estimates of the expected returns based on the observations.

Inspired by the theory of reward shaping, in [54] *reward shifting* was introduced ($R' = R + b$ with $b \in \mathbb{R}$) to encourage the agent to explore its environment and escape suboptimal points in the optimization landscape. In the context of reward shifting, it is not necessary to directly initialize the network's parameters to obtain higher Q-values. Instead, the Q-values of the optimal policy $\pi^*$ are

<table><caption>Table 2: ERT of optimal, theory-derived and RL-based DAC policies with fixed and adaptive shifting $b_a^-$. Standard deviations are in parentheses. Blue: RL outperforms theory-based policies. Bold: best non-optimal ERT.</caption><thead><tr><th></th><th colspan="4">ERT(↓)</th></tr><tr><th></th><th>n = 50</th><th>n = 100</th><th>n = 200</th><th>n = 300</th></tr></thead><tbody><tr><td>π<sub>cont</sub></td><td>272.39(76.40)</td><td>582.62(118.45)</td><td>1233.38(193.01)</td><td>1883.42(252.22)</td></tr><tr><td>π<sub>disc</sub></td><td>274.02(74.49)</td><td>593.44(128.13)</td><td>1248.88(195.01)</td><td>1889.45(251.95)</td></tr><tr><td>r = Δf - E + 1</td><td>282.88(100.56)</td><td>680.96(213.77)</td><td>1578.61(408.37)</td><td>2580.92(647.50)</td></tr><tr><td>r = Δf - E + 3</td><td>282.88(100.56)</td><td>680.96(213.77)</td><td>1578.61(408.37)</td><td>2583.82(648.63)</td></tr><tr><td>r = Δf - E + 5</td><td>282.43(99.66)</td><td>678.59(211.29)</td><td>1578.25(409.83)</td><td>2563.81(642.85)</td></tr><tr><td>r = Δf - E - 1</td><td>249.68(71.57)</td><td>568.14(132.78)</td><td>1315.25(253.09)</td><td>2112.46(368.38)</td></tr><tr><td>r = Δf - E - 3</td><td>252.46(70.54)</td><td>542.11(115.22)</td><td>1195.08(202.65)</td><td>1944.17(302.85)</td></tr><tr><td>r = Δf - E - 5</td><td>250.12(70.92)</td><td>551.99(116.40)</td><td><strong>1134.14</strong>(183.21)</td><td>1835.33(265.37)</td></tr><tr><td>r = Δf - E + b<sub>a</sub><sup>-</sup></td><td><strong>249.53</strong>(70.08)</td><td>542.12(120.62)</td><td>1178.75(209.03)</td><td><strong>1829.65</strong>(263.12)</td></tr><tr><td>r = (Δf - E)/n + b<sub>a</sub><sup>-</sup></td><td>249.60(71.23)</td><td><strong>538.25</strong>(122.48)</td><td>1188.64(209.49)</td><td>1865.88(293.33)</td></tr><tr><td>π<sub>opt</sub></td><td>246.39(71.13)</td><td>531.27(110.09)</td><td>1121.71(177.79)</td><td>1725.01(224.35)</td></tr></tbody></table>

shifted downward by a constant relative to the original situation. A proof of the relationship between external bias and the shifting distance is provided in the supplementary material. This shift assumes that all values associated with the approximate policy $\tilde{\pi}$ are initially higher than those of the true optimal policy $\pi^*$. In the network update, the Q-value of the chosen action at step $t$ is pulled closer to the shifted true optimal policy. Meanwhile, the Q-values of the unchosen actions are maintained at relatively high levels. In this manner, the selected action at step $t + 1$ will less frequently adhere to the knowledge of the optimal policy, resulting in a more extensive exploration of the environment. In contrast, initializing with lower Q-values of $\tilde{\pi}$ or setting the optimal policy $\pi^*$ higher can steer the agent toward exploitation rather than exploration; this concept is commonly referred to as *pessimistic initialization*. By demonstrating some empirical results, Sun et al. [54] conclude that an upward shift is associated with a positive value of $b^+$, which leads to conservative exploitation, while a downward shift corresponds to a negative value of $b^-$, inducing curiosity-driven exploration.

## 6.1 Reward Shifting with a Fixed Bias

Following [54], we implement the shifting mechanism by adding a constant bias into the original reward function in Equation (1): $r_t = \Delta f_t - E_t + b$. To determine the optimal shifting bias $b$, we replicate the experiments conducted in previous sections, employing both negative and positive biases. The considered shifts are $\{\pm 1, \pm 3, \pm 5\}$.

**Analysis.** In addition to using the ERT and HR to validate the effectiveness of incorporating the shifting bias into the original reward function of DDQN as in previous experiments, we also capture policy changes and the uncertainty in estimating action values to investigate the impact of the shifting mechanism on the diversification of policies. The uncertainty level is measured using the concept of entropy $H(\pi) = -\sum_a \pi(a|s) \log \pi(a|s)$, where $\pi(a|s)$ represents the distribution of Q-values across actions derived as $\pi(a|s) = \frac{\exp(Q(s,a))}{\sum_{a'} \exp(Q(s,a'))}$. A lower entropy indicates strong confidence in action-value estimation, while higher entropy suggests greater uncertainty, potentially encouraging more exploration.

Table 2 shows the average ERT across 10 RL runs for each approach, together with the baselines, where adding the positive fixed shifts $b$, which range from +1 to +5 results in generally higher ERT
<figure><img src="image_8.png" /><figcaption>Figure 7: DDQN performance (HR across training periods) using the original reward function with fixed positive (left) and negative (right) shifts. For negative shifting, HRs of the best-performing biases for each problem size are presented.</figcaption></figure>

(i.e., worse performance). All settings associated with the negative biases outperform the positive options. More explicitly, they are better than the discretized theory policy $\pi_{\text{disc}}$ and even outperform the original theory policy $\pi_{\text{cont}}$ in several cases. This observation consolidates our conjecture about the under-exploration problem in using the original reward function, and that the RL agent should focus more on exploration than exploitation.

Figure 7 provides more details about the ability of each approach in terms of converging to a good policy, where positive values of the shift completely fail the task with a problem size larger than 50. In contrast, the robustness of the negative shiftings is demonstrated in the three problem sizes ranging from 50 to 200, where almost over 90% of the evaluated points adhere to the theory policy. Although this strength is not maintained when the problem size increases to 300, where the HR decreases by half, the negative reward shifting mechanism remains a promising solution to the stagnation problem as the HR does increase during the later part of the training process.

To assess the effectiveness of reward shifting in helping exploration, we analyze the policy changes when employing fixed shifting bias compared to the original reward function. Figure 8 clearly demonstrates the significant increase in policy changes when compared to those without shifting bias. The learned agent selects a variety of actions and gradually converges towards the desired outcome throughout the training process. Meanwhile, the agent walks in the correct direction toward the theory baseline as shown in the ERT plot. Furthermore, the entropy in action selection during the training process is significantly higher than the one obtained from the original reward function. This observation suggests that the agent makes decisions with high uncertainty because it is aware of multiple paths that can lead to the goal.

## 6.2 Adaptive Shifting

Choosing the right value for $b$ is a nontrivial task. As illustrated in Table 2, the best bias varies across problem sizes. Sun et al. [54] suggests using a *meta-learner* to control the value of $b$, but this would significantly increase the cost of learning. Instead, we propose a simple yet effective mechanism, namely *adaptive reward shifting*, which approximates the bias by leveraging the reward values obtained during the learning's warming-up phase, i.e., when DDQN collects random samples to initialize the replay buffer before the learning starts. Figure 8 (bottom-right) shows the reward distribution in the replay buffer during this warmup phase across different problem sizes, where the number above each boxplot

<figure><img src="image_9.png" /><figcaption>Figure 8: Effectiveness of reward shifting for problem size 100 with $b = -3$. Top row: ERT and pairwise difference. Bottom row: entropy comparison and reward distribution for the first 10,000 steps in a single DDQN run.</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>Figure 9: DDQN performance of adaptive shifting with the original and scaled reward functions across 7 problem sizes.</figcaption></figure>

represents the median value. We define the adaptive bias $b_a^-$ as $b_a^- = -0.2|m(r)|$, where $m(r)$ is the median of the reward values observed during the warmup phase. The factor 0.2 is decided based on comparing the medians in Figure 8 (bottom-right) and the best shifting values indicated in Table 2. In practice, we may need to tune this factor when applying it to a new benchmark. However, this factor can be tuned across problem sizes or instances, in contrast to a fixed shift that likely needs to be tuned per problem size.

As shown in Table 2, the proposed adaptive bias shifting, represented as $r_t = \Delta f_t - E_t + b_a^-$, achieves highly competitive ERT performance across all problem sizes. In the two cases of $n = 50$ and $n = 300$, the average ERT is even slightly better than the best ones obtained from fixed shifting values.
<table><caption>**Table 3: Comparison of DDQN and the IRACE cascading method [14] in terms of: 1) ERT and 2) the minimum number of time steps required for the found policy to surpass $\pi_{disc}$**</caption><thead><tr><th rowspan="2"></th><th colspan="2">n = 500</th><th colspan="2">n = 1000</th><th colspan="2">n = 2000</th></tr><tr><th>ERT</th><th>#Steps (×10<sup>6</sup>)</th><th>ERT</th><th>#Steps (×10<sup>6</sup>)</th><th>ERT</th><th>#Steps (×10<sup>6</sup>)</th></tr></thead><tbody><tr><td>$\pi_{cont}$</td><td>3237.16</td><td>-</td><td>6587.45</td><td>-</td><td>13361.92</td><td>-</td></tr><tr><td>$\pi_{disc}$</td><td>3271.48</td><td>-</td><td>6701.00</td><td>-</td><td>13642.12</td><td>-</td></tr><tr><td>$r = \Delta f - E + b_a^-$</td><td><strong>3040.20</strong></td><td><strong>0.012</strong></td><td>6458.62</td><td><strong>0.012</strong></td><td>13599.94</td><td><strong>0.012</strong></td></tr><tr><td>$r = (\Delta f - E)/n + b_a^-$</td><td>3592.75</td><td>$\infty$</td><td>7046.52</td><td>$\infty$</td><td>15855.36</td><td>$\infty$</td></tr><tr><td>IRACE</td><td>3130.37</td><td>2002</td><td><strong>6421.68</strong></td><td>20046</td><td><strong>12751.15</strong></td><td>159439</td></tr><tr><td>$\pi_{opt}$</td><td>2938.08</td><td>-</td><td>6017.40</td><td>-</td><td>12185.07</td><td>-</td></tr></tbody></table>

## 6.3 Reward Shifting and Scaling

In Section 4, we have observed some potential of the reward scaling technique to improve learning performance. It motivates our study in this section where we investigate the combined effect of reward shifting and reward scaling. As shown in the previous section, our proposed adaptive bias shifting demonstrates competitive performance compared to the best version of its fixed bias counterpart. We incorporate it into reward scaling: $r_t = (\Delta f_t - E_t)/n + b_a^-$.

As shown in Table 2, compared to the shifting-only reward function, the overall average ERT of the shifting-scaling version is marginally worse. A similar observation concerning the learning stability, Figure 9 demonstrates that adding bias into the original reward surpasses the shifting-scaling approach in problem sizes of $n \in \{50, 100\}$. In a problem size of $n = 200$, the AUC and HR of the two reward functions are quite competitive with each other. On the other hand, the shifting-scaling association outperforms the original reward signal in the problem size of $n = 300$. In this scenario, shifting-scaling achieves a higher HR compared to the conventional reward function. In general, we do not observe a clear advantage in combining the two mechanisms.

## 7 Scalability Analysis

We extend our experiments to larger problem sizes $n \in \{500, 1000, 2000\}$. In the previous section, we have seen that the magnitude of the bias should increase as the problem size increases. Instead of having to tune the bias for each new problem size, we adopt the adaptive shifting bias idea proposed in the previous section. Additionally, since the problem sizes are significantly larger, we increase the RL training budget to 1.5 million steps, while keeping the same DDQN settings as in previous experiments.

In Table 3, we present two metrics. First the average ERT of DDQN across 10 RL runs, compared to the best policies found using the IRACE cascading method proposed in [14]. We observe that combining reward shifting and reward scaling provides no advantage over using reward shifting alone. This finding is further supported by Figure 9, where the AUC and HR values for the combination are generally lower than those for reward shifting alone. Overall, our adaptive reward shifting mechanism achieves highly competitive ERT and consistently outperforms the discretized theory-derived baseline $\pi_{disc}$ across all three problem sizes. It also surpasses IRACE on $n = 500$ but performs worse than IRACE on the larger problem sizes ($n = 1000$ and $n = 2000$). However, it is important to note that IRACE's tuning budget is substantially larger than our RL training budget. For instance, on $n = 500$, each iteration of IRACE's

cascading process consumes 5,000 episodes, amounting to at least 5,000 × 400 = 2,000,000 time steps. There are 9 iterations in total, which results in an 18-million time-step tuning budget. The tuning budget increases to 75 millions and 308 millions for $n = 1000$ and $n = 2000$, respectively (compared to the 1.5 million budget of RL). The ERT reported in Table 3 reflects the best result IRACE found at the end of this extensive tuning process.

To better assess the sample efficiency of each approach, we measure the number of training time steps required to first surpass the discretized theory-derived baseline $\pi_{disc}$. This metric, shown in the #Steps column of Table 3, reveals that DDQN with reward shifting requires several orders of magnitude fewer time steps than IRACE across all three problem sizes, highlighting DDQN's strong advantage in sample efficiency.

## 8 Conclusion

Our study of deep reinforcement learning for dynamic configuration of $(1+(\lambda,\lambda))$-GA on ONEMAX reveals that naïve DDQN implementations face scalability and convergence issues due to the reward function design. We address these through reward scaling and shifting strategies, including automatic shifting bias adjustment. The proposed reward shifting approach achieves superior performance and significantly improved sample efficiency compared to the previous IRACE-based method. Although our results demonstrate the importance of reward design in DAC, future work could explore alternative reward shaping strategies and extend beyond the theoretical $(1+(\lambda,\lambda))$-GA framework to real-world scenarios.

## Acknowledgments

The project is financially supported by the European Union (ERC, "dynaBBO", grant no. 101125586), by ANR project ANR-23-CE23-0035 Opt4DAC, and by an International Emerging Action funded by CNRS Sciences informatiques. The work used the Cirrus UK National Tier-2 HPC Service at EPCC funded by the University of Edinburgh and EPSRC (EP/P020267/1). André Biedenkapp acknowledges funding through the research network "Responsive and Scalable Learning for Robots Assisting Humans" (ReScaLe) of the University of Freiburg. The ReScaLe project is funded by the Carl Zeiss Foundation. This publication is based upon work from COST Action CA22137 "Randomised Optimisation Algorithms Research Network" (ROAR-NET), supported by COST (European Cooperation in Science and Technology).

## References

[1] Steven Adriaensen, André Biedenkapp, Gresa Shala, Noor Awad, Theresa Eimer, Marius Lindauer, and Frank Hutter. 2022. Automated dynamic algorithm configuration. *Journal of Artificial Intelligence Research* 75 (2022), 1633–1699.

[2] Sandip Aine, Rajeev Kumar, and P.P. Chakrabarti. 2008. Adaptive parameter control of evolutionary algorithms to improve quality-time trade-off. *Applied Soft Computing* 9, 2 (2008), 527–540. https://doi.org/10.1016/j.asoc.2008.07.001

[3] Martin Andersson, Sunith Bandaru, and Amos HC Ng. 2016. Tuning of Multiple Parameter Sets in Evolutionary Algorithms. In *Proceedings of the Genetic and Evolutionary Computation Conference 2016* (2016-01-01). 533–540. https://dl.acm.org/doi/10.1145/2908812.2908899

[4] Marc Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Remi Munos. 2016. Unifying count-based exploration and intrinsic motivation. *Advances in neural information processing systems* 29 (2016).

[5] Marc G. Bellemare, Salvatore Candido, Pablo Samuel Castro, Jun Gong, Marlos C. Machado, Subhodeep Moitra, Sameera S. Ponda, and Ziyu Wang. 2020. Autonomous navigation of stratospheric balloons using reinforcement learning. *Nat.* 588, 7836 (2020), 77–82.
[6] R. Bellman. 1957. A Markovian decision process. *Journal of Mathematics and Mechanics* (1957), 679-684.

[7] Carolin Benjamins, Gjorgjina Cenikj, Ana Nikolikj, Aditya Mohan, Tome Eftimov, and Marius Lindauer. 2024. Instance selection for dynamic algorithm configuration with reinforcement learning: Improving generalization. In *Proceedings of the Genetic and Evolutionary Computation Conference Companion*. 563–566.

[8] André Biedenkapp, H Furkan Bozkurt, Theresa Eimer, Frank Hutter, and Marius Lindauer. 2020. Dynamic algorithm configuration: Foundation of a new meta-algorithmic framework. In *ECAI 2020. IOS Press*, 427–434.

[9] André Biedenkapp, Nguyen Dang, Martin S Krejca, Frank Hutter, and Carola Doerr. 2022. Theory-inspired parameter control benchmarks for dynamic algorithm configuration. In *Proceedings of the Genetic and Evolutionary Computation Conference*. 766–775.

[10] Philipp Bordne, M. Asif Hasan, Eddie Bergman, Noor Awad, and André Biedenkapp. 2024. CANDID DAC: Leveraging Coupled Action Dimensions with Importance Differences in DAC. In *Proceedings of the Third International Conference on Automated Machine Learning (AutoML 2024)*, Workshop Track.

[11] Ronen I Brafman and Moshe Tennenholtz. 2002. R-max-a general polynomial time algorithm for near-optimal reinforcement learning. *Journal of Machine Learning Research 3*, Oct (2002), 213–231.

[12] Yuri Burda, Harri Edwards, Deepak Pathak, Amos Storkey, Trevor Darrell, and Alexei A Efros. 2018. Large-scale study of curiosity-driven learning. *arXiv preprint arXiv:1808.04355* (2018).

[13] Edmund K. Burke, Michel Gendreau, Matthew R. Hyde, Graham Kendall, Gabriela Ochoa, Ender Ozcan, and Rong Qu. 2013. Hyper-heuristics: a survey of the state of the art. *J. Oper. Res. Soc.* 64, 12 (2013), 1695–1724. https://doi.org/10.1057/jors.2013.71

[14] Deyao Chen, Maxim Buzdalov, Carola Doerr, and Nguyen Dang. 2023. Using automated algorithm configuration for parameter control. In *Proceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms*. 38–49.

[15] Leshem Choshen, Lior Fox, and Yonatan Loewenstein. 2018. Dora the explorer: Directed outreach reinforcement action-selection. *arXiv preprint arXiv:1804.04012* (2018).

[16] Jonas Degrave, Federico Felici, Jonas Buchli, Michael Neunert, Brendan D. Tracey, Francesco Carpanese, Timo Ewalds, Roland Hafner, Abbas Abdolmaleki, Diego de Las Casas, Craig Donner, Leslie Frip, Cristian Galpini, Andrea Huber, James Keeling, Maria Tsimpoukelli, Jackie Kay, Antoine Merle, Jean-Marc Moret, Seb Noury, Federico Pesamosca, David Pfau, Olivier Sauter, Cristian Sommariva, Stefano Coda, Basil Duval, Ambrogio Fasoli, Pushmeet Kohli, Koray Kavukcuoglu, Demis Hassabis, and Martin A. Riedmiller. 2022. Magnetic control of tokamak plasmas through deep reinforcement learning. *Nat.* 602, 7897 (2022), 414–419.

[17] Sheelabhadra Dey, James Ault, and Guni Sharon. 2024. Continual optimistic initialization for value-based reinforcement learning. In *Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems*. 453–462.

[18] Benjamin Doerr and Carola Doerr. 2015. Optimal parameter choices through self-adjustment: Applying the 1/5-th rule in discrete settings. In *Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation*. 1335–1342.

[19] Benjamin Doerr and Carola Doerr. 2018. Optimal static and self-adjusting parameter choices for the $(1+(\lambda, \lambda))(1+(\lambda, \lambda))$ genetic algorithm. *Algorithmica* 80 (2018), 1658–1709.

[20] Benjamin Doerr, Carola Doerr, and Franziska Ebel. 2015. From black-box complexity to designing new genetic algorithms. *Theoretical Computer Science* 567 (2015), 87–104.

[21] T. Eimer, A. Biedenkapp, M. Reimer, S. Adriaensen, F. Hutter, and M. Lindauer. 2021. DACBench: A Benchmark Library for Dynamic Algorithm Configuration. In *Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI'21)*. ijcai.org.

[22] Eyal Even-Dar and Yishay Mansour. 2001. Convergence of optimistic and incremental Q-learning. *Advances in neural information processing systems* 14 (2001).

[23] Grant C. Forbes, Nitish Gupta, Leonardo Villalobos-Arias, Colin M. Potts, Arnav Jhala, and David L. Roberts. 2024. Potential-Based Reward Shaping for Intrinsic Motivation. In *Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems* (Auckland, New Zealand) (AAMAS '24). International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 589–597.

[24] Github. 2025. https://github.com/taindp98/OneMax-DAC.git.

[25] Tuomas Haarnoja, Aurick Zhou, Kristian Hartikainen, George Tucker, Sehoon Ha, Jie Tan, Vikash Kumar, Henry Zhu, Abhishek Gupta, Pieter Abbeel, and Sergey Levine. 2018. Soft Actor-Critic Algorithms and Applications. *CoRR* abs/1812.05905 (2018).

[26] Assaf Hallak, Dotan Di Castro, and Shie Mannor. 2015. Contextual Markov Decision Processes. *CoRR* abs/1502.02259 (2015). http://arxiv.org/abs/1502.02259

[27] Nikolaus Hansen. 2006. The CMA evolution strategy: a comparing review. *Towards a new evolutionary computation: Advances in the estimation of distribution algorithms* (2006), 75–102.

[28] Frank Hutter, Holger H. Hoos, Kevin Leyton-Brown, and Thomas Stützle. 2009. ParamILS: An Automatic Algorithm Configuration Framework. 36 (2009), 267–306.

[29] Giorgos Karafotias, Selmar K. Smit, and A. E. Eiben. 2012. A Generic Approach to Parameter Control. In *Proc. of Applications of Evolutionary Computation (EvoAplications'12) (LNCS, Vol. 7248)*. Springer, 366–375. https://doi.org/10.1007/978-3-642-29178-4_37

[30] Elia Kaufmann, Leonard Bauersfeld, Antonio Loquercio, Matthias Müller, Vladlen Koltun, and Davide Scaramuzza. 2023. Champion-level drone racing using deep reinforcement learning. *Nat.* 620, 7976 (2023), 982–987.

[31] Eric Kee, Sarah Airey, and Walling Cyre. 2001. An Adaptive Genetic Algorithm. In *Proc. of Genetic and Evolutionary Computation Conference (GECCO'01)*. Morgan Kaufmann, 391–397. https://doi.org/10.5555/2955239.2955303

[32] Diederik P. Kingma and Jimmy Ba. 2015. Adam: A Method for Stochastic Optimization. In *Proceedings of the 3rd International Conference on Learning Representations, (ICLR'15)*. Yoshua Bengio and Yann LeCun (Eds.).

[33] Michail G Lagoudakis, Michael L Littman, et al. 2000. Algorithm Selection using Reinforcement Learning. In *ICML*. 511–518.

[34] Adam Daniel Laud. 2004. *Theory and application of reward shaping in reinforcement learning*. University of Illinois at Urbana-Champaign.

[35] S. Levine and P. Abbeel. 2014. Learning Neural Network Policies with Guided Policy Search under Unknown Dynamics. In *Proceedings of the 28th International Conference on Advances in Neural Information Processing Systems (NeurIPS'14)*, Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Weinberger (Eds.). 1071–1079.

[36] TP Lillicrap. 2015. Continuous control with deep reinforcement learning. *arXiv preprint arXiv:1509.02971* (2015).

[37] Timothy P. Lillicrap, Jonathan J. Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. 2016. Continuous control with deep reinforcement learning. In *4th International Conference on Learning Representations, ICLR 2016*, San Juan, Puerto Rico, May 2-4, 2016, *Conference Track Proceedings*, Yoshua Bengio and Yann LeCun (Eds.). http://arxiv.org/abs/1509.02971

[38] Marius Lindauer, Katharina Eggensperger, Matthias Feurer, André Biedenkapp, Difan Deng, Carolin Benjamins, Tim Ruhkopf, René Sass, and Frank Hutter. 2022. SMAC: A Versatile Bayesian Optimization Package for Hyperparameter Optimization. *J. Mach. Learn. Res.* 23 (2022), 54:1–54:9. https://jmlr.org/papers/v23/21-0888.html

[39] Manuel López-Ibáñez, Jérémie Dubois-Lacoste, Leslie Pérez Cáceres, Mauro Birattari, and Thomas Stützle. 2016. The irace package: Iterated racing for automatic algorithm configuration. *Operations Research Perspectives* 3 (2016), 43–58.

[40] Haozhe Ma, Kuankuan Sima, Thanh Vinh Vo, Di Fu, and Tze-Yun Leong. [n. d.]. Reward Shaping for Reinforcement Learning with An Assistant Reward Agent. In *Forty-first International Conference on Machine Learning*.

[41] Volodymyr Mnih. 2013. Playing atari with deep reinforcement learning. *arXiv preprint arXiv:1312.5602* (2013).

[42] Andrew Y Ng, Daishi Harada, and Stuart Russell. 1999. Theory and application to reward shaping. In *Proceedings of the Sixteenth International Conference on Machine Learning*.

[43] Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. 2016. Deep exploration via bootstrapped DQN. *Advances in neural information processing systems* 29 (2016).

[44] Jack Parker-Holder, Raghu Rajan, Xingyou Song, André Biedenkapp, Yingjie Miao, Theresa Eimer, Baoe Zhang, Vu Nguyen, Roberto Calandra, Aleksandra Faust, Frank Hutter, and Marius Lindauer. 2022. Automated Reinforcement Learning (AutoRL): A Survey and Open Problems. *Journal of Artificial Intelligence Research (JAIR)* 74 (2022), 517–568. https://doi.org/10.1613/jair.1.13596

[45] J Pettinger and R Everson. 2002. Controlling Genetic Algorithms with Reinforcement Learning. In *Proceedings of the 4th Annual Conference on Genetic and Evolutionary Computation* (2002-01-01). 692–692. https://dl.acm.org/doi/10.5555/2955491.2955607

[46] Jette Randløv and Preben Alstrøm. 1998. Learning to Drive a Bicycle Using Reinforcement Learning and Shaping.. In *ICML*, Vol. 98. 463–471.

[47] Y Sakurai, K Takada, T Kawabe, and S Tsuruta. 2010. A Method to Control Parameters of Evolutionary Algorithms by Using Reinforcement Learning. In *Proceedings of Sixth International Conference on Signal-Image Technology and Internet-Based Systems (SITIS) (2010-01-01)*, K Y é, A Dipanda, and R Chbeir (Eds.). IEEE Computer Society, 74–79. https://ieeexplore.ieee.org/document/5714532

[48] Elias Schede, Jasmin Brandt, Alexander Tornede, Marcel Wever, Viktor Bengs, Eyke Hüllermeier, and Kevin Tierney. 2022. A survey of methods for automated algorithm configuration. *Journal of Artificial Intelligence Research* 75 (2022), 425–487.

[49] Gresa Shala, André Biedenkapp, Noor Awad, Steven Adriaensen, Marius Lindauer, and Frank Hutter. 2020. Learning step-size adaptation in CMA-ES. In *Parallel Problem Solving from Nature-PPSN XVI: 16th International Conference, PPSN 2020. Leiden, The Netherlands, September 5-9, 2020, Proceedings, Part I 16*. Springer, 691–706.
[50] Mudita Sharma, Alexandros Komninos, Manuel López-Ibáñez, and Dimitar Kazakov. 2019. Deep reinforcement learning based parameter control in differential evolution. In *Proceedings of the genetic and evolutionary computation conference*. 709–717.

[51] David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. 2017. Mastering the game of go without human knowledge. *nature* 550, 7676 (2017), 354–359.

[52] Alexander L Strehl and Michael L Littman. 2004. An empirical evaluation of interval estimation for markov decision processes. In *16th IEEE International Conference on Tools with Artificial Intelligence*. IEEE, 128–135.

[53] Ryan Sullivan, Akarsh Kumar, Shengyi Huang, John Dickerson, and Joseph Suarez. 2024. Reward scale robustness for proximal policy optimization via DreamerV3 tricks. *Advances in Neural Information Processing Systems* 36 (2024).

[54] Hao Sun, Lei Han, Rui Yang, Xiaoteng Ma, Jian Guo, and Bolei Zhou. 2022. Exploit reward shifting in value-based deep-rl: Optimistic curiosity-based exploration and conservative exploitation via linear reward shaping. *Advances in neural information processing systems* 35 (2022), 37719–37734.

[55] R.S. Sutton and A.G. Barto. 1998. Reinforcement Learning: An Introduction. *IEEE Transactions on Neural Networks* 9, 5 (1998), 1054–1054. https://doi.org/10.1109/TNN.1998.712192

[56] Richard S Sutton. 1988. Learning to predict by the methods of temporal differences. *Machine learning* 3 (1988), 9–44.

[57] István Szita and András Lörincz. 2008. The many faces of optimism: a unifying approach. In *Proceedings of the 25th international conference on Machine learning*. 1048–1055.

[58] Hado Van Hasselt, Arthur Guez, and David Silver. 2016. Deep reinforcement learning with double q-learning. In *Proceedings of the AAAI conference on artificial intelligence*, Vol. 30.

[59] Hado P Van Hasselt, Arthur Guez, Matteo Hessel, Volodymyr Mnih, and David Silver. 2016. Learning values across many orders of magnitude. *Advances in neural information processing systems* 29 (2016).

[60] Diederick Vermetten, Sander van Rijn, Thomas Bäck, and Carola Doerr. 2019. Online selection of CMA-ES variants. In *Proc. of Genetic and Evolutionary Computation Conference (GECCO'19)*. ACM, 951–959. https://doi.org/10.1145/3321707.3321803

[61] Christopher JCH Watkins and Peter Dayan. 1992. Q-learning. *Machine learning* 8 (1992), 279–292.

[62] Peter R. Wurman, Samuel Barrett, Kenta Kawamoto, James MacGlashan, Kaushik Subramanian, Thomas J. Walsh, Roberto Capobianco, Alisa Devlic, Franziska Eckert, Florian Fuchs, Leilani Gilpin, Piyush Khandelwal, Varun Raj Kompella, HaoChih Lin, Patrick MacAlpine, Declan Oller, Takuma Seno, Craig Sherstan, Michael D. Thomure, Houmehr Aghabozorgi, Leon Barrett, Rory Douglas, Dion Whitehead, Peter Dürr, Peter Stone, Michael Spranger, and Hiroaki Kitano. 2022. Outracing champion Gran Turismo drivers with deep reinforcement learning. *Nat.* 602, 7896 (2022), 223–228.

[63] Ke Xue, Jiacheng Xu, Lei Yuan, Miqing Li, Chao Qian, Zongzhang Zhang, and Yang Yu. 2022. Multi-agent Dynamic Algorithm Configuration. In *Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems, NeurIPS'22*, Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh (Eds.).