\documentclass[a4j]{jarticle} \usepackage{graphicx} \begin{document} \title{強化学習の基礎} \author{講　　師：小池 康晴・鮫島 和行\\ レポーター：根本 憲・浦久保 秀俊} \date{2001年 4月 6日 金曜日} \maketitle \section{はじめに} 川人さんが提案されたフィードバック誤差学習などの中にはフィードバック コントローラというものが常に入っています。私が強化学習を始めたきっかけ は、このフィードバックコントローラがどのように学習されるのかが知りた いというものでした。昨日、Bartoの論文中にActor‐Criticの話が出てきまし たが、ここで Actor はまさしくフィードバックコントローラの役割をしてお り、それが何らかの報酬を与えることで学習ができるのです。そこで、この Actor - Criticの強化学習を使ってフィードバックコントローラを学習するよ うなものを作ろうと思い、強化学習の研究を始めました。私は当時、たまたま 自動車をつくっている会社にいたので、現在も車を運転するモデルに関して研 究をしています。入力情報として道路と車の間のずれや速度等を入れ、また報 酬として道の上にのっていればゼロ、道から外れれば罰として−1を与えると いった簡単なものでも、いろいろな道幅を走らせればちゃんと学習して速度に 応じて安全に道路を走るといった行動ができるようになります。初日の 銅谷さんのビデオでロボットが立っていたような話もありますし、今では強化 学習がそういったいろいろな制御に応用できる可能性があることが徐々に分かっ てきています。 \section{強化学習とは？} \subsection{教師あり学習との違い} 　強化学習は "環境との相互作用による学習"であると言えます。実際何か行 動してみて(例えばポインティングであればポインティングしてみて)、ちゃん としたターゲットについていたら報酬（サルだったらジュース）を与えるとい うように、自分から環境にはたらきかけて環境から報酬をもらえるといった相 互作用により学習していくというものです。また、ターゲットに向かっていく というようなものを使って学習していくということから、“ゴール指向型の学 習”とも言えます。この強化学習が教師あり学習と一番違うところは、どうや って手を伸ばすか、筋肉を活性化させるかという教師信号は全く与えず、ター ゲットまで手を伸ばせ、といったように行為に対して報酬を与えることで学習 できるという点であり、そこが面白いところではないかと思います。 　テキストの最初の方に赤ちゃんの話しが入っています。（赤ちゃんが寝返り したビデオを示しながら）この赤ちゃんは生後半年くらいであり、寝返り ができるようになって２・３日目ですが、赤ちゃんが寝返りしたり立って歩く ようになるのは、別に何をしろと教えているというわけではありません。これ が強化学習であるかどうかは判りませんが、教師あり学習ではありません。ど の赤ちゃんでも寝返りすることから、遺伝的に組みこまれていると考える人も いるかもしれません、しかし、赤ちゃんの体格は生まれてから半年で倍くらい になりますし、それからも徐々に成長していくことを考えると、人間の腕や足 は脳にとっては環境と同じ外界のものです。そのため、それを動かしながら学 習するということと併せて、強化学習に近いものが使われていると考えられま す。 　次に、教師あり学習と強化学習との違いについてです、教師あり学習は正し い行動というものがどういうものかが明確に示されているのに対し、強化学習 というのは正しい行動というのは与えられず、試行錯誤を通じて環境に適応し ていきます。教師あり学習は、ターゲットと実際の出力の差をとる、フィード バック誤差学習だと言えます。一方強化学習は、出力に対してなにか評価（報 酬とか罰）を与え、将来的に報酬が最も多くなるよう学習していくことでシス テムを良くしていきます。 \subsection{制御との関係} （Bartoの論文の図11.A,Bを入れる) 　強化学習を制御の視点から考えると、（図11.A）の様になります。 図中、Controller は、Contextとフィードバック信号との差を入力として、出 力をおこないます。川人さんのフィードバック誤差学習の話にもあるように、 Controller が良いものでなければ、フィードバック誤差学習で制御対象の逆 モデルを学習しようと思ってもいい逆モデルができません。このようなシステ ムにおいて、Controller をどのように設計するのか私にとってはわかりませ んでした。次に、先程の ControllerをActorにかえます（図11.B）。昨日の論 文にあるように、このActor-Criticという形式だと、環境（Controlled System） からの出力をContextを使って評価して評価信号というものを作り、それを用 いて Critic と Actor 両方を学習していくといった関係になります。ですか らフィードバック誤差学習の良いところは実際に運動しながら学習できるとこ ろにあり、順逆モデルの様に順モデルをまず学習しておいてそれを使って逆モ デルを学習しようといった順番はなくて、両方同時進行で、オンラインでど どん学習できます。順モデル、逆モデル、フィードバックコントローラが学習 しながら獲得できるのです。 　また、目標軌道の入力方法も問題になります。車の例であれは、車に乗って いると道路は見えます。それがActorにきて、今どこにいるのかがわかります。 それだけで、目標軌道がなくても道から外れないように運転するという方策を 学習しているので、道からそれないようにどんどん走っていきます。よって軌 道計画というのは特になくても、道の状況と実際の車の現在の状況を入れてあ げることで動かすことができます。そういうことから、強化学習は軌道計画や 運動学習を全部同時に考えていく枠組にもなっているのではないかと最近では 思っています。 \subsection{強化学習の要素} 　強化学習の要素には、 　１．Policy 　２．Reward function 　３．Value Function の３つがあります。Policyというのは”行動を決めるルール”です。例えば Random Policyといったら、迷路の問題で上・下・右・左4つの方向に動ける状 況において、上・下・右・左に行く確率が等確率で起こるというものです。こ の Policyを決めることで目的に達することができます。Reward functionとい うのは”ある状態において獲得できる報酬”のことをいいます。先程の車の例 でいうと、道から外れたら報酬は−１、道の上をどんどん走れていったら＋１ づつ、というようにルールを与える事です。仮に、できるだけ長く走ることを 目的とすると、この報酬を最大化することが長く走ることになります。どうい う報酬を与えるかというのも自分で決めなければならないのです。Value Functionというのは、”将来にわたって獲得できる報酬の総和”のことをさし、 状態の価値（State-Value Function）を判断することと、行動の価値 （Action−Value Function）を判断することの２種類があります。 これら３つの要素、 Policy、Reward function、Value Functionを決めるこ とで強化学習を行うことができるのです。 ＜演習＞ 　演習問題の前に、n-Armed Bandit問題について説明します。 ・The n-Armed Bandit Problem 　まず、スロットマシーンがn個あって、そのレバーを引くと、いくつかはわ からないですがコインがでてくる状況を考えます。この時、例えば1000回プレ イしてコインをできるだけたくさん出すにはどういう方策をとったらいいのか、 という問題が n-Armed Bandit 問題です。1回1回レバーをひくことをプレイと 呼びます。それぞれのプレイでレバーをひくとコインがでてくるので、そのコ インが報酬として与えられます。これは例えば平均的には5個出るとしても、 確率的なので分散によって2個だったり6個だったりいろいろでてきます。よっ ていくつでてくるかというのは、経験から予想しなくてはなりません。すべて のスロットマシーンがどれだけでるかということがわかれば（推定できれば） どれを選択すればいいのかということがおのずと決まってくるので、行動価値 を推定するという問題になります。 　このときに2つの言葉、ExploreとExploitというのがあります。平均的は5個 でてくるとしても、4個だったり6個だったり7個だったり１回に出る数はいろ いろなので、実際にでてきた値だけを信じていると、レバーを1回引くだけで は1番最大の報酬が出てくるものを探すということはできません。ですから、 色々な行動を探索します（Explore）。今までの経験では2番目のスロットマシ ーンがたくさんでてくるのだけれども、他にもっといいものがあるのではない かと思って隣のやつを引いてみる。人間でもいろいろな行動を探索しますが、 そういったことです。だけど、いつも適当にやっていると最大の報酬を得られ ることはありえません。ですから最も良い行動を利用しなくてはならない (Exploit)のですが、数をこなさないと確率的にどれがどのくらいでてくるか はわからないので、実際にレバーを引いてみるといった行動（Explore）も必 要です。 　ですから、Explore、Exploit両方必要なのですけれども、Explorationと Exploitationをどれだけの割合でしたらいいかといった問題がでてきます。 Exploitationというのは一番いいものだけを選んでくることですが、たまには そうでないのも選んでみたとき（Exploration）に報酬がどれだけ返ってくる かというのを評価することでよりよい評価関数（Value Function）を作ろうと いうような方策をとります。 　ここでQ（行動価値）をどうやって推定するかという話になります。例えば さっきの例でt回レバーを引いたとき、その中で２番目のスロット選択（行 動a）を$k_{a}$回選択したとすると、 \begin{eqnarray*} Q_{t}(a)&=&\frac{r_{1}+r_{2}+・・・+r_{k_{a}}}{k_{a}}\\ 　\lim_{ka\rightarrow\infty}Q_{t}(a)&=&Q^{*}(a) \end{eqnarray*} となります。ここで、$r_{1},r_{2},・・・,r_{k_{a}}$は各回の報酬です。これは それぞれでてきた報酬をたして$Ka$回で平均を取ったものに対し、$Ka$を無限大に することによりスロットマシーンの価値関数がわかるので、こういった方法で Action-Valueの推定を行うというやり方があります。 　行動の乱雑性導入の仕方にはいくつか方法がありますが、その中に $\epsilon$−greedyという方法があります。これは$1-\epsilon$の確率でExploitするのです が、$\epsilon$の確率だけExploreするというものです。$\epsilon$−greedyというのは ExplorationとExploitationをバランスさせる一つの方法になります。では$\epsilon$ をどうやって決めたらいいのか、どれだけランダムにやったらいいのかという 話しがでてきます。それは環境によっても依存するのですけれども、$\epsilon$を変え ると得られる報酬がどう変わるかを演習を通じてみてもらいたいと思います。 ＜演習課題＞ 　$\epsilon$-greedyによってThe n-Armed Bandit Problem解くMATLABプログラム narmband.mを用いて、各確率$\epsilon$を変化させた場合の学習曲線をプロットせよ。 また、もし1000回プレイする場合に、最も多くのコインを得るには$\epsilon$をどのよ うに設定すればいいだろうか。 ＜結果＞ 　（鮫島先生の結果の図をのせる） 　このグラフは$\epsilon$をパラメータとしたときの、プレイを1000回と限定してもら える報酬を最大にしようと考えたときの行動価値Qのグラフです。X軸が$\epsilon$、Y 軸がQを表しており、Qは100回平均したものになっています。このグラフから、 $\epsilon=0.07$付近で最大になっていることがわかります。すなわち、$\epsilon=0.07$がこ の場合最適な$\epsilon$であると考えられます。 Q この場合、解析的にどの$\epsilon$が最適なのか求められないのですか？ 答 スロットの特徴や再帰的な報酬の値の分布がわかっていれば求められるか もしれません。 \section{環境との相互作用} \subsection{Return for Continuing Tasks} 今の n-Armed Bandit 問題はすごく単純な例で、状態といいうものがなくい つも同じ状態にいたようなものです。例えば部屋がいくつかあってそれぞれス ロットマシーンがおいてあり、どの部屋のスロットマシーンがいいのか選ぶよ うになっているというものです。ここでは環境との相互作用で学習していくと いう話について述べたいと思います。 　Agentが何か行動を起こすと報酬が得られますが、それと共に状態も更新さ れる、という状況を考えます。そうするとある状態$S_{t}$である行動$a_{t}$を起 こすと、報酬 $r_{t+1}$ がもらえて状態が$S_t$から$S_{t+1}$になり、そこでまた 新しい行動$a_{t+1}$とをとると報酬$r_{t+2}$が得られ、状態も$S_{t+2}$に変わる、 というように状態と行動が遷移します。 　これから$\pi_{t}(s,a)$という変数をもちいますが、これは状態$s$で$a$をとると いう確率を表します。強化学習は経験からいかに方策(policy)$\pi$を改善するか という問題です。状態がずっと遷移していって、それぞれの状態遷移のときに、 おのおの報酬がもらえていたわけですけれども、長い試行を通して一番報酬が 多く得られるような方策を決めるというのが問題になります。 　またタスクとして、コンティニュアスタスクとエピソードタスクという2つを考 えないといけませんが、discount factor $\gamma$を入れることにより同じように考 えることができます。つまり、報酬を \begin{eqnarray*} 　　R_{t} &=& r_{t+1} + \gamma r_{t+2} + \gamma^{2}r_{t+3} + \cdot \\ &=& \sum_{k=0}^{\infty} \gamma^{k}r_{t+k+1} \end{eqnarray*} とすれば、γを0から1の間にすることですごく遠い将来のものは、階乗できい てきますのでほぼゼロになって、Rは無限大に発散することがなくなって和が 求まることになります。この式は$\infty$の部分を$T$(最終時刻）にすることで、$\gamma$を １にしてエピソードタスクを表現できることになります。しかし、先程の$\epsilon$と 同様に$\gamma$もどう決めるかというのは一般的には分からないので、試行錯誤的に 決めているというのが現状です。 \subsection{マルコフ性} 　強化学習というのはマルコフ性というのを仮定しています。本当は 　　 $ Pr\{s_{t+1}=s',r_{t+1}=r|s_{t},a_{t},r_{t},s_{t-1},a_{t-1},\cdots ,r_{1},s_{0}.a_{0}\} $ なのですが、マルコフ性を仮定してt+１の応答は1個直前の状態とアクション によって決める、すなわち $ 　　Pr\{s_{t+1}=s',r_{t+1}=r|s_{t},a_{t}\} $ としています。この場合、状態とアクションのセットが与えられると、ある状 態である行動をとったときに次の状態s'に行く確率を考えることができます。 それは遷移確率（$P_{ss'}^{a}$)と呼ぶものです。また、$s$という状態で$a$という 報酬が得られて$s'$に行ったときに、得られる報酬の期待値というのを $R_{ss'}^{a}$と書きます。遷移確率と報酬の期待値があると、先程の迷路の問 題のように右・左・上・下に行くといった4つのパターンしか動けないものを 考えた場合、現在のますより右に行くのを決定論的にしたければ、右に行く確 率を１にすればいいし、確率的に動かしたければ0.9の確率では右に行きあと の0.1の確率はランダムに動いてどこに行くかはわからないという条件にすれ ばいいといったことになります。そういう風に確率が分かっていると状態がど のように遷移していくのかが記述できるわけです。その時にどれだけ報酬がも らえるかというのがわかっていれば、先程$s_t$で$a_t$をとったときに$s_{t+1}$に 行くといった状態遷移がありましたが、これが全部記述できることになります。 また$R_{ss'}^{a}$がわかっていれば、環境に相互作用してぐるぐる回っていく ときにどういう状態遷移をして、そのときにどういう報酬を得られるかという のが全てわかります。 \subsection{Valuen Functions} $R_{ss'}^a$がわかっていればどういう報酬を得られるかというのが全てわ かりますが、そうすると価値関数が計算できます。価値関数には状態価値関 数と行動価値関数の2つがあります。状態価値関数は \begin{eqnarray*} 　　V^{\pi}(s) &=& E_{\pi}\{R_{t}|s_{t}=s\} \\ &=& E_{\pi}\{\sum_{k=0}^{\infty} \gamma^{k}r_{t+k+1}|s_{t}=s\} \end{eqnarray*} と書け、ｔの時刻におけるある状態ｓについて、それ以降どれだけ報酬がもら えるかという価値関数を表しています。ここで、時刻ｔで状態ｓにいることが 条件となります。また、「状態ｓで行動aをとると、どのくらい報酬が得られる か」を示す期待収益は、 \begin{eqnarray*} 　　Q^{\pi}(s,a) &=& E_{\pi}\{R_{t}|s_{t}=s , a_{t}=a\}\\ &=& E_{\pi}\{\sum_{k=0}^{\infty} \gamma^{k}r_{t+k+1}|s_{t}=s, a_{t}=a\} \end{eqnarray*} と書けます。先程のn-Armed Banit Problemの場合は行動価値関数を決めてい ましたが、状態が無かったので、$Q(a)$と表せていました。$V^{\pi}(s)$と $Q^{\pi}(s,a)$との違いは、$a$がついているかついていないかで、$V^{\pi}(s)$の場合 は状態$s$において，方策$\pi$で次々に行動した場合，得られる報酬がいいか悪いか、$Q^{\pi}(s,a)$ の場合は、ｓという状態でaをとってその後πという方策に従った場合にどれ だけ価値が得られるか、というものになっています。aというのが方策πに関 係ないということを覚えておいてください。それで$V^{\pi}(s)$と$Q^{\pi}(s,a)$との違 いがわかります。 \subsection{Bellman 方程式} Bellman方程式を \begin{eqnarray*} 　V^{\pi}(s) &=& E_{\pi}\{R_{t}|s_{t}=s\}\\ &=& E_{\pi}\{r_{t+1}+\gamma V(s_{t+1})|s_{t}=s\} \end{eqnarray*} で定義します。この式は、すべての行動に対して、次におこると期待されるす べての状態における価値とその報酬の和を、生起確率で重みづけしたものです。 このBellman方程式は \begin{eqnarray*} 　　R_t&=&r_{t+1}+\gamma r_{t+2}+\gamma ^2r_{t+3}+ \cdots\\ 　　　 &=& r_{t+1}+\gamma (r_{t+2}+\gamma r_{t+3}+ \cdots)\\ &=& r_{t+1}+\gamma R_{t+1} \end{eqnarray*} から求めることができます。Bellman方程式は確率の期待値で書いてありますが、 これをはずして違う形で書くと、 $ V^{\pi}(s)=\sum_{a} \pi (s,a) \sum_{s'} P_{ss'}^{a}{R_{ss'}^{a}+\gamma V^{\pi}(s')} $ となります。この式において、$\pi(s,a)$は $s$ という状態において $a$ という行 動をとる確率、すなわち方策を示します。例えば Grid Space (上下左右にの み動ける格子平面) におけるランダムpolicyを考えるなら、$\pi(s,上)=1/4$, $\pi(s,下)=1/4$,$\pi(s,左)=1/4$, $\pi(s,右)=1/4$ です。右にのみ行くポリシーを 考えるなら、$\pi(s,右)=1$ となります。また、$ P_{ss´}^{a}$ は $s$ という状態 で、行動 $a$ をとった時 $s'$に行く確率です。最後に求まる $V^{\pi}(s)$ は、$\pi$と いう方策のもとで、状態 s がどのくらい価値があるのかを示します。同様に $Q$ についても$\pi$という方策のもとで、価値を求めることができます。 \subsection{最適価値関数} これまでは、$\pi$という方策の元で、V、Qがどうなるのかを考えてきました。 しかし実際に求めたいのは、方策πが最適でない時、得られる報酬を最大にす る方策$\pi$です。そこで、その最適な方策$\pi$を求める方法を考えます。 有限MDPにおいて、 \begin{equation} \pi \geq \pi ' \ \ \mbox{if and only if} \ \ V^{\pi} \geq V^{\pi'} \ \ \mbox{for all }\ \ s \in S \end{equation} が成り立ちます。つまり、もし$\pi'$より$\pi$をとると価値関数Vが上がるのであれ ば、そちらの方策の方が良い訳です。ここで、私達は V 及び Q を最大にする πを求めたい。そこで最適な方策を$\pi^{*}$で表しましょう。 この最適方策$\pi^{*}$に対応して、最適状態関数$V^{*}$が次の様に求められます。 \begin{equation} V^{*}(s) = \max_{\pi} V^{\pi}(s) \ \ \mbox{for all s}\ \ \in S \end{equation} 同様に、最適行動関数$Q^{*}$が次のように求められます。 \begin{equation} Q^{*}(s,a) = \max_{\pi} Q^{\pi}(s,a) \ \ \mbox{for all }\ \ s \in S \ \ \mbox{and }\ \ a \in A(s) \end{equation} ここで、最適行動関数$Q^{*}$は、ある状態$s$ で行動 $a$ をとり、その後は最適 方策にしたがって行動した時の期待収益を表します。 \subsection{Bellman Optimally Equation} 以上より、V についての Bellman最適方程式は \begin{eqnarray*} V^{*} = \max_{a \in A(s)} Q^{\pi^{*}} (s,a)\\ = \max_{a \in A(s)} E_{\pi^{*}} \left\{ r_{t+1} + \gamma V^{*}(s_{t+1}) | s_{t} = s, a_{t} = a \right\}\\ = \max_{a \in A(s)} E_{\pi^{*}} \sum_{s'} P^{a}_{ss'} \left\{ R^{a}_{ss'} + \gamma V^{*} (s') \right\} \end{eqnarray*} と表せます。ここで、$V^{*}$ はある状態における、最適な状態価値関数です。 また、$Q$についても同じことが言え、 \begin{eqnarray*} Q^{*}(s,a) &=& E \left\{ r_{t+1} + \gamma \max_{a'} Q^{*}(S_{t+1}, a') | s_{t} = s, a_{t} = a \right\}\\ &=& \sum_{s'} P^{a}_{ss'} \left( R^{a}_{ss'} + \gamma \max_{a'} Q^{*}(s', a') \right) \end{eqnarray*} として、最適行動価値関数 $Q^{*}(s,a)$ を求めることができます。 最適状態価値関数 $Q^{*}(s,a)$ は、状態 $s$ のもとある行動 $a$ をとった時どれ ほどの報酬が得られるかを示すものなので、$Q^{*}$ が与えられれば、先読みす る必要もなく最適な方策$\pi^{*}$が与えられ、 \[ \pi^{*}_{s} = \arg \max_{a\in A(s)} Q^{*}(s,a) \] となります。 \subsection{Bellman Optimally Equation を解く} これより、具体的に Bellman 最適方程式を解くことで、最適な方策πを求め ることができます。このようにしてπをもとめる事ができるなら、これを「強 化学習」などと呼ばなくても良いのではと思われるかも知れません。しかし、 我々はこれまでに色々な仮定をしました。 \begin{enumerate} \item 環境のダイナミクスの知識が必要 \item 十分な計算資源 \item マルコフ性 \end{enumerate} １、はある状態で行動 a をとったらどこへ行くかや、どのような報酬があた えられるかに関する知識のことを言っており、これが判れば方策πを計算する ことが可能です。しかし、現実の問題を考えると、これが判っていることは ほとんどないのです。 ２、はアクションの数や、その後にとりうる状態の数が増えた時の計算資源 のことを言っています。これらの量が増すと、いくら ３、でマルコフ性を仮 定しても計算資源は足りなくなります。 このような仮定のもと、具体的に Bellman 最適方程式を解くには次の二つ の方法あります。一つは動的計画法、もう一つは強化学習です。 \begin{itemize} \item 動的計画法\\ Bellman 最適方程式を解く方法です。しかし、状態が増えると計算量が増え、 現実的に解く事はできなくなります。 \item 強化学習\\ Bellman 最適方程式を近似的に解く方法です。ただし、必ず正しい解を出すと 言う保証はなく、もし、めったに起きない状態の中に最適解があるとすると、 それを捜し出すことはできません。 \end{itemize} \section{動的計画法} \subsection{Policy Evaluation} これから、$\pi^{*}$を求める方法の一つである動的計画法で、Bellman 最適方 程式をどのように解くかについて話していきます。 まず、Policy を評価することを行います。つまり、Policy π が与えられ た時、その状態価値関数 $V^{\pi}$ を計算すると言うことです。これは、先程 と同様に以下の式で表すことができます。 \begin{eqnarray*} V^{\pi}(s) &=& E_{\pi}\{R_{t}|s_{t}=s\} \\ &=& E_{\pi}\{\sum_{k=0}^{\infty} \gamma^{k}r_{t+k+1}|s_{t}=s\} \end{eqnarray*} これより、$V^{\pi}$についての Bellman 方程式は同様に $ V^{\pi}(s)=\sum_{a} \pi (s,a) \sum_{s'} P_{ss'}^{a}{R_{ss'}^{a}+\gamma V^{\pi}(s')} $ と書けます。この式を解いて $V^{\pi}$ を求めます。 \subsection{Iterative Methods} 上の式より、Vを徐々に変えてゆき、$V^{*}$を求める事を考えます。 $ V_{0} \rightarrow V_{1} \rightarrow \cdots \rightarrow $ $ V_{t} \rightarrow V{t+1} \rightarrow \cdots \rightarrow V^{*} $ ここで、各々状態を更新するときは、すべての行動 a について sweep します 。V は大域的な計算式になっているので、下式にしたがって変わっていきます。 $ V_{t+1} = \sum_{a} \pi (s,a) \sum_{s'} P_{ss'}^{a}{R_{ss'}^{a}+\gamma V_{t}(s')} $ すなわち一つ前の $V$ を使って、次の時刻の $V$ を計算することができます。 この計算を繰り返すことで、$V^{*}$をもと求めることができるのです。 \subsection{Policy Improvement} 次は、$Q$ について考えます。すなわち、方策$\pi$のもとで計算された$V^{\pi}$ を用いて、状態 $s$ で行動 $a$ を行う事の価値を計算します。ここで、$Q^{\pi}$ は \begin{eqnarray*} Q^{\pi} &=& E_{\pi} \left\{ r_{t+1} + \gamma V^{*}(s_{t+1}) | s_{t} = s, a_{t} = a \right\}\\ &=& E_{\pi} \sum_{s'} P^{a}_{ss'} \left\{ R^{a}_{ss'} + \gamma V^{\pi} (s') \right\} \end{eqnarray*} の様に書くことができるので、V を使ってQを計算することができます。 $V^{\pi}$に関して greedy に行うとは、すべての $Q$ について最大の価値を与 える 方策を $\pi'(s)$とする時、$V^{\pi '}$が$V^{\pi}$より大きければ更新を行う ということです。すなわち、下式で表される操作を行うことに相当します。 \begin{eqnarray*} \pi '(s) &=& \arg \max_{\pi} Q^{\pi}(s,a)\\ &=& \arg \max_{\pi} \sum_{s'} P^{a}_{ss'} \left\{ R^{a}_{ss'} + \gamma V^{*} (s') \right\} \ \ \mbox{Then } \ \ V^{\pi '} \geq V^{\pi '} \end{eqnarray*} これを繰り返してゆき、最後に $V^{\pi '}$ が $V^{\pi}$ と等しくなったら、 そこで更新を止めます。この時、Bellman最適方程式は $ V^{\pi}(s) = \max_{a} \sum_{s'} P_{ss'}^{a}{R_{ss'}^{a}+\gamma V_{t}(s')} \ \ \mbox{for all} \ \ s \in S $ となり、そして $\pi ' = \pi^{*}$ が最適方策となります。 \subsection{A Small Grid World} 例として、簡単な計算をやってみましょう。ここでは Matlab は使わず、手 で解いてみます。 ＜４×４のグリッドの図＞ まず、図のような４×４のグリッドを考えます。ここで、とり得る行動は Action = {up, down, right, left} の４つののみとし、さらに次の様な条件をおきます。 \begin{enumerate} \item $\gamma = 1$ とする。 \item グリッドNo. 1-14 を非終端状態とする。 \item 1, 15を終端状態とする。 \item 行動 a は状態を変えない。 \item 報酬は終端状態にたどり着くまで-1ずつ与えられる。 \end{enumerate} さらに、状態 $s$ において行動 $a$ が選択されたとき、状態 $s'$になる確率 $P^{a}_{ss'}$は決定論的であるとし、これを境界処理に用います。例えば $ P^{right}_{5,6} = 1, P^{right}_{5,10} = 0, P^{right}_{7,7} = 1 $ の様になります。状態5から右という方向を選択すると、6(右)へ状態が変化す る確率は１ですが、それ以外の方向へは動けません。逆に右側が存在しない状 態7から右という行動を選択すると、同じ状態7へ行ってしまいます。また、ポ リシーは上下左右各々1/4で、固定することにします。 すべてのグリッドについて計算する時間はありませんので、グリッド1につ いてVを計算してみましょう。まず、初期状態評価関数は何でも良いですので すべてのグリッドについて 0 とします(図\ref{fig:init} 左)。 \begin{figure}[htbp] \begin{center} \includegraphics[width=7cm]{fig1.eps} \caption{{\bf 初期状態}} \label{fig:init} \end{center} \end{figure} %----------------- %|0.0|0.0|0.0|0.0| %----------------- %|0.0|0.0|0.0|0.0| %----------------- (これに対応する矢印を示すグラフ) %|0.0|0.0|0.0|0.0| %----------------- %|0.0|0.0|0.0|0.0| %----------------- % ＜図あ＞ このとき、グリッド1の状態は以下の式で更新されます。 \begin{eqnarray*} V(1) &=& \frac{1}{4}(-1+\gamma \cdot 0) + \frac{1}{4}(-1+\gamma \cdot 0) +\frac{1}{4}(-1+\gamma \cdot 0) + \frac{1}{4}(-1+\gamma \cdot 0)\\ &=& -1.0 \end{eqnarray*} 同様に他のグリッドも計算すると、(図\ref{fig:first} 左)のようになります。 \begin{figure}[htbp] \begin{center} \includegraphics[width=7cm]{fig2.eps} \caption{{\bf 1回の計算後}} \label{fig:first} \end{center} \end{figure} %--------------------- %| 0.0|-1.0|-1.0|-1.0| %--------------------- %|-1.0|-1.0|-1.0|-1.0| %--------------------- (これに対応する矢印を示すグラフ) %|-1.0|-1.0|-1.0|-1.0| %--------------------- %|-1.0|-1.0|-1.0| 0.0| %--------------------- % ＜図い＞ 同様の計算を繰り返すと、グリッド1の状態は以下の式で更新され、全体の状 態は(図\ref{fig:second} 左)のようになります。 \begin{eqnarray*} V(1) &=& \frac{1}{4}(-1+\gamma \cdot 0) + \frac{1}{4}(-1+\gamma \cdot (-1)) +\frac{1}{4}(-1+\gamma \cdot (-1)) + \frac{1}{4}(-1+\gamma \cdot (-1))\\ &=& -1.75 \end{eqnarray*} \begin{figure}[htbp] \begin{center} \includegraphics[width=7cm]{fig3.eps} \caption{{\bf 2回の計算後}} \label{fig:second} \end{center} \end{figure} %--------------------- %| 0.0|-1.7|-2.0|-2.0| %--------------------- %|-1.7|-2.0|-2.0|-2.0| %--------------------- (これに対応する矢印を示すグラフ) %|-2.0|-2.0|-2.0|-1.7| %--------------------- %|-2.0|-2.0|-1.7| 0.0| %--------------------- % ＜図う＞ この計算を何度も繰り返すと、(図\ref{fig:last} 左)の状態になります。この状態にな ると、式はもうこれ以上変化しません。 \begin{figure}[htbp] \begin{center} \includegraphics[width=7cm]{fig4.eps} \caption{{\bf 最終状態}} \label{fig:last} \end{center} \end{figure} %----------------- %|0.0|-14|-20|-22| %----------------- %|-14|-18|-20|-20| %----------------- (これに対応する矢印を示すグラフ) %|-20|-20|-18|-14| %----------------- %|-22|-20|-14|0.0| %----------------- % ＜図え＞ 求めた各状態 V を用いて一歩先読みし、もらえる報酬を予測することで、 各状態からの最適行動を求めることができます (図あ、い、う、え 右)。例え ば (図あ 左)の時はすべての状態価値 V が0ですので、ランダムに行動するし かありませんが、(図い)、(図う)になるにつれ、一歩先をみることでどちらに 行くのが良いか調べる事ができます。そして(図え)では$V^{*}$がわかっており、 確実に最適な行動を見つける事ができます。しかし、この方法では、状態、行 動の数が増えた時、計算が困難になります。 Q ゴールは無いのですか？ 答 グリッド１と１５がゴールです。ここに行ったらおしまいです。 Q ゴールで報酬はないのですか？ 答 無いです。代わりに、動くと-1の報酬が与えられます。なるべく早く ゴールした方が報酬の量が多い訳です。 Q 右に行けない場合もrewardは-1になるのですか？ 答 そうです。 \subsection{Generalized Policy Iteration} Small Grid World の場合は、一度ある方策$\pi^{0}$をおくだけで一番最適な$*$ が求まってしまいました。しかし、一般には方策の見積りと状態の見積りとを 繰り返すことで $V^{*}$、$\pi^{*}$を求めます。すなわち $ \pi_{0} \rightarrow V^{\pi_{0}} \rightarrow \pi_{1} \rightarrow V^{\pi_{1}} \rightarrow \cdots \rightarrow \pi_{*} \rightarrow V^{\pi_{*}} \rightarrow $ として$V^{*}$、$\pi^{*}$を求めるのです(図、講義で用いた図(下図))。 ＜講義で用いた図＞ \subsection{Monte Carlo 法} 最適な方策$\pi^{0}$を求めるために、動的計画法の他にモンテカルロ法と呼ば れるものがあります。動的計画法(DP)では、実際にはあり得ないすべての状態 を考えますが、モンテカルロ法では一つの状態遷移のみを考えます。そし て、ゴールにたどりつくまで一度試行を行ってみて、その時の報酬をもとに状 態価値関数$V(s)$を更新するのです。迷路の例ですと、一度agentがランダムに 動いてでゴールにたどり着くまで試行を行い、それで得られる報酬に基づいて 状態を更新することになります。 \section{強化学習} \subsection{TD Prediction} では、最後に強化学習における Bellman 最適方程式の解法について考えて みます。まず、方策πが与えられた時、状態価値関数を計算する方法について です。モンテカルロ法では下式の様に Terminal の状態まで試行を行い、時刻 tの後、実際に得られる報酬 $R_{t}$ を用いてVを更新しまが、この方法ではゴー ルにたどり着くまで報酬が判らないので状態の更新ができません。 $ V(s_{t}) \leftarrow V(s_{t}) + \alpha [R_{t} - V(s_{t})] $ それに対して、強化学習では、何か行動があった段階で、Vを更新する事を 考えます。次の式は単純なTD(0)と呼ばれる強化学習のアルゴリズムです。 $ V(s_{t}) \leftarrow V(s_{t}) + \alpha [r_{t+1} + \gamma V(s_{t+1}) - V(s_{t})] $ ここで重要なのは、Vの更新は収益の期待値 $r_{t+1} + \gamma V(s_{t+1})$ を用いて行われるという事です。これは、得られる報酬を予測したもので、MC で用いられている報酬 $R_{t}$ と同種のものです。$V$ は予測値なので、常に正 しいとは限りません。時刻が一つずれているのでTemporal Difference (TD)と 名付けられています。 Q R と V の違いは何ですか？ 答 Rは最終状態にいった時もらえるもの、$V_{t+1}$はその時の状態価値関数を 用いて予測したものです。 Q 予測が完全ならば MC法の $R_{t}$ と TD法の $r_{t+1} + \gamma V(s_{t+1})$ は一致するのですか？ 答 はい。 \subsection{Backup diagram} ここで、(図、下の図)にこれまで紹介した３つの方法の Backup diagram を 示します。 \begin{figure}[htbp] \begin{center} \begin{minipage}{7cm} \begin{center} \includegraphics[width=5cm]{MC.eps}\\ MC法 \end{center} \end{minipage} \begin{minipage}{7cm} \begin{center} \includegraphics[width=5cm]{TD.eps}\\ TD法 \end{center} \end{minipage} \begin{minipage}{7cm} \begin{center} \includegraphics[width=5cm]{DP.eps}\\ DP法 \end{center} \end{minipage} \caption{{\bf 3つの方法の比較}} \label{fig:first} \end{center} \end{figure} % ＜図、３種類「MC」「TD」「DP」の Backup diagram。 % 評価する部分が赤く塗りつぶされたもの。＞ 「(MC)」では、ある状態から「Action→状態→Action→状態→」を繰り返し てゆき最後にTerminalで得られた報酬 R を用いて V を更新します。 「(TD)」では、ある状態から「Action→次の状態」という情報のみを用いて 状態 V を更新します。 「動的計画法(DP)」では、ある状態で取りうる Action をすべて計算し、そ の結果得られる状態の価値関数をすべて足しています。つまり、すべての可能 性を考えて更新していきます。 (図、上の図)の赤い部分は、考慮にいれる状態、及びAction です。TD法が 一番小さい、すなわち状態の更新の為に考慮にいれる情報が少なくて良い事が 判ります。 \subsection{Q-learning} Q-learning とは、各状態において、可能な行動の中で、最も行動評価関数 の値が高い行動をとるように学習を行う方法です。学習は次の様に行われます。 $ Q(s_{t},a_{t}) \leftarrow Q(s_{t},a_{t}) + \alpha [r_{t+1} + \gamma \max_{a} Q(s_{t+1},a_{t+1})-Q(s_{t}, a_{t})] $ Q-learning が方策 off 型と呼ばれるのは、方策に関係なくaについて最大の 行動価値関数Qを用いてもとのQと比較を行い、行動価値関数を更新するためで す。 \subsection{Actor-Critic} ＜教科書P.86の図＞ Q-learning は、ある状態である行動をとることに対する善し悪しのみで方 策Qが決まりました。それに対して Actor-Critic は価値関数と同様に、学習 する方策が陽に表現されます。また、行動選択に必要な計算量が少ない、Soft Maxを使うなど確率的な方策も学習できる、そして生物学的理解に根ざしたモ デルであるなどの特徴があります。 Actor-Criticは、教師信号でなく、誤差信号を得ることで学習を行います。 すなわち $ \delta_{t} = r_{t} + \gamma V(s_{t+1}) -V(s_{t}) $ で誤差信号 $\delta_{t}$を求め、 $ p(s_{t}, a_{t}) \leftarrow p(s_{t}, a_{t}) + \beta \delta_{t} $ で $p(s,t)$ (actor が状態 $s$ で行動 $a$ を取る確率)を更新します。 $\delta_{t}$ は $V$ が完全に報酬を予測する事ができるようになれば０になりま す。 Q 初日に銅谷さんが見せたシュルツの実験では、ドーパミンニューロンの 活動がずれていました。これはTD誤差なのですか？もしTD誤差なら学習 が進むとゼロになるはずですし、一方それが価値関数であるならずっと 出ている筈ですが？ 答(銅谷) TD誤差と考えています。学習が進んでいない段階では $V(s) = 0$ な ので、$\delta_{t} = r_{t}$ が出ているわけです。 Q すると、これは学習が進行していないということですか？ 学習が進行すれば活動がゼロになるはずですね。 答(銅谷) タスクが始まるまでは、サルはいつ reward が貰えるのか判りま せん。そのため、タスクが始まるところではVが急に大きくなるのです。 そして、1-2秒後に小さくなりますが、これは reward があると予想で きる様になる為です。 Q では、サルが自分でstartボタンを押して、課題をはじめる様な実験を 行った場合はどうなるのですか？ 答(銅谷) 課題の始まりをサル自身に行わせるという事ですね。 彦坂先生はご存知ですか？ 答(彦坂) 例えばBlock 単位で trial を行う場合は、最初のtrialのFixation Point にサルは一番反応します。そして２trial目以降はほとんど変わり ません。 Q それは Inter Trial Interval に依存しませんか？ 答(彦坂) それは依ります。 Q 私はサルの訓練後、報酬が貰える筈のところで報酬が出なかった時の事を知 りたいです。これもTD誤差(マイナスの誤差)になりますが、反応はでるので すか？もしくはマイナスの誤差ですから違うところで出るのですか？ 答(銅谷) それに関してはシュルツ達が実験していて、本来出るべきタイミング で reward が出ないと、一時的にドーパミンニューロンに Depression が出 ることが観測されています。 \end{document}