Fairness in Learning: Classic and Contextual Bandits *
We introduce the study of fairness in multi-armed bandit problems. Our fairness definition demands that, given a pool of applicants, a worse applicant is never favored over a better one, despite a learning algorithm's uncertainty over the true payoffs. In the classic stochastic bandits problem we provide a provably fair algorithm based on "chained" confidence intervals, and prove a cumulative regret bound with a cubic dependence on the number of arms. We further show that any fair algorithm must have such a dependence, providing a strong separation between fair and unfair learning that extends to the general contextual case. In the general contextual case, we prove a tight connection between fairness and the KWIK (Knows What It Knows) learning model: a KWIK algorithm for a class of functions can be transformed into a provably fair contextual bandit algorithm and vice versa. This tight connection allows us to provide a provably fair algorithm for the linear contextual bandit problem with a polynomial dependence on the dimension, and to show (for a different class of functions) a worst-case exponential gap in regret between fair and non-fair learning algorithms.
This paper also studied the fairness in learning algorithm, along with another submission paper ID 212 which I also reviewed.  Paper ID 212 studied the case with classical multi-armed bandit. This paper considered the more general contextual bandit case, where a contextual bandit algorithm is considered \delta-fair, if it never selects an option with probability strictly greater than another better option.  The paper establish an equivalence between fair contextual multi-armed bandit and the KWIK learning. Roughly speaking, if a function class C is KWIK learnable, then the corresponding fair contextual multi-armed bandit problem can achieves a non-trivial regret after a polynomial number of rounds; and if the fair contextual multi-armed bandit problem admits a non-trivial algorithm, then the function class C is KWIK learnable. The proved guarantee is rather complicated, and indeed establish that these two concept are polynomially related.   In order to show that, the paper first gives a simple algorithm for the fair contextual multi-armed bandit problem. The idea is very simple, it associates a learner with carefully chosen parameters for each arm, and then it use the learners to provide a confidence range for each arm. In order to be fair, the algorithm treat all arms with overlapping confidence range as equal, and thus crate an equivalence class between the arms. Then it pick a random arm within the equivalent class containing the arm with highest upper range, and feed a sample to that.  There are some technical points like rolling back the history for the learner in order to deal with the bandit feedback setting, but overall the algorithm is intuitive and elegant.  Then the paper gives an algorithm for KWIT using a fair contextual multi-armed bandit problem as a subroutine. The high-level idea is that intuitively, since the algorithm is fair, it can only exploit if it is quite certain about the hidden function f. The reduction is also straightforward and the analysis is elegant.  
Technical quality:  I am confident that the results are correct.  But there are some issues in the proof. The (b) part in Lemma 1 seems not right, it should be the total number of times that s_i^t is not I don't know and i does get sample instead of the stated one, which seems wrong to me. Also, in Lemma 1 it says arm j but it use i later.  But the above issue does not affect the validity of the later proof, as it uses the right version. But this somehow makes me misunderstand something when I first read that.  Novelty/originality:  The study of the fairness in learning seems both interesting and of practical importance to me. And their definition is clearly original.  The connection between fair contextual multi-armed bandit and KWIK learning is a fantastic result. It is also nice to know that there is an exponential separation between fair and non-fair algorithm when considering the contextual problems.  Potential impact or usefulness:  I expect that this paper along with the author's another paper 212 will influence a number of future works in addressing the fairness concern in learning: i.e., maybe their definition can be applied to settings other than contextual multi-armed bandit, or it can inspired some other definition of fairness in learning, which has a weaker impact on the regret achievable.  Clarity and presentation:  The paper is generally well-written, but there are many typos/errors in some part of the paper.  A partial list of typos/errors:  As said before, the statement for Lemma 1 is not correct and need to be fix.  In line 15 of the KWIKTOFAIR algorithm, it should be "update the history for L_{j*}"  One Line 230, the total regret should be 2k\eps^* \cdot T + n +\delta T.  On the first line on page 6, n_i seems to mean the number of rounds that arm i outputs I don't know, instead of "some arm".  There is a unnecessary ) in the equation after line 237.  On line 9 of the FAIRTOKWIK algorithm, the x in A(h^t,x^t,x) should be x(\hat{\elk}).  I feel like the submission still needs some revisions.