Adversarial Combinatorial Bandits with General Non-linear Reward Functions

Xi Chen, Yanjun Han, Yining Wang

Introduction

In the realm of online learning, the combinatorial bandit problem represents a significant challenge: a learner must select a subset of $K$ items from a pool of $N$ available options to maximize a reward. Traditionally, research has focused on linear reward functions, where the total reward is simply the sum of individual item values. However, real-world applications—such as online retail assortment optimization—often involve complex, non-linear interactions between items.

This paper investigates the fundamental limits of learning in adversarial combinatorial bandits with general non-linear reward functions. The authors identify a stark "information gap": while linear rewards allow for efficient polynomial scaling, non-linear rewards in an adversarial environment force the learner to treat every possible combination as an independent entity, leading to exponential regret.

The Information Gap: Linear vs. Non-Linear Rewards

In a standard linear combinatorial bandit, the learner receives a reward $R_t = \sum_{i \in S_t} v_{i,t}$, where $S_t$ is the chosen subset and $v_{i,t}$ are the item values. Because the reward is additive, observing the outcome of one subset provides information about the constituent items, which in turn informs the learner about the potential performance of other subsets.

When the reward function $f(v_{i_1}, \dots, v_{i_K})$ is non-linear, this structural advantage disappears. In an adversarial setting, where an opponent can choose item values $v_{i,t}$ to minimize the learner's gain, the relationship between different subsets can be obscured. The authors prove that for non-linear functions, an adversary can construct value distributions such that picking one subset reveals virtually nothing about the performance of another, even if they share $K-1$ items. This effectively forces the learner to "search in the dark."

Algorithmic Frameworks

The authors provide upper bounds for regret using two distinct strategies based on the complexity of the reward function.

1. General Non-Linear Functions

For arbitrary reward functions, the problem is reduced to a classical Multi-Armed Bandit (MAB) problem. Here, each of the $\binom{N}{K}$ possible subsets is treated as a unique "super-arm." By applying the Implicitly Normalized Forecaster (INF) algorithm, the learner can manage these combinations. While mathematically sound, this approach highlights the inherent difficulty of the problem, as the number of subsets grows exponentially with $K$.

2. Polynomial Rewards and Tensorization

If the reward function is a polynomial of degree $d$, the authors employ a "tensorization" technique. By mapping the $N$-dimensional item values into a higher-dimensional space of $N^d$, the non-linear interactions are transformed into a linear form. This allows the use of the EXP2 algorithm, resulting in a regret bound of $\Theta(\sqrt{N^d T})$. This demonstrates that the difficulty of the problem is intrinsically linked to the degree of interaction between items.

Establishing Hardness: The Lower Bound

The core technical contribution of the paper is a non-constructive proof of minimax lower bounds using duality arguments. The authors establish that for any non-polynomial reward function, there exists a "worst-case" distribution of item values that negates any benefit of overlapping subsets.

This result is particularly impactful for the Multinomial Logit (MNL) model, a standard framework for modeling consumer choice in assortment optimization. The authors show that in an adversarial context, the MNL model suffers from the same "independence trap" as general non-linear functions. The optimal regret for MNL is $\Omega(\sqrt{N^K T})$, a "negative" result that defines the absolute limits of what is possible in these environments.

Summary of Regret Bounds

The paper provides a complete characterization of the minimax regret $R$ across different reward types:

  • Linear Reward ($d=1$): Regret is $\Theta(\sqrt{NT})$, matching known results.
  • Low-degree Polynomial ($d < K$): Regret is $\Theta(\sqrt{N^d T})$. The complexity grows with the degree of interaction.
  • General Non-linear / High-degree Polynomial: Regret is $\Theta(\sqrt{N^K T})$.

The jump from $\sqrt{N}$ to $\sqrt{N^K}$ represents a massive escalation in complexity. For a pool of $N=100$ items and a subset size of $K=10$, the difference is between a problem that is solvable in seconds and one that is practically impossible.

Conclusion and Future Directions

This research defines the absolute limits of what is achievable in adversarial combinatorial bandits. The findings suggest that the linearity often assumed in bandit literature is not just a convenience, but a requirement for efficient learning in adversarial settings.

Future work may focus on bridging the gap between the stochastic and adversarial models. While the adversarial setting is "hard," real-world environments may change slowly enough to allow for intermediate regret performance. Additionally, exploring "semi-bandit" feedback—where the learner observes individual item outcomes rather than just the total reward—could potentially mitigate the high cost of non-linearity.

Summary updated

BibTeX
@inproceedings{chen2021adversarial,
  author = {Xi Chen and Yanjun Han and Yining Wang},
  title = {{Adversarial Combinatorial Bandits with General Non-linear Reward Functions}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=rHCXjnwKV9_},
}
Figure