Conservative Contextual Linear Bandits
Safety is a desirable property that can immensely increase the applicability of learning algorithms in real-world decision-making problems. It is much easier for a company to deploy an algorithm that is safe, i.e., guaranteed to perform at least as well as a baseline. In this paper, we study the issue of safety in contextual linear bandits that have application in many different fields including personalized recommendation. We formulate a notion of safety for this class of algorithms. We develop a safe contextual linear bandit algorithm, called conservative linear UCB (CLUCB), that simultaneously minimizes its regret and satisfies the safety constraint, i.e., maintains its performance above a fixed percentage of the performance of a baseline strategy, uniformly over time. We prove an upper-bound on the regret of CLUCB and show that it can be decomposed into two terms: 1) an upper-bound for the regret of the standard linear UCB algorithm that grows with the time horizon and 2) a constant term that accounts for the loss of being conservative in order to satisfy the safety constraint. We empirically show that our algorithm is safe and validate our theoretical analysis.
POST-REBUTTAL:
The authors have answered my concerns and will clarify the point of confusion. I'm changing from a marginal accept to an accept.
OLD REVIEW:
Summary of the paper
This paper proposes a "safe" algorithm for contextual linear bandits. This definition of safety assumes the existence of a current "baseline policy" for selecting actions. The algorithm is "safe" in that it guarantees that it will only select an action that differs from the action proposed by the baseline policy if the new action produces larger expected reward than the action proposed by the baseline policy. Due to the random nature of rewards, this guarantee is with high probability (probability at least 1-delta).

Summary of review
The paper is well written. It is an extremely easy read - I thank the authors for submitting a polished paper. The proposed problem setting and approach are novel to the best of my knowledge. The problem is well motivated and interesting. Sufficient theoretical and empirical justifications are provided to convince the reader of the viability of the proposed approach.
However, I have some questions. I recommend at least weak acceptance, but would consider a stronger acceptance if I am misunderstanding some of these points.

Questions
1. Definition 1 defines a desirable performance constraint. The high probability nature of this constraint should be clarified. Notice that line 135 doesn't mention that (3) must hold with high probability. This should be stated.
2. More importantly, the statement of *how* (3) must hold is critical, since right now it is ambiguous. During my first read it sounds like (3) must hold with probability 1-\delta. However this is *not* achieved by the algorithm. If I am understanding correctly (please correct me if I am wrong), the algorithm ensures that *at each time step* (3) holds with high probability. That is:
\forall t \in \{1,\dotsc,T\}, \Pr \left ( \sum_{i=1}^t r_{b_i}^i - \sum_{i=1}^t r_{a_i}^t \leq \alpha \sum_{i=1}^t r_{b_i}^i \right )
NOT
\Pr \left ( \forall t \in \{1,\dotsc,T\},  \sum_{i=1}^t r_{b_i}^i - \sum_{i=1}^t r_{a_i}^t \leq \alpha \sum_{i=1}^t r_{b_i}^i \right )
The current writing suggests the latter, which (I think) is not satisfied by the algorithm. In your response could you please clarify which of these you are claiming that your algorithm satisfies?
3. If your algorithm does in fact satisfy the former (the per-time step guarantee), then the motivation for the paper is undermined (this could be addressed by being upfront about the limitations of this approach in the introduction, without changing any content).
Consider the actual guarantee that you provide in the domain used in the empirical study. You run the algorithm for 40,000 time steps with delta = 0.001. Your algorithm is meant to guarantee that "with high probability" it performs at least as well as the baseline. However, you only guarantee that the probability of playing a worse action will be at most 0.001 *at each time step*. So, you are guaranteeing that the probability of playing a worse action at some point will be at most 1-.999^40000 = (approximately) 1. That is, you are bounding the probability of an undesirable event to be at most 1, which is not very meaningful. This should be discussed.
For now, I would appreciate your thoughts on why having a per-step high probability guarantee is important for systems where there are large numbers of time steps. If a single failure is damning then we should require a high probability guarantee that holds simultaneously for all time steps. If a single failure is not damning, but rather amortized cost over over thousands of time steps is what matters, then why are we trying to get per-time step high probability guarantees?