# Contextual bandits with concave rewards, and an application to fair ranking

arXiv: https://arxiv.org/abs/2210.09957 · HTML: https://mlsanity.com/paper/2210.09957/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 52 of its 106 references that are in the map.
- First posted on arXiv 18 Oct 2022.

## Builds on (most cited first, 30 of 52)

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [Fairness of Exposure in Rankings](https://mlsanity.com/paper/1802.07281/) (2018)
- [Fairness-Aware Ranking in Search & Recommendation Systems with Application to LinkedIn Talent Search](https://mlsanity.com/paper/1905.01989/) (2019)
- [Fairness in Recommendation Ranking through Pairwise Comparisons](https://mlsanity.com/paper/1903.00780/) (2019)
- [Equity of Attention: Amortizing Individual Fairness in Rankings](https://mlsanity.com/paper/1805.01788/) (2018)
- [Bandits with concave rewards and convex knapsacks](https://mlsanity.com/paper/1402.5758/) (2014)
- [Linear Contextual Bandits with Knapsacks](https://mlsanity.com/paper/1507.06738/) (2015)
- [Measuring Fairness in Ranked Outputs](https://mlsanity.com/paper/1610.08559/) (2016)
- [Achieving Fairness in the Stochastic Multi-armed Bandit Problem](https://mlsanity.com/paper/1907.10516/) (2019)
- [FairRec: Two-Sided Fairness for Personalized Recommendations in Two-Sided Platforms](https://mlsanity.com/paper/2002.10764/) (2020)
- [Cascading Bandits: Learning to Rank in the Cascade Model](https://mlsanity.com/paper/1502.02763/) (2015)
- [Policy Learning for Fairness in Ranking](https://mlsanity.com/paper/1902.04056/) (2019)
- [Combinatorial Sleeping Bandits with Fairness Constraints](https://mlsanity.com/paper/1901.04891/) (2019)
- [Controlling Fairness and Bias in Dynamic Learning-to-Rank](https://mlsanity.com/paper/2005.14713/) (2020)
- [Degenerate Feedback Loops in Recommender Systems](https://mlsanity.com/paper/1902.10730/) (2019)
- [Learning Fair Policies in Multiobjective (Deep) Reinforcement Learning with Average and Discounted Rewards](https://mlsanity.com/paper/2008.07773/) (2020)
- [Concave Utility Reinforcement Learning: the Mean-Field Game Viewpoint](https://mlsanity.com/paper/2106.03787/) (2021)
- [Evaluating Stochastic Rankings with Expected Exposure](https://mlsanity.com/paper/2004.13157/) (2020)
- [An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives](https://mlsanity.com/paper/1506.03374/) (2015)
- [Fairness of Exposure in Stochastic Bandits](https://mlsanity.com/paper/2103.02735/) (2021)
- [Fair Contextual Multi-Armed Bandits: Theory and Experiments](https://mlsanity.com/paper/1912.08055/) (2019)
- [Preference Exploration for Efficient Bayesian Optimization with Multiple Outcomes](https://mlsanity.com/paper/2203.11382/) (2022)
- [Adversarial Attacks on Linear Contextual Bandits](https://mlsanity.com/paper/2002.03839/) (2020)
- [Reducing Disparate Exposure in Ranking: A Learning To Rank Approach](https://mlsanity.com/paper/1805.08716/) (2018)
- [Fairness in Ranking: A Survey](https://mlsanity.com/paper/2103.14000/) (2021)
- [Contextual Bandits with Large Action Spaces: Made Practical](https://mlsanity.com/paper/2207.05836/) (2022)
- [The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle](https://mlsanity.com/paper/1309.5550/) (2013)

## Built on by (most cited first, 2 of 2)

- [Fairness in Matching under Uncertainty](https://mlsanity.com/paper/2302.03810/) (2023)
- [Fairness in Reinforcement Learning with Bisimulation Metrics](https://mlsanity.com/paper/2412.17123/) (2024)

## Abstract (arXiv)

We consider Contextual Bandits with Concave Rewards (CBCR), a multi-objective bandit problem where the desired trade-off between the rewards is defined by a known concave objective function, and the reward vector depends on an observed stochastic context. We present the first algorithm with provably vanishing regret for CBCR without restrictions on the policy space, whereas prior works were restricted to finite policy spaces or tabular representations. Our solution is based on a geometric interpretation of CBCR algorithms as optimization algorithms over the convex set of expected rewards spanned by all stochastic policies. Building on Frank-Wolfe analyses in constrained convex optimization, we derive a novel reduction from the CBCR regret to the regret of a scalar-reward bandit problem. We illustrate how to apply the reduction off-the-shelf to obtain algorithms for CBCR with both linear and general reward functions, in the case of non-combinatorial actions. Motivated by fairness in recommendation, we describe a special case of CBCR with rankings and fairness-aware objectives, leading to the first algorithm with regret guarantees for contextual combinatorial bandits with fairness of exposure.