この記事でやること
LinTS方策におけるパラメータのサンプリングに必要である事後分布(ガウス分布)の期待値ベクトルと共分散行列を導出する.
Notation
記号 | 説明 |
---|---|
$t \in {1,..,T}$ | 時刻$t$ |
$i \in \mathcal{I}$ | アクション集合 |
$X_i(t)$ | 時刻$t$に観測されたアクション$i$からの報酬 |
$a_{i,t} \in \mathbb{R}^d$ | アクション$i$と時刻$t$に依存した$d$次元の文脈ベクトル |
$\theta_i \in \mathbb{R}^d$ | $d$次元のアクション$i$の真のパラメータベクトル |
$\epsilon(t)$ | 時刻$t$時点の線形モデルの誤差項 |
$a_{i(s),s} \in \mathbb{R}^d$ | 時刻$s$時点で選ばれたアクション$i$と時刻$s$に依存した$d$次元の文脈ベクトル |
$I_d$ | $d$次元の単位行列 |
文脈付きバンディットにおける報酬モデル
\begin{align}
\epsilon(t) &\overset{\mathrm{i.i.d}}{\sim} \mathcal{N}(0, \sigma^2)\\
X_i(t) &= \theta_{i}^{\top}a_{i,t} + \epsilon(t) \qquad \text{- (1)} \\
\end{align}
以上のように, アクション特有のパラメータ$\theta_i$と時刻$t$で観測された文脈(特徴量)の内積と, ガウス分布に従う確率変数であるノイズの和で表される.
\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}
X_i(t) \sim \mathcal{N}(\theta_{i}^{\top}a_{i,s}, \sigma^2)
ということで,期待値$\theta_{i}^{\top}a_{i,s}$,分散$\sigma^2$のガウス分布に従う確率変数の報酬$X_{i}(t)$が観測されるとする.
LinTS方策とは
文脈付きバンディット版のTS方策. 以下のように, パラメータ$\theta_i$に事前分布を導入することで, 時刻$t$までに収集された報酬のもとでのパラメータ$\theta_i$の事後分布をもとにサンプリングを行い, 線形モデルの内積値最大のアクションを選択する方策である.
\begin{align}
p(\theta_i) &= \mathcal{N}(\theta_i | \mathbf{0},\sigma_{0}^2I_d) \\
&= \frac{1}{(2\pi)^{\frac{d}{2}} |\sigma_{0}^2I_d|^{\frac{1}{2}}} \exp \left(- \frac{\theta_{i}^{\top} \theta_i}{2\sigma_{0}^2} \right)
\end{align}
報酬モデル$X_i(t)$も同様にガウス分布に従うので, 以下のように事後確率も同様にガウス分布に従う.
p(\theta_i | \{ X_i(s) \}_{s=1}^t) = \mathcal{N}(\theta_i | \mu_t,\Sigma_{t})
ということで, 時刻$t$時点においてパラメータのサンプリングに必要な多変量ガウス分布の期待値ベクトル$\mu_t$と共分散行列$\Sigma_{t}$を導出することが今回のテーマである.
事後分布の導出
事後分布もガウス分布に従うので, 指数関数内で二次形式を作ることが一つの着地点である.
\begin{align}
p(\theta_i | \{ X_i(s) \}_{s=1}^t) &\propto p(\theta_i)P(\{ X_i(s) \}_{s=1}^t | \theta_i) \\
&= p(\theta_i) \prod_{s=1}^t p(X_i(t)|\theta_i) \\
&= \frac{1}{(2\pi)^{\frac{d}{2}} |\sigma_{0}^2I_d|^{\frac{1}{2}}} \exp \left(- \frac{\theta_{i}^{\top} \theta_i}{2\sigma_{0}^2} \right) \prod_{s=1}^t \frac{1}{\sqrt{2\pi\sigma^2}} \exp \left(- \frac{1}{2\sigma^2}(X_i(s) - \theta_{i}^{\top}a_{i(s),s})^2 \right) \\
&= \frac{1}{(2\pi)^{\frac{d+t}{2}} (\sigma^2)^{\frac{t}{2}}|\sigma_{0}^2I_d|^{\frac{1}{2}}} \exp \left(- \left( \frac{\theta_{i}^{\top} \theta_i}{2\sigma_{0}^2} + \frac{1}{2\sigma^2} \sum_{s=1}^t \left( X_i(s) - \theta_{i}^{\top}a_{i(s),s} \right)^2 \right) \right) \\
&\propto \exp \left(- \left( \lambda_2\theta_{i}^{\top} \theta_i+ \lambda_1 \sum_{s=1}^t \left( X_i(s) - \theta_{i}^{\top}a_{i(s),s} \right)^2 \right) \right)
\end{align}
ここで, $\lambda_1 = \frac{1}{2\sigma^2}, \lambda_2 = \frac{1}{2\sigma_{0}^2}$と置き換えた.
\begin{align}
p(\theta_i | \{ X_i(s) \}_{s=1}^t) &\propto \exp \left(- \left( \lambda_2\theta_{i}^{\top} \theta_i+ \lambda_1 \sum_{s=1}^t X_i(s)^2 - 2 a_{i(s),s}^{\top} \theta_i + \theta_{i}^{\top}a_{i(s),s}a_{i(s),s}^{\top} \theta_i \right) \right) \\
&= \exp \left( - \left( \lambda_2\theta_{i}^{\top} \theta_i + \lambda_1 \left( \sum_{s=1}^t X_i(s)^2 \right) - 2\lambda_1 \left( \sum_{s=1}^t X_i(s)a_{i(s),s}^{\top} \right)\theta_i + \lambda_1\theta_{i}^{\top} \left( \sum_{s=1}^t a_{i(s),s}a_{i(s),s}^{\top} \right) \theta_i\right) \right) \\
&\propto \exp \left( - \left( \lambda_2\theta_{i}^{\top} \theta_i - 2\lambda_1 \left( \sum_{s=1}^t X_i(s)a_{i(s),s}^{\top} \right)\theta_i + \lambda_1\theta_{i}^{\top} \left( \sum_{s=1}^t a_{i(s),s}a_{i(s),s}^{\top} \right) \theta_i\right) \right) \\
&= \exp \left( - \left( \lambda_2\theta_{i}^{\top} \theta_i - 2\lambda_1 b_{t}^{\top}\theta_i + \lambda_1\theta_{i}^{\top} \widetilde{A}_{t} \theta_i\right) \right) \\
\end{align}
ここで,
b_t = \sum_{s=1}^t X_i(s)a_{i(s),s}, \quad \widetilde{A}_{t} = \sum_{s=1}^t a_{i(s),s}a_{i(s),s}^{\top}
と置き換えた.
\begin{align}
p(\theta_i | \{ X_i(s) \}_{s=1}^t) &\propto \exp \left( - \lambda_1 \left( \theta_{i}^{\top} \left( \widetilde{A}_{t} + \frac{\lambda_2}{\lambda_1}I_d \right)\theta_i - 2b_{t}^{\top}\theta_i\right) \right)
\end{align}
$\theta_i$について二次形式を作るために,以下の恒等式を考える.
\begin{align}
\theta_{i}^{\top}A_t\theta_i - 2b^{\top}\theta_i &= \left( \theta_i - A_{t}^{-1}b_t \right)^{\top}A_t\left( \theta_i - A_{t}^{-1}b_t \right) - b_{t}^{\top}A_{t}^{-1}b_t \\
&\propto \left( \theta_i - A_{t}^{-1}b_t \right)^{\top}A_t\left( \theta_i - A_{t}^{-1}b_t \right)
\end{align}
$A_t = \left( \widetilde{A}_{t} + \frac{\lambda_2}{\lambda_1}I_d \right)$として,上記の式に当てはめると二次形式ができる.
\begin{align}
p(\theta_i | \{ X_i(s) \}_{s=1}^t) &\propto \exp \left( - \lambda_1 \left( \left( \theta_i - A_{t}^{-1}b_t \right)^{\top}A_t\left( \theta_i - A_{t}^{-1}b_t \right) \right) \right)
\end{align}
$\lambda_1, \lambda_2$を戻して,
A_t = \left( \widetilde{A}_{t} + \frac{\sigma^2}{\sigma_{0}^2}I_d \right)
p(\theta_i | \{ X_i(s) \}_{s=1}^t) \propto \exp \left( - \frac{1}{2\sigma^2} \left( \left( \theta_i - A_{t}^{-1}b_t \right)^{\top}A_t\left( \theta_i - A_{t}^{-1}b_t \right) \right) \right)
ということで,見慣れた多変量ガウス分布の指数部分がうまくまとまった.
この式から事後分布の期待値ベクトルと共分散行列は以下の通り.
\begin{align}
\mu_t &= A_{t}^{-1}b_t \\
\Sigma_{t} &= \sigma^2 A_{t}^{-1} \\
\end{align}
事後分布の再掲
\begin{align}
p(\theta_i | \{ X_i(s) \}_{s=1}^t) &= \mathcal{N}(\theta_i | \mu_t,\Sigma_{t}) \\
&= \mathcal{N}(\theta_i | A_{t}^{-1}b_t, \sigma^2 A_{t}^{-1})
\end{align}
参考文献
・本多淳也,中村篤祥:バンディット問題の理論とアルゴリズム,講談社(2016)
・元田浩ほか訳:パターン認識と機械学習上,ベイズ理論による統計的予測,シュプリンガー・ジャパン (2007)