- 45 views
- 70 downloads
Perturbed History Exploration in Stochastic Subgaussian Generalized Linear Bandits
-
- Author / Creator
- Liu, Shuai
-
We consider stochastic generalized linear bandit (GLB) problems when the reward distributions are log-concave and subgaussian. We consider for this problem the perturbed history exploration (PHE) algorithmIn each round of its operation, PHE perturbs the observed rewards by adding fresh noise to them, fits a model to this perturbed data and selects the arm that has the highest reward according to the fitted model. The appeal of PHE is that it is efficient whenever model fitting and best arm selection enjoy efficient im- plementations. In this thesis, we present a refinement of the basic perturbed history exploration (PHE) algorithm, whereas the perturbations are adapted to the structure of GLBs. Our main result is a novel bound on the regret of the resulting algorithm. Building on an idea that was worked out for stochastic lo- gistic bandits, a special case of GLBs, we prove that the negative log-likelihood function on the observed data is a generalized self-concordant function. This allows us to obtain regret bounds that extend previous state-of-the-art results from special GLBs to our setting, achieving a new state-of-the-art. Finally, to reduce the computation cost, we present a rarely-switching variant of PHE. The resulting method is shown to suffer a small constant-factor multiplicative increase of the regret. To the best of the author’s knowledge, this is the first result that shows that randomized algorithms can also be sped up by reducing the frequency with which they update what action should be played.
-
- Subjects / Keywords
-
- Graduation date
- Fall 2023
-
- Type of Item
- Thesis
-
- Degree
- Master of Science
-
- License
- This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.