On the Interplay Between Misspecification and Sub-optimality Gap: From Linear Contextual Bandits to Linear MDPs
Authors: Weitong Zhang
Jiafan He
Zhiyuan Fan
Quanquan Gu
Venue: Submitted to ICLR 2023 (2023)

Abstract: We study linear contextual bandits in the misspecified setting, where the expected reward function can be approximated by a linear function class up to a bounded misspecification level $\zeta>0$. We propose an algorithm based on a novel data selection scheme, which only selects the contextual vectors with large uncertainty for online regression. We show that, when the misspecification level $\zeta$ is dominated by $\tilde O(\Delta / \sqrt{d})$ with $\Delta$ being the minimal sub-optimality gap and $d$ being the dimension of the contextual vectors, our algorithm enjoys the same gap-dependent regret bound $\tilde O ({d^2} /{\Delta})$ as in the well-specified setting up to logarithmic factors. Together with a lower bound adapted from Du et al. (2019); Lattimore et al.(2020), our result suggests an interplay between misspecification level and the sub-optimality gap: (1) the linear contextual bandit model is efficiently learnable when $\zeta \leq \tilde O({\Delta} / \sqrt{d})$; and (2) it is not efficiently learnable when $\zeta \geq \tilde \Omega({\Delta} / {\sqrt{d}})$. We also extend our algorithm to reinforcement learning with linear Markov decision processes (linear MDPs), and obtain a parallel result of gap-dependent regret. Experiments on both synthetic and real-world datasets corroborate our theoretical results.

Under review as a conference paper at ICLR 2023
ON THE INTERPLAY BETWEEN MISSPECIFICATION AND SUB-OPTIMALITY GAP: FROM LINEAR CONTEX- TUAL BANDITS TO LINEAR MDPs
Anonymous authors
Paper under double-bling blind review
ABSTRACT
We study linear contextual bandits in the misspecified setting, where the expected reward function can be approximated by linear function class up to a bounded misspecification level C > O. We propose an algorithm based on a novel data selection scheme, which only selects the contextual vectors with large uncertainty for online regression. We show that, when the misspecification level Ç is domi- nated by Ö(A/ Vd) with A being the minimal sub-optimality gap and d being the dimension of the contextual vectors, our algorithm enjoys the same gap-dependent regret bound (dd//) as in the well-specified setting up to logarithmic factors. Together with lower bound adapted from Du et al. (2019); Lattimore et al. (2020), our result suggests an interplay between misspecification level and the sub-optimality gap: (1) the linear contextual bandit model is efficiently learnable when Ç O(D/Vd); and (2) is not efficiently learnable when C Z (AAVvd) We also extend our algorithm to reinforcement learning with linear Markov deci- sion processes (linear MDPs), and obtain a parallel result of sap-dependent regret. Experiments on both synthetic and real-world datasets corroborate our theoretical results.
INTRODUCTION
Linear contextual bandits (Li et al. 2010 Chu et al. 2011 Abbasi- Yadkori et al., 2011: Agrawal & linear function of the contextual vectors. However, such a well-specified linear model assumption some- times does not hold in practice. This motivates the study of misspecified linear models. In particular, we only assume that the reward function can be approximated by linear function up to some worst- case error called misspecification level. Existing algorithms for misspecified linear contextual bandits (Lattimore et al. 2020; Foster et al. 2020) can only achieve an O(d K + <KVd log K) regret bound, where K is the total number of rounds and d is the dimension of the contextual vector. Such a regret, however, suggests that the performance these algorithms will degenerate to be linear in K when K is sufficiently large. The reason for this performance degeneration is because existing algorithms, such as OFUL YAbhasi-Yadkori et al. 2011) and linear Thompson sampling (Agrawal & Goyal 2013), utilize all the collected data without selection. This makes these algorithms vulner- able to " "outliers" caused by the misspecified model. Meanwhile, the aforementioned results do not consider the sub-optimality gap in the expected reward between the best arm and the second best arm. Intuitively speaking, if the sub-optimality gap is smaller than the misspecification level, there is no hope to obtain sublinear regret. Therefore. it sensible to take into account the sub-optimality gap in the misspecified setting, and pursue gap-dependent regret bound.
Goyal 2013) have been extensively studied when the reward function can be represented
The same misspecification issue also appears in reinforcement learning with linear function approx- imation, when a linear function cannot exactly represent the transition kernel or value function of the underlying MDP. In this case, Du et al. (2019) provided a negative result showing that the misspecification level is larger than certain threshold, any RL algorithm will suffer from ex- ponentially large sample complexity. This result was later revisited in the stochastic linear bandit setting by Lattimore al. (2020), which shows that large misspecification error will make the bandit model not efficiently learnable. However, these results cannot well explain the tremendous success of deep reinforcement learning various tasks (Mnih et al. 2013: Schulman et al. 2015

---

Under review as a conference paper at ICLR 2023
2017). where the deep neural networks are used function approximators with misspecification error.
In this paper, aim understand the role of model misspecification in linear contextual ban- dits through the lens of sub-optimality gap. By proposing a new algorithm with data selection, we achieve constant regret bound for such problem. We also extend our algorithm to the lin- ear Markov decision processes (Jin et al. 2020) and obtain a regret bound of similar flavor. Our contributions are highlighted follows:
We propose new algorithm called DS-OFUL (Data Selection OFUL). DS-OFUL only leams from the data with large uncertainty. We prove the misspecification level is small (i.e., < O / vd) and the minimal sub-optimality gap A is known. Our regret bound improves upon the gap-dependent regret in the well-specified setting (Abbasi- Yadkori et al.) 2011) by a logarithmic factor. To the best of our knowledge, this is the first constant gap-dependant regret bound for misspecified linear contextual bandits, assuming a known minimal sub-optimality gap.
gap-dependent regre bound when
We also prove a gap-dependent lower bound following the lower bound proof technique in Du et al. 2019); Lattimore et al.] (2020). This together with the upper bound suggests interplay between the misspecification level and the sub-optimality gap: the linear contextual bandit is efficiently learnable if Ç < O
while it is not efficiently learnable if Ç ((A/vd).
We extend the same idea to the misspecified linear MDP, and propose an algorithm called DS- LSVI (Data-Selection LSVT). DS-LSVI enjoys a gap-dependent regret bound, which suggests a similar interplay between the misspecification level and sub-optimality gap in episodic MDPs to achieve logarithmic regret bound O(H A log(K))
Finally, conduct experiments the linear contextual bandit with both synthetic and real datasets, and demonstrate the superior performance of DS-OFUL algorithm. This corroborates our theoretical results.
Notation.
Scalars and constants are denoted by lower and upper case letters, respectively. Vectors are denoted by lower case bold face letters x, and matrices by upper case bold face letters A. We de- note by [k] the set 21, J.} for positive integers k. For two non-negative sequence {an), (b.), an = (bb,) means that there exists positive constant C such that On S Cbn, and we use O(-) to hide the log factor in O(-) other than number of rounds T or episode K; an = 12(b,)) means that there exists positive constant C' such that an 2 Cbn, and we use 5i(-) hide the log factor. For vector x E IR and positive semi-definite matrix A E pdxd, we define ||x||ă = x Ax. For any set C, we use |C] to denote its cardinality.
2 RELATED WORK
In this section, we review the related work for misspecified linear bandits and misspecified rein- forcement learning. We defer more related work on the function approximation bandits and RL to Appendix A
(211)) is probably the first work considering the mis- specified linear bandits, which shows that the OFUL (Abbasi- Yadkori et al. 2011) algorithm cannot achieve a sublinear regret in the presence of misspecification. They, therefore, proposed a new al- gorithm with hypothesis testing module for linearity to determine whether to use OFUL (Abbasi-) Yadkori et al., 2011) or the multi-armed UCB algorithm. Their algorithm enjoys the same perfor- mance guarantee OFUL in the well-specified setting and avoid the linear regret under certain misspecification setting. Lattimore et al. (2020) proposed a phase-climination algorithm for mis- specified stochastic linear bandits. which achieves Ō(vdK + CK <Kvd vd) regret bound. For contextual linear bandits, both Lattimore et al. (2020) and Foster et al. (020) proved Ö(dVK + dd) regret bound. TTakemura et al. (202T); Vial et al. 2002)) also provide a similar regret bound without the knowledge of the misspecification level. Van Roy & Dong (219 proved lower bound of sam- ple complexity, which suggests when <vd 2 / log [D]. any best arm identification algorithm will
Misspecified Linear Bandits. Ghosh et al.
we use notation((.) hide the log factor other than numher of rounds T
2

---

Under review as a conference paper at ICLR 2023
suffer (2(24) sample complexity, where D is the decision set. When the outcome is deterministic and does not contain noise, they provided an algorithm using (d) sample complexity to identify A-optimal arm when < S A/vd. Lattimore et al. (2020) also mentioned that if <vā S A, there exists a best arm identification algorithm can only use (d)) arms to find a A-optimal arm with the knowledge of Ç. Note that although the exponential sample complexity lower bound for best eeppeeoee
arm identification can be translated into regret lower bound in linear contextual bandits, the al- gorithms for best-arm identification and the corresponding upper bounds cannot be easily extended to linear contextual bandits. Besides these works on misspecification, He et al. (2022) studies the linear contextual bandits with adversarial corruptions, which can be considered as similar setting of misspecification. They assume the summation of the approximation error over all K rounds is
bounded by the corruption level C. They proposed algorithm achieving (dv/K K dC) regret bound. However, their result in adversarial corrupted bandits cannot be directly translated to the misspecification setting since letting C = KC will lead to a Odd K + c) linear regret. Besides these series of work, Camilleri al. 2021 also studies the robustness of kernel bandit algorithms on the misspecification.
Misspecification in Reinforcement Learning Du al. (2019) showed that having good rep- resentation is insufficient for efficient reinforcement learning unless the approximation error (i.e.. misspecification level) by the representation is small enough. In particular, [Du et al. (2099) sug- gested that a 52( v H/dd misspecification will lead to 12(2#) sample complexity for RL. to find the optimal policy, even with a generative model. On the other hand, series of work (Jin et al. 2020) Zanette et al. 2020b Foster & Rakhlin 2020) provided Ö + (T)) regret bound for RL in various settings, ignoring the dependence on the dimension of the feature representation d and the planing horizon H. This suggests that the performance of RI will degenerate the total number of interactions with the environment I' increases. Also, these results do not consider the minimal sub-optimality gap of the action-value function. Du al. (2020) considered the agnostic Q-learning with misspecified linear function approximation. They proposed an algorithm with the access to a generative model and showed that if Ç S O(A/ /V), one can find the optimal policy using (d)) tra- jectories. Together with the lower bound provided in Du al. 2019), it suggests that O(A/vd) is a sufficient and necessary condition to achieve a polynominal sample complexity given the access to the generative model.
PRELIMINARIES OF LINEAR CONTEXTUAL BANDITS
We consider linear contextual bandit problem. In round i E [K]. the agent receives a decision set Dr C Idd and selects an arm X; E DD then observes the reward т& = r(xx) + Eks where r()) : d + [0, 1] is deterministic expected reward function and EY is zero-mean R-sub-Gaussian random noise. i.e., E[edex X1:k, 11 & cxp(X² R² /2), Ak E [K], x E IR.
D₁ satisfies ||x|| < L and the reward + -0, can be approximated by a linear function r(x) = x 0" + 7(x), where v7.)) : Rdd [-C.<] is the unknown misspecification error function. We further assume ||0"||2 < B and for simplicity, we assume B, L, 2 1. We denote the optimal reward at round k as r maxxeD, r(x) and the optimal arm x argmaxxeds r(x). Our goal is to minimize the
In this work, we assume that all contextual vector
function r(.) Rd
regret defined by Begret(K)= := E r(x)).
In this paper, we focus on the minimal sub-optimality gap condition.
Definition 3.1 (Minimal sub-optimality gap). For each x Dr. the sub-optimality gap Ax(x) is defined by (x(x) := ri r(x) and the minimal sub-optimality gap A is defined by A = minke[K]]xEDD, (xx (x > 0).
Then we further assume this minimal sub-optimality gap is strictly positive, i.e., A > 0.
4 PROPOSED ALGORITHM
In this section, we propose our algorithm, DS-OFUL, in Algorithm| [ The algorithm runs for K rounds. In each round, the algorithm first estimates the underlying parameter 0* by solving the
3

---

Under review as a conference paper at ICLR 2023
following ridge regression problem in Line
0x orgming (ra (x-0,00 + 1100
where Ck-1 is the index set of the selected contextual vectors for regression and is initialized as an empty set at the beginning. After receiving the contextual vectors set Dr. the algorithm selects an arm from the optimistic estimation powered by the Upper Confidence Bound (UCB) bonus in Line 4 In line []] the algorithm adds the index of current round into C₁ if the UCB bonus of the chosen arm Xg. denoted by |,x is greater than the threshold I', Intuitively speaking, since the UCB bonus reflects the uncertainty of the model about the given arm x, Lidsaarsss the data that brings little uncertainty (I) (||xlo,,) +) to the model. Finally we denote the total number of selected data
Line by |Cxrl- We will declare the choices of the parameter r, B and in the next section.
Algorithm Data Selection OFUL OFUL)
Input: Threshold r, radius 3 and regularizor À
1: Initialize Co 0, Uo AI,
2: for k == 1..... K do
3: Set Uy- AI + Eiec.-, x 10=0=11 = r;x;-
4: Receive decision set DA, select Xxx =r {x 0% + 0| }, receive reward Th
5: if [[|xxIll,"* 2 r then C. Ca-1 U {k} else Cs Ck-1
6: end for
REGRET ANALYSIS
In this section, provide the regret upper bound of Algorithm | and the regret lower bound for learning the misspecified linear contextual bandit.
Theorem 5.1 (Upper Bound). For any 0 8 < 1. let = B and r = A/(2/d(1) where + 8R 1og( Set = + 4/di2 R where 12 = log(3LBI-'), ls log((1 + BT If the misspecification level is
(24 + 18R) log(((2 + 54R)LBB
bounded by 2 < A, then with probability at least 6, the cumulative regret of Algorithm
is bounded by
3233 2nd log(1 (1 16dT 212)
Regret(K) <
Remark 5.2. Since 8 Ö(vd). Theorem 5.1 suggests Ö constant regret bound in- dependent of the total number of rounds K when Ç < (A/Vd). This suggests an O(d2A constant regret bound if the misspecification level is reasonably small, which improves the loga- rithmic regret Odd A -1 loog () in Abbasi-Yadkort et al. (2011) to constant regref" Note that our constant regret bound relies on the knowledge of the minimal sub-optimality gap A, while the OFUL algorithm in Abbasi- Yadkori et al. (2011) does not need prior knowledge about the minimal sub-optimality gap A.
Remark 5.3. Our high probability constant regret bound does not violate the lower bound proved in Hao et al. (2020), which says that certain diversity condition the contexts is necessary to achieve an expected constant regret bound (Papini et al. (202). In contrast, we only provide a high- probability constant regret bound. When extending this high probability constant regret bound to expected regret bound, we have
E[Regret(K)) & O(dPA-1og(11//0000
OK,
which depends on K. To obtain a sub-linear expected regret, we can set 6 = 1/K which yields logarithmic regret σ log(K) and does not violate the lower bound in Hao et al. (022)).
When we say constant regret, we ignore the log(1/8) factor in the regret choose 8 to be constant.
4

---

Under review as a conference paper at ICLR 2023
Furthermore, following the similar idea in Lattimore et al. (2020),
prove gap-dependent
lower bound for misspecified stochastic linear bandits. Note that stochastic linear bandit can be seen a special case of linear contextual bandits with fixed decision set Dj = D across all round E [K]. Similar result and proof can be found in Du et al. (2019) for episodic reinforcement learning.
Theorem 5.4 (Lower Bound), Given the dimension d and the number of arms [D], for any A < and Ç 2 3 log( [)) 1), there exists a set of stochastic linear bandit problems O with minimal sub-optimality gap A and misspecification error level Ç. such that for any algorithm that has sublinear expected regret bound for all 0 E θ i.e., E Reggret (K) & CK with C > 0 and S a 1, we have
(Reggre (K)] 2 KA. When K < O(DD), the expected regret is lower bounded by E [Regret
When K 2 (((D)), the expected regret is lower bounded by supece lE [eggett >
(og))))
Remark 5.5. Theorem 5.4 shows two regimes under the case < 2 (((A/Vd). In the first regime K S ((12)) where the decision set is large (e.g., [D] dd00), any algorithm will suffer from linear regret Ö(AK), which suggests that the regime cannot be efficiently learnable. the second regime K 2 O(ID)), Theorem 5.4 suggests a (2 log( K)) regret lower bound, which is matched by the multi-armed bandit algorithm with upper bound ( - ()) (Lattimore Szepesvári 2020). Therefore, in this easier regime, linear function approximation cannot provide any performance improvement and one can simply adopt the multi-armed bandit algorithm to learn the bandit model.
Remark 5.6. Theorems 5. and 5.4 provide a holistic picture about the role of misspecification in linear contextual bandits. Here we focus on the more difficult regime K S [D]. In the regime S (D), when < O(A/ vd). Theorem 5.1 suggests that the bandit problem is efficiently learnable, and our algorithm DS-OFUL can achieve constant regret, which improves upon the logarithmic regret bound in the well-specified setting (Abbasi- -Abbasi-Yadkori et al.) 2011). On the other hand, when
2 (A/ /d), Theorem 5.4 provides linear regret lower bound suggesting that the bandit model can not be efficiently learned.
PROOF SKETCH OF THEOREM 5.1
In this section, give overview of the main technical difficulty and our proof technique derive Theorem 5.1 The detailed proof is deferred to Appendix C
First, we aim at controlling the number of rounds in the index set Cx. Since we only select the data with ||xx l!u 2 I for ridge regression, we can lower bound the summation of the selected UCB
terms as Σtece / 2 Cx| On the other hand, noticing that U Eiec,,, X,xI we can upper bound the summation of UCB terms by using the elliptical potential lemma from Abbasi-- Yadkori et al. 2201 as Σxecx ||x S Ö(v ((vd)x))) Combining the upper bound and lower bound together we can bound the total number of the selected data |Cx| r|cx| - ((vd(Ckl), which suggests that |Cx| < (dT which irreverent with the total number rounds K.
Second, we control the fluctuations in the regression with misspecification error by |x (0 00) T(xx
| | Compare this result with the original result |x T (0x- 0*)l < ÖRRV++
<vdk) ||x||| in Jin et al. (022)), , our confidence radius Ö(Rv + <v Ck does not grow with the total number of rounds K. In lact, directly use the result in Jin et al. (2020) and follow the proof
outline in Abbbaai- Yadkori et al. (201T) will lead to the following regret bound:
Regret(K') < ō [RVd + <vdk) Ex=i|ilo S Ö (RdvK+ KK+(dk (cd).
which suggests a linear regret bound. As comparison, with the help of data selection rule in our work, the regression set Cx is finite and we can avoid the linear regret when using all data into regression. In addition, our result provides a vd tighter bound compared with Jin et al. (2020) by using the result provided in Zanette et al. 2020c)
5

---

Under review as a conference paper at ICLR 2023
Based on these two key observations, overcome the linear regret bound by partitioning the total round K into two different sets. The first set contains all non non-selected round, i.e. [X] Ck. In this
situation, the uncertainty satisfies |xxellu," I and we can prove that when Ç S O(A/va)) the instantaneous regret for the un-selected round is bounded
r r rxx) - 2Ç + 20(RVd + SvdCk <A,
which suggests that the non-selected data optimal and incur no regret.
For the data in the finite set CK, we follows the gap sap-dependent regret bound in Abbasi- Yadkori et al. 2011 to show that Ekeg r r(xx) I (dd A Log As result, by partition the set [K]
into two subsets [K] CK.. CK. we get the claimed cumulative regret bound by
(
(d (1l (Plog(Ck))) 0,
Regret( (K)
Σ Reg(k)
Σ Reg(k)
KKTx
where we denote Reg(k) the instantancous regret in round k (i.e. Th r(xx)).
7 MISSPECIFIED LINEAR MDPs
7.1 PRELIMINARIES OF LINEAR MDPS
We consider the episodic Markov Decision Process (MDP). Each episodic MDP is defined by tuple M(S, A. H. [r {Ph of each episode and Th S x A [0, 1] is the reward function at stage h. Ps. is the transition kernel where (s's'(s, |s a) denotes the transition probability from state to s' with action a at stage h. At the beginning of each episode, the agent determines policy
1 where S is the state space, A is the action space, H the length
1=
( h= where nTy S + A. Then = H. the agent repeatedly receives state 8n, takes the action as = TA (5x). )
from stage h receives the reward (sh, as.) and the next state 8h+1- For any policy the value function and the Q-function at stage h is defined by
(s)
Th (sw, (sw) = =
Q7 a) = rn(s a) + +E [V (S1+1)
an = =a]
It's obvious that for all policy æ. for all h [H] E S and E A, the value function and the Q-function is bounded by (s) H. 0 S (%(s,a) s H since (n a) E [o, 1]. We further define the optimal value function and the optimal Q-function as
(s) = max (s), (s, = max Q7 (s)
For simplicity, we denote (s, = Ry [V(')) and we have the Bellman equation along with the Bellman optimality equation as
as, ra (s) + [Px (s),
Qī) (s, + (ss
(7.1)
We consider the (-approximate linear MDP setting (Jin et al. 2020) in this work to study the impact of misspecification on function approximations in reinforcement learning.
Definition 7.1 (C-approximate linear MDP, Jin et al. 2020). For any Ç S. 1, we say that MDP M(S, AA H, {rx), (Pr)) is Ş-approximate linear MDP with feature map Φ S x A + Rd, if for any E [H], there exists d unknown (signed) measures μh unknown vector 0% Rdd such that for any (s, E A, [| a) - (0(s, a), (.)) TV S S,
(h , :... 2h over S and an
(ra(s,a) - (0(s, a), 0%) <
A and max μn (S) 10 S /d for w.l.o.g. we assume [ a)l2 $ for all (s, a) all h E [H].
Under Definition 7.] is easy to show that the Q-function under a certain policy N close to a linear function of the feature map Φ.

---

Under review as a conference paper at ICLR 2023
Lemma 7.2 (Lemma C.I. Lemma C.2. Jin al. 2020). For <-approximate linear MDP, for any policy т, there exists a corresponding (wi, to such that for any (s, a, h) E S x H]:
(s, (o(s,, a), wit 2HC, |w 2HHdd
We are concerning about minimizing the cumulative regret defined by Regret(K) Ex= (sftt) VT" (sf), where x² is the policy used in the k-th episode. Similar to linear contex- tual bandits, we introduce the minimal sub-optimality gap A originally defined in He et al. (202 la)
Definition 7.3 (Minimal sub-optimality gap. He et al. 2021a). la). For each (s, a, h)) E 8 x A x [M], the sub-optimality gap (s a) is defined as (s, a) = [ (s) 27 (s, a) and the minimal sub- optimality gap is defined A mink. ( (s) 0).
We further assume this minimal sub-optimality gap is strictly positive, i.e., A 0.
7.2 PROPOSED ALGORITIM
We propose our algorithm, DS-LSVI. for misspecified linear MDP Algorithm It applies the idea of DS-OFUL to the LSVI-UCB (Jin et al. 2020). For simplicity, we denote o ( a r Th (s ) for short when there is no confusion. The algorithm runs for K episodes. In the k- episode, the algorithm estimates the optimal Q-function using a linear function as indicated by
Lemma 7.2 In detail, at each stage h, after acquiring the estimated value function V (-) at state
+ in Line 4 the algorithm solves the following ridge regression problem
W argmin,, //l/ Eiec.,, ((0), w) -ri, (+++((+++))
where Cg-1 contains the indices of episodes selected for regression and r), + (s)+ is the esti- mated Q-function by Bellman optimality equation (7.1) Then the algorithm takes the greedy policy based on the estimated Q-function and receives the full episode. In Line T2 the algorithm adds the episode & into the regression index set C. if the data k-th episode provides more uncertainty (i.e. || 2 r' at any stage h E [H]. The intuition behind this selection is the same as Line 5 in Algorithm
[] when dealing with linear bandits: when one episode provide data sample with large uncertainty at stage, we add it to the regression. Otherwise, the episode will be ignored if the whole episode provide few uncertainty.
Algorithm Data Selection LSVI (DS-LSVI)
Input: Threshold I, radius 3
1: Initialize Cu 0, U% I, w
0 for all h E [M], ( = 1 0 for all (s, a)
2: for episodes = 1..... K do
3: for stage h H...., do
4: U = I+ Eiec.,, 01 ( w = (U -1 EiEce,, 0y (ri. + (
5:
Q)(:,) ( w/) (-)(()))))))
6: (-) = min (max, 1Q) (, a)) H). ++()) = argmax, (Q)(a))
7:
end for
8: Receive initial state a/
9: for stage h 1,
1...., ., do
10: Take action a.. T (s and receive reward r and next state s
end for
12: C₁ Ck-1 U (k) if 3h E [H] | (() 2 r else CR-1
13:
end for
7.3 REGRET ANALYSIS
We provide the regret upper bound of Algorithm for the Ç-approximate linear MDP. The proof is deferred to Appendix
Theorem 7.4 (Upper Bound), Let = e(Ad-1H-)), 8 = Ö(Hd), with probability at least
1- 6, if Ç = -(Ad-0.5-22) the cumulative regret of Algorithm 2 bounded by Regret(K)) <
o 3 Allgg (K)).
7

---

Under review as a conference paper at ICLR 2023
Remark 7.5. Theorem 7.4 suggests that if the misspecification level is upper bounded by 2(Ad-0.6H-225) we can achieve the same logarithmic regret bound 0(H 1) the well- specified setting (He et al. 2021a). This result indicates that reasonably small misspecificatioo will not deteriorate the performance. Our result improves the original regret bound O( + {dHHK K) for the misspecified linear MDP provided in Jin al. (022)).
Remark 7.6. Compared with the linear contextual bandit results, our result in the linear MDP set- ting also suggests the same relationship among Ç, and dimension d, ignoring the horizon factor H. Du et al. (219)) showed that when Ç 2 (AA/vd) any reinforcement learning algorithm suf- fers an O(2") sample complexity. In addition, Du et al. (0200) provided algorithm for agnostic Q-learning which takes (dd) trajectories find the optimal policy when << A/vd. However, their algorithm relies on generative model which takes multiple actions for the same state at the same time. In contrast, Theorem 7.4 suggests that O(dd 00.5 H -2.5) misspecification level can lead to a logarithmic regret without accessing the generative model.
EXPERIMENTS
To verify the performance improvement by data selection using the UCB bonus in Algorithm [ conduct experiments for bandit tasks both synthetic and real-world datasets, which we will describe in detail below. We also carry out exper- iments for linear MDPs on a synthetic dataset in Appendix B.4
Table 1:
Averaged cumulative regret and
elapsed time (E.T.) of DS-OFUL over 32 runs.
r
Regret (tean=isd.))
E.T.(sec)
0
305.15 = 43.98
10.26
0.02
332.28 = 76.17
7.75
0.05
256.265 = 61.28
3.96
0.08
184.75 +1.91
5.21
8.1 SYNTHETIC DATASET
0.20
374.63 277.51
4.56
LSW
348.73 = 69.28
4046
The synthetic dataset is composed as follows: we set d = 16 and generate parameter 0* ~ (O.LL) Ia) and contextual vectors { ~ (O, La) where N = 100. The generated parameter and vec- tors are later normalized to be 1/- = ||x 1. The reward function is calculated by r; (0", xx) + 7 where Y) ~ Unif(-
RLB
415.52 65.37
8.66
When r algorithm degrades to OFUL.
LSW: Using Eq. (6) in Lattimore et al. (2020)
RLB: Robust Linear Bandit (Ghosh et al. 2017
The con-
textual vectors and reward function is fixed after generated. The random noise the receiving rewards E, are sampled from the standard normal distribution.
We set the misspecification level ç 0.02 and verified that the sub-optimality gap the N contextual vectors A se 0.18. We do a grid search for 3 = (1,3, 10). x = 31,3, 10) and report the cumulative regret of Algorithm [ with different parameter r (0, 0.02, 0.05, 0.08, 0.2) over 32 independent trials with total rounds K = 2000. It's obvious that when I O, our algorithm degrades to the standard OFUL algorithm AAbbasi-Yadkori et al. [01I]) which uses data from all rounds into regression.
The result is shown Figure I(b) and the average cumulative regret on the last round reported in Table 1 with its variance over 32 trials. We can see that by setting I' z A/ 0.18/ / /16 0.05, Al Algorithm 1 can achieve less cumulative regret compared with OFUL (T = 0). The algorithm with a proper choice of I also convergences to zero instantaneous regret faster than OFUL. It is also evident that a slightly larger I' = 0.08 will not affect the performance but too large I 0.20 > A will cause the algorithm to fail to learn the contextual vectors and induce a linear regret. Also, our algorithm shows that using larger I' can significantly boost the speed of the algorithm by reducing the number of regressions needed in the algorithm.
We also compare with the algorithm (LSW) in Equation (6) of Lattimore et al. 2020 and the RLB in Ghosh et al. 2017 in Figure l(b) and Table
I For Lattimore et al. (2020) the estimated
reward is updated by r r(x) x 0 + 3 u. + Ex=lxx U x,=x,,1 1. However, since the term
is hard to be updated incrementally w.r.t. k. this algorithm is less efficient than Abbasi- Yadkon et al. (201T) as well as our algorithm. For the RLB algorithm in Ghosh
> ==1
1x KU x,,1 -
al. 2017 we did the hypothesis test for l 10 rounds and then decided whether use OFUL.
8

---

Under review as a conference paper at ICLR 2023
multi-armed UCB. The results show that both LSW and RLB achieve worse regret than OFUL since in our setting Ç is relatively small.
2000
1750
300
tegget
1500
1250
200
1000
100
500
(OFUL)
-- 0.01
0.05
0-
230
300
1000
1250 rounds
1500
1750
2000
0.0
0.2
# of rounds
1e6
(a) Cumulative regret comparison of DS- OSS-OUULL (b) Cumulative regret of DS-OFUL the Asirra (with difference choices of I),, Lattimore et al. dataset over 1M rounds with different I' under misspec- 2020) and RLB over 2000 rounds. Results are ification level ( = 0.01. Results are averaged over 8 runs with standard errors shown as shaded areas.
averaged over 32 replicates.
Figure 1: Experiment results on (a): synthetic dataset, and (b): real-world dataset.
8.2 REAL-WORLD DATASET
To demonstrate that the proposed algorithm can easily applied to modern machine learning tasks, we carried out experiments on the Asirra dataset (Elson et al. 2007). The task of agent is to dis- tinguish the image of cats from the image of dogs. At each round k. the agent receives the feature vector 1 521 of cat image and another feature vector 22 k 1252 of dog image. Both feature vectors are generated using ResNet-18 (He et al. 2016) pretrained on ImageNet (Deng et al. 2009). We normalize || ll2 @2,1112 I. The agent is required select the cat from these two vectors. It receives reward rt = if it selects the correct feature vector, and receives r2 = otherwise. It is trivial that the sub-optimality gap of this task is A the influence of misspecification on the performance of the algorithm, we only select the data with and r; otherwise. Or is a pretrained parameter on the whole dataset using linear regression l = argming ΣN (Ø. 0 - r,)?, which the agent does not know.
To better demonstrate
| 0* - ril S ( with r; if it
For pepeer-arrmmter tuning, we select = {1, 0.3, 0.1) and = {1, 3, 10) by doing grid search and repeat the experiments for 8 times 1M rounds for each parameter configuration. As shown 0) will have a better performance at the very beginning, setting I' = 0.05 s A/Vd 1/V512 will eventually improve the performance of the algorithm. As sensitivity analysis, we also C {0.5, 0.1, 0.05) to test the impact of misspecification on the performance of algorithm choices of r. More experiment configurations and results are deferred to Appendix
in Figure [(a] when Ç = 0.01, though the OFUL. algorithm (setting
CONCLUSION AND FUTURE WORK
We study the misspecified linear contextual bandit from a gap-dependent perceptive. We propose an algorithm and show that if the misspecification level ç Ô(A/ (d)//V)), Vd), the proposed algorithm can achieve the same gap-dependent regret bound as in the well-specified case. Along with Lattimore et al. 2020); Du al. (2019), we provide complete picture on the interplay between misspecifica- tion and sub-optimality gap, in which A/Vd plays important role the phase transition of ( to decide the bandit model can be efficiently learned. The algorithm and analysis have been extended to linear Markov decision processes and verified via experiments as well.
The promising result suggests a few interesting directions for future research. For example, it re- mains unclear if we can get rid of the prior knowledge of the minimum sub-optimality gap to achieve similar regret guarantees. It would also be interesting to incorporate the Lipschitz continuity or smoothness properties of the reward function derive fine-grained results.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Yasin Abhasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24:23 12-2200, 2011.
Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs.. In International Conference on Machine Learning, pp. 127-135. PMLR, 2013.
Peter Auer. Using confidence bounds for exploitation-exxloraiion trade-offs. Journal of Machine Learning Research, 3(Nov):397-422, 2002.
Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with value-targeted regression. In International Conference on Machine Learning, pp- 463-474. PMLR, 2020.
Romain Camilleri, Kevin Jamieson, and Julian Katz-Samuels. High-dimensional experimental de- sign and kernel bandits. In International Conference on Machine Learning, pp. 1227-1237. PMLR, 2021.
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff func- tions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 208. JMLR Workshop and Conference Proceedings, 2011.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hier- archical image database. In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pp. 248-255, 2009. doi: 10. 109/C/9R 10000.5.00888....
Simon Du, Sham Kakade, Ruosong Wang, and Lin F Yang. Is good representation sufficient for sample efficient reinforcement learning? In International Conference on Learning Represen- tutions, 2019.
Simon Du, Jason D Lee, Gaurav Mahajan, and Ruosong Wang. Agnostic g-learning with function approximation in deterministic systems: Near-optimal bounds on approximation error and sample complexity. Advances in Neural Information Processing Systems, 33:22327-2233 2020.
Jeremy Elson, John (JD) Douceur, Jon Howell, and Jared Saul. Asirra: A captcha that exploits interest-aligned manual image categorization. In Proceedings of 14th ACM Conference Com- puter and Communications Security (CCS). Association for Computing Machinery, Inc., October 2007.
Dylan Foster and Alexander Rakhlin. Beyond ucb: Optimal and efficient contextual bandits with regression oracles. In International Conference on Machine Learning, pp. 3199-3210. PMLR, 2020.
Dylan Foster, Claudio Gentile, Mehryar Mohri, and Julian Zimmert. Adapting misspecification in contextual bandits. Advances in Neural Information Processing Systems, 33, 2020.
Avishek Ghosh, Sayak Ray Chowdhury. and Aditya Gopalan. Misspecified linear bandits. In Pro- ceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
Botao Hao, Tor Lattimore, and Csaba Szepesvari. Adaptive exploration in linear contextual bandit. In International Conference on Artificial Intelligence and Statistics, pp. 3536-3545. PMLR, 2020.
Jiafan He, Dongruo Zhou, and Quanquan Gu. Logarithmic regret for reinforcement learning with linear function approximation. International Conference on Machine Learning, pp. 4171-41888 PMLR, 202
Jiafan He, Dongruo Zhou, and Quanquan Gu. Uniform-PAC bounds for reinforcement learning with lincar function approximation. In Thirty-Fifth Conference on Neural Information Processing Systems, 2021b. https:::: openreview net/ t
Eorum? Setprrummddd22eNooOUU 20eN0pU8 jae
Jiafan He, Dongruo Zhou, Tong Zhang, and Quanquan Gu. Nearly optimal algorithms for linear textual bandits with adversarial corruptions, 2022. URL httpt:tt///att :/tpiii.////xi.../// wwtp:/wwww.r.//a/////eaa/
06811
10

---

Under review as a conference paper at ICLR 2023
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Zeyu Jia, Lin Yang, Csaba Szepesvari, and Mengdi Wang. Model-based reinforcement learning with value-targeted regression. In Learning for Dynamics and Control, pp. 666-686. PMLR, 2020,
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pp. 2137-2143. PMLR, 2020.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Tor Lattimore, Csaba Szepesvari, and Gellert Weisz. Learning with good feature representations in bandits and in rl with generative model. In International Conference on Machine Learning, pp. 5662-5677 PMLR, 2020.
Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A contextual-bandii approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pp. 661-670, 2010.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wier- stra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602, 2013.
Aditya Modi, Nan Jiang, Ambuj Tewari, and Satinder Singh. Sample complexity of reinforcement learning using linearly combined model ensembles. In International Conference on Artificial Intelligence and Statistics, pp. 2010-2020, 2020.
Matteo Papini, Andrea Tirinzoni, Marcello Restelli, Alessandro Lazaric, and Matteo Pirotta. Lever- aging good representations linear contextual bandits. In International Conference on Machine Learning, pp. 8371-83388 -380. PMLR, 2021.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning. pp. 1889-1897. PMLR, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory algo-
rithms. Cambridge university press, 2014.
Kei Takemura, Shinji Ito, Daisuke Hatano, Hanna Sumita, Takuro Fukunaga, Naonori Kakimura, and Ken-ichi Kawarabayashi. A parameter-free algorithm for misspecified linear contextual ban- dits. In International Conference on Artificial Intelligence and Statistics, pp. 3367-3375 PMLR, 2021.
Benjamin Van Roy and Shi Dong. Comments on the du-kakade-wang-yaan lower bounds. arXiv preprint arXiv: 111//991000 100 2019.
Daniel Vial, Advait Parulekar, Sanjay Shakkottai, and R Srikant. Improved algorithms for misspec- ified linear markov decision processes. In International Conference on Artificial Intelligence and Statistics, pp. 4723-4746. PMLR, 2022.
Lin Yang and Mengdi Wang. Sample-optimal parametric q-learning using linearly additive features. In International Conference on Machine Learning, pp. 6995-7004. PMLR, 2019.
Andrea Zanette, David Brandfonbrener, Emma Brunskill, Matteo Pirotta, and Alessandro Lazaric. Frequentist regret bounds for randomized least-squares value iteration. In International Confer- ence on Artificial Intelligence and Statistics, pp. 1954-1964, 2020a.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning op- timal policies with low inherent bellman error. In International Conference on Machine Learning, pp. 10978-10989. PMLR, 2020b.
11

---

Under review as a conference paper at ICLR 2023
Andrea Zanette, Alessandro Lazaric, Mykel J. Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent bellman error. In ICML, 2020c.
Dongruo Zhou, Jiafan He, and Quanquan Gu. Provably efficient reinforcement learning for dis- counted mdps with feature mapping. International Conference on Machine Learning. PMLR, 2021.
12

---

Under review as a conference paper at ICLR 2023
A ADDITIONAL RELATED WORK
Linear Contextual Bandits. There large body of literature on linear contextual bandits. For example, Auer (2002); Chu et al. 201 101T); Agrawal & Goyal (0013) studied linear contextual bandits when the number of arms is finite. Abbasi- Yadkori et al. (2011) proposed an algorithm called OFUL to deal with the infinite arm set. All these works come with an O(v problem-independent regret bound, and an Odd2 loggK) gap-dependent regret bound is also given by Abbasi-Yadkori al. 2011).
RL with Linear Function Approximation. To tackle RL tasks in large state space, a line of work on RL with linear function approximation has emerged in the past years, For example, linear MDPs (Yang & Wang 2019 Jin al., 2020) probably one of the most widely studied models where both the transition kernel and the reward function are linear functions of a known feature mapping. Typical algorithms in this setting include LSVI-UCB (Jin et al.] 2020) and randomized ISVI Zanette et al. 2020a), both of which can achieve a sublinear regret. Besides, linear mix- ture/kernel MDPs (Modi et al. 2020 Jia et al. 2020: Ayoub et al. 2020 Zhou et al., 2021) has emerged popular model for model-based RL with linear function approximation, in which the transition kernel is defined as a mixture of feature mappings defined on the triplet of state, action, and next state. In this setting, nearly minimax optimal regret has been attained for both finite-horizon episodic MDPs and infinite horizon discounted MDPs (Zhou et al. (202I). The aforementioned works focused on the problem-independee regret bound, while He al. (2021a) provided gap-dependent regret bound for both linear MDPs (i.e., A 1)) and linear mixture MDPs (i.e., A A
B EXPERIMENT DETAILS AND ADDITIONAL RESULTS
B. EXPERIMENT CONFIGURATION
The experiment on synthetic dataset is conducted on Google Colab with 2-core Intel Xeon CPU @ 2.2 The experiment on the real-world Asirra dataset (Elson et al. 2007) is conducted on an AWS p2-xlarge instance.
B.2 DATA PREPROCESSING FOR THE ASIRRA DATASET
To demonstrate how algorithm can deal with different levels mis- specification, do data preprocess- ing before feeding the data into the agent. As described in Section 8.2 the remaining data with expected misspecification level Ç are shown in Table 2 It can be verified that even with the smallest misspecifica- tion level, there are still more than 10% the data selected.
Table 2: The number of remaining data samples after data processing with expected misspecification level
# of cats
of dogs
oo (without preprocessing) 0.5 (linear separable)
12500
12500
10316
10511
0.1
3182
3248
0.05
2408
2442
0.01
1886
1905
B.3 ADDITIONAL RESULT ON THE ASIRRA DATASET
As sensitivity analysis, change the misspecification level in the preprocessing part in the Asirra dataset. The result is shown in Figure 2 This result suggests that when the misspecification is small enough, setting r = A/vd can deliver reasonable result. It is aligned with the parameter setting in our theorem. Meanwhile, we found that when
0.5, which means it is strictly larger than the threshold A/Vd, the algorithm cannot achieve a similar performance with of Ç 0.1, regardless of the setting of parameter Г. This also verifies the theoretical understanding of how large misspecification level will harm the performance of the algorithm.
13

---

Under review as a conference paper at ICLR 2023
11930
F-32
10000
[-148
F-O SIA
[+0L]
0000
1339
2530
2000
0.0
0.3
0.6
10
(a) - 0.5
(b) Ç 0.1
(c) ( 0.05
Figure 2: The performance of DS-OFUL under different misspecification level Ç. Results are aver- aged over 8 runs with standard errors shown shaded areas.
B.4 ADDITIONAL EXPERIMENTS ON MISSPECIRIED LINEAR MDPS
To further verify the performance of our algorithm in misspecified linear MDPs, we generate synthetic MDP as follows. We select S = 6, A 4, H = 2 and generate Φ(s, a) and jus') ~ Unif.(O,, 1a) where d = 3 respectively. Since H 2, we define the first-stage transition kernel as Pi(s'(s, = (Ø(s, a), (n (ss)/SS
with normalization Φ(s,a) o(s a)/ /el/E.eta Eees (0(s, a), p) The misspecification error 17(s)) satisfies that (n{(')) - 2 x 10-3 and EVe[s) n(s') 0. The reward is generated by r(s,a) (o(s, a), + v)ss, a) with (n) (-approximate linear MDP with = 5 x 10 10-3 according to Definition 7.1 Then with the true transition kernel and the reward function, we can calculate that the minimal sub-optimality gap for the generated MDP is A R 0.0101.
10 It is easy verify that the generated MDP is
According to our theory, we choose == (1.3, 10) and report the cumulative regret with different choices of T. The results are shown in TableBand Figure 3 Three key observations can be revealed from the experiment result in Table 3 First, choosing
0.01 can achieve the best performance (lowest cumulative regret). Second, choosing 0.005 < r < 0.01 can also lead to comparable
constant regret, according to Table 3 but smaller I' may not lead to zero instantaneous regret within
200K rounds. Third, setting I > A will lead to linear regret.
In addition, our algorithm degrades to LSVI-UCB algorithm Jin et al. 2020p by setting I 0. For misspecified linear MDPs, the algorithm studied in Theorem 3.2 of Jin al. (2020) is still
LSVI-UCB with a different choices of confidence radius B. In our experiments the 3 is tuned as hyper-parameter. Therefore, the experiment results suggest that algorithm outperforms the LSVI-UCB algorithm in the misspecified setting.
800
500
Cumuistve Regret
600
660
200
460
100
0,001
0.005
0.009
0,002
0.006
0.01
25K
100K 125K 150K
175K
200K
0.002
0.004
0.006
0.008
0.010
(a) Averaged cumulative regret of DS-L.SVI over (b) Cumulative regret DS-L.VT with different choices of I after 200K rounds. Each experiment with the same I' is repeated for 8 times, and each point represents individual experiment.
8 replicates with different choices of T.
Figure 3: The performance of DS-LSVI with different choices of T. (a): averaged cumulative regret w.r. number of rounds. (b): cumulative regret after 200K rounds with different choices of T.
14

---

Under review as a conference paper at ICLR 2023
Table 3: Averaged cumulative and instantaneous regret of DS-LSVI over replicates for 200K rounds with different choice of I (see the footnote for the specific choice of T). "Last 1K rounds cumulative regret" means the total regret incurred in the very last IK rounds, in order to verify the final performance of the algorithm. "Total 200K rounds cumulative regret" means the total regret incurred during the entire 200K rounds.
Last IK rounds cumulative regret (scan=std.)
Total 200K round cumulative regret (meantsst.))
r
0.0
0,133 = 0,291
541.9 27.0
0.001
0.118 + 0.215
557.1 44.2
0.002
0.295 + 0,480
563.7 36.5
0.003
0.523 + 0.323
551.2 13.6
0.004
0.185 + 0.133
548.3
0.005
0.00 + 0.00
527.7 23.0
0.006
0.00 0.00
455.6
0.007
0.00
4 19.2
0.008
373.4 13.3
0.009
0.00 + 0.00
350.7 + 10.3
0.01
0.00 0.00
310.6 14.3
0.011
2.053 + 1.185
624.2 = 194.5
When 0, our algorithm degrades LSVI-UCB
r 0.005 A/Vd 0.0101/ /000///3//00 /3 in this setting
C DETAILED PROOF OF THEOREM 5.1
In this section, we provide the detailed proof for Theorem 5.1 First, we present technical lemma bound the total number of data used in the online linear regression in Algorithm [
Lemma C.1. Given 0 < r S 1, set À = B-2 For any 1: E [K]. [C S 16d[ log log(3LB(
Lemma C.1 suggests that up to Ō contextual vectors has a UCB bonus greater than T. A similar result is also provided in He et al. (2021b), suggesting ( Uniform-PAC sample complexity. Lemma C.T
C. also suggests that the numbers data added in regression set C is finite,
thus the regression procedure is not affected critically by the noise and the misspecification error.
For linear regression with up to |C&| data, the next lemma is crucial controlling the fluctuations with misspecification error.
Lemma C.2. Let À B-2, 2, For all 0, with probability least 1 8, for all R4 k e [K], the estimation error is bounded by:
x (0, - -0)) < 1 RV2di + sVIGel) ||x||o,",
where - = log((d + (2) (d))) and [C&] the total number of data used in regression at k-th round.
Lemma provides similar decomposition the well-specified linear contextual bandits algo- rithms like OFUL (Abbasi- Yadkori et al.) 2011). However, comparing the confidence radius here Ö(Rvd (CCC= with the conventional radius in OFUL (RVd), specification term will affect the radius in an vlC] order. If we directly use all data to do the regression, the confidence radius will be in the order of θ(v OKKvlog K) regret bound (see Lemma 11 in bound trivial since it goes beyond the trivial regret upper bound ((K) when K grows larger. In ours, however, the confidence radius is only v[Cx] where |Cx| is finite given Lemma C. As result, our regret bound will not grow with as OFUL, and will have a more stable prediction.
can find that the mis-
Yadkori K) and therefore would lead to (2011)). This makes the regret
When the misspecification level well bounded by ((A/Vd), the following corollary is a direct result of Lemmas C.2 by replacing the term Cx with its upper bound provided in Lemma C.I
Corollary C.3. Suppose 2 /d < A, let À B-2 and 0 I 1. Let 8 = 1 1+24r-1, / / + log( 167 22)) /5), then with probability least
R22dig where 12 log(3I.
15

---

Under review as a conference paper at ICLR 2023
1 1-8, for all x Rd, [K], the estimation error at round it [K] is bounded by: |x (0x-0")1
|||x||u,--
Proof. By Lemma C.I replacing [Cx] with its upper bound yields
0 0*) S (1 + 4 V22 + Rv R 22/2 |x S |||x|o,;"
where the second inequality is due to the condition 2vd S A/4.
Next introduce auxiliary lemma controlling the instantaneous regret bound using the UCB bonus and the misspecification level.
Lemma C.4. Suppose Corollary bounded by
C.3 holds, for all & [K], the instantaneous regret at round A is
(x(x)) = r r(xx) $ 2Ç 2/3 x
The next auxiliary lemma from He et al. (021a) bounds the summation of subset of the self- normalized vectors.
Lemma C.5 (Lemma 6.6, He et al. 2021a). For any subset g ,4i S Ck. we have
Σ
||x u s 2d + [g)T2/A))
kEG
The next two technical algebra lemma is used to control the dominated terms
Lemma C.6. Let = (24+188) log (174-+7)))DD((2---/7)))-11111)
1og(1/8), B, A/(2Vdr1)
(2 = log(3LB[ lg = log((1 + 161 16L2 we have 4 > 2 4 1/122 + RV
Equipped with these lemmas, we can start the proof of Theorem 5.1
Proof of Theorem 5.7 First, it worth mentioning that by setting r = A2(2/d(1), the confidence radius 3 becomes + 4 dig + 2 Then our proof starts with assuming that Corollary C.3 holds with probability at least 1 - 5. We decompose the index set [K] into two subsets. The first set [K] \ Cк indicating the non-selected data, the second set is the selected set Cx. We will bound the cumulative regret within two set separately.
First, for those non-selected data I & Ck. i.e. ||x||lu;" < r, combining Lemma C.4 with Corol-
lary yields
A
223
RA
4A
1 r(xx) < 25 23T 2Ç
(C.1)
ddi
41
41
where 41, /2, are the same as Theorem 5.1 and the second equation is from I A/(2/dr1).
When misspecification condition 2/d dc < A/t3 holds, [.I suggests that
2A
4A
4A
12
VA
r r(xx) <
(C.2)
Vdl
4
41
Lemma C.6 suggests that when (24 18R) log( SAR)LBVAA-1) +
log(1/8 lo
> 2 4 4/ 2 / C22) yields that the instantaneous regret r r(xx) < A at round k. By
Definition 3.1 the instantancous regret is zero for all & C,. indicating the non-selected data can incur instantaneous regret.
16

---

Under review as a conference paper at ICLR 2023
Then Lemma C.4
suggests that the instantaneous regret for those Cx is bounded by
Σ r - r(xx) 2
Σ
(2 lu," 25)
- 23 /CKl
1 12 + +2|Cx|5
KECK
< 8,8 /di 2d log(1 16dl -21) +-32Cl 3/2
- v63v 2d log(1 + 16d1 222) / + 64v 1412//
2 323 /2d log 16d[ 2(2)4
(C.3)
where the second inequality follows the C.S. inequality, the third one yields from Lemma C.5 while the fourth utilize the fact that r A (2 and Ç f A/(2 The last one is due to the fact that the second term in the forth inequality is dominated by the first one.
To warp up, the cumulative regret be decomposed by
E(r - (xxer())) 5O 323 2d log(1 + 16dl (12)
Regret(K) = E
(ri - rxx))) + kGCK
A
KECK
where the first two zeros are given by the fact that for E CR. we have rī r(xx) O. the regret bound for & E G is given by CC.3
D PROOF OF TECHNICAL LEMMAS IN APPENDIX
D. PROOF OF LEMMA
To prove this lemma, we introduce the well known elliptical potential lemma by Abbasi- Yadkori al. (20TT)
Lemma D.1 (Lemmaa 11, Yadkori et al. 2011 b. Let ( be sequence in Rd, define
U, AI Σi= o5 then
Σ min {1, | 1
Ad Ad + IT,2
s 2d
Ad
Then the following auxiliary lemma and its corollary useful Lemma D.2 (Lemmaa A.2, Shalev-Shwart, & Ben-David 2014). Let a 2 1 and > 0. Then x 4a log(2a) + 2b yields
log(x)
Lemma D.2 can easily indicate the following lemma.
Lemma D.3. Let 2 1. Then > 4 log((2) + a yields log(1 ar).
Proof. Let 1 + 4a log(2a) + 2. By Lemma D.2 this implies y 2 log(y) + which is exactly x 2 log(1 +ar).
1)/a. Then log(2a) + a1 is equivalent with y >
Equipped with these technical lemmas, we can start our proof.
Proof of Lemma C.1 Since the cardinality of C₁ is monotonically increasing w.r.t. k fix to be K in the proof and only provide the bound of Cx- For all selected data & E Ck, we have | 2 Therefore when I < 1, the summation of the UCB bonus over data Cj is lower bounded by
Σ min { 11, 11 2 |Cxl min(1, = [2.
(D.1)
RECK
17

---

Under review as a conference paper at ICLR 2023
On the other hand, Lemma
D.1 implies
Σ min { 11 I1 " } - 2d log
Ad CC L2
(D.2)
Xd
kECK
Combining D.2 and (.I) the total number of the selected samples [Cx] is bounded by
Ad + |Cx T,2
r&|c1= I 2d
Ad
This result can be re-organized
[
2L
CK]
< log
1+
(D.3)
2d
2d
Let B-2 2 and since 2L²B²
2 2 1
Lemma
D.3 suggests that
[4
log
+ +1 4 log
2d
r2
r2
2T
then D.3)
will not hold.
Thus the necessary condition for (D.3 is
[2[
A22B²
2LB
2LBe>
3LB
<
4log
+1
log
+ llo(()) 8log
<8
2d
r
r
r
r
By basic calculus we get the claimed bound for [Cxl and complete the proof of Lemma C.I
D.2 PROOF OF LEMMA C.2
The proof follows the standard technique for linear bandits, we first introduce the noff-normalized bound for vector-valued martingales from Abbasi- Yadkori et al. (201T).
Lemma D.4 (Theorem Abbasi -abbossi-addkoii et 2011). Let [Fe be a filtration. Let { be real-valued stochastic process such that E, is J.-measurable and e; conditionally R-sub-Gaussian for some R 2 0. Let { be an 1dd-vllued stochastic process such that Φ; is Fi-1 measurable
and ||/6|/ < L for all I. For any / 2 0, define U, AI ===1 Φ. Then for any 5 >> 0, with
probability at least 1 - 8, for all 2
Vdet(U.)
ΦREK
< 2R log
Vdee(U,))
Lemma D.5 (Lemma 8, Zanette et al. (020cc).. Let {a. 1 be any sequence of vectors in Id and [b,)1 Ji be any sequence scalars such that [b: I e. For any X > 0:
a
< nc²
i=1
En a. AT
The next lemma is to bound the perturbation of the misspecification
Lemma D.6. Let {mx) b be any sequence of scalars such that Innl for any k E [K]. For any index subset C' C [K], define U = AI Ekec XxX; then for any x E Rd, we have
Σ X
I _c/cl||ii/u-
x
REC
Proof. By Cauchy-Sehwartz inequality we have
X
<
|
Σ X
5 <CVCC||lilbu-
REC
AEC
U-1
where the second inequality dues to lemma D.5
18

---

Under review as a conference paper at ICLR 2023
The next lemma provides the Determinant-Trast inequality.
Lemma D.7. Suppose sequence {xt ) C R and for any l: E [K], |xx|l2 S L. For any index subset C _ [K]. define U XI + ΣkEc X for some À > 0, then det (U) 3 (A + /c)L2/dy".
Proof. The proof of this lemma is almost the same with Lemma 10 Abbasi- Yadkori et al. (2011) by replacing the index set [K] with any subset C. We refer the readers to check Abbasi-Yadkor Yadkori et al. 22011 for details.
Equipped with these lemmas, we can start our proof.
Proof of Lemma C.2 For any [K]. considering the data samples 1 E CB-1 used for regression round k. Following the update rule of UR and 0g yields
U2 - = U
Σ
XF.TK)
AI
Σ
x
MEECE-1
MEC
Σ
XETW 10"
Σ
X
REC+-1
k'ECa-1
-10"
+
Xp.(Tk'
x
W
= -00 +
Σ XKEW +
Σ X
R'ECA-1
WECx
where the first equation is due to the fact that Up AI Evec, X and 0g Us E''Exe XETK.. The last equation follows the fact that rwe is generated from TMe r(xx) + Ek' = xT.0" + 7(xx)) + Ex', where we denote n)(x))) as Th for the model misspecifi- cation error and EK the random noise. Therefore, consider any contextual vector x E R4, we have
x (0x 0*)l = U
Un
0*)
s x U k
0
x U
ΦNEN
+
x U
Σ
ΦUITK
k'EC
92
where the inequality is due to the triangles incquality. Lemma D.6 yields g SCVVCC A. we can bound term by < |||||||y||
|x|
U.
From the fact that [x Ayl
4 S x u | 10011,,, S - 1/2 B|xllu,,
(D.4)
where the last inequality is due to the fact that U, 3 -I Term q2 is also bounded as
K
- |x||u,'
Σ
XWEE
= |
1 IK' E C
(D.5)
U.."
where the second equation uses the indicator to replace the summation over subset Ck-1- Denoting Yu = 1 [k' E Ck-1] X noticing that ||yx|12
1|2 ||x ll2 S and
K
K
U
Σ X
Σ
1
I E x = Σ NuyI
A'EC-11
Ø=1
F=1
by Lemma D.4 I can be further bounded by
det((Ux) dee((Un)))
(dt((Us)
11 <
2R log
I Rg 2 log
= R1/ 2
(D.6)
[det(U.)))
Ado
19

---

Under review as a conference paper at ICLR 2023
where the second inequality follows the fact that dc) det(U,) = X4. Notice that U3
AI + ExecL_, X/ lemma D.7 suggests that det (Up) I (A + [C /d)", plugging this
into (.6)) we have 1 can be finally bounded by
(A+ Cx /22/d)0)) R 2d 2dlog
dd + 1C
1 s RV
2 log
X
dAg
Plugging the bound of 1 into D.5)
and combining with (D.) and Lemma D.6 together, replacing have with probability least 6, for all [K], E
[Cx-1/ with its upper bound |Cx
Ad + 1xx|122
x (0)- -0')
Ry
2d
+ BA BX- 1/2 + /V/C I
dAø
Letting 2 we get the claimed results.
D.3 PROOF OF LEMMA C.4
Proof. According to the definition of expected reward function r(x), we have for all e [K],
suppose the condition in Lemma C.2 holds, then
Th
77xx)) (xx) + (xx) 0- - x 0r
S 2 (xx) T 0- -x]
x 0"
2Ç + (xx) T 0% + (xx) (0" - 0:) - -x, 0x + x (0) - -k)
(0"
2Ç + (xx) T 0% + B |||x| ulu x 0x -111381l1 1
< 2Ç + x 0g |||x ul x2 0x + 3||xA| u
2Ç + |/| lu."
where the second inequality utilize the fact that [n) < for all X E Dz- The inequality on the forth line follows Corollary C3 The inequality on the fifth line due to the fact that X₃ argmaxxeD, x 0₂ + +| which is executed in Line 4 in Algorithm
D.4 PROOF OF LEMMA C.6
Proof. First it is clear to that 2213 log(1 B2T 2/2) + 2 llg((1))) Using the fact
that Va b S Va Vb, it can further bounded by
/213 S 22log(1 16L2 / (10g))
Assuming 1.2 1, B 1, = 2/(2/d)) S yields LBD-1 2 1, then by basic calculus one can verify that
2 4 < Ellgg(3LB
1llog(1 S 33log(LLBI
therefore we have that
2+ 4 RV21s _ 3R) log / 2og (
= -6 log (6LBv + /2 log(1/5)R,
where the last equality is from the fact that r A/(2/dr,) Lemma D.2 suggests that the necessary condition for
(6LBvdA da )e
(6LBVdA (6 + 38) log log(6LBVaa -t)) (6LBVdS 1) log 1
(D.7)
20

---

Under review as a conference paper at ICLR 2023
is that
(6LBvdA->)
3R))
+ +2(6LBv 22)6BBVAA")//22g((1/0/22 2)00))/(())))))
which suggests that setting
" = (24 + 1881 ( 5AR))BBVA + 8R log(1/6)
implies the fact that 41 4/12 Rv253
E PROOF OF THEOREM 5.4
To begin with, we introduce the lemma providing sparse vector set in Rd
Lemma E.1 (Lemmaa 3.1, Lattimore et al. 2020). For any > 0 and d < [[D]] such that d 2 [8 (og((D)) 21, there exists vector D Rd such that ||x|| 2 1 for all and (x. y) for all y E D and x #
Next, we present the Bretagnolle-Huber inequality providing the lower bound to distinguish sys- tem.
Hubber Lemma E.2 (Bretagnolle Huber inequality). Let P and Q be probability measures on the same
measurable space F), let A E F be an arbitary event. Then
+(A)+ 2 exp(-KL(P.Q))
For stochastic linear bandit problem with finite arm, we can denote (k(k) as the number rounds the algorithm visit the i-th arm over total k rounds. Then We have the KL-divergence decomposition lemma.
Lemma E.3 (Lemma 15.1, Lattimore Szepesvári (2220). Let v = (PI,... Pa) be the reward distributions associated with one n-arred bandit and let v' = (P).-.. P.)) be another n-armed bandit. Fix some algorithm and let P, P Poz, P.r Pvr. z be the probability measures on the canonical bandit model induced by the k-round interconnection of and v (respectively, and v'). Then (L,P,,
Ei E., (L)
Proof of Theorem 5.4 The proof starts from inheriting the idea from Lattimore al. 2020). Given dimension d and the number of arms (D), setting = (8lg(( 1). we can provide the contextual vector set D such that
8 (P)
|x||2 1, VX
Vx.y Dxx
For simplicity, we index the decision set as X1 provide the parameter set @ follows:
Given the minimal sub-optimality gap A,
+ (( Ax; 2AX, X, D,i D (): 1(0 Ax,
It can be verified that + contains two kinds of O. The first one ((i,)) is mixture of two different contexts x,, Xj with different strength A and 2A. The second one is 6 which only contains features from one context x, We can further verify that the size of O = |D|2 and ||0|| < V5A for 0 e O. For different parameter 0, the reward function is sampled from a Gaussian distribution (rre(x), 1), where the expected reward function is defined as
2A if X,
= ( [Aifx= X;
(o (x)
A ifx= x;
(x)
10 otherwise
0 otherwise
21

---

Under review as a conference paper at ICLR 2023
We can verify that the minimal sub-optimality of all these bandit problem is A. For different param- eter θ and input x, by utilizing the sparsity of the set D (i.e. misspecification level
|x y =f + y), we can verify the
22 2Ax x Ax, x Ae if xjj
( (x)
0 (8.5)
x
A 2Ax, x - Ax x - 2 if = X4
(0 2Ax, x Ax, x < 3 otherwise
0f X 110 Ax, x S As otherwise.
||A- Ax," x
rro (x) (x)(
Therefore we have verified that the misspecificatioo level is bounded by Ç = 3ÂE.
The provided bandit structure is hard for any linear algorithm to learn since any algorithm cannot get any information before it encounters non-zero expected rewards, even regardless of the noise of the rewards. We following the same method in Lattimore & Szepesvári (2020). If the algorithm choose arm i at the first round, there would be [D] parameters (i.e. 6,, 8 (c.)) receiving a non-zero expected reward. On the second round if the algorithm choose a different arm j. there would be (D] parameters (i.e. 0j. ()) receiving a non-zero expected reward. Therefore the average time of receiving zero expected reward should be
[D]
DI
[D] 2
2 11
(1 - i 1)
1)(
(D]
2
i([D)
i)
=0
DI-1
ID1-1
|D]
|D]
Σ i i-
Σ 12
t=
k=0
(D)
-
DD
1)
[DI-2
2
6
|D] 1
(1- 2|D| - 1
2
3|D|
|D] -
6
where the third equation is from the fact that Σ Σー n(n + 1)/2 and Σ ビ = 1)(2n + 1)/6. The last inequality is from the fact that 2 ()) < 2/3. Therefore, even without of the random noise, any algorithm expected to receive min K, (D) - 1)/66 uninformative data with expected reward to be zero. Therefore any algorithm will receive A Amin(K, (D) 1)/6}
regret considers the suboptimality as A.
Next, we consider the effect of random noise. For any algorithm running on this parameter set O we find two parameter O, and 0,,; where j + i. Define the event as A = (T)(k) 2 k/2) and A (k) < k/2]. By Lemma E.2 and Lemma E.3
k )
k TT(kk)
1
Po. (7,())
+ Po
exp( - KL Po..s))
2
2
(-
1
exp
(-I
Σ nED
Eo, (K) (Po Po,
2
(E.1)
Noticing the minimal sub-optimality gap is A. Also the j-th arm is the sub-optimal arm for pa- rameter 0,, Therefore, once Tkkk) 2 k/2, the algorithm will at least suffer from Ak/2 regret for parameter O,. Also, since the j-th arm is the optimal arm for bandit ((.)) If (k) < k/2, the algorithm will also at least suffer from Ak/2 regret for (i.g)) Denoting R (k) as the expected cumulative regret over le rounds, that is to say
Ak Pa. (T)(k) 2 k/2) Ra, (k) 2 2
AA Po. (T₃(K) < k\2)).
Ra, (k) 2 2
(E.2)
22

---

Under review as a conference paper at ICLR 2023
On the other hand since the bandit using 0, and 0 only differ in the j-th arm. Since standard Gaussian noise is adapted, KT.(Po,,n. Po (t.)))))) = A 1 [n j1/2. Combining this with F.2 (E.1) suggests that
Ak
A Be [T) [T)
Re, (k) + Ro, (k) 2
exp
2
2
which suggests that
log (Ak) log - Rog(Ro, (k) + Ro, (k))
Eg. (b)] 2
(E.3)
22/2
For any algorithm seeking to get sublinear expected regret bound of Ro (k:) S C with C >
0, 0,0 for all A θ (F.3) becomes
log( AA)
log 2 log(2Ck") log(Ak) loog(CC) log k
Eg, [+)
(E.4)
A
/
Since that the regret on 0, can be decomposed by
Re: (k) A
Σ nml,,ngh
(k),),
(E.5)
combining
B.5 with (.44) yields
2([D|- 1)
Ra (k)
max flog( AA) - -log(4C) log k, 0},
where the max operator is trivially taken for Ro(k) (k) 2 0.
F PROOF OF THEOREM 7.4
In this section we provide the proof of Theorem 7.4 start from the technical lemmas for the proof. The first lemma is similar with Lemma C. by setting À L as in Definition 771 and taking union for possible cases
Lemma F.I. Given
< 1. For any k [K], [2
8H log(6HT-
Then the next lemma extends Lemma C.2 and Lemma C.4
1 setting and is similar with Lemma C.5 in Jin et al. 22020) by replacing the total number K with Ck used in regression
Lemma F.2 (Lemma C.5. Jin et al. 2020). Let 3 (dH + (S-LVS where 4 log (2g()T--2), 12 log( a " ()) and cæ is an absolute constant. With probability least 1 - 8, for any fixed policy и and (s, a,, h, E A (H) x [K].
(s,a)w/ (T = PA 4+1 - V (s, + (s.
where (8) a)l < 3 (( (1
Given Lemma F22 we can provide the rate of confidence radius 3 by adapting the condition and parameters setting: on the misspecification level and the parameter setting
Corollary F.3. Let the misspecification level be bounded by Ç Ö H - and choose the threshold parameter to be 1yAd--H-2 one can verify that the / in Lemma F22 can be bounded by 3 < B = O(Hd).
Given this corollary, we show that the sub-optimality gap is controlled by three parts: summation of the UCB bonus, misspecification level and the noise induced by the probability transition kernel.
23

---

Under review as a conference paper at ICLR 2023
Lemma F.4. Suppose Corollary F.3
and Lemma F.2
holds, for any subset A S [K] and h E [H]
have
Σ REK
An(sh at)
VA (sh)
V (sh)
keK
H
H
2
Σ
1 ( 4
E
Σ
h'=h
kEk. I =1=++11
where 5x == [P h+1 V (s a (V (5ti(()) variable conditioned on all randomness before episode k.
Vitt (+)++1)) is zero-mean random
Then the next lemma suggests that the cumulative regret can be bounded by the summation of sub- optimality gap at all stage, with high probability
Lemma E.5 (Lemma 6.1, He al. 2021ap. For each MDP M(S, A, H, {ra), (Pii), with proba- bility at least ö, the cumulative regret over K episode is bounded by
H
16H
log (HK) +
Regret () 2
A (8 a
log
+
3
8
Jo
Equipped with these lemmas, we can start our proof.
Proof of Theorem 7.4 For simplicity, we denote the non-selected episode set as ČK := [K] \ Ck. We first assume Lemma F2 holds. We fix stage h and then define the following sequence to apply the peeling technique which is also used in He et al. (2011)). For O s 1 s log(H) (og(H/A), A) (2). E N,
let Kg and
k min(k: k 1/-1, 2'A S (N at) < 2 A, K E [K]].
Since a, a) < H. there exists 1 + log(H/A)/ log(2) levels. We further denote Kr: (k).... M |x, to be the set of the sequence {1/ We fix one level I in the following proof. lower bounded, we have
On the one hand, due to the fact that (s at)
Σ kEKi
An a
2 2'A//ll
(F.1)
On the other hand, Lemma F.4 yields
(s
S 23
1l (Ugg)
(F2)
Ck
kE
REK.
k'=h
kE i W'=h
1
1
By Azuma-Hoeffding's inequality, with probability least 5/H, H. T3 is bounded by
HK
1 =
2 log
(F33
Since [K] Ex U Ck. term I is be decomposed as
H
# l ( Σ Σ
1 = Σ Σ
Σ
Σ
l1 (1
kEKL M=A
kERSnN M=b
REKiNex M=hh
< HT]K nx + H H KINCK
Σ KEKiNR
11 ||
((ug))
HTT n Cxl + H KG CC
2d [(
< HT|K H Kc/ 2og K),
(F4)
24

---

Under review as a conference paper at ICLR 2023
where the first term in the first inequality utilizes that | - I for all h Cg and the second
term is from triangle's inequality. The second inequality utilizes Lemma C.5 The third inequality
is because both [K nxll and J Ck] is smaller than [Kr] as well as K. Plugging
F.3)
and (F.4)
into F22 then combining
F22 with (F.1) yields
НK 2/ & (23HT + 4H Ki + KHidKi + K) + + 22
(F.5)
Recall the parameter setting 3 T be guaranteed that I3 I A/2 - 2' A/2. The calculation of the logarithmic terms follow the proof of Theorem [.1 where we ignore for simplicity. Plugging this into (F.5) we have that when the condition on Ç satisfied,
as long as (= O(Dd
HK 8
2' 2' S 3H 32/K2 3 K) + /SIKi///Sog log
by the fact that (vā + vb)² < 2a 2b, this implies
НК
A KG & 646² H d + K) + 16H log
= LT.
(F6)
This suggests that [G] 4-'A-21, with probability least 1 5/H. Since for all k Kr, An o < 21+1 A, the cumulative sub-optimality gap in set IG, is bounded by
Σ kERT
An atd < 2 x 4- ' 1 S 2 14
(F.7)
Replacing ō with 8/(1+ log( H 1 (2). we have that with probability at least - 8/H, F.7 holds for all < log(HA (2), / N by union bound. Therefore we have that
Dlo( (/) 1og(
Σ
Σ
An a 2 Σ 2 - -1 14 14-
(F88
By union bound we have with probability at least - 8, F. holds for all h E [M]] thus
K
H
(s a I 4HA -14.
(F99
By Lemma
F.5
plugging the value of /4 in F.6 back to F.9 yields
K
16H3
(og(HK) +1
Regret( K))
ah) +
log
+2
3
h=1
16H3
log
log(HK) (HK) +1
< 88HA 1,
log
+2
3
512,3 2
loog( + K+)
128H A log(HH//))
16H3
log (K) +
log
+ 2,
5
with probability at least - 36 by union bound over the probability event in Lemma F2 Lemma F.5
and (F.9). By Corollary F33 3 O(Hd+ -H+ O(Hd), replace 6 with 8/3, we have the
regret is bounded by
Regret(K) (K) < Ō(H5& - lllg(K))
with probability at least 1-6 8.
25

---

Under review as a conference paper at ICLR 2023
G PROOF OF LEMMAS IN APPENDIX F
G.1 PROOF OF LEMMA F.1
The proof technique is similar with Lemma C.1 equipped with Lemma D.I and the Lemma D.3
Proof of Lemma F.I Since the selected data samples follows that there exists an h E [H] such that
1l (ug))1 2 r, therefore the summation of the data is lower bounded by
H
Σ
min 1, (lll)() 2) 1cx112
(G.1)
RECa h=1
on the other hand, Lemma yields
H
min 1, 11,1 (1:)) - 2dH 2dH log(1 + |Cxl/d),
(G.2)
AEC& A=1
where À = 1. Combining
G.1 with G.2) yields
2 Cal S 2d/1 log(1 + [Cxl/d]
(G.3)
then following the same rule as the proof of Lemma C.I we have the necessary condition for
G.3
is
C& < 8HdT log (6
(G.4)
G.2 PROOF OF LEMMA F.2
Proof of Lemma F.2 from which we have
The proof of this lemma follows the proof of Lemma C.5 in Jin et al.
2020
w -(( (UN)
Σ
[PA a a|)]
BEC+-1
4:
+ (U+)
Σ
Dish ah) ((th))(shh,h))
1ECx-1
Σ BEC
(lsh W 1 (sh. on))n)) + [Ph. P
94
where P(-|s. (s. a) is the well-specified transition kernel defined by P(-|s,a) = (u(-), (5s a)). From proof in Jin et al. (2020) we have that for any (s,a) E A,
(0(8, 91) (((s,))) ((d)))(((s
(allwllllll(s S VABIIo(s.
(Ø(s, a). q3) Pv (V+++ (s, p2, |2a < <2Hvdx|o66s (a)o)((s)))ee ((()))))
For the fourth term, by Lemma D.6 which improves the Lemma C.4 in Jin et al. (2020) by factor of Vd. we have
( qu) s
a) (
Finally, since (Ø(s.0) a), wh w (Ø(s, qı + q2 + qs qa) we have that (8(ss, a), wh) (T a) (V V (s,, a)) < Ö(Hd HS HCv a)llu))) plugging the bound of |C in Lemma back will have the claimed results.
n
26

---

Under review as a conference paper at ICLR 2023
G.3 PROOF OF LEMMA F.4
The proof of Lemma F.4 follows the same technique from Jin al. (2020) and warp it here for completeness. The first lemma shows that the estimation of Q function is still optimistic regardless the misspecification.
Lemma G.1 (Lemma C.S, Jin al. 2020). Under the parameter setting in Theorem 7.4 and 2 (7 a) 4H(H + - h)ς for all (s, a, h k) E
Lemma
F.2 holds, we have Q% a)
S x A x
[K].
Next lemma provides the recursive error bound for the estimated value function V%)
Lemma G.2 (Lemma C.6, Jin et al. 2020). Suppose Lemma F.2 holds, we have for all (h, k) E
[N] [K].
(5%) V (sh) Vh+ (+h+()))))= (
[PV Vad Vntillsh, + 23ll a (u:))
where V-+ 0.
Proof of Lemmal F.4 We first denote E as [P(V - V (s a it's easy to verify that is zero-mean random variable conditioned on all randomness before k-th episode. By Lemma G. for all (s, a, h, k) E S x A [H] [K], we have (s, a) 2 (s. 4H²g. Also, by the definition of minimal sub-optimality gap in Definition 7.3
we have
(s a = Vi - (7h ah)
Qh ah)
= I Oh (b + +412 ( a
Since Algorithm taking the greedy policy a argmax, 0 ( a), the sub-optimality gap bounded by
(n at) (5h at @ att) + 4H V (s+)) V/ (sh)) 4H²S.
(G.5)
since V/, (sh) V (s/)). Following Lemma
G.2 by telescoping we have
H
(sh ) VØ²** (s a
Σ
* + 28
Σ
( a (()))
(G.6)
W=A+1
k/=h
Plugging G.6 back into G.5 we will have the result as
H
H
& a
4H2S +
Σ
+ 23
Σ
( ti a (1U))))))))
h'=h
Since it holds for all & [K]. we can take additional summation over A E K. C [K] claimed result.
get the
27


Reviews:
[{"review_id": "xBU3zkH1ks", "reviewer": "Reviewer_2Y3y", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper studies linear contextual bandits and linear MDPs with misspecifications. It proposes a new thresholding scheme for data selection, which can be used with OFUL and LSVI seamlessly. For linear contextual bandit, DS-OFUL yields regret upper bounds of same order as that of the well-specified setting. The paper also provides a lower bound on regret for higher levels of misspecifications. For lin MDPs, it proposes DS-LSVI, which achieves logarithmic problem dependent regret.", "summary_of_the_review": "The paper theoretically studies misspecification in LCBs and LMDPs. It proposes a data selection refinement with OFUL and LSVI, that only considers data with higher uncertainty. The corresponding regret analysis conforming the bound on misspecification level, i.e. O(\\Delta/\\sqrt{d}), is an interesting result. The paper still lacks some portions as pointed out in the weakness. Addressing them will strengthen understanding of the contributions.\n\n*****\nAfter rebuttal: The authors have improved the experimental section with new comparisons demonstrating effectiveness of DS-OFUL and DS-LSVI. But the idea to tune $\\Gamma = \\Delta/ \\sqrt{d}$ seems unrealistic, as $\\Delta$ is not a prior knowledge in real applications. Additionally, the algorithm seems to be quite sensitive to $\\Gamma$ and can behave similar to (Lattimore et al., 2020) if not tuned. Thus, I shall increase my score due to the response but cannot argue for an acceptance.", "strength_and_weaknesses": "Strength:\nThe problem and results as mentioned in the summary are interesting and relevant to the existing literature in this topic.\n\nWeakness/Questions:\n1. The claim that the regret bound improves the logarithmic factor log (horizon) than existing linear contextual bandits results is misleading. For \\delta=1/K, which is a common and justified choice, we observe that this term reappears. Removing this claim misleads more than focusing on other interesting contributions in this paper.\n\n2. What happens to the regret upper bound of DS-OFUL when \\zeta > \\Delta/\\sqrt{d}? How does it grow with \\zeta or is it still robust up to certain limit?\n\n3. What is a good way to tune \\Gamma than trying different values as done in experiments? Does the analysis point us to any such choice?\n\n4. In experiments, we miss two things: a comparison with other misspecified bandit algos (such as Ghosh et al., 2017) and an experiment on linear MDPs. This leads to two questions: How is this algorithm better/worse than misspecified bandit algos? What is the challenge in applying DS-LSVI to lin MDPs and what benefit do we get in that case?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "k84jm4M-tgt", "reviewer": "Reviewer_Btqn", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper studies the linear contextual bandits in the misspecified setting where the reward function can be approximated by a linear function class up to a misspeci\nfication level. In the case of the misspecification being smaller than the gap between the best and second best arm (delta) over the square root of the dimension, then they show an efficiently learning algorithm with a constant regret bound (better by a log(K) factor). Experiments are shown on both simulated and real-world settings comparing their proposed approach with a previous algorithm.", "summary_of_the_review": "Overall, an interesting data selection idea applied to both the linear contextual bandit and linear MDP in the misspecified settings with good regret guarantees. Some lingering questions remain and hope to discuss with the authors.", "strength_and_weaknesses": "Pros:\n   (A) Novel algorithm for data selection such that it learns from the uncertain data points to obtain a O(d^2/Delta) gap-dependent regret bound when the misspecification is small. Similarly, they show a matching lower bound for learnability for the corresponding low misspecification level and not efficiently learnable otherwise. Similar results are shown for the misspecified linear MDP settings to achieve a logarithmic regret bound.\n   (B) They show extensive experiments on both synthetic and real datasets. On the synthetic dataset, they show that their regret for their proposed algorithm DS-OFUL is better than the one from Lattimore et al. Additional experiments showcasing the performance benefits are shown in supplementary.\n\nCons:\n\n   (i) It is not clear how the threshold parameter is chosen in the algorithms? Does it not depend on the data and needs to be adaptively estimated and refined?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "i212DFulzrR", "reviewer": "Reviewer_vLag", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This work focuses on the misspecification setting for both linear contextual bandits and linear MDPs. \nFor the linear bandits, it proposes the DS-OFUL algorithm. It derives an upper bound accordingly and also a lower bound.\nFor the linear MDPs, it devises the DS-LSVI with a similar design and also provides un upper bound for it.\nIt also provides numerical results in the linear bandit setting.", "summary_of_the_review": "This work considers the misspecification setting in the bandits. It proposes and analyzes a novel algorithm: DS-OFUL. It also extends the design to the linear MDPs and analyzes the DS-LSVI algorithm. The work makes some contribution, which would be presented cleared if the weaknesses above can be improved.\n\n\n===============\n\n\nAfter rebuttal:\nThanks for the rebuttal. I actually wonder if the optimal hyper parameters can be found in a quick grid search in a more difficult instance. Besides, $\\Delta$ may not always be prior knowledge.\n\nI would like to keep the score.", "strength_and_weaknesses": "Strength:\n1. The work is well-organized and easy to follow.\n1. It is novel to discard data that brings little uncertainty to the model, which improves the robustness of the algorithm in the misspecified setting.\n1. It provides both a high-probability and an expected bound on the regret in the linear bandit setting.\n\nWeaknesses:\n1. The experiments in linear bandits are not so convincing. Firstly, why do the author(s) apply such a grid search for the parameters? The data shown in the work does not represent a \"uniform search\". Secondly, what is the theoretical explanation of the fact that the algorithm with $\\Gamma=0.08$ performs the best?\n1. As the algorithm is sensitive to the value of $\\Gamma$, how should the value of this parameter be selected?\n1. Is it possible to provide some numerical results for the linear MDPs?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "OZbnpmvttQ", "reviewer": "Reviewer_1suH", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper looks at a linear contextual bandit and linear MDP in a misspecified setting. They provide an algorithm called DS-OFU for these problems. They showed that an $O(d^2/\\Delta)$ regret is achievable if the $\\zeta$ is small.\n", "summary_of_the_review": "this paper is well-written and addresses an interesting problem. ", "strength_and_weaknesses": "1)Author motivates the subject from a theoretical and practical point of view. 2)In the introduction, the author reviewed the previous works carefully. 3)the author successfully addressed the issue and recommended the algorithms. 4)The authors successfully provide simulation results for their algorithm. 5)The proof is mathematically correct.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "KEAIfeH8kl", "reviewer": "Reviewer_Psq2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper studies the problem of regret minimization in misspecified linear contextual bandits. The proposed algorithm, named DS-OFUL, only learns the underlying parameter $\\theta^*$ from arm pulling with large uncertainty, which makes it robust to misspecification. When the misspecification level is relatively small, a gap-dependent upper bound is proved, which does not depend on the number of time rounds. In addition, the authors provide a gap-dependent lower bound for the problem studied. It is shown that the misspecified linear contextual bandit model can be efficiently learnable only when the misspecification level is lower than a threshold $\\tilde{\\mathcal{O}}(\\Delta / \\sqrt{d})$. Finally, the authors extend their ideas into misspecified linear MDP and a gap-dependent upper bound is also proved.", "summary_of_the_review": "This paper suggests an interplay between the misspecification level and the sub-optimality gap, which clearly tells when the misspecified linear contextual bandit model can be efficiently learnable. For the proposed algorithm, I believe a deeper understanding in general situations could be achieved. Overall, the contribution is technically sound and valuable though some issues need to be addressed (see the detailed comments above). Therefore, I vote for borderline.\n\n", "strength_and_weaknesses": "Strength:\n\n1. The idea of only using data with large uncertainty is well-motivated and novel. \n2. The upper bound (Theorem 5.1) indicates that when the minimal sub-optimality gap is known, a constant regret bound is possible in the well-specified linear contextual bandits, which is an interesting byproduct.\n3. This paper focuses on the gap-dependent bounds, which differs from the previous works that study gap-independent results.\n\n\n\nWeakness:\n\n1. For the proposed algorithm, its performance is only studied when the  misspecification level is small than $\\Delta/(2\\sqrt d \\iota_1)$,  which may be a very small number. Although the following lower bound shows that  a worst-case linear regret is unavoidable when misspecification level is relatively large, it is still important to study the performance of DS-OFUL in general situations.\n2. In the experiments, the authors only compare their algorithm with Lattimore et al. (2020). More methods from related works should be included.\n3. The definition of $\\beta$ in Theorem 5.1 is slightly different from that in Appendix C.\n\n\n\nMinor comments:\n\n1. Do you assume that the number of arms is finite in the lower bound part?\n2. A few full stops are missing. \n3. Sometimes $T$ rather than $K$ is used to denote the number of rounds, which is not consistent. Besides, in the literature of bandits, it is uncommon to use $K$ to denote the number of rounds.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject