この記事でやること

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)