# Time-Varying Preference Bandits for Robot Behavior Personalization
## Appendix A Proof of Theorem 1  
Proof.: The proof techniques are basically similar to [12; 17], but the definition of \(V_{t}\) is different, and hence the proof of [12; 17] is not directly applicable. Let us decompose the upper bound into three terms. First, let us define the gradient of (5) as \(g_{t-1}(\theta):=\sum_{s=1}^{t-1}\gamma^{t-1-s}\mu\left(X_{s}^{\intercal} \theta\right)X_{s}+\lambda\theta\). Then, \(g_{t-1}(\hat{\theta}_{t})=\sum_{s=1}^{t-1}\gamma^{t-1-s}X_{s}R_{s}\) holds due to the update rule of \(\hat{\theta}_{t}\). We define the Jacobian of \(g_{t-1}\) as \(J_{t-1}(\theta):=\sum_{s=1}^{t-1}\gamma^{t-1-s}\hat{\mu}\left(X_{s}^{\intercal }\theta\right)X_{s}X_{s}^{\intercal}+\lambda I_{d}\). From the fundamental theorem of calculus, we have,  
\[G_{t-1}(\theta_{t}^{*},\theta) :=\int_{0}^{1}J_{t-1}(x\theta_{t}^{*}+(1-x)\theta)dx \tag{1}\] \[g_{t-1}(\theta_{t}^{*})-g_{t-1}(\theta) =G_{t-1}(\theta_{t}^{*},\theta)(\theta_{t}^{*}-\theta) \tag{2}\]  
where \(c_{\mu}V_{t}\leq G_{t-1}(\theta_{t}^{*},\theta)\). By using these facts, we can decompose the bound into three terms as follows,\[\|\hat{\theta}_{t}-\theta_{t}^{*}\|_{V_{t}}=\left\|G_{t-1}(\theta_{t}^ {*},\theta)^{-1}\big{(}g_{t-1}(\theta_{t}^{*})-g_{t-1}(\hat{\theta}_{t})\big{)} \right\|_{V_{t}} \tag{11}\] \[\leq \left\|\frac{1}{c_{\mu}}V_{t}^{-1}\big{(}g_{t-1}(\theta_{t}^{*})-g _{t-1}(\hat{\theta}_{t})\big{)}\right\|_{V_{t}}\] (12) \[\leq \frac{1}{c_{\mu}}\left\|\sum_{s=1}^{t-1}\gamma^{t-1-s}\big{(}\mu \big{(}X_{s}^{\intercal}\theta_{t}^{*}\big{)}-R_{s}\big{)}X_{s}\right\|_{V_{t}^ {-1}}+\frac{\left\|\lambda\theta_{t}^{*}\right\|_{V_{t}^{-1}}}{c_{\mu}}\] (13) \[\leq \frac{1}{c_{\mu}}\left\|\sum_{s=1}^{t-N(\gamma)-1}\gamma^{t-1-s} \big{(}\mu\big{(}X_{s}^{\intercal}\theta_{t}^{*}\big{)}-\mu\big{(}X_{s}^{ \intercal}\theta_{s}^{*}\big{)}\big{)}X_{s}\right\|_{V_{t}^{-1}}\] \[+\frac{1}{c_{\mu}}\left\|\sum_{s=1}^{t-1}\gamma^{t-1-s}\eta_{s}X _{s}\right\|_{V_{t}^{-1}}+\frac{\sqrt{\lambda}S}{c_{\mu}}\leq\alpha_{t} \tag{14}\]  
where \(\eta_{s}:=\mu(X_{s}^{\intercal}\theta_{t}^{*})-R_{s}\) and the last inequality holds due to the definition of \(\mathcal{T}(\gamma)\). Each term will be bounded by Lemma A1 and Lemma A2, and then \(\alpha_{t}\) is obtained.  
Lemma A1 (Proposition 2 in [17]).: _Consider a random variable, \(B_{t}:=\sum_{s=1}^{t-N(\gamma)-1}\gamma^{t-1-s}\)\((\mu\big{(}X_{s}^{\intercal}\theta_{t}^{*}\big{)}-\mu\big{(}X_{s}^{ \intercal}\theta_{s}^{*}\big{)})X_{s}\). For all \(t\in\mathcal{T}(\gamma)\), the following bound holds_  
\[\left\|B_{t}\right\|_{V_{t}^{-1}}\leq 2 SD^{2}/\sqrt{\lambda}\cdot\gamma^{N( \gamma)}\,/(1-\gamma). \tag{15}\]  
Lemma A2.: _Let \(S_{t-1}\) be \(\sum_{s=1}^{t-1}\gamma^{t-1-s}\eta_{s}X_{s}\). The following deviation inequality holds with probability at most \(\delta\)_  
\[\exists t\geq 0,\left\|S_{t-1}\right\|_{V_{t}^{-1}}\geq\sqrt{2\ln(1/ \delta)+\ln(\det(V_{t}/\lambda))} \tag{16}\]  
Proof Sketch.: The proof can be achieved by following the same procedure in [12] for \(V_{t}\). Note that the results in [12] cannot be directly applied to our case since the definition of \(V_{t}\) is different from [12], but it can be done similarly to [12].