We presented a novel reduction from stochastic contextual linear bandit problems to (fixed-context) linear bandit problems; our reduction explains why results, that are not achievable for adversarial contexts, are possible for stochastic contextual bandits, and offers a framework that can be leveraged to gain improved understanding and bounds for contextual linear bandit problems. We illustrate the power of our approach by applying it to achieve improved bounds over a number of cases; this is not an exhaustive list, and we hope that our approach will be a useful tool to researchers in this field.


Appendices
Proof of Theorem  REF
Theorem (Restatement of Theorem REF ) 
Let \(\Lambda \)  be any algorithm for linear bandits and \(I\)  be a contextual linear bandit instance with stochastic contexts, unknown parameter \(\theta _\star \)  and rewards \(r_t\)  generated as described in the reduction in Section REF . It holds that
\(\bullet \)  The reward \(r_t\)  is generated, by pulling the arm \(g(\theta _t)\) , from a linear bandit instance \(L\)  with action set \(\mathcal {X}\) , and unknown parameter \(\theta _\star \) .
\(\bullet \)  The reduction results in an algorithm \(\mathcal {M}\)  for contextual linear bandits such that with probability at least \(1-\delta \)  we have
\( |R_T^\mathcal {M}(I)-R_T^\Lambda (L)|\le c\sqrt{T\log (1/\delta )},\) 
where \(R^\Lambda _T(L)\)  is the regret of \(\Lambda \)  over the constructed linear bandit instance \(L\) , \(R_T^\mathcal {M}(I)\)  is the regret of algorithm \(\mathcal {M}\)  over the instance \(I\)  and \(c\)  is a universal constant.

Following the reduction described in the section, we start by showing that \(R_T^\Lambda (L)\) , the regret of the algorithm \(\Lambda \)  on a linear bandit instance, is at most \(\tilde{O}(\sqrt{T})\)  away from \(R_T^\mathcal {M}(I)\)  with high probability.
Recall that the regret \(R_T^\Lambda (L)\)  is defined as
\(R_T^\Lambda (L) = \sum _{t=1}^T \max _{\theta \in \Theta } {\langle g(\theta ),\theta _\star  \rangle } - {\langle g(\theta _t), \theta _\star  \rangle }.\) 
We notice that the function \(g\)  depends on the context distribution \(\mathcal {D}\) . In the following we assume for simplicity that for each \(\theta \in \Theta \) , there is a unique \(a_t\in \mathcal {A}_t\)  that satisfies \({\langle a_t,\theta  \rangle }=\sup _{a\in \mathcal {A}_t}{\langle a,\theta  \rangle }\)  almost surely. We discuss how to remove this assumption at the end of the proof.
The regret \(R_T^\mathcal {M}(I)\)  of the contextual algorithm can be decomposed as
\(R_T^\mathcal {M}(I)&= \sum _{t=1}^T {\langle \arg \max _{a\in \mathcal {A}_t} {\langle a,\theta _\star  \rangle },\theta _\star  \rangle } - {\langle \arg \max _{a\in \mathcal {A}_t} {\langle a,\theta _t \rangle },\theta _\star  \rangle } \nonumber \\&= \sum _{t=1}^T {\langle \arg \max _{a\in \mathcal {A}_t} {\langle a,\theta _\star  \rangle },\theta _\star  \rangle } - {\langle  \mathbb {E}[\arg \max _{a\in \mathcal {A}_t} {\langle a,\theta _\star  \rangle }],\theta _\star  \rangle } \nonumber \\&\qquad +{\langle  \mathbb {E}[\arg \max _{a\in \mathcal {A}_t} {\langle a,\theta _t \rangle }|\theta _t],\theta _\star  \rangle } - {\langle \arg \max _{a\in \mathcal {A}_t} {\langle a,\theta _t \rangle },\theta _\star  \rangle } \nonumber \\&\qquad +{\langle  \mathbb {E}[\arg \max _{a\in \mathcal {A}_t} {\langle a,\theta _\star  \rangle }],\theta _\star  \rangle } - {\langle  \mathbb {E}[\arg \max _{a\in \mathcal {A}_t} {\langle a,\theta _t \rangle }|\theta _t],\theta _\star  \rangle }\nonumber \\&= \sum _{t=1}^T {\langle \arg \max _{a\in \mathcal {A}_t} {\langle a,\theta _\star  \rangle },\theta _\star  \rangle } - \mathbb {E}[{\langle \arg \max _{a\in \mathcal {A}_t} {\langle a,\theta _\star  \rangle },\theta _\star  \rangle }] \nonumber \\&\qquad +\mathbb {E}[{\langle \arg \max _{a\in \mathcal {A}_t} {\langle a,\theta _t \rangle },\theta _\star  \rangle }|\theta _t] - {\langle \arg \max _{a\in \mathcal {A}_t} {\langle a,\theta _t \rangle },\theta _\star  \rangle } \nonumber \\&\qquad +{\langle g(\theta _\star ),\theta _\star  \rangle } - {\langle g(\theta _t),\theta _\star  \rangle },\) 

where the expectation is with respect to the randomness in the context generation \(\mathcal {A}_t\) . In the following we will first show that \({\langle g(\theta _\star ),\theta _\star  \rangle }=\max _{\theta \in \Theta ^{\prime }} {\langle g(\theta ),\theta _\star  \rangle }\) .
Indeed,we observe that \(\forall \theta ^{\prime }, \theta ^{\prime \prime }\in \Theta \)  we have
\(\max _{\theta \in \Theta }{\langle g(\theta ),\theta ^{\prime } \rangle }\ge {\langle g(\theta ^{\prime }),\theta ^{\prime } \rangle } &= \mathbb {E}[\max _{a\in \mathcal {A}_t} {\langle a,\theta ^{\prime } \rangle }]\nonumber \\&\ge \mathbb {E}[{\langle \arg \max _{a\in \mathcal {A}_t} {\langle a,\theta ^{\prime \prime } \rangle },\theta ^{\prime } \rangle }] = {\langle g(\theta ^{\prime \prime }),\theta ^{\prime } \rangle }.\) 

The above inequalities have to be met with equality since we can select
\(\theta ^{\prime \prime }=\arg \max _{\theta \in \Theta }{\langle g(\theta ),\theta ^{\prime } \rangle }\)  making the first and last terms equal.
Hence, we have proved that
\({\langle g(\theta ^{\prime }),\theta ^{\prime } \rangle }=\max _{\theta \in \Theta } {\langle g(\theta ),\theta ^{\prime } \rangle }, \quad \forall \; \theta ^{\prime }\in \Theta .\) 
Substituting in the last line of (REF ) using the triangle inequality, we get that
\(|R_T^\mathcal {M}(I)-R_T^\Lambda (L)|&\stackrel{(i)}{=} |\sum _{t=1}^T {\langle \arg \max _{a\in \mathcal {A}_t} {\langle a,\theta _\star  \rangle },\theta _\star  \rangle } - \mathbb {E}[{\langle \arg \max _{a\in \mathcal {A}_t} {\langle a,\theta _\star  \rangle },\theta _\star  \rangle }] \nonumber \\&\qquad +\mathbb {E}[{\langle \arg \max _{a\in \mathcal {A}_t} {\langle a,\theta _t \rangle },\theta _\star  \rangle }|\theta _t] - {\langle \arg \max _{a\in \mathcal {A}_t} {\langle a,\theta _t \rangle },\theta _\star  \rangle }| \nonumber \\&\le |\sum _{t=1}^T {\langle \arg \max _{a\in \mathcal {A}_t} {\langle a,\theta _\star  \rangle },\theta _\star  \rangle } - \mathbb {E}[{\langle \arg \max _{a\in \mathcal {A}_t} {\langle a,\theta _\star  \rangle },\theta _\star  \rangle }]| \nonumber \\&\qquad +|\sum _{t=1}^T\mathbb {E}[{\langle \arg \max _{a\in \mathcal {A}_t} {\langle a,\theta _t \rangle },\theta _\star  \rangle }|\theta _t] - {\langle \arg \max _{a\in \mathcal {A}_t} {\langle a,\theta _t \rangle },\theta _\star  \rangle }|,\) 

where \((i)\)  follows by definition of \(R_T^\Lambda (L)\)  and (REF ).
We next bound the quantity
\(\Sigma _T := \sum _{t=1}^T \mathbb {E}[{\langle \arg \max _{a\in \mathcal {A}_t} {\langle a,\theta _t \rangle },\theta _\star  \rangle }|\theta _t] - {\langle \arg \max _{a\in \mathcal {A}_t} {\langle a,\theta _t \rangle },\theta _\star  \rangle }.\) 
Let \(\mathcal {F}^{\prime }_t=\sigma \lbrace \theta _1,r_1,...,\theta _t\rbrace \)  be the filtration of all historic information of the linear bandit problem up to time \(t\) . we notice that
\(\mathbb {E}[\Sigma _t|\mathcal {F}^{\prime }_t]&=\mathbb {E}[\Sigma _{t-1}|\mathcal {F}^{\prime }_t]+\mathbb {E}[\mathbb {E}[{\langle \arg \max _{a\in \mathcal {A}_t} {\langle a,\theta _t \rangle },\theta _\star  \rangle }|\theta _t]|\mathcal {H}^{\prime }_t] - \mathbb {E}[{\langle \arg \max _{a\in \mathcal {A}_t} {\langle a,\theta _t \rangle },\theta _\star  \rangle }|\mathcal {F}^{\prime }_t]\nonumber \\&=\Sigma _{t-1}.\) 

Hence, \(\Sigma _{t}\)  is a martingale with a bounded difference (by boundedness of \(\Theta , \mathcal {A}_t\) ). By Azuma–Hoeffding inequality [1]}, we have that \(|\Sigma _T|\le c\sqrt{T\log 1/\delta }\)  with probability at least \(1-\frac{1}{2\delta }\) . For completeness, we state a special case of the Azuma-Hoeffding inequality at the end of our proof. The summation \(\Sigma ^{\prime }_T=\sum _{t=1}^T {\langle \arg \max _{a\in \mathcal {A}_t} {\langle a,\theta _\star  \rangle },\theta _\star  \rangle } - \mathbb {E}[{\langle \arg \max _{a\in \mathcal {A}_t} {\langle a,\theta _\star  \rangle },\theta _\star  \rangle }]\)  can be bounded similarly. Hence, by (REF ), we have that with probability at least \(1-\delta \)
\(|R_T^\mathcal {M}(I)-R_T^\Lambda (L)|\le c \sqrt{T\log 1/\delta }.\) 
We have shown that the regret of Algorithm REF  over the instance \(I\)  is \(O(\sqrt{T\log 1/\delta })\)  away from \(R_T^\Lambda (L)\)  with probability at least \(1-\delta \) . It remains to show that the rewards \(r_t\)  generated by the described interaction with the instance \(I\) , are generated from \(L\)  by the interaction of algorithm \(\Lambda \) .
Proposition 1 
The reward \(r_t\)  can be rewritten as
\(r_t = {\langle g(\theta _t),\theta _\star  \rangle }+\eta ^{\prime }_t,\) 
where \(\mathbb {E}[\eta ^{\prime }_t|\mathcal {F}^{\prime }_t]=0, \mathbb {E}[\exp (\lambda \eta ^{\prime }_t)|\mathcal {F}^{\prime }_t]\le \exp (2\lambda ^2) \quad \forall \lambda \in \mathbb {R}\) , and where \(\mathcal {F}^{\prime }_t=\sigma \lbrace \theta _1, r_1,..., \theta _t\rbrace \)  is the filtration of historic information up to time \(t\) .

We have that
\(r_t&={\langle a_t,\theta _\star  \rangle } + \eta _t = {\langle \arg \max _{b\in \mathcal {A}_t} {\langle b,\theta _t \rangle }, \theta _\star  \rangle } +\eta _t\nonumber \\&= {\langle g(\theta _t),\theta _\star  \rangle } + \left(\eta _t+ {\langle \arg \max _{b\in \mathcal {A}_t} {\langle b,\theta _t \rangle }, \theta _\star  \rangle } - {\langle g(\theta _t),\theta _\star  \rangle }\right).\) 

We let \(\eta ^{\prime }_t=\eta _t+ {\langle \arg \max _{b\in \mathcal {A}_t} {\langle b,\theta _t \rangle }, \theta _\star  \rangle } - {\langle g(\theta _t),\theta _\star  \rangle }\) . The proof that \(\mathbb {E}[\eta ^{\prime }_t|\mathcal {F}_t]=0\)  follows similarly to (REF )
\(\mathbb {E}[\eta _t^{\prime }|\mathcal {F}_t] &= \mathbb {E}[\eta _t|\mathcal {F}_t]+\mathbb {E}[{\langle \arg \max _{b\in \mathcal {A}_t} {\langle b,\theta _t \rangle }, \theta _\star  \rangle } - {\langle g(\theta _t),\theta _\star  \rangle }|\mathcal {F}_t]\nonumber \\&=\mathbb {E}[{\langle \arg \max _{b\in \mathcal {A}_t} {\langle b,\theta _t \rangle }, \theta _\star  \rangle } - {\langle g(\theta _t),\theta _\star  \rangle }|\theta _t] = 0.\) 

Lastly, \(\mathbb {E}[\exp (\lambda \eta ^{\prime }_t)|\mathcal {F}_t]\le \exp (2\lambda ^2) \forall \lambda \in \mathbb {R}\)  follows by boundedness of \(\eta ^{\prime }_t\)  which follows by boundedness of \(\eta _t, \Theta , \mathcal {A}_t\) .

This concludes the proof.
Lemma 1 [Azuma's Inequality [1]}]
Let \(\Sigma _0, \Sigma _1,...\)  be a martingale with respect to filtration \(\mathcal {F}_0,\mathcal {F}_1,...\)  such that \(|\Sigma _i-\Sigma _{i-1}|\le c\)  almost surely. Then for all \(\epsilon >0\) , we have that
\(\mathbb {P}[|\Sigma _n-\Sigma _0|>\epsilon ]\le 2\exp (-\frac{\epsilon ^2}{2nc^2}).\) 


When \(\sup _{a\in \mathcal {A}_t}{\langle a,\theta  \rangle }\)  is not Unique
One solution is to choose \(a_t\)  as any action \({\langle a_t,\theta  \rangle }\ge \sup _{a\in \mathcal {A}_t}{\langle a,\theta  \rangle }-\delta \)  for some \(\delta >0\) . The error arising from performing this step can be controlled by \(\delta \) , e.g., by setting \(\delta = \exp (-T)\) . Our proofs will follow by choosing \(a_t\)  as described above, using any deterministic or random choice function, as long as the action \(a_t\)  is measurable.

Proof of Theorem  REF
Theorem (Restatement of Theorem REF ) 
Let \(\Lambda _\epsilon \)  be an algorithm for linear bandits with \(\epsilon \)  misspecification and \(I\)  be a contextual linear bandit instance with stochastic contexts, unknown parameter \(\theta _\star \)  and rewards \(r_t\)  are generated as described in Algorithm REF . The following holds:
\(\bullet \)  Conditioned on \(\mathcal {H}_{t^{(m)}}=\sigma (\mathcal {A}_1,a_1,r_1,...,\mathcal {A}_{t^{(m)}},a_{t^{(m)}},r_{t^{(m)}})\) : in epoch \(m\) , the rewards \(r_t\)  are generated, by pulling arm \(g^{(m)}(\theta _t)\) , from a misspecified linear bandit instance \(L_m\)  for \(t=t^{(m)}+1,...,t^{(m+1)}\) , action set \(\mathcal {X}_m=\lbrace g^{(m)}(\theta )|\theta \in \Theta ^{\prime }\rbrace \) , unknown parameter \(\theta _\star \) , mean rewards \({\langle g(\theta ),\theta _\star  \rangle }\) , and unknown misspecification \(\epsilon ^{\prime }_m\) .
\(\bullet \)  The misspecification \(\epsilon ^{\prime }_m\)  is bounded by the known quantity \(\epsilon _m\)  with probability at least \(1-c\delta /M\) .
\(\bullet \)  With probability at least \(1-\delta \)  we have that \(|R_T(I)-\sum _{m=1}^MR^{\Lambda _{\epsilon _m}}_{T_m}(L_m)|\le c\sqrt{T\log (1/\delta )}\) , where \(R_T(I)\)  is the regret of Algorithm REF  over the instance \(I\) , \(R^{\Lambda _{\epsilon _m}}_{T_m}(L_m)\)  is the regret of algorithm \(\Lambda _{\epsilon _m}\)  over the bandit instance \(L_m\)  in phase \(m\) , \(T_m=t^{(m+1)}-t^{(m)}\) , and \(c\)  is a universal constant.

Let \(L_m\)  be a bandit instance with actions \(\mathcal {X}_m={\langle g^{(m)}(\theta )|\theta \in \Theta ^{\prime } \rangle }\)  indexed by the set \(\Theta ^{\prime }\) , mean rewards \({\langle g(\theta ),\theta _\star  \rangle }\forall \theta \in \Theta ^{\prime }\) , and \(t\in \lbrace t^{(m)}+1,...,t^{(m+1)}\rbrace \) . Let
\(\mathcal {H}_{t^{(m)}}=\sigma \lbrace \mathcal {A}_1,a_1,r_1,...,\mathcal {A}_{t^{(m)}},a_{t^{(m)}},r_{t^{(m)}}\rbrace \) 
be the filtration of all historic information before epoch \(m\) . Note that \(g^{(m)}\)  is defined in line 7 of Algorithm REF  and is the empirical estimate of \(g\)  using history \(\mathcal {H}_{t^{(m)}}\) , hence, \(g^{(m)}\)  is \(\mathcal {H}_{t^{(m)}}\) -predictable. Conditioned on \(\mathcal {H}_{t^{(m)}}\) , we have that \(L_m\)  is a misspecified linear bandit instance with misspecification, \(\epsilon _m^{\prime }=\sup _{\theta \in \Theta ^{\prime }}{\langle g(\theta )-g^{(m)}(\theta ),\theta _\star  \rangle }\) . And the regret of the algorithm \(\Lambda _{\epsilon _m}\)  over \(L_m\)  is the random quantity
\(R^{\Lambda _{\epsilon _m}}_{T_m}(L_m):=\sum _{t=t^{(m)}+1}^{t^{(m+1)}} {\langle g(\theta ),\theta _\star  \rangle } - {\langle g(\theta _t), \theta _\star  \rangle }.\) 
As we have shown in Proposition REF , conditioned on \(\mathcal {H}_{t^{(m)}}\) , \(r_t\)  is generated from \(L_m\)  by pulling arm \(\theta _t\) .
Define the event \(\mathcal {E}_m=\lbrace \epsilon ^{\prime }_m> \epsilon _m\rbrace \)  be the bad event that the random quantity \(\epsilon ^{\prime }_m\)  is greater than \(\epsilon _m\)  defined in Algorithm REF . We will show in Proposition REF  that \(\sum _{m=1}^M\mathbb {P}[\mathcal {E}_m]\le \delta \) .
We next bound the regret of Algorithm REF  in terms of the random quantities \(\lbrace R^{\Lambda _{\epsilon _m}}_{T_m}(L_m)\rbrace _{m=1}^M\) . By choosing \(\delta \)  sufficiently small, it it will be enough to bound \(R^{\Lambda _{\epsilon _m}}_{T_m}(L_m)\)  conditioned on \(\mathcal {H}_{t^{(m)}}\)  and the good event \(\mathcal {G}_m=\lbrace \epsilon ^{\prime }_m\le \epsilon _m\rbrace \) . Let us define the random quantity \(R^{\Lambda _\epsilon }_T(L_\epsilon )=\sum _{m=1}^MR^{\Lambda _{\epsilon _m}}_{T_m}(L_m)\) .
We show that \(R^{\Lambda _\epsilon }_T(L_\epsilon )\)  is at most \(\tilde{O}(\sqrt{T})\)  away from \(R_T^\mathcal {M}\)  with high probability. By definition of \(R^{\Lambda _{\epsilon _m}}_{T_m}(L_m)\)  we have that
\(R^{\Lambda _\epsilon }_T(L_\epsilon ) = \sum _{t=1}^T \max _{\theta \in \Theta ^{\prime }} {\langle g(\theta ),\theta _\star  \rangle } - {\langle g(\theta _t), \theta _\star  \rangle }.\) 
As in the proof of Theorem REF , we assume for simplicity that for each \(\theta \in \Theta \) , there is a unique \(a_t\in \mathcal {A}_t\)  that satisfies \({\langle a_t,\theta  \rangle }=\sup _{a\in \mathcal {A}_t}{\langle a,\theta  \rangle }\)  almost surely. This can be relaxed in the same way as in Theorem REF .
Recall that \(L\)  is the linear bandit instance in Theorem REF  with access to the function \(g\) , and actions in \(\mathcal {X}=\lbrace g(\theta )|\theta \in \Theta \rbrace \) . The regret \(R^\mathcal {M}_T(I)\)  of the contextual algorithm can be bounded as
\(R_T^\mathcal {M}(I)&\le |R_T^\mathcal {M}(I)-R_T^\Lambda (L)|+|R_T^\Lambda (L)-R^{\Lambda _\epsilon }_T(L_\epsilon )|,\) 

where \(R_T^\Lambda (L)\)  is defined as follows
\(R_T^\Lambda (L) = \sum _{t=1}^T \max _{\theta \in \Theta } {\langle g(\theta ),\theta _\star  \rangle } - {\langle g(\theta _t), \theta _\star  \rangle },\) 
and \(\lbrace \theta _t\rbrace \)  are the actions played by \(\lbrace \Lambda _{\epsilon _m}\rbrace \) .
The first term in (REF ) is bounded in Theorem REF . In the following, we focus on bounding \(|R_T^\Lambda (L)-R^{\Lambda _\epsilon }_T(L_\epsilon )|\) . To that end, we first show that
\(|{\langle g(\theta _\star ),\theta _\star  \rangle }-\max _{\theta \in \Theta ^{\prime }} {\langle g(\theta ),\theta _\star  \rangle }|\le 2/T.\) 
We recall from (REF ) that
\({\langle g(\theta ^{\prime }),\theta ^{\prime } \rangle }=\max _{\theta \in \Theta } {\langle g(\theta ),\theta ^{\prime } \rangle }, \quad \forall \; \theta ^{\prime }\in \Theta .\) 
From \(1/T\) -net properties, we also have that there exists \(\phi \in \Theta ^{\prime }\)  such that \(\Vert \theta _\star -\phi \Vert _2\le 1/T\) . Hence,
\(\max _{\theta \in \Theta ^{\prime }} {\langle g(\theta ),\theta _\star  \rangle } &\stackrel{(i)}{\le } \max _{\theta \in \Theta } {\langle g(\theta ),\theta _\star  \rangle }\stackrel{(ii)}{=}{\langle g(\theta _\star ),\theta _\star  \rangle }\nonumber \\&\stackrel{(iii)}{\le } {\langle g(\theta _\star ),\phi  \rangle }+1/T\nonumber \\&\le \max _{\theta \in \Theta } {\langle g(\theta ),\phi  \rangle }+1/T\nonumber \\&\stackrel{(iv)}{=} {\langle g(\phi ),\phi  \rangle }+1/T \stackrel{(v)}{\le } {\langle g(\phi ),\theta _\star  \rangle }+2/T \nonumber \\&\stackrel{(vi)}{\le } \max _{\theta \in \Theta ^{\prime }} {\langle g(\theta ),\theta _\star  \rangle }+2/T,\) 

where \((i)\)  follows from \(\Theta ^{\prime }\subseteq \Theta \) , \((ii)\)  follows from (REF ), \((iii)\)  follows from \({\langle g(\theta _\star ),\theta _\star -\phi  \rangle }\le \Vert g(\theta _\star )\Vert _2\Vert \theta _\star -\phi \Vert _2\le 1/T\) , \((iv)\)  follows from (REF ), \((v)\)  follows as in \((iii)\) , and \((vi)\)  follows from \(\phi \in \Theta ^{\prime }\) . Eq. (REF ) follows. Note that in this part it is important to have \(\Theta ^{\prime }\subseteq \Theta \) .
As a result \(|R_T^\Lambda (L)-R^{\Lambda _\epsilon }_T(L_\epsilon )|\)  can be bounded as
\(|R_T^\Lambda (L)-R^{\Lambda _\epsilon }_T(L_\epsilon )|&= |\sum _{t=1}^T \max _{\theta \in \Theta ^{\prime }}{\langle g(\theta ),\theta _\star  \rangle } - \max _{\theta \in \Theta }{\langle g(\theta ),\theta _\star  \rangle }|\nonumber \\&\le \sum _{t=1}^T |\max _{\theta \in \Theta ^{\prime }}{\langle g(\theta ),\theta _\star  \rangle } - \max _{\theta \in \Theta }{\langle g(\theta ),\theta _\star  \rangle }|\stackrel{(i)}{\le } 2,\) 

where \((i)\)  follows uses (REF ) and (REF ).
Hence, by (REF ), Theorem REF , (REF ) and union bound, we have that with probability at least \(1-\delta \)
\(|R^\mathcal {M}_T(I)-R^{\Lambda _\epsilon }_T(L_\epsilon )|\le c \sqrt{T\log 1/\delta }.\) 
Since \(R^{\Lambda _\epsilon }_T(L_\epsilon )=\sum _{m=1}^MR^{\Lambda _{\epsilon _m}}_{T_m}(L_m)\) , we have proved the second part of the theorem. It remains to show that in each epoch \(m\)  the rewards \(r_t\)  are generated from the for linear bandit instance \(L_m\)  and to bound the amount of misspecification. By Proposition REF , it suffices to show the following.
Proposition 2 
For each \(m\in [M]\) , we have that with probability at least \(1-\delta /M\)  it holds that
\(|{\langle g(\theta ),\theta ^{\prime } \rangle }-{\langle g^{(m)}(\theta ),\theta ^{\prime } \rangle }|\le 2\sqrt{\frac{\log (2M|\Theta ^{\prime }|/\delta )}{t^{(m)}}} \forall \theta \in \Theta ^{\prime }, \theta ^{\prime } \in \Theta .\) 


Since for a fixed \(\theta ^{\prime }\)  we have that \({\langle \arg \max _{a\in \mathcal {A}_t}{\langle a,\theta  \rangle },\theta ^{\prime } \rangle }\)  is \(1/4\) -subgaussian with mean \({\langle g(\theta ),\theta ^{\prime } \rangle }\) , we have that with probability at least \(1-\frac{\delta }{M|\Theta ^{\prime }|^2}\)  it holds that
\(|{\langle g(\theta ),\theta ^{\prime } \rangle }-{\langle g^{(m)}(\theta ),\theta ^{\prime } \rangle }|&=|{\langle g(\theta ),\theta ^{\prime } \rangle }-\frac{1}{t^{(m+1)}}\sum _{t=1}^{t^{(m+1)}}{\langle \arg \max _{a\in \mathcal {A}_t}{\langle a,\theta  \rangle },\theta ^{\prime } \rangle }|\nonumber \\&\le 2\sqrt{\frac{\log (2M|\Theta ^{\prime }|/\delta )}{t^{(m)}}}.\) 

By the union bound, the following holds with probability at least \(1-\delta /M\)
\(|{\langle g(\theta ),\theta ^{\prime } \rangle }-{\langle g^{(m)}(\theta ),\theta ^{\prime } \rangle }|\le 2\sqrt{\frac{\log (2M|\Theta ^{\prime }|/\delta )}{t^{(m)}}} \forall \theta , \theta ^{\prime } \in \Theta ^{\prime }.\) 
Let us pick arbitrary \(\theta \in \Theta ^{\prime }, \theta ^{\prime } \in \Theta \) . We have that there is \(\phi ^{\prime }\in \Theta ^{\prime }\)  such that \(\Vert \theta ^{\prime }-\phi ^{\prime }\Vert _2\le 1/T\) .
Hence, by Cauchy-Schwartz and the triangle inequality, we have that the following holds with probability at least \(1-\delta /M\)
\(|{\langle g(\theta ),\theta ^{\prime } \rangle }-{\langle g^{(m)}(\theta ),\theta ^{\prime } \rangle }|\le |{\langle g(\theta ),\phi ^{\prime } \rangle }-{\langle g^{(m)}(\theta ),\phi ^{\prime } \rangle }|+\frac{2}{T}\le 2\sqrt{\frac{\log (2M|\Theta ^{\prime }|/\delta )}{t^{(m)}}}+\frac{2}{T} \forall \theta \in \Theta ^{\prime }, \theta ^{\prime } \in \Theta .\) 

This concludes the proof.
