Stage-wise Conservative Linear Bandits
  We study stage-wise conservative linear stochastic bandits: an instance of
bandit optimization, which accounts for (unknown) safety constraints that
appear in applications such as online advertising and medical trials. At each
stage, the learner must choose actions that not only maximize cumulative reward
across the entire time horizon but further satisfy a linear baseline constraint
that takes the form of a lower bound on the instantaneous reward. For this
problem, we present two novel algorithms, stage-wise conservative linear
Thompson Sampling (SCLTS) and stage-wise conservative linear UCB (SCLUCB), that
respect the baseline constraints and enjoy probabilistic regret bounds of order
O(\sqrt{T} \log^{3/2}T) and O(\sqrt{T} \log T), respectively. Notably, the
proposed algorithms can be adjusted with only minor modifications to tackle
different problem variations, such as constraints with bandit-feedback, or an
unknown sequence of baseline actions. We discuss these and other improvements
over the state-of-the-art. For instance, compared to existing solutions, we
show that SCLTS plays the (non-optimal) baseline action at most O(\log{T})
times (compared to O(\sqrt{T})). Finally, we make connections to another
studied form of safety constraints that takes the form of an upper bound on the
instantaneous reward. While this incurs additional complexity to the learning
process as the optimal action is not guaranteed to belong to the safe set at
each round, we show that SCLUCB can properly adjust in this setting via a
simple modification.
