# Time-Varying Preference Bandits for Robot Behavior Personalization
## 5 Theoretical Analysis  
In this section, we analyze the cumulative regret of the proposed method. The cumulative regret is defined as  
\[\mathcal{R}_{T}:=\sum_{t=1}^{T}\mu(|(X_{t}^{*})^{\intercal}\theta_{t}^{*}|)- \mu(|X_{t}^{\intercal}\theta_{t}^{*}|), \tag{6}\]  
where \(\mu(x)\) is a logistic function, i.e., \(\mu(x):=(1+e^{-x})^{-1}\), \(X_{t}^{*}:=\operatorname*{arg\,max}_{X\in\mathcal{X}}\mu(|X^{\intercal}\theta _{t}^{*}|)\), and \(T\) is the number of iterations. \(X_{t}^{*}\) indicates the optimal query that contains the optimal trajectory such that \(\max_{\xi}\Phi(\xi)^{\intercal}\theta_{t}^{*}\). The cumulative regret is widely employed in bandit settings as a measure to assess the efficiency of exploration methods [13]. Then, we prove that our method has the sub-linear regret under the mild assumption on \(\theta_{t}^{*}\). In other words, our theoretical results tell us that the proposed method efficiently adapts to the time-varying parameters. First, we introduce the assumptions. **Assumption 1**. : _For \(\forall t\), \(\forall X\in\mathcal{X}\), and \(\forall\theta_{t}^{*}\), there exist \(D\) and \(S\) such that \(\|X\|_{2}\leq D\) holds and \(\|\theta_{t}^{*}\|_{2}\leq S\) holds._  
**Assumption 2**. : _Let \(B_{T}\) be the number of changing points. Assume that \(\theta_{t}^{*}\) is changed up to \(B_{T}\) times during \(T\) rounds._  
Initially, we make Assumption 1 that both feature vectors and the parameters are bounded. Assumption 2 tells us that the user parameter is changed discretely \(B_{T}\) times. Note that \(B_{T}=T\) indicates the most volatile user, and \(B_{T}=0\) indicates a stationary user. Furthermore, we define the lower bound of the derivative of the logistic function. **Definition 1**. : _For the logistic function \(\mu\), there exists a positive constant \(c_{\mu}\) such that \(c_{\mu}:=\inf_{\|\theta\|_{2}\leq S,\|x\|_{2}\leq D}\hat{\mu}(x^{\intercal} \theta)>0\). Note that \(c_{\mu}\) always exists for bounded \(\theta\) and \(x\)._  
Now, the set of time indices used for analysis is defined. **Definition 2**. : _For fixed \(\gamma\), let us define \(N(\gamma):=\lceil\ln(1/(1-\gamma))/(1-\gamma)\rceil\) and define an index set as \(\mathcal{T}(\gamma):=\{t\in\mathbb{N}|t\leq T\text{ and }\theta_{s}^{*}=\theta_{t}^{*}\text{ holds for }\forall s\in(t-N(\gamma),t]\}\)._  
For \(t\) in \(\mathcal{T}(\gamma)\), we can find the interval \([t-N(\gamma),t]\) where \(\theta_{s}^{*}\) does not change. In other words, \(\theta_{s}^{*}\) is fixed for \(N(\gamma)\) rounds. Then, we prove that the proposed method can adapt \(\theta_{s}^{*}\) in at least \(N(\gamma)\) rounds and, hence, the proposed method is no regret. Now, we first derive the confidence bound of the estimated parameter \(\hat{\theta}_{t}\) as follows. **Theorem 1**. : _Suppose that Assumptions 1-2 hold. Consider the gap between \(\hat{\theta}_{t}\) and \(\theta_{t}^{*}\). For all \(t\in\mathcal{T}(\gamma)\), the following inequality holds with probability at least \(1-\delta\),_  
\[\big{|}X^{\intercal}(\hat{\theta}_{t}-\theta_{t}^{*})\big{|}\leq\|\hat{ \theta}_{t}-\theta_{t}^{*}\|_{V_{t}}\|X\|_{V_{t}^{-1}}\leq\alpha_{t}\|X\|_{V_{ t}^{-1}} \tag{7}\]  
_where \(\alpha_{t}:=\frac{1}{c_{\pi}}\sqrt{2\ln\left(\frac{1}{\delta}\right)+d\ln \left(1+\frac{D^{2}(1-\gamma^{t})}{d\lambda(1-\gamma)}\right)}+\frac{\sqrt{ \lambda}S}{c_{\pi}}+\frac{SD^{2}\gamma^{N(\gamma)}}{c_{\pi}\sqrt{\lambda}(1- \gamma)}\)._  
\(\alpha_{t}\) is used to compute the confidence bound of the estimated parameter. By using Theorem 1, we can derive the regret bound of the proposed DPB. The detailed proofs of Theorem 1 can be found in Appendix A. **Theorem 2**. : _Suppose that Assumptions 1-2 hold; then, for fixed \(\delta\in(0,1)\), with probability at least \(1-\delta\), the regret of DPB is bounded as follows: \(\mathcal{R}_{\mathcal{T}}\leq\tilde{O}(B_{T}d^{1/2}T^{1/2})\)._  
If \(\tilde{O}(B_{T}d^{1/2}T^{1/2})\) is sub-linear with respect to \(T\), then, the proposed DPB is called no-regret. However, the sub-linearity of DPB depends on \(B_{T}\).