Contextual Set Selection Under Human Feedback With Model Misspecification

Shuo Yang 1 Rajat Sen 2 Sujay Sanghavi 3

Abstract

owner aims to select the most effective set of ads, i.e., theones that most engage the customer and potentially generate
the most profit. Yet, in real-world datasets, realizability –the assumption of an exact functional relationship between
human feedback and the features related to the context – israrely satisfied. Misspecification happens in several ways:
for example in personalized recommendation systems, multiple users might share an account occasionally. There canalso be less benign causes such as non-genuine click trafficor reviews injected into the feedback by adversarial thirdparty agents. In this paper, we delve into the challenge oflearning optimal set selection from online human feedback,even when faced with model misspecification.

A common and efficient way to elicit human feedback is to present users with a set of options,and record their relative preferences on the presented options. The contextual combinatorial bandits problem captures this setting algorithmically;
however, it implicitly assumes an underlying consistent reward model for the options. The settingof human feedback (which e.g. may use different
reviewers for different samples) means that there
may not be any such model – it is misspecified.
We first derive a lower-bound for our setting,and then show that model misspecification canlead to catastrophic failure of the C2 UCB algorithm (which is otherwise near-optimal when
there is no misspecification). We then propose
two algorithms: the first algorithm (MC2 UCB) requires knowledge of the level of misspecification
ϵ (i.e., the absolute deviation from the closest wellspecified model). The second algorithm is a general framework that extends to unknown ϵ. Our
theoretical analysis shows that both algorithms
achieve near-optimal regret. Further empiricalevaluations, conducted both in a synthetic environment and a real-world application of movie
recommendations, demonstrate the adaptabilityof our algorithm to various degrees of misspecification. This highlights the algorithm’s ability toeffectively learn from human feedback, even withmodel misspecification.

The stochastic contextual bandit is a general framework foronline learning problems, where at each round the learnerobserves a context c ∈ C, then chooses one out of m arms
and observes a reward for only the arm chosen. The problem has been widely studied for the last two decades andhas found uses ranging from online advertising, recommendations (Yue and Guestrin, 2011; Li et al., 2016) to drug
testing and medical trials (Durand et al., 2018; Villar et al.,2015). The task is to minimize regret commonly defined as
the difference in collected reward from an optimal policy.
For instance in online advertising, the context can be thebrowser history and search query from a user, the arm can bea specific advertisement out of many possible choices andthe reward can be a click or a purchase. The corresponding
task is then to maximize the expected click or purchase rate.
The main challenge is to achieve a delicate balance between
exploitation i.e., choosing the best arm based on the current
belief and exploration i.e., choosing a rarely chosen arm togather more information about the environment.

1. Introduction

Further, many real-world problems have many slots insteadof one (e.g., choosing multiple ads to show). It is commonlyreferred to as the contextual combinatorial bandit problem,
where at each time-slot the learner is allowed to select a
set of k < m arms. The problem has mostly been studied under the semi-bandit feedback where the learner can
see the rewards from the individual arms in the chosen set.
Prior works (Qin et al., 2014; Yue and Guestrin, 2011) havecommonly made some reasonable assumptions on the valueof a set of arms like sub-modularity or other smoothness
assumptions. Both these works study the problem under alinear function class, i.e., the mean reward of an arm is an

In many practical applications, the objective is to learn the
optimal set selection under a certain context. Take, for instance, the field of advertising, where multiple slots on a
webpage are available for displaying ads. Here, the business
1

Department of Computer Science, University of Texas atAustin, TX, US 2 Google, CA, US 3 Department of Electrical andComputer Engineering, University of Texas at Austin, TX, US.
Correspondence to: Shuo Yang <yangshuo ut@utexas.edu>.
Interactive Learning with Implicit Human Feedback Workshop at
ICML 2023.

1

Contextual Set Selection Under Human Feedback With Model Misspecification

unknown linear function of the arm’s feature.

2014). We show that our algorithm has slightly better performance than C2 UCB in the original setting
while outperforming C2 UCB by a large extent in thepresence of small model misspecification. Thus ouralgorithm can lead to robustness by preventing catastrophic failure, with little/no performance cost.

Model misspecification, as previously exemplified, is overwhelming in real-world problems with human feedback.
This is especially true when the chosen function class islinear, which is a common choice for theoretically analyzed
algorithms in contextual combinatorial bandits (Qin et al.,2014; Yue and Guestrin, 2011). Therefore, it is important
to develop and analyze algorithms that can provably work
under model misspecification without complete knowledge
about the level of misspecification.

2. Related Work
The combinatorial multi-armed bandit problem has beenstudied extensively in the last decade. There are several
works in the semi-bandit feedback setting (Chen et al., 2013;
Combes et al., 2015; Kveton et al., 2015; Merlis and Mannor,
2019; Yang et al., 2021), where the learner observes theindividual rewards of the arms in the set of arms chosen ateach round, along with the total reward for the composite
action. This is also the feedback model in our paper. The
problem has also been studied under full-bandit feedback
where only the composite reward of the whole set of arms
chosen can be observed (Cesa-Bianchi and Lugosi, 2012;
Lin et al., 2014; Agarwal and Aggarwal, 2018; Rejwan andMansour, 2020).

In this work we highlight the need for such robust algorithms in two ways, (i) theoretically, we show that a popularalgorithm for contextual combinatorial bandit (Qin et al.,2014) can have a catastrophic failure in the presence of misspecification, while our algorithm can avoid it without theknowledge of the exact level of misspecification and (ii) ina practical movie recommendation task we demonstrate that
our algorithms well adapt to the misspecification that naturally arises in the real-world dataset, and can outperformthe commonly adopted algorithm.
The main contributions of this paper are as follows,

The contextual version of the problem has been studiedin (Yue and Guestrin, 2011) under the linear function class,where the value utility from choosing a set of arms is submodular in terms of the individual rewards. Qin et al. (2014)
also study the problem under linear rewards, where the reward derived from a set of arms is a function of the individual rewards that satisfies some monotonicity and Lipschitz
properties. We closely follow the model in (Qin et al., 2014),
however as we will show both theoretically and empirically,
their algorithm is not robust to misspecification and canundergo catastrophic failure. Our algorithm, on the other
hand, can adapt to unknown model misspecifications. Notethat the contextual combinatorial bandit problem has beenstudied under general function classes recently in (Sen et al.,2021), however, they can only adapt to known misspecification and their algorithm only provably works for the casewhen the set function is just the sum of individual rewards.
In fact, we show that as a corollary of our results, we can
extend their algorithm to the unknown misspecification case.

• (Hardness) We first characterize the hardness ofmodel misspecification in linear contextual combinatorial
by providing a regret lower bound banditspof Ω kϵ (d − 1)/(8 log(m))T as Proposition 4.1,
where m is the number of arms, ϵ the level of misspecification, d the dimension of the arms’ features
and T the time-horizon. We also show that a popularalgorithm for this setting C2 UCB (Qin et al., 2014) canhave a catastrophic failure in the presence of model
misspecification, leading to arbitrarily large regret onsome problem instances. In particular, the C2 UCB
has regret kT /2, which is significantly worse than thelower bound O(kϵT ) when ϵ is small.
• (Algorithms) We first propose Algorithm 1 for the misspecified setting where the misspecification level ϵ isknown to the learner. In Theorem
that the √ 5.1, we show√ 
e d kT + kϵ dT , thusalgorithm has a regret of O
essentially matching our lower bound. Next we propose Algorithm 2 that works even when ϵ is unknown
to the learner. Algorithm 2 corrals multiple instancesof Algorithm 1 with different values of hypotheticalϵ’s, and is shown to have near-optimal regret.

The linear bandits problem was first studied in the misspecified setting in (Ghosh et al., 2017), where they propose
a robust algorithm that switches between OFUL (AbbasiYadkori et al., 2011) and UCB (Auer, 2002) based on ahypothesis test. It was shown in (Lattimore et al., 2020)
that the OFUL algorithm itself can be easily made robust
to known model misspecification. In fact our algorithm
for the known misspecification case can be seen as an extension of the algorithm in (Lattimore et al., 2020) to the
combinatorial setting. Takemura et al. (2021) have recently
come up with a robust version of LinUCB (Chu et al., 2011)that works without knowledge of the misspecification level,• (Empirical Validation) Through simulated experiments, we show that our algorithms can significantly
outperform the C2 UCB (i.e., ours achieve sublinear
regret while C2 UCB yields linear regret). We then validate our algorithm on the Movielens dataset (Harper
and Konstan, 2015) in a setting similar to (Qin et al.,2

Contextual Set Selection Under Human Feedback With Model Misspecification

maxSt E[Rt |ct , St ], i.e., the expected reward of the optimal
set given contextPct . The goal is to minimize the cumulativeT
regret R(T ) = t=1 Regt .

however their algorithm is not easily implementable. Foster
et al. (2020) have recently shown how to adapt to model
misspecification for contextual bandits under general function classes, however it is unclear how their algorithms canbe adapted to the combinatorial setting. There is also a
growing body of literature on adversarial corruption. Most
works in this area like (Seldin and Slivkins, 2014; Lykouris
et al., 2018; Gupta et al., 2019) study the non-contextual
K-armed setting. A recent work (Bogunovic et al., 2021)
has examined the problem in the context of Gaussian process bandit optimization. None of the prior works consider
the combinatorial contextual bandits setting. The contextual
bandit work√in (Bogunovic et al., 2021) can tolerate epsilon
up to O(1/ T ). Our regret bounds degrade gracefully withany ϵ, and we can achieve the same regret scaling with T .
However, it is important to note that we can only handle an
oblivious adversary which we believe is good enough formany real-world applications.

In this paper, we focus on a setting where an arm’s expectedscore rt (i) := E [ert (i)|ct , St ] comes from a linear modelwith some misspecification (Section 3.1) and the expected
reward of a set St is determined by a function of {ri }i∈St ,with some general properties (Section 3.2).
3.1. Misspecified Linear Model
The linear contextual combinatorial bandits problem has
been widely studied under the well-specified linear model:rt (i) = θ∗⊤ xt (i) (Qin et al., 2014). Since practical datasets
are unlikely to be well-specified w.r.t the linear function
class, recent work has begun to study the misspecified linear
model for contextual bandits (Lattimore et al., 2020).
Here we extend the line of recent work on the misspecified
model to contextual combinatorial bandits. Specifically, we
consider the case where the expected score rt (i) follows a
misspecified linear model:

Note that all the above works in misspecified bandits try toachieve a regret scaling of O(ϵT ), which is also the naturallower bound for most of the problem settings. The desideratum is for this linear (in T ) term to degrade gracefully withthe level of misspecification. Indeed algorithms that are
not robust to misspecification can have regret O(cT ) underϵ-misspecification where c is a constant with c ≫ ϵ (Lattimore et al., 2020). This is in particular concerning when
ϵ is small (e.g., ϵ = T −1/3 , as the algorithms have regret
linear in T while it is possible to achieve O(T 2/3 ) regret).

(i)

rt (i) = θ∗⊤ xt (i) + ∆t ,(i)where ∆t captures the misspecification, which can dependon the arm i, the played set St , and can potentially be different in different time step t. In this paper, we consider
bounded misspecification, which can be formalized as thefollowing assumption. Note that when it is clear from the(i)context we will drop the superscript in ∆t and just use thenotation ∆t .

Closely related is a growing body of literature on modelselection via corralling different bandit algorithms both in
the adversarial setting (Agarwal et al., 2017) and in thestochastic setting (Cutkosky et al., 2020; Arora et al., 2021).
Our algorithm that can adapt to unknown misspecification isbased on the stochastic corralling idea but explicitly adapted
to model misspecification, which can lead to sharper guarantees and much simpler algorithms.

Assumption 3.1 (Bounded Misspecification). For any time
step t ∈ [T ], arm i ∈ [m], and set S, we assume the mis(i)specification to be uniformly bounded as ∆t≤ ϵ.

The online learner might not know the misspecification level
ϵ. In subsequent sections, we first present a near-optimalalgorithm for the known ϵ scenario. Then we propose analgorithm that can adapt to an unknown misspecificationlevel. We show that our algorithms enjoy near-optimal regret
guarantees.

3. Problem Setting
We consider the following contextual combinatorial bandits
problem: At every time step t, the online learner observes
a context ct generated by the environment according to a
fixed context distribution DC . For the context ct , the arms
in set A = [m] are featurized as {xt (1), · · · , xt (m)} ⊂ Rd .
Based on {xt (i)}i∈[m] , the online learner selects k distinctarms, which we denote as St .

3.2. Set Reward Function
The expected reward Rt of set St is a general functionof the expected scores rt (i) for the arms i ∈ St and thearms’ embedding x therein. We denote the set reward
function to be fx (rt , St ), where x is the embedding of
the arms, rt is the vector of all m arms’ expected scores:
rt := [rt (1), · · · , rt (m)]. For brevity, we use f (rt , St ) in
the rest of our paper.

After the set St is played, the online learner observes aet forscore ret (i) for each arm i in set St , and a reward R
the set St , both generated by the stochastic environment.
Given the context
h ct , theireward expectation of St is denoted
et |ct , St . Correspondingly, the regret at
by Rt := E R
time step t is defined as Regt = Rt∗ − Rt , where Rt∗ :=In order to develop efficient algorithms, we need to impose
the following regularity assumptions (Qin et al., 2014):
3

Contextual Set Selection Under Human Feedback With Model Misspecification

Assumption 3.2 (Monotonicity of f ). For any S, if r(i) ≤r′ (i), ∀i ∈ S, we have f (r, S) ≤ f (r′ , S).

bound which holds both when the online learner knows ordoes not know the misspecification level ϵ.

Assumption 3.3 (Lipschitz continuity of f ). There exists a universal constant C > 0 such that for any two′′scoresqP r, r and any S, we have |f (r, S) − f (r , S)| ≤2′Ci∈S [r(i) − r (i)] .

Proposition 4.1 (Lower Bound for Misspecified Contextual
Combinatorial Bandits). There exists a set of arms’ features{xt (1), · · · , xt (m)} , t ∈ [T ], such that for any algorithm,
there is a θ∗ for which
s
 m
d−1
.
R(T ) ≥ kϵmin T,
8 log(m)2kHere we present two commonly seen examples that satisfy
the assumptions above.
P
Example 1 (Summation). f (r, S) =i∈S r(i) clearlysatisfies the assumptions.

Remark 4.2. The interesting regime is when m ≫ kT ,i.e., there is a large number of arms and the online learner
cannot play q
them all. The lower bound then becomesd−1
R(T ) ≥ kϵ 8 log(m)T . The linear in T term is unfortunately unavoidable.

Example 2 (Probabilistic Coverage). Consider the observed
score ret (i) being a Bernoulli random variable with expectation rt (i) and set reward function being f (r, S) =1 − Πi∈S (1 − r(i)). This f (r, S) measures the probability
that the set S has at least 1 positive scored arm. It is easy toverify that f (r, S) is monotone and 1-Lipschitz continuous
w.r.t r.

Proof Sketch: The proof follows by constructing a setof m arms, with features almost orthogonal to each other.
The misspecification is set such that all but the optimal arm
has reward 0. Therefore any algorithm learns nothing until
it includes the optimal arm into the played set, which inmexpectation takes min(T, 2k) steps. The environment canbe constructed
such
that
playingeach sub-optimal set inq
d−1
duces kϵ 8 log(m)regret (details deferred to Appendix A).
Combining the two parts completes the proof.

The online learner may not have direct knowledge of the set
reward function f (·, ·). Instead, we assume that the online
learner has access to an oracle O, which takes an estimate of
the arm scores b
rt = [brt (1), · · · , rbt (m)] as input and returns
the corresponding optimal set: O(brt ) = argmaxS f (brt , S).
Notice that there is no necessity for estimating the set reward function f (·, ·), as the online learner has the oracle O.
The main challenge in achieving optimal regret is to estimate the unknown parameter θ∗ in the presence of model
misspecification ∆t .

4.2. Catastrophic Failure from Not Adapting to
Misspecification
Algorithms not adapting to misspecification can have an
arbitrarily large gap to the lower bound in Proposition 4.1.
Here we focus on contextual combinatorial bandits algorithm C2 UCB (Qin et al., 2014, Algorithm 1), which isnear-optimal for linear models but does not adapt to misspecification. Specifically, C2 UCB estimates θ∗ by an online
ridge regression based on the arms’ scores.

4. The Hardness of Model Misspecification
Here we show the hardness of the linear contextual combinatorial bandits problem with model misspecification.
We focus on thePsimple setting with set reward function f (r, S) =i∈S r(i). The hardness is two-folds:
Information-theoretically, we show a regret lower boundin the presence of model misspecification (Proposition 4.1).
This lower bound holds for all possible algorithms and represents the hardness of model misspecification. Algorithmically, we show that a previously established near-optimalalgorithm for contextual combinatorial bandits (i.e., notadapted to misspecification) can be arbitrarily far from theinformation-theoretic lower bound (Proposition 4.3). This
corresponds to the hardness and challenge in designing effective algorithms.

θbt =

λI +

t−1 X
X
τ =1 i∈Sτ!−1⊤xτ (i)xτ (i)

t−1 X
X

!
reτ (i)xτ (i) .

τ =1 i∈Sτwhere λ > k is the ridge regression regularization. The
UCB for each arm i is calculated asq−1
rbt (i) = θbt⊤ xt (i) + βt xt (i)Vt−1
xt (i),(1)
Pt−1 P
where Vt−1 = λI + τ =1 i∈Sτ xτ (i)xτ (i)⊤ and βtscales the uncertainty (variance) to give the right confidence
interval. The set St is constructed by taking the arms with
top-k rb(i). The next result states that C2 UCB can be arbitrarily far from the regret lower bound in Proposition 4.1.

4.1. Regret Lower Bound
The lower bound here is a natural extension of the lower
bound for misspecified linear bandits (Lattimore et al.,2020). Recall that m is the number of arms, d is the dimension of arm’s feature xt (i). We have the following lower

Proposition 4.3 (Failure of Ignoring Misspecification). Forany ϵ > 0, there exists a problem instance with horizon T ,dimension d = 2 and misspecification level ϵ, such that the4

Contextual Set Selection Under Human Feedback With Model Misspecification

regret of C2 UCB is R(T ) = kT /2, which does not become
smaller when ϵ is small.
Remark 4.4. Comparing the regret in Proposition 4.3 withe
the corresponding regret lower bound of Ω(kϵT). We seethat the regret of C2 UCB is worse by a factor of 1/ϵ. Thisis clearly sub-optimal when ϵ is small.

Algorithm 1 M ISSPECIFIED C ONTEXTUAL C OMBINATORIAL(MC2 ) UCB FOR K NOWN ϵ
1: Input: Misspecification level ϵ, online ridge regression coefficient λ2: Initialize: V0 ← λI, b0 ← 0
3: for t = 1, · · · , T do
−14:
θbt ← Vt−1
bt−1
5:
Calculate rbt (i) according to Equation (2)6:Invoke oracle O with rbt (i), i ∈ [m] to calculate set St andplay set St
7:
Observe the stochastic arms score {ert (i)}i∈St and reward
et
R
P
8:
Update Vt ← Vt−1 + i∈St xt (i)xt (i)⊤ and bt ←P
bt−1 + i∈St ret (i)xt (i)9: end for

Proof Intuition. By carefully setting the misspecification∆t , a very small ϵ can lead to subtle differences between theestimate θbt and the true parameter θ∗ , which in turn leads
to the selection of a set St having constant regret (i.e., notdepending on ϵ). The ratio of the actual regret R(T ) and thelower bound kϵT can therefore be larger than any constantξ, by setting ϵ ≈ 1ξ .
Remark 4.5. As a comparison, we will present an algorithm
in the next section (Algorithm 1) adapted to model misspecification. The algorithm is nearly optimal, in the sense that
there exists a problem independent constant ξ0 ∈ R+ , such)√that kϵTR(T≤ ξ0 for all k, ϵ and T .
log TRegret Analysis. We now state our main result for the
known ϵ case. Without loss of generality, assuming boundedparameters ∥θ∗ ∥2 ≤ 1, ∥xt (i)∥2 ≤ 1 and bounded feedback
ret (i) ∈ [0, 1] for all t ≥ 0 and i ∈ [m], for any 0 <(i) and xt (i) to satisfy suchδ < 1, as one can rescale retq
assumptions. Setting βt = d log( 1+kt/λ) + λ1/2 andδ
λ > k, we have the following regret bound.

One particular regime of interest is when ϵ = Θ( √1T ).
While the lower bound √Proposition 4.1 suggests that it ispossible to achieve O(k T ) regret, our lower bound problem instance shows that the C2 UCB can only achieve a
linear Θ(kT ) regret. As we will see in the next section,
our proposed
algorithm (Algorithms 1 and 2) can achieve√
O(k T ) regret, which matches the lower bound and avoids
the linear regret.

Theorem 5.1 (Regret Upper Bound for Algorithm 1). With
probability at least 1 − δ, the regret ofAlgorithm 1 is√√ √√e ( d + λ) kT d + kϵ dT , where d is theR(T ) ≤ O
dimension of features xt (i), k is the size of St .
e notation ignores the logarithmic terms. See ApThe O
pendix B for the complete analysis. The regret bound has√ √√e ( d + λ) kT d ,two parts: well-specified bound O
which matches the established regret bound for wellspecified(Qin et al., 2014); and misspecified bound √ models
√e kϵ dT , which nearly matches the Ω(kϵ dT ) lowerObound in Proposition 4.1.

5. Known Misspecification Level ϵIn this section, we present the algorithm when the misspecification level ϵ is known. The algorithm incorporates the
misspecification into the optimistic arm estimate, which
gives a valid UCB for each arm in the presence of model
misspecification. Further, we prove that the proposed algorithm is nearly optimal for all general (monotone andLipschitz continuous) set reward functions f (r, S).

Theorem 5.1 Proof Intuition: The proof relies on showing that rbt (i) is always an optimistic estimate of rt (i) despite the ϵ misspecification (Lemma B.2). Conceptually,
this avoids under-estimating the arms belonging to the optimal set and converging to a sub-optimal set. Further, theregret of Algorithm 1 is closelyof
P related
Pto the “tightness”
estimate rbt (i), measured by t∈[T ] t∈St (brt (i) − rt∗ (i)).
The summation of the first two terms in Equation (2) minusrt∗ (i) can be bounded exactly as the C2 UCB analysis, andthe summationof the last two terms in Equation (2) gives√ethe O(kϵdT ) term.

Algorithm. The algorithm is inspired by the recent workon misspecified contextual bandits (Lattimore et al., 2020).
At time t, the algorithm constructs optimistic estimates rbt (i)for all arms:q−1
rbt (i) =θbt⊤ xt (i) + βt xt (i)Vt−1
xt (i)
+ϵ

t−1 X
X

−1
xt (i)Vt−1
xs (j) + ϵ,(2)

s=1 j∈Ss

Pt−1 P−1
bt−1 , bt−1 =with θbt = Vt−1eτ (i)xτ (i),τ =1i∈Sτ rPt−1 P
Vt−1 = λI + τ =1 i∈Sτ xτ (i)xτ (i)⊤ . Recall that reτ (i)is the observed stochastic score for arm i at time step τ . The
online learner then queries the oracle O with the optimistic
estimate br to obtain the set St . See Algorithm 1.

6. Unknown Misspecification Level ϵIn this section, we present an algorithm and the corresponding regret bound that works without knowledge of the misspecification level ϵ. Our proposed algorithm can be viewed
5

Contextual Set Selection Under Human Feedback With Model Misspecification

probability. The “UCB shift” term is inspired by (Cutkosky
et al., 2020) and has two-fold implications: intuitively, theshift makes the base algorithm selection biased towards Al
with smaller hypothetical misspecification level ϵl ; technically, the shift makes the final regret bound depends only on
ϵl∗ := minl ϵl ≥ ϵ, instead of depending on all ϵl . Note that
ϵ is the true misspecification level unknown to the online
learner.

as a meta algorithm built upon base algorithms designed forthe known ϵ case. Our theoretical analysis shows that analgorithm designed for known ϵ case can be coupled withthe proposed meta algorithm to work in the unknown ϵ case,at the cost of a log2 T multiplicative factor in the regretbound. We further instantiate the result with two different
base-algorithm implementations to show the generality andthe nearly optimal regret bound.

Besides the typical UCB-like base algorithm selection, themeta algorithm is also equipped with base algorithm elimination - to eliminate the base algorithms with hypothetical
misspecification level smaller than ϵ. Any base algorithm
Al satisfying the following inequality will be eliminated:

6.1. Algorithm
The algorithm for unknown misspecification level ϵ employs
multiple base algorithms designed for the known ϵ case,with each of the base algorithms Al having hypotheticallmisspecification level ϵl = √2T . The putative or promised
regret bound of base algorithm Al is typically in the formof:
RegAl (T ) ≤Reg0 (T )| {z }+

Well-specified regret

κϵ T| {zl },T (l,t) 

X≥RegAl (T (l, t))
+3

(3)

p

(5)

log(T 3 L/δ)T (l, t).

Misspecified regret

Recall that µblτ −1 is the empirical reward average of base
el isalgorithm Al when it is invoked for τ − 1 times. Rτ
the observed set reward when Al is invoked for the τ -thtime. RegAl (T (l, t)) corresponds to Equation (3), which isthe promised regret of base algorithm Al played for T (l, t)
steps, if Al has the correct misspecification level ϵl (i.e.,ϵl ≥ ϵ).

On top of the base algorithms, there is a meta algorithm thatchooses one of the base algorithm Al to construct and play
set St at each time step t. The meta algorithm conceptuallytreats each of the base algorithms Al as an “arm”, andadopts a UCB-like algorithm to choose Al . Though we are
not the first to combine base bandits algorithms (see recent
progress in (Pacchiano et al., 2020; Cutkosky et al., 2020;
Arora et al., 2021)), our algorithm is specially designed forthe misspecification problem and is therefore much simpler.
Specifically, the optimistic estimate for base algorithm Al
is:Intuitively, µblτ −1 serves as an approximate proxy ofl,∗Rτ (i.e., the optimal expected reward for the time
step when Al is invoked for its τ -th time).
Theelimination
criterionisthenapproximately
comparing
PT (l,t)  l,∗ el Rτ − Rτ with the promised regret boundτ =1PT (l,t)  leτl is significantly
RegAl (T (l, t)). If τ =1 µbτ −1 − Rlarger than RegAl (T (l, t)), it implies that the base algorithm Al has wrong hypothetical misspecification level ϵland should be eliminated. See Algorithm 2 for the pseudocode.

U (l, t) := µblT (l,t−1) − κϵl|{z}| {z }

UCB shift

s



τ =1

where the “Well-specified regret” Reg0 (T ) corresponds
to the regret when there is no misspecification (e.g.,√√ √e ( d + λ) kT d for Algorithm 1); andReg0 (T ) = O
the “Misspecified regret” κϵ√l T is induced by model mise
specification (e.g., κ = O(kd) for Algorithm 1).

Reward Avg.

eτlµblτ −1 − R

6.2. Regret Analysis!

(4)

We now present our main result for the unknown ϵ case. We
again assume bounded parameters ∥θ∗ ∥2 ≤ 1, ∥xt (i)∥2 ≤ 1and bounded feedback ret (i) ∈ [0, 1] for all t ≥ 0 andi ∈ [m].

The “Reward Avg.” term is the empirical reward average of base algorithm Al , defined as µ
blT (l,t−1) :=Pt−1 e1τ =1 Rτ · I(lτ = l), where T (l, t − 1) :=T (l,t−1)P
t−1
τ =1 I(lτ = l) is the number of times that Al is invoked
up to time step t − 1. The “Uncertainty of base algorithm
Al ” corresponds to the uncertainty of the empirical reward
average, where L is the total number of base algorithms Al
and δ is some hyper-parameter corresponding to the failure

Theorem 6.1 (Regret Upper Bound for Algorithm 2).
With probability at least
1 − 4δ, the regretof Algorithm 2 is R(T ) ≤ 1 + log2 T + log2 T RegAl∗ (T ) +p(1 + 4 log T ) 8T log(T 3 L/δ), where RegAl∗ (T ) is theregret bound for base algorithm Al∗ , with l∗ =argminl ϵl ≥ ϵ.

+ min 1,|32 log(T 3 L/δ).
T (l, t − 1){z}

Uncertainty of base algorithm Al

Corollary 6.2. If the base algorithms {Al }l implement
Algorithm 1, the regret of Algorithm 2 for the un6

Contextual Set Selection Under Human Feedback With Model Misspecification

Algorithm 2 M ISSPECIFIED C ONTEXTUAL C OMBINATORIAL

Theorem 6.1 Proof Intuition: The interesting part is toprove the overall regret only depends on ϵl∗ , where l∗ :=argminl ϵl ≥ ϵ. Consider step t and let Alt be the invokedbase algorithm. The single step regret can be rewritten as:(MC2 ) UCB FOR U NKNOWN ϵ
1: Input: Time horizon T , online ridge regression coefficient λ
2: Base Algorithms Initialization:
Base algorithms
A1 , · · · , A⌈ log T ⌉ , where Al implements Algorithm 1 with2lRt∗ − RTlt (lt ,t) = Rt∗ − U (l∗ , t) + U (l∗ , t) − U (lt , t)
|
{z
} |
{z
}

hypothetical misspecification level ϵl = √2T
3: Initialize: Set step counter T (l, 0) = 0 and empirical reward
average µ
bl0 = 0 for all baseA
 algorithms
 l . Initialize active
base algorithms set L1 = 1, · · · , log2 T .
4: for t = 1 to T do
5: Calculate optimistic estimate U (l, t) for all base algorithms
Al according to Equation (4)6:Choose base algorithm Alt with lt = argmaxl∈Lt U (l, t)
7:
Let base algorithm Alt choose and play a set St
8: Observe the stochastic arms score {ert (i, St )}i∈St and reet .
ward R
9:
Send {ert (i, St )}i∈St to Alt for its updates
10:
Update T (lt , t) = T (lt , t−1)+1 and T (l, t) = T (l, t−1)
for l ̸= lt
Peτ · I(lτ = lt ) and11:
Update µblTt(lt ,t) = T (l1t ,t) tτ =1 R

(a)

(b)

+ U (lt , t) − µ
blTt (lt ,t−1)
|
{z
}
(c)

+µ
blTt (lt,t−1 ) − RTlt (lt ,t)
|

{z
(d)

}

Intuitively, (a) only depends on l∗ . As lt is selected at timet, (b) is smaller than 0 and therefore is ignored in the upperbound. (c) has a −κϵl term, which originates from the UCB
shift term in the U (l, t) definition (Equation (4)). Finally,(d) has a κϵlt term, since Alt has a κϵlt T misspecified regret.
Note that the κϵlt in (c) and (d) cancels. The regret R(T )therefore only depends on ϵl∗ .

µblT (l,t) = µ
blT (l,t−1) for l ̸= lt
if elimination criterion Equation (5) is satisfied for lt then12:
13:
Lt+1 = Lt − {lt }
14:
else
15:
Lt+1 = Lt
16:
end if
17: end for

7. Experiments
In this section, we evaluate the proposed algorithms on asynthetic environment and an environment derived from areal-world dataset. The results show that our proposed algorithm (MC2 UCB) is significantly better than C2 UCB (Qinet al., 2014) (which is near-optimal for the well-specified
contextual combinatorial bandits) when the underlying environment is misspecified. Further, MC2 UCB closely matches
the performance of C2 UCB when the underlying environment is nearly well-specified.

known
ϵ can be bounded as: R(T ) ≤ √ misspecification√ √√e ( d + λ) kT d + kϵ dT .
O
Compared to the lower bound in Proposition 4.1, the regretbound in Corollary 6.2 is nearly optimal. Algorithm 2 is a
general-purpose algorithm for leveraging multiple instancesof a known misspecification base algorithm to obtain analgorithm for the unknown ϵ setting. In this context, we
can extend our results to a setting where rt (i) is a generalfunction of the context and the arm features (not just a linear
function θ∗⊤ xt (i)). The base algorithm can be Algorithm 1in (Sen et al., 2021).

Synthetic Experiments. The synthetic environment is constructed in the following way: We first generate 100 arms
with features x(i) and the vector θ∗ from a 10-dimensional
spherical Gaussian distribution N (0, √110 I10 ). For the wellspecified linear model, the score for the arm i at time step t
is generated as r(i) = x(i)⊤ θ∗ + ηt , where ηt ∼ N (0, 0.1)
is noise. The goal of the online learner is to find the optimal
set of 3 arms, which maximizes the sum of expected scores.

Corollary 6.3. Consider the setting where f (r, S) =
P
(i)
(i)
∗
<ϵ
i∈S ri and rt (i) = g (ct , xt (i), i) + ∆t s.t. ∆t(unknown to the learner). Suppose g ∗ lies in a known finite
function class G. Then Algorithm 2 applied with Algorithm
1 in (Sen et al., 2021) as a base algorithm has a regretpe k mT log(|G|) + kϵ√mT ,guarantee of, R(T ) ≤ O
e hides some polylog factors.
where O(·)

To create misspecification, we first rank the arms according to the inner product x(i)⊤ θ∗ in descending order andlet B denote the set of arms with indices in {30, · · · , 39}.
Intuitively, B is a set of bad arms in the well-specified environment. We change their scores to be r(i) = x(i)⊤ θ∗ +ϵ+ηt , ∀i ∈ B, where ϵ controls the level of misspecification.
Specifically, we set ϵ = 2, which completely changes thethe optimal set when comparing to the one under a wellspecified linear model θ∗ .

The above corollary generalizes the result in (Sen et al.,2021) to unknown misspecification level ϵ. We provide amore detailed result as Corollary C.1 in the appendix. Notethat as noted in (Sen et al., 2021), the above result can begeneralized to efficiently learnable infinite function classes.

We evaluate three algorithms: “MC2 UCB with ϵ = 2” correspond to Algorithm 1 with ϵ = 2. “MC2 UCB with unknown ϵ” corresponds to Algorithm 2, which adopts 3 base7

Contextual Set Selection Under Human Feedback With Model Misspecification

Regret15000

Accuracy

MC2UCB with unknown
MC2UCB with = 2
C2UCB

20000

0.7

10000
5000
0

0.6 0
0

1000

2000 3000
Steps

4000

50

5000

C2UCB
MC2UCB with = 0.5
MC2UCB with = 2.0
MC2UCB with unknown
100 150 200 250 300
Steps(a) No artificial misspecification

Figure 1: Performance of different learning algorithms ina misspecified environment. MC2 UCB with known ϵ (Algorithm 1) and unknown ϵ (Algorithm 2) significantly outperforms the C2 UCB. More importantly, C2 UCB converges
to the wrong set and has a linear regret. This shows that theMC2 UCB algorithms can well adapt to misspecification andavoid catastrophic failure.

Accuracy

0.6
0.4
0.2

algorithms with hypothetical ϵ in {0, 0.5, 2}. “C2 UCB” implements the Contextual Combinatorial UCB (Qin et al.,2014), which is designed for the well-specified contextual
bandits. The average regret (and standard deviation) of 5
runs are reported in Figure 1.

0

50

C2UCB
MC2UCB with = 0.5
MC2UCB with = 2.0
MC2UCB with unknown
100 150 200 250 300
Steps(b) First 25 steps misspecified

Figure 2: In the “No artificial misspecification” environment(Fig. (a)), the MC2 UCB with known ϵ = 0.5 and MC2 UCB
with unknown misspecification yield slightly better performances, which shows that the MC2 UCB algorithms canwell adapt to the misspecification that naturally arises in areal-world dataset. Further, in the misspecified environment(Fig. (b)), MC2 UCB algorithms offer significantly higher
accuracy.

Application to Online Movie Recommendation. We also
evaluate the performance of our proposed algorithms ona real-world problem. The environment is derived froma popular recommendation dataset: Movielens-1M, whichcontains over 1 million ratings of 3952 movies by 6040
users.
We construct the environment similar to (Qin et al., 2014).
Specifically, we split the users into a training set (containing
5740 users) and a test set (containing 300 users with morethan 100 ratings). We then use a rank-16 matrix factorizationon the ratings from the training set to create movies’ features.
Those movie features are used as arms’ features (xt (i)) in
the online learning environment.

with/without artificial misspecification). We set ϵ = 0.5
or 2 for MC2 UCB with known misspecification, and set
MC2 UCB with unknown to adopt 3 base algorithms withhypothetical ϵ in {0, 0.5, 2}. The results in Figure 2 are theaverage and standard deivation of 300 testing users. The
result shows the superior performance of MC2 UCB, as it
significantly outperforms the C2 UCB when the model is
misspecified and loses nothing in the nearly well-specified
environment.

For each of the users in the testing set, the online learningalgorithm recommends 30 movies to the user in every time
step t. A movie with a rating of 4 or 5 will have a score of 1,
and other movies have a score of 0. The algorithm interacts
with the user for 150 times (i.e., T = 150). The performancet|
is measured by recommendation accuracy: |P∩S
|St | , where
P is the set of movies that the user gives rating 4 or 5.

Acknowledgement
This work is supported by NSF grant 1934932.

For the misspecified environments, we consider the casewhere the first 25 feedback come a different model: The
environment draws a θ ′ from spherical Gaussian, and themovies whose embedding has top-20 inner product with θ ′have score 1 and all others have score 0. θ ′ is fixed for the
first 25 steps. The rewards of the entire time horizon thus
do not follow a single linear model.

References
Y. Abbasi-Yadkori, D. Pál, and C. Szepesvári. Improved
algorithms for linear stochastic bandits. In NIPS, volume 11, pages 2312–2320, 2011.
A. Agarwal, H. Luo, B. Neyshabur, and R. E. Schapire.
Corralling a band of bandit algorithms. In Conference on
Learning Theory, pages 12–38. PMLR, 2017.

We test C2 UCB and MC2 UCB on both environments (i.e.,
8Contextual Set Selection Under Human Feedback With Model Misspecification

M. Agarwal and V. Aggarwal. Regret bounds for stochastic combinatorial multi-armed bandits with linear spacecomplexity. arXiv preprint arXiv:1811.11925, 2018.

F. M. Harper and J. A. Konstan. The movielens datasets:
History and context. Acm transactions on interactive
intelligent systems (tiis), 5(4):1–19, 2015.

R. Arora, T. V. Marinov, and M. Mohri. Corralling stochastic bandit algorithms. In International Conference on
Artificial Intelligence and Statistics, pages 2116–2124.
PMLR, 2021.

B. Kveton, Z. Wen, A. Ashkan, and C. Szepesvari. Tight
regret bounds for stochastic combinatorial semi-bandits.
In Artificial Intelligence and Statistics, pages 535–543.
PMLR, 2015.

P. Auer. Using confidence bounds for exploitationexploration trade-offs. Journal of Machine Learning
Research, 3(Nov):397–422, 2002.

T. Lattimore, C. Szepesvari, and G. Weisz. Learning withgood feature representations in bandits and in rl with agenerative model. In International Conference on Machine Learning, pages 5662–5670. PMLR, 2020.

I. Bogunovic, A. Losalka, A. Krause, and J. Scarlett.
Stochastic linear bandits robust to adversarial attacks.
In International Conference on Artificial Intelligence andStatistics, pages 991–999. PMLR, 2021.

S. Li, A. Karatzoglou, and C. Gentile. Collaborative filtering bandits. In Proceedings of the 39th International
ACM SIGIR conference on Research and Development inInformation Retrieval, pages 539–548, 2016.

N. Cesa-Bianchi and G. Lugosi. Combinatorial bandits.
Journal of Computer and System Sciences, 78(5):1404–
1422, 2012.

T. Lin, B. Abrahao, R. Kleinberg, J. Lui, and W. Chen.
Combinatorial partial monitoring game with linear feedback and its applications. In International Conference on
Machine Learning, pages 901–909. PMLR, 2014.

W. Chen, Y. Wang, and Y. Yuan. Combinatorial multiarmed bandit: General framework and applications. In
International Conference on Machine Learning, pages
151–159. PMLR, 2013.

T. Lykouris, V. Mirrokni, and R. Paes Leme. Stochastic
bandits robust to adversarial corruptions. In Proceedingsof the 50th Annual ACM SIGACT Symposium on Theoryof Computing, pages 114–122, 2018.

W. Chu, L. Li, L. Reyzin, and R. Schapire. Contextual bandits with linear payoff functions. In Proceedings of the
Fourteenth International Conference on Artificial Intelligence and Statistics, pages 208–214. JMLR Workshop
and Conference Proceedings, 2011.

N. Merlis and S. Mannor. Batch-size independent regretbounds for the combinatorial multi-armed bandit problem.
In Conference on Learning Theory, pages 2465–2489.
PMLR, 2019.

R. Combes, M. S. Talebi, A. Proutiere, and M. Lelarge.
Combinatorial bandits revisited.
arXiv preprint
arXiv:1502.03475, 2015.

A. Pacchiano, M. Phan, Y. Abbasi-Yadkori, A. Rao, J. Zimmert, T. Lattimore, and C. Szepesvari. Model selection
in contextual stochastic bandit problems. arXiv preprint
arXiv:2003.01704, 2020.

A. Cutkosky, A. Das, and M. Purohit. Upper confidencebounds for combining stochastic bandits. arXiv preprint
arXiv:2012.13115, 2020.
A. Durand, C. Achilleos, D. Iacovides, K. Strati, G. D.
Mitsis, and J. Pineau. Contextual bandits for adapting
treatment in a mouse model of de novo carcinogenesis.
In Machine learning for healthcare conference, pages
67–82. PMLR, 2018.

L. Qin, S. Chen, and X. Zhu. Contextual combinatorial bandit and its application on diversified online recommendation. In Proceedings of the 2014 SIAM International Conference on Data Mining, pages 461–469. SIAM, 2014.
I. Rejwan and Y. Mansour. Top-k combinatorial bandits withfull-bandit feedback. In Algorithmic Learning Theory,
pages 752–776. PMLR, 2020.

D. J. Foster, C. Gentile, M. Mohri, and J. Zimmert. Adapting
to misspecification in contextual bandits. Advances in
Neural Information Processing Systems, 33, 2020.

Y. Seldin and A. Slivkins. One practical algorithm for bothstochastic and adversarial bandits. In International Conference on Machine Learning, pages 1287–1295. PMLR,
2014.

A. Ghosh, S. R. Chowdhury, and A. Gopalan. Misspecified
linear bandits. In Proceedings of the AAAI Conferenceon Artificial Intelligence, volume 31, 2017.
A. Gupta, T. Koren, and K. Talwar. Better algorithms forstochastic bandits with adversarial corruptions. In Conference on Learning Theory, pages 1562–1578. PMLR,
2019.

R. Sen, A. Rakhlin, L. Ying, R. Kidambi, D. Foster, D. Hill,and I. Dhillon. Top-k extreme contextual bandits witharm hierarchy. arXiv preprint arXiv:2102.07800, 2021.
9

Contextual Set Selection Under Human Feedback With Model Misspecification

K. Takemura, S. Ito, D. Hatano, H. Sumita, T. Fukunaga,
N. Kakimura, and K.-i. Kawarabayashi. A parameter-freealgorithm for misspecified linear contextual bandits. In
International Conference on Artificial Intelligence andStatistics, pages 3367–3375. PMLR, 2021.
S. S. Villar, J. Bowden, and J. Wason. Multi-armed bandit
models for the optimal design of clinical trials: benefits
and challenges. Statistical science: a review journal of
the Institute of Mathematical Statistics, 30(2):199, 2015.
S. Yang, T. Ren, I. S. Dhillon, and S. Sanghavi. Combinatorial bandits without total order for arms. arXiv preprint
arXiv:2103.02741, 2021.
Y. Yue and C. Guestrin. Linear submodular bandits and theirapplication to diversified retrieval. Neural Information
Processing Systems, 2011.

10

Contextual Set Selection Under Human Feedback With Model Misspecification

A. Proof of Section 4
A.1. Proof of Proposition 4.1
Proof. We begin by construct m unit l2 norm points in Rd , denote the stacking of those points as X0 ∈ Rm×d . We construct
X0 such thatr
8 log(m)⊤⊤a a = 1, ∀a ∈ rows(X0 ) and a b ≤, ∀a, b ∈ rows(X0 ).
d−1
The existence of such construction follows from Lemma 3.1 of (Lattimore et al., 2020). Replicate X0 for k times, denote theresulting matrix to be X ∈ Rkm×d . We next prove the lower bound with the bandits problem instance with arms’ features
being X.
Choose a∗ ∈ rows(X) and letsθ∗ = ϵd−1 ∗a .
8 log(m)Further, let the expected score of arms be
rt (a∗ ) = θ∗⊤ a∗ = ϵ

and rt (b) = θ∗⊤ b + ∆t (b) = 0 ∀b ̸= a∗ .

It is easy to verify that |∆t (a)| ≤ ϵ, ∀a ∈ rows(X), t ∈ [T ]. Let τ = min {t ≤ Tq: a∗ ∈ St }, i.e., the first time St containsa∗ . Notice that the optimal set S ∗ , composed by k copies of a∗ , has reward kϵthan a∗ gives 0 reward. We have thatsd−1
R(T ) = kϵE [τ ] .
8 log(m)d−18 log(m) . Also notice that all arms otherNotice that any there are m different features in X, and the algorithm sees the reward for at most k arms in each time
step. Since the arm a∗ is randomly chosen from X and the feedback of all other arms are 0 (which therefore provides nom). Therefore the regret lower bound isinformation about a∗ ), we have that E[τ ] ≥ min(T, 2k
s
 m
d−1
min T,.
R(T ) = kϵ8 log(m)2k■This completes the proof.
A.2. Proof of Proposition 4.3
The following proof is inspired by “Failure of unmodified algorithm” in Appendix E of (Lattimore et al., 2020).
Proof. Consider the simple case with feature dimension d = 2. Let the arms’ features {xt (1), · · · , xt (m)} be that
• For t ≤ T /2 and t is odd, xt (i) = [ϵ, 0], ∀i ∈ [m].
• For t ≤ T /2 and t is even, xt (i) = [0, ϵ], ∀i ∈ [m].
• For t > T /2, xt (i) = [1, 0], ∀i ≤ m/2 and xt (i) = [ϵ, ϵ]∀i > m/2.
Further, we assume m > 2k and no noise. Let θ∗ = [ 21 , − 12 ]. For the misspecification, let∆t ([ϵ, 0]) = −ϵ,∆t ([0, ϵ]) = ϵ,∆t ([1, 0]) = 0,

Notice that for t = T /2, the algorithm has 0 regret and"#2
λ + kT4ϵ0
VT /2 =,
20
λ + kT4ϵ11∆t ([ϵ, ϵ]) = 0.

"
bT /2 =

2

− kT4ϵkT ϵ24#

Contextual Set Selection Under Human Feedback With Model Misspecification

h

i
kT ϵ2
kT ϵ2
therefore θbT /2 = − 4λ+kT,
22
ϵ
4λ+kT ϵ . For t = T /2 + 1, we haveθbt⊤ [1, 0] + βt ∥[1, 0]∥V−1 = −
t

kT ϵ2
+O
4λ + kT ϵ2rd log T
kT ϵ2

!

and
r
θbt⊤ [ϵ, ϵ] + βt ∥[ϵ, ϵ]∥V−1 = 0 + Otd log TkT!

Therefore for kT ϵ2 large enough (i.e., larger than some problem independent constant C0 ), the algorithm will choose karms with feature [ϵ, ϵ] to construct the set.
We next show that the algorithm will play the set composed by k arms with feature [ϵ, ϵ] until T . Suppose the algorithm has
played such set up to time t0 > T /2, then
"
"
#
#
2
2
− kT4ϵλ + kT4ϵ + k(t0 − T /2)ϵ2k(t0 − T /2)ϵ2
V t0 =, bt0 = kT ϵ22
k(t0 − T /2)ϵ2
λ + kT4ϵ + k(t0 − T /2)ϵ2
4
h
i
kT ϵ2
kT ϵ2
and again we have θbt0 = − 4λ+kT
ϵ2 , 4λ+kT ϵ2 and for t = t0 + 1
!
r
2
d
log
T
kT
ϵ
⊤
+O
θbt [1, 0] + βt ∥[1, 0]∥V−1 = −t
4λ + kT ϵ2
4kt0 ϵ2 − kT ϵ2
andθbt⊤ [ϵ, ϵ] + βt ∥[ϵ, ϵ]∥V−1 > 0t

Therefore the algorithm will continue play the set composed by k copies of [ϵ, ϵ].
Notice that given the problem instance construction, we have xt (i) = [1, 0] has 1/2 reward and xt (i) = [ϵ, ϵ] has 0 reward.
Therefore for t > T /2, the algorithm induces kT /2 regret. This compeltes the proof.
■

B. Proof of Section 5
We first present the complete version of Theorem B.1 which provides an explicit regret bound.
Theorem B.1 (Regret upper bound of Algorithm2). Assume that ∥θ∗ ∥2 ≤ 1, ∥xt (i)∥2 ≤ 1 and rt (i) ∈ [0, 1] for all t ≥ 0qand i ∈ [m]. Given 0 < δ < 1, set βt =regret can be bounded as

d log( 1+kt/λ) + λ1/2 with λ ≥ k. Then, with probability at least 1 − δ, the total
δ

s

!s



1 + kt/λTk
1/2
R(T ) ≤2Cd log
+λkT d log 1 +
δ
λd
s


Tk
+ 2ϵkCT d log 1 ++ 2ϵkCT.
λd

Ignoring the constants and logarithm terms, the regret bound can be simplified as
√
√ √
√ 
e ( d + λ) kT d + kϵ dT .
R(T ) = Or
Lemma B.2. If we set βt =

d log



1+kt/λδ+ λ1/2 , with probability at least 1 − δ, for all S and i ∈ S, we have0 ≤ rbt (i) − rt∗ (i, S) ≤ 2βt ∥xt (i)∥V−1 + 2ϵ

t−1 X
X

t−1

s=1 j∈Ss

12−1
xt (i)Vt−1
xs (j) + 2ϵ.

Contextual Set Selection Under Human Feedback With Model Misspecification

Proof. Notice that−1
θbt =Vt−1

t−1 X
X

!
xs (i) · res (i, Ss )s=1 i∈Ss
−1
=Vt−1

t−1 X
X

!
θ∗⊤ xs (i) + ηs (i) + ∆s (i, Ss )xs (i) ·

s=1 i∈Ss−1=θbt+ + Vt−1

t−1 X
X

xs (i) · ∆s (i, Ss ),s=1 i∈Ss

P

t−1 P
−1
⊤
where we define θbt+ := Vt−1
. Therefore, we have
x
(i)
·
θ
x
(i)
+
η
(i)
s
s
s
∗
s=1
i∈Ss
q

⊤
−1
xt (i)
rbt (i) − rt∗ (i, S) = θbt+ − θ∗ xt (i) + βt xt (i)Vt−1|{z}term (a)−1+ xt (i)⊤ Vt−1

t−1 X
X

xs (j) · ∆s (j, Ss ) + ϵ

s=1 j∈Ss

t−1 X
X

−1
xt (i)Vt−1
xs (j)

s=1 j∈Ss|{z}term (b)+ ϵ − ∆t (i, S) .
{z}|
term (c)To see the range of term (a), applying Theorem 2 of (Abbasi-Yadkori et al., 2011) (we provided it in Lemma B.3) and we
have
q


⊤

−1
xt (i) ≤ ∥θbt+ − θ∗ ∥Vt−1 + βt ∥xt (i)∥V−1
θbt+ − θ∗ xt (i) + βt xt (i)Vt−1
t−1≤2βt ∥xt (i)∥V−1 .
t−1

Similarly we can show the term (a) is bounded below by 0.
For term (b), notice that−1xt (i)⊤ Vt−1

t−1 X
X

xs (j) · ∆s (j, Ss ) ≤ ϵ

t−1 X
X

−1
xt (i)Vt−1
xs (j) ,s=1 j∈Ss

s=1 j∈Ss

where the inequality follows as all ∆s (j, Ss )s are bounded by ϵ. Therefore the second term is bounded below by 0 and
Pt−1 P−1
upper bounded by 2ϵ s=1 j∈Ss xt (i)Vt−1
xs (j) .
Lastly, one can easily verify that the last term ranges from 0 to 2ϵ.

■Lemma B.3. For ∥θ∗ ∥2 ≤ 1 and ∥xt (i)∥2 ≤ 1, ∀t ∈ [T ] and i ∈ [m], define Vt = λI +
P

t−1 P
θb+ := V−1
xs (i) · θ ⊤ xs (i) + ηs (i) , we have
t

t−1

s=1

i∈Ss

Pt

s=1

⊤
i∈Ss xt (i)xt (i) . DefineP∗s∥θbt+ − θ∗ ∥Vt−1 ≤


d log

1 + kt/λδ+ λ1/2 .

Proof. This follows directly from Theorem 2 of (Abbasi-Yadkori et al., 2011).
Pt P
Lemma B.4 (Lemma 4.2 of (Qin et al., 2014)). Let Vt = λI + s=1 i∈Ss xs (i)xs (i)⊤ . For λ ≥ k, we havet X
X
s=1 i∈Sstk∥xs (i)∥2V−1 ≤ 2d log 1 +
.
t−1
λd
13

■

Contextual Set Selection Under Human Feedback With Model Misspecification

Now we present the proof of Theorem B.1.
Proof. We first bound the regret at round t as follows,
Regt = f (rt∗ , S ∗ ) − f (rt∗ , St ) ≤ f (brt , St ) − f (rt∗ , St ) ≤ CsX(brt (i) − rt∗ (i))

2

i∈St

≤C

X

(b
rt (i) − rt∗ (i)) .

i∈St

Therefore with probability at least 1 − δ,R(T ) ≤CT X
X(brt (i) − rt∗ (i))

t=1 i∈St

≤C

T X
X

2βt ∥xt (i)∥V−1 + 2ϵC

T XX
t−1 X
X

t−1

t=1 i∈St−1
xt (i)Vt−1
xs (j) + 2ϵkCT

t=1 i∈St s=1 j∈Ss

v
u
T X
u X
4βt2 ∥xt (i)∥2V−1≤C tkT

t−1

t=1 i∈St

v
u T
t−1 X
uX X X2−1+ 2ϵkCT t
xt (i)Vt−1
xs (j) + 2ϵkCT
t=1 i∈St s=1 j∈Ss

v
v
u
u T
T X
u X
uX X
2
t
∥xt (i)∥2V−1 + 2ϵkCT.
∥xt (i)∥V−1 + 2ϵkCT t≤2CβT kT
t−1

t=1 i∈St

r
With βT =

d log



1+kT /λδ

t=1 i∈St

t−1+ λ1/2 and Lemma B.4, we have

!s



1 + kT /λ
Tk
1/2
+λ
d log
kT d log 1 +R(T ) ≤2C
δ
λd
s


Tk
+ 2ϵkCT d log 1 ++ 2ϵkCT.
λd
 √
√ √
√ 
e C( d + λ) kT d + kϵ dT
Ignoring the log terms, we have R(T ) = Os■C. Deferred Results of Section 6
C.1. Formal Version of Corollary 6.3
P
(i)
(i)
Corollary C.1. Consider the setting where f (r, S) = i∈S ri and rt (i) = g ∗ (ct , xt (i), i) + ∆t s.t. ∆t < ϵ (unknown
to the learner). Suppose g ∗ lies in a known finite function class G. Then Algorithm 2 applied with Algorithm 1 in (Sen et al.,2021) as a base algorithm has a regret guarantee of,
s
!




√
log T
|G|T
2
R(T ) ≤ C 1 ++ log Tk (m − k + 1)T log+ ϵkT m − k + 12
δp+ (1 + 4 log T ) 8T log(T 3 L/δ).
C.2. Proof of Theorem 6.1
We first present the complete version of Theorem 6.1 which proivdes an explicit regret bound.
14

Contextual Set Selection Under Human Feedback With Model Misspecification

Theorem C.2 (Regret upper bound of Algorithm 2). Assume that ∥θ∗ ∥ ≤ B, ∥xt (i)∥2 ≤ 1 and rt (i) ∈ [0, 1] for all t ≥ 0
and i ∈ [m]. Then with probability at least 1 − 4δ, the regret can be bounded as


p
log T
2
R(T ) ≤ 1 ++ log T RegAl∗ (T ) + (1 + 5 log T ) 8T log(T 3 L/δ),2
where RegAl∗ (T ) is the regret bound from Algorithm 1 for base algorithm Al∗ , with l∗ = argminl ϵl ≥ ϵ. Ignoring theconstants and log terms, we have
√
√ √
√ 
e ( d + λ) kT d + kϵ dT .
R(T ) = Oeτl as the observed stochastic reward when the meta algorithm chooses base algorithm
Notation in the proof. We denote R
Al for the τ -th time, and denote its expectation to be Rτl . For that time step, we denote Rτl,∗ to be the expectation of the
optimal reward. Further, we denote T (l, t) to be the number of times we pick base algorithm Al up to time step t.
Let ϵ be the true misspecification bound, and define l∗ = argminl ϵl ≥ ϵ. Before proving Theorem 6.1, we first present a
few lemmas.
Lemma C.3 (Adapted from Lemma 8 of (Cutkosky et al., 2020)). With probability at least 1 − δ, for all l and t, we have
T (l,t)Xeτl ≤Rτl − Rp
8T (l, t) log (T 3 L/δ).

τ =1eτl . This follows directly from a martingale-type concentration.
Proof. Notice that Rτl is the expectation of R■

Lemma C.4 (Adapted from Lemma 9 of (Cutkosky et al., 2020)). With probability at least 1 − δ, for all l, for all t, we have
T (l,t)Xpµblτ − Rτl,∗ ≤ 3 8T (l, t) log(T 3 L/δ).

τ =1

Proof. By a martingale-type concentration, for all l and t, we have
T (l,t) X  peτl − Ec RτlR≤ 8T (l, t) log(T 3 L/δ).
ττ =1

Define R∗ = Ect [Rt∗ ], where the expectation is taken over the context ct ∼ DC . For any context ct , we have Rtl ≤ Rt∗ . Thus
we have Ect [Rtl ] ≤ Ect [Rt∗ ], andT (l,t) X peτl − R∗ ≤ 8T (l, t) log(T 3 L/δ).
Rτ =1

Therefore for any l and t, we havesµblt − R∗ ≤T (l,t)Xp
8 log(T 3 L/δ)=⇒µblτ − R∗ ≤ 2 8T (l, t) log(T 3 L/δ).
T (l, t)τ =1

(6)

Further notice that Rτl,∗ is a random variable in [0, 1], with expectation being R∗ and randomness induced by the context ct ,we have thats
T (l,t)Xlog( 1δ )T (l, t) p
R∗ − Rτl,∗ ≤≤ 8 log(T 3 L/δ)T (l, t).
(7)
2
τ =1
The first inequality follows from Hoeffding’s inequality. Combining Equations (6) and (7) completes the proof.
15■

Contextual Set Selection Under Human Feedback With Model Misspecification

Recall that R∗ = Ect [Rt∗ ], i.e., taking expectation over the context ct ∼ DC . We have the following lemma.
Lemma C.5 (Simplified Lemma 10 of (Cutkosky et al., 2020)). With probability at least 1 − 4δ, for l∗ = argminl ϵl ≥ ϵand for all t, we have the following hold simultaneously
T (l∗ ,t)X∗∗

Rτl ,∗ − Rτl ≤ RegAl∗ (T (l∗ , t)),

τ =1

RegAl∗ (T (l∗ , t − 1))R∗ − µblT (l∗ ,t−1) ≤ min 1,+2
T (l∗ , t − 1)s∗

8 log(T 3 L/δ)T (l∗ , t − 1)!
,T (l∗ ,t−1)

X∗el∗ ≤ RegA∗ (T (l∗ , t − 1)) + 4µ
blτ −1 − Rτlp

8T (l∗ , t − 1) log (T 3 L/δ).

τ =1

Proof. With Theorem B.1, with probability 1 − δ, we have that for all t, we have
T (l∗ ,t)∗X∗

Rτl ,∗ − Rτl ≤ RegAl∗ (T (l∗ , t)).

t=1With Lemma C.3, with probability 1 − δ, for all t, we have
T (l∗ ,t)∗e l∗ ≤
Rτl − RτX

p

8T (l∗ , t) log(T 3 L/δ).

τ =1

With Lemma C.4, with probability 1 − δ, for all t, we have
T (l∗ ,t)

X

∗

∗

µ
blτ − Rτl ,∗ ≤ 3p
8T (l∗ , t) log(T 3 L/δ).

τ =1

With Hoeffding’s inequality, for all l ∈ [L] and all t, with probability at least 1 − δ, we have
T (l,t−1)

X

R∗ − Rτl,∗ ≤p
8T (l, t) log(T 3 L/δ)

τ =1

The rest of proof conditions on the above 4 equations to hold, which has probability at least 1 − 4δ. Note that the first claimin the lemma immediately follows from the first equation above.
For the second equation, the 1 of the minimum holds by assumption that R∗ ≤ 1. For T (l∗ , t − 1) ̸= 0, we have∗R∗ − µblT (l∗ ,t−1) =R∗ −1∗
T (l , t − 1)T (l∗ ,t−1)∗≤∗
Rτl ,∗ +X
τ =1

RegAl∗ (T (l , t − 1))+2
T (l∗ , t − 1)s1∗
T (l , t − 1)T (l∗ ,t−1) 

X

∗

∗

eτl
Rτl ,∗ − R



τ =1

8 log(T 3 L/δ).
T (l∗ , t − 1)

For the third equation, we have
T (l∗ ,t−1)Xτ =1

T (l∗ ,t−1)∗
e l∗ =µblτ −1 − R
τ

X

∗
∗
∗
∗
∗
e l∗
µ
blτ −1 − Rτl ,∗ + Rτl ,∗ − Rτl + Rτl − Rττ =1≤RegAl∗ (T (l∗ , t − 1)) + 4p

8T (l∗ , t − 1) log(T 3 L/δ).
■16

Contextual Set Selection Under Human Feedback With Model Misspecification

Lemma C.6 (Adapted from Lemma 11 of (Cutkosky et al., 2020)). With probability at least 1 − δ, all base algorithms Al
satisfy:
T (l,T )Xµ
blτ −1 − Rτl ≤ RegAl (T (l, T )) + 5p

8T (l, T ) log(T 3 L/δ) + 1.

τ =1

Proof. Let t be the smallest time such that T (l, t) = T (l, T ). Then we have lt = l, which implies that lt ∈ Lt . Therefore
T (l,t−1)Xeτl ≤ RegA (T (l, t − 1)) + 4µ
blτ −1 − Rlp
8T (l, t − 1) log(T 3 L/δ).

τ =1

Further, by Lemma C.3, we have that
T (l,t−1)X

e l − Rl ≤
R
τ
τ

p

8T (l, t − 1) log(T 3 L/δ).

τ =1

Combining with the fact that µ
blT (l,T )−1 − RTl (l,t) ≤ 1, we have
T (l,T )Xµ
blτ −1 − Rτl ≤ RegAl (T (l, T )) + 5p

8T (l, T ) log(T 3 L/δ) + 1.

τ =1

■

This completes the proof.
Now we are ready to prove Theorem 6.1.

Proof. The proof again condition on the 4 events listed at the beginning of the proof for Lemma C.5, which happens with atleast 1 − 4δ probability. We first decompose the regret asTXRt∗ − Rt =

t=1

T
X

(Rt∗ − R∗ ) +lt ̸=l∗

X

∗

∗

X

(RTl (l,∗∗ ,t) − RTl (l∗ ,t) ) +lt =l∗(R∗ − RTlt (lt ,t) ).

lt ̸=l∗For the first term, we have
T
X

(Rt∗ − R∗ ) ≤p

8T log(T 3 L).

lt ̸=l∗For the summation for lt = l∗ , with Lemma C.5, we have
T (l∗ ,T )

X

∗

∗

Rτl ,∗ − Rτl ≤ RegAl∗ (T (l∗ , T )).

τ =1
∗

∗

For lt ̸= l , we must have U (lt , t) ≥ U (l , t) since l∗ ∈ Lt for all t. Then we haveR∗ =R∗ − U (l∗ , t) + U (l∗ , t) − U (lt , t) + U (lt , t)
RegAl∗ (T (l∗ , t − 1))≤ min 1,
+ κϵl∗ + U (lt , t).
T (l∗ , t − 1)This follows from the second equation in Lemma C.5 and the construction of U (l∗ , t). Thus, we have


X
X
X
RegAl∗ (T (l∗ , t − 1))lt∗R∗ − RT (lt ,t) ≤min 1,+κϵT (l, T )lT (l∗ , t − 1)lt ̸=l∗lt ̸=l∗
l̸=l∗

X
+
U (lt , t) − RTlt (lt ,t)lt ̸=l∗≤RegAl∗ (T ) log2 T + κϵl∗ T +X
lt ̸=l∗17


U (lt , t) − RTlt (lt ,t) .

Contextual Set Selection Under Human Feedback With Model Misspecification

For the termlt
lt ̸=l∗ U (lt , t) − RT (lt ,t) , first notice thatP

T (l,T )X

U (l, t) − µ
blT (l,t−1) =rX

min 1, 2τ =1

t|lt =l8 log(T 3 L/δ)
τ −1

!
− κϵl

p
≤4 8T (l, T ) log(T 3 L/δ) − κϵl T (l, T ).
Therefore, we have
X
X
blTt (lt,t−1 ) − RTlt (lt ,t)U (lt , t) − µ
blTt (lt ,t−1) + µ
U (lt , t) − RTlt (lt ,t) =lt ̸=l∗lt ̸=l∗




=

X

X


l̸=l∗

blT (l,t−1) − RTit(it ,t) U (l, t) − µ
blT (l,t−1) + µt|lt =l≤XT (l,T )Xp
4 8T (l, T ) log(T 3 L/δ) − κϵl T (l, T ) +µblτ −1 − Rτl 

l̸=l∗

τ =1

i
Xh p
≤
9 8T (l, T ) log(T 3 L/δ) + RegAl (T (l, T )) − κϵl T (l, T ) + 1 .
l̸=l∗

The last step uses Lemma C.6. Notice that
RegAl (T (l, T )) − κϵl T (l, T ) = Reg0 (T (l, T )),∀l ∈ [L].

Notice that l ∈ [ log2 T ]. Putting everything together, we havepR(T ) ≤ 8T log(T 3 L/δ) + RegAl∗ (T (l∗ , T )) + RegAl∗ (T ) log2 T + κϵl∗ T
p
log T
log T
+
Reg0 (T ) + 5 log(T ) 8T log(T 3 L/δ) +
2

 2
p
log T
2
+ log T RegAl∗ (T ) + (1 + 5 log T ) 8T log(T 3 L/δ).
≤ 1+
2
■

This completes the proof.

18