# Adversarial Combinatorial Bandits with General Non-linear Reward Functions

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 29 references that are in the map.
- First posted on arXiv 5 Jan 2021.

## Builds on (most cited first, 12 of 12)

- [Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms](https://mlsanity.com/paper/1407.8339/) (2014)
- [Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/1803.04623/) (2018)
- [Combinatorial Multi-Armed Bandit with General Reward Functions](https://mlsanity.com/paper/1610.06603/) (2016)
- [MNL-Bandit: A Dynamic Learning Approach to Assortment Selection](https://mlsanity.com/paper/1706.03880/) (2017)
- [Thompson Sampling for the MNL-Bandit](https://mlsanity.com/paper/1706.00977/) (2017)
- [Learning Mixtures of Gaussians in High Dimensions](https://mlsanity.com/paper/1503.00424/) (2015)
- [Top-k Combinatorial Bandits with Full-Bandit Feedback](https://mlsanity.com/paper/1905.12624/) (2019)
- [Tight Lower Bounds for Combinatorial Multi-Armed Bandits](https://mlsanity.com/paper/2002.05392/) (2020)
- [Batch-Size Independent Regret Bounds for the Combinatorial Multi-Armed Bandit Problem](https://mlsanity.com/paper/1905.03125/) (2019)
- [Polynomial-time Algorithms for Multiple-arm Identification with Full-bandit Feedback](https://mlsanity.com/paper/1902.10582/) (2019)
- [An Optimal Policy for Dynamic Assortment Planning Under Uncapacitated Multinomial Logit Models](https://mlsanity.com/paper/1805.04785/) (2018)
- [Dynamic Assortment Selection under the Nested Logit Models](https://mlsanity.com/paper/1806.10410/) (2018)

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

- [Multi-Armed Bandits with Interference](https://mlsanity.com/paper/2402.01845/) (2024)
- [Nearly Minimax Optimal Submodular Maximization with Bandit Feedback](https://mlsanity.com/paper/2310.18465/) (2023)
- [Combinatorial Bandits under Strategic Manipulations](https://mlsanity.com/paper/2102.12722/) (2021)
- [Global Rewards in Restless Multi-Armed Bandits](https://mlsanity.com/paper/2406.00738/) (2024)
- [Offline Learning for Combinatorial Multi-armed Bandits](https://mlsanity.com/paper/2501.19300/) (2025)
- [Graph-Dependent Regret Bounds in Multi-Armed Bandits with Interference](https://mlsanity.com/paper/2503.07555/) (2025)
- [Contextual Multinomial Logit Bandits with General Value Functions](https://mlsanity.com/paper/2402.08126/) (2024)
- [Optimal Arm Elimination Algorithms for Combinatorial Bandits](https://mlsanity.com/paper/2510.23992/) (2025)
- [No-Regret Mnatural-Concave Function Maximization: Stochastic Bandit Algorithms and Hardness of Adversarial Full-Information Setting](https://mlsanity.com/paper/2405.12439/) (2024)
- [Adversarial Combinatorial Semi-bandits with Graph Feedback](https://mlsanity.com/paper/2502.18826/) (2025)
- [Trading Off Resource Budgets for Improved Regret Bounds](https://mlsanity.com/paper/2210.05789/) (2022)
- [Logarithmic Regret for Unconstrained Submodular Maximization Stochastic Bandit](https://mlsanity.com/paper/2410.08578/) (2024)
- [A Resilience Framework for Bi-Criteria Combinatorial Optimization with Bandit Feedback](https://mlsanity.com/paper/2503.12285/) (2025)
- [Online Learning to Rank under Corruption: A Robust Cascading Bandits Approach](https://mlsanity.com/paper/2511.03074/) (2025)

## Abstract (arXiv)

In this paper we study the adversarial combinatorial bandit with a known non-linear reward function, extending existing work on adversarial linear combinatorial bandit. The adversarial combinatorial bandit with general non-linear reward is an important open problem in bandit literature, and it is still unclear whether there is a significant gap from the case of linear reward, stochastic bandit, or semi-bandit feedback. We show that, with N arms and subsets of K arms being chosen at each of T time periods, the minimax optimal regret is widetildeThetad(√Nd T) if the reward function is a d-degree polynomial with d< K, and ThetaK(√NK T) if the reward function is not a low-degree polynomial. Both bounds are significantly different from the bound O(√poly(N,K)T) for the linear case, which suggests that there is a fundamental gap between the linear and non-linear reward structures. Our result also finds applications to adversarial assortment optimization problem in online recommendation. We show that in the worst-case of adversarial assortment problem, the optimal algorithm must treat each individual binomNK assortment as independent.