  The safe linear bandit problem (SLB) is an online approach to linear
programming with unknown objective and unknown roundwise constraints, under
stochastic bandit feedback of rewards and safety risks of actions. We study the
tradeoffs between efficacy and smooth safety costs of SLBs over polytopes, and
the role of aggressive doubly-optimistic play in avoiding the strong
assumptions made by extant pessimistic-optimistic approaches.
  We first elucidate an inherent hardness in SLBs due the lack of knowledge of
constraints: there exist `easy' instances, for which suboptimal extreme points
have large `gaps', but on which SLB methods must still incur $\Omega(\sqrt{T})$
regret or safety violations, due to an inability to resolve unknown optima to
arbitrary precision. We then analyse a natural doubly-optimistic strategy for
the safe linear bandit problem, DOSS, which uses optimistic estimates of both
reward and safety risks to select actions, and show that despite the lack of
knowledge of constraints or feasible points, DOSS simultaneously obtains tight
instance-dependent $O(\log^2 T)$ bounds on efficacy regret, and $\tilde
O(\sqrt{T})$ bounds on safety violations. Further, when safety is demanded to a
finite precision, violations improve to $O(\log^2 T).$ These results rely on a
novel dual analysis of linear bandits: we argue that \algoname proceeds by
activating noisy versions of at least $d$ constraints in each round, which
allows us to separately analyse rounds where a `poor' set of constraints is
activated, and rounds where `good' sets of constraints are activated. The costs
in the former are controlled to $O(\log^2 T)$ by developing new dual notions of
gaps, based on global sensitivity analyses of linear programs, that quantify
the suboptimality of each such set of constraints. The latter costs are
controlled to $O(1)$ by explicitly analysing the solutions of optimistic play.
