強化学習の基本、行動価値関数について

f:id:s0sem0y:20170505075102p:plain

強化学習での行動評価
- 学習の仕方の違い（上記の記事の軽いおさらい）
  - 教師あり学習と教示
  - 強化学習と評価
- 評価をするための行動価値関数
  - 知識利用と探査
行動価値関数
- 行動価値関数の考え方
  - 報酬の標本平均
  - 漸化式への変形
- 行動価値関数更新の解釈と拡張
最後に

強化学習での行動評価

今回の記事は下記の記事の続きという感じで書きます。

以下の記事は強化学習の想定しているシーンや、その特殊な例であるn本腕バンディット問題などについて紹介しています。

s0sem0y.hatenablog.com

学習の仕方の違い（上記の記事の軽いおさらい）

教師あり学習と強化学習の最たる違いは学習の仕方です。

どのような情報を元に学習を行うのかが全く異なります。

教師あり学習と教示

教師あり学習では、あるデータが入力された際にシステムが出力すべき答えを明確に提示します。例えば０〜９の１０個の選択肢があり、その中からシステムがどの選択肢を選ぼうとも、答えが６であれば、答えは６ですよと教示します。

システムがどのような選択肢を選ぶかなんて構いません。２を選ぼうが４を選ぼうが、答えは６ですよと伝えます。ある入力に対して、その答えを完全に対応付けて教えるため、事実上システムが選ぶ選択肢のことなどどうでも良いのです。

現在のシステムでは違う選択肢を選んでしまうという、本来あるべき姿からの誤差を使って学習をするため、学習の過程で選択肢を選ばせることを行いますが、どれを選んだのかは実はそれほど重要ではありません。

強化学習と評価

強化学習では、ある環境下でシステムが行った出力に対して、その評価を返します。例えば０〜９の１０個の選択肢があり、その中からシステムが７を選んだのなら、その選択肢は「２１点」という具合に評価するのです。

ここで２１点が高いのか低いのかは、他の選択肢の評価と比べてみないことには分かりません。そして、この２１点という評価自体も経験的にその程度だろうと推定しているに過ぎなく、今後その値が変化することが考えられます。これは教示とは比べ物にならないくらい不確かな情報であることが理解できるはずです。

他の選択肢ならばどうであったのか、評価は高かったのだろうか、あるいは今の評価値自体正しいと言えるのだろうか。これらを総合的に試行錯誤しながら見つけていかなければならないのが強化学習です。

評価をするための行動価値関数

知識利用と探査

$t$ 回目の試行において、行動 $a$ を選択した場合の行動価値を返す関数を行動価値関数 $Q_t(a)$ とします。

強化学習においては、いろいろな行動を試しながら、この $Q_t(a)$ を推定していかなければいけません。推定された $Q_t(a)$ を用いて、最も価値が高い行動 $a$ を選ぶ、すなわち

$\arg\max_aQ_t(a)$

を選ぶのが、貪欲法と呼ばれる方法であり、現在までに得られてる知識を利用するという考え方です。一方で、利用ばかりを考えていると、行動価値関数の推定が進みません。もしかしたら他の行動の方がもっと価値が高いのかもしれないと考え、時には試しに他の行動を取ってみることもしなければなりません。これを探査と言います。

利用と探査のバランスを考えるための行動選択の指針として、ε-貪欲法やソフトマックス行動選択などがありました。

行動価値関数

今までは行動価値関数があったとして、どのように行動を選択するのかや、利用と探索のバランスが必要であるということを述べてきました。しかし行動価値関数自体も、あくまで過去の行動から推定していかなければなりません。

そのための行動価値関数の基本を抑えていきます。

行動価値関数の考え方

報酬の標本平均

n本腕バンディット問題において、価値とは、行動によって選んだ腕によってスロットマシンが放出する平均的な報酬です。例えば、ある腕を選ぶことで、スロットマシンが報酬を出してきます。過去の報酬額をすべて平均していけば、現在のその腕の価値を見積もることができます。

つまり、とある腕を選ぶという行動を $a$ として、これまで $k_a$ 回、その行動を取ったとしましょう。１回目には $r_1$ の報酬が得られ、2回目には $r_2$ が得られ、 $k_a$ 回目には $r_{k_a}$ の報酬が得られてきたわけですから、この腕の価値は

$\displaystyle Q_t(a) = \frac{r_1 + r_2 +...+r_{k_a} }{ k_a}$

と見積もることができます。これは単に、これまでの報酬の標本平均によって価値を推定していることになります。スロットマシンで言えば、もしかしたら、ほとんどの報酬が0であり、たまに大きな報酬として１００万円などを放出するかもしれません。

もっと一般的な問題を考えるうえでは、小さな報酬を与えてくる場合や、時として異なる報酬が出ると考えておけばいいでしょう。

漸化式への変形

標本平均を用いた行動価値関数の記述では、これまでの全ての報酬を保存して置かなければなりません。別に数式上では問題ありませんが、コンピュータに計算させる場合にはメモリの無駄遣いと言えます。実際には漸化式による更新式の形で記述することができます。

ここで、 $Q_t(a)$ は $t$ 回目における行動価値関数となりますが、行動価値関数は、各行動 $a$ について個別に見積もっています。 $a$ を $k$ 回試行したならば、その $k$ 回の標本平均によって計算しているだけでした。

従って、ここでは行動 $a$ にのみ着目することにして、今まで行動 $a$ を $k$ 回選択したとしましょう。従って、現時点での $a$ の行動価値は

$\displaystyle Q_k = \frac{r_1 + r_2 +...+r_{k} }{k}$

と表記しておけます。では、 $k+1$ 回目に報酬 $r_{k+1}$ が得られた場合は

$\displaystyle Q_{k+1} = \frac{r_1 + r_2 +...+r_{k}+r_{k+1} }{k+1}$

と書かれることになります。 $Q_k$ を用いてこれを記述し直すのが目標です。以下変形を書いておきます。

$\displaystyle Q_{k+1} = \frac{r_1 + r_2 +...+r_{k}+r_{k+1} }{k+1}$

$\displaystyle 　　　 = \frac{1}{k+1} (r_1 + r_2 +...+r_{k}+r_{k+1} )$

$\displaystyle 　　　 = \frac{1}{k+1} \left( \frac{k(r_1 + r_2 +...+r_{k})}{k}+r_{k+1} \right)$

$\displaystyle 　　　 = \frac{1}{k+1} (kQ_k+r_{k+1} )$

$\displaystyle 　　　 = \frac{1}{k+1} (kQ_k +Q_k - Q_k +r_{k+1} )$

$\displaystyle 　　　 = \frac{1}{k+1} \{(k+1)Q_k - Q_k + r_{k+1} \}$

$\displaystyle 　　　 = Q_k + \frac{1}{k+1} (r_{k+1} - Q_k )$

この形式であれば、前回までの価値と、行動 $a$ を選んだ回数 $k$ だけを保存しておけばよく、新しく得られた報酬 $r_{k+1}$ を使ってちょっと計算するだけで済みます。この形式の更新式は強化学習の多くのシーンで見られるので是非覚えておきましょう。

行動価値関数更新の解釈と拡張

行動価値関数の更新式

行動価値関数が以下の更新式で表されることを見ました。

$\displaystyle Q_{k+1} = Q_k + \frac{1}{k+1} (r_{k+1} - Q_k )$

これは、言葉を使って書きなおせば

$新しい価値＝古い価値＋ステップサイズ×(目標値-古い価値)$

と表すことができます。最新の報酬の情報と、（過去の情報で見積もった）古い価値との差を、今までの行動選択回数の逆数を係数として、更新量にしています。最新の報酬こそ目標値であると考えている点に注意してください。

言い直しになりますが、最新の報酬を目標値として、古い価値との誤差に係数を掛けて更新をしている非常にシンプルな式に見えます。

ここで、目標値との誤差に乗じている係数 $\frac{1}{k+1}$ をもう少し工夫することで、いろいろな更新方法を考えることができます。

指数減衰加重平均更新式

以下の更新式において、一旦添字を１つずらしておきます。（本質は何も変わりません）

$\displaystyle Q_{k+1} = Q_k + \frac{1}{k+1} (r_{k+1} - Q_k )$

$\displaystyle Q_{k} = Q_{k-1} + \frac{1}{k} (r_{k} - Q_{k-1} )$

と書いておきましょう。ここで、右辺第二項の係数 $\frac{1}{k}$ について、もっと一般的に $α_k$ と書き表しておくことを考えます。つまり

$\displaystyle Q_{k} = Q_{k-1} + α_k(r_{k} - Q_{k-1} )$

と表記するということです。この $α_k$ を $k$ の値によっていろいろ変わる方式にしてもいいですし、実は定数にしてしまっても構いません。ここでは $α$ は区間 $(0,1]$ の定数としておきます（例えば0.9)。

この場合、漸化式を解いて表記してみると

$\displaystyle Q_{k} = Q_{k-1} + α(r_{k} - Q_{k-1} )$

$\displaystyle 　　　= αr_k + (1-α)Q_{k-1}$

$\displaystyle 　　　= αr_k + (1-α)αr_{k-1} + (1-α)^2 Q_{k-2}$

$\displaystyle 　　　= αr_k + (1-α)αr_{k-1} + (1-α)^2 αr_{k-2} + ...$

$\displaystyle 　　　　+ (1-α)^{k-1}αr_{1} + (1-α)^kQ_0$

$\displaystyle 　　　= (1-α)^kQ_0 + \sum_{i=1}^k α(1-α)^{k-i}r_{i}$

第一項は価値の初期値であり、適当に与えるよりほかありません。第二項以降は、古い報酬ほど小さな重みが与えられており、過去全ての報酬の加重平均になっています。

すなわち、過去の報酬の情報はさほど重要ではないと考え、最新の報酬をより重要視して価値を決定していることになります。

価値を今までの報酬の標本平均にする方法は、スロットマシンの報酬が、腕によって完全に固定されている（定常である）ならば、上手く行きそうな方法でした。今回の方法で価値を更新していくならば、より新しい報酬を強く反映するため、スロットマシンの報酬が非定常で刻一刻と変化していく場合に対応できます。

実際、多くの実問題においては、取るべき行動が変化するケース（すなわち行動に対する報酬が変化するケース）が多いはずであり、行動の価値を決める場合に新しい情報を強く反映するというのは有効に働くはずです。

オプティミックス初期値

価値を更新式によって算出する上では、初期値を与えておかねばなりません。この際には、オプティミックス（楽観的）に初期値を与えることが良いとされています。

楽観的に初期値を与えるというのは、価値を高めに設定しておくことに相当します。強化学習では、価値を推定することをしていくのですが、本来の価値より高めに見積もられてしまっているものを、真の価値に収束させるのと、低めに見積もられているものを真の価値に収束させるのでは、前者のほうが上手くいくとされています。

高めに見積もった価値は、行動として選択されやすくなりますが、実際には高く見積もりすぎているに過ぎなく、「価値はもっと低い」という更新を受けます。すると、選択肢の中で他の価値が選ばれやすくなるため、探査が起こる可能性が高くなるためです。

下の例では、楽観的に見積もったお陰で、システムは価値を下方修正し、いろいろな選択肢を試すようになっています。（１．上　２．下　３．おそらく真ん中が選ばれるでしょう）

f:id:s0sem0y:20170428010254p:plain

もしも全ての選択肢を低めに見積もってしまえば、最初に選ばれた行動は、「価値がもっと高い」と判定を受け、以降も選択されやすくなってしまい、十分な捜査をすることなく学習が（局所的な解へ）収束してしまうことが想定されます。（ずっと真ん中が選ばれがちに）

f:id:s0sem0y:20170428010312p:plain

最後に

今回は強化学習の基本となる行動価値関数について紹介しました。しかし、まだ本来の強化学習まで到達していません。

現在扱っているのは、選択肢の価値が定まっているがわからない場合に、価値を推定しながら知識利用と探査を上手く織り交ぜて学習していく方法です。また、指数減衰加重平均によって、価値が変化していくケースにも対応できることを見ました。

しかし強化学習が扱うタスクは更に複雑であり、システムが取った行動によって、環境や状態が変化していくケースを想定しなければなりません（現在はまだ想定されていない。価値の推定と、それに基づいた行動選択の仕方を述べているだけ）。

例えば、システムの取った行動によって、スロットマシンが態度を変えてくるような場合はどうでしょう。こちらもただ過去の知識を利用するのではなく、スロットマシンの態度を見て選択の仕方を調整すべきでしょう。環境とエージェント、観測や状態や方策などの言葉が今後出てくることになります。

何はともわれ基本的なことを抑えて、その後必要性を確認した上で複雑な問題に発展させていかなければ、十分な理解は得られないと思うので、ゆっくり勉強していきましょう。