1. 3.1 強化学習
機械学習の1つである強化学習は, 報酬を利用して方策を最適化することで, エージェントを環境に適応させることを目的とする.ここでは強化学習においてエージェントが得た知識を利用して, 方策を改善する手法を説明する.
強化学習(Reinforcement Learning)は動物の適応的な行動獲得を工学的観点からモデル化した手法である.強化学習の特徴は最適な行動を人間がエージェント(学習主体(ex.ロボット))に教えるのではなく, エージェント自身が環境との試行錯誤を通して得た行動の結果から, 自律的に意思決定の方策(policies)をより良いものへと構築していく学習手法であるという点にある.より具体的には, 目的を達成した際にスカラー値の報酬を与えることによってのみ学習を行う.強化学習では, エージェントは環境の状態(state)を観測し, それに応じて行動 (action)を選択する.この際, エージェントの選択した行動によって報酬 (reward)が与えられる.また, エージェントは状態, もしくは状態と行動の組に対する評価値(value)を持っており, 行動はこれらの評価値によって決定される. (e.g., 次の状態の評価値が最大になるように行動を選択する.又は, 評価値を気にせず探索的な行動を選択する.) 評価値はその状態における現在から未来にわたって得られる報酬の割引かれた累積和を示し, エージェントは評価値を最大化することを目的とする.その結果, エージェントは自律的に意志決定の方策 (policy) をより良いものへと構築していくことができる.
図3.1 強化学習の枠組
強化学習の枠組を図3.1に示しているように, エージェントは, 環境をセンサによって知覚し, それに対して自身の取る行動を選択し, 自律的に行動していくことができる知的システムで, 通常環境に対して行動を選ぶための行動規範を内部に持っている。この行動規範を強化学習によって, 探査的な行動を行い, 目的に沿った行動をした時に報酬を与えられるものとし, これの報酬を使いながら, 環境と行動の相互作用を観測しながら更新し, より複雑な環境に対しても, 目的にあった行動をするように, 行動規範を改善していて, 自身の振る舞いを改善していくことができる。
次に強化学習の手法のうち, 今回実験に使った方法である, 非TD制御とTD制御の2つのアルゴリズム, SarsaとQ-learning)について説明し, これらのアルゴリズムの特徴, 利点, 欠点について紹介する。
まず, TD制御(時間的差分学習;Temporal Difference Learning)は, 環境のダイナミクスのモデルを用いずに, 経験から状態stに対する行動価値関数V(st)を直接学習することができ, 最終結果を待たずに, 他の推定値の学習結果を一部利用し, 推定値を更新する予測法で, 時刻t+1で直ちに目標値を作り, 観測した報酬r(t+1)と推定量V(St+1)を使って適切な更新を行う。最も単純なTD法はTD(0)と呼ばれ, 以下のようになる。
V(st) V(st)+α[rt+1+γV(st+1)-V(st)] (3.1)
TD更新は, rt+1+γV(st+1)を目標とする。そして, 利点としては, 以下のようになる。
・環境モデル;つまり報酬と次の状態の確率分布を必要としない。
・オンライン手法として完全な漸進型の手続きに実装できること。
次にTD(0)でのSarsaとQ-learningについて説明する。
Sarsaは, 価値の差から学習するという意味において強化学習の中心となっている考え方である。Sarsaは, 環境のモデル(遷移確率と報酬分布) を必要とせず, 相互作用によって得た経験(experience) から直接学習ができる.経験とは, 環境との1 回の相互作用から得られる状態, 行動, 報酬, 次状態の4 つ組(st, at, rt+1, st+1) である。Sarsaは与えられた方策πの価値関数Vπを推定するためのアルゴリズムで, 方策評価の方法によって, 最適価値関数Vを求める方策改善である。本章では, 方策評価に限って説明する。Sarsaは, 環境のモデルが分からないため, エージェントは実際に環境と相互作用してみる必要がある.時刻t における環境との1 回の相互作用から得られる経験を用いて, 現在の状態St の価値V(St) を以下の式によって更新する。
V(st) ← V(st) + αδt (3.2)
δt = rt+1 +γV(st+1) -V(st) (3.3)
αは学習率と呼ばれるパラメータで, (0, 1)の間の実数である。式(3.2) は, TD 誤差(TD-error) と呼ばれ, 次状態の割引価値に報酬を上乗せした値から現在の価値を差し引いた値である。次の表にSarsaのアルゴリズムを掲載する。
表3-1 Sarsaアルゴリズム
① V(s) を任意に初期化し, π を評価対象の方策に初期化する
② 各エピソード1) に対して繰り返し:
1.1 s を初期化
1.2 エピソードの各ステップに対して繰り返し:
3.1.1 a ← s に対してπ で与えられる行動a を取り2), 報酬r と次状態s を観察す
る
V(s) ← V(s) + α[r + γV(s) − V(s)]
s ← s.
3.1.2 s が終端状態3)ならば繰り返しを終了
注: 1) 学習の初期状態から終端状態までをエピソードという.
2) ここで, greedy な行動選択を取れば方策改善が行われ, 最適価値関数V∗ に収束する.
3) 終端状態とは, エージェントに与えたタスクが達成された状態である.
Sarsaの特徴をまとめると以下のようになる。
・ 環境のモデル(遷移関数と報酬分布) を必要とせず, 実際に相互作用した経験から学習が可能である。
・ オンライン手法として漸進型の手続きで実装できる。すなわち, 経験を得るにしたがって状態が正しく評価される。また, 方策改善を行えば行動も改良されていく。
もう1つのQ-learningは, Sarsaをベースにしたアルゴリズムである。Sarsaと同じく環境のモデルを必要とせず, 経験から学習ができる。Sarsaと異なるのは, 状態価値V(s)ではなく, 行動価値Q(s, a)の更新を行う点である。また, 方策評価とともに方策改善も更新式に明示的に含まれているため最適価値関数に収束する。行動価値Q(s, a) とは, 方策πの元で状態s において行動a を取ったときの価値で, その後に方策πに従った期待報酬として, 次のように定義される.
Qπ(s, a) =Eπ{Rt|st = s, at = a}=Eπ{∑∞ k=0γk rt+k+1|st = s, at = a} (3.4)
ここでは状態価値V(s) と異なり, 各状態で取る行動を含めて価値を評価する。Q 学習もSarsaと同じく経験から学習する.時刻t における環境との1 回の相互作用から得られる経験を用いて, 現在の状態st で行動at を取ったときの行動価値Q(st, at) を以下の式によって更新する.
Q(st, at)←Q(st, at) +α[rt+1 +γmaxaQ(st+1, a)-Q(st, at)] (3.5)
更新規則はSarsaと似ているが, 次状態st+1において, 最大の行動価値を持つ行動aを選択している点が異なっている.これは, 方策改善を表しており, 更新規則に明示的に組み込まれている.
方策の選択にはmax選択とε-greedy 方策がよく用いられる。Max選択は最大の行動価値を持つ行動arg maxa Q(s, a) を選択するというものである。一方ε-greedy 方策は確率εでランダムな行動を選択し, それ以外は, 最大の行動価値を持つ行動arg maxa Q(s, a) を選択するというものである。ε-greedyではεの大きさによって, 探索の程度を変化させうることができる。次の表にQ学習のアルゴリズムをまとめる。
表3-2 Q-learningのアルゴリズム
(1) Q(s, a) を任意に初期化
(2) 各エピソードに対して繰り返し:
(2-1) s を初期化
(2-2) エピソードの各ステップに対して繰り返し:
(2-2-1) Q から導かれる方策(例えばQ に対する greedy 方策) を使って, s での行動a を選択する
(2-2-2) 行動a を取り, r, s を観察する
Q(s, a) ← Q(s, a) + α[r + γ argmax Q(s, a) − Q(s, a)]
s ← s
(2-2-3) s が終端状態ならば繰り返しを終了
Q学習は, 得られた経験に基づいて 更新を繰り返し行うことによって最適価値関数に収束することが証明されている。
Q 学習の特徴をまとめると以下のようになる.
・方策改善を更新式に明示的に含んでいる。
・最適価値関数・最適方策に収束することが保証されている。
・学習が遅く, 大量の相互作用が必要である。
2 パラメータに敏感であり, 調整が必要である。
Q学習やSarsaなどのTD手法は適格度トレースと結合して, さらに効率的に学習することの出来そうな一般的手法TD(λ)を得ることが出来る。適格度トレースを用いた手法は1ステップ手法に比べると計算量(計算時間のこと)が多くなるが, その代わりに, 学習速度はかなり速くなる。
適格度トレースの見方は理論的(前方観測的な見方(forward view))と技法的(後方観測的な見方(backward view))の2つの見方がある。そして, 前方観測的な見方のTD (λ)アルゴリズムは, nステップ・バックアップを平均化する方法の1つである。平均にはnステップ分のバックアップすべてが含まれており, その各各はλnー1(0≦λ≦1)に比例して重み付けされる。結果として得られるバックアップはλ収益(λ-return) 式( 3.6)と呼ぶ。
Rλt=(1-λ) ∑∞ n=1λn-1Rn t (3.6)
その更新は以下式(3.7)のようになる。
Rλt=(1-λ)Σn=1λn-1Rnt+λT-t-1Rt (3.7)
ここで, Tはエピソードの最終時間ステップである。よって, λ収益アルゴリズムとは, λ収益を用いてバックアップを実行するアルゴリズムである。従って, 前方観測的な見方は, 訪問した各状態に対して, 将来起こりうるすべての報酬を眺め, 最良の組み合わせ方を決定する見方である。
一方, TD(λ)の後方観測的な見方(技法的)は, 概念的にも計算上でも, 単純であるという理由から有用である。特に, 前方観測的な見方は実際には直接的に実装可能ではない。
なぜなら, 各ステップにおいて, 何ステップか後に起こることの知識を使うので, 因果関係がわからないからである。後方観測的な見方は, 前方観測的な見方を近似するための, 因果関係のある漸進的メカニズムを提供し, オフラインの場合には正確に近似する。
TD(λ)の後方観測的な見方においては, 各状態に関連する付加的なメモリ変数が存在し, それが適格度トレースである。時刻tにおける状態sの適格度トレースをet(s)∊R+(R+は正の実数である)と表す。各ステップにおいて, この適格度トレースはすべての状態に対してγλだけ減哀し, そのステップで訪問された1個の状態の適格度トレースはすべてのs∊Sに対して式(3.8)のように1だけ増加する。この種の適格度トレースを累積トレースと呼ぶ。
γλet-1(s) (s≠stの時)
et(s)=
γλet-1(s)+1 (s=stの時) (3.8)
δt=γt+1+γV(st+1)-V(st) (3.9)
TD(λ)の後方観測的な見方においては, 全体的なTD誤差信号は, 最近訪問した非ゼロトレース信号を持つすべての状態に対して, 比例配分的な更新を生じさせる, つまり, すべてのs∊Sに対して, 式(3.10)のようになる。
ΔVt(st)=αδtet(s) (3.10)
よって, TD(λ)の技法的定義が与えられる。そして, オンライン表形式TD(λ)のアルゴリズムは以下のように表される。
表3-3 オンライン表形式TD(λ)のアルゴリズム
- V(s)を任意に初期化し, すべてのs∈Sに対してe(s)=0とする
- 各エピソードに対して繰り返し:
(ア)sを初期化
(イ)エピソードの各ステップに対して繰り返し:
①
a sに対してπで与えられる行動aを取り, 報酬rと次状態s’を観測する
δt=γt+1+γV(st+1)-V(st)
e(s) e(s)+1
すべてのsについて:
V(s) V(s)+αδe(s)
e(s) γλe(s)
s s’
(2-2-2) sが終端状態ならば繰り返し終了.
TD(λ)でのSarsaとQ-learningはSarsa(λ)とQ(λ)と呼ぶ, この2つの手法について説明しよう。Sarsa(λ)の考え方は:TD(λ)予測手法を状態ではなく, 状態行動対に対して適用することである。すべてのs, aに対して(式3.11)で表示したようになる。
Qt+1(s, a)=Qt(s, a)+ αδtet(s, a)
δt=rt+1+γQt(st+1, at+1)- Qt(st, at)
γλet-1(s, a)+1 (s=stかつa=atの時)
et(s, a)=
γλet-1(s, a) (それ以外の時) (3.11)
である。Sarsa(λ)も方策オン型のアルゴリズムであり, 現在の方策πに対する行動価値Q(s, a)を近似し, 現在の方策に対する近似された価値に基づいて徐々に方策を改善する。表3-4にSarsa(λ)のアルゴリズムを示しておく。
表3-4 テーブル型Sarsa(λ)のアルゴリズム
(1) Q(s, a)を任意に初期化し, すべてのs, aに対して, et(s, a)=0とする
(2) 各エピソードに対して繰り返し:
(2-1) s, aを初期化
(2-2) エピソードの各ステップに対して繰り返し:
(2-2-1) 行動aを取り, r, s’を観測する
(2-2-2) Qから導かれる方策(例えばεグリーディ)を用いてs’で取る行動a’を選択して以下の更新をおこなう。
δ r+γQ(s’, a’)- Q(s, a)
e(s, a) e(s, a)+1
すべてのs, aに対して
Q(s, a) Q(s, a)+ αδe(s, a)
e(s, a) γλe(s, a)

s s’ ; a a’
(2-2-3) sが終端状態であれば終了.
Q(λ)は適格度トレースとQ学習を組み合わせた手法で, 最初に提案した研究者達の名を取ってそれぞれ, WatkinsのQ(λ)とPengのQ(λ)と呼ぶ。理論的, あるいは前方観測的な見方から見ると, TD(λ)とSarsa(λ)とは異なり, WatkinsのQ(λ)はバックアップ中に, エピソードの終わりまでずっと先読みすることはしない。Q(λ)は次の探査的行動のみを先読みする。行動価値の知識に基づき, 最初の探査的であれば, WatkinsのQ(λ)はrt+1+γmaxaQt(st+1, a)に向けてQt(st, at)の1ステップ更新を行う。一方, WatkinsのQ(λ)の技法的, あるいは後方観測的な見方から見ると, 最初に, すべての状態行動対のトレースはγλの割合で減哀するが, あるいは探査的行動が取られた場合は0に設定される。次に, 現在の状態と行動に対応するトレースは1だけ増加する。全体的な結果は次式(3.12)になる。
γλet-1(s, a) (Qt-1(st, at)= maxaQt-1(st, a)の時
et(s, a)=I sst・I aat+
0 (それ以外の時) (3.12)
I xyは一致関数(identity-indicator function)で, x=yならばその値は1で, それ以外であれば0である。このアルゴリズムの残りの部分は次のように定義される。
Qt+1(s, a)=Qt(s, a)+ αδtet(s, a) (3.13)
δt=rt+1+γmaxa’Qt(st+1, a’)- Qt(st, at) (3.14)
である。
表3-5にWatkinsのQ(λ)アルゴリズムをまとめて示す。
表3-5 WatkinsのQ(λ)アルゴリズム
(1) Q(s, a)を任意に初期化し, すべてのs, aに対してe(s, a)=0とする
(2) 各エピソードに対して繰り返し:
(2-1) s, aを初期化
(2-2) エピソードの各ステップに対して繰り返し:
(2-2-1) 行動aを取り, r, s’を観測する
(2-2-2) Qから導かれる方策(例えばεグリーディ)を用いて
s’で取る行動a’を選択する
a* argmaxbQ(s’, b)
(a’の場合と最大値が等しいならば;a* a’)
δ r+γQ(s’, a*)- Q(s, a)
e(s, a) e(s, a)+1
すべてのs, aについて:
Q(s, a) Q(s, a)+ αδe(s, a)
もしa’=a*ならば, e(s, a) γλe(s, a)
それ以外e(s, a) 0

s s’ ; a a’
(2-2-3) sが終端状態であれば繰り返し終了
一方, PengのQ(λ)は, Sarsa(λ)とWatkinsのQ(λ)の混合型であり, Q 学習とは異なり, 探査的行動とグリーディ行動との間の区別はない, 各要素バックアップは広いステップ数の実際の行動にまたがっているが, 最後の部分で行動群に関する最大化を行って完成する。よって, 要素バックアップは方策オン型でも, オフ型でもない。初期の遷移は方策オン型であるが, 最後の遷移ではグリーディ方策が使われている。結果として, PengのQ(λ)の元では, 固定された非グリーディ方策QtはQπ(行動価値関数)にもQ*(最適行動価値関数)にも収束しないが, 両者の中間的なものには収束する。
3.2 決定木
決定木とは, 根または中間ノードが条件式, 枝が条件式の答え, 葉ノードがクラスを表すような木構造であり, ある属性を持つ事例がどのクラスに属するかを判断する知識を表現する。クラスとは, ある事例が, どういう集合に属するかを表す。たとえば, クラスには「正しい」と「間違っている」場合を考えよう。「正しい」クラスに属する事例を複数用意する。「間違っている」クラスに属する事例を複数用意する。これらの2種類のクラスに属する複数の事例を決定木学習システムに与えると, 決定木という一種の知識を獲得する。この決定木を利用して, 未知の事例がどのクラスに属するか(正しいか, 間違っているか)を判断する。図3.2にその概略を示す。図3.2ではクラスは2種類だが, 3種類以上も可能である。
はじめに, 事例をどのように表現するかを考えよう。たとえば事例の例として, 野球のボールや卓球のボールを考えよう。これらの事例には属性がある。たとえば, 色, 形, 大きさなどである。属性には, それぞれ取ることができる値がある。色ならば, 赤, 白, 黒など, 形ならば, 球, 直方体, 立方体などである。これらを属性値と呼ぶ。事例は, 属性値を列挙した形で持つ。
人間の例を挙げる, 一つ目の属性は, 背の高さである。この属性がとることができる属性値は「高い」「低い」を持つ。二つ目の属性は髪の色であり, 属性値は「うす黒い」, 「赤」, 「ブロンド」を持つ。三つ目の属性は, 目の色であり, 「青い」, 「茶色い」を属性値として持つ。

図3.2 2種類のクラス
・「背の高さ」高い, 低い
・「髪の色」うす黒い, 赤, ブロンド
・「目の色」青い, 茶色い
事例である人は, この三つの属性が列挙された状態(ベクトル)で表す。ある人は, (低い, ブロンド, 青い)と表せるし, 別の人は, (高い, ブロンド, 茶色い)と表せる。ベクトルの順序には, 意味があり, (背の高さ, 髪の色, 目の色)の順に表現する。
事例の表現では, 人間を例に挙げた。では, クラスはどうなるか。ここの人間の例では, Aさんが好きな人と嫌いな人に分ける。(低い, ブロンド, 青い)と表現された人は好きな人, (高い, ブロンド, 茶色い)と表現された人は嫌いな人と言うように, 各属性値ベクトルで表現された事例が, どのクラスに属するかを決めておく。この事例と事例の属するクラスが帰納学習での入力となる。
では, 機械で学習させて, 得られた知識はどのように表現するか。一例は, if-thenルールである。もし, 髪の色=ブロンド, かつ, 目の色=茶色だったら, 「好きな人」のクラスに属するとか, もし, 髪の色=うす黒い, ならば, 「嫌いな人」のクラスに属すると言うようにif-then(もし~ならば~)という形式で表現する方法がある。ここでは, このif-thenルールで表現する方法に似ているが, これを圧縮した形で表現する決定木という方法をとる。
決定木の例を図3.3に示した。(低い, ブロンド, 青い)と表現された人はどのクラスに属するかをどう調べるか。まず, 一番上の部分に「髪の色」とある。ここでは, 髪の色が何かを調べる。この場合は, 「ブロンド」である。「ブロンド」の線をたどると, 「目の色」とある。そこで, 目の色を調べる。ここでは, 「青い」である。「青い」の線をたどると「好き」である。ここで, 「好き」なクラスに属することがわかる。(高い, ブロンド, 茶色い)という属性を持つ人は, 「嫌い」であることを確認できるだろうか。先ほどと同様に, 一番

上の髪の色を調べ, ブロンドを辿り, 目の色を調べ, 茶色いを辿り, 嫌いに属する。このような構造を木と呼ぶ。一番上の髪の色とかかれた部分を根(root)と呼ぶ。線を上から辿って, 一番下の部分の「好き」「嫌い」とかかれた4箇所を葉(leaf)と呼ぶ。植物の木を逆さにしたような構造である。
この木は4つのif-thenルールで表現できる。
1 もし, 髪の色がうす黒いならば嫌い
2 もし, 髪の色が赤いならば好き
3 もし, 髪の色がブロンドで, かつ, 目の色が青いならば好き
4 もし, 髪の色がブロンドで, かつ, 目の色が茶色いならば嫌い
最初に調べる属性が髪の色であるから, このように if-thenルールを圧縮できる。
では, 事例から, 決定木を得る方法を説明する。まず, 最初に木の根に相当する属性を何にして, 分類するかである。ここでの人の例の属性は, 背の高さ, 髪の色, 目の色の3種類がある。このうち, どれを選択するか評価してくれる関数があるとする。その評価関数の評価値によって, もっともうまく分類できる, 最も適した属性を調べることができると仮定しよう。この関数は事例と各事例が属するクラスが与えられ, 各属性の評価値を求める。その関数によって, 最初の属性は「髪の色」がよいとわかったとする。そうすると, うす黒い, 赤い, ブロンドと3つに枝分かれする。髪の色がうす黒い事例とその事例が属するクラスを調べる。すべて, 同じクラスに属していれば, そこは葉になる。この場合は, すべて, 嫌いに属していたので, 「嫌い」という葉になる。同様に, 髪の色が赤い事例とその事例が属するクラスを調べる。すべて, クラスがすべて「好き」だったので, 「好き」という葉になる。髪の色がブロンドの事例は「好き」に属する場合と, 「嫌い」に属する2種類が混在していたとする。その場合は, 再び, 先ほどの評価関数を利用して, 評価関数に髪の色がブロンドに属する事例とクラスを与え, この時点ではどの属性で分類すればいいかを調べる。そうしたら, 「目の色」がここで分類するのがよいと得られたとする。次は目の色が青い事例とその事例が属するクラスを調べる。ここでは, すべて「好き」なので, 「好き」という葉になる。同様に, 目の色が茶色いを調べると, すべて, 嫌いなのでここでは嫌いという葉になる。 以上を整理すると, 事例がすべて同じクラスに属していたら, そのクラスの葉となる。事例が複数のクラスに属している場合は, 分類するための属性を評価関数によって求め, その属性で分類する。分類した先は, 再帰的にこの処理を呼び出す。
決定木学習の代表的な学習法にはキンラン(1993)によるC4.5があり, 本研究ではこれを使うことにした。キンランのC4.5では評価関数として, 以下のエントロピ-に基づく量を使用する。
H(S)=-∑pj log pj (3.15)
ここで, jはクラスでPjは集合Sにおけるあるクラスjの出現率を示す。エントロピーH(S)は, 集合(S)内のクラス分布の「あいまいさ」, つまり, 乱雑さを示しているので, H(s)がなるべく小さいサブ集合から構成されるほど, 分類精度が高いといえる。
一方, 図3.4に示すように, ある条件式で, 集合Sをサブ集合S1とS2に分割した場合, エントロピーの変化は式4.2で表される。
Gain=H(S)-(|S1|*H(S1)+|S2|*H(S2))/|S| (3.16)
この量を相互情報量ゲイン率と呼ぶ。
キンランのC4.5アルゴリズムでは, あらゆる属性についてありうる条件式を用いて分割テストを行い, 分割テストの際に相互情報量ゲイン率を最大化する条件式を選択しながら, 木構造を成長させることによって最適な決定木を獲得する。
3.3 問題点
強化学習の中のSarsaとQ-learningは, 環境モデルを必要とせず経験から学習する, 最適性・収束性が得られているなどの利点があって, 広く使われているが, 環境状態があまり大きく変化すると, ほとんど知識のない状態から再度相互作用のみによって学習するので, 大量の相互作用が必要となる。このため学習の収束が遅くなる。また, 各環境に対する学習の際, 過度に適応すると, 少し異なる環境への適応性(汎用性)が失われるなどといった問題が考えられる。
また, 行動のルールをマイニングする場合も, 事例として, 環境(属性)と行動〔クラス〕をサンプリングして, これから行動ルールをマイニングすればよいが, この事例のサンプリングを人間が判断しながらおこなうと膨大なコスト(時間, マンパワーの両面で)かかる恐れがある。こうした両者の問題は, 強化学習と決定木を組み合わせ, 強化学習で得た結果を決定木によってマイニングすることにより, 改善できる可能性がある。
次章では, 実際に簡単なエージェントの行動習得実験を通して, 強化学習の結果から, 汎用ルールを決定木でマイニングする試みについて述べる。