Patent ID: 12198216

DETAILED DESCRIPTION

Specific, non-limiting embodiments of the present invention will now be described with reference to the drawings. It should be understood that particular features and aspects of any embodiment disclosed herein may be used and/or combined with particular features and aspects of any other embodiment disclosed herein. It should also be understood that such embodiments are by way of example and are merely illustrative of a small number of embodiments within the scope of the present invention. Various changes and modifications obvious to one skilled in the art to which the present invention pertains are deemed to be within the spirit, scope and contemplation of the present invention as further defined in the appended claims.

The methods, systems, and storage mediums disclosed herein may be applied to various sequential recommendation problems, such as commodity recommendation, study material recommendation, incentives recommendation. The following description uses a ride-hailing platform recommending incentive programs to drivers as an example, but the approaches may be applied to other sequential recommendation scenarios with minor adjustments.

In some embodiments, the approaches disclosed herein may be adopted to design a method for applying reinforcement learning (RL) to optimize or train program recommendation policies in a virtual environment before the policies are actually deployed in a real-world environment. The virtual environment may refer to a simulated environment approximating the real-world environment, both of which include a plurality of drivers, a ride-hailing platform, and various environment parameters (also called confounding variables or confounding factors). The (virtual) drivers, the (virtual) ride-hailing platform, and the (virtual) various environment parameters interact in a similar way in the virtual environment as the ones interact in the real-world environment. In some embodiments, the virtual environment may be constructed as a simulator trained based on historical data to precisely recover the key dynamics of the real-world environment. The trained simulator may simulate interactions between virtual drivers and a virtual ride-hailing platform for a given program recommendation policy. In order to apply RL, an uplift inference network may be trained as a reward function for the virtual environment to quantify rewards for the simulated interactions. By combining the virtual environment with the uplift inference network, a program recommendation policy candidate may be trained or optimized to maximize the rewards without incurring interaction costs with the real-world environment.

Recommending programs by a ride-hailing platform to drivers using the platform may be classified as a sequential recommendation problem. The platform needs to make recommendations to drivers while taking into account the drivers' feedback. For example, the platform may recommend personalized programs (e.g., a certain amount of reward for finishing a certain number of orders within a period of time) to each driver, where each program is recommended according to how a previous program was received and responded by a corresponding driver. Thus, RL may be used to train a policy to make recommendations that maximize one or more desired rewards for the ride-hailing platform. In order to avoid the high trial-and-error cost of applying RL in the real-world environment (e.g., directly interact with drivers and the platform), the real-world environment may first be reconstructed as a virtual environment that approximates the real-world environment. In the following description, the driver in the virtual environment may refer to a virtual driver simulating a driver in the real-world (e.g., the way how the driver reacts to a recommended program), and the ride-hailing platform in the virtual environment may refer to a virtual ride-hailing platform that approximates the real-world ride-hailing platform (e.g., the way how the platform determines which program to recommend in observation of a driver's state).

The environment reconstruction may be accomplished by training an action policy for each virtual player (who can act in response to an observation) in the environment based on historical data. Take the example of the ride-hailing platform recommending programs to drivers, the drivers and the platform may be viewed as two agents interacting with each other, where the driver agent views the platform as the driver's environment, and the platform agent views the drivers as the platform's environment. Therefore, a platform policy and a driver policy may be trained from the historical data to simulate the interactions between the platform and the drivers. However, from the perspective of the drivers, they may receive much more information from the real-world that is not recorded in the historical data. These unobservable factors may be referred to as hidden confounders. Therefore, in order to accurately reconstruct a realistic environment in the real-world environment, these hidden confounders may be taken into account while training the policies in the virtual environment.

To facilitate describing application scenarios of various embodiments disclosed herein, several terms are first explained below.

Generative Adversarial Nets (GAN) may refer to an unsupervised machine learning technique that involves two neural networks, pitting one against the other (thus “adversarial”) in order to generate new, synthetic instances of data that approximate the data distribution of real data. For example, GAN may train a generator G and a discriminator D in a two-player zero-sum game, wherein objective function is represented as:

argminG⁢argmaxDϵ⁡(0,1)⁢𝔼x~pE[log⁢D⁡(x)]+𝔼z∼pz[log⁡(1-D⁡(G⁡(z)))](1)
where G is the generator, D is the discriminator, PE is the expected (i.e., desired) distribution, and PZ is a noise distribution, x is a sample generated from the expected distribution, and z is a sample generated from the noise distribution. In this game, the generator G learns to produce samples x from the expected data distribution. The discriminator D is trained to classify the real samples and the generated samples by supervised learning, while the generator G aims to minimize the classification accuracy of D by generating samples like real ones. It may be noted that D may generate a value between 0 and 1 representing the similarity between the generated samples and the real ones. The discriminator D and the generator G are trained in an adversarial fashion until converge.

Generative Adversarial Imitation Learning (GAIL) allows a policy (e.g., an action policy learned in machine learning algorithms) to interact with the environment. It adopts the GAN framework to learn the policy (e.g., the generator G) with the guidance of a reward function (e.g., the discriminator D) given expert demonstrations as real samples. Using the same example as above, GAIL formulates an objective function represented as:

argminπ⁢argmaxDϵ⁡(0,1)⁢𝔼π[log⁢D⁡(s,a)]+𝔼πE[log⁡(1-D⁡(s,a))]-λ⁢H⁡(π)(2)
wherein π stands for the policy to be trained, D is the reward function, s refers to a state, a refers to an action, (s, a) represents a state-action pair, πEstands for the expert's join distribution over state-action pairs, λ is a multiplier, and H(π)π[−log π(a|s)] represents the entropy of π.

With GAIL, the policy it may be optimized to maximize the similarity between the policy-generated trajectories and the expert ones measured by D. The “similarity” may be understood as a reward, or a negative loss. Thus, the updates to policy π are aimed to minimize a loss function represented as:
l(s,π(s))=x[logD(s,a)]−λH(π)≈τi[log π(a|s)Q(s,a)]−λH(π)  (3)
where Q(s, a)=τi[log(D(s, a))|s0=s, a0=a] is the state-action value function, π stands for the policy to be trained, D is the reward function (e.g., the discriminator), (s, a) represents a state-action pair, πEstands for the expert's join distribution over state-action pairs, λ is a multiplier, and H(π) represents the entropy of π. The discriminator D is trained to predict the conditional distribution D(s, a)=p(y|s, a), where y∈[πE, π]. In other words, D(s, a) may be understood as the likelihood (e.g., probability) that the pair (s, a) comes from π rather than from πE.

Uplift Modeling may refer to a set of techniques that model the incremental impact of an action or a treatment on a user outcome. For example, a manager in an e-business company may be interested in estimating the effect of sending an advertising email to different customers on their probability to click the links to promotional ads. Uplift modeling is both a causal inference and a machine learning problem. It is a causal inference problem because it needs to estimate the difference between two outcomes that are mutually exclusive for an individual (either receives a promotional email or does not receive it). It is a machine learning problem as it needs to train different models and select the one that yields the most reliable uplift prediction according to some performance metrics.

The approaches disclosed herein may be adopted to design a pipeline for applying reinforcement learning (RL) to optimize or train program recommendation policies in a virtual environment before the policies are actually deployed in a real-world environment. In some embodiments, the virtual environment may be constructed as a simulator trained based on historical data to precisely recover the key dynamics of the real-world environment. The trained simulator may simulate interactions between drivers and a ride-hailing platform for a given program recommendation policy. In order to apply RL, an uplift inference network may be trained as a reward function for the virtual environment to quantify rewards for the simulated interactions. By combining the virtual environment with the uplift inference network, a program recommendation policy candidate may be trained or optimized to maximize the rewards without incurring interaction costs with the real-world environment.

FIG.1Aillustrates differences between Markov Decision Process (MDP) in a classic environment and an environment with a confounder in accordance with various embodiments. A Markov decision process (MDP) is a discrete time stochastic control process. It provides a mathematical framework for modeling decision making in situations where outcomes are partly random and partly under the control of a decision maker. RL is often adopted to solve MDP. As mentioned above, real-world scenarios often are too complex to offer a fully observable environment because of the presence of hidden confounders, such as weather, special events, holidays, other drivers' reactions, family members' location and schedule, government policies and regulations, competitors' policy changes, another suitable confounding factor, or any combination thereof. Ignoring these hidden confounders during RL may result in misunderstanding of the MDP and thus generate inaccurate policies. The embodiments disclosed herein learn a hidden confounding policy to take into account the impact of these confounders on the players (the drivers or the ride-hailing platform) in the real-world environment.

As shown inFIG.1A, in the classic setting of section (a), the environment is assumed fully observable. That is, the policy may be learned solely based on the states observed from the environment. For example, the next state st+1 in a MDP depends on the previous state st and the executed action at in response to the previous state. However, in real-world applications, the next state st+1 may be further influenced by some hidden confounders. As shown in section (b) ofFIG.1A, a confounding variable h (also denoted as a confounder) may be present in the environment and not observable. In RL, hidden confounders may affect both actions and rewards as an agent interacts with the environment. For example, the previous state st and the hidden confounding variable h may be jointly deemed as an observation ot, which may directly affect the policy in determining the action at. In response to the action at, the environment may transition into the new state st+1, which may be similarly affected by the confounding variable h and jointly provide an observation Ot+1. As a result, ignoring the confounders during the learning process might mislead the RL agents (e.g., policies) by the appeared fake associations in the data, due to the unawareness of the possible hidden causes. Thus, it is important to involve the confounder into the learning task.

FIG.1Billustrates an exemplary system100to which optimizing recommendation policies may be applied, in accordance with various embodiments. The exemplary system100may include a computing system102, a computing device104, and a computing device106. It is to be understood that although two computing devices are shown inFIG.1B, any number of computing devices may be included in the system100. Computing system102may be implemented in one or more networks (e.g., enterprise networks), one or more endpoints, one or more servers, or one or more clouds. A server may include hardware or software which manages access to a centralized resource or service in a network. A cloud may include a cluster of servers and other devices which are distributed across a network.

The computing devices104and106may be implemented on or as various devices such as a mobile phone, tablet, server, desktop computer, laptop computer, vehicle (e.g., car, truck, boat, train, autonomous vehicle, electric scooter, electric bike), etc. The computing system102may communicate with the computing devices104and106, and other computing devices. Computing devices104and106may communicate with each other through computing system102, and may communicate with each other directly. Communication between devices may occur over the internet, through a local network (e.g., LAN), or through direct communication (e.g., BLUETOOTH™, radio frequency, infrared).

In some embodiments, the system100may include a ride-hailing platform. The ride-hailing platform may facilitate transportation service by connecting drivers of vehicles with passengers. The platform may accept requests for transportation from passengers, identify idle vehicles to fulfill the requests, arrange for pick-ups, and process transactions. For example, passenger140may use the computing device104to order a trip. The trip order may be included in communications122. The computing device104may be installed with a software application, a web application, an API, or another suitable interface associated with the ride-hailing platform.

The computing system102may recommend various programs to the passengers and the drivers of the vehicles150through communications122and124, respectively. These programs may be designed for various purposes. For example, promotion programs (e.g., coupons, discounts) may be sent to the passengers140to encourage their use of the ride-hailing service. Driver incentive programs (e.g., bonus for finishing a certain number of rides within a period and/or within a location) may be recommended to the drivers of vehicles150to increase the activities on the platform, or driver supply in certain areas. These passenger promotion programs may be sent to the passengers140through the computing devices104associated with the passengers140, such as smart phones. Similarly, the driver incentive programs may be delivered to the computing devices106associated with the drivers of the vehicles150. After programs are recommended to the passengers140and the drivers of the vehicles150, the computing system102may monitor or collect their reactions in order to determine whether the recommended programs are effective in achieving the desired business purposes. The drivers' reactions may include acting in accordance with the recommended programs (such as repositioning to a target location specified in a recommended program) or acting by ignoring the recommended programs (such as staying idle without serving orders). Based on the monitored or collected reactions, the computing system102may determine and adjust its strategy in recommending the next program. The recommended programs (from the ride-hailing platform) and reactions (of the drivers in response to the recommended programs) of this iterative process may be collected and stored in a server130as historical data. The historical data may be mined to help the ride-hailing platform discover the underlying relationships between its program recommendation policies and user (drivers and/or passengers) reactions, and optimize the policies accordingly.

While the computing system102is shown inFIG.1Bas a single entity, this is merely for ease of reference and is not meant to be limiting. One or more components or one or more functionalities of the computing system102described herein may be implemented in a single computing device or multiple computing devices. The computing system102may include a simulator training component112, an uplift inference network training component114, a virtual environment component116, and a candidate policy optimization component118.

In some embodiments, the simulator training component112may be configured to train a simulator by reconstructing the ride-hailing environment. In some embodiments, two representative agents (platform agent πaand driver agent πb) may first be formulated to interact with each other to learn a platform policy and a driver policy. The platform policy may reflect a mapping relationship between an observation (e.g., a driver's state) and a program to be recommended (e.g., an incentive program to be recommended to the driver). The driver policy may reflect a mapping relationship between a recommended program received by a driver and the driver's reaction to the recommended program. In addition, in order to simulate the confounding effect of hidden confounders, a new agent πhmay then be added into the interaction to learn a hidden confounding policy to reflect the impact of the hidden confounders on the driver policy. According to the causal relationship, each of the three policies corresponding to πa, πb, and πhmay be trained based on interaction data between the drivers and the platform by imitation learning. Since the hidden confounders are unobservable from the training data, the policy for πh(denoted as confounding policy) may not be directly learned. In some embodiments, a confounder embedded policy and a compatible discriminator may be used to train the simulator. The confounder embedded policy may embed the confounding policy into one of the observable policies corresponding to πaand πb. The compatible discriminator is designed to discriminate the state-action pairs of the two observable policies (e.g., one observed policy, and one joint policy comprising the other observed policy and the confounding policy) so as to provide the respective imitation reward. As the training converges, the de-confounded environment may be reconstructed as a simulator.

In some embodiments, the uplift inference network training component114may be configured to train a neural network to infer the uplift of a platform action for a given observation. Uplift is a measure of the incremental impact of an action to the platform, and it may be used to measure that efficiency of the action. After the simulator is trained by the simulator training component112, a platform policy candidate (e.g., a manual configured policy, a randomly generated policy, or a to-be-optimized policy) may be trained with RL by interacting with the environment provided by the simulator. In one embodiment, in this simulator-based RL, the platform actions are determined to maximize a long-term cumulative reward. However, in many real-world applications, the execution of an action may consume certain resources (e.g., a budget for the total amount of incentives within a period of time). When the amount of resources is limited, the choice of an action cannot only focus on the reward. For example, an action with the largest long-term value may not be the optimal one if it would inevitably cause more resource consumption. For this reason, the resource utilization efficiency of each action may need to be considered while determining which action to take. In some embodiments, a deep neural network is adopted for uplift modeling to infer the uplift in a multi-treatment setting, where each treatment may correspond to an action. The network structure may be divided into two modules from functional perspective: representation module and inference module. The representation module may be designed to learn effective representations of the counter-factual space (e.g., an observation in the environment). Following the representation module, the inference module may split into two branches: the control branch and the treatment branch. The control branch may be trained to predict the potential outcome of a control action (e.g., without treatment). Based on the output of the control branch, the treatment branch is trained to infer the uplift behind the observed outcome by executing a treatment. The network may be trained in an alternate optimization approach, by inferring uplift by alternately updating the parameters of two branches. When the model converges, the output of the treatment branch may converge to the true value of uplift.

In some embodiments, the virtual environment component116may be configured to construct a virtual training environment for optimizing platform policy candidates. The simulator constructed by the simulator training component112may generate simulated interactions between drivers and the ride-hailing platform in response to the policy candidates, and the uplift inference network trained by the uplift inference network training component114may be used as a reward function to evaluate the simulated interactions and thus guide the optimization of the policy candidates.

In some embodiments, the candidate policy optimization component118may be configured to optimize policy candidates using the virtual environment constructed by the virtual environment component116. The virtual environment may provide a simulator to simulate a driver's response to a platform's action, where the platform's action is determined according to a platform policy candidate, and then simulate the platform's reaction to the driver's response. At the same time, the uplift inference network trained by the uplift inference network training component114may determine a reward for each action determined by the platform policy, and thus provide guidance to optimize the platform policy candidate. In some embodiments, the optimization may be performed for a certain number of iterations or a certain period of time, and the resultant policy may be deemed as an optimized version of the policy. The platform may determine whether to deploy such optimized policy accordingly.

FIG.2illustrates an exemplary construction of a virtual environment for driver program recommendation in accordance with various embodiments. The real-world environment210inFIG.2involves a plurality of drivers and a ride-hailing platform directly interacting with each other. In the real-world environment210, the platform may have various incentive programs to encourage drivers to perform certain actions. For example, after a driver is notified that a certain region has a higher surge multiplier (which may result in higher driver fare), he or she may be incentivized to move towards that region to serve. By this way, the supply-demand balance in that region may be adjusted. During this process, the platform may determine which incentive program to recommend to a specific driver. The factors considered by the platform may include the driver's information. In response to the programs recommended by the platform, the drivers may react in certain ways. The drivers' reactions may transition the drivers' states into new states.

Besides the two observable players (e.g., the drivers and the platform), the real-world environment210may further comprise various hidden confounders that have impact on the drivers' reactions to the policy recommendations. Some examples of the confounding factors may include weather, special events, holidays, other drivers' reactions, government policies and regulations, competitors' policy changes, another suitable confounding factor, or any combination thereof. These confounding factors may not be directly recorded in the real-world historical data215, but they may have an underlying impact on the drivers' reactions. For example, bad weather may discourage a driver from performing according to a recommended program; a competitor's new incentive policy may distract the driver (e.g., by providing more attractive incentives) and thus diminish the effect of the recommended program. As another example, one driver's reaction to a recommended program may affect another driver's decision. Therefore, the drivers' reaction collectively may also affect the impact of the hidden confounders. In other words, the drivers and the hidden confounders interact with each other in an unobservable way. However, the underlying impact of these confounding factors on the drivers may be learned and recovered from the drivers' resultant performance and actual reaction to the recommended programs. In some embodiments, the underlying impact may be recovered as a hidden policy in the virtual environment220corresponding to the real-world environment210.

In some embodiments, the virtual environment220corresponding to the real-world environment210may include a simulated platform policy222, a confounder policy224, and a simulated driver policy226. These policies may be trained based on the real-world data215and collectively generate simulated data225. The virtual environment220is constructed in a way that the data distribution of the generated data225approximates the data distribution of the real-world data215. In some embodiments, the distance between the two data distributions may be measured by various divergences, such as a Kullback-Leibler (KL) divergence, Bregman divergence, Hellinger distance, or another suitable divergence measurement. Here, “approximate” may refer to an action to minimize a divergence between the two data distributions. In some embodiments, a discriminator230may be designed to determine a likelihood that the data generated by the virtual environment is from the real-world data215. A high likelihood may indicate a high quality simulation and thus a higher reward for training the policies. That is, the discriminator230may serve as a reward function for training the policies in the virtual environment220.

Within the virtual environment220, the platform policy222is trained to generate a simulated action of the ride-hailing platform for a driver. The factors considered by the platform policy222may include the driver's features, such as static features (e.g., age, gender, vehicle information, another feature that does not change regularly) and dynamic features (e.g., recent activities, customer rating, current temporal and/or spatial information). In response to a recommendation from the platform policy222, the simulated driver policy226may react in a certain way. As explained above, a driver's reaction may not solely be affected by the recommendation, but also impacted by certain hidden confounders. The underlying impacts of the confounders may be trained as a confounder policy224. Whenever a confounder is implied (e.g., current weather, competitor's new policy), it may be captured by the confounder policy224, and impact the simulated driver policy226. By this way, a driver's reaction simulated by the virtual environment220may take into account the hidden confounders in the real-world environment210.

FIG.3illustrates an exemplary training process of a simulator for driver program recommendation in accordance with various embodiments. The simulator may refer to the virtual environment220inFIG.2. As shown, the training of the simulator may involve a multi-agent generator310and a compatible discriminator320. The multi-agent generator310comprises a first agent learning a platform policy πa, a second agent learning a hidden confounding policy πh, and a third agent learning a driver policy πb. The compatible discriminator320may refer to the discriminator230inFIG.2, and may provide a compatible interface for evaluating both simulated platform actions and simulated driver actions generated by the multi-agent generator310.

In some embodiments, the multi-agent generator310may be learned by imitation learning. The objective function may be defined as:

(πa,πb,πh)=argmin(πa,πb,πh)⁢𝔼oA∼Pτreal[L⁡(oA,aA,aB)](4)
where E refers to expectation, πarefers to the platform policy, πhrefers to the hidden confounding policy, and πbrefers to the driver policy, L refers to an imitation loss function, OArefers to an observation obtained from real historical data, Pτrealrefers to a data distribution of the real historical data, aAmay refer to a simulated action of the platform according to the platform policy πa, and aBmay refer to a simulated action of the driver according to the driver policy πb. That is the training of the three policies aims to minimize a loss function so that the simulated actions generated by the simulator is as close to the real data distribution as possible.

According to formula (3), the imitation loss function L in formula (4) may be represented as:

L⁡(oA,πa,πh,πb)=𝔼πa,πh,πb[log⁢D⁡(oA,aA,aB)]-λ⁢∑πϵ⁢{πa,πh,πb}⁢H⁡(π)(5)
where H(π) represents the entropy of π, λ is a multiplier, and D is the discriminator (reward function).

In some embodiments, the platform policy πamay be independent with the hidden confounding policy πhand the driver policy πb. With conditional independence, the D(OA, aA, aB) may be decomposed as

D⁡(oA,aA,aB)=p⁡(πa,πh,πb❘oA,aA,aB)=p⁡(πa❘oA,aA,aB)⁢p⁡(πh,πb❘oA,aA,aB)=p⁡(πa❘oA,aA)⁢p⁡(πh,πb❘oA,aA,aB)=Da(oA,aA)⁢Dhb(oA,aA,aB)(6)
where Da(OA, aA) refers to the imitation item of policy πa, and Dhb(OA, aA, aB) refers to the imitation item of policies πhand πb. Combining formula (5) and (6), the loss function may be decomposed as:

L⁡(oA,πa,πh,πb)=𝔼πa,πh,πb[log⁢Da⁡(oA,aA)⁢Dhb(oA,aA,aB)]-λ⁢∑πϵ⁢{πa,πh,πb}H⁡(π)=𝔼πa[log⁢Da⁡(oA,aA)]-λ⁢H⁡(πa)+𝔼πh,πb⁢Dhb(oA,aA,aB)]-λ⁢∑πϵ⁢{πh,πb}H⁡(π)=L⁡(oA,πa(oA))+l⁡((oA,aA),πb⁢O⁢πh((oA,aA)))(7)
which indicates that the optimization of the three policies may be decomposed as optimizing policy πaand joint policy πhb(comprising both πhand πb) individually by minimizing their respective loss functions. The loss function for the platform policy πamay be represented as:

l⁡(oA,πa(oA))=𝔼π⁢a[log⁢Da(oA,aA)]-λ⁢H⁡(πa)≅𝔼τi[log⁢πa(aA❘oA)⁢Q⁡(oA,aA)-λ⁢H⁡(πa)(8)
where Q(oA, aA)=τi[log(D(oA, aA))|o0−oA, a0=aA] refers to a state-action value function of πa, and the loss function of the joint policy πhbmay be represented as:

l⁡((oA,aA),πhb((oA,aA)))=𝔼π⁢h,π⁢b[log⁢Dhb((oA,aA),aB)]-λ⁢∑πϵ⁢{πh,πb}H⁡(π)≅𝔼τi[log⁢πhb(aB❘oA,aA)⁢Q⁡(oA,aA,aB)]-λ⁢∑πϵ⁢{πh,πb}H⁡(π)(9)
where Q(oA, aA, aB)=τi[log(D(oA, aA), aB))|o0=oA, aA0=aA, aB0=aB] refers to a state-action value function of πhb.

As described above, the interaction between the agent A (platform policy agent) and the agent B (driver policy agent) may be observed, while the policy and data of the agent H (known as hidden confounders) are unobservable. In some embodiments, based on the decomposition result of the objective function in formula (4), the confounder policy πhwith the observable policy πbmay be jointly trained, denoted as πhb. Together with the observable policy πa, the multi-agent generator may be formalized as an interactive environment of two policies. In some embodiments, the joint policy πhbmay be represented as:
πhb(oA,aA)=πb(oA,aA,πh(oA,aA))  (10)
where the input (OA, aA) and the output aBare both observable from the historical data. Therefore, these two policies πband πhbmay be trained with imitation learning methods to imitate the observed interactions.

Referring back toFIG.3, the policies πa, πb, πhbin the multi-agent generator310collectively determine the simulated actions for the platform and the drivers. In the example shown inFIG.3, OAmay refer to an observation of a driver (e.g., the driver's static and dynamic features), which may be input into the platform policy πato generate a simulated platform action aA. The observation OAand the simulated platform action aAmay then be concatenated as an input to the hidden confounding policy πh, which may generate an intermediate action aH. The aHmay be in the same format as aAbut with adjustments caused by various confounding factors. Subsequently, the observation OA, the simulated platform action aA, and the intermediate action aHmay be concatenated as an input to the driver policy πbto generate a simulated action of the driver aB. With the involvement of the hidden confounding policy πh, the impact of the confounding factors is considered when determining the driver's action in response to the platform's action, e.g., a recommended incentive program.

In some embodiments, the compatible discriminator320shown inFIG.3is trained as a reward provider for the multi-agent generator310. Different from general adversarial learning frameworks where only one task needs to be modeled and learned in the generator, here, at least two different reward functions need to be developed for the platform policy πaand the joint confounder-driver policy πhbin the multi-agent generator, respectively. In some embodiments, the discriminator320is designed to be compatible with both policies and serve a unified interface to provide both reward functions. Correspondingly, the discriminator320may have two types of input: state-action pairs (OA, aA, aB) of policy πhb, and zero-padded state-action pairs (OA, aA, 0) of policy πa. This setting indicates that the discriminator320splits not only the state-action space of the policy πhb, but also the state-action space of the policy πa. Formally, the loss functions may be defined as
Eτsim[log(Dσ(oA,aA,aB))]+Eτreal[log(1−Dσ(oA,aA,aB))]  (11)
for policy πhb, and
Eτsim[log(Dσ(oA,aA,0))]+Eτreal[log(1−Dσ(oA,aA,0))]  (12)
for policy πa, where Γsimrefers to a data distribution of the simulated state-action pairs, Γrealrefers to a data distribution of the real (observed) state-action pairs,represents the parameters of the discriminator. The output of the discriminator320may be a probability that an input state-action pair comes from the data distribution observed in the real environment. The discriminator320may be trained with supervised learning by labeling the real state-action pair as 1 and the simulated fake state-action pair as 0. Accordingly, the reward function for policy πhbmay be represented as:
rHB=−log(1−D(oA,aA,aB))  (13)
and the reward function for policy πamay be represented as:
rA=−log(1−D(oA,aA,0))  (14)

For example, the compatible discriminator320may provide one interface accepting three inputs: an input observation, a first input action, and a second input action. For the case of πa, the observation OAand the simulated platform action aAmay be inputted to the compatible discriminator320as the input observation and the first input action, and the second input action may be padded with a zero. Correspondingly, the compatible discriminator320may generate a reward ra322according to formula (13) for the input state-action pair (SA, aA), where SA=OA. For the case of πhb, the observation OAand the simulated platform action aA(may be collectively denoted as observation B, or OB) may be inputted to the compatible discriminator320as the input observation and the first input action, and the simulated action of the driver aBmay be input to the compatible discriminator320as the second input action. Correspondingly, the compatible discriminator320may generate a reward rhb324according to formula (14) for the input state-action pair (SB, aB), where SB={OA, aA}. This way, one compatible discriminator320is trained to serve as two reward functions (sharing weights) respectively for the platform policy πaand the joint confounder-driver policy πhb.

FIG.4illustrates an exemplary method400for training a simulator for driver program recommendation in accordance with various embodiments. The method400may be adopted to train the multi-agent generator and the compatible discriminator illustrated inFIG.3. The method400may be implemented by the computing system102inFIG.1. Depending on the implementation, the method400may have more, fewer, alternative steps. In some embodiments, the steps (including sub-steps within each step) illustrated inFIG.4may be executed in different order, sequentially or in parallel.

In some embodiments, the method400may start with initializing the parameters of a platform policy, a driver policy, a hidden confounding policy, and a discriminator. The process of the training of the simulator may involve adjusting the parameters of the policies and the discriminator to maximize cumulative rewards.

In step410, a plurality of historical interaction trajectories may be obtained from historical data, each of the plurality of historical interaction trajectories comprising a sequence of observed interaction records between a driver and a ride-hailing platform, each interaction record comprising a recommendation from the ride-hailing platform and the driver's response to the recommendation. The trajectory may span a plurality of points in time. For example, in the context of recommending programs to drivers, the action at each point in time may include recommending (by the ride-hailing platform) a program to a driver according to the driver's state, and the state at each point in time may refer to the driver's state, including dynamic information related to the point in time, such as recent activities up to the point in time, information of the domain (e.g., features and dynamics) that the driver is in, spatial and temporal information, other suitable information, or any combination thereof. In some embodiments, the state may also include the driver's static information such as personal information, the driver's vehicle information, the driver's tenure on the ride-hailing platform. In some embodiments, the state of the driver at each point in time may or may not depend on the action at a previous point in time. For example, if the driver receives a recommended program (i.e., the action by the ride-hailing platform at a previous point in time) and reacts (e.g., stay, relocate, accept an order, etc.) according to the recommended program and the environment, he or she may change its previous state to a new state. In this case, the new state at the current point in time is dependent on the action at the previous point in time and some environmental parameters. As another example, if the driver ignores a recommended program, his or her next state may be independent of the action at the previous point in time, and only affected by the environmental parameters. These environmental parameters may include weather, special events, holidays, family members' locations and schedules, competitor's policies, and so on. For example, the driver may reposition to a target region not only because he or she prefers to execute the recommended program therein, but also because it is more convenient to pick up a family member at the target region. Thus, the driver's new state is not only affected by the action of the platform, but also the environment parameters.

In step420, one of the interaction trajectories may be randomly sampled from the plurality of obtained historical interaction trajectories. The first interaction record in the interaction trajectory may include an initial state of the corresponding driver. The initial state may be inputted into the simulator to generate a simulated interaction trajectory according to the policies in the simulator.

In step430, upon receiving the input state, the platform policy may simulate a platform action. The joint confounder-driver policy may simulate a driver action (e.g., a simulated reaction to the simulated platform action) by considering the input state, the simulated platform action, and the impacts of various confounding factors. Then the discriminator may determine a first reward for the simulated platform action, and a second reward for the simulated driver action. Subsequently, a simulated interaction record may be constructed by including the input state, the simulated action of the platform, the simulated action of the driver, and the first and second rewards. Lastly, the input state may be transitioned to a new state based on the simulated driver's action and predefined transition rules.

In step440, a loop may be created to repeat the step430for a plurality of iterations. In some embodiments, the number of iterations (denoted as T) may be equal to the number of interaction records in the sampled interaction trajectory from the historical data. This is to make sure the simulated trajectory and the sampled interaction trajectory (from the real world)) have the same length. For each iteration, the new state may be fed into the step430as the new input state. In other embodiments, the number of iterations may be greater or smaller than the number of interaction records. In some embodiments, the loop in step440may exit before iterating for T times when certain conditions are met, e.g., when a timer expires.

In step450, the simulated interaction trajectory may be constructed based on the sequence of interaction records generated from step430during the loop.

In step460, the parameters of the platform policy and the joint confounder-driver policy may be updated according to the interaction trajectory. For example, based on the rewards for each interaction record in the trajectory, Trust Region Policy Optimization (TRPO) may be used to optimize the parameters of the policies.

In step470, steps420-460may be repeated to sample more interaction trajectories and further update the parameters of the platform policy and the joint confounder-driver policy until a first exit condition is met. In some embodiments, the first exit condition may be determined based on the number of steps of generator per discriminator step (e.g., updating the discriminator once after the generator is updated for a plurality of times). In other embodiments, the first exit condition may comprise a timer (e.g., the repetition terminates when the time expires), a convergency monitor (e.g., the repetition terminates when the parameters of the generator are converged), another suitable exit condition, or any combination thereof.

In step480, the parameters of the discriminator may be updated by minimizing the losses in formulas (11) and (12).

In step490, the training process in steps420-460may be repeated until a second exit condition is met. In some embodiments, the second exit condition may comprise a counter (e.g., the repetition terminates when the counter expires), a timer (e.g., the repetition terminates when the timer expires), a convergence monitor (e.g., the repetition terminates when the parameters of the generator and/or the discriminator are converged), another suitable exit condition, or any combination thereof.

In step495, the trained policies πa, πh, and πbare returned. These trained policies may be formed as the trained simulator to simulate the interactions between the drivers and the platform.

FIG.5illustrates an exemplary diagram of an uplift inference network for driver program recommendation in accordance with various embodiments. As described above, the uplift inference network may be trained to evaluate the actual reward by performing an action when performing the action itself consumes certain resources. Uplift may serve as a better reward function when the resources are limited. A reward function in the context of machine learning (including RL) provides guidance on how the model (e.g., a policy) being trained needs to be optimized. For example, recommending a program by the ride-hailing platform to a driver may yield certain rewards to the platform (e.g., the driver may finish a greater number of orders), but the rewards may not be solely caused by the recommended program. It is possible that, even if the program is not recommended, the platform still observes some reward. As another example, each program recommended by the ride-hailing platform may consume an uncertain amount of resources, and thus the resource consumption cost needs to be considered during making each recommendation. As a result, it is critical to understand the uplift (also called incremental reward) between recommending the program and not recommending the program. However, a historical interaction trajectory may only disclose the reward of one of the two options (either the program is recommended, or not recommended). Thus, the uplift inference network needs to be trained to predict the incremental reward of recommending each program.

In some embodiments, the uplift inference network may comprise two modules: a representation module520, and an inference module530. The representation module520may be trained to learn high-level features of input observed data (e.g., an observed driver's state) that can effectively represent the potential outcome space. Based on the high-level features, the inference module530may be trained to predict the outcome550that is given in the observed data. In some embodiments, the inference module530may be split into two branches: the control branch532and the treatment branch534. The output of the control branch532comprises the estimated reward if no treatment is performed, and the output of treatment branch534is the uplift estimation for a specific treatment (e.g., the incremental reward).

The representation module520may have a plurality of parameters θ522to be trained, the treatment branch532may have a plurality of parameters ω1to be trained, and the control branch534may have a plurality of parameters ω0to be trained. The input to the uplift inference network may comprise an observation510. Here, the observation510may refer to a driver's information, including static information and dynamic information. The representation module520may then extract high level features from the input observation510, and feed the extracted features into the treatment branch523and control branch534.

In the control branch534, the extracted features are fed through one or more layers of neurons with parameters ω0to generate an estimated reward Y0for not recommending a program to the driver.

In the treatment branch532, the extracted features are fed through one or more layers of neurons with parameters ω1to generate a plurality of uplifts539for a plurality of program candidates to be recommended to the drivers. When the uplift inference network needs to obtain an uplift for recommending a specific program to a driver under a certain condition, a mask vector540may be provided to the treatment branch532of the uplift inference network. The mask vector540comprises a plurality of binary values indicating which program is activated (e.g., queried). If the mask vector540has a value 1 at its position t, the uplift of program t may be extracted from the uplifts539, denoted as ut. Based on the utand the Y0, a final outcome Y may be determined, where Y may represent the observed gain by recommending program t to the driver.

In some embodiments, the uplift inference network may be trained with a supervised alternate optimization approach. The control branch534of the uplift inference network and the representation module520may be jointly trained; and the treatment branch532of the uplift inference network and the representation module520may be jointly trained. Accordingly, the objective function of the training process may be formulated as:
l(x,t,ŷ,θ,ω0,ω1)=L(ŷ,y0(x,θ,ω0)+et*un(x,θ,ω1))  (15)
where θ, ω0, ω1are the parameters for the representation module520, the treatment branch532, and the control branch534, respectively, x refers to the observation510(input state), t refers to time or other suitable temporal information, ŷ refers to the ground truth outcome, y0refers to the predicted outcome550(the outcome from the control branch and the uplift from the treatment branch) under the observation x and treatment t, etrefers to the mask vector540with the t-th bit set as 1, unrefers to the uplifts539, L refers to a loss function that may be a regression loss function (e.g., Mean Squared Error (MSE) or Root Mean Squared Error (RMSE)), or a classification loss function (e.g., a logarithmic loss function).

FIG.6illustrates an exemplary method600for training an uplift inference network for driver program recommendation in accordance with various embodiments. The method600may be used to train the uplift inference network illustrated inFIG.5. Depending on the implementation, the exemplary method600may have more, fewer, or alternative steps as shown inFIG.6. The steps illustrated inFIG.6may be executed in different order, sequentially or in parallel.

In step610, data samples for training the uplift inference network may be obtained by randomized trial experiments. For example, the data samples may be formulated as control-treatment data set D={(x, t, ŷ)} with a plurality of triples (x, t, ŷ). Within the control-treatment data set, some of the triples belong to a control group, and the other triples belong to a treatment group. Both of the control group and the treatment group may comprise a plurality of drivers, where the drivers in the control group do not receive treatments that the drivers in the treatment group receive. In this way, the data collected from the drivers in the control group may be used as a baseline measure, and the data collected from the drivers in the treatment group may be used to, in comparison with the baseline measure, quantify the actual reward (also called uplift) of receiving the treatments. In each triple, x refers to the observed driver's information at a time step, t refers to the time step or other temporal information, and ŷ refers to the observed reward (e.g., for the treatment group, the observed reward of recommending a program to the driver; for the control group, the observed reward of not recommending a program to the driver).

In step620, the representation module, control branch, and the treatment branch of the uplift inference network are initialized with corresponding parameters. Using the denotation ofFIG.5, (θ, ω0) may be trained together, and (θ, ω1) may be trained together.

In step630, from the data samples, a mini batch of data may be selected for training. The selected mini batch of data may include some control group data and some treatment group data, which may be used to train the representation module and the control branch in step640and the representation module and the treatment branch in step642, respectively. For example, in step640, the parameters (θ, ω0) may be updated to minimize the loss function in formula (15) using the control group data, and in step642, the parameters (θ, ω1) may be updated to minimize the loss function in formula (15) using the treatment group data.

In step650, the training steps involving steps630,640, and642may be repeated until an exit condition is met. In some embodiments, the exit condition may comprise a counter (e.g., the repetition terminates when the counter expires), a timer (e.g., the repetition terminates when the timer expires), a convergence monitor (e.g., the repetition terminates when the parameters of the representation module, the control branch, and/or the treatment branch are converged), another suitable exit condition, or any combination thereof.

In step660, after training the uplift inference network for a predetermined number of iterations, the parameters (θ, ω1) of the representation module and the treatment branch may be returned. These two sets of parameters may be deemed as the uplift inference network to provide uplift estimations for simulated platform actions generated by the simulator shown inFIG.3.

FIG.7illustrates an exemplary method700for constructing a virtual environment for a ride-hailing platform in accordance with various embodiments. The method700may be implemented in an environment shown inFIG.1BandFIG.2. The method700may be performed by a device, apparatus, or system illustrated byFIGS.1-6, such as the system102. Depending on the implementation, the method700may include additional, fewer, or alternative steps performed in various orders or in parallel.

Block720includes 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.

Block730includes training a simulator based on the plurality of historical interaction trajectories, 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.

In some embodiments, the confounding policy and the driver policy are trained jointly as a confounder-driver policy, and the training a simulator comprises: training a discriminator 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; initializing the platform policy and the confounder-driver policy to form a multi-agent generator; 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 the discriminator and the first state-action pair, a first reward for the platform policy; 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.

In some embodiments, the training a 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. In some embodiments, 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.

In some embodiments, 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.

Block740includes integrating a reward function with the simulator to construct the virtual environment. In some embodiments, 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 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.

In some embodiments, 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. In some embodiments, 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. In some embodiments, 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.

In some embodiments, the method700may 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. In some embodiments, 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. In some embodiments, the plurality of confounding variables comprise one or more of: location information, weather information, event information, holidays, and a competitor's policy.

In some embodiments, the method700may further comprise 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.

FIG.8illustrates an example computing device in which any of the embodiments described herein may be implemented. The computing device may be used to implement one or more components of the systems and the methods shown inFIGS.1-7. The computing device800may comprise a bus802or other communication mechanism for communicating information and one or more hardware processors804coupled with bus802for processing information. Hardware processor(s)804may be, for example, one or more general purpose microprocessors.

The computing device800may also include a main memory808, such as a random-access memory (RAM), cache and/or other dynamic storage devices810, coupled to bus802for storing information and instructions to be executed by processor(s)804. Main memory808also may be used for storing temporary variables or other intermediate information during execution of instructions to be executed by processor(s)804. Such instructions, when stored in storage media accessible to processor(s)804, may render computing device800into a special-purpose machine that is customized to perform the operations specified in the instructions. Main memory808may include non-volatile media and/or volatile media. Non-volatile media may include, for example, optical or magnetic disks. Volatile media may include dynamic memory. Common forms of media may include, for example, a floppy disk, a flexible disk, hard disk, solid state drive, magnetic tape, or any other magnetic data storage medium, a CD-ROM, any other optical data storage medium, any physical medium with patterns of holes, a RAM, a DRAM, a PROM, and EPROM, a FLASH-EPROM, NVRAM, any other memory chip or cartridge, or networked versions of the same.

The computing device800may implement the techniques described herein using customized hard-wired logic, one or more ASICs or FPGAs, firmware and/or program logic which in combination with the computing device may cause or program computing device800to be a special-purpose machine. According to one embodiment, the techniques herein are performed by computing device800in response to processor(s)804executing one or more sequences of one or more instructions contained in main memory808. Such instructions may be read into main memory808from another storage medium, such as storage device810. Execution of the sequences of instructions contained in main memory808may cause processor(s)804to perform the process steps described herein. For example, the processes/methods disclosed herein may be implemented by computer program instructions stored in main memory808. When these instructions are executed by processor(s)804, they may perform the steps as shown in corresponding figures and described above. In alternative embodiments, hard-wired circuitry may be used in place of or in combination with software instructions.

The computing device800also includes a communication interface818coupled to bus802. Communication interface818may provide a two-way data communication coupling to one or more network links that are connected to one or more networks. As another example, communication interface818may be a local area network (LAN) card to provide a data communication connection to a compatible LAN (or WAN component to communicate with a WAN). Wireless links may also be implemented.

The performance of certain of the operations may be distributed among the processors, not only residing within a single machine, but deployed across a number of machines. In some example embodiments, the processors or processor-implemented engines may be located in a single geographic location (e.g., within a home environment, an office environment, or a server farm). In other example embodiments, the processors or processor-implemented engines may be distributed across a number of geographic locations.

Each of the processes, methods, and algorithms described in the preceding sections may be embodied in, and fully or partially automated by, code modules executed by one or more computer systems or computer processors comprising computer hardware. The processes and algorithms may be implemented partially or wholly in application-specific circuitry.

When the functions disclosed herein are implemented in the form of software functional units and sold or used as independent products, they can be stored in a processor executable non-volatile computer readable storage medium. Particular technical solutions disclosed herein (in whole or in part) or aspects that contribute to current technologies may be embodied in the form of a software product. The software product may be stored in a storage medium, comprising a number of instructions to cause a computing device (which may be a personal computer, a server, a network device, and the like) to execute all or some steps of the methods of the embodiments of the present application. The storage medium may comprise a flash drive, a portable hard drive, ROM, RAM, a magnetic disk, an optical disc, another medium operable to store program code, or any combination thereof.

Particular embodiments further provide a system comprising a processor and a non-transitory computer-readable storage medium storing instructions executable by the processor to cause the system to perform operations corresponding to steps in any method of the embodiments disclosed above. Particular embodiments further provide a non-transitory computer-readable storage medium configured with instructions executable by one or more processors to cause the one or more processors to perform operations corresponding to steps in any method of the embodiments disclosed above.

Embodiments disclosed herein may be implemented through a cloud platform, a server or a server group (hereinafter collectively the “service system”) that interacts with a client. The client may be a terminal device, or a client registered by a user at a platform, wherein the terminal device may be a mobile terminal, a personal computer (PC), and any device that may be installed with a platform application program.

The various features and processes described above may be used independently of one another or may be combined in various ways. All possible combinations and sub-combinations are intended to fall within the scope of this disclosure. In addition, certain method or process blocks may be omitted in some implementations. The methods and processes described herein are also not limited to any particular sequence, and the blocks or states relating thereto can be performed in other sequences that are appropriate. For example, described blocks or states may be performed in an order other than that specifically disclosed, or multiple blocks or states may be combined in a single block or state. The example blocks or states may be performed in serial, in parallel, or in some other manner. Blocks or states may be added to or removed from the disclosed example embodiments. The exemplary systems and components described herein may be configured differently than described. For example, elements may be added to, removed from, or rearranged compared to the disclosed example embodiments.

The various operations of exemplary methods described herein may be performed, at least partially, by an algorithm. The algorithm may be comprised in program codes or instructions stored in a memory (e.g., a non-transitory computer-readable storage medium described above). Such algorithm may comprise a machine learning algorithm. In some embodiments, a machine learning algorithm may not explicitly program computers to perform a function but can learn from training data to make a prediction model that performs the function.

The various operations of exemplary methods described herein may be performed, at least partially, by one or more processors that are temporarily configured (e.g., by software) or permanently configured to perform the relevant operations. Whether temporarily or permanently configured, such processors may constitute processor-implemented engines that operate to perform one or more operations or functions described herein.

Similarly, the methods described herein may be at least partially processor-implemented, with a particular processor or processors being an example of hardware. For example, at least some of the operations of a method may be performed by one or more processors or processor-implemented engines. Moreover, the one or more processors may also operate to support performance of the relevant operations in a “cloud computing” environment or as a “software as a service” (SaaS). For example, at least some of the operations may be performed by a group of computers (as examples of machines including processors), with these operations being accessible via a network (e.g., the Internet) and via one or more appropriate interfaces (e.g., an Application Program Interface (API)).

The performance of certain of the operations may be distributed among the processors, not only residing within a single machine, but deployed across a number of machines. In some example embodiments, the processors or processor-implemented engines may be located in a single geographic location (e.g., within a home environment, an office environment, or a server farm). In other example embodiments, the processors or processor-implemented engines may be distributed across a number of geographic locations.

Throughout this specification, plural instances may implement components, operations, or structures described as a single instance. Although individual operations of one or more methods are illustrated and described as separate operations, one or more of the individual operations may be performed concurrently, and nothing requires that the operations be performed in the order illustrated. Structures and functionality presented as separate components in example configurations may be implemented as a combined structure or component. Similarly, structures and functionality presented as a single component may be implemented as separate components. These and other variations, modifications, additions, and improvements fall within the scope of the subject matter herein.

Although an overview of the subject matter has been described with reference to specific example embodiments, various modifications and changes may be made to these embodiments without departing from the broader scope of embodiments of the present disclosure. Such embodiments of the subject matter may be referred to herein, individually or collectively, by the term “invention” merely for convenience and without intending to voluntarily limit the scope of this application to any single disclosure or concept if more than one is, in fact, disclosed.

The embodiments illustrated herein are described in sufficient detail to enable those skilled in the art to practice the teachings disclosed. Other embodiments may be used and derived therefrom, such that structural and logical substitutions and changes may be made without departing from the scope of this disclosure. The Detailed Description, therefore, is not to be taken in a limiting sense, and the scope of various embodiments is defined only by the appended claims, along with the full range of equivalents to which such claims are entitled.

Any process descriptions, elements, or blocks in the flow diagrams described herein and/or depicted in the attached figures should be understood as potentially representing modules, segments, or portions of code which include one or more executable instructions for implementing specific logical functions or steps in the process. Alternate implementations are included within the scope of the embodiments described herein in which elements or functions may be deleted, executed out of order from that shown or discussed, including substantially concurrently or in reverse order, depending on the functionality involved, as would be understood by those skilled in the art.

As used herein, “or” is inclusive and not exclusive, unless expressly indicated otherwise or indicated otherwise by context. Therefore, herein, “A, B, or C” means “A, B, A and B, A and C, B and C, or A, B, and C,” unless expressly indicated otherwise or indicated otherwise by context. Moreover, “and” is both joint and several, unless expressly indicated otherwise or indicated otherwise by context. Therefore, herein, “A and B” means “A and B, jointly or severally,” unless expressly indicated otherwise or indicated otherwise by context. Moreover, plural instances may be provided for resources, operations, or structures described herein as a single instance. Additionally, boundaries between various resources, operations, engines, and data stores are somewhat arbitrary, and particular operations are illustrated in a context of specific illustrative configurations. Other allocations of functionality are envisioned and may fall within a scope of various embodiments of the present disclosure. In general, structures and functionality presented as separate resources in the example configurations may be implemented as a combined structure or resource. Similarly, structures and functionality presented as a single resource may be implemented as separate resources. These and other variations, modifications, additions, and improvements fall within a scope of embodiments of the present disclosure as represented by the appended claims. The specification and drawings are, accordingly, to be regarded in an illustrative rather than a restrictive sense.

The term “include” or “comprise” is used to indicate the existence of the subsequently declared features, but it does not exclude the addition of other features. Conditional language, such as, among others, “can,” “could,” “might,” or “may,” unless specifically stated otherwise, or otherwise understood within the context as used, is generally intended to convey that certain embodiments include, while other embodiments do not include, certain features, elements and/or steps. Thus, such conditional language is not generally intended to imply that features, elements and/or steps are in any way required for one or more embodiments or that one or more embodiments necessarily include logic for deciding, with or without user input or prompting, whether these features, elements and/or steps are included or are to be performed in any particular embodiment.