Back to search

Boston University

Constrained learning in the bandit setting: doubly optimistic strategies and fast rates

Abstract

dc:description.abstract

The (stochastic) bandit problem is a classic example used to address the challenge of balancing exploration and exploitation when dealing with bandit feedback. This dissertation focuses on stochastic bandits with constraints, where each action (or arm) bears both a reward and a safety risk. The objective is to maximize rewards while avoiding unsafe options. We explore the application of the optimistic principle in this context. Specifically, we study two performance metrics, the reward regret and the constraint violation. Our formulation penalizes deficit reward and excess risk in a per-round sense, thus pertinent to the safety critical scenario. We propose a doubly optimistic approach that aggressively determines which arms are feasible to be considered, along with several realizations of this strategy to specific scenarios. We instantiate this scheme on the multi-armed bandit, linear bandit, and generalized linear bandit cases. Our findings demonstrate that these algorithms achieve a regret bound that is faster than existing results. For the constrained multi-armed bandit problem, we achieve logarithmic regret for both the reward and safety risk; for linear and generalized linear bandit settings, we carry out a dual analysis based on linear programming sensitivity, identify the discreteness from the continuous problem, and manage to show a logarithmic regret on reward and a log(T) to √T safety violation, which is the best to expect without prior information. The upper bounds are accompanied with lower bounds that are matching in terms of time horizon and gaps. We complement our study with illustrative simulations, and conclude with several future directions.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy
Level thesis:degree_level
doctoral
Discipline thesis:degree_discipline
Electrical & Computer Engineering
Grantor
Boston University
Year dc:date.issued
2024

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Chen, Tianrui
Advisor dc:contributor.advisor
  • Saligrama, Venkatesh

Subjects

dc:subject × 1

Rights

dc:rights
Statement dc:rights
  • Attribution 4.0 International
Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/2144/48856

Chain of custody

source
Harvested from
Boston University
Base URL
open.bu.edu/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Chen, Tianrui. Constrained learning in the bandit setting: doubly optimistic strategies and fast rates. doctoral thesis, Boston University, 2024. https://hdl.handle.net/2144/48856