Adversarial Combinatorial Bandits with General Non-linear Reward Functions

Below is an informal statement of our main result, as a summary of Theorem 1 later in the paper.

The results in Corollary 1 easily cover the linear link function case $g(x)=x$, with $d=1$ and the optimal regret being $\widetilde{\Theta}(\sqrt{NT})$ (Bubeck et al., 2012). On the other hand, Corollary 1 shows that when $g$ is not a polynomial, no algorithm can achieve a regret better than $O(\sqrt{N^{K}T})$. This shows that when $g$ is a general non-linear reward function, the $\binom{N}{K}$ subsets of the $N$ arms can only be treated as “independent” and it is information-theoretically impossible for any algorithm to exploit correlation between subsets of arms to achieve a significantly smaller regret.

Dynamic assortment optimization is a key problem in revenue management and online recommendation, which naturally serves as a motivation for the generalized combinatorial bandit problem studied in this paper. In the standard setup of dynamic assortment optimization (Agrawal et al., 2019), there are $N$ substitutable products, each associated with a known profit parameter $p_{i}\in[0,1]$ and an unknown mean utility parameter $v_{i}\in[0,1]$. At each time, the seller offers an assortment (i.e., the recommended set of products) $S_{t}\subseteq[N]$ of size $K$, e.g., there are $K$ display spots of recommended products on an Amazon webpage. Then the customer either purchases one of the products being offered (i.e., $i_{t}\in S_{t}$) or leaves without making any purchase (i.e., $i_{t}=0$). The choice behavior of the customer is governed by the well-known MultiNomial-Logit (MNL) model from economics (Train, 2009):

with the definition that $v_{0}:=1$, where $v_{0}$ denote the utility of no-purchase. The objective for the seller or retailer is to maximize the expected profit/revenue

Note also that, in the adversarial setting, the mean utility vector $v_{t}=\{v_{ti}\}_{i=1}^{N}$ will be different for each time period $t=1,2,\cdots,T$, and will be selected by an adaptive adversary. The regret is then defined as (2).

Let us first consider a special case, where all the products have the profit one (i.e., $p_{i}\equiv 1$) and only binary purchase/no-purchase actions are observable. That is, one only observes a binary reward at time $t$, $r_{t}=\boldsymbol{1}\{i_{t}\in S_{t}\}$, which indicates whether there is a purchase. Then the dynamic assortment optimization question reduces to the generalized (adversarial) combinatorial bandit problem formulated in Eqs. (1,2) with the link function $g(x)=x/(1+x)$. Since $g(x)=x/(1+x)$ is clearly not a polynomial, Corollary 1 shows that $\Theta(\sqrt{N^{K}T})$ should be the optimal regret. The following corollary extends this to the general case of dynamic assortment optimization, where different products can have different profit parameters.

The next corollary, on the other hand, shows that the $O(\sqrt{N^{K}T})$ regret in not improvable, even with a richer non-binary feedback and if all products have the same profits parameter $p_{i}\equiv 1$.

Both corollaries are consequences of Proposition 1 and Lemma 3 later in the paper.

As we shall see later in this paper, the upper bounds of $\widetilde{O}_{g,K,d}(\sqrt{N^{d}T})$ or $O_{g,K}(\sqrt{N^{K}T})$ in Corollary 1 are relatively easier to establish, via reduction to known adversarial multi-armed or linear bandit algorithms. The key challenge is to establish corresponding $\Omega(\sqrt{N^{d}T})$ and $\Omega(\sqrt{N^{K}T})$ lower bounds in Corollary 1.

In this section we give a high-level sketch of the key ideas in our lower bound proof. For simplicity we consider only the case when $g(\cdot)$ is not a polynomial function. The key insight is to prove the existence of a distribution $\mu$ on $v\in[0,1]^{n}$, such that for any $S\subseteq[n]$, $|S|=K$, the following holds on the choice distribution $\mathbb{P}(\cdot|S,v)$ with $\mathbb{P}_{0}\neq\mathbb{P}_{1}$:

Intuitively, Eq. (4) shows that, no information is gained unless an algorithm exactly guesses the optimal subset $S^{\star}$, even if the subset $S_{t}$ produced by the algorithm only differ by a single element from $S^{\star}$. Since there are $\binom{N}{K}$ different subsets, the question of guessing the optimal subset $S^{\star}$ exactly correct is similar to locating the best arm of a multi-armed bandit question with $\binom{N}{K}=\Theta_{K}(N^{K})$ arms, which incurs a regret of $\Omega_{K}(\sqrt{N^{K}T})$.

To gain deeper insights into the construction of $v\sim\mu$ that satisfies Eq. (4), it is instructive to consider some simpler bandit settings in which a small regret can be achieved and understand why the construction of $\mu$ does not apply there.

• •

  The first setting is dynamic assortment optimization under the stationary setting, in which the $\{v_{t}\}_{t=1}^{T}$ vectors remain the same for all $T$ periods. The results of (Agrawal et al., 2019) achieve $\widetilde{O}(\sqrt{NT})$ regret in this setting. In this setting, the vector $v$ is deterministic and fixed, and therefore the laws $\mathbb{P}(\cdot|S,v)$ and $\mathbb{P}(\cdot|S^{\prime},v)$ must be correlated as long as $S\cap S^{\prime}\neq\emptyset$. This means that Eq. (4) cannot be possibly satisfied, with every subset $S\neq S^{\star}$ revealing no information about $S^{\star}$.

• •

  The second setting is the adversarial combinatorial bandit with a linear link function $g(x)=cx$, for which an $\widetilde{O}_{K}(\sqrt{NT})$ regret is attainable (Bubeck et al., 2012; Combes et al., 2015). When $g$ is linear, the expectation of the mixture distribution $\mathbb{E}_{v\sim\mu}[\mathbb{P}(\cdot|S,v)]$ is

  $$\mathbb{E}_{v\sim\mu}[R(S,v)]=g(\langle\boldsymbol{1}_{S},\mathbb{E}_{\mu}[v]\rangle),$$

  where $\boldsymbol{1}_{S}\in\{0,1\}^{n}$ is the indicator vector of the subset $S\subseteq[N]$. Clearly, this is impossible to achieve (4) as there is no vector $w\in\mathbb{R}^{N}$ satisfying that $\langle\boldsymbol{1}_{S},w\rangle$ is constant for all $S\neq S^{\star}$ and $\langle\boldsymbol{1}_{S},w\rangle\neq\langle\boldsymbol{1}_{S^{\star}},w\rangle$.

• •

  The third setting is a special stochastic combinatorial bandit, where $v\sim\mu$ is random but there exists a total ordering of the stochastic dominance relation among the components $(\mu_{1},\cdots,\mu_{N})$ of $\mu=\prod_{i=1}^{N}\mu_{i}$, and an increasing $g$. In this setting, it was shown in (Agarwal & Aggarwal, 2018) that a regret of $\widetilde{O}_{K}(N^{1/3}T^{2/3})$ can be achieved, and the stochastic dominance requirement implies that once an element of $[N]\backslash S^{\star}$ is replaced by an element of $S^{\star}$, the expected reward must increase. Therefore, (4) cannot hold in this scenario either.

Combinatorial bandit is a classical question in machine learning and has been extensively studied under the settings of stochastic semi-bandits (Chen et al., 2013; Combes et al., 2015; Kveton et al., 2015; Chen et al., 2016a, b; Wang & Chen, 2018; Merlis & Mannor, 2019, 2020), stochastic bandits (Agarwal & Aggarwal, 2018; Rejwan & Mansour, 2020; Kuroki et al., 2020), and adversarial linear bandits (Cesa-Bianchi & Lugosi, 2012; Bubeck et al., 2012; Audibert et al., 2014; Combes et al., 2015). In the above-mentioned works, either the reward link function $g(\cdot)$ is linear, or the model is stochastic (stationary).

There is another line of research on dynamic assortment optimization with the multinomial logit model, which is a form of combinatorial bandit with general reward functions (Rusmevichientong et al., 2010; Agrawal et al., 2017; Chen et al., 2018a, b; Chen & Wang, 2018; Chen et al., 2019; Agrawal et al., 2019). All of these works are carried out under the stochastic setting, with the exception of (Chen et al., 2019) which studied an $\varepsilon$-contamination model and obtained a regret upper bound $\widetilde{O}(\sqrt{NT}+\varepsilon T)$. Clearly, with the adversarial setting in this paper ($\varepsilon=1$) the regret bound in (Chen et al., 2019) becomes linear in $T$ and thus meaningless.

For a multi-index $\alpha\in\mathbb{N}^{d}$, let $|\alpha|=\sum_{i=1}^{d}\alpha_{i}$, and $D^{\alpha}f=\partial^{|\alpha|}f/\prod_{i=1}^{d}\partial x_{i}^{\alpha_{i}}$ for a $d$-variate function $f$. For $m\in\mathbb{N}$ and interval $I$, let $C^{m}(I)$ be the set of $m$-times continuously differentiable functions on $I$. For two probability distributions $P$ and $Q$, let $\mathrm{TV}(P,Q)=\frac{1}{2}\int|dP-dQ|$ and $D_{\mathrm{KL}}(P\|Q)=\int dP\log(dP/dQ)$ be the total variation (TV) distance and the Kullback–Leibler (KL) divergence, respectively. We adopt the standard asymptotic notation: for two non-negative sequences $\{a_{n}\}$ and $\{b_{n}\}$, we use the notation $a_{n}=O_{c}(b_{n})$ to denote that $a_{n}\leq Cb_{n}$ for all $n$ and constant $C<\infty$ depending only on $c$, $a_{n}=\Omega_{c}(b_{n})$ to denote $b_{n}=O_{c}(a_{n})$, and $a_{n}=\Theta_{c}(b_{n})$ to denote both $a_{n}=O_{c}(b_{n})$ and $a_{n}=\Omega_{c}(b_{n})$. We also use $\widetilde{O}(\cdot),\widetilde{\Omega}(\cdot),\widetilde{\Theta}(\cdot)$ to denote the respective meanings up to a multiplicative poly-logarithmic factor in $(N,T)$.

We first prove the $O_{K}(\min\{T,\sqrt{N^{K}T}\})$ regret upper bound for general link functions. In fact, we state the following result that is much more general than Theorem 1.

We remark that Proposition 1 is more general and contains the $C_{g,K}\min\{T,\sqrt{N^{K}T}\}$ upper bound in Theorem 1 as a special case. By considering the feedback model $b_{t}\in S_{t}\cup\{0\}$ and $r_{t}(b_{t})=\sum_{i\in S_{t}}p_{i}\boldsymbol{1}\{b_{t}=i\}$, Proposition 1 also covers the dynamic assortment optimization model described in Sec. 1.2 and Corollary 2.

We next establish the $O(\min\{T,\sqrt{N^{d}T\log N}\})$ upper bound for polynomial reward functions.

Propositions 1 and 2 complete the proof of minimax upper bounds in Theorem 1.

We first prove the following result corresponding to the minimax lower bounds in Theorem 1.

Our proof is based on the following technical lemma:

The proof of Lemma 2 is deferred to the Sec. 3. The construction of the distributions in Lemma 2 is non-constructive and uses duality existential arguments. Its proof also applies several technical tools from real analysis and functional analysis (Rudin, 1991; Donoghue, 1969; Dudley, 2018).

We are now ready to prove Lemma 1.

Next, we establish an $\Omega(\sqrt{N^{K}T})$ lower bound for the dynamic assortment optimization model described in Sec. 1.2. It implies Corollary 3 in the introduction section.