大分前から、強化学習に興味があったんだけど、意味が分からな過ぎて半ばあきらめていた。最近、小難しいことを色々やるようになったので、「そろそろ拙者も強化学習に入門しよう」と思い立ち、Qiitaの優良な記事（と、あとWikipediaな）などを読みつつお勉強したので、成果をしぇあするぞ！

例によって、私は数式がダメダメなので「コードを書いて」理解していく方式を取ります。本来、数式じゃないと表現できなさそうなものも無理やりコードで表現するという、プログラマー向けの記事にするぜ！

問題設定

そもそも、「強化学習」とは何なのか？ということですが、ざっくり言うと：

世界が「マルコフ決定過程」という過程に従っているとしよう。そのとき、ある状態sで行動aをとる「確率」を現す関数πを考えることができる。このπを方策と呼ぶことにする。方策πを定めるため、ある状態sで行動aをとったとき、将来的にどの程度の利得（報酬）が得られるのか知りたい。そのためには、ある状態sで行動aをとったときの割引報酬和の期待値を計算する必要があるだろう。じゃあ、それを計算しようではないか。

ということだと理解しました。うわー、うすぼんやりですね。まぁ、ともかくそういうことなので、まずはこの「マルコフ決定過程」という代物を理解する必要がありそうです。それは、これだ！めんどうなので、Wikipediaをまるごと引用するぜ！

みてのとおり、とっても抽象的です。これだけでは、実装もクソもないので、今回は壮大な社会実験を想定した「ぐたいてきながくしゅうのれい」を私が親切にも示してあげるぞ！

状態

とはいえ、一つの例に限定してしまうとAは離散じゃないとダメなの？とか、Sの形式は配列じゃないとダメなの？みたいな議論になってしまうので、ちょっとプログラムっぽく、こいつらを表記してみることにします。まずは、この状態Sとか、行動Aとかの集合をコードっぽく書いてみよう（コードを書くと、なんか分かった気になるのは私だけ？）。

# 状態（離散でも、連続でも良い）
# 連続の場合、範囲で表記することにしよう
# 実数0~1の集合なら(0,1)のように書く。
S = ((0.0, 1.0),) # 連続
S = [1] # 離散

# 行動（離散でも、連続でも良い）
A = ((0.0, 1.0),) # 連続
A = [0] # 離散

#
# 実際の問題を解く際は、S,Aの組を問題に応じて定義する。
#

# 連続2状態、離散4行動
S = ((0.0, 1.0), (-1.0, 1.0))
A = [0,1,2,3]

# 離散4状態、連続1自由度の行動
S = [0,1,2,3]
A = ((0.0, 1.0))

# 離散4状態、離散3行動
S = [0,1,2,3]
A = [0,1,2]

# 連続2状態、連続2自由度の行動
S = ((0.0,1.0), (0.0, 1.0))
A = ((-1.0,1.0), (-1.0, 1.0))

こんな感じになると思われます。思ったより簡単そうです。実際、この集合SだのAだのは、問題設定によって表現形式も、離散／連続などの区分も変わるため、「こういうものです」と帽子からウサギを出すように現物を出して見せることはできません。ただし、有限集合と書いているので、任意の実数とかはダメなんじゃないかなぁ。ある程度、値の範囲に制限のある多次元ベクトルを状態としてもいいし、行動もモーターの回転数とか、トルクのような連続量でも良いようです。まぁ、なんでもいいってことですが、「状態」と「行動」の二つを定量化し、問題に合わせて表現してやらねばならぬ。そういうことのようです。離散の場合は、適当な整数を並べて状態とか、行動にしてもよい。もちろん、離散状態と実数行動（異常、正常というに状態と、制御変数xみたいな組み合わせ）でも良いようです。

ただ、これではあんまりなので、今回は次のような具体的な状態、行動を問題設定とします。

# 離散状態、離散行動
# 政治家の行動モデル。

# 状態は社会の状態とする。
# S = (腐敗、健全）
CORRUPTED, HEALTHY = 0, 1

# 行動は真面目にやるか不正をするかの二択
# A = (真面目にやる、不正をする）
HONESTY, CHEAT = 0, 1

S = [CORRUPTED, HEALTHY]
A = [HONESTY, CHEAT]

この場合、SとAは離散で二状態になります。最も簡単なパターンですね。一応、ねんのため、これは私が勝手に作った例題なので説明しますが、ここでやりたいことは、世界の状態として「健全、腐敗」の離散二状態、そのとき政治家が取れる行動として「真面目にやる、ずるをする」の離散二行動を考えて、集合SやAを表現しようということです。モデルはちゃちいですが、シミュレーションの意図は壮大なのだ！

遷移関数、報酬関数

次に、遷移関数とか、報酬関数とかそういうものです。遷移関数の値域は[0,1]となっているので、これは確率っぽい感じ。報酬関数はRなので、実数なら何でもよい。ただ、これだけ見てると、これが集合としてモデル化されるべきなのか、関数としてモデル化されるべきなのかが、いまいちです。私は、関数っぽい形の方が分かりやすいので、ためしに無理やり関数っぽくして書いてみます。

# 状態遷移関数
# 状態s0で行動をaを取ったとき、s1に遷移する確率を返す関数。
# 入力：今の状態s0、状態s0で取れる行動a、遷移先の状態s1
# 出力：s0でaを取ったとき、s1に遷移する「確率」
# →Tは「確率（重み）」を返す関数。マルコフ連鎖の遷移行列的なしろもの。
def T(s0, a, s1):
    pass

# 報酬関数
# 状態s0で行動aを取り、s1に遷移した場合得られる報酬
# 又は、その期待値を返す関数。
# 入力：今の状態s0、状態s0でとれる行動a、遷移先の状態s1
# 出力：s0でaを取ったとき、s1に遷移するともらえる報酬（の期待値）
# →確定的、又は何らかの確率分布に従って確定的な報酬（実数）を返す関数。
def R(s0, a, s1):
    pass

これも、具体的にこういうものという形が定まっているわけではなく、問題によって決まります。ただし、現実の問題を解く場合は、これが「不明」というケースが多いはずです（じゃなけりゃ、わざわざ学習する意味がない）。ただし、そういう状態においても、入力と出力はある程度観測できなければなりません。次に先ほどの政治家問題における遷移関数、報酬関数を実際に作ってみますが、そのまえに「いめーじ」としてどんな形になるのか、とりあえず示そうと思ってこんなふうにしてみました。自分で強化学習のシミュレーションをしたい場合、上記のような関数（離散状態なら行列形式でもよい）を問題に合わせて実装してやればいいことになります。

もしかしたら、こんな書き方ですっきり理解できるようになるのは、ボンクラな私だけかもしれませんが、S×A×Sです。と言われるより、この方が、あー、こんな感じで実装すればいいのね、というイメージがわきやすいと思います。ただし、こいつを「実装」する必要があるのは、問題自体が「疑似問題」である場合だけ。通常、「強化学習」をする場合「このTとかRが不明なので、最適な行動をとれるようにQとかVを学習しようね！」という状況にあるため、ように出てくることはない連中です（が、プロセスをマルコフ決定過程としてみる場合、重要な役者であります）。

さて、政治家問題に関して、遷移関数と報酬関数を次のように定義してみました。状態も行動も離散なので、この場合はわざわざ関数にしなくとも、行列にすればよさそうです（行列は関数とみなすこともできますしね）。まー、本来は「何らかの関数」とする方が（強化学習の理解に於いて）いいような気もしますが、面倒なので実装は行列にしました。

T = [ [ [0, 0,], [0, 0] ],
      [ [0, 0,], [0, 0] ] ]

# 各状況と行動に応じて、社会の状態が決まる。
# その遷移確率のテーブルを作る。
T[CORRUPTED][HONESTY][CORRUPTED] = 0.4
T[CORRUPTED][CHEAT][CORRUPTED] = 0.6
T[CORRUPTED][HONESTY][HEALTHY] = 0.7 # こうあって欲しい
T[CORRUPTED][CHEAT][HEALTHY] = 0.3
T[HEALTHY][HONESTY][HEALTHY] = 0.6
T[HEALTHY][CHEAT][HEALTHY] = 0.4 # ずるい奴は一定数いる
T[HEALTHY][HONESTY][CORRUPTED] = 0.1 # みんなが真面目なら世界は健全
T[HEALTHY][CHEAT][CORRUPTED] = 0.9 # いいことは長く続かない

R = [ [ [0, 0,], [0, 0] ],
      [ [0, 0,], [0, 0] ] ]

# 各状況と行動に応じて、政治家に対する報酬が決まる。
R[CORRUPTED][HONESTY][CORRUPTED] = -1.0 # 腐敗した世界では報われない。
R[CORRUPTED][CHEAT][CORRUPTED] = 5.0 # 腐敗した世界では悪い奴が正義
R[CORRUPTED][HONESTY][HEALTHY] = 9.0 # 改革に成功すると報酬大
R[CORRUPTED][CHEAT][HEALTHY] = -5.0 # 悪者は罰せられる（そうあって欲しいｗ）
R[HEALTHY][HONESTY][HEALTHY] = 3.0 # 真面目にやってもたいして報われない。
R[HEALTHY][CHEAT][HEALTHY] = 5.0 # ずるをした方が報酬は大きい。
R[HEALTHY][HONESTY][CORRUPTED] = -3.0 # こういう時は真面目なやつが損をする。
R[HEALTHY][CHEAT][CORRUPTED] = 7.0 # 世の流れに乗れれば悪者もはびこる。

どこが関数やねん、という気もしますが、どちらも（現在の状態、現在の行動、一ステップ先の状態）の組から「遷移確率」または「報酬」に対するマップになっていると考えれば、関数と言い張れないこともないと分かると思います。値は、適当に設定しました。本来、こういう例を出す場合、ちょしゃの方がちゃんと収束計算をして、アルゴリズムが正しく動いていたらこうなるはず、と示しをつけるのが通例ですが、わたしは計算は「にがて」ですので、値は適当に設定しました。ちゃんと収束するかって？知りませんｗ

一応、あまりに意味不明だと困るので、これについてもうちょっと説明します。マルコフ決定過程をシミュレーションするにあたって、どの状態で何をすると、どの程度の確率で状態遷移が起きるのか？を決めなければなりません。例えば下記の行は：

T[CORRUPTED][HONESTY][HEALTHY] = 0.7 # こうあって欲しい

腐敗した世界（状態０）にいるとき、正直な行動をとると（行動０）、世界の状態が腐敗⇒健全に遷移する確率は７０％にしよう、と決めていることになります。もちろん、元来これは「強化学習」の文脈で、学習しようとしている人（又はエージェント）が決める（直接知る）ことのできるパラメータではありませんが、今回は練習問題なのであらかじめ答えを決めて、学習アルゴリズムが（間接的に）世界の真実に気付くかどうかをシミュレーションしようという趣旨なので、私が独断と偏見により真実を定めます。

次に報酬についてですが、これも同じで状態sと行動aの組に対して、なんとなくそれっぽい値を返すように設定しておきます。

R[CORRUPTED][HONESTY][HEALTHY] = 9.0 # 改革に成功すると報酬大

ちなみに、一般に、環境と言われるものがこれらに相当します。私が知る限り、「強化学習」はある程度、環境が定常（このTとかRとかの写像関係が時間に従って変化しないもの）を想定しているのじゃないかなぁと思うのですが…この辺はちょっと自信がないぜ。

ともかく、まぁ、これらが今回、私がお勉強した成果を披露するためでっちあげた問題設定です。そして、「強化学習」を試しにやってみようと思った場合、このように「マルコフ決定過程」にそって問題の定式化を行う必要があります。これは疑似問題ではなく、本当の（？）問題を解く場合でも同じで、状態とか行動の集合は、TとかRが不明の場合でも、何らかの形で与えてやらなければなりません。また、貴方が解こうとしている問題が、上手く「マルコフ決定過程」として表現できるかも吟味しなければならなそうです。

ようするに、S、T、A、R（スターーーーーズ）を問題に合わせて決めるということが、強化学習を適用する際、最初に行わなければならない作業です。

学習の仕組み

さて、問題設定はできましたが、ここから、なにをどうすればいいのか？いま、マルコフ決定過程がS、A、T、R（スターーーーーズ）として決まっているので、例えば、ある状態sで行動aをとったときの報酬Rなどは確定的（又は確率的に期待値として）求めることができるという状況になっています。また、関数Tもわかっているので、状態s0と行動a0が決まれば、状態の集合Sの全要素に対して、遷移確率が決まっていることもわかっています。ここまで分かれば、後はある状態s0にいるとき、どうやってAの中から行動を選択するのか（方策π）さえ与えてやれば、とりあえずシミュレーションを走らせることが出来そうです。さて、方策πですが、これはどうすればいいのだろう？まずは、疑似コードを書いてみます。

# 方策π
# ある状態において、ある行動が選択される確率を返す。
# 入力：状態s、行動a
# 出力：状態sで行動aを選択する「確率」を返す。
#
def pi(s,a):
    pass

これが、なるべく元のπの定義に沿った書き方になるかと思います。ところで、先ほどのTとかRなどと違って、方策オン型の学習アルゴリズム（SARSAとか）では、こいつを具体的に書き下してやる必要があります。というわけで、中身がpassでは駄目です。ただし、この方策πと、強化学習によって得られる状態価値関数VやQ関数とは密接なかかわりがあるため、まずは先にそちらを見ていきます。

価値関数

さて、ここで新しい概念が登場するぞ！その名は価値関数（ここでエコーがかかる）。数学ができる人は、下記の数式をみて、まるっと理解してみよう。

これが価値関数だ！今まで通り、sは状態、πは方策、r(t+1)は時点t+1における報酬。新しく出てきたのは、このγというやつです。見ての通り、価値関数は「状態sで、方策πの確率密度に比例して行動を選択したときの、報酬の無限和にガンマを掛けたやつ」として定義されるのですが、この「無限和」というのが曲者で、これをそのまま計算すると、どの状態sにおいても報酬の和が無限というどうしようもない事態になってしまいます（報酬r>0のとき）。そのため、適当な割引率γ<1を決めてやって、総和が発散しないようにしているのですね。こうすることで、無限和をとっても期待値は一定の値に収束するわけです。

とまあ、計算上はそうなのですが、このγは割引率として解釈することもできます。割引率とは（経済を勉強したことがある方なら知っていると思いますが）「今日の一万円の価値は、一年後の一万円の価値より大きいです（インフレ率＋の場合）」というアレです。なぜならば、金利水準がプラスの時、銀行に一万円を預金すると、一年後の価値は(1+r)×一万円で、r>0なら価値が増加します。逆に言うと、タンス預金をしていたら、タンスの一万円の価値は銀行口座にある（利子込みの）一万円の価値に比べて1/(1+r)になるわけですから、（物価水準が金利に応じて増加するという半ば怪しい仮定のもとで）物価に対して減価していることになります。よって、（経済学者によると）銀行口座に入れたお金に利子がついたとしても、実は得になっているわけではないのです。損を防いでいるだけなんですね。ピンとこない方は、ジンバブエドルを思い出しましょう。

つまり、このγは単なる帳尻合わせではなく、強化学習の主体となるエージェントに対して、将来の報酬に対する減価率を与えているとも解釈できるわけです。あるいは、何事も無限には続かないので、将来的な利得の計算はあるところで打ち切ろう、という考えを反映しているとも解釈できる（と思う。たぶん）。そう考えれば、具体的な問題に適応する場合、どの程度の値にすればいいかは、うすぼんやりと見当がつくのではないかと思います。もし、今の行動が、ものすごく先の将来にまで影響する（状態に長期的な影響を及ぼす）のならガンマは大きめ、先々のことより今すぐが大事（リアルタイム制御など）の場合はガンマは小さめという感じですかね。まぁ、私は実務には携わってないので適当な意見ですが、多分そんな感じ。

さて、この価値関数は価値反復法や方策反復法という動的計画法っぽいアルゴリズムで計算できることが分かっているのですが、色々と面倒なので（そして、実装はしないので）この記事では、こいつとは別の価値関数を使って学習を行うことにします。それが、かの有名なアイツです。

出ました、Q関数。一時DQN、DQNと呼ばれて人気者だったあれですね。今では、もう誰もDQNなんて言わないですが、強化学習の枠組みの主役といえば、DQN。そしてDQNのセンターであるQに相当するのがこいつです。価値関数に形がよく似ていますが、引数として状態と行動の組を取っていますね！なんだか、こいつの値が分かれば、「ある状態sにいるとき、行動aをとると、長期的な割引報酬の総和」が計算できそうな気がしませんか（しますよね！）？

というわけで、やっとこさ、やっとこさ、やつの奴の脳天に一発ぶちかませたぜ…じゃないや、強化学習のかなめにたどり着きました。見ての通り、このQと言うやつが学習できれば、状態sにおいて、こいつの値が最大になる行動aを選ぶことが出来そうです。それは紛れもなく、私たちが探し求めていた最適なπに比例する値となりますのでπが分かったも同然です。

学習アルゴリズム

では、このQはどうやって学習すればよいのでしょうか？強化学習の枠組みでは「実際にやってみて」学習します。なんだか、私のようですね！スマートに推計したりするのではなく、泥臭くトライ＆エラーで各状態と行動における報酬の推移を観察して、Q値が収束するまで反復計算で求るという感じです。そう言ったアルゴリズムの中から、今回は二つ選んで試してみます。まず一つ目はSARSAというアルゴリズムだそうです。

SARSA

https://en.wikipedia.org/wiki/Sarsa_(singer)

ポーランドの歌手です。

数式です。

検索したら、二件引っかかったので、念のため二つとも紹介しておきます。この記事では、上のSARSAについては解説しません。さて、理屈はともかく、このありがたい数式で反復計算を行うと、アーレ不思議Q(s,a)の値がちゃんと収束して、学習ができるよ！ということのようです。この式にあるほとんどの項は、既にこれまでの説明でうすぼんやりとわかるかと思うのですが、新たにαという奴が出てきました。このαというのが、かの有名なラーニングレートと言うやつですな。コードにすると、こんな感じ：

# SARSAアルゴリズム
def sarsa(Q, s0, a0, r1, s1, a1):
    td = r1 + gamma * Q[s1][a1] - Q[s0][a0]
    return Q[s0][a0] + alpha * td

さて、このSARSAですが、方策オン型TD学習と呼ばれる区分（？）のアルゴリズムであり、状態sにおける行動aの選択基準は、とりあえずで与えてやらねばならぬもののようです。

この方策オンというのは、Qの更新がとりあえずの方策πに依存するアルゴリズムのことだそうで、Q学習とはその点が異なっているそう。また、TD学習というのは、遷移後の状態における価値関数の値を（とりあえず）用いることで、報酬の無限和を計算する方法の総称だそうです。確かに式を見てみると、そのように読み取れないこともないですね。遷移後の状態におけるQ(s(t+1),a(t+1))にガンマが掛け算されているのがミソでしょうか。一見すると、ワンステップだけ先読みするような感じに思えますが、たとえば、エージェントが適当な経路をぐるぐる回っているような状況で順にこの計算を行っていけば、Q(s(t),a(t))に対して、gamma * Q(s(t+1),a(t+1))-Q(s(t),a(t))の値が順次積算されてゆくことになりそうです。数式で、現時点の報酬Q(s(t),a(t))を引いているのは、現時点の報酬をダブルカウントしないようにするためだと思われます。

すると、斬化式を再帰的に計算する要領で、この項が割引報酬の無限和（実際にはシミュレーションステップ数分の和）に収束しそうな感じがします（うすぼんやり）。こういう再帰っぽい計算式のアルゴリズムって、ちょっとわかりずらいですよね。でも、まぁ、「こんぴゅーたさいえんてぃすと」がちゃんと収束を証明してくれているはずなので、我々一般市民はナイーブにそれを信じることにしましょう。

Q学習

さて、次にQ学習ですが、数式にすると次のようなものになるそうです。

SARSAとの違いは、将来的な割引報酬和の見積もりが「遷移先の状態Qにおいて取り得ることのできる行動の最大値」に置き換わっているところだけです。ただし、SARSAと違って、Q学習におけるQ値の更新は方策に依存しない方策オフ型です。これも、式を見るとうすぼんやりとわかりますね。遷移先の状態で「Q値が最大になるような行動」を用いてQ値を更新するので、特定の行動を選ぶための方策πがなくとも、Q値が計算できるということになりそうです。よって、SARSAとことなり、Q学習においてQ値の更新作業にπは影響を与えないと、そういう理解でいいのかな？（うすぼんやり）。というわけで、この辺がうすぼんやりな人は（私か？）下記のセクションでご紹介する記事なんぞを読んで、勉強するがいいぞ。

二つの違いについて

この二つの違いについて、興味深い考察が下記のブログでなされています。どうやら、Q学習は「遷移先において取れる行動によってもたらされる、報酬の最大値」によって今の状態における行動を決定するため、多少リスクがあっても（たとえば、遷移先の状態でミスると大きなペナルティが課せられる）果敢に攻めるような行動特性になるようです。あー、これは分かってないとダメそうですね。

うすぼんやりだと、こういうことに気づきずらいので、ちゃんとわかっている人の説明は貴重です。あと、Qiitaにもすごくよくまとまった記事がありました。こういうのを読んでみると、果たして自分が記事を書く意味があるのか！？疑問に思わざるを得ません！！！

なるほどねー。やっぱり、私は数式はダメじゃ。maxとるかとらないかの違いでそんなに変わる？という気がしていたのですが、特に一番目に紹介したブログの実験結果などは結構衝撃的です。というわけで、こういったアルゴリズムも「とりあえずQ学習が流行ってるから、Q学習で！」という感じで決めると、うまく行かない可能性もあるということですね。たとえば、下水のそばを歩くロボットの問題みたいな場合はね。

Q値を学習する

ただ、方策オンだろうがオフだろうが、実際に環境から報酬を得て、サンプリングしながらQ値を計算するわけですから、Qの「更新」に方策がいるかどうかはさておき、サンプリングのためには（とりあえずの）方策πが必要になりそうです。この記事では、例題のためTとかRをあらかじめ決めてやったわけですが、本来これは不明であり、状態sで行動aをとって報酬を観察しながらQ値を学習するというのが「強化学習」なのですから、行動のとりようがなければ学習もできません。方策オフであるとは、飽くまでQ値の更新に際してπが必要ないということに過ぎません。探索行動を行う以上、何らかの行動は選択できなければならないわけですから、とりあえずの行動指針は必要になります。というわけで、さっそく、（私がでっち上げた）例題を解くため、当面のπとして適当な方策を決めることを考えます。

探索行動

さて、最適なπはQ値の学習（更新）を通して手に入れるとして、とりあえずの方策（行動指針）はどうすればいいでしょうか。これについて、いくつかの具体案を出して、比較検討してみようと思います。

さて、今回、離散二値の社会的環境における政治家の学習過程という壮大なシミュレーションをするにあたり、政治家の行動モデルを提案しようと思います。まずは、「適当な政治家モデル」

# 政治家とは適当なものである。
def choose(A):
    return A[0] if np.random.uniform(0,1) < 0.5 else A[1]

これは、長年の心理学的観察に基づいた「政治家の頭は空っぽ」という普遍的真理を、たった一行の関数で実装したものです。これを、行動指針の候補の一つとしたいと思います！ランダム行動モデルと呼ぶことにしましょう。これをπのモデルとしてみると、取り得る行動aに対する一様分布を想定していることになります。ただ、aに対して0.5を返すだけだとシミュレーションできないので、乱数を入れ込んで「誠実か、ずるか」を半々の確率で選択するようにしています。

一方、ある研究者によると「政治家は、強欲で気まぐれである」といわれています。というわけで、そのモデルについても具体的な形を作って実装してみましょう（これが、かの有名なεグリーディーです）。

# 政治家とは強欲で気まぐれなものである。
def eps_greedy(A, s, Q, epsilon):
    if np.random.uniform() < epsilon:
        return choose(A)
    else:
        return A[0] if Q[s][A[0]] > Q[s][A[1]] else A[1]

いまのところ、Aは二値とわかっているので、あまり汎用的なコードではないですが、面倒くさかったのでこうなりました。この場合、確率εでランダムに行動を選択、それ以外の場合、Qという関数の値が最大になる行動を選ぶという方式になっております。これが、「強欲で気まぐれ」な政治家のモデルです。

さて、こんなんでちゃんと学習できるのでしょうか？結論から言うと、できるようです。この方策πというのは別段賢くなくても良いのです。私は高等な数学は分からないので、いまいち自信はないですが、どうやら方策πとは、サンプリング戦略のようなもののようです。よって、π自体が賢くなくとも、学習はできると思われます。πが関わってくるのは、いわゆる「探索・活用のトレードオフ」に関する部分のようです。

たとえば、εグリーディーのように、学習したQ値を「活用」するタイプのアルゴリズムなら、Qの学習が進むにつれていわゆる重点サンプリングのような効果が働き、Q関数の高い部分を重点的に探索するようになる、などなど。もちろん、サンプリングアルゴリズムが悪ければ、確率分布の一部しかサンプリングできなかったり、偏りが出たりということがあると思います。あと、収束が遅くなったりね。というわけで、「何でもよい」というものでもないのですが、最悪、上記のようにランダムサンプリングでも、Q値の値はちゃんと計算できます。というか、適当なπでもいつのまにかQの値を通して最適なπを学習することができる、というのが「強化学習」の肝に当たる部分のようです（このあたりから、どんどん自信がなくなってくる）。

もしかすると、途方もない勘違いなのかもしれませんが、「強化学習」って結局は報酬Rを最大化するような方策の確率分布πを推定する問題なのかも、という気もします。ただ、この辺、数学ができない私には、まだうすぼんやりな感じです。

学習する

これで、道具立てはそろったので動かしてみます。一応、振り返って手順をまとめると：

まず最初に、問題をマルコフ決定過程として定式化する。具体的には行動の集合A、Sを何らかのデータに落とし込む。
次に、遷移確率関数T(s0,a,s1)を関数や行列を利用して実装する。報酬R(s0,a,s1)に関しても同様に関数や行列で実装する。ただし、現実の問題を解く場合、TやRは所与のものであることが多い。今回は、強化学習の「練習」なので適当に設定する。
Q値を更新するためのアルゴリズムを選択する（今回はSARSAを使うことにする）。
Q値を更新するためには、実際に状態sで行動aを取り、報酬Rを測定する必要がある。そのためには、実際に状態sでどの行動をとるのか選ばねばならない。今回はランダムサンプリングとεグリーディーを利用して、結果を比べてみる。

まずは、環境に相当するものをエミュレートするため、状態の推移のためのコードと、報酬を出力するためのコードを書きます。まぁ、余計といえば余計ですが、後からいろいろいじくって実験したいので、関数として実装しておきます。

# 状況は確率的に推移する——最善の行動をとっても報われるとは限らない。
def transition(s,a):
    p0 = T[s][a][CORRUPTED]
    dice = np.random.uniform(0,1)
    return CORRUPTED if p0 < dice else HEALTHY

def reward(s0,a,s1):
    # 報酬は確定的（確率的にしてもよい）
    return R[s0][a][s1]

次に、適当な初期状態s0とa0から始めて、順次、行動の決定、状態の推移、報酬の取得を行うコードを書きます。これも、ワンステップ分を一つの関数として実装した方がよさそうです。そうしましょう。

# 当選一期分のシミュレーション
def step(s0, a0, Q):
    # 次の状態を取得する。T(s0,a,s1)に従い確率的に遷移する。
    s1 = transition(s0, a0)
    # 遷移先の状態s1における報酬を取得する。
    r1 = reward(s0, a0, s1)
    #a1 = choose(A)
    # 次のステップで取るべき行動はεグリーディーで選択。
    a1 = eps_greedy(A, s0, Q, epsilon)
    # SARSAでQ値の更新を行う。
    Q[s0][a0] = sarsa(Q, s0, a0, r1, s1, a1)
    # 遷移先s1と、s1で取るべき行動a1を返す。
    return s1, a1

これが、ワンステップ分のシミュレーションとなります。実際には、このワンステップを適当な数（100とか？）連続して行い、それをワンエピソードとします。そして、再び初期状態から始める…ということを何度か繰り返すそうです。ただし、今回の場合、終了状態（たとえば、状態sに達すると、終了。そこからの遷移先は空集合という感じ）がないので、別に「エピソード」ごとに区切らずともよい気もします。が、一応、後々そういうパターンを扱うことも考えて、エピソードごとに区切ってシミュレーションします。

# 政治家人生一回分のシミュレーション
def episode(s, a, N, Q):
    # 状態と行動の履歴を残す
    life = [(s,a)]
    for i in range(N):
        s,a = step(s, a, Q)
        life.append((s,a))
    return life

# 1000エピソードで学習
trials = 1000
# Q値は後々グラフを表示するため履歴を残す。
Qs = np.zeros((trials,2,2))
for i in range(trials):
    # 初期条件は「エピソード」ごとにリセット
    s0 = CORRUPTED # 世界は本質的に良くない。
    a0 = HONESTY # 政治家も人の子。
    life = episode(s0, a0, 50, Q)
    # Q値の履歴を更新
    Qs[i] = np.array(Q)

さて、いよいよ壮大なシミュレーション実行の時が来ました。おもむろにIDLEXのF5を押して、実行してみます。

学習できているっぽいです。ブログの記事などでよく見るグラフですね。今回の例だとQ値は（腐敗、誠実）、（腐敗、ずる）、（健全、誠実）、（健全、ずる）という状態sと行動aの組み合わせに対する関数なので、値が４つあります。見ると、二つはなんとなく収束していますが、残りの二つはちゃんと収束してないみたい。一応、結果を見てみます。

>>>
Q(CORRUPTED,HONESTY)=5.1132318541939075
Q(CORRUPTED,CHEAT)=0.8140231450594659
Q(HEALTHY,HONESTY)=-0.6698088374171418
Q(HEALTHY,CHEAT)=15.147652583055166

晒したコードには載せていませんが、一応Q値を出力するようにしています。どうやら、「腐敗した世界では正直」に、「正直な世界ではずるをする」のが、政治家としては最良の選択のようです。まぁ、問題を設定したときに思っていた感じになりました（結果ありき）。ただし、腐敗した世界でずるをする場合と、健全な世界で正直に振舞う場合についてはQ値がうまく収束していません。おそらく、健全な世界で真面目の場合と不正な世界でずるをする場合、世界の状態が移行したときペナルティを与えるよう報酬関数を設定したので、そのせいかも（一応、コードの断片を再掲します）。この辺、ちゃんと割引報酬和を計算してみたら、正しい答えが分かるのでしょうが、それが面倒なので学習アルゴリズムを書くのだ、ということを思いだせば、まあいいや、という気になります（アルゴリズムの確認のためなのだから、本来それじゃダメ、というのは分かっているのだよ、念のため）。

# 各状況と行動に応じて、政治家に対する報酬が決まる。
...
R[CORRUPTED][CHEAT][HEALTHY] = -5.0 # 悪者は罰せられる（そうあって欲しいｗ）
...
R[HEALTHY][HONESTY][CORRUPTED] = -3.0 # こういう時は真面目なやつが損をする。

ちなみに、下記が最後の一エピソードにおける行動の履歴になります。

CORRUPTED HONESTY
HEALTHY HONESTY
CORRUPTED CHEAT
HEALTHY HONESTY
CORRUPTED CHEAT
CORRUPTED HONESTY
CORRUPTED HONESTY
HEALTHY HONESTY
CORRUPTED HONESTY
CORRUPTED HONESTY
CORRUPTED CHEAT
HEALTHY HONESTY
CORRUPTED CHEAT
HEALTHY HONESTY
CORRUPTED CHEAT
CORRUPTED HONESTY
CORRUPTED HONESTY
HEALTHY HONESTY
CORRUPTED CHEAT
CORRUPTED HONESTY
CORRUPTED HONESTY
CORRUPTED HONESTY
CORRUPTED HONESTY
HEALTHY HONESTY
CORRUPTED CHEAT
HEALTHY HONESTY
CORRUPTED CHEAT
HEALTHY HONESTY
HEALTHY CHEAT
HEALTHY CHEAT
HEALTHY CHEAT
HEALTHY CHEAT
HEALTHY CHEAT
HEALTHY CHEAT
HEALTHY CHEAT
HEALTHY CHEAT
HEALTHY CHEAT
HEALTHY CHEAT
HEALTHY CHEAT
HEALTHY CHEAT
HEALTHY CHEAT
HEALTHY CHEAT
HEALTHY CHEAT
HEALTHY CHEAT
HEALTHY CHEAT
HEALTHY CHEAT
HEALTHY CHEAT
HEALTHY CHEAT
HEALTHY CHEAT
HEALTHY CHEAT
HEALTHY CHEAT

どうやら、このシミュレーションの安定点は、健全な社会で不正をする、ということになるようです。腐敗した世界で、正直な政治家として出発した若者が、不正をすることを覚え、社会は不健全になるが、不健全な社会で誠実に振舞うことが、長期的には利益になるということを学習して心を入れ替えた結果、再び社会は健全さを取り戻す。しかし、主人公は、すでに健全な社会では不正をした方が得をするということを学習してしまっているため、「健全な社会で不正をする」というのが安定点と言う、なんとも後味の悪い結果になりました。

次にコードを修正して、当面の行動指針として乱択アルゴリズムを用いる場合も試してみました。

学習過程が全体的に不安定になっていますね。学習したQ値を使わないので、ぶれが出ている模様です。ちなみに、この場合、「頭が空っぽ」の政治家ですので、行動はランダムになるはずです。一応、ちょっと見てみましたが、行動指針が全くないのであまり面白くないですね。ランダムなので、ドラマ仕立てにはならない。まー、当たり前ですね。

CORRUPTED HONESTY
CORRUPTED CHEAT
HEALTHY CHEAT
HEALTHY HONESTY
...（面白くないので省略）...
CORRUPTED HONESTY
CORRUPTED CHEAT
HEALTHY CHEAT
HEALTHY HONESTY
CORRUPTED HONESTY
HEALTHY CHEAT

ランダムに行動している様子が分かります。それでも、Q関数がちゃんと収束しつつあるように見えるのは、SARSAアルゴリズムがちゃんとQ値の更新を行ってくれているからでしょうか。ようするに、当面の行動指針として適当なものを選んでも、Q値はそれなりに収束するようです。ただし、εグリーディーの場合と異なり、得られたQ値は（当面の方策の影響か）ちょっと違う値になっています。

>>>
Q(CORRUPTED,HONESTY)=6.20323015026619
Q(CORRUPTED,CHEAT)=2.2786916313550583
Q(HEALTHY,HONESTY)=0.4864887524489936
Q(HEALTHY,CHEAT)=8.201714889286968

まとめ

強化学習というと難しい感じがするが、難しいのはむしろQ関数を近似したりしている所かも。強化学習自体は概念としても理解するのがそれほど難しくなく、また、にょろにょろやでんでんむしも出てこない。よって、頑張れば数学音痴でも理解はできそう。一応の実装はできたが、使い道がまだ思いつかねーや。もし、なんか面白そうな応用があったら、追ってお知らせする、では。