Real-Time Rideshare Driver Supply Values Using Online Reinforcement Learning

Benjamin Han; Hyungjun Lee; Sébastien Martin

doi:10.1145/3534678.3539141

Real-Time Rideshare Driver Supply Values Using Online Reinforcement Learning

Benjamin Han, Hyungjun Lee, Sébastien Martin

Managerial Economics, Decision Sciences and Operations

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

7 Scopus citations

Abstract

In this paper, we present Online Supply Values (OSV), a system for estimating the return of available rideshare drivers to match drivers to ride requests at Lyft. Because a future driver state can be accurately predicted from a request destination, it is possible to estimate the expected action value of assigning a ride request to an available driver as a Markov Decision Process using the Bellman Equation. These estimates are updated using temporal difference and are shown to adapt to changing marketplace conditions in real-time. While reinforcement learning has been studied for rideshare dispatch, fully-online approaches without offline priors or other guardrails had never been evaluated in the real world. This work presents the algorithmic changes needed to bridge this gap. OSV is now deployed globally as a core component of Lyft's dispatch matching system. Our A/B user experiments in major US cities measure a +(0.96±0.53)% increase in the request fulfillment rate and a +(0.73±0.22)% increase to profit per passenger session over the previous algorithm.

Original language	English (US)
Title of host publication	KDD 2022 - Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining
Publisher	Association for Computing Machinery
Pages	2968-2976
Number of pages	9
ISBN (Electronic)	9781450393850
DOIs	https://doi.org/10.1145/3534678.3539141
State	Published - Aug 14 2022
Event	28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2022 - Washington, United States Duration: Aug 14 2022 → Aug 18 2022

Publication series

Name	Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

Conference

Conference	28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2022
Country/Territory	United States
City	Washington
Period	8/14/22 → 8/18/22

Keywords

adaptive
dispatch
matching
multi-agent reinforcement learning
on-policy control
online learning
real-time
rideshare
streaming
temporal difference
transportation

ASJC Scopus subject areas

Software
Information Systems

Access to Document

10.1145/3534678.3539141

Cite this

Han, B., Lee, H., & Martin, S. (2022). Real-Time Rideshare Driver Supply Values Using Online Reinforcement Learning. In KDD 2022 - Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (pp. 2968-2976). (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining). Association for Computing Machinery. https://doi.org/10.1145/3534678.3539141

Han, Benjamin ; Lee, Hyungjun ; Martin, Sébastien. / Real-Time Rideshare Driver Supply Values Using Online Reinforcement Learning. KDD 2022 - Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. Association for Computing Machinery, 2022. pp. 2968-2976 (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining).

@inproceedings{95e76042b3ce481591ccd1554b6985ef,

title = "Real-Time Rideshare Driver Supply Values Using Online Reinforcement Learning",

abstract = "In this paper, we present Online Supply Values (OSV), a system for estimating the return of available rideshare drivers to match drivers to ride requests at Lyft. Because a future driver state can be accurately predicted from a request destination, it is possible to estimate the expected action value of assigning a ride request to an available driver as a Markov Decision Process using the Bellman Equation. These estimates are updated using temporal difference and are shown to adapt to changing marketplace conditions in real-time. While reinforcement learning has been studied for rideshare dispatch, fully-online approaches without offline priors or other guardrails had never been evaluated in the real world. This work presents the algorithmic changes needed to bridge this gap. OSV is now deployed globally as a core component of Lyft's dispatch matching system. Our A/B user experiments in major US cities measure a +(0.96±0.53)% increase in the request fulfillment rate and a +(0.73±0.22)% increase to profit per passenger session over the previous algorithm.",

keywords = "adaptive, dispatch, matching, multi-agent reinforcement learning, on-policy control, online learning, real-time, rideshare, streaming, temporal difference, transportation",

author = "Benjamin Han and Hyungjun Lee and S{\'e}bastien Martin",

note = "Publisher Copyright: {\textcopyright} 2022 Owner/Author.; 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2022 ; Conference date: 14-08-2022 Through 18-08-2022",

year = "2022",

month = aug,

day = "14",

doi = "10.1145/3534678.3539141",

language = "English (US)",

series = "Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining",

publisher = "Association for Computing Machinery",

pages = "2968--2976",

booktitle = "KDD 2022 - Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining",

}

Han, B, Lee, H & Martin, S 2022, Real-Time Rideshare Driver Supply Values Using Online Reinforcement Learning. in KDD 2022 - Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Association for Computing Machinery, pp. 2968-2976, 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2022, Washington, United States, 8/14/22. https://doi.org/10.1145/3534678.3539141

Real-Time Rideshare Driver Supply Values Using Online Reinforcement Learning. / Han, Benjamin; Lee, Hyungjun; Martin, Sébastien.
KDD 2022 - Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. Association for Computing Machinery, 2022. p. 2968-2976 (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Real-Time Rideshare Driver Supply Values Using Online Reinforcement Learning

AU - Han, Benjamin

AU - Lee, Hyungjun

AU - Martin, Sébastien

PY - 2022/8/14

Y1 - 2022/8/14

N2 - In this paper, we present Online Supply Values (OSV), a system for estimating the return of available rideshare drivers to match drivers to ride requests at Lyft. Because a future driver state can be accurately predicted from a request destination, it is possible to estimate the expected action value of assigning a ride request to an available driver as a Markov Decision Process using the Bellman Equation. These estimates are updated using temporal difference and are shown to adapt to changing marketplace conditions in real-time. While reinforcement learning has been studied for rideshare dispatch, fully-online approaches without offline priors or other guardrails had never been evaluated in the real world. This work presents the algorithmic changes needed to bridge this gap. OSV is now deployed globally as a core component of Lyft's dispatch matching system. Our A/B user experiments in major US cities measure a +(0.96±0.53)% increase in the request fulfillment rate and a +(0.73±0.22)% increase to profit per passenger session over the previous algorithm.

AB - In this paper, we present Online Supply Values (OSV), a system for estimating the return of available rideshare drivers to match drivers to ride requests at Lyft. Because a future driver state can be accurately predicted from a request destination, it is possible to estimate the expected action value of assigning a ride request to an available driver as a Markov Decision Process using the Bellman Equation. These estimates are updated using temporal difference and are shown to adapt to changing marketplace conditions in real-time. While reinforcement learning has been studied for rideshare dispatch, fully-online approaches without offline priors or other guardrails had never been evaluated in the real world. This work presents the algorithmic changes needed to bridge this gap. OSV is now deployed globally as a core component of Lyft's dispatch matching system. Our A/B user experiments in major US cities measure a +(0.96±0.53)% increase in the request fulfillment rate and a +(0.73±0.22)% increase to profit per passenger session over the previous algorithm.

KW - adaptive

KW - dispatch

KW - matching

KW - multi-agent reinforcement learning

KW - on-policy control

KW - online learning

KW - real-time

KW - rideshare

KW - streaming

KW - temporal difference

KW - transportation

UR - http://www.scopus.com/inward/record.url?scp=85137139810&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85137139810&partnerID=8YFLogxK

U2 - 10.1145/3534678.3539141

DO - 10.1145/3534678.3539141

M3 - Conference contribution

AN - SCOPUS:85137139810

T3 - Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

SP - 2968

EP - 2976

BT - KDD 2022 - Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining

PB - Association for Computing Machinery

T2 - 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2022

Y2 - 14 August 2022 through 18 August 2022

ER -

Han B, Lee H, Martin S. Real-Time Rideshare Driver Supply Values Using Online Reinforcement Learning. In KDD 2022 - Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. Association for Computing Machinery. 2022. p. 2968-2976. (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining). doi: 10.1145/3534678.3539141

Real-Time Rideshare Driver Supply Values Using Online Reinforcement Learning

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this