DETAILED ACTION
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
This office action is in responsive to communication(s): original application filed on 06/28/2023. Claims 1-20 are pending. Claims 1, 11, and 20 are independent.
Specification
The disclosure is objected to because of the following informalities:
in ¶ [0041], "… it can be inferred that (a) or (b is not satisfied …" appears to be "… it can be inferred that (a) or (b) is not satisfied …";
in ¶ [0042], "… where D(n)[Symbol font/0xCE][0,4000], D(n) = 6.65ln(n)+9.57 for FIG. 1, D(n) = 0.037exp(1.15n) for FIG. 2, and D(n) = 0.037exp(1.15n) for FIG. 3, where D(n) = exp(-(n-20)2/40) …" appears to be "… where D(n)[Symbol font/0xCE][0,4000], D(n) = 6.65ln(n)+9.57 for FIG. 2, D(n) = 0.037exp(1.15n) for FIG. 3, and D(n) = exp(-(n-20)2/40) for FIG. 4 …" according to FIGS. 2-4;
in ¶ [0044], "… the method of the invention (ALINUCB) still outperforms other algorithms, but it performance may be explained …" appears to be "… the method of the invention (ALINUCB) still outperforms other algorithms, but its performance may be explained …".
Appropriate correction is required.
The use of the term "Bluetooth" in ¶ [0024] and "Wi-Fi" in ¶¶ [0025]-[0026], which is a trade name or a mark used in commerce, has been noted in this application. The term should be accompanied by the generic terminology; furthermore the term should be capitalized wherever it appears or, where appropriate, include a proper symbol indicating use in commerce such as ™, SM , or ® following the term.
Although the use of trade names and marks used in commerce (i.e., trademarks, service marks, certification marks, and collective marks) are permissible in patent applications, the proprietary nature of the marks should be respected and every effort made to prevent their use in any manner which might adversely affect their validity as commercial marks.
Claim Objections
Claims 1-3, 5-9, 11-13, and 15-20 are objected to because of the following informalities:
in Claim 1, line 5; Claim 11, line 6; and Claim 20, line 6, "… wherein the shape of a reward function for …" appears to be "… wherein a shape of a reward function for …";
in Claim1, line 12; Claim 11, line 13; and Claim 20, line 13, "… causing/cause each of the multiple arms to be independently drawn by …" appears to be "… causing said each of the multiple arms to be independently drawn by …";
in Claim 1, line 15; Claim 11, line 16; and Claim 20, line 16, "… has the best reward during the predetermined time period …" appears to be "… has best reward during the predetermined time period …";
in Claim 1, line 17; Claim 11, line 18; and Claim 20, line 18, "… detecting the expiration of the predetermined time period …" appears to be "… detecting expiration of the predetermined time period …";
in Claim 1, lines 18-19; Claim 11, lines 19-20; and Claim 20, lines 19-20, "… testing each of the multiple arms for a subsequent predetermined time period" appears to be "… testing said each of the multiple arms for a subsequent predetermined time period";
in Claim 2, lines 2-3; and Claim 12, lines 2-3, "… where each of the multiple arms includes a fixed, unknown and independent probability-law of reward" appears to be "… where said each of the multiple arms includes a fixed, unknown and independent probability-law of reward";
in Claim 3, lines 2-3; and Claim 13, lines 2-3, "… the agent selecting an arm from the multiple arms at each step and receiving a non-stationary reward responsive to selecting an arm" appears to be "… the agent selecting an arm from the multiple arms at each step and receiving a non-stationary reward responsive to selecting the arm";
in Claims 5-8 and 15-18, line 1, "… wherein implementing includes …" appears to be "… wherein implementing the ALINUCB algorithm includes …" according to Claims 3 and 13;
in Claim 6, lines 1-3; and Claim 16, lines 1-3, "… applying the policy at a predetermined time to obtain a sequence of choices, wherein the policy includes a Gain" appears to be "… applying the dynamic policy at a predetermined time to obtain a sequence of choices, wherein the dynamic policy includes a Gain";
in Claim 7, lines 1-5; and Claim 17, lines 1-5, "… measuring the policy relative to a predetermined number of plays … an expected gain obtained by the policy" appears to be "… measuring the dynamic policy relative to a predetermined number of plays … an expected gain obtained by the dynamic policy";
in Claim 8, lines 1-4; and Claim 18, lines 1-4, "… computing an index for each of a plurality of trial plays for each of the multiple arms, wherein the index for each arm of the multiple arms is responsive to a corresponding confidence interval" appears to be "… computing an index for each of a plurality of trial plays for said each of the multiple arms, wherein the index for said each of the multiple arms is responsive to a corresponding confidence interval";
in Claim 9, lines 3-6; and Claim19, lines 3-6, "… applying an Argmax function to the arm for each of a plurality of predetermined times; and observing a reward for the arm for each of the predetermined times" appears to be "… applying an Argmax function to the arm for each of a plurality of predetermined times; and observing a reward for the arm for said each of the plurality of predetermined times";
in Claim 12, line 1, "The method of Claim 11 …" appears to be "The computing system of Claim 11 …";
in Claim 13, line 1, "The method of Claim 12 …" appears to be "The computing system of Claim 12 …";
in Claim 14, line 1, "The method of Claim 13 …" appears to be "The computing system of Claim 13 …";
in Claim 15, line 1, "The method of Claim 11 …" appears to be "The computing system of Claim 11 …";
in Claim 16, line 1, "The method of Claim 15 …" appears to be "The computing system of Claim 15 …";
in Claim 17, line 1, "The method of Claim 16 …" appears to be "The computing system of Claim 16 …";
in Claim 18, line 1, "The method of Claim 1 …" appears to be "The computing system of Claim 11 …";
in Claim 19, line 1, "The method of Claim 8 …" appears to be "The computing system of Claim 18 …".
Appropriate correction is required.
Applicant is advised that should Claims 8-9 be found allowable, Claims 18-19 will be objected to under 37 CFR 1.75 as being a substantial duplicate thereof. When two claims in an application are duplicates or else are so close in content that they both cover the same thing, despite a slight difference in wording, it is proper after allowing one claim to object to the other as being a substantial duplicate of the allowed claim. See MPEP § 608.01(m).
Claim Interpretation
The following is a quotation of 35 U.S.C. 112(f):
(f) Element in Claim for a Combination. – An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
The following is a quotation of pre-AIA 35 U.S.C. 112, sixth paragraph:
An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
The claims in this application are given their broadest reasonable interpretation using the plain meaning of the claim language in light of the specification as it would be understood by one of ordinary skill in the art. The broadest reasonable interpretation of a claim element (also commonly referred to as a claim limitation) is limited by the description in the specification when 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is invoked.
As explained in MPEP § 2181, subsection I, claim limitations that meet the following three-prong test will be interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph:
(A) the claim limitation uses the term “means” or “step” or a term used as a substitute for “means” that is a generic placeholder (also called a nonce term or a non-structural term having no specific structural meaning) for performing the claimed function;
(B) the term “means” or “step” or the generic placeholder is modified by functional language, typically, but not always linked by the transition word “for” (e.g., “means for”) or another linking word or phrase, such as “configured to” or “so that”; and
(C) the term “means” or “step” or the generic placeholder is not modified by sufficient structure, material, or acts for performing the claimed function.
Use of the word “means” (or “step”) in a claim with functional language creates a rebuttable presumption that the claim limitation is to be treated in accordance with 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is rebutted when the claim limitation recites sufficient structure, material, or acts to entirely perform the recited function.
Absence of the word “means” (or “step”) in a claim creates a rebuttable presumption that the claim limitation is not to be treated in accordance with 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is not interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is rebutted when the claim limitation recites function without reciting sufficient structure, material or acts to entirely perform the recited function.
Claim limitations in this application that use the word “means” (or “step”) are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, except as otherwise indicated in an Office action. Conversely, claim limitations in this application that do not use the word “means” (or “step”) are not being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, except as otherwise indicated in an Office action.
This application includes one or more claim limitations that do not use the word “means,” but are nonetheless being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, because the claim limitation(s) uses a generic placeholder that is coupled with functional language without reciting sufficient structure to perform the recited function and the generic placeholder is not preceded by a structural modifier. Such claim limitation(s) is/are: "computing system" and "machine learning system" in Claim 11.
Because this/these claim limitation(s) is/are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, it/they is/are being interpreted to cover the corresponding structure described in the specification as performing the claimed function, and equivalents thereof (e.g., computer 101 in the computing environment 100 described in ¶¶ [0017]-[0026] with FIG. 1).
If applicant does not intend to have this/these limitation(s) interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, applicant may: (1) amend the claim limitation(s) to avoid it/them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph (e.g., by reciting sufficient structure to perform the claimed function); or (2) present a sufficient showing that the claim limitation(s) recite(s) sufficient structure to perform the claimed function so as to avoid it/them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph.
Claim Rejections - 35 USC § 112
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
The following is a quotation of 35 U.S.C. 112 (pre-AIA ), second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
Claims 1-20 are rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor (or for applications subject to pre-AIA 35 U.S.C. 112, the applicant), regards as the invention.
Claims 1 and 11 recite the limitation "… solving a contextual bandit problem having a trending reward function … identifying/identify a contextual bandit (MAB) problem having multiple arms and a known trend …" in lines 1-4 and 2-5 respectively, which rendering these claims indefinite because it is unclear whether two instances of "contextual bandit problem" are the same or different. Clarification is required.
Claims 1, 11, and 20 recite the limitation "the primary arm" in lines 14-15, 15-16, and 15-16 respectively. There is insufficient antecedent basis for this limitation in the claim. For examination purposes, "the preferred arm" is considered.
Claims 2-10 and 12-19 are rejected for fully incorporating the deficiency of their respective base claims.
Claims 4 and 14 recite the limitation "wherein the reward is responsive to …" in line 1, which rendering these claims indefinite because "… wherein the primary arm has the best reward during the predetermined time period …" and "… receiving a non-stationary reward responsive to selecting an arm …" are also recited in their respective based claim, and it is unclear which instance of "reward" ("best reward" or "non-stationary reward" recited in their respective based claim) is referred by "the reward" recited here (see also Claim Objections to Claims 1, 3, 11, and 13 as well as 112 Rejections to Claims 1 and 11). Clarification is required.
Claims 7 and 17 recite the limitation "... measuring the policy relative to a predetermined number of plays and an expected regret at the predetermined time, wherein the predetermined time is a time horizon and an expected regret after the predetermined number of plays is responsive to an optimal gain expectation and an expected gain obtained by the policy" in lines 1-5, which rendering these claims indefinite because it is unclear whether two instances of "expected regret" are the same or different (see also Claim Objections to Claims 7 and 17). Clarification is required.
Claim 11 recites the limitation "A computing system, comprising: a machine learning system for implementing a method for solving … the system configured to ..." in lines 1-3, which rendering the claim indefinite because it is unclear which instance of "system" ("computing system " or "machine learning system ") is referred by "the system". For examination purposes, "A computing system, comprising: a machine learning system for implementing a method for solving … the computing system configured to ..." is considered.
Claims 12-17 are rejected for fully incorporating the deficiency of their respective base claims.
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 1-20 are rejected under 35 U.S.C. 101 because the claimed invention is directed to abstract idea without significantly more.
Independent Claims 1, 11, and 20
Step 1: Claim 1 is a process claim, Claim 11 is a system claim, and Claim 20 is a claim for a computer readable storage medium (excluding transitory signal per se. in ¶¶ [0016] and [0057]). These claims fall within at least one of the four categories of patent eligible subject matter.
Step 2A Prong 1: The claim(s) recite(s) "solving a contextual bandit problem having a trending reward function" (Claims 1 and 11), "identifying/identify a contextual bandit (MAB) problem having multiple arms and a known trend, wherein the shape of a reward function for each of the multiple arms is known, and wherein a distribution of the reward function is unknown", "implementing/implement a Linear Upper Confidence Bound Contextual Bandit (ALINUCB) algorithm to take advantage of the shape of the reward function", "causing/cause each of the multiple arms to be independently drawn responsive to a sequence during a predetermined time period", "identifying/identify a preferred arm from the multiple arms, wherein the primary arm has the best reward during the predetermined time period"; "engaging/engage the preferred arm during the predetermined time period"; "detecting/detect the expiration of the predetermined time period"; and "testing/test each of the multiple arms for a subsequent predetermined time period" which can be reasonably considered as mental processes (i.e., which "can be performed in the human mind, or by a human using a pen and paper") or mathematical concepts/calculations/algorithms.
Step 2A Prong 2: This judicial exception is not integrated into a practical application because the claim(s) recite(s) additional elements/limitations of "an agent", "a computing system" (Claim 11), "a machine learning system" (Claim 11), "a computer readable storage medium" (Claim 20), and "a processor" (Claim 20) which only amount to "apply it" with the use of generic computer components or insignificant extra solution activity. None of the additional elements/limitations, taken alone or in combination, integrate the abstract idea into a practical application.
Step 2B: The claim(s) does/do not include additional elements that are sufficient to amount to significantly more than the judicial exception because the additional limitation/element of "machine learning" (Claim 11) is well-understood, routine and conventional (WURC) activity similar to "performing repetitive calculation" (see MPEP 2106.05(d), "Performing repetitive calculations, Flook, 437 U.S. at 594, 198 USPQ2d at 199 (recomputing or readjusting alarm limit values)"). Thus, none of the additional limitations, taken either alone or combined, amount to significantly more than the abstract idea.
Claims 2 and 12
Step 1: Claim 2 is a process claim and Claim 12 is a system claim. These claims fall within at least one of the four categories of patent eligible subject matter.
Step 2A Prong 1: The claim(s) further recite(s) .
Step 2A Prong 2: This judicial exception is not integrated into a practical application because the claim(s) does/do not further recite(s) additional elements/limitations.
Step 2B: The claim(s) does/do not further include additional elements that are sufficient to amount to significantly more than the judicial exception. Thus, none of the additional limitations, taken either alone or combined, amount to significantly more than the abstract idea.
Claims 3 and 13
Step 1: Claim 3 is a process claim and Claim 13 is a system claim. These claims fall within at least one of the four categories of patent eligible subject matter.
Step 2A Prong 1: The claim(s) further recite(s) .
Step 2A Prong 2: This judicial exception is not integrated into a practical application because the claim(s) does/do not further recite(s) additional elements/limitations.
Step 2B: The claim(s) does/do not further include additional elements that are sufficient to amount to significantly more than the judicial exception. Thus, none of the additional limitations, taken either alone or combined, amount to significantly more than the abstract idea.
Claims 4 and 14
Step 1: Claim 4 is a process claim and Claim 14 is a system claim. These claims fall within at least one of the four categories of patent eligible subject matter.
Step 2A Prong 1: The claim(s) further recite(s) .
Step 2A Prong 2: This judicial exception is not integrated into a practical application because the claim(s) does/do not further recite(s) additional elements/limitations.
Step 2B: The claim(s) does/do not further include additional elements that are sufficient to amount to significantly more than the judicial exception. Thus, none of the additional limitations, taken either alone or combined, amount to significantly more than the abstract idea.
Claims 5 and 15
Step 1: Claim 5 is a process claim and Claim 15 is a system claim. These claims fall within at least one of the four categories of patent eligible subject matter.
Step 2A Prong 1: The claim(s) further recite(s) .
Step 2A Prong 2: This judicial exception is not integrated into a practical application because the claim(s) does/do not further recite(s) additional elements/limitations.
Step 2B: The claim(s) does/do not further include additional elements that are sufficient to amount to significantly more than the judicial exception. Thus, none of the additional limitations, taken either alone or combined, amount to significantly more than the abstract idea.
Claims 6 and 16
Step 1: Claim 6 is a process claim and Claim 16 is a system claim. These claims fall within at least one of the four categories of patent eligible subject matter.
Step 2A Prong 1: The claim(s) further recite(s) .
Step 2A Prong 2: This judicial exception is not integrated into a practical application because the claim(s) does/do not further recite(s) additional elements/limitations.
Step 2B: The claim(s) does/do not further include additional elements that are sufficient to amount to significantly more than the judicial exception. Thus, none of the additional limitations, taken either alone or combined, amount to significantly more than the abstract idea.
Claims 7 and 17
Step 1: Claim 7 is a process claim and Claim 17 is a system claim. These claims fall within at least one of the four categories of patent eligible subject matter.
Step 2A Prong 1: The claim(s) further recite(s) .
Step 2A Prong 2: This judicial exception is not integrated into a practical application because the claim(s) does/do not further recite(s) additional elements/limitations.
Step 2B: The claim(s) does/do not further include additional elements that are sufficient to amount to significantly more than the judicial exception. Thus, none of the additional limitations, taken either alone or combined, amount to significantly more than the abstract idea.
Claims 8 and 18
Step 1: Claim 8 is a process claim and Claim 18 is a system claim (see also Claim objections to Claim 18). These claims fall within at least one of the four categories of patent eligible subject matter.
Step 2A Prong 1: The claim(s) further recite(s) .
Step 2A Prong 2: This judicial exception is not integrated into a practical application because the claim(s) does/do not further recite(s) additional elements/limitations.
Step 2B: The claim(s) does/do not further include additional elements that are sufficient to amount to significantly more than the judicial exception. Thus, none of the additional limitations, taken either alone or combined, amount to significantly more than the abstract idea.
Claims 9 and 19
Step 1: Claim 9 is a process claim and Claim 19 is a system claim (see also Claim objections to Claim 19). These claims fall within at least one of the four categories of patent eligible subject matter.
Step 2A Prong 1: The claim(s) further recite(s) .
Step 2A Prong 2: This judicial exception is not integrated into a practical application because the claim(s) does/do not further recite(s) additional elements/limitations.
Step 2B: The claim(s) does/do not further include additional elements that are sufficient to amount to significantly more than the judicial exception. Thus, none of the additional limitations, taken either alone or combined, amount to significantly more than the abstract idea.
Claim 10
Step 1: Claim 10 is a process claim which falls within at least one of the four categories of patent eligible subject matter.
Step 2A Prong 1: The claim(s) further recite(s) .
Step 2A Prong 2: This judicial exception is not integrated into a practical application because the claim(s) does/do not further recite(s) additional elements/limitations.
Step 2B: The claim(s) does/do not further include additional elements that are sufficient to amount to significantly more than the judicial exception. Thus, none of the additional limitations, taken either alone or combined, amount to significantly more than the abstract idea.
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claims 1-20 are rejected under 35 U.S.C. 103 as being unpatentable over Bouneffouf ("Finite-time analysis of the multi-armed bandit problem with known trend", 2016 IEEE Congress on Evolutionary Computation (CEC), Jul 24-29, 2016, pp. 2543-2549), hereinafter Bouneffouf'2016 or Bouneffouf et al. ("Multi-armed Bandit Problem with Known Trend", arXiv:1508.07091v4, May 10, 2017, pp. 1-6), hereinafter Bouneffouf'2017 in view of Huang ("Linear Upper Confidence Bound Algorithm for Contextual Bandit Problem with Piled Rewards", Advances in Knowledge Discovery and Data Mining, 20th Pacific-Asia Conference, PAKDD 2016 Auckland, New Zealand, April 19–22, 2016 Proceedings, Part II, in LNAI 9652, pp. 143-145), hereinafter Huang.
Independent Claims 1, 11, and 20
Bouneffouf'2016 or Bouneffouf'2017 discloses a method for solving a contextual bandit problem having a trending reward function, the method comprising: identifying a contextual bandit (MAB) problem having multiple arms and a known trend, wherein the shape of a reward function for each of the multiple arms is known by an agent, and wherein a distribution of the reward function is unknown by the agent; and implementing a (Bouneffouf'2016, Abstract of Page 2543: study here an a problem called "the multiarmed bandit problem with known trend", where an agent knows the shape of the reward function of each arm but not its distribution; this problem is motivated by different real world tasks, where when an arm is sampled by the model the received reward change according to a known trend; by adapting the standard multi-armed bandit algorithms, propose to study the regret upper bounds of three algorithms: the two first one assumes a stochastic model; and the last one is based on a Bayesian approach; Section I of Page 2543: the study of the online learning problem and specifically the Multi-Armed Bandit (MAB) problem, which are interesting model that can match almost all existing overload information problems [2], [3], [4]; the MAB can be described as problem where at each step, an agent looking for rewards has to choose between K arms, each having a fixed, unknown and independent probability distribution of reward; this reward is drawn according to the selected arm’s distribution and it is independent of previous actions; study here a special case of this model where the rewards of each arm of the bandit follow a known function; knowing the shape of the reward function assumption is realistic for several real-world problems like on-line active learning [5], A/B testing [7] and music recommendation [6]; in this setting, propose to study this new model derived from this problem, by adapting the existing algorithm to the new setting and analyzing their regret; Section II of Page 2543-2544: in the bandit problem, each arm delivers rewards that are independently drawn from an unknown distribution; [15], [16] studied the restless bandits, where the states of all arms can change in each step according to a stochastic transition function; [17] study specific classes of drifting restless bandits selected for their relevance to modelling an online website optimization process; the contribution was a feasible weighted least squares technique capable of utilizing contextual arm parameters while considering the parameter space drifting nonstationary within reasonable bounds; Section III.A with Algorithm 1 of Page 2546: to adapt the UCB algorithm for the news setting, the proposed A-UCB algorithm (Algorithm 1) computes at each trial t an index
I
i
=
μ
^
i
+
c
i
∙
D
n
i
t
for each arm i, where c(i) is the corresponding confidence interval, so that
c
i
=
2
×
l
o
g
t
n
i
t
; for the bandit problem with known trend, the accumulated expected regret R of A-UCB policy is bounded by Theorem 4; Section IV of Pages 2548-2549: study here the "MAB problem with known trend" a formulation of the MAB problem motivated by the real world problem of active learning, music and interface recommendation; in this setting the set of strategies available to a MAB algorithm changes rapidly over time; provide an extension that allows UCB, AE and TS algorithms to be used in the case of MAB problem with known trend; REFERENCES of Page 2549: "Contextual bandits for context-based information retrieval” for Ref. [3]; "Contextual bandit for active learning: Active Thompson sampling” for Ref. [5]) or (Bouneffouf'2017, Abstract of Page 1: consider a variant of the multi-armed bandit model, which we call multi-armed bandit problem with known trend, where the gambler knows the shape of the reward function of each arm but not its distribution; this new problem is motivated by different on-line problems like active learning, music and interface recommendation applications, where when an arm is sampled by the model the received reward change according to a known trend; by adapting the standard multi-armed bandit algorithm UCB1 to take advantage of this setting, propose the new algorithm named Adjusted Upper Confidence Bound (A-UCB) that assumes a stochastic model; provide upper bounds of the regret which compare favorably with the ones of UCB1; also confirm that experimentally with different simulations; Section I of Page 1: the basic formulation of the Multi-Armed Bandit (MAB) problem can be described as follows: there are K arms, each having a fixed, unknown and independent probability-distribution of reward; at each step, a player chooses an arm and receives a reward; this reward is drawn according to the selected arm’s distribution and it is independent of previous actions; study here a special case of this model where the rewards of each arm of the bandit follow a known function; the real motivation is operational: knowing the shape of the reward function assumption is realistic for several real-world problems like on-line active learning, A/B testing and music recommendation; all these problems can be modeled as new bandit problem called “Multiarmed Bandit Problem with Known Trend” where each arm follow a known trend reward function; propose to study this new model derived from this problem, by adapting the existing algorithm to the new setting and analyzing their regret; evaluate the proposed algorithms through different simulations; Section II of Pages 1-2: in the bandit problem, each arm delivers rewards that are independently drawn from an unknown distribution; our work is an adaptation of these classes of policies for MAB Problem with known trend reward function; [10], [11] studied the restless bandits, where the states of all arms can change in each step according to an arbitrary stochastic transition function; [13] study specific classes of drifting restless bandits selected for their relevance to modelling an online website optimization process; the contribution was a feasible weighted least squares technique capable of utilizing contextual arm parameters while considering the parameter space drifting nonstationary within reasonable bounds; our new model can be considered an extension of the work done in [14], [15], the main difference is in the fact that, in our case the reward function of each arm can follow any function not specially a decreasing function; our model can also be a specification of the general model of restless bandits with a known shape of the reward function; Section III.A with Algorithm 1 of Page 2-3: to adapt the UCB algorithm for the news setting, the proposed A-UCB algorithm (Algorithm 1) computes at each trial t an index
I
i
=
μ
^
i
+
c
i
∙
D
n
i
t
for each arm i, where c(i) is the corresponding confidence interval, so that
c
i
=
2
×
l
o
g
t
n
i
t
; for the bandit problem with known trend, the accumulated expected regret R of A-UCB policy is bounded by Theorem 1; Section V of Pag 5: introduce a new formulation of the MAB problem motivated by the real world problem of active learning, music and interface recommendation; in this setting the set of strategies available to a MAB algorithm changes rapidly over time; provide an extension that allows UCB algorithm to be used in the case of MAB problem with known trend; further, provide an upper bound of regret of the proposed algorithm);
identifying a preferred arm from the multiple arms, wherein the primary arm has the best reward during the predetermined time period; engaging the preferred arm during the predetermined time period; detecting the expiration of the predetermined time period; and testing each of the multiple arms for a subsequent predetermined time period (Bouneffouf'2016, Section II of Page 2543-2544: compute an index for each arm and they choose the arm with the highest index; our work is most related to the study of dynamic versions of the MAB where either the set of arms or their expected reward may change over time; a solution to cope with nonstationary is to drop the stochastic reward assumption and assume the reward sequences to be chosen by an adversary; [12] considers the situation where the distributions of rewards remain constant over epochs and change at unknown time instants; they analyze two algorithms: the discounted UCB and the sliding-window UCB and they establish for these two algorithms an upper-bound for the expected regret by upper-bounding the expectation of the number of times a suboptimal arm is played; they establish a lower-bound for the regret in presence of abrupt changes in the arms reward distributions; [13] develop algorithms for a variety of cases with constant switching rate: when switching occurs all arms change (Global Switching), switching occurs independently for each arm (Per-Arm Switching); [14] proposed a policy where only the state of the arm currently selected can change in a given step, and proved its optimality for time discounting; another line of work studies the non-stationary reward of arms by considering that each arm has a finite lifetime; in this mortal bandits setting, each disappearing arm changes the set of available arms; in their model they study the mixture-of-experts paradigm, where a set of experts is specified in each time period; the goal of the algorithm is to choose one expert in each time period to minimize regret against the best mixture of experts; Section III with FIGS. 1-2 and Algorithms 1-3 of Pages 2544-2548: in the MAB setting, to maximize his gain the player has to find the best arm as soon as possible, and then exploit it; in our setting, the rewards follow a known function; when the player has found the best arm, he knows that this arm will be the best just for a certain period of time; the player needs to re-explore at each time to find the next best arm; let ri(1), …, ri(n) be a sequence of independent draws of the random variable ri ∈ [0, 1] with n the number of trials and let μi = E[ri] be its mean reward; at each time t, the player chooses an arm i ∈ {1, …, K} to play according to a (deterministic or random) policy φ based on sequence of plays and reward, and obtains a non-stationary reward z(t) where
z
t
=
r
i
t
(
t
)
∙
D
(
n
i
t
(
t
)
)
, where
D
(
n
i
t
(
t
)
is a trend reward function assumed to be known,
n
i
t
(
t
)
is the number of times i is played and
r
i
t
(
t
)
is the stationary reward for arm i at time t; a dynamic policy can be defined as function such that (φ : t
↦
n1(t), …, nK(t)) or φ : Ht−1
↦
K, where Ht−1 is the history of rewards known at time t; by applying a policy φ, at t a sequence of choices obtained (1, 2, …, t) ∈ [K]t; at time t, the gain of the policy φ is:
G
φ
t
=
∑
t
z
t
=
∑
t
r
i
t
t
D
n
i
t
t
; the performance of a policy φ is measured in terms of regret in the first T plays, which is defined as the expected difference between the total rewards collected by the optimal policy φ∗ (playing at each time instant the arm i∗ with the highest expected reward) and the total rewards collected by the policy φ; the objective is to minimize the regret R(T) at time T, where T is the time horizon; the expected regret after T plays is defined in Definition 1 as the difference between the optimal gain expectation and the expected gain got by the policy φ; note that we distribute the expectation because
r
i
t
(
t
)
and
n
i
t
(
t
)
are independent; the optimal policy in any time φ∗ consists in always playing the arm i∗ ∈ {1. …, K} with largest expected reward:
i
*
=
a
r
g
m
a
x
i
μ
i
∙
D
n
i
t
, where μi is the expectation of the reward
r
i
(
t
)
; F is the cumulative function of D(s) and is expressed as in Definition 3, notice that in the demonstration of the theorem 4, F is assumed to be Lipschitz; Theorem 1: the optimal policy in any time π∗ consists in always playing the arm i∗ ∈ {1, …, K} with largest expected reward:
i
*
=
a
r
g
m
a
x
1
≤
K
μ
i
∙
D
n
i
t
, where μi is the expectation of the reward
r
i
(
t
)
; demonstrate in lemma 1 that an optimal policy π cannot attend the optimal at t+1 if it is not optimal at time t and which means that the optimal policy has to select at each time the optimal arm; Theorem 2: for the bandit problem with known trend, the accumulated expected regret R for any policy φ and any horizon T is lower bounded by
1
m
a
x
i
μ
i
D
m
a
x
∑
i
:
n
i
T
>
n
i
*
T
E
n
i
T
-
n
i
*
T
≤
E
R
T
; to adapt the UCB algorithm for the news setting, the proposed A-UCB algorithm (Algorithm 1) computes at each trial t an index
I
i
=
μ
^
i
+
c
i
∙
D
n
i
t
for each arm i, where c(i) is the corresponding confidence interval, so that
c
i
=
2
×
l
o
g
t
n
i
t
; the UCB index is multiplied by
D
n
i
t
to stop playing the supposed optimal arm when its rewards become suboptimal.; for the bandit problem with known trend, the accumulated expected regret R of A-UCB policy is bounded by
E
R
T
≤
m
a
x
i
μ
i
D
m
a
x
∑
i
:
n
i
*
T
>
n
i
T
8
l
n
T
∆
'
i
2
+
K
π
2
3
, where
∆
i
'
=
D
m
i
n
D
m
a
x
μ
i
t
*
-
μ
i
t
with Dmin and Dmax two Lipschitz constants; the Action elimination (AE) algorithm attempts to sample each arm a minimal number of times and eliminate the arms one after the other; however in our case a sub optimal arm at time t can be optimal arm at time t+1 and applying AE can eliminate the future optimal arms; to adapt the AE algorithm to our setting, the proposed A-AE (Alg. 2) algorithm compute the
μ
^
m
a
x
∙
D
n
i
T
-
μ
^
i
∙
D
n
i
T
rather than
μ
^
m
a
x
-
μ
^
i
for the arm elimination; for the bandit problem with known trend, the accumulated expected regret R of A-AE policy is bounded by
∑
t
=
1
T
r
e
g
r
e
t
t
≤
∑
i
=
2
n
l
o
g
T
δ
∆
i
'
∆
i
'
with
∆
'
=
D
m
a
x
D
m
i
n
μ
^
i
*
-
μ
^
i
; using Beta prior and considering the Bernoulli bandit problem (the rewards are either 0 or 1), Thompson Sampling (TS) initially assumes arm i to have prior Beta(1, 1) on μi (the probability of success); at time t, having observed Si(t) successes (reward = 1) and Fi(t) failures (reward = 0) in θi(t) = Si(t) + Fi(t) selects of document i, the algorithm updates the distribution on μi as Beta(Si(t)+1, Fi(t)+1); the algorithm then generates independent samples from these posterior distributions of the μi, and selects the document with the largest sample value μi; to adapt the TS sampling for our setting, propose A-TS (Algorithm 3), this algorithm multiply θi(t) by D(ni(t)) to stop playing the supposed optimal arm when its rewards start to decrease; for the bandit problem with known trend, the total regret in time T for A-TS is bounded by
E
R
T
≤
1
∆
i
'
-
ϵ
2
l
g
1
T
+
8
l
n
T
∆
'
i
2
+
1
+
π
2
3
+
O
(
1
)
) or (Bouneffouf'2017, Section I of Page 1: the nonstationary bandit problem where the player must decide which arm to play while facing the possibility of a changing environment; Section II of Pages 1-2: compute an index for each arm and they choose the arm with the highest index; our work is most related to the study of dynamic versions of the MAB where either the set of arms or their expected reward may change over time; a solution to cope with nonstationary is to drop the stochastic reward assumption and assume the reward sequences to be chosen by an adversary; [7] considers the situation where the distributions of rewards remain constant over epochs and change at unknown time instants; they analyze two algorithms: the discounted UCB and the sliding-window UCB and they establish for these two algorithms an upper-bound for the expected regret by upper-bounding the expectation of the number of times a suboptimal arm is played; they establish a lower-bound for the regret in presence of abrupt changes in the arms reward distributions; [8] propose a Thompson Sampling strategy equipped with a Bayesian change point mechanism to tackle this problem; they develop algorithms for a variety of cases with constant switching rate: when switching occurs all arms change (Global Switching), switching occurs independently for each arm (Per-Arm Switching), when the switching rate is known and when it must be inferred from data; [9] proposed a policy where only the state of the arm currently selected can change in a given step, and proved its optimality for time discounting; to deal with the partial information nature of the bandit problem, in Adapt-Eve [12] the mean reward of the estimated best arm is monitored; the drawback of this approach is that it does not tackle the case of a suboptimal arm becoming the best arm; another line of work studies the non-stationary reward of arms by considering that each arm has a finite lifetime; in this mortal bandits setting, each disappearing arm changes the set of available arms; in their model they study the mixture-of-experts paradigm, where a set of experts is specified in each time period; the goal of the algorithm is to choose one expert in each time period to minimize regret against the best mixture of experts; Section III of Pages 2-4: in the MAB setting, to maximize his gain the player has to find the best arm as soon as possible, and then exploit it; in our setting, the rewards follow a known function; when the player has found the best arm, he knows that this arm will be the best just for a certain period of time; the player needs to re-explore at each time to find the next best arm; in the MAB setting, to maximize his gain the player has to find the best arm as soon as possible, and then exploit it; in our setting, the rewards follow a known function; when the player has found the best arm, he knows that this arm will be the best just for a certain period of time; the player needs to re-explore at each time to find the next best arm; let ri(1), …, ri(n) be a sequence of independent draws of the random variable ri ∈ [0, 1] with n the number of trials and let μi = E[ri] be its mean reward; at each time t, the player chooses an arm i ∈ {1, …, K} to play according to a (deterministic or random) policy φ based on sequence of plays and reward, and obtains a non-stationary reward z(t) where
z
t
=
r
i
t
(
t
)
∙
D
(
n
i
t
(
t
)
)
, where
D
(
n
i
t
(
t
)
is a trend reward function assumed to be known,
n
i
t
(
t
)
is the number of times i is played and
r
i
t
(
t
)
is the stationary reward for arm i at time t; a dynamic policy can be defined as function such that (φ : t
↦
n1(t), …, nK(t)) or φ : Ht−1
↦
K, where Ht−1 is the history of rewards known at time t; by applying a policy φ, at t a sequence of choices obtained (1, 2, …, t) ∈ [K]t; at time t, the gain of the policy φ is:
G
φ
t
=
∑
t
z
t
=
∑
t
r
i
t
t
D
n
i
t
t
; the performance of a policy φ is measured in terms of regret in the first T plays, which is defined as the expected difference between the total rewards collected by the optimal policy φ∗ (playing at each time instant the arm i∗ with the highest expected reward) and the total rewards collected by the policy φ; the objective is to minimize the regret R(T) at time T, where T is the time horizon; the expected regret after T plays is defined in Definition 1 as the difference between the optimal gain expectation and the expected gain got by the policy φ; note that we distribute the expectation because
r
i
t
(
t
)
and
n
i
t
(
t
)
are independent; the optimal policy in any time φ∗ consists in always playing the arm i∗ ∈ {1. …, K} with largest expected reward:
i
*
=
a
r
g
m
a
x
i
μ
i
∙
D
n
i
t
, where μi is the expectation of the reward
r
i
(
t
)
; F is the cumulative function of D(s) and is expressed as in Definition 3, notice that in the demonstration of the theorem 1, F is assumed to be Lipschitz; to adapt the UCB algorithm for the news setting, the proposed A-UCB algorithm computes at each trial t an index
I
i
=
μ
^
i
+
c
i
∙
D
n
i
t
for each arm i, where c(i) is the corresponding confidence interval, so that
c
i
=
2
×
l
o
g
t
n
i
t
; The UCB index is multiplied by
D
n
i
t
to stop playing the supposed optimal arm when its rewards become suboptimal.; the A-UCB algorithm is shown in Algorithm 1; for the bandit problem with known trend, the accumulated expected regret R of A-UCB policy is bounded by
E
R
T
≤
m
a
x
i
μ
i
D
m
a
x
∑
i
:
n
i
*
T
>
n
i
T
8
l
n
T
∆
'
i
2
+
K
π
2
3
, where
∆
i
'
=
D
m
i
n
D
m
a
x
μ
i
t
*
-
μ
i
t
with Dmin and Dmax two Lipschitz constants; Section IV of Page 5 with FIGS, 1-3 of Page 6: in order to illustrate the strengths and weaknesses of A-UCB in comparison to the state-of-the-art, three synthetic known trend bandit problems are formulated with three reward functions, decreasing reward function (Figure 1), sigmoid reward function (Figure 2) and Gaussian reward function (Figure 3); in these three problems, we have generated a non-stationary arms based on a known shape of the reward function using 8 arms and we have fixed their mean reward as follows: μ1 = 0:6, μ2 = 0:4, μ3 = 0:3, μ4 = 0:3, μ5 = 0:15, μ6 = 0:1, μ7 = 0:05, μ8 = 0:05, where n [Symbol font/0xCE] [0; 4000], D(n) = –6.65ln(n) + 9:57 for Figure 1, D(n) = 0:037exp(1:15n) for Figure 2, and D(n) = exp(–(n–20)2/40) for Figure 3;iIn this simulation, at each round, if the algorithm chooses the right arm the reward is 1 or else 0; the accumulated rewards are computed each 1000 iteration; the plot of the curves (Figure 1, 2, 3) are produced by averaging 20 runs of each algorithm; we run the simulation for 32000 iterations; the first problem (Figure 1), shows a decreasing reward function, this kind of model can be seen in different real world problem of recommendation system like music or ads recommendation; on this problem, A-UCB quickly outperforms the other algorithms, which is due to the fact that at each iteration the algorithm is aware about the reward function of each arm, this allows it to find the optimal arms at the optimal time; in the second problem (Figure 2), sigmoid reward function, this kind of model can be seen in different real world problem of recommendation system like interface recommendation; on this problem, A-UCB still outperforms other algorithms and this performance is explained by the rapidity of the A-UCB to find the greatest trade-off between arms; in the third problem (Figure 3), the Gaussian reward function can model the reward function of games or clothes recommendation).
Bouneffouf'2016 or Bouneffouf'2017 further discloses a computing system, comprising: a machine learning system for implementing a method described above (Bouneffouf'2016, Section I of Page 2543: the study of the online learning problem; study here a special case of this model where the rewards of each arm of the bandit follow a known function. Knowing the shape of the reward function assumption is realistic for several real-world problems like on-line active learning [5], A/B testing [7] and music recommendation [6]; Section IV of Pages 2548-2549: study here the "MAB problem with known trend" a formulation of the MAB problem motivated by the real world problem of active learning, music and interface recommendation; i.e., inherited in a system for performing online active learning problem) or (Bouneffouf'2017, Abstract of Page 1: this new problem is motivated by different on-line problems like active learning, music and interface recommendation applications; Section I of Page 1: knowing the shape of the reward function assumption is realistic for several real-world problems like on-line active learning, A/B testing and music recommendation; e.g., in [1], the analysis of the active learning problem led the authors to model the active learning problem as a MAB problem; Section V of Page 5: introduce a new formulation of the MAB problem motivated by the real world problem of active learning, music and interface recommendation; i.e., inherited in a system for performing online active learning problem).
Bouneffouf'2016 or Bouneffouf'2017 also discloses a computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a processor to cause the processor to perform operations described above (Bouneffouf'2016, Section I of Page 2543: the study of the online learning problem; study here a special case of this model where the rewards of each arm of the bandit follow a known function. Knowing the shape of the reward function assumption is realistic for several real-world problems like on-line active learning [5], A/B testing [7] and music recommendation [6]; Section IV of Pages 2548-2549: study here the "MAB problem with known trend" a formulation of the MAB problem motivated by the real world problem of active learning, music and interface recommendation; i.e., inherited in a system for performing online active learning problem) or (Bouneffouf'2017, Abstract of Page 1: this new problem is motivated by different on-line problems like active learning, music and interface recommendation applications; Section I of Page 1: knowing the shape of the reward function assumption is realistic for several real-world problems like on-line active learning, A/B testing and music recommendation; e.g., in [1], the analysis of the active learning problem led the authors to model the active learning problem as a MAB problem; Section V of Page 5: introduce a new formulation of the MAB problem motivated by the real world problem of active learning, music and interface recommendation; i.e., inherited in a system for performing online active learning problem).
Bouneffouf'2016 or Bouneffouf'2017 fails to explicitly disclose wherein an Adjusted Upper Confidence Bound Contextual Bandit (A-UCB) algorithm include a Linear Upper Confidence Bound Contextual Bandit (ALINUCB) algorithm.
Huang teaches a system and a method relating to contextual bandit problem (Huang, Abstract of Page 143), wherein an Adjusted Upper Confidence Bound Contextual Bandit (A-UCB) algorithm include a Linear Upper Confidence Bound Contextual Bandit (ALINUCB) algorithm (Huang, Abstract of Page 143: study the contextual bandit problem with linear payoff function; in the traditional contextual bandit problem, the algorithm iteratively chooses an action/arm based on the observed context, and immediately receives a reward for the chosen action/arm; motivated by a practical need in many applications, study the design of algorithms under the piled-reward setting, where the rewards are received as a pile instead of immediately; present how the Linear Upper Confidence Bound (Lin-UCB) algorithm for the traditional problem can be naïvely applied under the piled-reward setting, and prove its regret bound; then, extend LinUCB to a novel algorithm, called Linear Upper Confidence Bound with Pseudo Reward (LinUCBPR), which digests the observed contexts to choose actions/arms more strategically before the piled rewards are received; prove that LinUCBPR can match LinUCB in the regret bound under the piled-reward setting; experiments on the artificial and real-world datasets demonstrate the strong performance of LinUCBPR in practice; Section 1 of Pages 143-144: study the contextual bandit problem (CBP) [13], which is an interactive process between an algorithm and an environment; in the traditional CBP, the algorithm observes a context from the environment in each time step; then, the algorithm is asked to strategically choose an action/arm from the action/arm set based on the context, and receives a corresponding feedback, called reward, while the reward for other actions/arms are hidden from the algorithm; the goal of the algorithm is to maximize the cumulative reward over all time steps; because only the reward of the chosen action/arm is revealed, the algorithm needs to choose different actions/arms to estimate their goodness, called exploration; on the other hand, the algorithm also needs to choose the better actions/arms to maximize the reward, called exploitation; balancing between exploration and exploitation is arguably the most important issue for designing algorithms of CBP; ϵ-Greedy [3] and Linear Upper Confidence Bound (LinUCB) [10] are two representative algorithms for CBP; ϵ-Greedy learns one model per action/arm for exploitation and randomly explores different actions/arms with a small probability ϵ; LinUCB is based on online ridge regression, and takes the concept of upper-confidence bound [2,5] to strategically balance between exploration and exploitation; LinUCB enjoys a strong theoretical guarantee [5] and is state-of-the-art in many practical applications [10]; the traditional CBP setting assumes that the algorithm receives the reward immediately after choosing an action/arm; to reduce the cost of communication, the ad exchange often does not reveal the individual reward immediately after choosing an action; instead, the ad exchange stores the individual reward first, and only sends a pile of rewards back to the system until sufficient number of rewards are gathered; call the scenario as the contextual bandit problem under the piled-reward setting; a related setting in the literature is the delayed-reward setting, where the reward is assumed to come at several time steps after the algorithm chooses an action; study how LinUCB can be applied under the piled-reward setting; present a naïve use of LinUCB for the setting and prove its theoretical guarantee in the form of the regret bound; the result helps us understand the difference between the traditional setting and the piled-reward setting; then, design a novel algorithm, Linear Upper Confidence Bound with Pseudo Reward (LinUCBPR), which is a variant of LinUCB that allows more strategic use of the context information before the piled rewards are received; prove that LinUCBPR can match the naïve LinUCB in its regret bound under the piled-reward setting; Section 2 of Pages 145-146: introduce the CBP under the piled-reward setting. Instead of receiving the reward right after choosing an action (and thus right before observing the next context), the setting assumes that the rewards come as a pile after observing multiple contexts in a round; the goal of the algorithm is to maximize the cumulative reward
∑
t
=
1
T
∑
i
=
1
n
r
t
i
,
a
t
i
after T rounds; the piled-reward setting assumes that the context comes at time steps {11, 12, …, 1n, 21, 22, …, t1, t2, …, Tn−1, Tn}, while the rewards come after every n contexts as a pile; note that the traditional setting is a special case of the piled-reward setting when n = 1; consider the CBP with linear payoff function; assume that
r
t
i
,
a
connects with
x
t
i
linearly through K hidden weight vectors u1, u2, …, uK ∈
R
d
with
u
i
2
≤
1
; that is,
Ε
r
t
i
,
a
|
x
t
i
=
x
t
i
T
u
a
; let
a
t
i
*
=
arg
m
a
x
a
∈
[
K
]
x
t
i
T
u
a
be the optimal action for
x
t
i
; define regret of an algorithm to be
∑
t
=
1
T
∑
i
=
1
n
r
t
i
,
a
t
i
*
-
∑
t
=
1
T
∑
i
=
1
n
r
t
i
,
a
t
i
; the goal of maximizing the cumulative reward is equivalent to minimizing the regret; Linear Upper Confidence Bound (LinUCB) [5] is a state-of-the-art algorithm for the traditional CBP (n = 1); LinUCB maintains K weight vectors
w
t
1
,
1
,
w
t
1
,
2
,
…
,
w
t
1
,
K
to estimate u1, u2, …, uK at time step t1; the K weight vectors are calculated by ridge regression as shown in Eqn. (1); let
A
t
1
,
a
=
I
d
+
X
(
t
-
1
)
1
,
a
T
X
(
t
-
1
)
1
,
a
and
b
t
1
,
a
=
X
(
t
-
1
)
1
,
a
T
X
(
t
-
1
)
1
,
a
; the solution to (1) is
w
t
1
,
a
=
A
t
1
,
a
-
1
b
t
1
,
a
; when a new context
x
t
1
comes, LinUCB calculates two terms for each action a: the estimated reward
r
~
t
1
,
a
=
x
t
1
T
w
t
1
,
a
and the uncertainty
c
t
1
,
a
=
x
t
1
T
A
t
1
,
a
-
1
x
t
1
, and chooses the action with the highest score
r
~
t
1
,
a
+
α
c
t
1
,
a
, where α is a trade-off parameter; after receiving the reward, LinUCB updates the weight vector
w
t
1
,
a
t
1
immediately, and uses the new weight vector to choose the action for the next context; LinUCB conducts exploration when the chosen action is of high uncertainty; after sufficient (context, action, reward) information is received,
r
~
t
1
,
a
shall be close the expected reward, and
c
t
1
,
a
will be smaller; then, LinUCB conducts exploitation with the learned weight vectors to choose the action with the highest expected reward; Section 3 with Algorithms 1-2 of Pages 146-148: extend LinUCB to a more general framework that utilizes the additional information within the contexts before the true rewards are received; since no rewards are received before the end of the current round t, the naïve LinUCB does not update the model during round t, and only takes the fixed
w
t
1
,
a
and
A
t
1
,
a
to calculate the estimated reward
r
~
t
1
,
a
and the uncertainty
c
t
1
,
a
for each action a; i.e., LinUCB only updates
w
t
1
,
a
before the beginning of round t as the solution to (1) with
X
(
t
-
1
)
1
,
a
,
r
(
t
-
1
)
1
,
a
under the traditional setting replaced by
X
(
t
-
1
)
n
,
a
,
r
(
t
-
1
)
n
,
a
under the piled-reward setting; in addition,
A
t
1
,
a
can be similarly defined from
X
(
t
-
1
)
n
,
a
instead; there is a possible drawback for the naïve LinUCB; if similar contexts come repeatedly in the same round, because
w
t
i
,
a
a and
A
t
i
,
a
stay unchanged within the round, LinUCB will choose similar actions repeatedly; then, if the chosen action suffers from low reward, LinUCB suffers from making the low-reward choice repeatedly before the end of the round; our idea is that the contexts
x
t
i
received during round t can be utilized to update the model before the rewards come; i.e., at time step ti, in addition to the labelled data (context, action, reward) gathered before time step (t−1)n that LinUCB uses, the unlabeled data (context, action) gathered at time steps {t1, t2, …, ti−1} can also be included to learn a more decent model; i.e., we hope to design some semi-supervised learning scheme within round t to guide the upper-confidence bound algorithm towards more strategic exploration within the round; the regret of LinUCB under the piled-reward setting is bounded by the summation of
c
t
i
,
a
over all time steps; but note that
c
t
i
,
a
only depends on
x
t
i
,
a
and
A
t
i
,
a
; i.e., upon receiving
x
t
i
and choosing an action
a
t
i
, the term
c
t
i
,
a
i
can readily be updated without the true reward; by updating
c
t
i
,
a
i
within the round, the algorithm can explore different actions strategically instead of following similar actions when similar contexts come repeatedly in the same round; propose to couple each context
x
t
1
,
x
t
2
,
…
,
x
t
i
-
1
with a pseudo reward
p
τ
,
a
τ
, where τ is the time step, before receiving the true reward
r
τ
,
a
τ
; the pseudo reward can then pretend to be the true reward and allow the algorithm to keep updating the model before the true rewards are received; note that pseudo rewards have been used to speed up exploration in the traditional CBP [4], and can encourage more strategic exploration in our framework; we name the framework Linear Upper Confidence Bound with Pseudo Reward (LinUCBPR); when receiving the true rewards in the end of round t, we discard the change from pseudo rewards, and use the true rewards to update model again; we show the framework of LinUCBPR in Algorithm 1; the only remained task is what
p
τ
,
a
should be; we will study two variants, one is to use
p
τ
,
a
=
r
~
τ
,
a
, the estimated reward of actions; we name the variant LinUCBPR with estimated reward (LinUCBPR-ER); another variant is to be even more aggressive, and set
p
τ
,
a
=
r
~
τ
,
a
-
β
c
τ
,
a
, a lower-confidence bound of the reward, where β is a trade-off parameter; the lower-confidence bound can be viewed as the underestimated reward, and should allow more exploration within the round, at the cost of more computation; we name the variant LinUCBPR with underestimated reward (LinUCBPR-UR)).
Bouneffouf'2016 or Bouneffouf'2017 and Huang are analogous art because they are from the same field of endeavor, a system and a method relating to contextual bandit problem. Therefore, it would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention to apply the teaching of Huang to Bouneffouf'2016 or Bouneffouf'2017. Motivation for doing so would provide a strong theoretical guarantee [5] and state-of-the-art in many practical applications [10] (Huang, 3rd .
Claims 2 and 12
Bouneffouf'2016 or Bouneffouf'2017 in view of Huang discloses all the elements as stated in Claims 1 and 11 respectively and further discloses wherein identifying the MAB problem includes the agent selecting the MAB problem, where each of the multiple arms includes a fixed, unknown and independent probability-law of reward (Bouneffouf'2016, Section I of Page 2543: the study of the online learning problem and specifically the Multi-Armed Bandit (MAB) problem, which are interesting model that can match almost all existing overload information problems [2], [3], [4]; the MAB can be described as problem where at each step, an agent looking for rewards has to choose between K arms, each having a fixed, unknown and independent probability distribution of reward; this reward is drawn according to the selected arm’s distribution and it is independent of previous actions; study here a special case of this model where the rewards of each arm of the bandit follow a known function; knowing the shape of the reward function assumption is realistic for several real-world problems like on-line active learning [5], A/B testing [7] and music recommendation [6]; in this setting, propose to study this new model derived from this problem, by adapting the existing algorithm to the new setting and analyzing their regret) or (Bouneffouf'2017, Section I of Page 1: the basic formulation of the Multi-Armed Bandit (MAB) problem can be described as follows: there are K arms, each having a fixed, unknown and independent probability-distribution of reward; at each step, a player chooses an arm and receives a reward; this reward is drawn according to the selected arm’s distribution and it is independent of previous actions; study here a special case of this model where the rewards of each arm of the bandit follow a known function; the real motivation is operational: knowing the shape of the reward function assumption is realistic for several real-world problems like on-line active learning, A/B testing and music recommendation; all these problems can be modeled as new bandit problem called “Multiarmed Bandit Problem with Known Trend” where each arm follow a known trend reward function; propose to study this new model derived from this problem, by adapting the existing algorithm to the new setting and analyzing their regret; evaluate the proposed algorithms through different simulations).
Claims 3 and 13
Bouneffouf'2016 or Bouneffouf'2017 in view of Huang discloses all the elements as stated in Claims 2 and 12 respectively and further discloses wherein implementing the ALINUCB algorithm includes the agent selecting an arm from the multiple arms at each step and receiving a non-stationary reward responsive to selecting an arm (Bouneffouf'2016, Section III with FIGS. 1-2 and Algorithms 1-3 of Pages 2544-2548: in the MAB setting, to maximize his gain the player has to find the best arm as soon as possible, and then exploit it; in our setting, the rewards follow a known function; when the player has found the best arm, he knows that this arm will be the best just for a certain period of time; the player needs to re-explore at each time to find the next best arm; let ri(1), …, ri(n) be a sequence of independent draws of the random variable ri ∈ [0, 1] with n the number of trials and let μi = E[ri] be its mean reward; at each time t, the player chooses an arm i ∈ {1, …, K} to play according to a (deterministic or random) policy φ based on sequence of plays and reward, and obtains a non-stationary reward z(t) where
z
t
=
r
i
t
(
t
)
∙
D
(
n
i
t
(
t
)
)
, where
D
(
n
i
t
(
t
)
is a trend reward function assumed to be known,
n
i
t
(
t
)
is the number of times i is played and
r
i
t
(
t
)
is the stationary reward for arm i at time t; a dynamic policy can be defined as function such that (φ : t
↦
n1(t), …, nK(t)) or φ : Ht−1
↦
K, where Ht−1 is the history of rewards known at time t; by applying a policy φ, at t a sequence of choices obtained (1, 2, …, t) ∈ [K]t; at time t, the gain of the policy φ is:
G
φ
t
=
∑
t
z
t
=
∑
t
r
i
t
t
D
n
i
t
t
; the performance of a policy φ is measured in terms of regret in the first T plays, which is defined as the expected difference between the total rewards collected by the optimal policy φ∗ (playing at each time instant the arm i∗ with the highest expected reward) and the total rewards collected by the policy φ; the objective is to minimize the regret R(T) at time T, where T is the time horizon; the expected regret after T plays is defined in Definition 1 as the difference between the optimal gain expectation and the expected gain got by the policy φ; note that we distribute the expectation because
r
i
t
(
t
)
and
n
i
t
(
t
)
are independent; the optimal policy in any time φ∗ consists in always playing the arm i∗ ∈ {1. …, K} with largest expected reward:
i
*
=
a
r
g
m
a
x
i
μ
i
∙
D
n
i
t
, where μi is the expectation of the reward
r
i
(
t
)
; F is the cumulative function of D(s) and is expressed as in Definition 3, notice that in the demonstration of the theorem 4, F is assumed to be Lipschitz; Theorem 1: the optimal policy in any time π∗ consists in always playing the arm i∗ ∈ {1, …, K} with largest expected reward:
i
*
=
a
r
g
m
a
x
1
≤
K
μ
i
∙
D
n
i
t
, where μi is the expectation of the reward
r
i
(
t
)
) or (Bouneffouf'2017, Section III of Pages 2-4: in the MAB setting, to maximize his gain the player has to find the best arm as soon as possible, and then exploit it; in our setting, the rewards follow a known function; when the player has found the best arm, he knows that this arm will be the best just for a certain period of time; the player needs to re-explore at each time to find the next best arm; in the MAB setting, to maximize his gain the player has to find the best arm as soon as possible, and then exploit it; in our setting, the rewards follow a known function; when the player has found the best arm, he knows that this arm will be the best just for a certain period of time; the player needs to re-explore at each time to find the next best arm; let ri(1), …, ri(n) be a sequence of independent draws of the random variable ri ∈ [0, 1] with n the number of trials and let μi = E[ri] be its mean reward; at each time t, the player chooses an arm i ∈ {1, …, K} to play according to a (deterministic or random) policy φ based on sequence of plays and reward, and obtains a non-stationary reward z(t) where
z
t
=
r
i
t
(
t
)
∙
D
(
n
i
t
(
t
)
)
, where
D
(
n
i
t
(
t
)
is a trend reward function assumed to be known,
n
i
t
(
t
)
is the number of times i is played and
r
i
t
(
t
)
is the stationary reward for arm i at time t; a dynamic policy can be defined as function such that (φ : t
↦
n1(t), …, nK(t)) or φ : Ht−1
↦
K, where Ht−1 is the history of rewards known at time t; by applying a policy φ, at t a sequence of choices obtained (1, 2, …, t) ∈ [K]t; at time t, the gain of the policy φ is:
G
φ
t
=
∑
t
z
t
=
∑
t
r
i
t
t
D
n
i
t
t
; the performance of a policy φ is measured in terms of regret in the first T plays, which is defined as the expected difference between the total rewards collected by the optimal policy φ∗ (playing at each time instant the arm i∗ with the highest expected reward) and the total rewards collected by the policy φ; the objective is to minimize the regret R(T) at time T, where T is the time horizon; the expected regret after T plays is defined in Definition 1 as the difference between the optimal gain expectation and the expected gain got by the policy φ; note that we distribute the expectation because
r
i
t
(
t
)
and
n
i
t
(
t
)
are independent; the optimal policy in any time φ∗ consists in always playing the arm i∗ ∈ {1. …, K} with largest expected reward:
i
*
=
a
r
g
m
a
x
i
μ
i
∙
D
n
i
t
, where μi is the expectation of the reward
r
i
(
t
)
; F is the cumulative function of D(s) and is expressed as in Definition 3, notice that in the demonstration of the theorem 4, F is assumed to be Lipschitz).
Claims 4 and 14
Bouneffouf'2016 or Bouneffouf'2017 in view of Huang discloses all the elements as stated in Claims 3 and 13 respectively and further discloses wherein the reward is responsive to a number of times the arm is engaged by the agent and to a known stationary reward for the arm at a given time (Bouneffouf'2016, Section III with FIGS. 1-2 and Algorithms 1-3 of Pages 2544-2548: in the MAB setting, to maximize his gain the player has to find the best arm as soon as possible, and then exploit it; in our setting, the rewards follow a known function; when the player has found the best arm, he knows that this arm will be the best just for a certain period of time; the player needs to re-explore at each time to find the next best arm; let ri(1), …, ri(n) be a sequence of independent draws of the random variable ri ∈ [0, 1] with n the number of trials and let μi = E[ri] be its mean reward; at each time t, the player chooses an arm i ∈ {1, …, K} to play according to a (deterministic or random) policy φ based on sequence of plays and reward, and obtains a non-stationary reward z(t) where
z
t
=
r
i
t
(
t
)
∙
D
(
n
i
t
(
t
)
)
, where
D
(
n
i
t
(
t
)
is a trend reward function assumed to be known,
n
i
t
(
t
)
is the number of times i is played and
r
i
t
(
t
)
is the stationary reward for arm i at time t; a dynamic policy can be defined as function such that (φ : t
↦
n1(t), …, nK(t)) or φ : Ht−1
↦
K, where Ht−1 is the history of rewards known at time t; by applying a policy φ, at t a sequence of choices obtained (1, 2, …, t) ∈ [K]t; at time t, the gain of the policy φ is:
G
φ
t
=
∑
t
z
t
=
∑
t
r
i
t
t
D
n
i
t
t
; the performance of a policy φ is measured in terms of regret in the first T plays, which is defined as the expected difference between the total rewards collected by the optimal policy φ∗ (playing at each time instant the arm i∗ with the highest expected reward) and the total rewards collected by the policy φ; the objective is to minimize the regret R(T) at time T, where T is the time horizon; the expected regret after T plays is defined in Definition 1 as the difference between the optimal gain expectation and the expected gain got by the policy φ; note that we distribute the expectation because
r
i
t
(
t
)
and
n
i
t
(
t
)
are independent; the optimal policy in any time φ∗ consists in always playing the arm i∗ ∈ {1. …, K} with largest expected reward:
i
*
=
a
r
g
m
a
x
i
μ
i
∙
D
n
i
t
, where μi is the expectation of the reward
r
i
(
t
)
; F is the cumulative function of D(s) and is expressed as in Definition 3, notice that in the demonstration of the theorem 4, F is assumed to be Lipschitz; Theorem 1: the optimal policy in any time π∗ consists in always playing the arm i∗ ∈ {1, …, K} with largest expected reward:
i
*
=
a
r
g
m
a
x
1
≤
K
μ
i
∙
D
n
i
t
, where μi is the expectation of the reward
r
i
(
t
)
) or (Bouneffouf'2017, Section III of Pages 2-4: in the MAB setting, to maximize his gain the player has to find the best arm as soon as possible, and then exploit it; in our setting, the rewards follow a known function; when the player has found the best arm, he knows that this arm will be the best just for a certain period of time; the player needs to re-explore at each time to find the next best arm; in the MAB setting, to maximize his gain the player has to find the best arm as soon as possible, and then exploit it; in our setting, the rewards follow a known function; when the player has found the best arm, he knows that this arm will be the best just for a certain period of time; the player needs to re-explore at each time to find the next best arm; let ri(1), …, ri(n) be a sequence of independent draws of the random variable ri ∈ [0, 1] with n the number of trials and let μi = E[ri] be its mean reward; at each time t, the player chooses an arm i ∈ {1, …, K} to play according to a (deterministic or random) policy φ based on sequence of plays and reward, and obtains a non-stationary reward z(t) where
z
t
=
r
i
t
(
t
)
∙
D
(
n
i
t
(
t
)
)
, where
D
(
n
i
t
(
t
)
is a trend reward function assumed to be known,
n
i
t
(
t
)
is the number of times i is played and
r
i
t
(
t
)
is the stationary reward for arm i at time t; a dynamic policy can be defined as function such that (φ : t
↦
n1(t), …, nK(t)) or φ : Ht−1
↦
K, where Ht−1 is the history of rewards known at time t; by applying a policy φ, at t a sequence of choices obtained (1, 2, …, t) ∈ [K]t; at time t, the gain of the policy φ is:
G
φ
t
=
∑
t
z
t
=
∑
t
r
i
t
t
D
n
i
t
t
; the performance of a policy φ is measured in terms of regret in the first T plays, which is defined as the expected difference between the total rewards collected by the optimal policy φ∗ (playing at each time instant the arm i∗ with the highest expected reward) and the total rewards collected by the policy φ; the objective is to minimize the regret R(T) at time T, where T is the time horizon; the expected regret after T plays is defined in Definition 1 as the difference between the optimal gain expectation and the expected gain got by the policy φ; note that we distribute the expectation because
r
i
t
(
t
)
and
n
i
t
(
t
)
are independent; the optimal policy in any time φ∗ consists in always playing the arm i∗ ∈ {1. …, K} with largest expected reward:
i
*
=
a
r
g
m
a
x
i
μ
i
∙
D
n
i
t
, where μi is the expectation of the reward
r
i
(
t
)
; F is the cumulative function of D(s) and is expressed as in Definition 3, notice that in the demonstration of the theorem 4, F is assumed to be Lipschitz).
Claims 5 and 15
Bouneffouf'2016 or Bouneffouf'2017 in view of Huang discloses all the elements as stated in Claims 1 and 11 respectively and further discloses wherein implementing includes defining a dynamic policy which is responsive to a history of rewards known at a given time (Bouneffouf'2016, Section III with FIGS. 1-2 and Algorithms 1-3 of Pages 2544-2548: in the MAB setting, to maximize his gain the player has to find the best arm as soon as possible, and then exploit it; in our setting, the rewards follow a known function; when the player has found the best arm, he knows that this arm will be the best just for a certain period of time; the player needs to re-explore at each time to find the next best arm; let ri(1), …, ri(n) be a sequence of independent draws of the random variable ri ∈ [0, 1] with n the number of trials and let μi = E[ri] be its mean reward; at each time t, the player chooses an arm i ∈ {1, …, K} to play according to a (deterministic or random) policy φ based on sequence of plays and reward, and obtains a non-stationary reward z(t) where
z
t
=
r
i
t
(
t
)
∙
D
(
n
i
t
(
t
)
)
, where
D
(
n
i
t
(
t
)
is a trend reward function assumed to be known,
n
i
t
(
t
)
is the number of times i is played and
r
i
t
(
t
)
is the stationary reward for arm i at time t; a dynamic policy can be defined as function such that (φ : t
↦
n1(t), …, nK(t)) or φ : Ht−1
↦
K, where Ht−1 is the history of rewards known at time t; by applying a policy φ, at t a sequence of choices obtained (1, 2, …, t) ∈ [K]t; at time t, the gain of the policy φ is:
G
φ
t
=
∑
t
z
t
=
∑
t
r
i
t
t
D
n
i
t
t
; the performance of a policy φ is measured in terms of regret in the first T plays, which is defined as the expected difference between the total rewards collected by the optimal policy φ∗ (playing at each time instant the arm i∗ with the highest expected reward) and the total rewards collected by the policy φ; the objective is to minimize the regret R(T) at time T, where T is the time horizon; the expected regret after T plays is defined in Definition 1 as the difference between the optimal gain expectation and the expected gain got by the policy φ; note that we distribute the expectation because
r
i
t
(
t
)
and
n
i
t
(
t
)
are independent; the optimal policy in any time φ∗ consists in always playing the arm i∗ ∈ {1. …, K} with largest expected reward:
i
*
=
a
r
g
m
a
x
i
μ
i
∙
D
n
i
t
, where μi is the expectation of the reward
r
i
(
t
)
; F is the cumulative function of D(s) and is expressed as in Definition 3, notice that in the demonstration of the theorem 4, F is assumed to be Lipschitz; Theorem 1: the optimal policy in any time π∗ consists in always playing the arm i∗ ∈ {1, …, K} with largest expected reward:
i
*
=
a
r
g
m
a
x
1
≤
K
μ
i
∙
D
n
i
t
, where μi is the expectation of the reward
r
i
(
t
)
) or (Bouneffouf'2017, Section III of Pages 2-4: in the MAB setting, to maximize his gain the player has to find the best arm as soon as possible, and then exploit it; in our setting, the rewards follow a known function; when the player has found the best arm, he knows that this arm will be the best just for a certain period of time; the player needs to re-explore at each time to find the next best arm; in the MAB setting, to maximize his gain the player has to find the best arm as soon as possible, and then exploit it; in our setting, the rewards follow a known function; when the player has found the best arm, he knows that this arm will be the best just for a certain period of time; the player needs to re-explore at each time to find the next best arm; let ri(1), …, ri(n) be a sequence of independent draws of the random variable ri ∈ [0, 1] with n the number of trials and let μi = E[ri] be its mean reward; at each time t, the player chooses an arm i ∈ {1, …, K} to play according to a (deterministic or random) policy φ based on sequence of plays and reward, and obtains a non-stationary reward z(t) where
z
t
=
r
i
t
(
t
)
∙
D
(
n
i
t
(
t
)
)
, where
D
(
n
i
t
(
t
)
is a trend reward function assumed to be known,
n
i
t
(
t
)
is the number of times i is played and
r
i
t
(
t
)
is the stationary reward for arm i at time t; a dynamic policy can be defined as function such that (φ : t
↦
n1(t), …, nK(t)) or φ : Ht−1
↦
K, where Ht−1 is the history of rewards known at time t; by applying a policy φ, at t a sequence of choices obtained (1, 2, …, t) ∈ [K]t; at time t, the gain of the policy φ is:
G
φ
t
=
∑
t
z
t
=
∑
t
r
i
t
t
D
n
i
t
t
; the performance of a policy φ is measured in terms of regret in the first T plays, which is defined as the expected difference between the total rewards collected by the optimal policy φ∗ (playing at each time instant the arm i∗ with the highest expected reward) and the total rewards collected by the policy φ; the objective is to minimize the regret R(T) at time T, where T is the time horizon; the expected regret after T plays is defined in Definition 1 as the difference between the optimal gain expectation and the expected gain got by the policy φ; note that we distribute the expectation because
r
i
t
(
t
)
and
n
i
t
(
t
)
are independent; the optimal policy in any time φ∗ consists in always playing the arm i∗ ∈ {1. …, K} with largest expected reward:
i
*
=
a
r
g
m
a
x
i
μ
i
∙
D
n
i
t
, where μi is the expectation of the reward
r
i
(
t
)
; F is the cumulative function of D(s) and is expressed as in Definition 3, notice that in the demonstration of the theorem 4, F is assumed to be Lipschitz).
Claims 6 and 16
Bouneffouf'2016 or Bouneffouf'2017 in view of Huang discloses all the elements as stated in Claims 5 and 15 respectively and further discloses wherein implementing includes applying the policy at a predetermined time to obtain a sequence of choices, wherein the policy includes a Gain (Bouneffouf'2016, Section III with FIGS. 1-2 and Algorithms 1-3 of Pages 2544-2548: in the MAB setting, to maximize his gain the player has to find the best arm as soon as possible, and then exploit it; in our setting, the rewards follow a known function; when the player has found the best arm, he knows that this arm will be the best just for a certain period of time; the player needs to re-explore at each time to find the next best arm; let ri(1), …, ri(n) be a sequence of independent draws of the random variable ri ∈ [0, 1] with n the number of trials and let μi = E[ri] be its mean reward; at each time t, the player chooses an arm i ∈ {1, …, K} to play according to a (deterministic or random) policy φ based on sequence of plays and reward, and obtains a non-stationary reward z(t) where
z
t
=
r
i
t
(
t
)
∙
D
(
n
i
t
(
t
)
)
, where
D
(
n
i
t
(
t
)
is a trend reward function assumed to be known,
n
i
t
(
t
)
is the number of times i is played and
r
i
t
(
t
)
is the stationary reward for arm i at time t; a dynamic policy can be defined as function such that (φ : t
↦
n1(t), …, nK(t)) or φ : Ht−1
↦
K, where Ht−1 is the history of rewards known at time t; by applying a policy φ, at t a sequence of choices obtained (1, 2, …, t) ∈ [K]t; at time t, the gain of the policy φ is:
G
φ
t
=
∑
t
z
t
=
∑
t
r
i
t
t
D
n
i
t
t
; the performance of a policy φ is measured in terms of regret in the first T plays, which is defined as the expected difference between the total rewards collected by the optimal policy φ∗ (playing at each time instant the arm i∗ with the highest expected reward) and the total rewards collected by the policy φ; the objective is to minimize the regret R(T) at time T, where T is the time horizon; the expected regret after T plays is defined in Definition 1 as the difference between the optimal gain expectation and the expected gain got by the policy φ; note that we distribute the expectation because
r
i
t
(
t
)
and
n
i
t
(
t
)
are independent; the optimal policy in any time φ∗ consists in always playing the arm i∗ ∈ {1. …, K} with largest expected reward:
i
*
=
a
r
g
m
a
x
i
μ
i
∙
D
n
i
t
, where μi is the expectation of the reward
r
i
(
t
)
; F is the cumulative function of D(s) and is expressed as in Definition 3, notice that in the demonstration of the theorem 4, F is assumed to be Lipschitz; Theorem 1: the optimal policy in any time π∗ consists in always playing the arm i∗ ∈ {1, …, K} with largest expected reward:
i
*
=
a
r
g
m
a
x
1
≤
K
μ
i
∙
D
n
i
t
, where μi is the expectation of the reward
r
i
(
t
)
) or (Bouneffouf'2017, Section III of Pages 2-4: in the MAB setting, to maximize his gain the player has to find the best arm as soon as possible, and then exploit it; in our setting, the rewards follow a known function; when the player has found the best arm, he knows that this arm will be the best just for a certain period of time; the player needs to re-explore at each time to find the next best arm; in the MAB setting, to maximize his gain the player has to find the best arm as soon as possible, and then exploit it; in our setting, the rewards follow a known function; when the player has found the best arm, he knows that this arm will be the best just for a certain period of time; the player needs to re-explore at each time to find the next best arm; let ri(1), …, ri(n) be a sequence of independent draws of the random variable ri ∈ [0, 1] with n the number of trials and let μi = E[ri] be its mean reward; at each time t, the player chooses an arm i ∈ {1, …, K} to play according to a (deterministic or random) policy φ based on sequence of plays and reward, and obtains a non-stationary reward z(t) where
z
t
=
r
i
t
(
t
)
∙
D
(
n
i
t
(
t
)
)
, where
D
(
n
i
t
(
t
)
is a trend reward function assumed to be known,
n
i
t
(
t
)
is the number of times i is played and
r
i
t
(
t
)
is the stationary reward for arm i at time t; a dynamic policy can be defined as function such that (φ : t
↦
n1(t), …, nK(t)) or φ : Ht−1
↦
K, where Ht−1 is the history of rewards known at time t; by applying a policy φ, at t a sequence of choices obtained (1, 2, …, t) ∈ [K]t; at time t, the gain of the policy φ is:
G
φ
t
=
∑
t
z
t
=
∑
t
r
i
t
t
D
n
i
t
t
; the performance of a policy φ is measured in terms of regret in the first T plays, which is defined as the expected difference between the total rewards collected by the optimal policy φ∗ (playing at each time instant the arm i∗ with the highest expected reward) and the total rewards collected by the policy φ; the objective is to minimize the regret R(T) at time T, where T is the time horizon; the expected regret after T plays is defined in Definition 1 as the difference between the optimal gain expectation and the expected gain got by the policy φ; note that we distribute the expectation because
r
i
t
(
t
)
and
n
i
t
(
t
)
are independent; the optimal policy in any time φ∗ consists in always playing the arm i∗ ∈ {1. …, K} with largest expected reward:
i
*
=
a
r
g
m
a
x
i
μ
i
∙
D
n
i
t
, where μi is the expectation of the reward
r
i
(
t
)
; F is the cumulative function of D(s) and is expressed as in Definition 3, notice that in the demonstration of the theorem 4, F is assumed to be Lipschitz).
Claims 7 and 17
Bouneffouf'2016 or Bouneffouf'2017 in view of Huang discloses all the elements as stated in Claims 6 and 16 respectively and further discloses wherein implementing includes measuring the policy relative to a predetermined number of plays and an expected regret at the predetermined time, wherein the predetermined time is a time horizon and an expected regret after the predetermined number of plays is responsive to an optimal gain expectation and an expected gain obtained by the policy (Bouneffouf'2016, Section III with FIGS. 1-2 and Algorithms 1-3 of Pages 2544-2548: in the MAB setting, to maximize his gain the player has to find the best arm as soon as possible, and then exploit it; in our setting, the rewards follow a known function; when the player has found the best arm, he knows that this arm will be the best just for a certain period of time; the player needs to re-explore at each time to find the next best arm; let ri(1), …, ri(n) be a sequence of independent draws of the random variable ri ∈ [0, 1] with n the number of trials and let μi = E[ri] be its mean reward; at each time t, the player chooses an arm i ∈ {1, …, K} to play according to a (deterministic or random) policy φ based on sequence of plays and reward, and obtains a non-stationary reward z(t) where
z
t
=
r
i
t
(
t
)
∙
D
(
n
i
t
(
t
)
)
, where
D
(
n
i
t
(
t
)
is a trend reward function assumed to be known,
n
i
t
(
t
)
is the number of times i is played and
r
i
t
(
t
)
is the stationary reward for arm i at time t; a dynamic policy can be defined as function such that (φ : t
↦
n1(t), …, nK(t)) or φ : Ht−1
↦
K, where Ht−1 is the history of rewards known at time t; by applying a policy φ, at t a sequence of choices obtained (1, 2, …, t) ∈ [K]t; at time t, the gain of the policy φ is:
G
φ
t
=
∑
t
z
t
=
∑
t
r
i
t
t
D
n
i
t
t
; the performance of a policy φ is measured in terms of regret in the first T plays, which is defined as the expected difference between the total rewards collected by the optimal policy φ∗ (playing at each time instant the arm i∗ with the highest expected reward) and the total rewards collected by the policy φ; the objective is to minimize the regret R(T) at time T, where T is the time horizon; the expected regret after T plays is defined in Definition 1 as the difference between the optimal gain expectation and the expected gain got by the policy φ; note that we distribute the expectation because
r
i
t
(
t
)
and
n
i
t
(
t
)
are independent; the optimal policy in any time φ∗ consists in always playing the arm i∗ ∈ {1. …, K} with largest expected reward:
i
*
=
a
r
g
m
a
x
i
μ
i
∙
D
n
i
t
, where μi is the expectation of the reward
r
i
(
t
)
; F is the cumulative function of D(s) and is expressed as in Definition 3, notice that in the demonstration of the theorem 4, F is assumed to be Lipschitz; Theorem 1: the optimal policy in any time π∗ consists in always playing the arm i∗ ∈ {1, …, K} with largest expected reward:
i
*
=
a
r
g
m
a
x
1
≤
K
μ
i
∙
D
n
i
t
, where μi is the expectation of the reward
r
i
(
t
)
) or (Bouneffouf'2017, Section III of Pages 2-4: in the MAB setting, to maximize his gain the player has to find the best arm as soon as possible, and then exploit it; in our setting, the rewards follow a known function; when the player has found the best arm, he knows that this arm will be the best just for a certain period of time; the player needs to re-explore at each time to find the next best arm; in the MAB setting, to maximize his gain the player has to find the best arm as soon as possible, and then exploit it; in our setting, the rewards follow a known function; when the player has found the best arm, he knows that this arm will be the best just for a certain period of time; the player needs to re-explore at each time to find the next best arm; let ri(1), …, ri(n) be a sequence of independent draws of the random variable ri ∈ [0, 1] with n the number of trials and let μi = E[ri] be its mean reward; at each time t, the player chooses an arm i ∈ {1, …, K} to play according to a (deterministic or random) policy φ based on sequence of plays and reward, and obtains a non-stationary reward z(t) where
z
t
=
r
i
t
(
t
)
∙
D
(
n
i
t
(
t
)
)
, where
D
(
n
i
t
(
t
)
is a trend reward function assumed to be known,
n
i
t
(
t
)
is the number of times i is played and
r
i
t
(
t
)
is the stationary reward for arm i at time t; a dynamic policy can be defined as function such that (φ : t
↦
n1(t), …, nK(t)) or φ : Ht−1
↦
K, where Ht−1 is the history of rewards known at time t; by applying a policy φ, at t a sequence of choices obtained (1, 2, …, t) ∈ [K]t; at time t, the gain of the policy φ is:
G
φ
t
=
∑
t
z
t
=
∑
t
r
i
t
t
D
n
i
t
t
; the performance of a policy φ is measured in terms of regret in the first T plays, which is defined as the expected difference between the total rewards collected by the optimal policy φ∗ (playing at each time instant the arm i∗ with the highest expected reward) and the total rewards collected by the policy φ; the objective is to minimize the regret R(T) at time T, where T is the time horizon; the expected regret after T plays is defined in Definition 1 as the difference between the optimal gain expectation and the expected gain got by the policy φ; note that we distribute the expectation because
r
i
t
(
t
)
and
n
i
t
(
t
)
are independent; the optimal policy in any time φ∗ consists in always playing the arm i∗ ∈ {1. …, K} with largest expected reward:
i
*
=
a
r
g
m
a
x
i
μ
i
∙
D
n
i
t
, where μi is the expectation of the reward
r
i
(
t
)
; F is the cumulative function of D(s) and is expressed as in Definition 3, notice that in the demonstration of the theorem 4, F is assumed to be Lipschitz).
Claims 8 and 18
Bouneffouf'2016 or Bouneffouf'2017 in view of Huang discloses all the elements as stated in Claims 1 and 11 respectively (see Claim Objections to Claim 18) and further discloses wherein implementing further includes computing an index for each of a plurality of trial plays for each of the multiple arms, wherein the index for each arm of the multiple arms is responsive to a corresponding confidence interval (Bouneffouf'2016, Section III with FIGS. 1-2 and Algorithms 1-3 of Pages 2544-2548: in the MAB setting, to maximize his gain the player has to find the best arm as soon as possible, and then exploit it; in our setting, the rewards follow a known function; when the player has found the best arm, he knows that this arm will be the best just for a certain period of time; the player needs to re-explore at each time to find the next best arm; let ri(1), …, ri(n) be a sequence of independent draws of the random variable ri ∈ [0, 1] with n the number of trials and let μi = E[ri] be its mean reward; at each time t, the player chooses an arm i ∈ {1, …, K} to play according to a (deterministic or random) policy φ based on sequence of plays and reward, and obtains a non-stationary reward z(t) where
z
t
=
r
i
t
(
t
)
∙
D
(
n
i
t
(
t
)
)
, where
D
(
n
i
t
(
t
)
is a trend reward function assumed to be known,
n
i
t
(
t
)
is the number of times i is played and
r
i
t
(
t
)
is the stationary reward for arm i at time t; a dynamic policy can be defined as function such that (φ : t
↦
n1(t), …, nK(t)) or φ : Ht−1
↦
K, where Ht−1 is the history of rewards known at time t; by applying a policy φ, at t a sequence of choices obtained (1, 2, …, t) ∈ [K]t; at time t, the gain of the policy φ is:
G
φ
t
=
∑
t
z
t
=
∑
t
r
i
t
t
D
n
i
t
t
; the performance of a policy φ is measured in terms of regret in the first T plays, which is defined as the expected difference between the total rewards collected by the optimal policy φ∗ (playing at each time instant the arm i∗ with the highest expected reward) and the total rewards collected by the policy φ; the objective is to minimize the regret R(T) at time T, where T is the time horizon; the expected regret after T plays is defined in Definition 1 as the difference between the optimal gain expectation and the expected gain got by the policy φ; note that we distribute the expectation because
r
i
t
(
t
)
and
n
i
t
(
t
)
are independent; the optimal policy in any time φ∗ consists in always playing the arm i∗ ∈ {1. …, K} with largest expected reward:
i
*
=
a
r
g
m
a
x
i
μ
i
∙
D
n
i
t
, where μi is the expectation of the reward
r
i
(
t
)
; F is the cumulative function of D(s) and is expressed as in Definition 3, notice that in the demonstration of the theorem 4, F is assumed to be Lipschitz; Theorem 1: the optimal policy in any time π∗ consists in always playing the arm i∗ ∈ {1, …, K} with largest expected reward:
i
*
=
a
r
g
m
a
x
1
≤
K
μ
i
∙
D
n
i
t
, where μi is the expectation of the reward
r
i
(
t
)
; demonstrate in lemma 1 that an optimal policy π cannot attend the optimal at t+1 if it is not optimal at time t and which means that the optimal policy has to select at each time the optimal arm; Theorem 2: for the bandit problem with known trend, the accumulated expected regret R for any policy φ and any horizon T is lower bounded by
1
m
a
x
i
μ
i
D
m
a
x
∑
i
:
n
i
T
>
n
i
*
T
E
n
i
T
-
n
i
*
T
≤
E
R
T
; to adapt the UCB algorithm for the news setting, the proposed A-UCB algorithm (Algorithm 1) computes at each trial t an index
I
i
=
μ
^
i
+
c
i
∙
D
n
i
t
for each arm i, where c(i) is the corresponding confidence interval, so that
c
i
=
2
×
l
o
g
t
n
i
t
; the UCB index is multiplied by
D
n
i
t
to stop playing the supposed optimal arm when its rewards become suboptimal.; for the bandit problem with known trend, the accumulated expected regret R of A-UCB policy is bounded by
E
R
T
≤
m
a
x
i
μ
i
D
m
a
x
∑
i
:
n
i
*
T
>
n
i
T
8
l
n
T
∆
'
i
2
+
K
π
2
3
, where
∆
i
'
=
D
m
i
n
D
m
a
x
μ
i
t
*
-
μ
i
t
with Dmin and Dmax two Lipschitz constants; the Action elimination (AE) algorithm attempts to sample each arm a minimal number of times and eliminate the arms one after the other; however in our case a sub optimal arm at time t can be optimal arm at time t+1 and applying AE can eliminate the future optimal arms; to adapt the AE algorithm to our setting, the proposed A-AE (Alg. 2) algorithm compute the
μ
^
m
a
x
∙
D
n
i
T
-
μ
^
i
∙
D
n
i
T
rather than
μ
^
m
a
x
-
μ
^
i
for the arm elimination; for the bandit problem with known trend, the accumulated expected regret R of A-AE policy is bounded by
∑
t
=
1
T
r
e
g
r
e
t
t
≤
∑
i
=
2
n
l
o
g
T
δ
∆
i
'
∆
i
'
with
∆
'
=
D
m
a
x
D
m
i
n
μ
^
i
*
-
μ
^
i
; using Beta prior and considering the Bernoulli bandit problem (the rewards are either 0 or 1), Thompson Sampling (TS) initially assumes arm i to have prior Beta(1, 1) on μi (the probability of success); at time t, having observed Si(t) successes (reward = 1) and Fi(t) failures (reward = 0) in θi(t) = Si(t) + Fi(t) selects of document i, the algorithm updates the distribution on μi as Beta(Si(t)+1, Fi(t)+1); the algorithm then generates independent samples from these posterior distributions of the μi, and selects the document with the largest sample value μi; to adapt the TS sampling for our setting, propose A-TS (Algorithm 3), this algorithm multiply θi(t) by D(ni(t)) to stop playing the supposed optimal arm when its rewards start to decrease; for the bandit problem with known trend, the total regret in time T for A-TS is bounded by
E
R
T
≤
1
∆
i
'
-
ϵ
2
l
g
1
T
+
8
l
n
T
∆
'
i
2
+
1
+
π
2
3
+
O
(
1
)
) or (Bouneffouf'2017, Section III of Pages 2-4: in the MAB setting, to maximize his gain the player has to find the best arm as soon as possible, and then exploit it; in our setting, the rewards follow a known function; when the player has found the best arm, he knows that this arm will be the best just for a certain period of time; the player needs to re-explore at each time to find the next best arm; in the MAB setting, to maximize his gain the player has to find the best arm as soon as possible, and then exploit it; in our setting, the rewards follow a known function; when the player has found the best arm, he knows that this arm will be the best just for a certain period of time; the player needs to re-explore at each time to find the next best arm; let ri(1), …, ri(n) be a sequence of independent draws of the random variable ri ∈ [0, 1] with n the number of trials and let μi = E[ri] be its mean reward; at each time t, the player chooses an arm i ∈ {1, …, K} to play according to a (deterministic or random) policy φ based on sequence of plays and reward, and obtains a non-stationary reward z(t) where
z
t
=
r
i
t
(
t
)
∙
D
(
n
i
t
(
t
)
)
, where
D
(
n
i
t
(
t
)
is a trend reward function assumed to be known,
n
i
t
(
t
)
is the number of times i is played and
r
i
t
(
t
)
is the stationary reward for arm i at time t; a dynamic policy can be defined as function such that (φ : t
↦
n1(t), …, nK(t)) or φ : Ht−1
↦
K, where Ht−1 is the history of rewards known at time t; by applying a policy φ, at t a sequence of choices obtained (1, 2, …, t) ∈ [K]t; at time t, the gain of the policy φ is:
G
φ
t
=
∑
t
z
t
=
∑
t
r
i
t
t
D
n
i
t
t
; the performance of a policy φ is measured in terms of regret in the first T plays, which is defined as the expected difference between the total rewards collected by the optimal policy φ∗ (playing at each time instant the arm i∗ with the highest expected reward) and the total rewards collected by the policy φ; the objective is to minimize the regret R(T) at time T, where T is the time horizon; the expected regret after T plays is defined in Definition 1 as the difference between the optimal gain expectation and the expected gain got by the policy φ; note that we distribute the expectation because
r
i
t
(
t
)
and
n
i
t
(
t
)
are independent; the optimal policy in any time φ∗ consists in always playing the arm i∗ ∈ {1. …, K} with largest expected reward:
i
*
=
a
r
g
m
a
x
i
μ
i
∙
D
n
i
t
, where μi is the expectation of the reward
r
i
(
t
)
; F is the cumulative function of D(s) and is expressed as in Definition 3, notice that in the demonstration of the theorem 1, F is assumed to be Lipschitz; to adapt the UCB algorithm for the news setting, the proposed A-UCB algorithm computes at each trial t an index
I
i
=
μ
^
i
+
c
i
∙
D
n
i
t
for each arm i, where c(i) is the corresponding confidence interval, so that
c
i
=
2
×
l
o
g
t
n
i
t
; The UCB index is multiplied by
D
n
i
t
to stop playing the supposed optimal arm when its rewards become suboptimal.; the A-UCB algorithm is shown in Algorithm 1; for the bandit problem with known trend, the accumulated expected regret R of A-UCB policy is bounded by
E
R
T
≤
m
a
x
i
μ
i
D
m
a
x
∑
i
:
n
i
*
T
>
n
i
T
8
l
n
T
∆
'
i
2
+
K
π
2
3
, where
∆
i
'
=
D
m
i
n
D
m
a
x
μ
i
t
*
-
μ
i
t
with Dmin and Dmax two Lipschitz constants).
Claims 9 and 19
Bouneffouf'2016 or Bouneffouf'2017 in view of Huang discloses all the elements as stated in Claims 8 and 18 respectively (see Claim Objections to Claim 19) and further discloses wherein the ALINUCB algorithm includes, selecting an arm from the multiple arms; applying an Argmax function to the arm for each of a plurality of predetermined times; and observing a reward for the arm for each of the predetermined times (Bouneffouf'2016, Section III with FIGS. 1-2 and Algorithms 1-3 of Pages 2544-2548: in the MAB setting, to maximize his gain the player has to find the best arm as soon as possible, and then exploit it; in our setting, the rewards follow a known function; when the player has found the best arm, he knows that this arm will be the best just for a certain period of time; the player needs to re-explore at each time to find the next best arm; let ri(1), …, ri(n) be a sequence of independent draws of the random variable ri ∈ [0, 1] with n the number of trials and let μi = E[ri] be its mean reward; at each time t, the player chooses an arm i ∈ {1, …, K} to play according to a (deterministic or random) policy φ based on sequence of plays and reward, and obtains a non-stationary reward z(t) where
z
t
=
r
i
t
(
t
)
∙
D
(
n
i
t
(
t
)
)
, where
D
(
n
i
t
(
t
)
is a trend reward function assumed to be known,
n
i
t
(
t
)
is the number of times i is played and
r
i
t
(
t
)
is the stationary reward for arm i at time t; a dynamic policy can be defined as function such that (φ : t
↦
n1(t), …, nK(t)) or φ : Ht−1
↦
K, where Ht−1 is the history of rewards known at time t; by applying a policy φ, at t a sequence of choices obtained (1, 2, …, t) ∈ [K]t; at time t, the gain of the policy φ is:
G
φ
t
=
∑
t
z
t
=
∑
t
r
i
t
t
D
n
i
t
t
; the performance of a policy φ is measured in terms of regret in the first T plays, which is defined as the expected difference between the total rewards collected by the optimal policy φ∗ (playing at each time instant the arm i∗ with the highest expected reward) and the total rewards collected by the policy φ; the objective is to minimize the regret R(T) at time T, where T is the time horizon; the expected regret after T plays is defined in Definition 1 as the difference between the optimal gain expectation and the expected gain got by the policy φ; note that we distribute the expectation because
r
i
t
(
t
)
and
n
i
t
(
t
)
are independent; the optimal policy in any time φ∗ consists in always playing the arm i∗ ∈ {1. …, K} with largest expected reward:
i
*
=
a
r
g
m
a
x
i
μ
i
∙
D
n
i
t
, where μi is the expectation of the reward
r
i
(
t
)
; F is the cumulative function of D(s) and is expressed as in Definition 3, notice that in the demonstration of the theorem 4, F is assumed to be Lipschitz; Theorem 1: the optimal policy in any time π∗ consists in always playing the arm i∗ ∈ {1, …, K} with largest expected reward:
i
*
=
a
r
g
m
a
x
1
≤
K
μ
i
∙
D
n
i
t
, where μi is the expectation of the reward
r
i
(
t
)
; demonstrate in lemma 1 that an optimal policy π cannot attend the optimal at t+1 if it is not optimal at time t and which means that the optimal policy has to select at each time the optimal arm; Theorem 2: for the bandit problem with known trend, the accumulated expected regret R for any policy φ and any horizon T is lower bounded by
1
m
a
x
i
μ
i
D
m
a
x
∑
i
:
n
i
T
>
n
i
*
T
E
n
i
T
-
n
i
*
T
≤
E
R
T
; to adapt the UCB algorithm for the news setting, the proposed A-UCB algorithm (Algorithm 1) computes at each trial t an index
I
i
=
μ
^
i
+
c
i
∙
D
n
i
t
for each arm i, where c(i) is the corresponding confidence interval, so that
c
i
=
2
×
l
o
g
t
n
i
t
; the UCB index is multiplied by
D
n
i
t
to stop playing the supposed optimal arm when its rewards become suboptimal.; for the bandit problem with known trend, the accumulated expected regret R of A-UCB policy is bounded by
E
R
T
≤
m
a
x
i
μ
i
D
m
a
x
∑
i
:
n
i
*
T
>
n
i
T
8
l
n
T
∆
'
i
2
+
K
π
2
3
, where
∆
i
'
=
D
m
i
n
D
m
a
x
μ
i
t
*
-
μ
i
t
with Dmin and Dmax two Lipschitz constants; the Action elimination (AE) algorithm attempts to sample each arm a minimal number of times and eliminate the arms one after the other; however in our case a sub optimal arm at time t can be optimal arm at time t+1 and applying AE can eliminate the future optimal arms; to adapt the AE algorithm to our setting, the proposed A-AE (Alg. 2) algorithm compute the
μ
^
m
a
x
∙
D
n
i
T
-
μ
^
i
∙
D
n
i
T
rather than
μ
^
m
a
x
-
μ
^
i
for the arm elimination; for the bandit problem with known trend, the accumulated expected regret R of A-AE policy is bounded by
∑
t
=
1
T
r
e
g
r
e
t
t
≤
∑
i
=
2
n
l
o
g
T
δ
∆
i
'
∆
i
'
with
∆
'
=
D
m
a
x
D
m
i
n
μ
^
i
*
-
μ
^
i
; using Beta prior and considering the Bernoulli bandit problem (the rewards are either 0 or 1), Thompson Sampling (TS) initially assumes arm i to have prior Beta(1, 1) on μi (the probability of success); at time t, having observed Si(t) successes (reward = 1) and Fi(t) failures (reward = 0) in θi(t) = Si(t) + Fi(t) selects of document i, the algorithm updates the distribution on μi as Beta(Si(t)+1, Fi(t)+1); the algorithm then generates independent samples from these posterior distributions of the μi, and selects the document with the largest sample value μi; to adapt the TS sampling for our setting, propose A-TS (Algorithm 3), this algorithm multiply θi(t) by D(ni(t)) to stop playing the supposed optimal arm when its rewards start to decrease; for the bandit problem with known trend, the total regret in time T for A-TS is bounded by
E
R
T
≤
1
∆
i
'
-
ϵ
2
l
g
1
T
+
8
l
n
T
∆
'
i
2
+
1
+
π
2
3
+
O
(
1
)
) or (Bouneffouf'2017, Section III of Pages 2-4: in the MAB setting, to maximize his gain the player has to find the best arm as soon as possible, and then exploit it; in our setting, the rewards follow a known function; when the player has found the best arm, he knows that this arm will be the best just for a certain period of time; the player needs to re-explore at each time to find the next best arm; in the MAB setting, to maximize his gain the player has to find the best arm as soon as possible, and then exploit it; in our setting, the rewards follow a known function; when the player has found the best arm, he knows that this arm will be the best just for a certain period of time; the player needs to re-explore at each time to find the next best arm; let ri(1), …, ri(n) be a sequence of independent draws of the random variable ri ∈ [0, 1] with n the number of trials and let μi = E[ri] be its mean reward; at each time t, the player chooses an arm i ∈ {1, …, K} to play according to a (deterministic or random) policy φ based on sequence of plays and reward, and obtains a non-stationary reward z(t) where
z
t
=
r
i
t
(
t
)
∙
D
(
n
i
t
(
t
)
)
, where
D
(
n
i
t
(
t
)
is a trend reward function assumed to be known,
n
i
t
(
t
)
is the number of times i is played and
r
i
t
(
t
)
is the stationary reward for arm i at time t; a dynamic policy can be defined as function such that (φ : t
↦
n1(t), …, nK(t)) or φ : Ht−1
↦
K, where Ht−1 is the history of rewards known at time t; by applying a policy φ, at t a sequence of choices obtained (1, 2, …, t) ∈ [K]t; at time t, the gain of the policy φ is:
G
φ
t
=
∑
t
z
t
=
∑
t
r
i
t
t
D
n
i
t
t
; the performance of a policy φ is measured in terms of regret in the first T plays, which is defined as the expected difference between the total rewards collected by the optimal policy φ∗ (playing at each time instant the arm i∗ with the highest expected reward) and the total rewards collected by the policy φ; the objective is to minimize the regret R(T) at time T, where T is the time horizon; the expected regret after T plays is defined in Definition 1 as the difference between the optimal gain expectation and the expected gain got by the policy φ; note that we distribute the expectation because
r
i
t
(
t
)
and
n
i
t
(
t
)
are independent; the optimal policy in any time φ∗ consists in always playing the arm i∗ ∈ {1. …, K} with largest expected reward:
i
*
=
a
r
g
m
a
x
i
μ
i
∙
D
n
i
t
, where μi is the expectation of the reward
r
i
(
t
)
; F is the cumulative function of D(s) and is expressed as in Definition 3, notice that in the demonstration of the theorem 1, F is assumed to be Lipschitz; to adapt the UCB algorithm for the news setting, the proposed A-UCB algorithm computes at each trial t an index
I
i
=
μ
^
i
+
c
i
∙
D
n
i
t
for each arm i, where c(i) is the corresponding confidence interval, so that
c
i
=
2
×
l
o
g
t
n
i
t
; The UCB index is multiplied by
D
n
i
t
to stop playing the supposed optimal arm when its rewards become suboptimal.; the A-UCB algorithm is shown in Algorithm 1; for the bandit problem with known trend, the accumulated expected regret R of A-UCB policy is bounded by
E
R
T
≤
m
a
x
i
μ
i
D
m
a
x
∑
i
:
n
i
*
T
>
n
i
T
8
l
n
T
∆
'
i
2
+
K
π
2
3
, where
∆
i
'
=
D
m
i
n
D
m
a
x
μ
i
t
*
-
μ
i
t
with Dmin and Dmax two Lipschitz constants).
Claim 10
Bouneffouf'2016 or Bouneffouf'2017 in view of Huang discloses all the elements as stated in Claim 9 and further discloses wherein the ALINUCB algorithm is bounded by an upper bounding limit (Bouneffouf'2016, Section III with FIGS. 1-2 and Algorithms 1-3 of Pages 2544-2548: in the MAB setting, to maximize his gain the player has to find the best arm as soon as possible, and then exploit it; in our setting, the rewards follow a known function; when the player has found the best arm, he knows that this arm will be the best just for a certain period of time; the player needs to re-explore at each time to find the next best arm; let ri(1), …, ri(n) be a sequence of independent draws of the random variable ri ∈ [0, 1] with n the number of trials and let μi = E[ri] be its mean reward; at each time t, the player chooses an arm i ∈ {1, …, K} to play according to a (deterministic or random) policy φ based on sequence of plays and reward, and obtains a non-stationary reward z(t) where
z
t
=
r
i
t
(
t
)
∙
D
(
n
i
t
(
t
)
)
, where
D
(
n
i
t
(
t
)
is a trend reward function assumed to be known,
n
i
t
(
t
)
is the number of times i is played and
r
i
t
(
t
)
is the stationary reward for arm i at time t; a dynamic policy can be defined as function such that (φ : t
↦
n1(t), …, nK(t)) or φ : Ht−1
↦
K, where Ht−1 is the history of rewards known at time t; by applying a policy φ, at t a sequence of choices obtained (1, 2, …, t) ∈ [K]t; at time t, the gain of the policy φ is:
G
φ
t
=
∑
t
z
t
=
∑
t
r
i
t
t
D
n
i
t
t
; the performance of a policy φ is measured in terms of regret in the first T plays, which is defined as the expected difference between the total rewards collected by the optimal policy φ∗ (playing at each time instant the arm i∗ with the highest expected reward) and the total rewards collected by the policy φ; the objective is to minimize the regret R(T) at time T, where T is the time horizon; the expected regret after T plays is defined in Definition 1 as the difference between the optimal gain expectation and the expected gain got by the policy φ; note that we distribute the expectation because
r
i
t
(
t
)
and
n
i
t
(
t
)
are independent; the optimal policy in any time φ∗ consists in always playing the arm i∗ ∈ {1. …, K} with largest expected reward:
i
*
=
a
r
g
m
a
x
i
μ
i
∙
D
n
i
t
, where μi is the expectation of the reward
r
i
(
t
)
; F is the cumulative function of D(s) and is expressed as in Definition 3, notice that in the demonstration of the theorem 4, F is assumed to be Lipschitz; Theorem 1: the optimal policy in any time π∗ consists in always playing the arm i∗ ∈ {1, …, K} with largest expected reward:
i
*
=
a
r
g
m
a
x
1
≤
K
μ
i
∙
D
n
i
t
, where μi is the expectation of the reward
r
i
(
t
)
; demonstrate in lemma 1 that an optimal policy π cannot attend the optimal at t+1 if it is not optimal at time t and which means that the optimal policy has to select at each time the optimal arm; Theorem 2: for the bandit problem with known trend, the accumulated expected regret R for any policy φ and any horizon T is lower bounded by
1
m
a
x
i
μ
i
D
m
a
x
∑
i
:
n
i
T
>
n
i
*
T
E
n
i
T
-
n
i
*
T
≤
E
R
T
; to adapt the UCB algorithm for the news setting, the proposed A-UCB algorithm (Algorithm 1) computes at each trial t an index
I
i
=
μ
^
i
+
c
i
∙
D
n
i
t
for each arm i, where c(i) is the corresponding confidence interval, so that
c
i
=
2
×
l
o
g
t
n
i
t
; the UCB index is multiplied by
D
n
i
t
to stop playing the supposed optimal arm when its rewards become suboptimal.; for the bandit problem with known trend, the accumulated expected regret R of A-UCB policy is bounded by
E
R
T
≤
m
a
x
i
μ
i
D
m
a
x
∑
i
:
n
i
*
T
>
n
i
T
8
l
n
T
∆
'
i
2
+
K
π
2
3
, where
∆
i
'
=
D
m
i
n
D
m
a
x
μ
i
t
*
-
μ
i
t
with Dmin and Dmax two Lipschitz constants; the Action elimination (AE) algorithm attempts to sample each arm a minimal number of times and eliminate the arms one after the other; however in our case a sub optimal arm at time t can be optimal arm at time t+1 and applying AE can eliminate the future optimal arms; to adapt the AE algorithm to our setting, the proposed A-AE (Alg. 2) algorithm compute the
μ
^
m
a
x
∙
D
n
i
T
-
μ
^
i
∙
D
n
i
T
rather than
μ
^
m
a
x
-
μ
^
i
for the arm elimination; for the bandit problem with known trend, the accumulated expected regret R of A-AE policy is bounded by
∑
t
=
1
T
r
e
g
r
e
t
t
≤
∑
i
=
2
n
l
o
g
T
δ
∆
i
'
∆
i
'
with
∆
'
=
D
m
a
x
D
m
i
n
μ
^
i
*
-
μ
^
i
; using Beta prior and considering the Bernoulli bandit problem (the rewards are either 0 or 1), Thompson Sampling (TS) initially assumes arm i to have prior Beta(1, 1) on μi (the probability of success); at time t, having observed Si(t) successes (reward = 1) and Fi(t) failures (reward = 0) in θi(t) = Si(t) + Fi(t) selects of document i, the algorithm updates the distribution on μi as Beta(Si(t)+1, Fi(t)+1); the algorithm then generates independent samples from these posterior distributions of the μi, and selects the document with the largest sample value μi; to adapt the TS sampling for our setting, propose A-TS (Algorithm 3), this algorithm multiply θi(t) by D(ni(t)) to stop playing the supposed optimal arm when its rewards start to decrease; for the bandit problem with known trend, the total regret in time T for A-TS is bounded by
E
R
T
≤
1
∆
i
'
-
ϵ
2
l
g
1
T
+
8
l
n
T
∆
'
i
2
+
1
+
π
2
3
+
O
(
1
)
) or (Bouneffouf'2017, Section III of Pages 2-4: in the MAB setting, to maximize his gain the player has to find the best arm as soon as possible, and then exploit it; in our setting, the rewards follow a known function; when the player has found the best arm, he knows that this arm will be the best just for a certain period of time; the player needs to re-explore at each time to find the next best arm; in the MAB setting, to maximize his gain the player has to find the best arm as soon as possible, and then exploit it; in our setting, the rewards follow a known function; when the player has found the best arm, he knows that this arm will be the best just for a certain period of time; the player needs to re-explore at each time to find the next best arm; let ri(1), …, ri(n) be a sequence of independent draws of the random variable ri ∈ [0, 1] with n the number of trials and let μi = E[ri] be its mean reward; at each time t, the player chooses an arm i ∈ {1, …, K} to play according to a (deterministic or random) policy φ based on sequence of plays and reward, and obtains a non-stationary reward z(t) where
z
t
=
r
i
t
(
t
)
∙
D
(
n
i
t
(
t
)
)
, where
D
(
n
i
t
(
t
)
is a trend reward function assumed to be known,
n
i
t
(
t
)
is the number of times i is played and
r
i
t
(
t
)
is the stationary reward for arm i at time t; a dynamic policy can be defined as function such that (φ : t
↦
n1(t), …, nK(t)) or φ : Ht−1
↦
K, where Ht−1 is the history of rewards known at time t; by applying a policy φ, at t a sequence of choices obtained (1, 2, …, t) ∈ [K]t; at time t, the gain of the policy φ is:
G
φ
t
=
∑
t
z
t
=
∑
t
r
i
t
t
D
n
i
t
t
; the performance of a policy φ is measured in terms of regret in the first T plays, which is defined as the expected difference between the total rewards collected by the optimal policy φ∗ (playing at each time instant the arm i∗ with the highest expected reward) and the total rewards collected by the policy φ; the objective is to minimize the regret R(T) at time T, where T is the time horizon; the expected regret after T plays is defined in Definition 1 as the difference between the optimal gain expectation and the expected gain got by the policy φ; note that we distribute the expectation because
r
i
t
(
t
)
and
n
i
t
(
t
)
are independent; the optimal policy in any time φ∗ consists in always playing the arm i∗ ∈ {1. …, K} with largest expected reward:
i
*
=
a
r
g
m
a
x
i
μ
i
∙
D
n
i
t
, where μi is the expectation of the reward
r
i
(
t
)
; F is the cumulative function of D(s) and is expressed as in Definition 3, notice that in the demonstration of the theorem 1, F is assumed to be Lipschitz; to adapt the UCB algorithm for the news setting, the proposed A-UCB algorithm computes at each trial t an index
I
i
=
μ
^
i
+
c
i
∙
D
n
i
t
for each arm i, where c(i) is the corresponding confidence interval, so that
c
i
=
2
×
l
o
g
t
n
i
t
; The UCB index is multiplied by
D
n
i
t
to stop playing the supposed optimal arm when its rewards become suboptimal; the A-UCB algorithm is shown in Algorithm 1; for the bandit problem with known trend, the accumulated expected regret R of A-UCB policy is bounded by
E
R
T
≤
m
a
x
i
μ
i
D
m
a
x
∑
i
:
n
i
*
T
>
n
i
T
8
l
n
T
∆
'
i
2
+
K
π
2
3
, where
∆
i
'
=
D
m
i
n
D
m
a
x
μ
i
t
*
-
μ
i
t
with Dmin and Dmax two Lipschitz constants).
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Upadhyay (US 2021/0065897 A1, pub. date: 03/04/2021) discloses in ABSTRACT and ¶¶ [0003], [0006]-[0010] and [0050]-[0077] that (1) obtaining a feature vector characterizing a system to be analyzed via online partially rewarded machine learning; (2) based on the feature vector, making a decision, via the machine learning, using an online policy; (3) observing the system for environmental feedback; (3) in at least a first instance, wherein the observing indicates that the environmental feedback is available, obtaining the environmental feedback; (4) in at least a second instance, wherein the observing indicates that the environmental feedback is missing, imputing the environmental feedback via an online imputation method; (5) updating the online policy based on results of the obtained environmental feedback and the online imputation method; (6) outputting a decision based on the updated online policy; (7) providing enhanced accuracy including, e.g., improving reward and/or reducing regret; (8) providing enhanced learning for the same number of samples as compared to prior art techniques so desired level of accuracy can be achieved with fewer samples, thus, reducing CPU time to achieve desired accuracy, thereby improving computer performance of a computer implementing machine learning; (9) using multi-GCN embedded Upper Confidence Bound (GCNUCB) embeddings according to aspects of the invention reduces the dimensionality of the context, enabling faster matrix inversion than LINUCB (Linear Upper Confidence Bound) (an existing method/prior art), thereby reducing computation time and improving computer performance of a computer implementing machine learning; (10) using a GPU for each GCN (GCN=Graph Convolutional Networks) in GCNUCB allows for parallel computation, reducing computation time and improving computer performance of a computer implementing machine learning; (11) GCNUCB synthesizes elements of semi-supervised Graph Convolutional Neural Networks (GCNs) and the contextual "bandit" algorithm LINUCB (Linear Upper Confidence Bound) to solve the OPR problem; (12) as in the general case, a feature vector is input to the system and the output is an action and/or decision; (13) in a first step, retrieve the GCN embedding of the feature vector and pass this embedding to LINUCB to make a decision; (14) in a second step, observe the environmental response and/or feedback; if missing, employ GCN to impute response and/or feedback; (15) in a third step, update LINUCB with environmental or imputed response and/or feedback; and update the GCN with the environmental response; (16) address a new problem at the intersection of semi-supervised learning and contextual "bandits," useful for a number of applications including clinical trials and advertisement recommendations; (17) a Graph Convolutional Network (GCN), a semi-supervised learning approach, can be adjusted to the new problem formulation; (18) provide a variant of the linear contextual bandit with semi-supervised missing rewards imputation and establish imputation-agnostic regret bounds; (19) aspects of both approaches are combined in to provide a multi-GCN embedded contextual "bandit"; (19) consider the problem of Online Partially Rewarded (OPR) learning, which poses a synthesis of the challenges often considered in the semi-supervised and contextual "bandit" literature; (20) in clinical trials, reward is partial, as patients may not return for follow-up evaluation; (21) when patients do return, if feedback on their treatment is negative, the best treatment, or true label, remains unknown and the only available information is a reward of 0 for the treatment administered; (22) the "multi-armed bandit" problem provides a solution to the exploration versus exploitation trade-off, informing a player how to pick within a finite set of decisions while maximizing cumulative reward in an online learning setting; (23) in Linear Upper Confidence Bound (LIN-UCB) and in Contextual Thompson Sampling (CTS), a linear dependency is assumed between the expected reward of an action and its context; the representation space is modeled using a set of linear predictors; (24) in some applications, reward may not be available at every step t, hence adjust the LINUCB algorithm to learn from data with missing rewards; and (25) combine LINUCB with a user-defined imputation mechanism for the reward when environment response is missing.
Li et al. ("Provably Optimal Algorithms for Generalized Linear Contextual Bandits", arXiv:1703.00048v2, Jun 18, 2017, pp. 1-17) discloses in ABSTRACT and Section 1 of Pages 1-2 that (1) generalized linear models (logistical regression in particular) have demonstrated stronger performance than linear models in many applications where rewards are binary; (2) however, most theoretical analyses on contextual bandits so far are on linear bandits; (3) in this work, we propose an upper confidence bound based algorithm for generalized linear contextual bandits, which achieves an
O
~
d
T
regret over T rounds with d dimensional feature vectors; (4) this regret matches the minimax lower bound, up to logarithmic terms, and improves on the best previous result by a
d
factor, assuming the number of arms is fixed; (5) a key component in our analysis is to establish a new, sharp finite-sample confidence bound for maximum-likelihood estimates in generalized linear models, which may be of independent interest; (6) we also analyze a simpler upper confidence bound algorithm, which is useful in practice, and prove it to have optimal regret for certain cases; (7) study the following stochastic, K-armed contextual bandit problem: (a) suppose at each of the T rounds, an agent is presented with a set of K actions, each of which is associated with a context (a d-dimensional feature vector); (b) by choosing an action based on the rewards obtained from previous rounds and on the contexts, the agent will receive a stochastic reward generated from some unknown distribution conditioned on the context and the chosen action; and (c) the goal of the agent is to maximize the expected cumulative rewards over T rounds; (8) we therefore consider generalized linear models (GLM) in the contextual bandit setting, in which linear, logistic and probit regression serve as three important special cases; and (9) propose a GLM version of the UCB algorithm called SupCB-GLM that achieves a regret over T rounds of order
O
~
d
T
;
Any inquiry concerning this communication or earlier communications from the examiner should be directed to HWEI-MIN LU whose telephone number is (313)446-4913. The examiner can normally be reached Mon - Fri: 9:00 AM - 6:00 PM EST.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Mariela D. Reyes can be reached at (571) 270-1006. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/HWEI-MIN LU/Primary Examiner, Art Unit 2142
Prosecution Insights