FTL-BTL補題が謎だった

BTL補題は，任意の$u \in \mathcal{X}$に対して以下が成り立つことをいう．

$$\begin{aligned} \sum_{t=1}^T f_t(x_{t+1}) \leq \sum_{t=1}^T f_t(u) \end{aligned}$$

これを見ると，

$$\begin{aligned} \min_{x \in \mathcal{X}} \sum_{t=1}^T f_t(x) = \sum_{t=1}^T f_t(x_{t+1}) \end{aligned}$$

のような気がするんだけど，違うらしい．なんで？

$\min$の定義を履き違えてるのでは．下界全体の最大の値なんじゃないか？多分，以下が正しい．

$$\begin{aligned} \min_{x \in \mathcal{X}} \sum_{t=1}^T f_t(x) \geq \sum_{t=1}^T f_t(x_{t+1}) \end{aligned}$$

これで，

$$\begin{aligned} Regret_{FTL}(T) &= \sum_{t=1}^T f_t(x_t) - \min_{x \in \mathcal{X}} \sum_{t=1}^T f_t(x) \\ &\leq \sum_{t=1}^T \left(f_t(x_t) - f_t(x_{t+1})\right) \end{aligned}$$

こうなるのか．

Written with StackEdit.