IP Library › Granted Patent US 12,198,216
Granted Patent B2
US 12,198,216 · App. 17/058,407 · Granted Jan 14, 2025

Method and system for constructing virtual environment for ride-hailing platforms

Inventors: Wenjie Shang (Beijing, CN); Qingyang Li (Mountain View, CA); Zhiwei Qin (Mountain View, CA); Jieping Ye (Beijing, CN); Yang Yu (Nanjing, CN); Yiping Meng (Beijing, CN)
Assignee: Beijing DiDi Infinity Technology and Development Co., Ltd.
G06Q50/40G06N20/00G06Q10/067G06Q30/0207
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,198,216
App. No.
17/058,407
Granted
Jan 14, 2025
Kind
B2
Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for constructing a virtual environment for a ride-hailing platform are disclosed. An exemplary method comprises: obtaining a plurality of historical interaction trajectories each comprising one or more interaction records between a driver and a ride-hailing platform, each interaction record comprising a program recommendation of the ride-hailing platform to the driver and a reaction of the driver in response to the program recommendation; training a simulator based on the plurality of historical interaction trajectories; and integrating a reward function with the simulator to construct the virtual environment, wherein the plurality of first program recommendations and the plurality of reactions form a plurality of simulated interactions, and a data distribution of the plurality of simulated interactions approximates a data distribution of a plurality of interaction records in the plurality of historical interaction trajectories.

Claims (98)

1. A computer-implemented method for constructing a virtual environment for a ride-hailing platform, comprising:

obtaining a plurality of historical interaction trajectories each comprising one or more interaction records between a driver and the ride-hailing platform, each interaction record comprising a program recommendation of the ride-hailing platform to the driver and a reaction of the driver in response to the program recommendation;

training a simulator based on the plurality of historical interaction trajectories using reinforcement learning (RL); and

integrating a reward function with the simulator to construct the virtual environment,

wherein the simulator comprises:

a platform policy for generating a plurality of first program recommendations by a virtual ride-hailing platform,

a confounding policy for generating a plurality of second program recommendations based on the plurality of first program recommendations and a plurality of confounding variables, and

a driver policy for generating a plurality of reactions of a plurality of virtual drivers based on the plurality of first program recommendations and the plurality of second program recommendations, and

wherein the plurality of first program recommendations and the plurality of reactions form a plurality of simulated interactions between the plurality of virtual drivers and the virtual ride-hailing platform, and a data distribution of the plurality of simulated interactions approximates a data distribution of a plurality of interaction records in the plurality of historical interaction trajectories, and

the confounding policy and the driver policy are trained jointly as a confounder-driver policy, and the training of the simulator comprises:

constructing a multi-agent generator based on the platform policy and the confounder-driver policy;

inputting a driver state of a virtual driver to the multi-agent generator to generate a simulated interaction record according to the platform policy and the confounder-driver policy;

determining a first state-action pair and a second state-action pair from the simulated interaction record;

determining, based on a discriminator and the first state-action pair, a first reward for the platform policy, wherein the discriminator is trained to determine a probability that a state-action pair is from the data distribution of the plurality of interaction records in the plurality of historical interaction trajectories;

determining, based on the discriminator and the second state-action pair, a second reward for the confounder-driver policy; and

optimizing the platform policy and the confounder-driver policy according to the first reward and the second reward, respectively.

2. The method of claim 1 , wherein the integrating a reward function with the simulator comprises:

obtaining a plurality of control-treatment data sets from randomized trial experiments in the ride-hailing platform;

training an uplift inference network based on the plurality of control-treatment data sets, wherein the trained uplift inference network infers a plurality of uplifts corresponding to the plurality of first program recommendations in response to a given driver state, each of the plurality of uplifts indicating a reward difference between (1) the virtual ride-hailing platform not making the corresponding first program recommendation in response to the given driver state and (2) the virtual ride-hailing platform making the corresponding first program recommendation in response to the given driver state; and

integrating the trained uplift inference network as the reward function with the simulator to construct the virtual environment.

3. The method of claim 2 , wherein the control-treatment data set comprises a plurality of treatment data entries and a plurality of control data entries, the plurality of treatment data entries comprising a plurality of rewards for the ride-hailing platform making one or more program recommendations, and the plurality of control data entries comprising a plurality of rewards for the ride-hailing platform not making the one or more program recommendations.

4. The method of claim 2 , wherein the uplift inference network comprises a feature extraction subnetwork for extracting a plurality of features from an input driver state, and an uplift inference subnetwork for inferring an uplift for a first program recommendation in response to the input driver state.

5. The method of claim 4 , wherein the uplift inference subnetwork comprises a treatment branch and a control branch, and the training an uplift inference network comprises:

training the feature extraction subnetwork and the treatment branch based on the control-treatment data set; and

training the feature extraction subnetwork and the control branch based on the control-treatment data set.

6. The method of claim 1 , further comprising optimizing a candidate platform policy in the virtual environment by:

determining an initial driver state;

determining, based on the initial driver state, a simulated interaction between a virtual driver and the virtual ride-hailing platform according to the simulator, wherein the simulated interaction comprises a program recommendation from the virtual ride-hailing platform;

determining a reward for the program recommendation from the virtual ride-hailing platform according to the reward function in the virtual environment;

optimizing one or more parameters of the candidate platform policy based on the reward; and

transitioning the initial driver state to a new driver state based on the simulated interaction.

7. The method of claim 6 , wherein the initial driver state comprises at least one of following driver features at a time step: gender, age, tenure on the ride-hailing platform, and recent activities on the ride-hailing platform.

8. The method of claim 1 , wherein the plurality of confounding variables comprise one or more of: location information, weather information, event information, holidays, and a competitor's policy.

9. The method of claim 1 , wherein the training the simulator further comprises:

obtaining a simulated interaction trajectory generated by the multi-agent generator; and

updating one or more parameters of the discriminator based on the simulated interaction trajectory to minimize a first loss function corresponding to the platform policy and a second loss function corresponding to the confounder-driver policy.

10. The method of claim 1 , wherein the inputting a driver state to the multi-agent generator to generate a simulated interaction record comprises:

generating, according to the platform policy and the driver state, a third program recommendation;

generating, according to the confounding policy, a fourth program recommendation based on (1) the driver state and (2) the third program recommendation;

generating, according to the driver policy, a reaction of the virtual driver based on (1) the driver state, (2) the third program recommendation, and (3) the fourth program recommendation; and

obtaining a simulated interaction record comprising the driver state, the third program recommendation, and the reaction.

11. The method of claim 10 , wherein:

the first state-action pair comprises a first state and a first action;

the second state-action pair comprises a second state and a second action, and

determining the first state-action pair and the second state-action pair from the simulated interaction record comprises:

for the first state-action pair, determining the driver state as the first state, and the third program recommendation as the first action; and

for the second state-action pair, determining the driver state and the third program recommendation jointly as the second state, and the reaction of the virtual driver as the second action.

12. The method of claim 1 , further comprising evaluating a candidate platform policy in the virtual environment by:

determining an initial driver state;

determining, based on the initial driver state, a simulated interaction trajectory between a virtual driver and the virtual ride-hailing platform according to the simulator;

obtaining a plurality uplifts for the plurality of first program recommendations by the virtual ride-hailing platform in the simulated interaction trajectory; and

determining a score of the candidate platform policy based on the plurality of uplifts.

13. A system comprising one or more processors and one or more non-transitory computer-readable memories coupled to the one or more processors, the one or more non-transitory computer-readable memories storing instructions that, when executed by the one or more processors, cause the system to perform operations comprising:

obtaining a plurality of historical interaction trajectories each comprising one or more interaction records between a driver and a ride-hailing platform, each interaction record comprising a program recommendation of the ride-hailing platform to the driver and a reaction of the driver in response to the program recommendation;

training a simulator based on the plurality of historical interaction trajectories using reinforcement learning (RL); and

integrating a reward function with the simulator to construct an virtual environment,

wherein the simulator comprises:

a platform policy for generating a plurality of first program recommendations by a virtual ride-hailing platform,

a confounding policy for generating a plurality of second program recommendations based on the plurality of first program recommendations and a plurality of confounding variables, and

a driver policy for generating a plurality of reactions of a plurality of virtual drivers based on the plurality of first program recommendations and the plurality of second program recommendations, and

wherein the plurality of first program recommendations and the plurality of reactions form a plurality of simulated interactions between the plurality of virtual drivers and the virtual ride-hailing platform, and a data distribution of the plurality of simulated interactions approximates a data distribution of a plurality of interaction records in the plurality of historical interaction trajectories, and

the confounding policy and the driver policy are trained jointly as a confounder-driver policy, and the training of the simulator comprises:

constructing a multi-agent generator based on the platform policy and the confounder-driver policy;

inputting a driver state of a virtual driver to the multi-agent generator to generate a simulated interaction record according to the platform policy and the confounder-driver policy;

determining a first state-action pair and a second state-action pair from the simulated interaction record;

determining, based on a discriminator and the first state-action pair, a first reward for the platform policy, wherein the discriminator is trained to determine a probability that a state-action pair is from the data distribution of the plurality of interaction records in the plurality of historical interaction trajectories;

determining, based on the discriminator and the second state-action pair, a second reward for the confounder-driver policy; and

optimizing the platform policy and the confounder-driver policy according to the first reward and the second reward, respectively.

14. The system of claim 13 , wherein the integrating a reward function with the simulator comprises:

obtaining a plurality of control-treatment data sets from randomized trial experiments in the ride-hailing platform;

training an uplift inference network based on the plurality of control-treatment data sets, wherein the trained uplift inference network infers a plurality of uplifts corresponding to the plurality of first program recommendations in response to a given driver state, each of the plurality of uplifts indicating a reward difference between (1) the virtual ride-hailing platform not making the corresponding first program recommendation in response to the given driver state and (2) the virtual ride-hailing platform making the corresponding first program recommendation in response to the given driver state; and

integrating the trained uplift inference network as the reward function with the simulator to construct the virtual environment.

15. The system of claim 13 , wherein the operations further comprise optimizing a candidate platform policy in the virtual environment by:

determining an initial driver state;

determining, based on the initial driver state, a simulated interaction between a virtual driver and the virtual ride-hailing platform according to the simulator, wherein the simulated interaction comprises a program recommendation from the virtual ride-hailing platform;

determining a reward for the program recommendation from the virtual ride-hailing platform according to the reward function in the virtual environment;

optimizing one or more parameters of the candidate platform policy based on the reward; and

transitioning the initial driver state to a new driver state based on the simulated interaction.

16. A non-transitory computer-readable storage medium storing instructions that, when executed by one or more processors, cause the one or more processors to perform operations comprising:

obtaining a plurality of historical interaction trajectories each comprising one or more interaction records between a driver and a ride-hailing platform, each interaction record comprising a program recommendation of the ride-hailing platform to the driver and a reaction of the driver in response to the program recommendation;

training a simulator based on the plurality of historical interaction trajectories using reinforcement learning (RL); and

integrating a reward function with the simulator to construct an virtual environment,

wherein the simulator comprises:

a platform policy for generating a plurality of first program recommendations by a virtual ride-hailing platform,

a confounding policy for generating a plurality of second program recommendations based on the plurality of first program recommendations and a plurality of confounding variables, and

a driver policy for generating a plurality of reactions of a plurality of virtual drivers based on the plurality of first program recommendations and the plurality of second program recommendations, and

wherein the plurality of first program recommendations and the plurality of reactions form a plurality of simulated interactions between the plurality of virtual drivers and the virtual ride-hailing platform, and a data distribution of the plurality of simulated interactions approximates a data distribution of a plurality of interaction records in the plurality of historical interaction trajectories, and

the confounding policy and the driver policy are trained jointly as a confounder-driver policy, and the training of the simulator comprises:

constructing a multi-agent generator based on the platform policy and the confounder-driver policy;

inputting a driver state of a virtual driver to the multi-agent generator to generate a simulated interaction record according to the platform policy and the confounder-driver policy;

determining a first state-action pair and a second state-action pair from the simulated interaction record;

determining, based on a discriminator and the first state-action pair, a first reward for the platform policy, wherein the discriminator is trained to determine a probability that a state-action pair is from the data distribution of the plurality of interaction records in the plurality of historical interaction trajectories;

determining, based on the discriminator and the second state-action pair, a second reward for the confounder-driver policy; and

optimizing the platform policy and the confounder-driver policy according to the first reward and the second reward, respectively.

17. The storage medium of claim 16 , wherein the integrating a reward function with the simulator comprises:

obtaining a plurality of control-treatment data sets from randomized trial experiments in the ride-hailing platform;

training an uplift inference network based on the plurality of control-treatment data sets, wherein the trained uplift inference network infers a plurality of uplifts corresponding to the plurality of first program recommendations in response to a given driver state, each of the plurality of uplifts indicating a reward difference between (1) the virtual ride-hailing platform not making the corresponding first program recommendation in response to the given driver state and (2) the virtual ride-hailing platform making the corresponding first program recommendation in response to the given driver state; and

integrating the trained uplift inference network as the reward function with the simulator to construct the virtual environment.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Nov 24, 2020
From: SHANG, WENJIE; LI, QINGYANG; QIN, ZHIWEI; YE, JIEPING; YU, YANG; MENG, YIPING
To: BEIJING DIDI INFINITY TECHNOLOGY AND DEVELOPMENT CO., LTD.
Reel/Frame 054459/0706 →
Continuity (1)
Related Publication 20220138887A1 · May 5, 2022
References Cited (52)
US 11017688B1 · Arazi · 2021 [cited by examiner]
US 20090048938A1 · Dupray · 2009 [cited by examiner]
US 20090063274A1 · Dublin, III · 2009 [cited by examiner]
US 20090164321A1 · Vasilakos · 2009 [cited by examiner]
US 20090182630A1 · Otto · 2009 [cited by examiner]
US 20170234688A1 · Abhishek · 2017 [cited by applicant]
US 20170364795A1 · Anderson · 2017 [cited by examiner]
US 20200151640A1 · Chen et al. · 2020 [cited by applicant]
US 20230245651A1 · Wang · 2023 [cited by examiner]
CN 105117777A · 2015 [cited by applicant]
CN 108520452A · 2018 [cited by applicant]
CN 111052158A · 2020 [cited by applicant]
Shuo Ma, Real-Time City-Scale Taxi Ridesharing, 2014, p. 1782-1785 (Year: 2014). [cited by examiner]
Brenna D. Argall et al., “A survey of robot learning from demonstration”, Robotics and Autonomous System, vol. 57, 2009, pp. 469-483. [cited by applicant]
Susan Athey et al. “Machine Learning Methods for Estimating Heterogeneous Casual Effects”, arXiv:1504.01132v1, [stat.ML] Apr. 5, 2015, pp. 1-24. [cited by applicant]
Elias Bareinboim et al., “Bandits with Unobserved Confounders: A Casual Approach”, Accepted to the Neural Information Processing Systems (NIPS) Conference, Technical Report R-460, Nov. 2015, 9 pages. [cited by applicant]
Noam Brown et al., “Safe and Nested Subgame Solving for Imperfect-Information Games”, 31st Conference on Neural Information Processing Systems (NIPS 2017), Long Beach, CA, arXiv:1705.02955v3 [cs.Al] Nov. 16, 2017, 22 pa… [cited by applicant]
Tianqi Chen et al., “XGBoost: A Scalable Tree Boosting System”, arXiv:1603.02754v1 [cs.LG] Mar. 9, 2016, 13 pages. [cited by applicant]
Xinshi Chen et al., “Generative Adversarial User Model for Reinforcement Learning Based Recommendation System”, Proceedings of the 36th International Conference on Machine Learning, Long Beach, CA, PMLR 97, 2019, arXiv:… [cited by applicant]
Chelsea Finn et al., “A Connection Between Generative Adversarial Networks, Inverse Reinforcement Learning, and Energy-Based Models”, arXiv:1611.03852v3 [cs.LG] Nov. 25, 2016, 10 pages. [cited by applicant]
Andrew Forney et al., “Counterfactual Data-Fusion for Online Reinforcement Learners”, Proceedings of the 34th International Conference on Machine Learning, Sydney. Australia, PMLR 70, 2017, Technical Report R-26, Jun. 2… [cited by applicant]
Ian J. Goodfellow et al., “Generative Adversarial Nets”, arXiv: 1406.2661v1 [stat.ML] Jun. 10, 2014, pp. 1-9. [cited by applicant]
Leo Guelman et al., “Optimal personalized treatment rules for marketing interventions: A review of methods, a new proposal, and an insurance case study”, UB Riskcenter Working Paper Series, Working paper Jun. 2014, Rese… [cited by applicant]
Pierre Gutierrez et al., “Casual Inference and Uplift Modeling A review of the Literature”, JMLR: Workshop and Conference Proceedings 67, 2016, pp. 1-13. [cited by applicant]
Behram Hansotia et al., “Incremental Value Modeling”, Journal of Interactive Marketing, vol. 16, No. 3, Summer 2002. [cited by applicant]
Jonathan Ho et al, “Generative Adversarial Imitation Learning”, 30th Conference on Neural Information Processing Systems (NIPS 2016), Barcelona, Spain, 14 pages. [cited by applicant]
Maciej Jaskowski et al., “Uplift modeling for clinical trial data”, Appearing in the ICML 2012 Workshop on Clinical Data Analysis, Edinburgh, Scotland, UK, 2012, 8 pages. [cited by applicant]
Fredrik D. Johansson et al., “Learning Representations for Counterfactual Inference”, Proceedings of the 33rd International Conference on Machine Learning, New York, NY, 2016, JMLR: W&CP vol. 48, 10 pages. [cited by applicant]
Victor S.Y. Lo, “The True Lift Model—A Novel Data Mining Approach to Response Modeling in Database Marketing”, SIGKDD Explorations, vol. 4, Issue 2, Dec. 2002, pp. 78-86. [cited by applicant]
Christos Louizoa et al., “Casual Effect Inference with Deep Latent-Variable Models”, arXiv:1705.08821v1 [stat.ML] May 24, 2017, pp. 1-12. [cited by applicant]
Chaochao Lu et al., “Deconfounding Reinforcement Learning in Observational Settings”, arXiv:1812.10576v1 [cs.LG] Dec. 26, 2018, pp. 1-30. [cited by applicant]
Jacob Menick et al., “Generating High Fidelity Images with Subscale Pixel Networks and Multidimensional Upscaling”, arXiv:1812.01608v1 [cs.CV] Dec. 4, 2018, pp. 1-15. [cited by applicant]
Volodymyr Mnih et al., “Human-level control through deep reinforcement learning”, Research Letter, Nature, vol. 518, Feb. 26, 2015, pp. 529-533. [cited by applicant]
Houssam Nassif et al., “Uplift Modeling with ROC: An SRL Case Study”, Appears in the Proc. of International Conference on Inductive Logic Programming (ILP'13), Rio de Janeiro, Brazil, 2013. [cited by applicant]
Christopher Berner et al., “Dota 2 with Large Scale Deep Reinforcement Learning”, arXiv:1912.06680v1 [cs.LG] Dec. 13, 2019, https://openai.com/bibtex/openai2019dota.bib, pp. 1-66. [cited by applicant]
Judea Pearl, “Causal inference in statistics: An overview”, Statistics Survey, vol. 3, 2009, pp. 96-146, Technical Report R-350, Sep. 2009. [cited by applicant]
Dean A. Pomerleau, “Efficient Training of Artificial Neural Networks for Autonomous Navigation”, Neural Computation 3:1, 1991, pp. 88-97. [cited by applicant]
Nicholas J. Radcliffe, “Using Control Groups to Target on Predicted Lift: Building and Assessing Uplift Models”, 2007, 14 pages. [cited by applicant]
Nicholas J. Radcliffe et al., “Real World Uplift Modeling with Significance-Based Uplift Trees”, Portrait Technical Report TR-2011-1, Stochastic Solutions White Paper, 2011, pp. 1-33. [cited by applicant]
Paul R. Rosenbaum et al., “The central role of the propensity score in observational studies for casual effects”, Biometrika, vol. 70, 1983, pp. 41-55. [cited by applicant]
Stephane Ross et al., “A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning”, Appearing in Proceedings of the 14th International Conference on Artificial Intelligence and Statistics (… [cited by applicant]
Stuart Russell, “Learning agents for uncertain environments (extended abstract)”, Proceedings of the 11th Annual Conference on Computational Learning Theory, Jul. 1998, pp. 101-103. [cited by applicant]
Piotr Rzepakowski et al., “Decision trees for uplift modeling with single and multiple treatments”, Knowl Inf Syst, vol. 32, 2012, pp. 303-327. [cited by applicant]
Stefan Schaal, “Is imitation learning the route to humanoid robots?”, Trends in Cognitive Sciences, vol. 3, No. 6, Jun. 1999, pp. 233-242. [cited by applicant]
John Schulman et al., “Trust Region Policy Optimization”, Proceedings of the 31st International Conference on Machine Learning, Lille, France, 2015. JMLR: W&CP vol. 37, 9 pages. [cited by applicant]
Jing-Cheng Shi et al., “Virtual-Taobao: Virtualizing Real-world Online Retail Environment for Reinforcement Learning”, arXiv:1805.10000v1 [cs.Al] May 25, 2018, pp. 1-15. [cited by applicant]
David Silver et al., “Mastering the Game of Go with Deep Neural Networks and Tree Search”, Nature, vol. 529, Jan. 28, 2016, pp. 484-489. [cited by applicant]
Xiaogang Su et al., “Facilitating Score and Causal Inference Trees for Large Observational Studies”, Journal of Machine Learning Research, vol. 13, 2012, pp. 2955-2994. [cited by applicant]
Stefan Wager et al., “Estimation and Inference of Heterogeneous Treatment Effects using Random Forests”, Journal of the American Statistical Association, vol. 113, No. 523, 2018, pp. 1228-1242, Theory and Methods. [cited by applicant]
Lukasz Zaniewicz et al., “Support Vector Machines for Uplift Modeling”, Proceedings of the 2013 IEEE 13th International Conference on Data Mining Workshops, Dec. 2013, pp. 131-138. [cited by applicant]
Peng Zhao et al., “Handling Concept Drift via Model Reuse”, arXiv:1809.02804v1 [cs.LG] Sep. 8, 2018, pp. 1-33. [cited by applicant]
PCT International Search Report and the Written Opinion mailed Feb. 18, 2021, issued in related International Application No. PCT/CN2020/090215 (9 pages). [cited by applicant]
Cited By (1)
US 12,450,561