Featured
Deep RL with enhanced experience reply
In IEEE World Congress on Computational Intelligence 2026
This work is the product of a Capstone project that I supervised at MITB, with a highly capable and motivated student (now graduate), Lim Kai Zhuo, as first-author. The work is also the result of a collaboration with Aldy Gunawan, Cédric Verbeeck and Dai Bing Tian. It is presented today (24 June 2026) at IEEE WCCI, under the CEC (Congress on Evolutionary Computation) Optimization track.
The full title is Deep Reinforcement Learning for the Stochastic Orienteering Problem with Time Windows, and the code repository can be found here: https://github.com/LimKaiZhuo/Deep-Reinforcement-Learning-with-MEER.
The structure is as follows:
- Introduction
— Problem Statement
— Contributions
— SOPTW Formulation - Methodology
— Overview
— RL Set-up
— RL Training and Exploration
— MEER (improving the replay buffer) - Results and Findings
— RL outperformance on benchmark
— Improvement due to MEER - Conclusion
Introduction
Problem statement
The Orienteering Problem (OP) is an NP-hard problem, and is part of the Combinatorial Optimisation domain. Here, we are dealing with SOPTW (Stochastic OP with Time Windows), which is OP with stochasticity and time constraints, ie. it is not just about getting to places, but getting there within a prescribed timeslot.
The travel time between two nodes varies, which means that the agent must be flexible in responding to changes. Consider this:
You planned to watch a movie at 7.00pm tonight. Your girlfriend wants to return home by 12 midnight. When driving to pick up your girlfriend, there was a massive jam due to an accident, and you arrived at her house at 6.45pm, and the earliest time you can arrive at the cinema is 7.30pm.
What should you do? Going ahead with the original plan would not be ideal.
Contributions
The central message is that online reinforcement learning, enhanced by metaheuristic replay, can adapt to stochastic travel conditions better than fixed offline routes.
Our contributions which got us accepted are as follows:
- used set transformers to encode the graph state, handle stochasticity with QR-DDQN, and utilized Reinforcement Learning (RL) for adaptive decisions to get higher rewards
- introduce Metaheuristic Enhanced Experience Replay (MEER), which integrates metaheuristic operators to generate diverse experiences, improving the RL training
We demonstrated that our RL agents achieve higher rewards by adapting in real time rather than relying on precomputed fixed paths.
SOPTW Formulation
We can represent the problem as a graph. Each location is a node (i.e. vertex), and each connection between two locations is an edge. The agent starts from a starting node, visits some intermediate nodes to collect rewards, and eventually ends at a terminal node.
Each node has a reward and its respective time window. For example, in a tourist-routing example, visiting a famous attraction may give a high reward, while visiting a less important location may give a lower reward.
However, the reward is only collected if the agent arrives within the prescribed time window. If the location is open from 3.00pm to 5.00pm, then arriving at 4.00pm is useful. Arriving at 5.30pm is not.
The complication is that the travel time between two nodes is stochastic. This expectation and variance in time/cost is represented by edges between the nodes. The agent may expect a trip to take 30 minutes, but the realized travel time may be 60 minutes such that arrival time falls outside of an attraction’s operating hours.
So the agent is not simply solving: “What is the best route?”
It is solving: “Given where I am now, the time, the nodes I had visited, the feasible time windows, and how much travel budget remains, what should I do next?”
Methodology
Overview
Before going into individual details, let us build a big-picture view of the approach.
The innermost layer (blue box [1]) is the standard RL interaction: we observe the current state, choose an action, receive some reward from the environment, and transition into the next state.
The second layer (green box [2]) shows the RL training process. Experiences are sampled from the replay buffer and used to updates the Q-network. The outer layer (orange box [3]) is our MEER ‘trick’: it selects top paths, applies metaheuristic operators, re-executes modified routes in the stochastic environment, and stores the resulting episodes back into replay memory.
Graph state representation with Set Transformers
Before the RL agent can make a good decision, it needs to understand the current state of the graph.
Each node contains a feature vector which stores information such as whether it has already been visited/is current node, its operating window, service time (eg. a movie takes 2 hours), associated reward/penalty, as well as spatial information. We also include information about the expected travel time and its variance, along with the remaining budget after visiting that node.
A node with high reward may still be a bad choice if it is far away, risky to travel to, or likely to cause the agent to miss future time windows.
Get James Koh, PhD’s stories in your inbox
Join Medium for free to get updates from this writer.
To encode all these information, we used Set Transformers. This is because locations need to be analyzed in conjunction with all options. The node features are processed through Set Attention Blocks (SABs). Due to the dynamic nature of the Q/K/V components, this means that nodes will attend to each other differently, based on each given situation.
RL Set-up
Once the graph state is encoded, the next question is on how we are going to decide the sequence of nodes to visit.
We formulate the problem as a Markov Decision Process, to be solved via RL. At each step, the agent observes the current state (see above sub-section) of the environment. The action is the choice of next node, with visited nodes explicitly masked out (and hence not selectable, since we don’t want to revisit the same place).
Instead of generating the entire route at once, we build it one step at a time. After each move, the environment reveals the realized travel time, updates its state, and makes the next decision (ie. decide on where to go). This is what makes the approach adaptive. If the agent experiences a delay, the next decision can take into account this delay. It may decide to skip a ‘risky’ node and visit a nearer node or go directly to the terminal node.
The pseudocode below gives an overview of the process.
(line 8 of Algo1) During training, the agent does not always choose the node it currently thinks is best. Like in classic RL, we need to balance between exploration and exploitation. A hybrid ϵ-greedy and Boltzmann policy exploration was used, biasing exploration toward more promising regions of the action space.
(line 9–10 of Algo1) After the agent chooses an action, the environment performs the transition. The agent travels to the selected node, observes the realized travel time, receives a reward (if it arrives within the time window), and moves into the next state. This creates an experience tuple (state, action, reward, next_state), accumulated in a replay buffer. Top-performing episodes are also stored in a separate heap, to be used under MEER, to be described in a stand-alone section.
RL Training and Exploration
Quantile Regression Double Deep Q-Network (QR-DDQN) is used to evaluate (and hence select) actions. We learn the distribution of returns through quantile regression, rather than a single expected return. Even though action selection is eventually determined based on the mean values across different quantiles, the training signal is richer this way. Meanwhile, the ‘double’ in DDQN mitigates the tendency for over-optimistic Q-values, by having separate networks for evaluation and selection.
The replay buffer helps make the learning process more efficient, as the neural network does not learn only from the latest experience. Instead, it repeatedly samples past experiences and uses them to update the Q-network, which is an estimator of the expected returns of taking an action under the current state. (reward and return are different things; I assume you have basic RL knowledge, otherwise please refer here for basic definitions).
However, having good experiences to learn from is non-trivial. Trajectories obtained randomly are more likely than not to be poor, and due to the humongous number of possible routes (even for just tens of nodes), obtaining a good trajectory by chance is like finding a needle in a haystack. This is where Metaheuristic Enhanced Experience Replay (MEER) comes in.
MEER
MEER is this paper’s main novelty. To sum up in one sentence, it works like this:
Rather than wait for good things to happen, we make things happen, and keep the good ones
Instead of relying only on random exploratory actions to populate the replay buffer, we take good historical trajectories (stored in a top-N heap amongst other experience) and modify them with metaheuristic operators. The modified action sequence is then re-executed in a separate stochastic environment instance, so the replay buffer receives valid experiences under the same stochastic dynamics.
Imagine you enter a special casino where the games are coin flips. If you get heads, you win money. On the other hand, if you get tails, that particular game is simply ignored and you get to try again in the next round, with your previous winnings intact. Sounds great, right?
At the risk of oversimplifying things, this captures the spirit of evolutionary algorithms, where we select good solutions and mutate them, keeping the better ones.
MEER follows a similar intuition. In terms of selection, we directly maintain on operate on a top-N heap. Specific to our SOPTW problem, we perform intra-route and inter-route modifications to the good trajectories.
Intra-route operators modify a single path, using classic operations such as swap, reverse and insert. In addition, we also introduced a RL-based destroy-reconstruct operator, where a portion of the route is removed and subsequently rebuilt by selecting (using the main Q-network) high-value feasible nodes.
Meanwhile, inter-route operators combine information across two routes with relatively high total rewards. The first route contributes the prefix (ie. initial nodes), while the second route provides candidate nodes for reconstruction (line 4 of Algo 3). The Q-network then selects among these candidates (line 5 of Algo 3). This resembles crossover, but the RL value function guides the reconstruction efficiently.
Results and Findings
To evaluate our approach, we used a benchmark SOPTW dataset based on real-world road network information from the Netherlands and Luxembourg. The dataset contains 36 test instances with 20, 50, and 100 nodes. Each instance includes node rewards, penalties, service times, opening and closing times, as well as mean and variance adjacency matrices representing travel-time between nodes.
For each test instance, the RL agent was trained for 1.2 million steps. After training, the learned policy was evaluated over 3000 repeated trials per instance. The average reward was then compared against the benchmark from prior SOPTW literature.
RL outperformance on benchmark
The first key result is that the RL agent performed especially well on larger instances. It consistently outperformed the benchmark across all 100-node scenarios, and outperformed most of the 50-node scenarios.
While larger graphs are more challenging to solve, the larger search space and stochastic variability gives our RL agent more room to benefit from adaptive decision-making. A fixed offline route may look good before execution, but it cannot easily respond after an unexpected delay. On the other hand, such changes do not necessarily throw our RL agent off track, because it chooses one node at a time and can update its next decision based on the current situation.
Improvement due to MEER
The second key result is that MEER improved the RL training process.
When comparing RL with MEER against RL without MEER, the MEER version produced better reward distributions for both 50-node and 100-node instances. The mean, minimum, and maximum rewards improved. The Wilcoxon signed-rank test gave a p-value of 0.001 for the 50-node cases and 0.021 for the 100-node cases, indicating that the improvement was most probably not by chance.
The spread of performance also became tighter, meaning that MEER made the agent not only better on average, but also more consistent. This is important because consistency matters in stochastic routing. We do not only want a method that occasionally finds a good route. We want a method that performs reliably across different stochastic realizations.
We also looked more closely at the MEER operators themselves.
Some operators make very small changes to the route. For example, swap and insert usually modify only one or a few nodes, so the resulting path remains quite similar to the original path. These can be useful for local improvement, but may not create substantial diversity.
Meanwhile, reverse changes the path more notably, with the tendency to create routes that are more different from the original, which can be useful when more exploration is needed. Using inter-route operators, we get even more meaningful diversity. The new route is still based on promising routes discovered, while being different enough to give the replay buffer more useful training experiences.
Conclusion
Our study demonstrates that deep RL can solve SOPTW effectively when paired with graph representations, QR-DDQN, and MEER for more effective experience replay.
More broadly, MEER suggests that the replay buffer does not have to be treated as passive storage. For off-policy RL problems where good experiences are difficult to discover by random exploration alone, there may be value in actively improving the experiences. In our case, this was done through metaheuristic operators applied to promising routes. However, the concept of an enhanced replay buffer can be extended beyond just SOPTW use cases.
Disclaimer: All opinions and interpretations are that of the writer, and not of MITB. I declare that I have full rights to use the contents published here, and nothing is plagiarized. I declare that this article is written by me and not with any generative AI tool such as ChatGPT. I declare that no data privacy policy is breached, and that any data associated with the contents here are obtained legitimately to the best of my knowledge. I agree not to make any changes without first seeking the editors’ approval. Any violations may lead to this article being retracted from the publication.
