Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper considers contextual bandits with concave rewards where the rewards are defined by a concave objective function with stochastic reward vectors. This setting removes the restrictions on the policy space compared to prior works. Under this setting, this paper proposes an (first) algorithm with the vanishing regret. The theoretical results and techniques could be applied to fair ranking problems. Experimental results also support the derived results. 

strength_and_weaknesses: This paper is well written. The model (setting) in this paper is interesting, well motivated (based on the provided concrete examples) and more general compared to prior works. The geometric interpretation of CBCR (policy space spanned by a convex set) is a nice explanation and illuminates the optimization directions. This paper provides a nice and elegant reduction from CBCR regret to a scalar-reward bandit problem based on Frank-Wolfe analysis. This bypasses the core challenges in optimization in policy space. However, it is not clear  (at least to the reviewer) whether the obtained regret for CBCR (under this specific setting) is optimal or not. This paper lacks analysis and explanation in this aspect. 

clarity,_quality,_novelty_and_reproducibility: The paper talks about interesting and important topics related to the general concave bandit problem with good quality and clarity. The idea is novel as far as I know together with the techniques (not original but nice apply).  

summary_of_the_review: Overall, I think that the studied model in this paper is well-motivated with more general problem setting. The proposed algorithm is sound  together with the related analysis. Therefore, I recommend “accept”.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies a contextual bandit problem with **stationary** context and **fixed** action set. At each step, the environment randomly selects a context $x$, then the player needs to choose an action $a$ that maximizes $f(\mu(x)a)$ where $f(\cdot)$ is a known concave function and $\mu$ is an unknown matrix-valued function. This paper solves this problem by nesting Frank-Wolfe algorithm with standard linear/contextual bandit algorithms.

strength_and_weaknesses: 
### Strength

The paper provides a new setting, designs a new algorithm, proves its theoretical guarantee, and conducts experiments on real-world data to validate its performance. The paepr is rather complete for this problem.

### Weakness

By considering only the stationary context set and fixed action set, the paper is actually more restrictive than most contextual bandit literature that considers possibly adversarial context sets. In particular, the paper shall not claim at the end of Sec. 2 that it "subsumes classical contextual bandits." Also, the "reduction" in Sec. 3.2 is not that rigorous because LinUCB and SquareCB both work for adversarial contexts, meaning that the reduction cannot be understood as that the algorithm in the paper could replace LinUCB or SquareCB. Consequently, I am concerned on the impact of this paper over the bandits learning society.

The paper does not contain much technical novelty that could possibly inspire future work, as the proof seems to be a straightforward combination of Frank-Wolfe algorithm.

clarity,_quality,_novelty_and_reproducibility: 
The paper refers to $\mu(x_t)a_t$ as "reward" and defines regret as the difference between $f(\text{reward})$ and the best $f(\text{reward})$. This is different from the classical way of defining regret as the difference of reward and may confuse some readers.

Apart from this, the paper is generally well-written and I did not find any apparent typos in main text. Some LaTeX errors in appendix need be fixed, e.g., Lemma ?? in page 25.

The paper appears to supplement enough details for reproduce the results, including the code. I did not run the code, though.

summary_of_the_review: 
The setting does not sound interesting or important to me. Besides, I have some concerns as prescribed in "Weakness" section.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper considers contextual bandits with multi-dimensional rewards, with a known concave function that transforms the cumulative multi-dimensional rewards to a one-dimensional value to be maximized. This paper proposes a method to reduce the CBCR problem to scalar-reward bandits which has been extensively studied, so that no restrictions necessary on the policy space. Also, a smoothing technique is provided in case of non-smooth concave function $f$. Then, the paper introduces an application using their reduction method, which focuses on contextual ranking bandits with fairness-aware objectives, and shows that their method is efficient with regret guarantee. Experimental evaluations are presented.
strength_and_weaknesses: Strengths:
* This paper proposes an interesting method to reduce CBCR problem to a studied problem, being the first to remove restrictions on the policy space.
* The reduction method has some generality to cover a class of applications that can be modeled by CBCR framework, such as the fair ranking problem mentioned in the paper.

Weaknesses:

Overall, I believe this is a high-quality paper, which has some solid contributions that may benefit future works. Here, I have some minor suggestions and questions:
* In the ``setting'' paragraph in Section~2, the reward is defined as a noisy multi-dimensional reward. I would suggest authors to further declare the noise, e.g., the support of the random noise; the restrictions on the distribution; is it heavy tailed? As the distribution of the noise can heavily affect the policy design, even it may have zero mean. Or, if the only requirement of the noise is zero mean in this work, please also mention that.
* Throughout the paper, the concave function $f$ on the reward is assumed as known by the learner, and the reduction also requires the knowledge of $f$. What if $f$ is unknown so that $f(\sum_t r_t)$ is unknown? How much difficulty will be brought to address the CBCR problem with an unknown $f$? As I think an unknown $f$ is more commonly seen in real world. Or, what will be the case if both the reward $r_t$ and $f$ are unknown and we only know $f(\sum_t r_t)$? Nonetheless, both alternative settings can be considered in future works.
clarity,_quality,_novelty_and_reproducibility: This work has good quality in writing and clarity. I have no problem in understanding the ideas. The novelty and contributions are decent to be published.
summary_of_the_review: Overall, I enjoyed reading this work, and I learnt interesting results from it. The idea of the reduction method is novel and general. Related literature is well-discussed in Introduction section.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: Authors provide the first algorithms for provably vanishing regret for Contextual Bandits with Concave Rewards.
strength_and_weaknesses: Strengths:
  * Multi-objective criterion arise frequently in practice.
  * Reduction-based algorithm design maximizes reuse of existing and novel componentry and overall utility of approach.
     * e.g., the discussion mentions constraints (good: reduction to CB-knapsack algos might work).
  * Figure 1 (right) is particularly persuasive.

Weaknesses;
  * FW-LinUCB will give you nice theorems, but composing with the infinite action linear version of square cb[2] will give you an algorithm people will actually want to deploy. 
    * We never use UCB algos in production here because they are not robust to reward feedback delay.
    * You might also find interesting a composition with a smoothed regret variant of square cb for infinite action spaces [3].
  * It's not clear how to elicit the trade-off function in practice.  
    * For example, does the Lin et. al.[1] elicitation technique yield a concave tradeoff function (or, e.g., would preference elicitation be viable over a constrained model class like generalized gini)?

[1] https://arxiv.org/abs/2203.11382

[2] https://arxiv.org/abs/2207.05836

[3] https://arxiv.org/abs/2207.05849
clarity,_quality,_novelty_and_reproducibility: Clarity gets an A+.  Authors cover a *lot* of territory while managing to retain intelligibility and hit the page limit.  Kudos.

Quality and originality also gets an A+.  This is clear improvement over Agarwal 2016.
summary_of_the_review: Exemplary work.

Confidence is just a 3 because I didn't check the proofs.  If I get time I'll circle back to them.  "Math/other details were not carefully checked."
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper considers a new problem: contextual bandits with concave rewards (CBCR) where the rewards are defined by a concave objective function with stochastic reward vectors.  The authors proposed a general reduction from CBCR to scalar-reward bandits and solved the problem by new algorithms combining Frank-Wolfe with existing contextual bandit algorithms.  The authors proved vanishing regret of the proposed solution. The authors also showed that CBCR can be applied to ranking problem with fairness-aware objectives.

Overall, the reviewers appreciate the problem setting and the theoretical analysis of proposed solutions. The application of ranking with fairness of exposure is also an important contribution. The authors are encouraged to include the discussion on novelty and limitation during the response period in the final version. I recommend acceptance.
justification_for_why_not_higher_score: The acceptance can be either as poster or spotlight. The paper could be potentially interesting to many audiences as it considers a general problem (contextual bandits with concave rewards) with popular applications such as fair ranking and beyond.
justification_for_why_not_lower_score: All reviewers appreciate the novel and general problem setting and the theoretical analysis of proposed solutions with high ratings.
Decision: Accept: poster