はじめに

2019年から強化学習ゼミを実施しています。ゼミで議論になった部分について記録します。

使用している教科書

強化学習著：森村哲郎

ディスカッション

近似ベルマン作用素がベルマン期待作用素に収束する計算

M($\pi$)にエルゴード性を仮定する。

\lim_{T\rightarrow\infty }\frac{1}{T}\sum_{t=0}^{T-1}I_{s_t=s} = p_\infty^\pi(s) > 0

すると

\begin{align}
&\lim_{T\rightarrow\infty }\frac{1}{T}\sum_{t=0}^{T-1}I_{s_t=s}(r_t+\gamma v(s_{t+1})) \\
&=\lim_{T\rightarrow\infty }\frac{1}{T}\frac{\sum_{t'=0}^{T-1}I_{s_{t'}=s}}{\sum_{t'=0}^{T-1}I_{s_{t'}=s}}\sum_{t=0}^{T-1}I_{s_t=s}(r_t+\gamma v(s_{t+1})) \\
&=\lim_{T\rightarrow\infty }\frac{1}{T}\sum_{t'=0}^{T-1}I_{s_{t'}=s}\mathbb{E}^\pi[R_t+\gamma v(S_{t+1})|S_t=s] \\
&=p_\infty^\pi(s)\mathbb{E}^\pi[R_t+\gamma v(S_{t+1})|S_t=s]
\end{align}

この式変形を式(4.4)に適用すると式(4.7)が得られる。

収束の速さ

式(4.2)のモンテカルロ法は効率が悪い。ベルマン作用素を使用した方法のほうが効率が良い
→具体的にどれくらい効率が良いか示されていない。要調査

トレースの計算量

式(4.25)を各tごとに計算するのは計算量が多く、前方観測的なTD($\lambda$)法のほうが有利ではないのか？
→トレースについて、式(4.26)を各tで計算するのは大変だが、p.101の式のように漸化式にすれば、1ステップ前の値さえ記憶していれば計算できるので計算量は多くない。

z_{t,\lambda}(s) = I_{s_t=s} + \lambda \gamma z_{t-1, \lambda}(s)

一方で$\hat V(s)$はすべての$s\in S$に対して記憶しておく必要があることに注意。計算量自体は多くない。

\delta_t = r_t + \gamma \hat V(s_{t+1}) - \hat V(s_t)

おわりに

現在は4.1節〜4.2節までやりましたがとてもわかり易いです。