この記事でやること
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方策のにおいては,ガウス分布に従うことまで仮定する必要はない.
X_i(t) = \theta_{i}^{\top}a_{i,t} + \epsilon(t) \qquad \text{- (1)}
\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}
\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$はハイパーパラメータ.
\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$の最小二乗推定量である.
\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}}$を用いた予測モデルは以下の通り.
\hat{\mu_{i}}(t) = a_{i,t}^{\top} \hat{\theta_{i}}
予測モデル$\hat{\mu}_{i}(t)$の期待値は以下の通りである.
\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)$は以下のようにも書ける.
\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スコアに繋がるわけなので,
- 真のパラメータに対する最小二乗推定量$\hat{\theta_i}$の導出
- 予測モデル$\hat{\mu}_{i}(t)$の期待値,分散の導出
を順に行っていく.
1. 真のパラメータに対する最小二乗推定量の導出
(再掲)
\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}$となる.
\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}$は以下の通り.
\hat{\theta_i} = A_{t}^{-1}\sum_{s=1}^{t} a_{i(s),s} X_{i}(s)
但し,
A_{t} = \sum_{s=1}^{t} a_{i(s),s} a_{i(s),s}^{\top}
さらに観測される報酬は(1)の通りなので,
\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}$を予測モデルに適用させると以下の通り.
\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 期待値の導出
\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 分散の導出
\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)$は独立同分布に従うので,
\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スコアの再掲
\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.