Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors propose a new penalization framework for the stochastic multi-armed bandit problem with fairness constraints. They formalize the penalized regret to evaluate the performance of bandit algorithms under this setting. They propose a hard-threshold UCB algorithm and provide its gap-dependent/independent regret bounds. Experiments on synthetic data show its superiority over other existing methods.
main_review: Strengths:
1. The authors propose a new framework with penalty terms to model fairness constraints, which is different from previous fairness MAB formulations.
2. The proposed penalized regret (Eq.(10)) helps justify the tradeoff between reward and fairness.
3. Both upper and lower regret bounds of the hard-threshold UCB algorithm are provided.
4. Experimental results are consistent with the theoretical findings and show the superiority of the proposed algorithm over other methods.

Weaknesses:
1. Motivation. Although the proposed penalization framework makes sense, it is unclear why we need this new framework. Is it just another way to model the fairness MAB? Does it have any advantages over other formulations? Some motivating examples/applications might be helpful.
2. The idea behind the hard-threshold UCB algorithm seems to be very straightforward: just adding penalty terms to the original UCB values to favor arms that have not satisfied the fairness requirements.
3. For the gap-dependent upper bound in Theorem 2, is it possible to remove the assumption that $\Delta_k \ge 4\sqrt{\frac{\log T}{\tau_k T}}$? Otherwise, I think the regret upper bound without this assumption will depend on $4\sqrt{\frac{\log T}{\tau_k T}}$, then it becomes unclear how $\tau_k$ would affect the regret (i.e., smaller $\tau_k$ might incur larger regret).
4. There is a gap between the upper bound $O(T^{2/3})$ in Theorem 4 and the lower bound $O(\sqrt{T})$ in Theorem 7. Though the authors said it is an open question to improve the gap-independent to be $O(\sqrt{T})$, IMHO, the $O(T^{2/3})$ upper bound is typical for ETC (Explore-Then-Commit) algorithms but not UCB-type algorithms. A natural question that arises: is it possible to modify the ETC algorithm to achieve the same regret bound as the hard-threshold UCB algorithm?
5. The experiments are only running on small synthetic data. It is better to show some experiments with real-world data.

summary_of_the_review: This paper introduces a new penalization framework for the fairness MAB problem. The authors propose a UCB-type algorithm with theoretical guarantees. From the technical perspective, my main concerns are: 1) relatively simple algorithm design; 2) some issues of the regret analysis. Besides, the motivation for introducing such a new framework and its potential real-world applications are unclear in the current version.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors deal with the stochastic multi-armed bandit problem with constraints in the least number of arms pulls for fairness. They convert such a problem into the unconstrained but penalized version. Then, they propose the hard-threshold UCB algorithm with the analyses of its gap-dependent and -independent regrets. The lower bounds on these regrets of the present algorithm.
main_review: Strength:
- The authors propose a novel algorithm for the penalized variant of the fair MAB problem with the tight analyses of the gap-dependent and -independent regrets.

Weakness:
- The definition of the fairness constraint is not reasonable.
- The paper lacks the rigorous guarantee of fairness.


I recommend the rejection of this paper due to the lack of a reasonable fairness guarantee. 

First of all, the main issue of this paper is the problem formulation in Eq. 2, particularly its constraints. The constraints require the algorithm to pull each arm at least the specified times ONLY AT THE END OF ROUNDS. Indeed, we can easily come up with a trivial solution to this problem:
1. Pull each arm $\lceil\tau_kT\rceil$ times.
2. Conduct the optimal algorithm for the unconstrained MAP problem.

Unlike Eq. 2, the existing work, Patil et al. 2020, employs the constraint of anytime guarantee of fairness.  That is, the algorithm needs to pull each arm at least the specified fraction of times FOR ANY ROUND. 

The MAB with the penalized reward in Eq. 3 might be a proxy for solving the MAB with the anytime guarantee of fairness. That is, the proposed algorithm has a chance to guarantee the anytime guarantee of fairness. However, it is necessary to analyze and demonstrate the rigorous guarantee of fairness. 

The claims regarding the lower bound are somewhat incorrect. In the introduction, the authors mention the optimality of the obtained regret. However, what the authors analyzed is the lower bounds on the regrets of the present algorithm and is not the lower bounds on the regrets of any algorithm. Hence, while the lower bounds indicate the tightness of the bounds, they do not reveal the optimality of the bounds.
summary_of_the_review: I recommend the rejection of this paper due to the lack of a reasonable fairness guarantee.  See the detailed comment.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper examines the problem of reward maximization in a Multi-Armed Bandit, with the additional fairness constraint that each arm should be pulled for at least a fraction of time. The authors propose and analyze an algorithm where the UCB index of an arm $i$   is increased by a specified amount (which is a parameter for the algorithm) $A_i$ for the time instances where the arm is lagging behind the fairness constraint. Results about the asymptotic satisfaction (or not) of the fairness constraints depending on the relationship between $A_i$ and the suboptimality gap of each arm are given, as well as results about the gap-dependent and gap-independent regret of the studied algorithm under a modified reward with the threshold (that is, a cost $A_i$ is given to all arms $i$ that do not satisfy the fairness constraints at time $t$). This algorithm is also compared with two recent state of the art algorithms for this problem in synthetic examples and illustrates superior performance.   
main_review: - Strengths: 
  -  The idea of the algorithm is quite intuitive, however seems novel (not been proposed and analyzed in the literature). 
  -  The analysis is thorough and rigorous.  

- Weaknesses: 
  - It is crucial to select a penalty $A_i$ larger than the suboptimality gap of arm $i$ ; otherwise, this arm will only get pulled for a number of epochs logarithmic  to the horizon $T$, therefore totally failing the fairness constraint. 
  - Comparison with the state of the art is rather weak. First, comparing them with respect to the penalized regret is unfair to the baselines, as they are not optimized against it and the penalties here serve more as a way to ensure the fairness constraints than an end to themselves; A more illustrative comparison would be to compare the "unfairness" and "normal" regret (without the penalties) of each algorithm. Second, when comparing for different values of the scale parameter, $\eta$, the threshold and weight in FLearn and LFG, respectively, both scale with the horizon $T$; this means that, in values of $\eta$ not close to $1$, the parameters of these algorithms are too large. Experiments with a more reasonable range for the parameters of the state of the art need to be presented.  

- Additional Comments: 
   - It would be nice to have a comparison on the theoretical results on regret (without the penalty) and unfairness of the proposed algorithm and the two baselines (e.g. the scalings with $T$ in some table). 
   - It would also be nice to have more details in the figure captions on what the figure is showing - for instance, what is the setting for each row of plots. 
summary_of_the_review: A solid analysis of a novel and intuitive algorithm for the MAB problem under a type of fairness constraints, however the comparisons with related work are rather weak.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies one variant of fair multi-armed bandit (MAB) problem: For each arm $k$ played, there is a known fairness parameter $\tau_k$, which gives the fraction of times that this arm should be played, and if the total time $k$ is played by time horizon $T$ is less than $\tau_k T$, a penalty $A_k$ is added to the regret term for each insufficient play. The authors propose a hard-threshold UCB-based algorithm, provide its gap-dependent and gap-independent regret bounds, and show that the gap-dependent bound almost matches the lower bound, while the gap-independent bound has a significant difference between the lower bound --- the lower bound is $O(T^{1/2})$ while the current upper bound is $O(T^{2/3})$.

main_review: Strength of the paper

- Considering fairness in MAB is an important direction, and the current paper studies the variant where the fairness consideration is put into the objective function as a penalty, in contrast with the previous study that treat it as a hard constraint.

- The paper proposes a hard-threshold UCB-based algorithm with regret analysis and empirical good performance.

Weakness of the paper

- The gap-independent regret upper bound of the algorithm has a large gap comparing to the lower bound. It is unclear from the discussion in the paper whether it is due to the analysis or the algorithm. This indicates that the current result of the paper is still transitional.

- The authors do not discuss why they chose this fairness model while there are other fairness model in the literature. There is no application motivation discussed, so it is unclear to the readers what kind of applications are suitable for their model.

- There is no proof outline in the main text for either the upper bounds or the lower bounds, so it is unclear how the analysis deals with the new challenges in the new setting. There is only one short paragraph on "technical challenges" for the upper bound, but it only says the term $(\tau_k T - N_k(T))_{+}$ should be treated carefully, but does not say anything on how to do it. Even when browsing through the supplementary material, there is no outline highlighting the differences and technical novelty of the analysis. One as to read the 10 page proof in detail to perhaps understand the new technical novelty. Without such explanations, the technical novelty if any will not benefit the readers.


Other issues of the paper:

- Page 2, 3rd paragraph, $N_k t$ should be $N_k(t)$

- Page 2, notations paragraph, the slash between $a \le Cb$ and $a \ge b/C$ is confusing since it looks like a division sign. I guess it means the logical AND.

- Page 3, Equation (4). It is better to put a bracket [ ] after the expectation sign $\mathbb{E}$ and the bracket contains the $( )_+$ inside, otherwise, the subscript $+$ seems to be outside the expectation. This applies also to many other cases in the paper.

- Eq.(5) and the explanation afterwards. 
I feel that it is more direct to explain that Eq.(4) is the reward achieved by a policy $\pi$, and the regret is comparing this reward with the optimal reward achieved by a prophet policy that knows $\mu_i$'s. Eq.(5) gives me the impression that it is comparing against always playing the best arm, which is no longer the best policy under the penalty term, and later I realized that it is just a different way to derive the regret I described above.

- Eq.(6) and the equation above.
Why are there still the expectation sign in the equations? There is no longer randomness in the formula I think.

- Page 5, 2nd paragraph, "By choosing the penalty rate properly"
This expression gives me the impression that we could choose the penalty rate, but it should be given as problem input, not chosen, right?

This is related to the condition $A_k - \Delta_k \ge c_a$ in Theorem 1. I would like to see more discussions on whether this assumption is reasonable, and if there is any thing we can do if the assumption does not hold.

- Page 5, Theorem 2
In the line before the third equation in the theorem, notation $k_j$ seems to be wrong. I guess it should be $k$.

Also, there is a redundant "the" in the second line after the theorem.

- Page 8, Experiment A, Case 3. $A$ should be $A_k$?
summary_of_the_review: The paper has positive contribution to the community on studying the penalty-based fairness condition in MAB, but due to the weakness pointed out, its contribution is limited and is not easy to understand. Therefore, I think it is not a case of clear acceptance, so I give the marginal accept recommendation.
review_title: null

Meta-review: The paper provides an algorithm for the stochastic multi armed bandit (MAB) problem in the regime with fairness constraints. It continues a line of work that in high level define fairness as a requirement to ensure a minimum amount of exploration for every arm.
The main concern I found in the reviews regards the definition of fairness in this paper. Although it follows the same high level narrative of previous works its exact definition and difference from previous papers is not convincingly motivated, and seems to be tailored to the proposed algorithm rather to a real world fairness constraint. This issue could have been mitigated by a novel or generalizable technique, or insightful experiments, but this does not seem to be the case given the reviewers comment about the limited novelty and basic experiments.
Decision: Reject