Toward Realistic Online Learning
Date Issued
2014
Date
2014
Author(s)
Chiang, Chao-Kai
Abstract
We study the online decision problem in which a player iteratively chooses an action and then receives certain loss information from the environment for a number of rounds. The player would like to have an online algorithm that makes it possible to learn from past experiences, make better decisions as time goes by, and achieve small regret which is defined as the difference between the total loss of the algorithm and that of the best fixed action.
Recently, a class of studies consider variants of the Online Convex Optimization (OCO, which is a variant of the classical convex optimization problem) and the Prediction with Expert Advice (PEA, which models an online decision problem in which the set of actions consists of finite number of actions) problems that can be used to model more realistic challenges. In this thesis, we will present our contributions in this direction.
In the first part, we study instances of gradually changing environments in our daily life. We define a new notion that is referred to as the deviation that measures the total difference between consecutive loss functions in order to describe a gradually changing environment. We show that a modification of the well understood FOLLOW THE REGULARIZED LEADER algorithm leads to regret in terms of deviation, thereby implying a small regret for environments with small deviations.
In the second part, we ask the same question in a setting where there is partial information. Our goal is to determine how much information is needed, in situations where the deviation constraint is in effect, in order to obtain regret bounds that are close to the regret bounds that were obtained in our previous study [28]. A novel sampling scheme is designed in order to estimate the unknown gradient information that is needed in order to apply the algorithms that are introduced in [28]. We construct two-point bandit algorithms that are able to achieve regret bounds that are close to the regret bounds from our previous study [28] that were based on the full information setting.
In the third part, we consider the possibility of active players, since there are scenarios where it seems possible for the player to spend some effort or resources to actively collect some intentionally selected information about the loss functions. We describe a new scenario where the player is allowed to actively issue a limited number of queries in order to obtain the loss information she needs in each round before making a decision. This scenario generalizes the previous problem models in which no query is allowed to be issued before a decision is made. We design an algorithm that achieves the regret as a function of the number of bits that can be queried in one round and provide lower bounds showing that the upper bound in general cannot be improved.
In the last part, we study the contextual bandit problem, which is different from the traditional bandit problem, the learner can access additional information about the environment (i.e., context) before making selections. Motivated by the better regret bounds that are available in settings with full information, we create a new notion called pseudo-reward that can be employed for making guesses about unseen rewards and develop a forgetting mechanism for handling fallacious rewards that were computed in the early rounds. Combining the pseudo-rewards and the forgetting mechanism, we propose and analyze a new algorithm called LINPRUCB that is an extension of a state-of-the-art algorithm called LINUCB.
Subjects
線上學習
後悔度
查詢
偏離度
最少訊息
含文意的最少訊息
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-103-D97922013-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):85371bc558ca5b81aabff5101f0540da