ºìÐÓÊÓƵ

Topic

Thresholded Linear Bandits

Department of Computer Science

Date & location

• Thursday, April 17, 2025

• 2:00 P.M.

• Virtual Defence

Reviewers

Supervisory Committee

• Dr. Nishant Mehta, Department of Computer Science, University of Victoria (Supervisor)

• Dr. Yun Lu, Department of Computer Science, UVic (Member) 

External Examiner

• Dr. Nidhi Hegde, Department of Computer Science, University of Alberta 

Chair of Oral Examination

• Dr. Elisabeth Gugle, Department of Economics, UVic 

Abstract

Thresholded linear bandits is a novel bandit problem that lies in the intersection of several important multiarmed bandit (MAB) variants, including active learning, structured bandits, and learning halfspaces. To achieve sublinear regret in the presence of exponentially many arms, one method is to exploit the structure of the reward function. However, the presence of an unknown threshold component makes previously known algorithms for structured bandits unsuitable. Moreover, the threshold introduces a discontinuity to the reward function, making the problem significantly more difficult. In this thesis, we study the union of axis parallel halfspace variant of the thresholded linear bandits problem. We suggest an algorithm that achieves sublinear regret and provide theoretical guarantees on the performance of the algorithm.