I use a dDQN to dispatch drivers in a ride-hailing environment. The action space has size (#drivers + 1), which means we can choose one of the drivers or choose to refuse an order (and wait for the next possibly 'better' order). I am trying to teach the agent when to refuse an order and when to assign it to a driver. The goal is to maximize the total income earned during an episode. This total income is defined by the sum of all prices of the trips served. For the problem we are solving it is also relevant which driver we choose, but this is out of scope for the issue I am writing about.
Refusing an order is relevant since we have both spatial and temporal dynamics. Spatial dynamics mean we have both hot regions (with many requests) and cold regions (with few requests). Temporal dynamics are for example rush hours when the demand is higher than average. Because of these spatial and temporal dynamics, the chances of receiving a new order at the destination of a specific order actually have much influence on the total income earned. For example, if in 5 minutes there appear 2 orders, first an order to a cold region and then an order to a hot region. If there is only one driver available, it is most lucrative to refuse the order to the cold region and let a driver serve the order to a hot region.
The state-space consists of information on both the driver distribution and the specific order we are dispatching. I tried three different reward settings to achieve our objective:
- Option 1: Reward = trip price
In this setting, we simply set the reward equal to the price of the trip in case we serve the order. In case we refuse, the reward = 0. When training the agent, both the loss and Q-value converge. Unfortunately, the agent converges to a situation where refusal is seen as a bad move. This means after training, the agent never refuses an order and always immediately accepts an order. Of course, this is not preferable since we want a situation where we actually remove orders in order to accept a better order in the future.
- Option 2: Reward = 1 if we accept an order to a 'hot node' and -1 in case we reject an order to a 'hot node'
This setting assumes preknowledge about the hot nodes in the environment. The idea is that we first 'directly' give this knowledge to the algorithm through the reward. Once this is working, we can try to find a proxy for the reward metric (e.g. based on the number of orders in the node where the driver arrives or the driver/order distribution in that specific node). This reward setting actually is working: the agent converges to a behavior where it is refusing orders in +-30% of the cases in order to earn more in the future.
- Option 3: Reward = 1 if we accept an order to a node where in the next round the most orders appear and -1 in case we reject an order to such a node
This setting is comparable to option 2. However, we try to implement our 'hot nodes' using a proxy. Unfortunately, this agent also converges to always accepting an order (just as option 1). This could be the case given that the number of orders that appear in a node each timestep is stochastic. This means that the node that is assigned as 'hot' by this proxy, is sometimes incorrect.
The question can be summarized as follows: how can we ensure our algorithm explores the sequence of actions that lead to possibly higher rewards in the future and prevent that it goes for short-term rewards?
The complete idea (with reward setting Option 1) has been implemented using Tabular Q-learning. This algorithm is working and shows a significant improvement compared to a random strategy.
I tried a lot of other things to improve learning, including hyperparameter tuning (e.g. setting gamma to 1 to maximally focus on long-term reward, tweaking the size of the replay buffer, and adjusting the epsilon-exploration settings), adjusting the state space and creating different reward representations. Unfortunately, the impact is minimal: either the agent converges to a 'good' solution where it refuses orders or the agent converges to a situation where it always immediately accepts orders for short-term income. I would say extending the DQN in fancy ways like a prioritized replay or dueling DQN will not solve the problem.
- batch size: 64
- replay memory size: 2**16
- initial epsilon: 0.95
- epsilon anneals linearly to 0.01 over 500000 steps
- warming up period: 200 episodes
- update target model every: 10000 steps
- soft target network update factor: 0.95
- optimizer: AdamOptimizer
- learning rate: 0.0001