この前の記事で、強化学習について書いたのですが、色々と試してみたので追加報告です。

強化学習と行動選択

前の記事で説明したように、強化学習は最適な方策πの分布を求める問題なのですが、πの分布に相当するQ値を計算するため、何らかの方法でとりあえずの行動選択をする必要があるのでした。もちろん、Q値が収束してくるのなら、その情報を使って選択肢を選ぶ方が賢いわけですから、乱択アルゴリズムを用いるより、マシな方法があるはずです（あります）。この手の「行動選択」の問題について知りたい場合「多椀バンディット問題」という名前の付いた素敵な問題がありますので、その辺を掘ってみるとよいかもしれません。今回は、わたしがふんわりと理解しているいくつかのアルゴリズムを用いて、前回の記事で作成した「政治家バカ一代——人生シミュレーション」のプログラムを改良したいと思います。

行動選択の手法と特徴

まずは、候補となる行動選択の手法についてみていきます。

乱択アルゴリズム

エントリーNo.1番。方策πの中から等しい確率でランダムで選ぶ、という無策なアルゴリズムです。何の工夫もしない場合、これでもなんとかQ値が収束するようです。特にQ学習を用いる場合、割と何事もなかったかのように収束します。コードは以下の通り：

def uniform(A):
    pi_cdf = np.cumsum(np.tile(1, len(A)) / len(A))
    return np.argwhere(pi_cdf > np.random.uniform(0,1))[0][0]

前回のバージョンはA（行動の集合）の要素が二つと決め打ちでしたが、今回のコードはN個の行動に対応するようにしたZE☆。

εグリーディー

エントリーNo.2番、かの有名な（？）εグリーディーです。「すうしき」ではなく言葉で説明すると、「確率εで乱択アルゴリズムを選択、そうではない場合、Q値が最も高い行動を選択」です。気まぐれなので、確率εで乱択（探索）する一方、愚直に報酬が一番でかい奴をとる（活用する）のでεグリーディーと呼ばれるようです。コードは下記の通り：

def eps_greedy(A, s, Q, epsilon):
    if np.random.uniform() < epsilon:
        return uniform(A)
    else:
        return np.argmax(Q[s])

Sofmaxアルゴリズム

これも、なんか有名だったよね？なんか、ニューラルネットワークでよく使われるアレですな。シグモイドとかの代わりに使うと、なんか、こういい感じになるというね（うる覚え）。とはいえ、これでは余りにいい加減なので、Wikipedia英語版を引用しておきます。

In probability theory, the output of the softargmax function can be used to represent a categorical distribution – that is, a probability distribution over K different possible outcomes.

今回行動は離散値を想定しているので、上記の解釈でよさそうですね！さすがにこいつに関しては、数式の方が分かりやすいのでWikipediaから拝借してきたものを引用。

なんか、eとか出てきているので難しい感じがしますが、何のことはないです。普通、なんかの値を合計1になるように正規化するとき、分母を値の合計として正規化することがありますよね？Softmaxの場合、値zの代わりにnp.exp(z)としたものを使っています。違いはそれだけ！

というわけで、コードです。

# これがかの有名なsoftmaxである。控えよろぉ
def softmax(A, s, Q, T):
    num = np.array([np.exp(Q[s][a]/T) for a in A])
    denom = np.sum([np.exp(Q[s][b]/T) for b in A])
    pi_cdf = np.cumsum(num / denom)
    index = np.argwhere(pi_cdf > np.random.uniform(0,1))[0][0]
    return A[index]

Tは定数パラメータです。これも、ちゃんと決め方？あるんだろうけど、今回は適当な値を、独断と偏見によって設定しています。

UCBアルゴリズム

最後に、「多椀バンディット問題」界隈で「最も優秀なやつ」と言われているUCBアルゴリズムです。これ理屈がよく分かっていないのですが、式は次の通りになります：

実はこの辺はまだお勉強中。何か分かったら続報します。

# UCBは評判が良い。
def ucb(A, s, Q, n, ni, C):
    _ucb = C * np.sqrt(np.log(n) / (ni[s] + 1e-8))    
    index = np.argmax(Q[s] + _ucb)
    ni[s][index] += 1
    return index

これが一番面倒ですねー。コード中のCというパラメータが、参考文献の数式にはないのですが、他の情報ソースだとあったりするので、一応、実装しておきました。このCについては、よく分からないので1にして実験します。実はuに足されているルートの部分ですが、これが真の平均値との誤差を現しているようです。その信頼区間の上限を与えるのがUCBだそうなので、たぶんこのCをいじると上限を調整できるような仕組みになっていると思われます。

えーと、これではふわりとしすぎているので、上の講義資料から引用します。

At an intuitive level, the additional term helps us avoid always playing the same arm without checking out other arms. This is because as ni,t increases, UCBi,t decreases.

直感的には、同じ選択肢ばかり選んでいるとniの値が増えて、その選択肢に対するucbは小さくなる。よって、同じ選択肢ばかり選んでしまうことを回避するよう動く、という感じのようです。ただ、単にそういう理由で追加の項がつけられているわけではありません。飽くまで直感的にはそのように動作すると言うだけの話。本来は、

But there is a more fundamental reason for the choice of the term. It is a high confidence upper bound on the empirical error of ˆµi,t.

ということで、上で説明した通り、Q値の見積と真値との誤差の分布を考えて、その信頼区間の上限を計算するため余計な項を追加しているということのようです。これについて、もっと詳しい解説が下記のサイトにあります。sub-Gaussian distributionとかって言われて、「ああ、あれのことか」と思った識者の方（はこの記事読んでないでしょうけど）下記のサイトの方が分かりがいいと思います。私は分からないので流し読みして、とりあえず「わからない」のフラグを付けました。そのうち、Thompson Sampling（事後分布を求めて、そこから乱数をサンプリングして、行動選択をするという七面倒くさい方法）などとも合わせて、記事にしようかなと思ってたり、思ってなかったり。

一応、私のふんわりとした理解では、ここで示した数式はGaussianのテールの分布から計算されているようです。だから、「Q値の見積もり（現在値）と決して観測できない真のQとの誤差は、独立した正規分布に従うから～」とかって考えてもよいのなら、今回のケースにそのまま当てはめても良いと、私が独断で判断しました（というわけで、あてにはならないZE☆）。

比較実験

さて、小難しい理論のお勉強はさておき、実際、サンプリングの方法（とりあえずの方策π）を変えると、Q値に対して何らかの影響が出るのでしょうか？これまでの調査から：

SARSAは方策ON型⇒影響受けそう
Q学習は方策OFF型⇒影響受けなさそう

といううすぼんやりな予想が立ちます。というわけで、いざやってみませう。

SARSAアルゴリズム

まずは、方策によって差が出そうなSARSAから。今回のモデルは、二状態、二行動なのでQ値は四つなのですが、割と大きめの値に収束している二つの成分のみ図示します（見やすさ優先）。

ちょっとできる男ぶって、X軸は対数軸にしてみたぜ（収束までの立ち上がりに差が出るか見たかったため）。まー、どれを使っても横並びと言う感じです。ただし、乱択アルゴリズム（Uniformというやつ）だけ、なんか収束値が他とちがーう。もしかすると、私のコードのバグなのかもしれませんが、明らかに差が出ているのは乱択アルゴリズムだけであり、その他の方策の間には言うほどの差が出ていませんでした（まぁ、今回は問題がちゃちいせいかもしれないですが）。

Q学習アルゴリズム

次は方策オフ型のQ学習です。

この通り、方策πとしてどれを使ってもほとんど何の差もないように思えます。これが、方策πオフ型という言葉の意味なのでしょうか？？まー、それ以外に考えらえないので、そうだと思われます。とりあえずの方策πとして、何を選んでもOKという感じですね。

考察

今回のグラフでは、収束の速度に微妙な差が出ているように見えますが、実はこれは場合によってまちまちです。乱数の当たりはずれで差が出ているだけのようです。εグリーディーに関しては、たまーに、オーバーシュート気味になる傾向があるようですが、スクリーンショットを取るために何度かやってみたけど再現不能でした（そのくらいの頻度でしか起こらない）。この辺、パラメータの調整いかんによって変わるかも。

今回は問題自体が「トイ・プロブレム」なせいもあってか、UCB、Softmax、εグリーディーの間にほとんど差はないという結果になりました。もちろん、これは問題の質いかんに依りますが、学習している分布の判別がそもそも難しいような問題だと、今度は逆に「どれを使ってもダメ」ということになるのは知っているので、逆に、これらのアルゴリズムに顕著な差が出る例というのがどんなものなのか気になります。

今回の実験で、Q学習に関しては前評判通りの結果が得られました。方策πとしてどれを用いても、最終的なQ値はほとんど変わらず横並び。一方で、SARSAに関しては乱択アルゴリズムを用いた場合と「その他」のもっとましなものを利用した場合で差が出ている模様です。私のコードのバグと言う可能性もありますが、いやー、それはないと思うんだけどなぁ。一応、「その他」代表としてSoftmaxと乱択アルゴリズムを比較した図を再掲します。

始めは「ダイス目（乱数のあたり）」によって差が生じているのかと思ったのですが、そうではなく、何度やってもこうなるので明らかに収束先が違います。ちなみに、あまり収束の良くない残りの二成分に関しては、次のようになります。

これに対して、UCBとSoftmaxだとたいして差は出ません。

「その他」の連中に関しては、他のペアでも試してみたけど、あまり差はなくて(CORRPUTED,CHEAT)の成分は1.0前後、(HEALTHY, HONESTY)に関しては、-1.0前後で落ち着く傾向があります。この選択肢は同じ状態の別の選択肢に比べて圧倒的に報酬が低いので、「その他」アルゴリズムでは、あまり選ばれることがないと考えられます。もしかしたら、そのあたりが原因になっているのかも…と思ったりもしたのですが、そもそも上の図では、かなり報酬が大きい(HEALTHY, CHEAT)でも結構差が出ていますから、やはり根本的な差があるはずです。こういうとき、ちゃんと「理論」が分かっていると、この差が何に起因するのか、数理的に解析できるのですが…（私にそこまでのスキルはないのだよ）。

ちなみに、収束の悪かったQ値の二成分ですが、Q学習を使うと収束が悪いこともなくて、いや、収束うんぬん以前に値が全然違う（´д｀）。まー、前回から気づいていたことではあるのですが、やっぱりこの違いはちょっと大きすぎる気がするなぁ。

# Q learning, Softmax
Q(CORRUPTED,HONESTY)=16.5611406258961
Q(CORRUPTED,CHEAT)=12.189450821142987
Q(HEALTHY,HONESTY)=9.659405579753871
Q(HEALTHY,CHEAT)=19.638699342600873

# SARSA, Softmax
Q(CORRUPTED,HONESTY)=4.780767009416528
Q(CORRUPTED,CHEAT)=-0.09092740013288299
Q(HEALTHY,HONESTY)=-1.7684210230902597
Q(HEALTHY,CHEAT)=15.749407567621757

ちなみに、前回リンクしたブログの記事には、以下のような記述があります：

なぜそのような結果になったかというと
Q学習は遷移先状態の最大行動価値だけを用いるため、
単純にゴールがどれだけ近いかのみを見みます。
そのため、近い道を見つけています。
逆に言えば、遷移先状態の最大行動価値以外の価値は見ないため、
危険かどうかは考慮ぜず行動します。
崖に近い道を選択しているので、探索行動によってと崖から落ちているため、
報酬が小さくなっています。

今回の「政治家モデル」では、社会の状態が移行した場合に発生する「リスク」を見ていないことが、Q学習とSARSAで差が出たことの理由かもしれません。一方で：

一方で、SARSAは ϵ-greedyで、ϵを0にしない限り、
遷移先状態のすべての行動価値を考慮して学習します。
そのため、危険な道も考慮して学習することになり、
安全な道を学習したと言えます。

ということは、SARSAでもεグリーディーで、εをゼロにすると同じような結果が得られるのでしょうか。ちょっと試してみましょう。

えー、なんないよー。もしかすると、実装の違いによるものなのかもしれませんが、冷静に考えてみるとSARSAでepsilon=0.0のグリーディー法を用いたからと言って、Q値の計算式が変わるわけではないですから、状況が違うからなのか、私の実装の問題なのか、やはりそうはなりません。

そもそも、Q学習とSARSAの根本的な差は、遷移先の状態の最大価値によってQ値を計算する（Q学習）か、遷移先の状態と行動のペアに対してQ値を計算するか、という違いのはず。よって、行動「も」考慮するSARSAは、探索中の方策πに依存したQ値を計算することになる…というロジックだったはず、です。だから、当面の方策πとして何を用いるかで、Q学習とSARSAに差が出るというのはやはりちょっと違う気がしてきたぞ。方策πの選択によって影響を受けるのは、SARSAを用いた場合だけ。そして、そもそもQ値の計算方法が違うのだから、当面の方策πの取り方をどうしようが、この二つの差を埋める効果が出るとは思えない。もちろん、リンク先の記事はそういうことを言っているのではなく、SARSAでeps=0にすると、よりQ学習に近づくと言っているだけで、一致するとは言ってないのだけど…手元も実装における実験だと、近づいている様子すらない。

# SARSA epsilon 0.0
Q(CORRUPTED,HONESTY)=4.66074326302942
Q(CORRUPTED,CHEAT)=-0.5472905666725869
Q(HEALTHY,HONESTY)=-0.9003129910955786
Q(HEALTHY,CHEAT)=15.556233195546863

# SARSA epsilon 0.25
Q(CORRUPTED,HONESTY)=5.605838383183802
Q(CORRUPTED,CHEAT)=0.5995419268978659
Q(HEALTHY,HONESTY)=-1.0566836214001902
Q(HEALTHY,CHEAT)=12.422147871329159

# Q-Learning epsilon 0.0
Q(CORRUPTED,HONESTY)=15.984002289879417
Q(CORRUPTED,CHEAT)=12.438994448206547
Q(HEALTHY,HONESTY)=10.169715156265966
Q(HEALTHY,CHEAT)=19.770554030908112

# Q-Learning epsilon 0.25
Q(CORRUPTED,HONESTY)=16.740204956876553
Q(CORRUPTED,CHEAT)=13.070834890849726
Q(HEALTHY,HONESTY)=10.362246973047434
Q(HEALTHY,CHEAT)=19.839819982762172

というわけで、これがSARSAとQ学習の差なのかもしれませんが、もしかしてひょっとするとバグかもｗｗｗｗ。こういうとき、バグなのか、それとも、問題設定上このくらいの差が出てもおかしくないのか知りたければ、やはり数学とお付き合いする必要がありそうです。そもそも、こういったアルゴリズムの実装は、元から得意だったわけではないので、やってみてあのスキルがない、このスキルがないということを感じることが多い。そこが改善点ですね。私というアルゴリズムの（うまいこと言った、上手いこと言ったよ！いま！）。

結論

というわけで、異なる方策によりQ学習、SARSAでしょーもない問題の強化学習をしたとき、どんな差が出るのか？という検証の結果は以上のとおりです。結論から言うと：

Q学習とSARSAでは得られるQ値が結構違う場合がある。
Q学習を用いる場合、方策として何を用いても差は出ない模様。
SARSAを用いる場合、乱択アルゴリズムを方策として用いると差が出る。
収束の速度については、方策として何を用いたとしても、それほど差はない。

ということになります。ただし！

今回使用したコードにバグがある可能性。
SoftmaxやUCBが力を発揮するには、問題が単純すぎた可能性

があることを念頭に、さらなる実験が必要、だと思われます。

以上です！