Sarsa - ややプログラム紀行

OpenAI Gymの練習と強化学習の理解のためにMountainCar-v0タスクをSarsaと線形回帰の組み合わせで解くプログラムを書いてみた

学習前、適当に行動を選んでいる時の様子↓

1500ステップ刻みでの学習の様子↓*1

やっぱこういうのは実際に見れる形にした方が盛り上がるな！😤サーバー上で諸々やんのめんどいけど

実装は基本的にReinforcement Learning: An IntroductionのExample 10.1を参考にした

教科書ではepisodic semi-gradient one-step Sarsaと呼ばれているもので、具体的には、最適な行動価値関数 $q(s,a)$ を線型結合

$\displaystyle \hat{q}(s,a,\textbf{w}) := \textbf{w}^\top \textbf{x}(s,a) = \sum_{i=1}^d w_i x_i(s,a)$

とSarsaの組み合わせによって近似する手法
ここで $x_i(s,a)$ というのはtile codingによって決まる値で、 $s,a$ がI番目のタイルに入っているときは1、そうでない時は0の値をとる
タイルの敷き方は様々だけれど、ここでは9.5.4 Tile Codingという章に載ってるものを8枚タイルにスケールアップしたものを採用した*2

Sarsaは本来行動価値関数に対してTD学習を当てはめたものだが、semi-gradient one-step Sarsaでの更新式は

$\displaystyle \textbf{w}_{t+1} \leftarrow \textbf{w}_t + \alpha \left[ R_{t+1} + \gamma \hat{q}(S_{t+1}, A_{t+1}, \textbf{w}_t) - \hat{q}(S_t, A_t, \textbf{w}_t) \right] \nabla \hat{q}(S_t, A_t, \textbf{w}_t)$

で、今回は $\hat{q}$ が線形関数なので $\nabla \hat{q}(S_t, A_t, \textbf{w} _ t ) = \textbf{x}(S_t, A_t)$ となる*3

matplotlibの勉強も兼ねて価値関数(を-1倍したもの)の3Dプロットもしてみた

このタスクはゴールするためには一度逆方向の坂を登って速度をつけなければいけないというものだが、実装のキモは報酬が毎ステップ-1であること、そして行動価値関数の初期値が0であることで、これによって基本的に訪れた行動価値関数は負の値をとり、なるべくまだ訪れていない行動価値、例えば左右にある坂の上の方を目指すような方策が出来上がる*4
最適な方策は価値関数が一番高まる行動をgreedyに選んでいくものなので、上のgifでいうと初期地点からなるべく低い方へと勾配降下を行うことになり、学習からしばらくすると初期位置からゴール地点*5への滑り台のようなものが出来上がることになる*6

実際に実装をしてみると、報酬の減衰率を0.9にしていた時は学習がめちゃくちゃ不安定なのに0.99だとうまくいったので思った以上に減衰率がセンシティブなパラメータだということ、そして2枚目のgifの1500ステップ目や4500ステップ目を見ればわかるが、まるで谷底に滑り止めがあるかのような挙動をするということなどがわかった
前者はおそらく減衰率が低い時はゴールしたという情報の伝播が遅くなるからで、これは例えばSarsa( $\lambda$ )など、数ステップ分考慮して更新する手法を使えば改善されると思う
後者は前者で述べたように更新行動が1ステップだけであることに加え、

速度が遅くて谷底にいる時は、右への加速と左への加速の差別化が難しく、それに $\epsilon$ -greedy法によるノイズも加わる
MountainCar-v0において行動が0(左に加速),1(何もしない),2(右に加速)と定義されていることと、numpyのargmaxがargmax([0,0,0])=0となること