Combinatorial Bandits for Maximum Value Reward Function under Value-Index Feedback
Authors: Yiliu Wang
Wei Chen
Milan Vojnovic
Venue: ICLR 2024 poster (2024)
Keywords: Combinatorial multi-armed bandit
$k$-MAX bandit
value-index feedback
maximum reward function
Primary area: learning theory
TL;DR: We studied a combinatorial MAB problem for max reward function under a new feedback structure.

Abstract: We investigate the combinatorial multi-armed bandit problem where an action is to select $k$ arms from a set of base arms, and its reward is the maximum of the sample values of these $k$ arms, under a weak feedback structure that only returns the value and index of the arm with the maximum value. This novel feedback structure is much weaker than the semi-bandit feedback previously studied and is only slightly stronger than the full-bandit feedback, and thus it presents a new challenge for the online learning task. We propose an algorithm and derive a regret bound for instances where arm outcomes follow distributions with finite supports. Our algorithm introduces a novel concept of biased arm replacement to address the weak feedback challenge, and it achieves a distribution-dependent regret bound of $O((k/\Delta)\log(T))$ and a distribution-independent regret bound of $\tilde{O}(\sqrt{T})$, where $\Delta$ is the reward gap and $T$ is the time horizon. 
Notably, our regret bound is comparable to the bounds obtained under the more informative semi-bandit feedback. 
We demonstrate the effectiveness of our algorithm through experimental results.

Published as a conference paper at ICLR 2024
COMBINATORIAL BANDITS FOR MAXIMUM VALUE RE- WARD FUNCTION UNDER VALUE-INDEX FEEDBACK
Yiliu Wang"
Wei Chen
Allen Institute
Microsoft Research
Seattle, WA 98109, USA
Beijing, China
wiliv.wanggalll wtwp:aaleeeinnnntiiiiiii istiiute..trtrr
we weicêmi croso ft..oottoooo com
Milan Vojnović
Department of Statistics, LSE London, United Kingdom
m. n.vojnovi.co c se..eee.. ac. uk
ABSTRACT
We investigate the combinatorial multi-armed bandit problem where an action is select k arms from a set of base arms, and its reward is the maximum of the sample values of these k arms, under a weak feedback structure that only returns the value and index of the arm with the maximum value. This novel feedback structure is much weaker than the is only slightly stronger than the full-bandit feedback, and thus it presents a new challenge for the online learning task. We propose an algorithm and derive a regret bound for instances where arm outcomes follow distributions with finite supports. Our algorithm introduces a novel concept of biased arm replacement to address the weak feedback challenge, and it achieves a distribution-depended regret bound O((kk/ A) IT)( and a distribution iettiion-indeeddeent regret bound where A is the reward gap and T is the time horizon. Notably, our regret bound is comparable to the bounds obtained under the more informative semi-bandit feedback. We demonstrate the effectiveness of our algorithm through experimental results.
feedback previously studied and
INTRODUCTION
We address a combinatorial bandit problem where, in each round, the agent selects a set of k arms from a pool of arms. Each selected arm produces an independent random outcome, and the reward of the selected set of arms is determined by the maximum value among these outcomes. Following the selection of arms in a round, the agent receives feedback consisting of the maximum outcome value and the identity of the arm that achieved this value. The goal of the agent is to maximize the reward accrued over a time horizon. We term this sequential max value-index feedbuck.. The outcomes of arms are assumed to be independent random variables across arms and rounds. Initially, we consider arm outcomes according to binary distributions, and then extend analysis to arbitrary discrete distributions with finite supports. The performance of the agent is evaluated based on the expected cumulative regret over a predefined time horizon, which quantifies the difference between the cumulative reward achieved by selecting set with maximum expected reward each round and the cumulative reward achieved by the agent.
prcisioonmakinng problem the k-MAX bandit with
As concrete motivating application scenario, consider an online platform recommending some products, e.g., Netflix, Amazon, and Spotify. Assume there is in total n products for recommendation on the platform. The goal is to display subset of k product items to user that best fit the user preference. The feedback can be limited, as we may only observe which displayed product item the user clicked on and their subsequent rating of that product. Many other problems can be formulated in our setting, such as project portfolio selection (Blau et al., 2004; Jekunen, 2014), team formation
"The work was conducted during internship at Microsoft Research and part of thesis at the London School of Economies.

---

Published as a conference paper at ICLR 2024
(Kleinberg & Raghu, 2018; Sekar et al., 2021; Lee et al., 2023; Mehta et al., 2020), and sensor placement problems (Golovin & Krause, 2011; Asadpour & Nazerzadeh, 2016).
The problem presents two main challenges. Firstly, the reward function is the maximum value function, which is nonlinear and depends not only on the expected values of the constituent base arms. As demonstrated in the numerical section, high-risk, high-reward arms may outperform stable- outcome arms in this scenario, even though their expected outcome may be the same. The second challenge is due to the limited feedback. The agent only observes the maximum value and the identity of an arm that achieves this value, which makes it difficult to learn about other non- non-winning arms.
The problem we consider shares similarities with some combinatorial bandit problems -eesa-Bianchi & Lugosi, 2012: Chen et al., 2013; 20)6 but it differs in the feedback structure. Specifically, the max value-index feedback structure is neither the semi-bandit nor the full-bandit feedback, which are commonly studied in the bandit literature. To elaborate, let XI...... X,, be independent random variables corresponding to arm outcomes. In the semi- comi-bandit feedback, the feedback consists of all values {X, i E S} for any set S of arms. In contrast, the full-bandit feedback includes only the maximum value, max (X, | i E S), under the maximum value reward function. The max value-index feedback, on the other hand, provides both the maximum value max(X; E S) and the index I E arg [X, | E S}. Thus, the max value-index feedback is much weaker than the feedback, and only slightly stronger than the full-bandit feedback. This week feedback structure provides very limited information its current outcome is low by chance, or it cannot win anyway even with its highest support value. This poses severe challenge in learning the information of all arms.
non- wonniwgning arm * I: it is unclear whether loses because
We present algorithms and regret bounds for the k-MAX problem with max value-index feedback, under different assumptions regarding the information available about arm outcomes. Our results show that despite considerably more limited feedback, comparable regret bounds to those of combinatorial semi-bandits can be achieved for the K-MAX bandit problem with max value-index feedback.
1.1 RELATED WORK
The problem we study has connections with combinatorial multi-armed bandits (CMAB) (Cesa- Bianchi & Lugosi, 2012; Chen al., 2013; 2016b). Most existing work on CMAB problems focuses on the semi-bandit feedback setting, as seen in (Chen et al., 2013; Kveton et al., 2015a). The K-MAX problem with cemi-bandii feedback was addressed in (Chen et al., 2016 where the solution is simpler compared to our paper due to the semi-bandit feedback assumption.
In most works on full-bandit CMAB problems, restrictions are typically imposed on the reward function. For instance, Rejwan& & Mansour (2020) considered the sum reward function, while only few algorithms have been proposed for non-linear reward functions. In a bipartite setting where the agent selects pair of arms from row of K items and column of L items, Katariya et al. (2017) examined the minimum value reward function for rank-1 I bandit problems. It is worth noting that the rank-1 assumption holds for Bernoullidissributeed arms in the general setting under the maximum value reward function. On the other hand, Gopalan et al. (2014) investigated the full-bandit CMAB with general rewards using a Thompson sampling algorithm. However, computing the posteriors in the algorithm is computationally intensive, and the regret bound has a large exponential constant. More recently, Agarwal et al. (2021a) proposed a merge and sort algorithm under the assumption that the distributions of arm outcomes obey first-order stochastic dominance (FSD) condition. However, this condition is restrictive, as it fails to hold for binary distributions. Additionally, Agarwal et al. (2021b) proposed an adaptive accept-reject algorithm (DART) that sequentially identifies good arms based on mean rewards obtained by playing actions containing that arm. However, this algorithm relies on the arm-ordering assumption that the goodness of arms is ordered by their expected reward, which is not satisfied in k-MAX bandit. In summary, existing full-bandit CMAB solutions either do not apply our problem have exponential computational complexity.
A related work is on combinatorial cascading bandits, e.g. Kveton et al. (2015b). Here the agent chooses an ordered sequence from the set of arms and the outcomes of arms are revealed one by one until a stopping criteria is met. Chen et al. (2016b) generalized the problem to combinatorial aami-bandits with probabilistically triggered arms (CMAB-T). The main difference with our setting is that CMAB-T and cascading bandits in particular assume more feedback information and is inherently bandit In the recommendation system scenario, cascading bandits assume that the user would follow the recommendation order and investigate each item one by one and stop when clicking on an
2

---

Published as a conference paper at ICLR 2024
Table 1: Known regret bounds for CMAB problems under different settings.
Feedback
Reward
Assumptions
Regret
Chen et al. (2016a)
semi-bandit
general
general
nk log(T))
Rejwan & Mansour (2020)
full-bandit
linear
sub-Gaussian
0 lTg(T)
Katariya et al. (2017)
full-bandit
min
rank-1
0 log(T)
Agarwal et al. (2021a)
full-bandit
general
FSD
Ó 1n 12/22/222/23)
Agarwal et al. (2021b)
full-bandit
general
arm-ordering Bernoulli general
(kkvnTT)
Kveton et (2015b)
cascading- banndit
max
log(T)
Our work
value-index
max
0 (T))
attractive item, while our setting essentially removes this sequential order assumption and allows the user to browse through the items in any order and only returns the value and index of the selected item as the feedback. Another difference with the cascading bandit is that we consider more general distributions of arm outcomes. Our work also bears resemblance MNL bandits (Agrawal et al., 2019), in which the user selects an item following multinormial logit (MNL) model, which is different from our k-MAX selection model. They assume that item values are known, while handling unknown item values is one of the main challenges we are facing.
We summarize some known results on regret bounds for CMAB problems in Table 1. In the table, A denotes the gap between the optimum expected regret of a set and the best suboptimal expected regret of a set. Agarwal et al. (2021a) and Agarwal et al. (2021b) only provide distribution-ine berrbbtiooondeeeedeen regret bounds, which are worse than the ( (kkT) distrbuttion-indeennenn regret bounds that follow from distribution-dependee regret bounds.
The index feedback bear resemblance to comparison observations in ducling bandits (Ailon et al., 2014; Sui et al., 2017), which only provide which arm wins a two-way or multi-way comparisons, with the purpose of identifying the single best arm. In contrast, approach incorporates the value information to guide the learning process with the aim finding the best combination arms with the expected maximum value outcome.
1.2 SUMMARY OF CONTRIBUTIONS
Our contributions can be summarized as follows:
We introduce and investigate a novel combinatorial bandit problem, which involves maximizing the reward function based on maximum value-index feedback. This feedback structure falls between the extensively studied full- full-bandit and semi-bandee feedback types, offering slightly more information than full-bandit feedback. In contrast to the full-bandit scenario, we incorporate additional knowledge of the maximum-valuu index, a feature observed in certain real-world applications. Our work can be viewed as progression towards resolving full-bandit CMAB problems with non-linear reward functions, under relatively modest assumptions.
We introduce algorithms tailored for binary distributions of arm outcomes. We first discuss the case when the order of arm outcome values known. Then for the case when the ordering of values is a priori unknown to the algorithm, we propose variant of the CUCB algorithm that leverages the novel concept of biased arm replacement. We demonstrate that this algorithm achieves regret upper bound comparable to that observed in scenarios where the ordering of values is known in advance. Consequently, offers performance similar that achievable under semi-bandit feedback.
We extend the algorithm to address the more general case of arbitrary discrete distributions with finite supports. By establishing an equivalence relationship between the binary distributions and arbitrary discrete distributions, we reduce the general case back to the binary distribution case to solve the problem.
Organization of the paper In Section 2, we formally define the problem. In Section 3, first establish key properties of the reward function and then present our algorithms and regret bounds for the case of binary distributions of arm outcomes. Section 4 discusses extensions to arbitrary discrete distributions with finite supports. Our numerical results are presented in Section 5. Finally, summarize our work in Section 6. Proofs of theorems are provided in the Appendix.
3

---

Published as a conference paper at ICLR 2024
2 PROBLEM FORMULATION
We consider a sequential decision-making problem involving an agent and a set of n arms, denoted For each arm i E A, its outcome is sampled according to random
as A [n] 21, ..... nt. variable X; with a discrete distribution having a finite support. The outcomes of arms in all rounds are independent across both arms and rounds. Let support of the distribution of X,, where is positive integer, and 8; + +11 is the size of the support. Let pi.j = Pr[[X, = v. for j E (0. 8.), with < Σ}= =- Pi.j < Let = (0i,.... vn) and p = (Pi..... Pn), where V, = (Ui,I..... v,,,,) with V.y E [0,1], and p. = (Pr.1...... pt...). For the special case of binary distributions,
11 < U1 < .... < Vi.s. denote the values of the
pi and U; instead of P;,1 and 14 respectively. Both u and p. as well as the s; in the general case, are unknown parameters to the agent. Further discussion about the real-world implications of our assumptions regarding the arm support is provided in Appendix A.
We define J = (S 24 round i, the agent selects an action St E F. The agent observes the maximum outcome value of selected arms and the index of an arm achieving this maximum outcome value, and receives the reward corresponding to the maximum outcome value. We denote the expected reward of an action S as (p, v) [[max Xx, i E $}]. which is a function of parameters p and v.
|||
k} as the set of actions, where 0 < k
an integer. At each
The performance of the agent is measured by the cumulative regret, defined as the difference of the expected cumulative reward achieved by playing the best action and the expected cumulative reward achieved by the agent. Denote OPT v) max (rs(p, v) S E F). An (a. -ppapoooxiittion oracle takes (p': v') as input and returns a set S such that Pr(rs(p' w²) a OPT(p'
(T(p'.' x')l 2 3 where is the approximation ratio and /3 is the success probability. If the agent uses an (a, 3) apprrxximationn oracle, then we consider the (a, (), -approxximtai regret defined as
T
R(T) T a 3 OPT(p, v) -
Ts. (p. Σ
The general offiine A-MAX problem be approximately solved by a greedy algorithm achieve a (1 - 1/ee approximation, or by a polynomial-time approximation scheme (PTAS) to achieve a (1 =) approximation for any >> (Chen al., 201 6a). The binary K-MAX problem can be solved exactly using dynamic programming (Du et al., 2024), and the Bernoulli K-MAX problem can be solved exactly by ordering values and selecting the top valued items.
ALGORIHTM AND REGRET BOUNDS FOR BINARY DISTRIBUTIONS
In this section, we present algorithms and regret bounds for the k-MAX problem with max value-index feedback with arm outcomes according to binary distributions. We first establish some properties of reward functions which are crucial for our regret analysis. Next we discuss the scenario when the ordering of vI,..., Un values is known. Then, we consider the case when the ordering of ci,... Un a priori unknown. We present an algorithm and establish that it achieves the same regret bound as when the ordering is known, up to constant factors.
For the convenience of exposition, we assume that values vi..... Up are distinct. This ensures that for any action S.. there is unique arm achieving the maximum value over the arms in S, Alternatively, allowing for non-unique values can be addressed by using a deterministic tie-breaking rule. Further discussion this matter be found in Appendix B.
We define an extended set B of arms as the union of two sets of arms, namely 2 and V. The first set 2 = aij , . a,, consists of arms whose outcomes are according independent Bernoulli random variables Z,..., Zn with mean values ...... PPn- The second set V = arms whose outcomes are deterministic with corresponding values vi...., Un- Note that the outcome of each arm i E A can be written as X; = V,Z, Each time an action S₁ is played, we obtain information for some of the arms B. We call these arms triggered arms and observe their outcome values as feedback. An important observation is that when arms are ordered in decreasing order with respect to their values, lower-order arms being triggered implies that higher-order arms had zero outcomes. We define T., the number of times arm at is triggered, and TW, as the number of times arm at is triggered up to time step L.
a")) consists of n
Additional notation
For any two vectors x., ar RRD we write 2 ar' if x; 2 of for all i [n].
4

---

Published as a conference paper at ICLR 2024
3.1 PROPERTIES OF REWARD FUNCTION
For the prevailing case of binary distributions of arm outcomes, for any set S E F, under the assumption that A are ordered in decreasing order of values U1...,, Un the expected reward can be expressed as:
rs vp
Σ u:P: II (1-P)), jES:jci
(3.1)
where the product over an empty set has a value of
There are two key properties of the reward function in (3.1) that we leverage in our regret analysis: monotonicity and bounded smoothness, as we define and reason below.
Monotonicity The first property is monotonicity.
Lemma 3.1. For every S E F, (p, v) is increasing in every ps and ve-
It is clear from (3.1) that rs(p, v) is monotonically increasing in ey. Additionally, it can be shown to be monotonically increasing in pt by taking the first-order derivative with respect to ps and demonstrating that it is non-negative.
The second property is relative triggering probability modulated (RTPM) bounded smoothness, which, with a slight abuse of notation, defined as follows: for an arbitrary set of arms B with expected outcome values μe, and r's denoting the expected reward of action S.
Bounded Smoothness
Definition 3.2 (RTPM smoothness). The RTPM smoothness holds for reward functions rs if there exist constants b; >> 0 for i E [ni] such that, for any two vectors of expected outcomes and μ², for every action set S,
Irs(m) rs(w0) - Σ D.lpp p41.
RES
where th denotes the triggering probability of arm i under action S and the expected arm outcomes μ.. Note that when (p)) increasing in μe, and μ 2 pt, we can remove the absolute value in the above inequality.
The definition of RTPM smoothness is a generalization of the condition in (Wang Chen, 2017), extended to incorporate the triggering probability g...S and weight to modulate the standard 1-norm condition. This modification allows to account for arm-specific values, as we will demonstrate in our next lemma. The intuition behind this definition is that we underweight the importance of arms with small triggering probability in the expected reward, since even if we cannot accurately estimate the expected value of such arms, we incur very little loss in the expected reward due to their low triggering probabilities. This will be important point in our regret analysis.
Let S be the triggering probability for arm at and action S, and jp.$ be the triggering probability for arm of and action S. Note that p.S = IIj<;( - -P)) and p.. = 0f P.5 Pt. because arm at is triggered when all arms j < i (with higher values) has outcome Z, = 0, while arm aj triggered when arm E A is the winning arm. The following lemma is key for our regret analysis.
Lemma 3.3. The expected reward functions in (3.1) satisfy the RTPM condition with respect to the extended set B of arms, i.e. for every S. p and p', and v', it holds
Irs(p, - rs(p', v
Σ
q P.S. d/lp -1/1+ Σ pp. 1 1
Furthermore, if 2 p', then we can remove the factor 2 in the last inequality.
The lemma can be intuitively explained as follows: When an arm i E A has small value of or the corresponding arm at unlikely to be triggered (small ②) the estimation error on p. does not effect much on the reward estimate. Similarly, if the arm is unlikely to win (small Φ) the estimate error on v does not affect much on the reward estimate. This concept is crucial for proving our regret bounds. For arms less likely to win due small value small winning probability, we may not be able to estimate their value and probability parameters accurately due to scarce observations. The lemma suggests that this is not critical issue for regret analysis. To prove Lemma 3.3, we consider sequence of vectors changing from (p, v) to (p', v') and add up the changes in expected rewards. The full proof is provided in Appendix F.2.
5

---

Published as a conference paper at ICLR 2024
Algorithm 3.1 CUCB algorithm for unknown ordering of values
1: For E A, 0, T." +-0
Number of triggering times for oj and ot Initial estimation of parameters
2: For E p: 1, 6-
3: for == 1,2...., do
4:
Fori +
(l
P: 11T 00
2T,
5:
Fori A. p. t (in + p. 1). 8 t min( + p., &. Oracle is the dynamic programming algorithm in (Du et al., 2024)
P UCB indices
6:
5 Oracle(p, B)
7:
Play S and observe winner index 8² and value oi-
8:
if 0 then
Reset T 0, Tj t 1,
t Ds-.
10:
end if
11:
For i E S such that ú; 2 w;:: T <- T2 +1
12:
For i E S such that 0 > up: P: <- (1 1/T;)
13:
For i S such that 0, U-: P:- + (1 1/T, bb 1/T
14:
end for
3.2 ALGORITHM FOR KNOWN ORDERING OF VALUES
We discuss the case of known ordering of values as a theoretically important step towards the more challenging case when the ordering of values is a priori unknown to the algorithm. For the case of known ordering of values, we can solve the k-MAX problem by using the standard CUCB algorithm. For space reasons, we provide the full algorithm and regret analysis in Appendix and Appendix E.3. The estimates of parameters p and v are initialized to vectors with all elements equal to 1. At each time step in which F; is observed to be the maximum value in the selected action, we update the estimate of vy and the estimates for p: for arms in the action set ordered before j. The algorithm maintains an upper confidence bound (UCB) for both parameters and feeds the UCB values to the approximation oracle to determine the next action.
3.3 ALGORITHM FOR UNKNOWN ORDERING OF VALUES
We now consider the case when the agent lacks knowledge about the ordering of values. This lack of knowledge significantly reduces the information that can be deduced from observed feedback. To understand this, let examine the situation when the value u; of arm of is yet observed. In the scenario where the ordering of values is known, the triggering of až occurs when arm has higher value than that of the winning arm j. Consequently, we can deduce that Z, must be zero. However, in the case when the ordering is unknown, we cannot make this deduction. It remains uncertain whether Z, has value of zero or one. Consider a round t where action S, played, and arm j E S, emerges as the winner with value Uy. While the value-index pair (u5,5) j) is observed, the value for an arm i E St is still unknown. Consequently, we cannot determine whether v; < Uy or v; > Uy. In the former case, the outcome of arm i could be a non-zero value that remains unobserved, whereas it takes value of zero in the latter case. Notably, the triggering of at hinges on whether the value of v; is known. This aspect diverges from the CMAB-T framework. A conservative approach would be to apply CUCB algorithm for the known ordering case directly, and only increment the triggering count TV for arm af after v; is observed. Parameters for arm E A would be updated only when T7' * O. However, this conservative approach may cause the arms with low p; and low v; (bad arms with high risk and low reward) to be selected often, since their UCB values will be kept 0; and p. 1. This would lead to significant regret.
We propose a variant of the CUCB algorithm outlined in Algorithm 3.1, which introduces the novel concept of biased arm replacement: We do not wait to update Pa only after observing value v; but replace it with another arm with biased estimate of 0; = 1. This approach treats of as always triggered initially, allowing every arm high chance of being a winner. As result, the true winners gradually emerge, while arms whose values have not yet been observed are still given opportunities. Essentially, we extend CUCB by using a biased estimate of (p/, of) with of = 1 to replace parameters (p,, vz) of an unobserved arm. Our analysis shows that this bias can be controlled, and it still leads to a good regret bound. We present the result and an outline of the analysis below.
For each action S E F, we define the gap As = max(aOPT(p,, v) - rs v), 03. We call an action S bad if s > 0. For each arm i E A contained in at least one bad action, we define
Ajuin min A S E S. P.S. 5 0, > 0) and A A max S
o. .%

---

Published as a conference paper at ICLR 2024
0 > 0}. For every arm A not contained in bad action, we define A min Do and A max = 0. Let Amin min A and maxx = max A
S. P.S.
Theorem 3.4. For the k-MAX problem with max value-index feedback, under assumption that ordering of values is unknown to the algorithm a priori and Awin > 0, Algorithm 3.1 has the following distribution-dependedd regret bound, for some constants e1 and c2.
R(T) C1
k + log
( k
+1)
log
llog
k A min
+1 + +1)+1)
Amax + +1).
A
A min
min
Theorem 3.4 implies a regret upper bound of O((nk/ Amiu) IT)( This result aligns with the bound for the simpler case presented in Theorem D.1, up to constant factors. Furthermore, Theorem 3.4 implies ÖVvnkT) distributioo-indeeendee regret bound (Appendix E.5). For modifications to Algorithm 3.1 aimed at improving the dependency of the regret upper bound on k, please refer to Appendix E.6.
Proof sketch We outline the proof of Theorem 3.4. The complete proof can be found in Appendix E.5. Our problem does not fit into the standard CMAB-T framework. As discussed earlier, the algorithm assumes that af is always triggered and takes value zero. However, this may not be accurate when iy is actually less than the value of the winning arm. Consequently, the estimates produced by the algorithm are biased. We cannot simply apply the regret result of CMAB-T or follow its analysis to reach our desired outcome. To address this challenge, we introduce the concept of biased arm replacement. In each round f, for every arm i with parameters (pi, Dt) and TV O, we replace it with another arm having biased parameters (p's rf), where p' = P:t; and E 1. We give subscript (p', e') in the following analysis as their values depend on T,,,- The two arms have the same expected outcome but their effect on the reward among k selected arms are different yet satisfying an order property, which is shown the following lemma.
Lemma 3.5. For every set S F, (p( v) S '''
Next, we consider the contribution of action S₁ to the regret, denoted as As,, under the assumption that the approximation oracle performs well (F, Ts. (Pr. B,) 2 a OPT(P,, B,)), where Pt, 8, are the values p, 6 at the end round t. By Lemma 3.5, for each such that 1 S 8 S T, we have
a OPT(P's 2/) 2 a OP)
(3.2)
Thus,
As. S a OPT v/) - rs. (p,
aa OP - rs, v) + rs, (Pe, 0.) OPT 0.)
Srs. (pr, 8.) - v) (rs, (Pc: 0.) rs. (p',, vf)) + (rs, v/) rs, (p, v)).
The first inequality arises from condition (3.2), the second from the approximation oracle, and the third from the monotonicity of rg in and v. We refer to the term inside the first bracket as the regret caused by estimation error Ag., and the term inside the second bracket as the regret caused by replacement error A - To derive a tight regret upper bound, we show that the regret bound for the estimation error dominates that of the replacement error. This justifies the intuition behind using replacement arms. Now, let us examine these two terms separately.
By Lemma 3.3, we have
A S.
<
Σ of
S S Uz. (pi. - p(,))-
iESS
Note that we do not need to include the v; term, as v/,, = 0; = 1 for all when ez is not observed, and ofe E2 iy after ty is observed. In both cases, there is no estimation error for Uy.
We apply Lemma 3.3 to obtain
AG. 2
Σ
P.S. -P',))
Σ L (0', vz).
VES.
SES.
To sum up, we have
s, S
Σ
of
S Di, (pr,
pl,,) + 2
Σ
d
S 1/ -',,)+ + Σ g v.).
P.S
ieS.
i.
7

---

Published as a conference paper at ICLR 2024
Algorithm 4.1 CUCB algorithm for arbitrary distributions with finite supports
I: For E A. t
Number known values for arm i Number triggering times for fictitious arm b Initial estimates of parameters for the fictitious arm
For E A,, + 0, T.o +- 3: For E Pt, +- 1, 01,0 4
4:
do
Pii t 1[77 0 & Confidence radius of parameters 6: For A and j E (o o. Pe,j +- min + pt.s, 1) Rx,5 4- min(ū:, + pt.,, 13 b UCB indices use Eq. (4.2) to convert the binary form of (treated as p) to the multi-valuee form P (treated p) k-MAX PTAS oracle (Chen al., 201 6a)
5: For E and j [o(i)o, Pig +
Bloo(t
275.3
7:
8:
St Oracle(ep,
Play and observe winner index i" and value
10:
o & J.r E [o(())]} then
11:
a(1") + a(f") + +, Ti + 0, ((() + 1, (0,0(0) t
12:
end if
13: Fori S and E (o(i) such that 0.,, 2 Thi -T;; +
Fort i and j E (v)lo such that 0j > v: Pi. t- (1
1/T P
15: For i E S and E (A)] such that Ut., = v: Pi,y
+- (1 1/T 1
16:
end for
We can bound the first term by following the proof of the regret bound for the standard CMAB-T problem, stated in Theorem C.I for completeness. and the estimate p; at the time observing tú. This is because pl,, Pru; when is unknown and Pi P; afterwards. However, for both stages, our estimates are accurate such that they always lie within the confidence interval which decreases as the counter number increases.
see this, recall that we have reset the count T;
For the second term, we note that P/A, p; in the first stage, and P'., p; after observing u. Therefore, the contribution to regret by the second term is zero in the second stage. For the first stage, this term be analyzed in similar way the last term. The key observation is that P: PL., = (1 v3) S p:- This eliminates a large regret factor that would be introduced if we use the conservative CUCB approach describe before.
Finally, we note that the analysis for the last summation term is the same as the case where the ordering of values is known, since there no change the triggering process of arms in V.
Summing up the resulting bounds over time horizon T, we show that the first term dominates the other two terms, which leads our theorem.
4 ARBITRARY DISTRIBUTIONS OF ARM OUTCOMES WITH FINITE SUPPORTS
We consider the more general case of arbitrary discrete distributions of arm outcomes with finite supports, which accommodates the case of binary distributions as special case. We show that it is possible to represent a variable corresponding to an arm outcome with set of binary variables. This allows us to extend to the general case of discrete distributions with finite supports.
To see this, let X, be a random variable with an arbitrary discrete distribution with finite sup- port as defined in Section 2. Recall that Pr[X; virl Pi.j. for E {0, 10,1,.....] where Wij E [0, 1] and V;,0 0. Let X......., .i.., be independent binary random variables such that X.,, takes value U. with probability Pa,j and value 0 otherwise. We can obtain the conversion between these two set of parameters by the following equations:
Pi.i
PiJ 2ij++1 Pi.
Vj E [si]. (4.1) Psj
II (1 pa) Peg. Vj E [s.]. (4.2) 1=++1
can be readily checked that max(X.., j [s:]] has the same distribution as random variable X,. In this way, we establish the equivalence between binary variables and any discrete variables with finite support in terms of the max operator. This means that we can use our algorithm to solve the M-MA problem for any discrete distributions of arm outcomes with finite supports. We present Algorithm 4.1 for the general discrete distributions with finite support. The algorithm an extension of Algorithm 3.1, adapted to allow unknown support sizes of arm distributions.
8

---

Published as a conference paper at ICLR 2024
UCB somiee Mapritirs
1222
Jemibardt De'1
3030
Carepertiin
Sems sande
1933
LVY
Rounds
Rouncs
Figure I: Regret for Algorithm 3.1 and benchmarks used for comparison, for different distributions of arm outcomes as defined in Appendix F.
Recall that we work with binary arms with outcomes according to {X [n],j [s:]] where + I is the support size of X,. To handle unknown support size 5;, we introduce counter (i) to denote the number of observed values X; and dynamically maintain a list of these observed values. We increase this counter and reset the triggering times and probability estimates for the a arm whenever we observe a new value for X₁. On the other hand, we use a fictitious arm (denoted with index with value not know the support size, we always keep this fictitious arm and update its probability estimates just as normal binary arm. If an observed value of X; to enforce that the fictitious arm is always ordered higher than the real binary arm with value (see Appendix B tie-breaking). In the algorithm, use notation [m]] 1,, .m..
placeholder for those arms whose values remain unobserved. Since do
apply the deterministic tie-breaking rule
Note that we convert UCBs of the binary arms to multi-valued forms according to relationship in Equation (4.2) and use the k-MAX PTAS in (Chen al., 2016a) as the offline oracle. We cannot use the dynamic programming algorithm in (Du et al., 2024), because if we use the binary form, we need an oracle such that for each binary arm (i:j) with outcome X if (i,j) )) selected, then all ji,j") for j' [s:] must also be selected because they correspond to the same base arm X,. Due to the space constraint, we provide the theoretical regret guarantee Appendix E.7.
5 NUMERICAL RESULTS
We perform experiments to evaluate the performance of Algorithm 3.1 on specific problem instances. We compare our algorithm with three baseline methods: the well-known UCB algorithm treating each set of size as one arm, the standard CUCB algorithm for semi-bandit CMAB (Chen et al., 2013), and DART (Agarwal et al., 2021b) for full-bandit CMAB. We use the greedy algorithm the offline oracle. The code we use is available at: https: : thub. com/ Sket ch EXP kmax. We consider settings with distributions such that single arm changes from one scenario to another. We expect the algorithm to perform well for all three cases. For space reasons, we show the detailed setup in Appendix F. We run each experiment for horizon time of T = 5000. In each round, we select arms according to the offline oracle and sample their values for updates. We compare the reward to that of the optimal set S We repeat the experiments 20 times and average the cumulative regrets.
and sets of cardinality k = 3. We tested on three different arm
Results Figure presents the regrets of Algorithm 3.1 and three baseline methods across the three scenarios. It is evident that our algorithm achieves significantly lower regrets compared to the UCB algorithm and DART. Furthermore, our regret curve closely aligns with that of the CUCB method under the semi-bandit CMAB setting, indicating that do not incur substantial losses despite receiving much less feedback.
6 CONCLUSION
We investigated the k-MAX combinatorial mulli--rmee bandit problem under maximum inlue-index feedback. This feedback, situated between cemi-bandit and full-bande feedback. provides less information compared to semi-bandit feedback. For the binary arm case, we propose a CUCB-based algorithm that introduces a novel concept of biased arm replacement, and for the general finite support case, reduce it to the binary case and uses fictitious arm to handle unknown support sizes. Through rigorous analysis, we demonstrated that our algorithms guarantee a regret upper bound comparable that observed under bandit feedback. albeit with some constant factors.
Future research could explore the Æ-MAX problem under full-bandit feedback, as well as extending soft max objectives. Furthermore,
the --MAX objective other variants such as the second there is potential value in considering other CMAB problems under feedback scenarios between semi-bandit and full-bandit feedback, where biased replacement may also be applicable.

---

Published as a conference paper at ICLR 2024
REFERENCES
Mridul Agarwal, Vaneet Aggarwal, Christopher J Quinn, and Abhishek K Umrawal. Stochastic top-k subset bandits with linear space and non-linear feedback. In Algorithmic Learning Theory, pp- 306-339, PMLR, 2021a.
Mridul Agarwal, Vaneet Aggarwal, Abhishek Kumar Umrawal, and Chris Quinn. DART: Adaptive accept reject algorithm for non-linear combinatorial bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 6557-6565, 2021b.
Shipra Agrawal, Vashist Avadhanula, Vineet Goyal, and Assaf Zeevi. MNL-bandit: A dynamic learning approach to assortment selection. Operations Research, (5):1453-1485, 2019.
Nir Ailon, Zohar Karnin, and Thorsten Joachims. Reducing dueling bandits to cardinal bandits. In International Conference Machine Learning, pp. 856-864 PMLR, 2014.
Arash Asadpour and Hamid Nazerzadeh. Maximizing stochastic monotone submodular functions. Management Science, (2(8):2374-239) 2016.
Gary E Blau, Joseph Pekny, Vishal A Varma, and Paul R Bunch. Managing a portfolio of interde- pendent new product candidates in the pharmaceutical industry. Journal of Product Innovation Management, 21(4):227-245, 2004.
Nicolo Resa-Bianchi and Gábor Lugosi. Combinatorial bandits. Journal of Computer and System Sciences, 400441244 2012.
Wei Chen, Yajun Wang, and Yang Yuan. Combinatorial multi-armed bandit: General framework and applications. International conference on machine learning, pp. 151-159. PMLR, 2013.
Wei Chen, Wei Hu, Fu Li, Jian Li, Yu Liu, and Pinyan Lu. Combinatorial multi-armed bandit with general reward functions. Advances in Neural Information Processing Systems, 29, 2016a.
Wei Chen, Yajun Wang, Yang Yuan, and Qinshi Wang. Combinatorial multi-armed bandit and its extension to probabilistically triggered arms. Journal of Machine Learning Research, 17(50):1-33, 2016b.
Yihan Du, Srikant, and Wei Chen. Cascading reinforcement learning. In The Twelfth International Conference on Learning Representations, 2024.
Daniel Golovin and Andreas Krause. Adaptive submodularity: Theory and applications active learning and stochastic optimization. Journal of Artificial Intelligence Research, 42:427-486. 2011.
Aditya Gopalan, Shie Mannor, and Yishay Mansour. Thompson sampling for complex online problems. In International conference on machine learning, pp. 100-108. PMLR, 2014.
Antti Jekunen. Decision-making in product portfolios of pharmaceutical research and development- managing streams of innovation in highly regulated markets. Drug Des Devel Ther. 2014.
Sumeet Katariya, Branislav Kveton, Csaba Szepesvari, Claire Vernade, and Zheng Wen. Stochastic rank-1 bandits. Artificial Intelligence and Statistics, pp. 392-401. PMLR, 2017.
Jon Kleinberg and Maithra Raghu. Team performance with test scores. ACM Trans. Econ. Comput., 6(3-4), October 2018. ISSN 2167-8375
Branislay Kveton, Zheng Wen, Azin Ashkan, and Csaba Szepesvari. Tight regret bounds for stochastic combinatorial semi-bandits. In Artificial Intelligence and Statistics, pp. 535-543. PMLR, 2015a.
Branislay Kveton, Zheng Wen, Azin Ashkan, and Csaba Szepesvari. Combinatorial cascading bandits. Advances in Neural Information Processing Systems, 28, 2015b.
Dabeen Lee, Milan Vojnovic, and Se- Young Yun. Test score algorithms for budgeted stochastic utility maximization. INFORMS Journal Optimization, 5(1):27-67, 2023.
10

---

Published as a conference paper at ICLR 2024
Xutong Liu, Jinhang Zuo, Siwei Wang. Carlee Noe-Wong, John Lui, and Wei Chen. Batch-size independent regret bounds for combinatorial cemi-bandits with probabilistically triggered arms or independent arms. Advances in Neural Information Processing Systems, 19114444-4966. 2022.
Aranyak Mehta, Uri Nadav, Alexandros Psomas, and Aviad Rubinstein. Hitting the high notes: Subset selection for maximizing expected order statistics. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 15800-15810. Curran Associates, Inc., 2020.
Idan Rejwan and Yishay Mansour. Top-k combinatorial bandits with full-bandit feedback. In Algorithmic Learning Theory, pp. 752-776. PMLR, 2020.
Shreyas Sekar, Milan Vojnovic, and Se- Young Yun. A test score-based approach to stochastic submodular optimization. Manag. Sci., 67(2))1075--1992 2021.
Yanan Sui, Vincent Zhuang, Joel W Burdick, and Yisong Yue. Multi-dueling bandits with dependent arms. arXiv preprint arXiv:1705. 170.000255.0 2017.
Qinshi Wang and Wei Chen. Improving regret bounds for combinatorial semi-bandits with probabilis- tically triggered arms and its applications. Advances Neural Information Processing Systems, 30, 2017.

---

Published as a conference paper at ICLR 2024
SUPPLEMENTARY MATERIALS
A FURTHER DISCUSSION ON MOTIVATION
Our work focuses on M-MAX bandit for general arm distributions with finite, unknown support. We further discuss the real-world implications of our assumption regarding the arm support.
Unknown support Firstly, we argue that in some cases, the agent has no knowledge of the feedback scale. For example, in bidding or donation scenarios, the agent may not have access to the internal values of the bidders donors beforehand. Similarly, 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 user actually perceives. On most systems, choices may be offered 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 100, respectively. However, the user customer may value 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 each random variable, resulting in smaller regret.
Finite support We also argue that our assumption of finite support is applicable across various applications, as categorical ratings ranks commonly used in the real world. Additionally, note the possibility of extending our results to accommodate continuous reward distributions by discretizing continuous distributions. However, discretization may introduce tradeoff between discretization granularity and regret bound.
Furthermore, it is worth noting that the observation made in the previous paragraph applies here as well. In many cases, even though the support size may be infinite based the values offered by the platform (e.g., real-valued feedback), the actual value of the customer for an item may only have a few possible internal values. Therefore, treating the variable as having finite and unknown support size could effectively reduce regret in numerous practical scenarios.
B FURTHER DISCUSSION ON TIE-BREAKING
In Section 3, we assume that all values 01, .2...., Un are unique, and state that this is equivalent to allowing for non-unique values with a deterministic breakin rule. In this appendix, we provide a more formal argument for this equivalence.
Deterministic tie- bie-brekking means that whenever two arms and j appear in the same action S and their outcomes have the same values v; = Vy, and this outcome the maximum among all outcomes of arms in S, we deterministically decide which of i would win according to a predefined order. Without loss of generality, we assume the predefined order dictates that the smaller indexed arm always wins in tic-breaking; that is, if U. ey then arm i wins if < j.
For any problem instance with the above tie-breaking rule, we can convert it another instance where all values are unique, showing that the two instances essentially behave the same. The conversion involves adding lower-order digits to the current value of 's make all values unique while respecting the deterministic tie-breaking rule. The actual conversion is as follows: Suppose problem instance in the deterministic tie brebbre setting is (p, v), and without loss of generality, assume that v1 2 2 ... 2 Un- Let Ep > 0 be an arbitrarily small value. Let & = 6o/n. new problem instance (p','') such that p' p. and for all vf 02 + (n i)e. With this construction, we know that if v; > Uy then i < j. and of 0 + (n i) > Bj + (n -inn-je j)s i/;; if by and < j. then 2 = v; + (n - i)e > "y + (n - j)= = t/j- This means we have all unique values with of > 2/ ... 2r,, and the value order respects the previous value order together with the deterministic tie-breaking rule. Because p' p, we know that for any action S, the winning index distribution for these two instances must be the same. Moreover, for every i, |o - (n İ)ε < Eo. which means the reward value of the new instance arbitrarily close to the original instance. Therefore, through the above construction, we show that any problem instance under the deterministic tie-breaking rule can be viewed as an instance with unique values that are arbitrarily close the original values. This demonstrates that the problem instances under the deterministic tie- breaking rule can be treated equivalently as instances with unique values with essentially the same result.
n. Then we construct
12

---

Published as a conference paper at ICLR 2024
In the recommender system setting, deterministic tie-breaking models the scenario where customers instinctively seek additional clues or information when faced with two similar items to make a selection, rather than relying solely chance. There may be discrepancy between the value feedback based on the choices offered by the agent and the internal values of the items, depending on the granularity of the feedback scale. For example, consider four items A, B, C, and D presented to a user on a five-star scale. Initially, A, B, and C are shown, and the user favors A, rating it stars. Later, when B, C, and are shown, the user prefers B and also rates 4 stars. Although the user gives the same value feedback to both A and B, there may be additional factors not captured in the feedback, leading to deterministic tie-brekiing when choosing between and simultaneously. Random tie-breaking, on the other hand, may be of interest primarily for mathematical curiosity or theoretical exploration.
C CMAB-T FRAMEWORK AND ADDITIONAL NOTATION
We review the framework and results for the classical CMAB problem with triggered arms considered by (Wang& & Chen, 2017). In this problem, the expected reward is function action S and expected values of arm outcomes
We denote the probability that action triggers arm as p, M.S. It is assumed that in each round, the values of triggered arms are observed by the agent. The CUCB algorithm (Chen et al., 2013) is used to estimate the expectation vector directly from samples.
The following theorem pertains to the standard CMAB problem with triggered arms (CMAB-T). is assumed that the CMAB-T problem instance satisfies monotonicity and I-norm TPM bounded smoothness (Definition 3.2 with b = B for all E [n]). We will use some of the proof steps and the result of this theorem in proofs of our results.
Theorem C.1 (Theorem 1 in (Wang & Chen, 2017)). For the CUCB algorithm on CMAB-T problem instance satisfying monotonicity and I-norm TPM bounded smoothness, we have the following cetributiiondeppended regret bound,
R(T) S 576B*k
Σ
log(T)+ +
Σ
log
2Bk
+ +1)
+1)+2)
+2)
x A max + 4Bn
A
A min
min
where Amin inf S. >0,55>0' As.
We next give various definitions used in our analysis. The definitions are given specifically for binary distributions of arm outcomes.
We define two sets of triggering probability (TP) groups. Let be positive integer. For the set Z of arms we define the triggering probability group St as
S = (S o. < 2--++
We define the triggering probability group S for the set V of arms similarly. We note that the triggering probability groups divide actions that trigger arm i into separated groups such that the actions in the same group contribute similarly to the regret bound.
Let N be the counter of the cumulative number of times in TP group S is selected at the end of round t. Similarly, use NY denote the counter of the cumulative number of times i in TP group SY, is selected at the end of round t.
We define the event-filtered regret for a sequence of events {Ee} as
T
R(T, (E.) = OPT(p.v) - E
Σ (()))s.(p.))
which means that the regret is accounted for in round t only if event & occurs in round t. We next define four good events as follows:
E1 The approximation oracle works well, i.e.
F. = (rs, (p, σ) 2 OPT(p,
13

---

Published as a conference paper at ICLR 2024
Algorithm D.1 CUCB algorithm for known ordering of values
For E T; f- 0
Number of triggering times for aj Initial estimation of parameters
2: For E f; f L, 0; +1
3: for 1,,...., do
4: For A. t log((t)
Confidence radius values
27:
5: For E A. P: + min fir Pi, 11 8/ 6z
> UCB values P Oracle decides the next action
6:
S S Oracle(p, 8)
7:
Play S and observe winner index i' and value op
8:
Update 6. for winner arm i": 02.. +- 2/--
9: For E S such that i I :": T3 T; +1
10: For E S such that i < : P. + (1 -1- 1/T,)p:
11: Ps- (1 1/T pi 1/T
12:
end for
E2 The parameter vector is estimated well, i.e. for every i E [n]] and t 2 1,
No.- = (lps,-1 Pil < pi.)}
where Pr,c-1 is the estimator p. at round and Pi, == /3log(t)/(2T..c.)) We denote this event with Ng.
E3 Triggering is nice for given set of integers fmmax he(nj- i.e. for every TP group S defined by arm and I j I Jmaxx under the condition (ogg())(((() (/) < it holds - 2 - 2-, We denote this event with Gi
E4 Triggering nice for V. i.e. for every arm E A, under the condition Ni 2 3p, log(t)2), there is Th * 0. Equivalently, we can define this event in terms of TP group SY by removing the factor of p i.e., under the condition NY 2 3 log(t)2). We denote this event with G
Note that E1, E2 and E3 are also used in (Wang & Chen, 2017), and event E4 newly defined for our problem. We can easily show the following bound by using the Hoeffding's 's inequality.
Lemma C.2. For each round 2 1, it holds Pr(-g)) S n/t?
D CUCB ALGORITHM FOR KNOWN ORDERING OF VALUES
We propose the CUCB algorithm defined in Algorithm D.1. As discussed the main text, the estimates of parameters p and
initialized vectors with all elements equal 1. At each time step in which Uy is observed to be the maximum value in the selected action, we update the estimate of új and the estimates for pi, for arms the action ordered before j. The algorithm maintains an upper confidence bound (UCB) for both parameters and feeds the UCB values to the approximation oracle determine the next action.
Theorem D.1. For the K-MAX problem with max value-index feedback, under assumption that ordering of values is a priori known to the algorithm and Amin > Algorithm I.1 has the following distribution- deapedden regret bound,
R(T)= S 1=1
k log
k
++1+)) log log
Σ
(( [log
+1) + +1) A max +1).
A
A min
A min
min
where C1 and 02 are some positive constants.
In Theorem D.I, the only term in the regret bound that depends horizon time T is the first summation term. In this summation term, the summands have two terms, one scaling linearly with k/ A and other scaling logarithmically with k/ A which due uncertainty of parameters and v. respectively. Hence, we may argue that the uncertainty about values of parameters p has more effect regret than uncertainty about values of parameters The regret bound in Theorem D.1 implies Ô(VT) distribution-indeeenddee regret bound.
14

---

Published as a conference paper at ICLR 2024
To see how the regret analysis of the algorithm can be decomposed to CMAB-T problem. consider the contribution of each action to regret, i., Ås, = maxfa OPT(p, v) rss (p, v) 0). Let F. be the good event {rs, (p. 8) 2 OPT(p, 2)} meaning that the approximation oracle works well. By the smoothness condition, under Fi we have
ss. S rrs (p. TS, (p. v) v Σ S
of
(p. P.) + Σ SE
( v.).
Clearly, the first term corresponds to regret from the set of arms 2, and the second term corresponds to regret from the set arms V. We bound As, by bounding the two summation terms individually. The first summation term is standard in existing literature. For bounding the second term, need to make extra steps as our estimates for v are not more and more accurate as the number of selections of arm i increases. The UCB value for E; remains at the upper bound value until arm of is triggered once and we then know the exact value of U;. We show the proof of Theorem D.1 in Appendix E.3.
E PROOFS
E. PROOF OF LEMMA 3.1
Without loss of generality, consider {l..... k}} under assumption U1 2 ... ..22 Uk. The expected regret can be written as
sp v) = pr + (1 - P1 |2 + ................................ + (1 - 11))p-)-. ... (1 P= 1)
It is clear from the expression that (p, v) is monotonic increasing in
Let us consider (p. v) for arbitrarily fixed v. Taking derivative with respect to pt, we have
d _rs(p, v) (1-p1) ... (..(1-P:11) U; P14141+1
Ea- (1--)41) p, (1-P))p 1
dp;
We claim that the term inside the bracket is non negative. This can be shown as follows,
Σ pi+1) ... p. 1P)))pt++1
2. Ps+11/+11
128
2 (1- - Pi+1) - (1 - Pi+1 (2-1))(422/22 - - (11-htt)(L P142)P143344
IV WMM
(1 Pi++ (1 - pi+2) ... (1 pk-1)( (1:-i-pi-p))) PkUX)
IV I
(1 Pi+1)(1 Pi+2) ... ...11 pk)u:
0.
Thus, the reward function is monotonic increasing in Pi.
E.2 PROOF OF LEMMA 3.3
For the purpose this proof only, we assume that the arms are ordered in decreasing order of values. This applies to both and v'. Recall that
rs(p,v)
Σ u.P.
II
(1 11-P)) pÿ).
iES
JES:J<i
Let p- (Pi.... .p. pk) and p' (ph,..., 1/b), and (0) =p', (1)
.oi,....200 (pI,...,PP.P// Pp:.//+1..... ,K)). for
1 1 j < k, and p = p. Similarly, let v = (U1,.... 2%k and o' = (r/...., 2.)). and (0))) = v',
x0) = (vi,..., Uj ,'+t,.... v)), for < j < k and (k:) = n.
Let us define
f(p(), o()) = iidd + .... + (1 - pi) ... (1-P)-1)pp + - (1-pi) ... (1 P-))pf+ +
Clearly, we have v) (k) (())) and rs (p', ()) ()))) Note that
( ((-1)) pidi +... p1) pm)..... -oー (1--1) 10-11111/)00 1
15

---

Published as a conference paper at ICLR 2024
The only difference is caused by position j. By definition of triggering probabilities q.'² and of we can write,
(f(p!), f(p(-1), ( =
10 (p
-pjj// - (1--p/a pf+1) p/-1))/u((p) -/)1
121
sag p. p5lu3 - + u3.² 2//l3 p/1l
+ o3 (1)+1 + (1 - 1 + ....)ly - -p'l
=20 2 1//0, 1//1 + 10,
where the first inequality is due the triangle inequality and the second incquality is due to the monotonicity property. If 2 p', we only need to consider the first two terms in the second line.
Now we note that u))(p,))-r((p's w')1 = 1f(p!)) b()) - f(p b
Σ 1( x6)) 1(00-11) (
Summing over j we obtain the statement of the lemma.
E.3 PROOF OF THEOREM D.1
We consider the contribution of action S, to regret As.. for every 1. Let M, := A A Recall that As = max (a - OPT p.u rs(p, v). 0}. Assume that As, 2 Ms, where Mg = maxies Mj. Note that if As, Ms, then As, since we have either an empty set, or As, Ms, M; for some i E St.
By the smoothness condition, we have
As. S rs, (Pt, 0x) rs. (P, Σ U.,
pt)
Σ (o vz)-
bES.
Since As, 2 Ms,, we add and subtract Ms, from the last expression and we have,
As. < Ms. +2
Σ S.s (F, - -pp)+
(Us - us))
VES,
iES,
< 2
Σ P Us (pi, pi)
Mi
+ 2
pP (Ur v.)
Mi
4k
4k
ViSS.
NiES
Let us call the first term A s, and the second term A We bound Ag, by bounding the two summation terms individually.
Note that we can bound the term AG, following the same procedure as in the proof for Theorem C.I. However, cannot use the same procedure for A The key difference is that estimate for U; will not be more and more accurate as the number of selections of arm increases. We know the exact value of o; as soon is triggered once. We assume that arm is in TP group SY Let ja be the index of the TP group with S, E SY We take j = log 4k/M + 1).
Case 1: 1 I Jimax. In this case, gp... 2-
T.. (T (T.e-
vx) -2) 2. 1. 1 = 0}
Under the good event Gj, when No N 3 logg(1) 2/, the contribution to regret is zero Otherwise, it is bounded by,
(Ti vx) 2 2-
Case Je 2 Huuux In this case,
M,
S $2.2 2 <
4k
Thus the term does contribute regret in this case.
16

---

Published as a conference paper at ICLR 2024
We next calculate the filtered regret under the good events mentioned above and the event that As, 2 Ms.. Note that
T
R(T, 2 Fs. 97 9i) S
S.
tm
Am1
For the event E3 set mmx (lk M, 1). By Theorem C.1 in Appendix C, know that under good events E1, E2 and E3, the first term is bounded by
Σ LA'. S 1152k 1=1
Σ M
log(T) + 4n
and, otherwise, the corresponding filtered regrets are
R(T, -i) S (1 3)T Amar
x²
R(T, -W) z n
3
max
R(T, -7) <
x²² log
Σ
M
4k
+
A
max.
Now, we focus on bounding the contribution of the second term regret. Note that under event E4,
A
KjgT (M,,(Mi,, 8)
i=1
where
2.2
if log (T) 2
K2 (M, 8)
0
if 3 3log (T) 2
For every arm i and j 2 1, we have
-
(T)
Σ
(M, S
RiaT Mi, 8) = 6 log(T).
2=0
Hence, the contribution of the second term to regret is bounded by
N T-T-1
(M,, 8) s
Σ
log
4k
+ +1)) log(T).
M;
==0
The filtered regrets for the case when event E4 fails to hold is bounded by,
R(T, 9
Pr(-G))
n
max-
We obtain the distribution regret bound by adding up the filtered regrets calculated above. The corresponding distributioon-ideeeendde regret bound is implied by taking M; / /16nk/7 for every i E [2).
E.4
PROOF OF LEMMA 3.5
Without loss of generality assume that [k] and V1 2 02 2 2 Ug. Recall that we can write rs(p, v) Pidi 1 + (1 pi )2 + ... p1) ... (1 PR 1)pU
Now, for p == (p1, .Pi.....PP. -P&) and p' = ( p,),, let
p ( (V..... p/, p
and define similarly w(d) for and v' After changing p1 to p' = p and 01 r/ 1, 11( (1)) = P1 + (1 2 +... (1 - -101) ... Pk- 11-1)
Clearly have (1) (22)) r)(p,v). Following the same argument, can see that (2) x(2)) (L) ((1)). Continuing this way (k) x())
can prove the lemma.
17

---

Published as a conference paper at ICLR 2024
E.5 PROOF OF THEOREM 3.4
By the RTPM smoothness condition, as discussed in the main text, we have
As.
s C,,( -P,,)) + Σ o ol
p/) +
Σ iES,
of (1 vi).
SES
sES
Key step: bounding the contribution of each action regret Let M, A min Assume that As. 2 Ms, where Ms maxies M, As in the known value ordering case, we can bound As, such that,
As. - Ms. +2
ph+))+ Σ p' ( -Pk,)) +2
Σ
P.S
p.) +
Σ c
(1/,e vi)
SE
iESt
iESt
Mi
Mi
<
Σ
Ui (T,,t -p',))
+4
Σ
of t/ -v1)
8k
81
VESt
VIES
Mi
+
Σ VEES
qi
(t'ee - 0x))
(E.1)
8k:
Let j; be the index the TP group St such that St E St., We bound As, by bounding the three summation terms in (E.1) separately.
Bounding the first term. Recall that we reset T, and Nigh at the time we observe V;. This because when b2 is unknown (first stage) and ph., = p; and v//, e, after observing
Pí,, = p, and v/, (second stage). A key observation is that within both stages estimates are accurate in the sense that under event E2, the approximation error decreases as the counter number increases in the following way.
3 llg((t)
Pr.e Pb. S. 2p, = V
2T
We note that for the second stage where u; is observed, this term is similar to the A term in the known value ordering case. Specifically, under event E3,
18 l8gg
}
Di. ph,, S min
(V
2 2- No Ni
thus
72 2 log(T)
2 Sul pl..) S min
2-22-
Nig.t-1
For the event E3, let jmax = log(8k/MMM HM; 1). the case ji 2 Jmax + this term does not contribute regret we have,
d $p., (p.,
- ph.1) 2 <
M;
8k
Similarly, for 1 S js S Jince there is no contribution to regret if N i 2 (.,((M,) where
4608 2- 1og (T)
(M)(M)
M
For the first stage, we note that the event E3 not required to hold, as we treat of as always triggered and the triggering is always nice for Z in the first stage. Thus for the first stage we have,
(log(T) T
Ca. - Ph.a) S min {
This term does contribute to regret if T 2 (M,) where
(M)) = 384A2 (T)
M
18

---

Published as a conference paper at ICLR 2024
Bounding the second term. Take Imax log(8k/M, + 1). Similarly as the first term, in the ji 2 Jmax + the contribution to regret is non-positive. For S Jr S Imax as p,, = peu,, we have
of 14, p4.)) 22.22 p:(1 ox).
Under the event E4, we know that the contribution to regret is zero if N 1 3p," log(T) 2/. Otherwise, it is upper bounded by 2- 2 Pt- Bounding the third term. Take Jimax log(8k/A) + 1). In the case j; 2 Jmax + 1, the contribution
to regret is non-posiine non-positive. For I J. - J'max we have of g.. - 2- p.. thus
P. (U,t vi) - 2 2 p.p. p.p. = 2 pp p. 1[ = 0}.
Under the event E4, we know that the contribution to regret is zero if Ni 3p, logg(T) 2 Otherwise, it is upper bounded by
(BLL - 2. 2
Note that this bound is the same as the bound for the second term.
Summing over the time horizon Next, we sum up As, over time and calculate the filtered regret under the above mentioned good events and the event that As, Ms. i.e, R(sAs, 2 Fr, 97, (.).
By equation (E,1), know that the filtered regret be upper bounded by sum of three terms the time horizon 7. By Theorem C. in Appendix C, we know under good events E1, E2 and E3, the second stage of the first term bounded by
2
Σ of P.S.
(pr. Ph.e)
M, Sk
<
2304k
Σ
log(T) + 4n
M.
iES.
and, otherwise, the corresponding filtered regrets are bounded by,
R(T, -F) < (1 3)TA
n n max
R(T, -))
R(T, - <
π² log
8k
+1)Amax:
Amax.
M;
1=1
To bound the first term, we also need to derive a bound for the first stage when the value is not observed. This is bounded by,
(M.)
Σ S P
(Dit Ph.
M
logg(T)
64k
Σ
1
log(T).
8k:
M₁
VES.
Following similar analysis for the Ag
term of Theorem D.I, have that
T
Mi
8k
c.
S
(o/,
< 12
log
+ 1
log(T).
8k
M;
t=1
S.
i=1
Similarly, we can bound
M;
8k
P.S
(p
pl..)
<
24
log
+ 1) log(T).
8k
M;
1=1
GES
The filtered regret for the case where event E4 fails to hold is bounded by.
T
Pr(-9:) A Amax S =² n n
R(T,
<
6
i=1
19

---

Published as a conference paper at ICLR 2024
We obtain the distribution-depee deeeeddent regret by adding up the filtered regrets calculated above. Similarly as before, the distributionninneeeenn regret is implied by taking M, v /64nk/T for every i [n]. The iettribution-nddppeeeeee regret bound is Ö(VT), the same as cascading bandits upper bound.
R(T) c1 (VnkT + log (VnkT+1)) log + 0 ((log (VnkT++ + +1) + 1) Amax + +1)
E.6 FURTHER IMPROVEMENT OF REGRET BOUND DEPENDENCY ON k:
We can further improve the regret upper bound dependency l from k log(k) using TPVM condition in (Liu et al., 2022). We outline the steps and changes as follows.
Algorithm In the algorithm, besides maintaining confidence bound for the mean value of p, also maintain a confidence bound for its variance as Algorithm 1 in (Liu et al., 2022).
Verification for TPVM Following the notations in (Liu et al., 2022). let p' = p + S 17. then
P.S ?
(rs(p.v) rs(p',0)) S B
Σ
B1
P.S
T/ +
Σ
ofp
1/1
(1 p:)pp
:ES
iE
iE8
which satisfies TPVM with respect the base arm Z with (B,,, B1, (2, 02)
To see this, consider the first term of the RTPM condition in Lemma 3.3,
12 %
Σ S q dplp
p/l 2
Σ
P.S
Ps(1
pb)
Ps 1/11
ps(1 p.)
iE8
iES
22 pp
Ps 1/11 2
pr(1 1i(1-pip pi)
1pt p/12 5
Σ
q (1
P.S
Pi)Pt
iS
iES
where the first inequality is due to definition of triggering probabilities, and the second inequality is due to the fact that Eies q... 1 and v/
Regret analysis Recall that we have As, S AS, + A. We make changes to bound the estimation error A We note that the replacement error will not be affected. We define F, = {As, S 24 and F, = fAs, I 2- ). We note that R(T) < R(T,FF Rr), We consider the filtered regret under F...
We replace the confidence radius specified in the good event (F2) by the confidence radius specified in Lemma 8 of (Liu et al., 2022),
(E2) The parameter vector p is estimated well, i.e. for every i E [m] and t 2 1,
NR. = ( - Pel < p(c))
where Pi,e-1 is the estimator of p. at round t and Pı. == 4/3 p:(1-p;) T--1.
28
+ T--1.
Under Fe and (E2), have
log(t) T;
log(t)
As. < 8/3
Σ min
1/28
qp + 56 Σ min
1/28 qf T
SES:
iES.
We note that we can still use the technique of arm replacement to show that within both stages our estimates for are accurate. As explained in the proof of Theorem 3.4, the first stage corresponds to a degenerated case where arms are always triggered, and the second stage corresponds to the case of standard probabilistically triggered arms. Following steps of Lemma and Lemma 11 in Appendix C.3 in (Liu et al., 2022), we can conclude that
log k tog(T)
R(T,F) 5O
Σ log
A
A
20

---

Published as a conference paper at ICLR 2024
And from Theorem 3.4, we know that
k
SO
log
log(T))
A min
Therefore, we improve the regret upper bound from (((k/)) log T) to O((log k/ log T).
E.7 THRORETICAL. GUARANTER OF ALGORITHM 4.1
We claim the comparable regret bound upper bound in Theorem 3.4 holds for Algorithm 4.1.
Theorem E.1. For the k-MAX problem with max value-index feedback, under the general case of arbitrary discrete distributions of arm outcomes with finite support defined in Section 2 and under assumption Amin > O, Algorithu 4.1 has the following (1 E, 1) cetrrbuttiondependdee regret bound when using the k-MAX PETAS oracle from (Chen et al., 2016a) that guarantees (1 -6) approximation,
R(T) SI
Σ 1=1
k min
+ log
( ++++)) 8, log (Tg(T)+02)) Σ 31 ((18g
( k
(
A (A
1-+1 +11 +1
A Amax +
A
min
We explain the derivation steps in details.
Let U U111 < Vg,s, denote values of the support of distribution of X;, where 8; is positive integer, and 8; 9,+1 1 the support size. Recall that pi.j = Pr[X; = Uc,5 for j E {0, 1, ................. ........) $ with 2j=1 Pi.j S
By Equation 14.1), for each variable X,, can replace it with set of binary variables X 's. We provide more detailed explanation to justify this reduction. For ease of discussion, we restate the equation here:
if S < st if j 84-
Pi.j
Pi,s;
The key verify that Y; max(Xi, 1 [s.]] has the same distribution as the original random variable X,. In fact, for every Vijj in Xi's support, the probability of Y; V.jj is equal to the probability that for all j' > j. Xig = and X,, Vt.j- By Equation (E.1), the latter probability is
1-E Pi. Pi. E-E Pc. - (- 1iy PL.
y Pi.') Pij (1 I-
Pcj
111 = Pr.j- Therefore, the probability of Y, = Vi,5 is the same as the probability of X; = Uz.j. Since Y, can only take values from the support values of X,, we can see that Y; and X; have the same distribution.
Pi.
Given the above fact, we can see that for each variable X,, we can replace it with variables Xt, ss so that when select set S of X:'s, max {X, S} has the same distribution max (x.j, S,j E [s:]]. because max ( X E 5} = max Yú i E S} max max (Xi,, j E [si]], i S}
max (Xit, S.j E [s]]-
Consider the contribution action S, to regret. By the above reduction,
As. S a OPT v) rs, (p,v) a OPT v) - rs. (p.
For the remaining steps, we will treat the regret rs. (p. v) that of the of equivalent binary arms.
We note that we convert the UCBs of the binary arms (p. T) to their multi-valued forms and use the K-MAX PTAS offline oracle. Again, the approximation oracle works well, by Equation (E.1), we have rss (p, ū) 2 OPT(p, (p. 8). Therefore, by the arm replacement implementing on the set of binary arms,
As, S (rs, (p, v) rs, (p', v()) + (r.s, (P/, rss. (p, v))
By the RTPM condition applied the set of binary arms,
81
As. < Σ
Σ
Ri (piss---ppp Σ
S.S
Vig
P.S
(1/ v..))
(ES.
j=0
iE8. f=0
21

---

Published as a conference paper at ICLR 2024
Semtibunde CUCB
Mid UCB
800
V48 UCB
Sumt duundi cuce
Our Garalgenthm
elger
Cumulrtrr leeeet
600
Canulorbes
920
800
220
200
Rourds
Rounds
Figure 2: Regret for Algorithm 4.1 and considered benchmark algorithms, for different distributions of arm outcomes.
In Algorithm 4.1, we relax the assumption of knowing the support size of arm distributions by introducing counter (i) for each arm X,, This means for some and binary arms {X... 8; ,.....&;
{i)} whose values fi,j have not been observed, we replace them with a single fictitious binary arm, instead of s; ai) fictitious arms. This is clearly justified, as the replaced arms have values of = 1. For each term inside the summations, we can bound following the arguments as in Theorem 3.4. We can obtain the regret upper bound as claimed.
F SUPPLEMENTARY INFORMATION FOR SIMULATIONS
In this section, we provide supplementary information for Section 5 on numerical results.
Setup We consider settings with arms and sets of cardinality k 3 for the following distributions of arms:
D1 (0.1, 0.2, 0.9)T. p such that p; 0.3 for 1 s 6, and pt 0.5 otherwise.
D2 Similar to D1, but we modify arm to have a larger probability P1 = 0.9.
D3 Similar to DI, but modify the last arm have smaller probability ps 0.2. Despite having the same expected value as arm 6, arm 9 is included in the optimal set.
Note that the optimal super arm is S (7, 8, 9) in all cases. Distributions D1, D2 and DD3 represent different scenarios. D1 is the base case. In D2, there a stable arm with low value, while D3 there high-risk high-reward arm. Both not easy to observe and cause challenges for our algorithm design, especially the latter type of arms, which can outperform less-risky arms under the maximum value reward function.
We also verify Algorithm 4.1 for the general case of arbitrary discrete distributions of arm outcomes with finite supports. For each arm distribution, we slightly vary the non-zero arm values by adding a small value perturbations to such that each arm takes two different non-zero values centered around u/- We assume the small value perturbation follows Gaussian distribution with mean ;; and standard deviation 0.03.
We show the regrets of Algorithm 3.1 and three baseline methods in Figure 1. The regret plots for the categorical settings using Algorithm 4.1 shown in Figure 2. We plot the 1- approximation regrets instead of (1 1/ee-e)-appoooo ffe)-approximatioon regret as the offline greedy oracle performs much better than (1 1/e) approximaaiii in this case. We can see that our algorithm performs well, achieving much lower regrets in all cases.
Regret plots
Discussion on DART We note that DART does not perform well our binary setting. This can be attributed to mainly two reasons. As mentioned in the section of related works, DART assumes that arms can ordered according to their mean rewards obtained by playing actions containing them. However, in case, arm values cannot be determined in this way. DART is therefore inherently unsuitable for our tasks. Moreover, DART requires a threshold A to accept and reject. In our case, hard for DART to distinguish between good and bad arms. To reach sufficiently small threshold, DART takes over 10000 rounds of iterations. On the other hand, our algorithm can correctly order arms at 5000 rounds, as shown in the regret plots. For these reasons, we do not include DART benchmark for the categorical setting.
22


Reviews:
[{"review_id": "F1f2tiH73h", "reviewer": "Reviewer_hUTf", "summary": "The authors consider MAB problems where the action set is combinatorial (subsets with cardinality k) and the reward function is the max reward over the base arms.  Base arms are discrete valued and the authors consider both known and unknown support.  The authors propose a variant of semi-bandit feedback where the agent (only) learns which base arm had the largest value.   The authors then adapt the CUCB algorithm for this setting and obtain problem independent regret bound dependence of $\\tilde{O}(\\sqrt{T})$.", "questions": "1. Motivation – What would be a motivating application of K-max with the max-index feedback for which the arm supports would be unknown? Elaborate more on how one or multiple applications motivate the problem set up you consider.  The ‘concrete’ scenario mentioned in the introduction of recommender systems “The goal is to display a subset of k product items to a user that best fit the user preference. The feedback can be limited, as we may only observe on which displayed product item the user clicked and their subsequent rating of this product.”  For most systems I can think of, the numerical feedback would be on a known, fixed scale (like 1-5 stars, or on a 1-10 scale) meaning the support is identical for all arms and known a priori.\n\n\n\n### Minor \n2. In the contributions, “Our work may be seen as a step towards solving full-bandit CMAB problems with non-linear reward functions under mild assumptions.”  Can you elaborate on that (if that's kept in the main contributions)?  The feedback model and modifications to CUCB to appear specialized for the max reward function and thus the work does not seem extendable to other non-linear rewards.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "### Strengths\n\n- Novelty – There is some novelty in the problem, method, and analysis.  K-max has been studied under semi-bandit feedback (all base arm values revealed; Chen et al. (2016)) and for special cases (Bernoulli arms) studied under bandit feedback (see note about (Agarwal et al. (2021)) below).  The proposed max-index feedback considered shares some similarity with other feedback models (cascading, triggering, dueling, etc) but I am not aware of this specific feedback model being studied previously.  The algorithm and analysis largely (though not trivially) follow that for the CUCB for probabilistically triggered arms -- the realization and index of the maximizing base arm are modeled as two arms that are triggered.  \n- Significance – I think with stronger motivation for the problem set up considered this would be of some interest to the CMAB community.  \n- Quality – I did not go through the proofs, but from my reading the work appears sound.", "weaknesses": "## Weaknesses\n### Related work\n- There’s an uncited work that is relevant -- https://ojs.aaai.org/index.php/AAAI/article/view/16812 “DART” by the same authors of (Agarwal et al. (2021)), for picking K sized subsets with a non-linear rewards.  The former does not have the same FSD assumption as the cited work and in terms of horizon $T$ dependence they get $\\tilde{O}(\\sqrt{T})$ problem independent upper regret bounds and lower bounds.  They show that K-max for independent Bernoulli arms satisfies the assumptions in that paper.  \n\n\n\n### Writing & Clarity \nThere are a few (addressable) issues with the writing that affect readability.  \n\n- Is the regret $R(T)$ formally defined?  I didn’t see it in the problem formulation or anywhere before it is upper bounded in Theorem 3.4.  In addition to being unambiguous about cumulative vs instantaneous, regret vs pseudo-regret, you mentioned approximation algorithms for the general offline problem and so it becomes ambiguous if you are working with regret or an $\\alpha$-regret (and if so specifically a $\\alpha=1-1/e$ regret or an $\\alpha=1-\\varepsilon$ regret).  \n\n- 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.  That should be formally discussed in the problem setup or at least before pseudocode for the algorithm that calls it.  Also, for completeness the procedures that are proposed to be used for an oracle should be formally described (appendix would be fine).\n\n\n- Algorithms – \n    - (minor) I found the discussion in the text confusing about maintaining confidence bounds on not only $p_i$’s but also $v_i$’s, which are deterministic.  Looking in the pseudocode for the $v_i$’s there aren’t any confidence bounds – instead the values are set optimistically to $1$ and (since the support is deterministic) updated exactly once on the first time that arm is the maximizer (if that occurs).  Calling it a confidence bound is confusing in my opinion.\n    - (Minor) – In Section 3.2 I would suggest linking to the pseudocode earlier, such as at end of second paragraph “Due to limited space, the pseudocode is presented in Algorithm B.1.”  \n\n- I think it would be valuable to have a fuller discussion of the hardness for the offline setting and corresponding approximation methods (Bernoulli (which seems easy based on (Agarwal et al. (2021))’s DART results), non-Bernoulli binary (you mention can be solved exactly with dynamic programming, but are hardness results known for the non-Bernoulli binary case?), and general (you cite Chen et al. (2016a).) to give the reader a fuller intuition.  E.g. explicitly state that the general offline problem (and non-Bernoulli binary offline problem too) is NP-hard; don’t just state that greedy methods can get an $\\alpha$ approximation.\n\n\n### Experiments\n- Semi-bandit CUCB is good to include; it would be good to also include Agarwal et al. (2021))’s DART since that has  $\\tilde{O}(\\sqrt{T})$ guarantees under bandit feedback when the arms are Bernoulli.  It would probably do worse since its assumptions might not hold for non-Bernoulli arms, but it might be more competitive than UCB.\n- The distributions in the experiments are all binary?  That should be mentioned in the main text.  \n- “three different arm distributions representing different scenarios” is quite generic and suggests potentially distinct problems (such as modeling three different applications), but the ‘different scenarios’ are almost identical manually constructed examples with a single arm changed from scenarios 1 to 2 and then from 2 to 3.  That is ok to do but the description in Section 5 should be revised to reflect both of those issues (manually designed and single arm changes from one scenario to another).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Et8I8pquol", "reviewer": "Reviewer_AX9C", "summary": "This paper studies the problem of combinatorial bandits with maximum value reward function with a intermediate feedback between semi-bandit and full-bandit. In particular, the learner chooses a subset $S_t \\\\subseteq [K]$ of $|S_t|=k$ arms as the action at each round $t$ and incurs the maximum realized reward $\\\\max_{i\\\\in S_t} X_t(i)$ among those arms, where $X_t(1),\\\\dots,X_t(K)$ are the i.i.d. stochastic rewards of the $K$ arms at round $t$. The learner then observes the incurred reward together with the identity $I_t \\\\in \\\\arg\\\\max_{i\\\\in S_t} X_t(i)$ of any arm achieving such a reward within the action. The authors consider discrete distributions with finite support (always including $0$) for the rewards and propose an algorithm achieving a regret bound for binary distributions that is comparable to previously-known bounds under more informative semi-bandit feedback. The results are first presented for the case of binary distributions with known ordering of arms with respect to the nonzero value in the support, and then generalized by first relaxing the assumption of a-priori known ordering. The paper also discusses extensions to discrete distributions with finite supports and presents numerical results that validate their theoretical findings.", "questions": "- Is the presence of $0$ in the support strictly necessary? Or do you believe it is possible to lift this assumption? If so, could you hint at the intuition for doing so?\n- Please, see weaknesses and further elaborate on those points.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The paper considers a feedback structure for combinatorial bandits with maximum reward function that lies in between commonly studied semi-bandit and full-bandit feedback structures in combinatorial multiarmed bandit problems, recovering similar guarantees as the more informative semi-bandit setting for binary distributions.\n- The authors present regret bounds for problem instances with stochastic arm outcomes according to binary distributions that always have $0$ in their support. The authors also argue how their techniques could generalize to the case of discrete distributions with finite support.\n- The experimental results show that their proposed algorithm indeed achieves similar performance as an algorithm with semi-bandit feedback in this specific setting.\n- The problem of combinatorial multiarmed bandits with maximum reward function can be relevant to many real-world scenarios.", "weaknesses": "- The paper could benefit from more detailed explanations of the proposed algorithm and its intuition. There is also no explicit definition of regret $R(T)$, which is a fundamental concept in the entirety of this work, especially for readers that might be unfamiliar with the combinatorial bandits literature. Its definition is only left implicit in how results are presented and proved, but the presentation could benefit from a formal definition in the problem formulation section. Only the \"event-filtered regret\" is defined, but its definition is deferred to the appendix. Finally, the authors keep referring to $R(T)$ as the regret, while its actually a more relaxed version known as $\\\\alpha$-regret (could be mentioned at least once in the problem setting).\n- The paper focuses on binary distributions of arm outcomes always including $0$ in their support, which may not be representative of many real-world scenarios. The paper could benefit from exploring more general distributions of arm outcomes. Even if the authors argue about adapting to more general discrete distributions with finite support, these are also quite limited in the applications of their techniques. Furthermore, no theoretical guarantee is provided for there latter distributions, and the proposed reduction is expected to introduce a linear dependence in the support sizes to the regret. This is therefore unfeasible and undesirable for distributions with large enough supports, let alone countably infinite (or even continuous) supports as per many common distributions.\n- The baseline methods used in the numerical results are never explicitly described or properly referenced. It is therefore unclear how meaningful the experimental results are without understanding what assumptions are made in the other algorithms used in the comparison.\n- In line 7 of Algorithm 3.1 it says the learner is able to observe value $v_{i^*}$ of $i^*$ while it might happen that no value is observed if all arms in $S_t$ for a certain round $t$ have realized value equal to $0$.\n- Some of the main ideas adopted in this paper, while adjusted to fit a setting with simpler distributions but less informative feedback, seem to be taken directly from Chen et al. (2016a) without striking changes.\n\nReferences:\n- Chen et al. (2016a): Wei Chen, Wei Hu, Fu Li, Jian Li, Yu Liu, and Pinyan Lu. \"Combinatorial multi-armed bandit with general reward functions\". *Advances in Neural Information Processing Systems*, 29, 2016.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ocQAqYJeVj", "reviewer": "Reviewer_AcYK", "summary": "This paper considers combinatorial bandits with maximum value and index feedback. The new feedback model lies somewhere in between semi-bandit and full-bandit feedback models. The new feedback model has applications in recommender systems. Assuming that the maximum value is unique, if we know the maximum value and the index of the base arm that achieves the maximum value, then we also know that all base arms selected in that particular round have reward realizations less than or equal to the maximum reward. The authors analyze the gap-dependent and gap-free regrets under base arms with finite support. They show that under these assumptions, the dependence of the regret on the batch size k and time matches with that of semi-bandit feedback algorithms.", "questions": "Based on my initial reading, there are several unclear parts in the paper. I will be able to provide a better assessment of the quality of the paper after the authors' feedback. Answers to the following questions are crucial for my reassessment. \n\n- Section 3 rests on the assumption that for any action $S_t$, there is a unique arm achieving the maximum value among all arms in $S_t$. Then, it is argued that this can be extended to the non-unique values using a deterministic tie-breaking rule. My question is about implementation issues regarding this deterministic tie-breaking rule in a recommender system. A user who likes two of the shown movies out of k can randomly decide to watch one of them. Imposing a deterministic tie-breaking rule puts a restriction on the behavior of the user. I wonder if this tie-breaking rule can be justified in practice, specifically for applications in recommender systems, for instance, in the one that I mentioned above. \n\n- How is $q^{\\mu,S}_i$ related to $q^{p,S}_i$ and $\\tilde{q}^{p,S}_i$? \n\n- As a starting point, the authors extend the CUCB algorithm to accommodate for max value and index feedback for the case with Bernoulli rewards and known ordering of values. The claim is that most of the parts of the regret analysis of CUCB for CMAB-T remain valid under the new setting. Is it the case that in max-value max-index feedback, the estimates of base arm outcomes $p_i$ are still unbiased? This seems crucial for event E2 from the previous work Wang & Chen 2017 to apply, which achieves unbiasedness thanks to semi-bandit feedback. \n\n- Please comment on the batch-size dependence of the distribution-free regret bound derived from B.1. Is it the same as cascading bandits upper bound? \n\n- What about batch size independent regret bounds as in Liu et al. 2022, NeurIPS? Is it possible to obtain them under your current assumptions? Does triggering probability and variance modulated smoothness (TPVM) condition hold for your reward function? If so, what is the most general case in your paper so that this assumption holds? If this condition holds, then providing TPVM-based regret bounds will be good.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This paper considers an important CMAB problem with real-world applications. There exists a wide spectrum of feedback models that lie between semi-bandit and full-bandit feedback models. Max-value feedback with an index is one of them that is mainly encountered in recommender systems. Although it seems to provide just a little more information than the full-bandit feedback setting, i.e., the index of the arm that achieves the max reward, correct utilization of this additional information results in performance almost matching with the semi-bandit feedback model. \n\nThe paper nicely develops the theory for the new setting by starting from the Bernoulli reward case with known support values. It starts building the algorithms by borrowing tools from the CMAB-T framework. In particular, extension to arbitrary distributions with finite supports by using the representation of the outcome of a single arm with finite support as multiple binary variables and using an appropriate action selection oracle is interesting. This equivalence allows the use of the techniques formed for Bernoulli rewards in addressing the more general and challenging case.", "weaknesses": "The most practically relevant setting for the proposed work seems to be the case with arbitrary distributions of arm outcomes with finite supports. Technical development in the paper starts from the simpler cases and gives the reader an expectation that the special cases are solved to provide intuition for the general case. Algorithm 4.1 looks like the pinnacle of the paper. However, is there any result (theoretical or experimental) related to this algorithm? If the regret bound in Theorem 3.4 still holds, putting proof of this would be nice. Moreover, simulations are concerned with the Bernoulli case. Verifying the performance of Algorithm 4.1 in simulations would be nice. \n\nAnother weakness is related to the deterministic tie-breaking rule, which is proposed as a way to accommodate non-unique arm reward values. I wonder if there is an application in which this tie-breaking is in the control of the decision-maker instead of its environment. More about this is asked in the questions part of the review. \n\nOther weaknesses are mostly related to presentation issues and pinpointing the difference between the estimators used compared to the ones in the semi-bandit feedback CMAB-T setting. Please see the questions section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "x1KvRIAml5", "reviewer": "Reviewer_oHUd", "summary": "The paper focuses on solving a combinatorial multi-armed bandit problem that incorporates both maximum value and index feedback, a structure that falls between semi-bandit and full-bandit feedback scenarios. The authors introduce an algorithm and establish regret bounds for the case where arm outcomes are subject to arbitrary distributions with finite supports. They examine a broader range of arms and employ a smoothness condition to analyze regret. The algorithm achieves regret bounds that depend on the specific distribution as well as bounds that are distribution-independent, and these results are similar to those found in more informative semi-bandit feedback situations. Experimental evidence validates the algorithm's effectiveness.", "questions": "What is the main obstacle in finding the lower bound for the exact problem setting you are considering ?\n\nWould it be possible to extend this work to unbounded rewards ? Like Gaussian ones ?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper presents an innovative feedback structure called \"max value-index feedback,\" positioning it between the well-explored semi-bandit and full-bandit feedback frameworks. This introduces a fresh approach to understanding combinatorial bandit problems. The authors establish regret bounds for their algorithm, encompassing situations that rely on distribution-specific and distribution-agnostic characteristics. These bounds are demonstrated to be on par with those obtained in more informative semi-bandit feedback settings. In the paper, algorithms are introduced for both binary and arbitrary discrete distributions of arm outcomes, incorporating the max value-index feedback, and they exhibit effective performance.", "weaknesses": "The known ordering case is a simple extension of the cascading bandit.This should be more emphasis that this is not a contribution but rather a simple first case for better understanding of the new and non-trivial unknown ordering case.\n\nAlthough 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. The paper focuses on one specific problem, the k-MAX bandit problem with maximum value index return, and I'm not convinced that this is a fundamental step towards dealing with the full-bandit CMAB problem.\n\nThe paper is specifically centered on addressing a particular combinatorial multi-armed bandit problem that incorporates maximum value and index feedback. However, it does not delve into exploring how this approach might be applied to different types of bandit problems or alternative feedback structures. The paper does not thoroughly clarify the algorithm's limitations when dealing with diverse problem settings.\n\nThe 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. The implications of these assumptions on the algorithm's performance and regret bounds are not exhaustively examined.\n\nWhile 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. To gain a more comprehensive understanding of the algorithm's performance, a more thorough evaluation on a wider range of problem instances and a comparison with existing approaches would be beneficial.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)