Adversarial Combinatorial Bandits with General Non-linear Reward Functions

Yanjun Han, Yining Wang, Xi Chen

TL;DR Most combinatorial bandit research assumes that rewards are "linear"—meaning the total reward is simply the sum of its parts. This paper shatters that comfort zone by proving that in adversarial environments, even slightly non-linear reward functions make the problem exponentially harder, forcing algorithms to treat every possible combination of items as if they were completely independent.

The Problem: Linear vs. Non-Linear Rewards

In a standard Combinatorial Bandit problem, an agent chooses a subset of $K$ items (arms) out of $N$ possibilities at each time step $T$. Traditionally, researchers assumed a linear reward: the reward for a set of items is the sum of their individual values. This assumption allows the agent to learn quickly, as information gained about one item helps predict the performance of any set containing that item.

However, real-world rewards are rarely linear. Consider assortment optimization in e-commerce: the probability of a user clicking a product depends heavily on what other products are shown alongside it (the "substitution effect").

While non-linear rewards have been studied in stochastic settings (where item values are drawn from a fixed distribution), this paper tackles the much tougher adversarial setting. Here, an "adversary" can change the values of items at every step to trick the algorithm. The authors ask a fundamental question: Can we still achieve efficient learning (low "regret") when rewards are non-linear and the environment is actively working against us?

Methodology: Bounding the Regret

As a theoretical machine learning paper, the results are established through rigorous mathematical proofs and probabilistic modeling rather than empirical datasets. The authors characterize the "minimax regret"—the best possible performance an algorithm can guarantee against the worst possible adversary—using two main approaches:

1. Upper Bounds (Algorithms) * For General Functions: The authors show that any non-linear problem can be reduced to a standard Multi-Armed Bandit problem where each of the $\binom{N}{K}$ possible subsets is treated as a unique, independent arm. They use the Implicitly Normalized Forecaster (INF) algorithm to manage this vast action space. * For Polynomials: If the reward function is a polynomial of degree $d$, they use a technique called tensorization. This mathematically transforms the non-linear reward into a high-dimensional linear reward, allowing them to deploy the EXP2 algorithm.

2. Lower Bounds (The "Hardness" Proof) The core of the paper is a sophisticated mathematical proof using duality and functional analysis. The authors prove the existence of a "nasty" reward distribution where an algorithm learns absolutely zero information about the optimal set of items unless it happens to pick that exact set. This effectively proves that treating subsets independently is sometimes the only mathematically viable strategy.

Key Insights and Results

The paper provides a complete characterization of optimal regret, highlighting a massive jump in difficulty between linear and non-linear rewards.

  • The Fundamental Gap: In the linear case, regret scales with $\sqrt{N}$. For general non-linear functions (like those used in retail modeling), regret scales with $\sqrt{N^K}$. This means as the number of items you choose ($K$) grows, the problem becomes exponentially harder.
  • The Death of Correlation: In linear bandits, subsets are correlated; sharing an item means sharing information. The authors prove that an adversary can destroy this correlation for non-linear functions, rendering overlapping subsets useless for mutual information sharing.
  • Polynomials as a Bridge: The "hardness" of the problem is tied directly to the degree of the reward function.
  • For low-degree polynomials ($d < K$), the optimal regret is $\tilde{\Theta}(\sqrt{N^d T})$.
  • For non-polynomials or high-degree polynomials, the optimal regret is $\Theta(\sqrt{N^K T})$.
  • Assortment Optimization: For the popular Multinomial Logit (MNL) model, they prove that the optimal algorithm must treat each of the $\binom{N}{K}$ assortments as independent, leading to an unavoidable $\Theta(\sqrt{N^K T})$ regret.

Ultimately, these results demonstrate that the "efficient" regret bounds ($\sqrt{\text{poly}(N, K)T}$) previously seen in linear or stochastic settings are impossible to achieve in the general adversarial non-linear case.

Limitations and Future Work

  • Existential Constants: While the paper provides the "rate" of the regret (how it scales with $N, K, T$), the specific constants (e.g., $c_{g,K}$) are "existential." The authors proved they exist but haven't calculated their exact values—a common open challenge in theoretical machine learning.
  • Bridging the Gap: The adversarial setting is notoriously pessimistic. The authors suggest future work could explore "intermediate" settings—perhaps an adversary that is somewhat constrained—to see if better regret bounds are possible in more realistic, less "evil" environments.
  • Latent Variables: They propose exploring models where item values change over "epochs" rather than every single step. This structure might allow for better information sharing even when dealing with non-linear rewards.

Summary updated

Abstract

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 combinatori...
BibTeX
@inproceedings{han2021adversarial,
  author = {Yanjun Han and Yining Wang and Xi Chen},
  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