Or: How I Learned to Stop Guessing Parameters and Embrace Adaptive Reward Shifting
TL;DR: We are thrilled to share that our paper has been awarded the prestigious Best Paper Award at the Genetic and Evolutionary Computation Conference (GECCO 2025) in Málaga, Spain! Out of a highly competitive pool of international submissions (featuring a strict 36% acceptance rate), this work highlights how a simple, automated “adaptive reward shifting” mechanism prevents AI agents from getting stuck, allowing them to crush traditional theoretical baselines with unprecedented sample efficiency.
Big News from GECCO 2025! 🏆
Held in beautiful Málaga, Spain, from July 14-18, 2025, GECCO is the premier international forum for research in evolutionary computation and randomized search heuristics. Receiving this recognition from the community is an unbelievable milestone for our team.
Our award-winning paper is titled: 👉 “On the Importance of Reward Design in Reinforcement Learning-based Dynamic Algorithm Configuration: A Case Study on OneMax with (1+(λ,λ))-GA”
The Big Idea: Smarter AI Assistants
To understand why this research matters to the general public, imagine you are trying to solve a complex puzzle or optimize a massive logistics network. To get the best result, you have to constantly fiddle with a control panel full of knobs and dials-a tedious process computer scientists call algorithm configuration.
Now, imagine an intelligent AI assistant that doesn’t just sit there with fixed settings, but actively adapts and turns those dials in real-time as the situation changes. This fluid adaptability is known as Dynamic Algorithm Configuration (DAC).
To build this assistant, researchers typically use Reinforcement Learning (RL)-a type of machine learning where an AI agent learns to make optimal decisions by trial and error, guided entirely by a system of virtual “rewards” for good moves and “penalties” for bad ones.
| RL-based Policy | Random Policy |
|---|---|
 |  |
The Problem: Naïve Rewards Trap the AI
The core breakthrough of our paper comes from looking at how these rewards are designed. If you give the AI a standard, intuitive reward signal-like simply tracking immediate progress while subtracting the computational cost-the AI actually becomes too conservative.
Because the computational cost scales with larger settings, a raw calculation makes the AI terrified of spending energy. Instead of exploring bold new strategies, it panics and gets trapped in a loop of picking the smallest, safest settings over and over again. Computer scientists call this divergence-stagnation-and it causes the AI to completely fail when problems grow to a massive scale.
Original Naïve Reward: Traps the AI in safe, low-performing loops.
The Solution: Cultivating AI Curiosity
To break the AI out of this safety trap, our team implemented a strategy called Reward Shifting. By mathematically anchoring a small negative bias factor ($b^{-}$) to the reward structure , we downward-shift the value of the safe, familiar paths. This forces the unchosen paths to look highly attractive by comparison , effectively injecting a sense of virtual “curiosity” that drives the AI to explore the wider environment.
Because manual tuning is time-consuming, we took it a step further by building an Adaptive Shifting mechanism. During a quick warm-up phase, the system automatically checks the median of early environmental responses and configures its own optimal curiosity balance.
Unlocking Massive Scale and Speed
The results speak for themselves. When tested on the rigorous OneMax-DAC benchmark , our curiosity-driven AI assistant consistently surpassed the gold-standard, mathematically proven theoretical limits across all problem dimensions.
Expected Runtime Benchmarks (Lower is Better 👇)
| Problem Complexity ($n$) | Theoretical Standard Policy ($\pi_{disc}$) | Naïve Reward Loop ($r = \Delta f- E$) | Adaptive Shifting (Ours) ($r = \Delta f- E + b_{a}^{-}$) |
|---|---|---|---|
| $n=50$ (Small) | 274.02 | 271.38 | 249.53 |
| $n=100$ (Medium) | 593.44 | 643.67 | 542.12 |
| $n=200$ (Large) | 1248.88 | 1409.01 | 1178.75 |
| $n=300$ (Massive) | 1889.45 | 2500.03 | 1829.65 |
Beyond pure performance, the true superpower of this method is sample efficiency. Traditional, heavy black-box tuning frameworks like IRACE require a grueling budget of up to 75 million to 308 million training steps to stabilize a reliable policy for massive scales ($n=1000$ to $n=2000$).
By giving our agent an off-policy framework backed by adaptive exploration, our model achieved baseline-beating performance in just 12,000 steps. That is an acceleration of several orders of magnitude , making real-time AI parameter adaptation incredibly practical for real-world computing systems where testing configurations is costly.
The Bottom Line
Unlocking Reinforcement Learning for dynamic engineering tasks requires a fundamental paradigm shift:
-
Don’t let raw operational costs dominate and bias your AI’s immediate reward calculations.
-
Use negative reward shifting to build an optimistic, exploratory environment landscape.
-
Let the system auto-calibrate its curiosity boundaries during warm-up data collection.
Interested in exploring the code or implementing our adaptive solvers yourself? Check out the project’s official open-source repository here: 🌐 OneMax-DAC on GitHub
@inproceedings{10.1145/3712256.3726395,
author = {Nguyen, Tai and Le, Phong and Biedenkapp, Andr\'{e} and Doerr, Carola and Dang, Nguyen},
title = {On the Importance of Reward Design in Reinforcement Learning-based Dynamic Algorithm Configuration: A Case Study on OneMax with (1+(λ,λ))-GA},
year = {2025},
isbn = {9798400714658},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3712256.3726395},
doi = {10.1145/3712256.3726395},
booktitle = {Proceedings of the Genetic and Evolutionary Computation Conference},
pages = {1162–1171},
numpages = {10},
location = {NH Malaga Hotel, Malaga, Spain},
series = {GECCO '25}
}