A Smoothed Analysis of the Greedy Algorithm for the Linear Contextual Bandit Problem
Bandit learning is characterized by the tension between long-term exploration and short-term exploitation. However, as has recently been noted, in settings in which the choices of the learning algorithm correspond to important decisions about individual people (such as criminal recidivism prediction, lending, and sequential drug trials), exploration corresponds to explicitly sacrificing the well-being of one individual for the potential future benefit of others. In such settings, one might like to run a "greedy" algorithm, which always makes the optimal decision for the individuals at hand -but doing this can result in a catastrophic failure to learn. In this paper, we consider the linear contextual bandit problem and revisit the performance of the greedy algorithm. We give a smoothed analysis, showing that even when contexts may be chosen by an adversary, small perturbations of the adversary's choices suffice for the algorithm to achieve "no regret", perhaps (depending on the specifics of the setting) with a constant amount of initial training data. This suggests that in slightly perturbed environments, exploration and exploitation need not be in conflict in the linear setting.
Post Rebuttal:  Thanks for the clarification. You are right about the lemma. Sorry about this. I raised my score correspondingly.  In my defense, it does seem like the lemma can be improved, however. Using the method of mixtures the dependence on d in the square root should disappear. Perhaps there is a small price to pay in the logarithmic term. Here is the brief sketch:  Let eta_1,...,eta_n be a sequence of conditionally 1-subgaussian random variables adapted to filtration (F_t). Then let X_1,...,X_n be a sequence of random elements with X_t in R^d and assume that X_t is F_{t-1}-measurable (that is, (X_t) is (F_t)-predictable).  Let us fix 1 <= i <= d. Since X_{ti} is F_{t-1}-measurable and eta_t is conditionally 1-subgaussian it follows that X_{ti} eta_t is conditionally X_{ti}-subgaussian. Hence  exp(sum_t (L X_{ti} eta_t - L^2 X_{ti}^2 / 2)) is a supermartingale for any L > 0.  Hence Prob(sum_t X_{ti} eta_t >= L sum_t X_{ti}^2 / 2 + log(1/delta) / L) <= delta for any L > 0.  If the X_{ti} where non-random, then you could choose L \approx sqrt(log(1/delta) / sum_t X_{ti}^2). But you can't do this, because it is random. The solution is either the method of mixtures or a covering argument. The first is cleaner (Google it). The covering argument is easier to explain simply.  Since 0 <= sum_t X_{ti}^2 <= n we can take a union bound over all L in some covering set of [0,n] shows that  Prob(sum_t X_{ti} eta_t >= something_1 + sqrt(sum_t X_{ti}^2 log(something_2 /delta)) where something_2 should be a lower degree polynomial of n and something_1 is small due to the approximation error in the covering set.  Now take a union bound over the coordinates and argue symmetrically for the lower tails and you should have something like  |sum_t X_{ti} eta_t| lesssim sqrt(sum_t X_{ti}^2 log(d n / delta))  Hence || sum_t eta_t X_t ||_2^2 <= sum_i sum_t X_{ti}^2 log(dn / delta) = n log(dn/delta).  And so you should have a bound that is O(sqrt(n log(dn / delta))). I did not go back to check how much this would improve the results.  I also encourage you to work hard on motivating the assumptions and correcting the minor notational issues.  Summary.  This paper is about contextual linear bandits. The authors are trying to understand the phenomenon observed in practice that exploration seems much less important than the theory usually suggests. To make a start understanding this they analyze the greedy policy that chooses the arm for which the inner product with the least squares estimator and the context is largest.  With no further assumptions this leads to linear regret. The authors make a 'perturbation' assumption where the contexts are first chosen by an adversary and then perturbed using zero-mean noise. Under carefully chosen assumptions on the noise they show that the greedy algorithm now enjoys O(sqrt(T)) regret.  The two standard settings are studied. (a) where there is one unknown parameter vector and (b) where there is an unknown parameter vector for each action.  The results setting (b) are unsurprisingly much weaker than (a) where some forced exploration of all arms is required. A lower bound is given proving that this is unavoidable for the greedy algorithm. In setting (a) the assumptions on the perturbation distribution ensure the minimum eigenvalue of the design matrix is increasing linearly, which ensures sufficient accuracy of the least-squares estimator.   Quality:  The results seem reasonable in principle. I think there is at least one bug in the proof (see 'Question about Lemma A1' below). It should be fixable with limited loss in the logarithms.  Originality:  Perturbation analysis of this kind is not new, but I think the modifications are interesting enough.   Clarity:  This is a weak point of the paper. There are issues with row/column vectors being mismatched, notation used in multiple different ways. Many unexplained details. Regret bounds and conditions under which they hold are given in Big-O notation and there is no way to see what is the variable of interest. The supplementary material is in better shape than the main body, which is a bit unfortunate. Statements involving probabilities are often a little imprecise and there are many typos. The full paper is also very long. I have to say I did not read all proofs.   Significance:  The difference between practice and theory for contextual bandits is quite large and any attempt to understand this is welcome and potentially significant. For the present article the main issue is the validity of the assumptions. Is the perturbation model reasonable? I did not see that this is addressed anywhere, which is quite unfortunate.   Other comments:  I leave the philosophy to others, but is it not also repugnant and short-sighted to explore suboptimally in clinical trials and then waste the results because the data does not statistically support the hypothesis that the drug works? I thought the point of sequential design was to optimize this process.  Perhaps a better argument is that explicit exploration may actually not be required. That is, explicit exploration is not the enemy, but rather excessive exploration.  Question about Lemma A.1:  The proof of this result does not seem correct. You are right that the coordinates of S_t are rs-subgaussian, but this is much weaker than you need because summing over the squares will give you a bound of sqrt(2trsd log(d/delta)), which has an extra d relative to what you have.  Really what you want to show is that with high probability  sum_{s=1}^t eta_s x^s_i < sqrt(sum_{s=1}^t eta_s (x^s_i)^2 log(1/delta))  Then summing the squares of the coordinates and taking the sqrt will yield your bound. The problem now is that showing the above for arbitrary choices of x the above might not hold. You will need a more sophisticated method such as the method of mixtures and something extra will appear in the logarithm.    Overall I find the paper to be interesting, but suffers from several issues in terms of clarity and motivation for the assumptions. Having found so many issues in the first 20 pages or so it seems the authors should spend more time polishing the article and perhaps consider submitting to a journal where a work of this length might be more appreciated.   Minors:  * Is mathcal H^* defined?  * Supp. First para of proof of Lemma 3.2 there is a missing \Vert  * There seems to be some indecision about what is a column/row vector. Eg., L215 there is ^beta^t x_i^t  * Display after L185. beta e -> beta . e.  * Should say that s-subgaussian means exp(lambda X) <= exp(lambda^2 s / 2) not exp(lambda^2 s^2 / 2)? Unfortunately different authors use different defs (I see it in the supp, but not main)  * Sometimes you write || . || and sometimes || . ||_2 for the Euclidean norm.  * Condition 1 (and elsewhere). You can help the reader by giving domains for variables.  * The wide hats over r-good and r-auspicious don't seem to add anything and look bad.  * Theorem 4.1. The definition of low perturbation regime is given in terms of Big-O notation and the regret here is also Big-O notation. But what is the variable? T? d? The theorem statement should be made rigorous.  * Expectation operators are often used when the underlying measure is unclear and sometimes the notation is really strange (Proof of Lem 3.2 for example).  * Second to last equality in Proof of Lem 3.2. Why is this an equality? Diversity provides a lower bound, no?  * Why is there a t in logarithm in Lemma A.1? The union bound is done coordinate-wise, not over time so it should be log(d/delta).  * Lemma A.2. This proof is missing some expectations. The LHS is a number, but the RHS after the second inequality is a random variables.  * Proof of Lemma 3.1. Is eta^t defined? I suppose it must be the vector of noise up to time t. Note that this lemma probably needs changing if Lemma A.1 is indeed not true. Elsewhere it seems that eta^t is the vector of noise over the coordinates, so this seems like a bit of a mismatch.  * The statement of Corollay 3.1 is a bit weird. Whether or not a certain number of rounds are r-auspicious is itself a random quantity, so the probabalistic quantifier should not come after. Perhaps you need to define an indicator function IND that this number of rounds occurs and then claim that with probability at least 1 - delta it holds that  IND ||beta - ^beta^t|| \leq 32 \sqrt ....  * L223. The probability measure here should be given. This is over the perturbations of the adversary in round t only.