LinUCB方策のUCBスコア導出

# この記事でやること
LinUCB方策におけるUCBスコアに必要な報酬モデルの期待値と分散を導出する.

# Notation

|記号|説明|
|---|---|
|$t \in \{1,..,T\}$|時刻$t$|
|$i \in \mathcal{I}$|アクション集合|
|$X_i(t)$|時刻$t$に観測されたアクション$i$からの報酬|
|$a_{i,t}$|アクション$i$と時刻$t$に依存した文脈ベクトル|
|$\theta_i$|アクション$i$の真のパラメータベクトル|
|$\epsilon(t)$|時刻$t$時点の線形モデルの誤差項|
|$a_{i(s),s}$|時刻$s$時点で選ばれたアクション$i$と時刻$s$に依存した文脈ベクトル|


# 文脈付きバンディットにおける報酬モデル
以下のように,アクション特有のパラメータ$\theta_i$と時刻$t$で観測された文脈(特徴量)の内積と独立,期待値0,分散$\sigma^2$の確率変数であるノイズの和で表される.なお,UCB方策のにおいては,ガウス分布に従うことまで仮定する必要はない.
```math
X_i(t) = \theta_{i}^{\top}a_{i,t} + \epsilon(t) \qquad \text{-  (1)}
```
```math
\begin{align}
\mathbb{E}_{\epsilon} \left[ X_i(t) \right] &= \mathbb{E}_{\epsilon} \left[ \theta_{i}^{\top}a_{i,t} + \epsilon(t) \right] \\
&= \theta_{i}^{\top}a_{i,t} + \mathbb{E}_{\epsilon}[\epsilon(t)] \\
&= \theta_{i}^{\top}a_{i,t} 
\end{align}
```
```math
\begin{align}
\mathbb{V}_{\epsilon} \left[ X_i(t) \right] &= \mathbb{V}_{\epsilon} \left[ \theta_{i}^{\top}a_{i,t} + \epsilon(t) \right] \\
&= \mathbb{V}_{\epsilon}[\epsilon(t)] \\
&= \sigma^2
\end{align}
```
ということで,期待値$\theta_{i}^{\top}a_{i,s}$,分散$\sigma^2$の確率変数の報酬$X_{i}(t)$が観測されるとする.

# LinUCB方策とは
文脈付きバンディット版のUCB方策.アイデアは,確率的バンディットのUCB方策と同じで,報酬の期待値と分散を補正項としたUCBスコアが最大となるとアクションを選択するという方策.そのUCBスコアは以下の通りで,$\alpha_t$はハイパーパラメータ.

```math
\begin{align}
\bar{\mu_{i}}(t) = \hat{\theta}_{i}^{\top} a_{i,t} + \alpha_t \sigma \sqrt{a_{i,t}^{\top}A_{t}^{-1}a_{i,t}} \quad \text{- (2)}
\end{align}
```
$\hat{\theta}_i$は,真のパラメータ$\theta_i$の最小二乗推定量である.

```math
\begin{align}
\mathcal{J}(\theta_{i}^{'}) &= \sum_{s=1}^{t} (X(s) - 
a_{i(s),s}^{\top} \theta_{i}^{'} )^2 \\
\hat{\theta_i} &= \underset{\theta_{i}^{'}}{\mathrm{argmin}} \quad \mathcal{J}(\theta_{i}^{'})
\end{align}
```
そして,得られた最小二乗推定量$\hat{\theta_{i}}$を用いた予測モデルは以下の通り.
```math
\hat{\mu_{i}}(t) = a_{i,t}^{\top} \hat{\theta_{i}}
```
予測モデル$\hat{\mu}_{i}(t)$の期待値は以下の通りである.

```math
\begin{align}
\mathbb{E}_{\epsilon}[\hat{\mu}_{i}(t)] &= a_{i,t}^{\top} \hat{\theta_{i}} \\
\mathbb{V}_{\epsilon}[\hat{\mu}_{i}(t)] &= \sigma^2 a_{i,t}^{\top}A_{t}^{-1}a_{i,t}
\end{align}
```
つまり,(2)のUCBスコア$\bar{\mu}_{i}(t)$は以下のようにも書ける.

```math
\bar{\mu}_{i}(t) = \mathbb{E}_{\epsilon}[\hat{\mu}_{i}(t)] + \alpha_{t} \sqrt{\mathbb{V}_{\epsilon}[\hat{\mu}_{i}(t)]}
```
要するに,予測の線形モデル$\hat{\mu}_{i}(t)$の期待値と分散がUCBスコアに繋がるわけなので,
1. 真のパラメータに対する最小二乗推定量$\hat{\theta_i}$の導出
2. 予測モデル$\hat{\mu}_{i}(t)$の期待値,分散の導出

を順に行っていく.

# 1. 真のパラメータに対する最小二乗推定量の導出

(再掲)
```math
\begin{align}
\mathcal{J}(\theta_{i}^{'}) &= \sum_{s=1}^{t} (X(s) - 
a_{i(s),s}^{\top} \theta_{i}^{'} )^2 \\
\hat{\theta_i} &= \underset{\theta_{i}^{'}}{\mathrm{argmin}} \quad \mathcal{J}(\theta_{i}^{'})
\end{align}
```
損失関数$\mathcal{J}(\theta_{i}^{'})$は凸関数なので, $\frac{\partial{\mathcal{J}(\theta_{i}^{'})}}{\partial{\theta_{i}^{'}}} = \mathbf{0}$となる点が大域最適解であり,$\hat{\theta_i}$となる.

```math
\begin{align}
\frac{\partial{\mathcal{J}(\theta_{i}^{'})}}{\partial{\theta_{i}^{'}}} &=  -2 \sum_{s=1}^{t} a_{i(s),s}(X_{i}(s) - a_{i(s),s}^{\top} \theta_{i}^{'} ) = \mathbf{0} \\
&= \sum_{s=1}^{t} a_{i(s),s}(X_{i}(s) - a_{i(s),s}^{\top} \theta_{i}^{'} ) = \mathbf{0} \\
&= \sum_{s=1}^{t} a_{i(s),s} X_{i}(s) = \sum_{s=1}^{t} a_{i(s),s} a_{i(s),s}^{\top} \theta_{i}^{'} \\
\theta_{i}^{'} &= \left (\sum_{s=1}^{t} a_{i(s),s} a_{i(s),s}^{\top} \right)^{-1}  \sum_{s=1}^{t} a_{i(s),s} X_{i}(s)
\end{align}
```
ということで, 最小二乗推定量$\hat{\theta_i}$は以下の通り.
```math
\hat{\theta_i} = A_{t}^{-1}\sum_{s=1}^{t} a_{i(s),s} X_{i}(s)
```
但し,
```math
A_{t} = \sum_{s=1}^{t} a_{i(s),s} a_{i(s),s}^{\top}
```
さらに観測される報酬は(1)の通りなので,

```math
\begin{align}
\hat{\theta_i} &= A_{t}^{-1}\sum_{s=1}^{t} a_{i(s),s} X_{i}(s) \\
&= A_{t}^{-1}\sum_{s=1}^{t} a_{i(s),s} (a_{i,s}^{\top}\theta_{i} + \epsilon(s)) \\
&= \theta_i +   A_{t}^{-1}\sum_{s=1}^{t} a_{i(s),s} \epsilon(s) \qquad \text{ -  (3)}
\end{align}
```
よって、真のパラメータ$\theta_i$の最小二乗推定量$\hat{\theta_i}$の導出が完了した.

# 2. 予測モデルの期待値,分散の導出
求めた最小二乗推定量$\hat{\theta_i}$を予測モデルに適用させると以下の通り.
```math
\begin{align}
\hat{\mu_{i}}(t) &= a_{i,t}^{\top} \hat{\theta_{i}} \\
&= a_{i,t}^{\top} \left( \theta_i +   A_{t}^{-1}\sum_{s=1}^{t} a_{i(s),s} \epsilon(s) \right)
\end{align}
```
## 2.1 期待値の導出
```math
\begin{align}
\mathbb{E}_{\epsilon} \left[ \hat{\mu_{i}}(t) \right] &= \mathbb{E}_{\epsilon} \left[ a_{i,t}^{\top} \left( \theta_i +   A_{t}^{-1}\sum_{s=1}^{t} a_{i(s),s} \epsilon(s) \right) \right] \\
&= a_{i,t}^{\top} \theta_i  + \mathbb{E}_{\epsilon} \left[a_{i,t}^{\top}A_{t}^{-1}\sum_{s=1}^{t} a_{i(s),s} \epsilon(s) \right] \\
&= a_{i,t}^{\top} \theta_i  + a_{i,t}^{\top} A_{t}^{-1}\sum_{s=1}^{t} a_{i(s),s} \mathbb{E}_{\epsilon} \left[\epsilon(s) \right] \\
&= a_{i,t}^{\top} \theta_i

\end{align}
```

誤差項$\epsilon(t)$の期待値は時刻$t$によらず0なので,一項目のみ残った.

## 2.2 分散の導出

```math
\begin{align}
\mathbb{V}_{\epsilon} \left[ \hat{\mu_{i}}(t) \right] &= \mathbb{V}_{\epsilon} \left[  a_{i,t}^{\top} \hat{\theta_{i}}\right] \\
&= \mathbb{V}_{\epsilon} \left[  a_{i,t}^{\top} \left( \theta_i +   A_{t}^{-1}\sum_{s=1}^{t} a_{i(s),s} \epsilon(s) \right) \right] \\
&= \mathbb{V}_{\epsilon} \left[ a_{i,t}^{\top} \theta_i  + a_{i,t}^{\top}A_{t}^{-1}\sum_{s=1}^{t} a_{i(s),s} \epsilon(s) \right] \\
&= \mathbb{V}_{\epsilon} \left[ a_{i,t}^{\top} A_{t}^{-1}\sum_{s=1}^{t} a_{i(s),s} \epsilon(s) \right] \\
&= \mathbb{V}_{\epsilon} \left[ a_{i,t}^{\top} A_{t}^{-1}\left( a_{i(1),1} \epsilon(1)+ \cdots + a_{i(t),t} \epsilon(t) \right) \right]
\end{align}
```
誤差項$\epsilon(t)$は独立同分布に従うので,

```math
\begin{align}
\mathbb{V}_{\epsilon} \left[ \hat{\mu_{i}}(t) \right] &= \mathbb{V}_{\epsilon(1)} \left[ a_{i,t}^{\top} A_{t}^{-1} a_{i(1),1} \epsilon(1)\right] + \cdots + \mathbb{V}_{\epsilon(t)} \left[ a_{i,t}^{\top} A_{t}^{-1} a_{i(t),t} \epsilon(t)\right] \\
&= \left( a_{i,t}^{\top} A_{t}^{-1} a_{i(1),1} \right)^2 \mathbb{V}_{\epsilon(1)} \left[ \epsilon(1)\right] + \cdots + \left( a_{i,t}^{\top} A_{t}^{-1} a_{i(t),t} \right)^2 \mathbb{V}_{\epsilon(t)} \left[ \epsilon(t)\right] \\
&= \left( a_{i,t}^{\top} A_{t}^{-1} a_{i(1),1} \right)^2 \sigma^2 + \cdots + \left( a_{i,t}^{\top} A_{t}^{-1} a_{i(t),t} \right)^2 \sigma^2 \\
&= \sigma^2 \sum_{s=1}^{t} \left( a_{i,t}^{\top} A_{t}^{-1} a_{i(s),s} \right)^2 \\
&= \sigma^2 \sum_{s=1}^{t} a_{i,t}^{\top} A_{t}^{-1} a_{i(s),s} a_{i(s),s}^{\top} A_{t}^{-1} a_{i,t} \\
&= \sigma^2 a_{i,t}^{\top} A_{t}^{-1} \left( \sum_{s=1}^{t} a_{i(s),s} a_{i(s),s}^{\top} \right) A_{t}^{-1} a_{i,t} \\
&= \sigma^2 a_{i,t}^{\top} A_{t}^{-1} A_t A_{t}^{-1} a_{i,t} \\
&= \sigma^2 a_{i,t}^{\top} A_{t}^{-1} a_{i,t}
\end{align}
```
つかれた.よって,予測モデル$\hat{\mu_i}(t)$の期待値,分散の導出が完了

# UCBスコアの再掲

```math
\begin{align}
\bar{\mu}_{i}(t) &= \mathbb{E}_{\epsilon}[\hat{\mu}_{i}(t)] + \alpha_{t} \sqrt{\mathbb{V}_{\epsilon}[\hat{\mu}_{i}(t)]} \\
&= \hat{\theta}_{i}^{\top} a_{i,t} + \alpha_t \sigma \sqrt{a_{i,t}^{\top}A_{t}^{-1}a_{i,t}}
\end{align}
```
# 参考文献
・ 本多淳也，中村篤祥：バンディット問題の理論とアルゴリズム，講談社（2016）
・ Lihong Li, Wei Chu, John Langford, and Robert E. Schapire. 2010. A contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web (WWW '10). Association for Computing Machinery, New York, NY, USA, 661–670.