In this section, we prove prop:conbandits by applying the black box reduction of [1]} to our prop:kpieceregression. The key lemma is as follows:
[!t]
[1]
Init: \(A\)  instances of the Piecewise Regressor (alg:generalreg) \(\mathbf {\mathsf {regressor}}(a)\)  for \(a \in \mathcal {A}\) , learning rate \(\gamma > 0\) , exploration parameter \(\mu > 0\) .
each time \(t= 1,2,\dots \) 
recieve  \(x_t\) 
each action \(a \in \mathcal {A}\) 
 predict \(\hat{y}_t(a) = \mathbf {\mathsf {regressor}}(a)\mathbf {\mathsf {.predict}}(x_t)\)  blue!70!black% Prediction step of alg:generalreg
Assign \(b_t \leftarrow \operatornamewithlimits{argmin}_{a \in \mathcal {A}} \hat{y}_t(a)\) 
each \(a \ne b_t\) 
 Assign
\(p_{t,a} \leftarrow \frac{1}{\mu + \gamma (\hat{y}_t(a) - \hat{y}_t(b_t))} \) 
