The “lob-pass” problem and an on-line learning model of rational choice
Naoki Abe, Jun’ichi Takeuchi · 1993
We consider an on-line learning model of rational choice, in which the goal of an agent is to choose its actions so as to maximize the number of successes, while learning about its reacting environment through th$e very sctions.In particular, we consider a model of tennis play, in which the only actions that the player can take are a 'pass' and a 'lob,' and the opponent is modeled by two linear (probabilistic) functions ~'(r) = alr + bl and jp(r) = a2r + ~, specifying the probabllit y that a 10b (and a pass, respectively) will win a point when the proportion of lobs in the put trials is r.We measure the performance of a player in this model by its expected regret, namely how many less points it expects to win as compared to the ideal player (one that knows the two probabilistic functions) ss a function oft, the total number of trials.which is unknown to the player a priori.A&urning that the probabilistic functions satisfy the matching shoulder condition, i.e. f~(0) = ~P (l), we obtain a variety of upper bounds for sssmuptions and restrictions of varying degrees, ranging from o(logt),'o(t*), O(t+), O(t:), O(tf) to O(t$) as well as a matching lower bound of order $l(log t) for the most restrictive case.When the total number of trials t is given to the player in advance, the upper bo~nds can be improved sigrdkantly.