Method and system for optimal stopping using fast probabilistic learning algorithms
A method for using a Gaussian Process-based algorithm to approximate an optimal stopping of a time series that corresponds to a sequence of events is provided. The method includes: receiving information that relates to an event sequence; estimating, based on the received information, a first potential reward that is obtained by stopping the event sequence at a first time, and a set of respective second potential rewards that are obtained by stopping the event sequence at corresponding times; and determining, based on the estimated first and second potential rewards, an optimal time for stopping the event sequence. The event sequence may include a numerical sequence that is modeled as a statistical learning method via a Gaussian Process (GP) function and/or a deep GP function that indicates a probability density distribution of the items in the numerical sequence over a predetermined time interval.
1 . A method for determining an optimal time for stopping an event sequence, the method being implemented by at least one processor, the method comprising:
receiving, by the at least one processor, first information that relates to the event sequence, wherein the event sequence includes a sequence of values that is modeled by using a Gaussian Process (GP) function that indicates a probability density distribution of the values over a predetermined time interval;
estimating, by the at least one processor based on the first information, a first potential reward that is obtained by stopping the event sequence at a first predetermined time;
estimating, by the at least one processor based on the first information, a plurality of respective second potential rewards that are obtained by stopping the event sequence at a corresponding one from among a plurality of second predetermined times; and
determining, based on the estimated first potential reward and the plurality of estimated second potential rewards, an optimal time for stopping the event sequence,
wherein the determining of the optimal time for stopping the event sequence comprises applying a non-adaptive artificial intelligence (AI) algorithm that implements a machine learning technique with respect to the first information and the GP function, the non-adaptive AI algorithm being trained by using historical data and fixed warm start data that relates to the event sequence,
wherein the historical data used in training the non-adaptive AI algorithm are clustered and GP function is fitted to a centroid of each cluster for reducing computational complexity, and
wherein the fixed warm start data is provided by clustering, by the at least one processor, an initial warm start period of data that relates to the event sequence for reducing computational complexity.
2 . The method of claim 1 , wherein the determining of the optimal time for stopping the event sequence comprises estimating a value function that relates to a look-ahead value associated with the event sequence at a particular time.
3 . The method of claim 2 , wherein the estimating of the value function is based on an assumption that the value function depends only on a most recent event in the event sequence and a predetermined set of historical data.
4 . The method of claim 1 , wherein the determining of the optimal time for stopping the event sequence further comprises applying an adaptive AI algorithm that modifies the GP function based on a subset of the first information that corresponds to a most recent portion of the predetermined time interval.
5 . The method of claim 1 , further comprising using a result of the applying of the non-adaptive AI algorithm to measure a first metric that relates to a quality of the determination of the optimal time for stopping the event sequence.
6 . The method of claim 1 , further comprising using a result of the applying of the non-adaptive AI algorithm to estimate an uncertainty that relates to the determination of the optimal time for stopping the event sequence.
7 . The method of claim 1 , wherein the event sequence is modeled by using a Deep Gaussian Process (DGP) function that relates to a distribution of a plurality of prior GP functions that each indicate a respective probability density distribution of the values over a predetermined time interval.
8 . A computing apparatus for determining an optimal time for stopping an event sequence, the computing apparatus comprising:
a processor;
a memory; and
a communication interface coupled to each of the processor and the memory,
wherein the processor is configured to:
receive, via the communication interface, first information that relates to the event sequence, wherein the event sequence includes a sequence of values that is modeled by using a Gaussian Process (GP) function that indicates a probability density distribution of the values over a predetermined time interval;
estimate, based on the first information, a first potential reward that is obtained by stopping the event sequence at a first predetermined time;
estimate, based on the first information, a plurality of respective second potential rewards that are obtained by stopping the event sequence at a corresponding one from among a plurality of second predetermined times; and
determine, based on the estimated first potential reward and the plurality of estimated second potential rewards, an optimal time for stopping the event sequence,
wherein the determination of the optimal time for stopping the event sequence comprises applying a non-adaptive artificial intelligence (AI) algorithm that implements a machine learning technique with respect to the first information and the GP function, the non-adaptive AI algorithm being trained by using historical data and fixed warm start data that relates to the event sequence,
wherein the historical data used in training the non-adaptive AI algorithm are clustered and GP function is fitted to a centroid of each cluster for reducing computational complexity, and
wherein the fixed warm start data is provided by clustering an initial warm start period of data that relates to the event sequence for reducing computational complexity.
9 . The computing apparatus of claim 8 , wherein the processor is further configured to estimate a value function that relates to a look-ahead value associated with the event sequence at a particular time.
10 . The computing apparatus of claim 9 , wherein the processor is further configured to estimate the value function based on an assumption that the value function depends only on a most recent event in the event sequence and a predetermined set of historical data.
11 . The computing apparatus of claim 8 , wherein the processor is further configured to determine the optimal time for stopping the event sequence by applying an adaptive AI algorithm that modifies the GP function based on a subset of the first information that corresponds to a most recent portion of the predetermined time interval.
12 . The computing apparatus of claim 8 , wherein the processor is further configured to use a result of the application of the non-adaptive AI algorithm to measure a first metric that relates to a quality of the determination of the optimal time for stopping the event sequence.
13 . The computing apparatus of claim 8 , wherein the processor is further configured to use a result of the application of the non-adaptive AI algorithm to estimate an uncertainty that relates to the determination of the optimal time for stopping the event sequence.
14 . The computing apparatus of claim 8 , wherein the event sequence is modeled by using a Deep Gaussian Process (DGP) function that relates to a distribution of a plurality of prior GP functions that each indicate a respective probability density distribution of the values over a predetermined time interval.
15 . A non-transitory computer readable storage medium storing instructions for determining an optimal time for stopping an event sequence, the storage medium comprising executable code which, when executed by a processor, causes the processor to:
receive first information that relates to the event sequence;
estimate, based on the first information, a first potential reward that is obtained by stopping the event sequence at a first predetermined time;
estimate, based on the first information, a plurality of respective second potential rewards that are obtained by stopping the event sequence at a corresponding one from among a plurality of second predetermined times; and
determine, based on the estimated first potential reward and the plurality of estimated second potential rewards, an optimal time for stopping the event sequence,
wherein the determination of the optimal time for stopping the event sequence comprises applying a non-adaptive artificial intelligence (AI) algorithm that implements a machine learning technique with respect to the first information and the GP function, the non-adaptive AI algorithm being trained by using historical data and fixed warm start data that relates to the event sequence,
wherein the historical data used in training the non-adaptive AI algorithm are clustered and GP function is fitted to a centroid of each cluster for reducing computational complexity, and
wherein the fixed warm start data is provided by clustering an initial warm start period of data that relates to the event sequence for reducing computational complexity.
16 . The storage medium of claim 15 , wherein when executed by the processor, the executable code further causes the processor to estimate a value function that relates to a look-ahead value associated with the event sequence at a particular time.