Combinatorial Bandits for Maximum Value Reward Function under Value-Index Feedback

We would like to thank the reviewer for positively appreciating the technical soundness and presentation of our paper. We give detailed comments on the points of concern and questions raised in the review. We update the appendix with more discussions and will incorporate all addressed points in the final version of our paper.

P1 Although the paper presents the application scenarios that motivate it, it is necessary to explore in more detail how the proposed approach could be applied to a wider range of problems.
P2 The paper is specifically centered on addressing a particular combinatorial multi-armed bandit problem that incorporates maximum value and index feedback..

Yes, we acknowledge that the current work focuses on one specific problem. We will downplay a bit of this point of contribution, but we note that 1) the max value-index feedback assumes far less information than most of other types of feedback structures 2) the idea of arm equivalence and using fictitious arms can be possibly applied to solve CMAB problems of other non-linear rewards.

P3 The paper assumes that arm outcomes follow arbitrary distributions with finite supports, allowing for a broad treatment of the problem. Nevertheless, it may not accurately capture the characteristics of real-world scenarios.

We argue that our setting assuming finite support is not limited in the applications, as categorical ratings or ranks are commonly used in the real world. We note the possibility of extending our result to allow for continuous reward distributions by discretizing continuous arm distributions. However, discretization may incur a tradeoff between discretization granularity and regret bound. We add a section in the appendix giving more detailed comments on the real world implications of our assumptions on the arm support.

P4 While the paper does provide experimental results that showcase the effectiveness of the proposed algorithm, these experiments are conducted on a limited scale and lack extensive benchmarking against other algorithms.

The main goal of the numerical part is to show that our algorithm achieves good regret bound, as proved in the theoretical results. In particular, it is designed purposely to show that the algorithm works for scenarios with high-risk high-reward items or stable-valued items with low reward. We chose the benchmark algorithm carefully such that this assumption works. We will test for alternative algorithms such as DART where this assumption does not hold and add another plot for items of categorical distributions.

P5 What is the main obstacle in finding the lower bound for the exact problem setting you are considering?

We acknowledge that finding the lower bound for the exact problem setting remains an open problem. We note that related works such as Kveton et al 2015 and Wang and Chen 2017 use arguments similar to ours. The key is to find a special case of $k$-MAX problem such that items are almost always triggered but the probability parameters are never accurately estimated.

P6 Would it be possible to extend this work to unbounded rewards? Like Gaussian ones?

We believe that it is possible to extend the work to unbounded rewards like Gaussian. Unboundness is not a serious issue as Gaussian distribution is highly centred. There are prior works that extend from bounded rewards to unbounded rewards using concentration inequalities. We also argue that the infinite support size is not of a big concern. In many cases, even though the support size may be infinite from the values offered by the platform (e.g. real-valued feedback), the actual value of the customer on an item may only have a few possible internal values, and thus treating the variable as having finite and unknown support size could work well and save regret for many practical scenarios.

We thank the reviewer for the insightful feedback. We have addressed each point of concern and questions asked in the following. More updates are included in the appendix and we will incorporate all addressed points in the final version of our paper.

P1 Algorithm 4.1 looks like the pinnacle of the paper. However...

Yes, a comparable regret upper bound as in Theorem 3.4 holds for Algorithm 4.1: For the $k$-MAX problem with max value-index feedback, under general case of arbitrary discrete distributions of arm outcomes with finite support as defined in Section 2 and under assumption $\Delta_{\min}>0$, Algorithm 4.1 has the following distribution-dependent regret bound, $R(T)\leq c_1 \sum_{i=1}^n\left(\frac{k}{\Delta_{\min}^i} + \log\left(\frac{k}{\Delta_{\min}^i}+1\right)\right) s_i\log(T) +c_2 \sum_{i=1}^n s_i\left(\left(\log \left(\frac{ k}{\Delta_{\min}^i}+1\right)+1\right)\Delta_{\max}+1\right),$ We give further comments of the claim in the appendix.

The current experimental setup is designed purposefully to show that the algorithm works for scenarios with high-risk high-reward items or stable-valued items with low reward. We will add another plot for items of categorical distributions to demonstrate that Algorithm 4.1 is an effective approach.

P2 I wonder if there is an application in which this tie-breaking..
P3 My question is about implementation issues regarding this deterministic tie-breaking rule..

Thanks for asking this good question. In the recommender system setting, deterministic tie-breaking models the case that the customer is always intrinsically looking for other clues and information when facing two similar items to make a selection in his/her head, instead of purely relying on a coin toss in his/her head. There could be a difference between the value feedback based on the choices that the platform offers and the internal values of the items that a user actually perceives, which rely on the granularity of the feedback scale. Think of four items A, B, C, and D given to the user on a five-star scale. The first time, A, B, and C are shown and the user favors A and rates it 4 stars. The second time, B, C, and D are shown and the user favors B and rates it also 4 stars. The user gives both A and B the same value feedback, but there could be some confounding factors that are not captured in the value feedback, which implies a deterministic tie-breaking when facing A and B at the same time. Considering random tie-breaking is perhaps only purely for mathematical curiosity or interest.

P4 How is $q_i^{\mu,S}$ related to $q_i^{p,S}$ and $\tilde{q}_i^{p,S}$?

$q_i^{\mu,S}$ in Definition 3.2 is a general definition for the triggering probability of arm $i$ under action $S$ and a set of base arms $\mathcal{B}$ with expectation values $\mu$, and the reward function depends on $\mu$ only. $q_i^{p,S}$ and $\tilde{q}_i^{p,S}$ are defined for our specific problem setting when the (extended) set of base arms $\mathcal{B}$ consists of the union of two sets $\mathcal{Z}$ and $\mathcal{V}$. $q_i^{p,S}$ is the triggering probability of arm $a_i^z$ under action $S$ and is dependent on $p$ only. $\tilde{q}_i^{p,S}$ is the triggering probability of arm $a_i^v$ under action $S$. We did not write $\tilde{q}_i^{p,v, S}$ as the triggering probability is also dependent on $p$ only.

P5 The estimates of base arm outcomes are still unbiased?...

Yes, as explained in section 3.3, the estimates of base arms are biased and this is one of the key challenges we have for our problem. As a result, the Event E2 does not directly apply. To tackle with this difficulty, we introduce the concept of arm equivalence such that we can restore the CMAB-T framework by using some replacement items $(p',v')$. We note that $p_{i,t} '= p_iv_i, v_{i,t}' = 1$ when $v_i$ is unknown (first stage) and $p_{i,t} '= p_i, v_{i,t}' = v_i$ after observing $v_i$ (second stage). In this way, the estimates of base arms are unbiased in two stages. We then justify that using the replacement arms will not cause excessive regrets.

P6 Please comment on the batch-size dependence..

Yes. The current distribution-independent regret bound is $\tilde{O}(\sqrt{KT})$, the same as cascading bandits upper bound. $R(T)\leq c_1\left(\sqrt{nKT} + \log\left(\sqrt{nKT} +1\right)\right)\log T +c_2 \left(\left(\log \left(\sqrt{nKT} +1\right)+1\right)\Delta_{\max}+1\right),$

P7 What about batch size independent regret bounds as in Liu et al. 2022, NeurIPS...

Yes, we checked that our case satisfies the TPVM condition. We can improve the regret bound dependency from $k$ to $\log(k)$. The change is due to a tighter bound of the regret caused by estimation error of $p$. In the algorithm, besides maintaining a confidence bound for the mean value of $p$, we also maintain a confidence bound for its variance as Algorithm 1 in (Liu et al. 2022). We note that most of our methods and analysis remain the same. We give a summary of changes in the appendix.

We thank the reviewer for positively appreciating the presentation of our work and providing us with detailed comments. However, we think the reviewer misunderstood some parts of our work and we do not agree with some of the comments that qualify our technical contributions to be a straightforward modification of existing results. We give detailed explanations of the questions asked in the following. More updates are included in the appendix, and we will incorporate all addressed points in the final version of our paper.

P1 The paper could benefit from more detailed explanations of the proposed algorithm and its intuition. There is also no explicit definition of regret, which is a fundamental concept in the entirety of this work, especially for readers that might be unfamiliar with the combinatorial bandits literature.

We are sorry that we mistakenly removed a paragraph in the problem formulation section. We add back the formal definition of the regret and the approximation oracle as follows.

P2 The paper focuses on binary distributions of arm outcomes always including $0$ in their support.. Even if the authors argue about adapting to more general discrete distributions..
P3 Is the presence of $0$ in the support strictly necessary?

No, it is totally fine to have arms without 0 in its support. We did not impose this constraints for arm distributions. Please take another look at section 2 problem formulation on page 3. We require that $0 < \sum_{j=1}^{s_i} p_{i,j}\leq 1$. Note that when the right inequality holds with equal sign, $p_{i,0} = 0$ and the arm outcome does not include zero in the support. In the binary case, this simply means that we have a deterministic arm. In the general case, the equivalence relationship is not affected. For example, if $X_i$ takes value $0.1$ with probability $2/3$, and value $0.22$ with probability $1/3$, then by eqn.(4.1), we can represent $X_i$ by two random variables $X_{i,1}$ and $X_{i,2}$ such that $X_{i,1}$ takes value $0.1$ with probability $1$, and $X_{i,2}$ takes value $0.2$ with probability $1/3$ and value 0 with probability $2/3$. One can easily verify that $Y=\max\{X_{i,1}, X_{i,2}\}$ follows the distribution exactly the same as the original $X_i$, namely with probability $2/3$ $Y=0.1$ and with probability $1/3$ $Y=0.2$.

We also argue that our setting is not limited in the applications, as categorical ratings or ranks are commonly used in the real world. The general algorithm on discrete distributions with finite support does have theoretical guarantees. As we discussed in the main text, equipped with the equivalence relationship, we are able to treat arms with outcomes according to arbitrary distributions with finite supports as a set of arms with outcomes according to binary distributions and use our algorithm defined for the case of arms with binary distributions. Specifically, we have the following claim for regret upper bound,

For the $k$-MAX problem with max value-index feedback, under general case of arbitrary discrete distributions of arm outcomes with finitesupport as defined in Section 2 and under assumption $\Delta_{\min}>0$, Algorithm 4.1 has the following distribution-dependent regret bound, $R(T)\leq c_1 \sum_{i=1}^n\left(\frac{k}{\Delta_{\min}^i} + \log\left(\frac{k}{\Delta_{\min}^i}+1\right)\right) s_i\log(T) +c_2 \sum_{i=1}^n s_i\left(\left(\log \left(\frac{ k}{\Delta_{\min}^i}+1\right)+1\right)\Delta_{\max}+1\right)$ We give further comments of the claim in the appendix.

We acknowledge that our current regret bound does depend on the support size of the discrete variables. We believe this does not limit the applicable scenarios of our algorithm. In many applications, the support size is relatively small. For application scenario where the support size is large, we would like to emphasize the distinction between the choices that the platform offers and the internal values of the items that a user actually perceives. In may cases, even though the support size may be infinite from the values offered by the platform (e.g. real-valued feedback), the actual value of the customer on an item may only have a few possible internal values.

We note the possibility of extending our result to allow for continuous reward distributions by discretizing continuous arm distributions. We do like to mention that when all the values of the variables are unknown, intuitively the exploration does seem to need to explore all possible support values of variables in order to exploit the best option, and this may suggest some inherent dependency on the support size or a tradeoff between discretization granularity and regret bound. This is indeed an intriguing research direction for future research to study the upper and lower bound dependencies on the support size, but we believe it is out of the scope of the current paper, while our current paper already has proper technical innovations that cover a reasonable range of practical applications.

We would like to thank the reviewer for positively appreciating the technical soundness and novelty of the problem we study, and providing detailed comments on the paper presentation. More updates are included in the appendix, and we will incorporate all addressed points in the final version of our paper.

P1 here’s an uncited work that is relevant -- “DART” by the same authors of (Agarwal et al. (2021).

Thanks for pointing this out. We will cite this work in the related work section on full-bandit CMAB problems. We note that our $k$-MAX bandit setting does not satisfy the assumption 2 Good arms generate good actions in Agarwal et al. (2021). High-risk high reward item in our setting could be favored by the maximum reward. Consider $n=3$ and $k=2$ such that $X_1$ taking 0.9 with probability 0.2, $X_2$ taking 0.5 with probability 0.4 and $X_3$ taking 0.6 with probability 1. In this case, $E(X_1)<E(X_2)$ but $X_1$ is in the optimal set instead of $X_2$.

P2 Is the regret $R(T)$ formally defined... Relatedly, page 5 is the first place approximation oracle is mentioned once in the text before the Alg 3.1 pseudocode but what “approximation oracle” refers to is not formally described.?

We truly apologize for the ambiguity caused. We have mistakenly removed one paragraph from the problem formulation section that formally defines the regret and the approximation oracle with the procedures. It is added back as a section in the appendix.

P3 Algorithms I found the discussion in the text confusing about maintaining confidence bounds..
P4 "In Section 3.2 I would suggest linking to the pseudocode earlier.

The confidence radius of $v_i$ is defined as $\boldsymbol{1}\{\tilde{T}_i = 0\}$. It is defined in this way for notation convenience and consistency. Note that the value may never be revealed. We will make it explicit in Algorithm B.1 and link the pseudocode at the end of second paragraph of section 3.2.

P5 I think it would be valuable to have a fuller discussion of the hardness for the offline setting and corresponding approximation methods.

Thanks for the good question. We give a full discussion of the hardness results. For the general offline $k$-MAX problem (Goel et al 2014), finding the exact optimal solution is NP-hard. (Chen et al 2016) shows that there exists a PTAS for the offline $k$-MAX problem such that for any constant $\epsilon>0$ there is a polynomial-time $(1-\epsilon)$-approximation algorithm for the offline $k$-MAX problem. The binary and Bernoulli $k$-MAX problems are not NP-hard. The binary $k$-MAX problem can be solved exactly using dynamic programming. The Bernoulli $k$-MAX problem can be solved exactly by ordering values and selecting the top $k$.

P6 Semi-bandit CUCB is good to include; it would be good to also include Agarwal et al. (2021))’s DART.

We will test the performance of the DART algorithm. We note that the current experimental setup is designed purposely to show that the algorithm works for scenarios with high-risk high-reward items or stable-valued items with low reward. As mentioned, this assumption does not hold in Agarwal et al. (2021)).

P7 The distributions in the experiments are all binary?
P8 "three different arm distributions representing different scenarios" is quite generic..

Thanks for pointing these out. We will clarify the experimental setup as suggested.

P9 *Motivation – What would be a motivating application of K-max with the max-index feedback for which the arm supports would be unknown? *

Firstly, we argue that in some cases, the agent has no knowledge of the feedback scale. For example, in bidding or donation, the agent would have no access to the internal value of the bidders or donors beforehand; in sensor detection, the agent does not know the informativeness of sensors before receiving signals.

Moreover, we would like to emphasize the distinction between the choices that the platform offers and the internal values of the items that a user actually perceives. On most systems, we may offer choices on a 1-10 or 1-100 scale. If we treat this as the case of known support size, the support size would be 10 or 100, respectively. However, the user/customer may value a given item with only one or a few possible values. By treating these possible values as unknown supports, we may have a much smaller support size to deal with on each random variable, and thus resulting into smaller regret.

P10 Our work may be seen as a step towards solving full-bandit CMAB problems..?

In our current work, we consider the expected maximum as the reward function. We acknowledge that the proof techniques are tailored to leverage properties of the expected maximum. We note that the idea of arm equivalence and using fictitious arms can be possibly applied to solve CMAB problems of other non-linear rewards. We will downplay a bit of this point of contribution.