Reinforcement Learning for On-Demand Logistics

The assignment algorithm at DoorDash has been crafted over the years to consider all these factors and more, in order to best serve consumers, merchants, and dashers. However, given the breadth of the assignment problem, and the fact that we don’t have ground truths for what the best assignments are, improvements to the algorithm do not always come easily. When Hackathon XIII rolled around, we wondered, “Could an artificially intelligent assignment algorithm learn to improve itself?”.

What is reinforcement learning?

Reinforcement learning is one of the most popular and powerful artificial intelligence algorithms today. Instances of reinforcement learning have reached mainstream news, such as AlphaGo, the reinforcement learned computer program that defeated the world’s top Go player. In short, the goal of reinforcement learning is to learn the best action given a state of the environment, in order to maximize the overall rewards. Here are the fundamental concepts in reinforcement learning, summarized in Figure 2.

State: The current status of the environment. It represents all the information needed to choose an action.

Action: The set of all possible moves at a state.

Reward: The feedback as a result of the action. Note that rewards can be immediate or delayed.

Policy: The strategy used to choose an action at each state.

Agent: The entity that takes actions and tries to learn the best policy.

Environment: The world that the agent interacts with.

Here’s an example application to illustrate these concepts. Let’s say we are designing a delivery robot and teaching it to pick up delivery items while avoiding pedestrians. In this case the robot is an agent trying to learn the optimal policy, i.e. optimal action in each state. The states can be the area that robot is operating in, with the items and pedestrians at various locations, and the actions can be move left, right, forward, or backward. The robot receives a positive reward when it picks up an item, a negative reward when it runs into a pedestrian, and no reward otherwise. With these settings the robot can learn the optimal policy to pick up all the items in a way that maximizes the reward.

The goal of reinforcement learning is to find the optimal policy. This is not trivial since unlike Markov Decision Processes, the rewards and transition probabilities between states are unknown, as seen in Figure 3. For this reason, there are many techniques to either obtain this information (model-based) or obtain the optimal policy directly (model-free), such as Monte Carlo, Bootstrap, and SARSA. The most commonly used is Q-learning, which is a model-free, off-policy method that can directly give us an estimate of the Q function to find the optimal policy.

It is worth mentioning that to use Q-learning, we need to collect data by following an exploration policy. When we are more concerned with learning about the world than maximizing utility, we can choose a no-exploitation, all-exploration policy, which explores the action space by always choosing a random action. When we care more about utility, we need to balance exploration and exploitation, so that we can reap the benefits of what we’ve learned while still not being blind to opportunities that we haven’t yet encountered. One common approach in the second case is the epsilon-greedy algorithm, which explores with probability epsilon and exploits with probability 1-epsilon.

In practice, when there are a large number of states, the state space is featurized and function approximation is used to determine the Q function. This makes the Q function a model instead of a lookup table. Oftentimes, handcrafting features is difficult, so deep learning models like fully connected or convolutional neural networks are used to represent the Q function. This approach is known as Deep Q-Network (DQN) and is very useful when feature dimensionality is high and data volume is also high.

Reinforcement learned assignment

Now we will discuss how we applied reinforcement learning to the DoorDash assignment problem. To formulate the assignment problem in a way that’s suitable for reinforcement learning, we made the following definitions.

State: The outstanding deliveries and working Dashers, since they represent the current status of the world from an assignment perspective. Note that this means that the state space is practically infinite, since deliveries and Dashers individually can have many different characteristics (pick up location/time, drop off location/time, etc.) and there can be many different combinations of deliveries and Dashers.

Action: The most natural choice is the assignment of Dashers to deliveries. However, even with just 15 deliveries and 15 Dashers, the total number of combinations exceeds one trillion! Therefore, to significantly reduce the action space, we defined the actions to be different variants of the assignment algorithm with different parameters. This can be thought of as intelligent parameter tuning where the model learns which parameters are best for a given state of deliveries and Dashers.

Reward: Combination of delivery speeds and Dasher efficiency. We want deliveries to reach customers as quickly as possible while utilizing Dashers as efficiently as possible. This translates to maximizing delivery speeds and maximizing Dasher efficiency. The reward also includes a penalty for undelivered deliveries, to ensure that all the deliveries are actually assigned to Dashers and delivered to consumers.

With these concepts defined to fit reinforcement learning, we now needed to implement the two key components to actually perform reinforcement learning, the environment and the agent.

Environment: We need a system that can output states (deliveries and Dashers) and rewards (delivery speeds and Dasher efficiencies), as well as take in actions (variants of assignment algorithm) and subsequently update the states and rewards. Our production assignment system fits the bill, but we run the risk of hurting our actual deliveries and customers, since the agent might choose bad actions as it learns via an exploration policy. Fortunately, we already have a simulator for our assignment system that can take in an assignment algorithm and produce simulated assignments that mirror our production system. This assignment simulator is used for obtaining offline results before trying online experiments for the assignment system. Therefore, we used this simulator as our environment, allowing us to train our reinforcement learning model on states/actions/rewards that are accurate to our production system without impacting our customers.

Agent: We chose a deep neural network as the agent, since it makes sense to use a model for the Q function and featurize the states into high dimensional vectors, given our infinite state space. More details about this featurization and model will be covered in the next section.

A high level summary of our problem formulation can be found in Figure 4. In summary, the assignment simulator outputs the state, which the agent uses to choose a variant of the assignment algorithm. The assignment simulator runs the chosen algorithm and outputs the new state and the reward, which are both passed back to the agent. This cycle repeats at a preset time interval.

For the actual implementation, we wrapped the DoorDash assignment simulator into an OpenAI Gym environment and used Keras RL for the agent and training, as the two libraries are compatible out-of-the-box.

Deep agent

As previously mentioned, we used a deep neural network as our agent. Recall that the agent maps state and action pairs to rewards. Concretely, the network takes as input the state (represented as different features) and predicts the Q-value for each action, as seen in Figure 5.