見出し画像

強化学習

澁谷直樹

学習目標

強化学習の基本的な理論を理解する。

  • バンディットアルゴリズム

  • マルコフ決定過程モデル

  • 価値関数

  • 方策勾配

キーワード：割引率、ε-greedy方策、UCB方策、マルコフ性、状態価値関数、行動価値関数、Q値、Q学習、REINFORCE、方策勾配法、Actor-Critic、A3C


強化学習とは

教師あり学習と教師なし学習では学習ようのデータを全て使っての分析という側面が強いですが、強化学習では初めから全てのデータが見えているわけではなく探索などを通して環境から得た知識を活用することにより長期にわたって最適の行動を選択できるよう学習するものです。

つまり、強化学習はエージェントが環境に作用しながら反応を得て学習するという手法で、子供が遊びならが間違えを繰り返して学んでいくのと似ています。教師あり学習と違って正解を直ちに教えてくれるわけではないので、どの行動がベストな選択なのかを探索していく必要がありますし、得られた経験をためて利用する仕組みが必要となります。

報酬構造

強化学習は、ゲームに勝利するなど目的がある学習でよく使われる手法です。

例えば、ロボット（エージェント）が木からリンゴをとるという目的があったとして、それをどのようにエージェントに学習させるのかという問題を扱います。

ロボットはリンゴを取れば報酬を貰えるのですが、それ以外の行動は報酬を０とするとロボットは偶然にリンゴを取るまでは何をしても報酬がなく学習効率が悪くなります。

そこで、リンゴに近づくことで少し報酬を貰えるように環境を設定しエージェントの行動を促すようにしたとします。しかし、こういった人間の考えによる報酬構造の設定が裏目に出る場合もあります。例えば、ロボットはリンゴに近づいたり離れたりを永遠に繰り返し報酬を貯め続けるという行動を学習するかもしれません。

では、リンゴから離れたらペナルティ（マイナスの報酬）を与えるとしたらどうでしょうか。この場合、ロボットと木の間に障害物があるとロボットが障害物に体当たりし続けて身動きできなくなるかもしれません。

この辺りが強化学習の難しいところです。また、あまり報酬構造に人間の考えや意向を入れすぎるとルールベースのアルゴリズムと変わらないエージェントになってしまいます。

時間要素

強化学習では時間の要素も入っています。ある時刻tでエージェントが行動を起こすとエージェントのいる状態が変わったり、報酬あるいはペナルティを受けたりします。

  1. 時刻tでエージェントは環境を観察し状態が$${s_t}$$であると認識する

  2. エージェントの現在の判断基準により、行動$${a_t}$$を選択し実行する

  3. エージェントの行動が環境に作用し、エージェントは報酬$${r_{t+1}}$$を受け取る。

  4. 時刻$${t+1}$$となり、ステップ１から繰り返す。

報酬は０あるいはマイナス（ペナルティ）も含めます。

累積報酬

時刻tの時点で、将来にわたって受け取る報酬$${r_{t+1}}$$、$${r_{t+2}}$$、$${r_{t+3}}$$、…と予測したとします。これらを全てそのまま合計すると以下の不都合が起こることがあります。

  • 報酬の合計が無限大になる可能性がある

  • 近い将来に得られる報酬と遠い将来に得られる同値の報酬に差がない

これらの問題を避けるために割引率（discount rate）と呼ばれるハイパーパラメータを使います。割引率は、ファイナンスで使われるのと同等の意味で、将来の1万円と現在の1万円なら現在の1万円の方が価値があるのを数式で表しています。

$$
\begin{align*}
 \\
R_t &= r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \gamma^3 r_{t+4} + \dots \\
       &= \sum_{k=1}^\infty \gamma^{k-1} r_{t+k}
\end{align*}
$$

割引率を考えるときは通常$${\gamma}$$は0より大きく１より小さい数値を考えます。また、$${\gamma}$$が1だと上式は単純な総和になります。

バンディットアルゴリズム

強化学習では最適な行動を選べるように学習するのが目的ですが、初期のエージェントは経験が少ないのでさまざまな行動を試す探索（exploration）が必要となります。ただし、探索ばかりしているとランダムな行動になってしまうので、得た知識を活用（exploitation）していくことも重要です。よって、探索と活用のバランスを取るような学習方法が必要となります。

多腕バンディット問題（multi-armed bandit problem）は、複数の候補から最良のものを探す問題です。

  • 複数の選択肢があるが、どれが最適かはわかっていない

  • 試行回数をなるべく少なくしつつ報酬の合計を最大化したい

このような問題を解く手法をバンディットアルゴリズム（bandit algorithm）と呼び、ε-greedy方策やUCB方策などがあります。方策（policy）とは行動を選ぶための戦略のことで行動選択を確率分布で表現します。

ちなみに、バンディットという名前は昔のスロットマシンが片腕の盗賊（バンディット）と呼ばれていたことから来ています。よって、多腕バンディットは複数の選択肢を象徴しています。

画像元：wikipedia

ε-greedy方策

ε-greedy方策（epsilon-greedy policy）では、各時刻で確率$${\epsilon}$$で探索、$${1 \, – \, \epsilon}$$で活用を行います。

  • 探索：ランダムに行動を選ぶ

  • 活用：報酬平均が最高な行動を選ぶ

この繰り返しで探索と活用のバランスを取りながら累積報酬の最大化を目指します。$${\epsilon}$$がハイパーパラメータなのでこれをうまく調節するのが難点ではあります。

また、探索が行われる確率が固定されているのでいつまで経っても探索がランダムに起きる問題があります。

UCB方策

UCB方策（upper-confidence bound policy）ではそれぞれの行動に対してスコアを計算し、スコアが最大な行動を選びます。UCB方策での探索では、あまり選ばれていない行動を積極的に選ぶように工夫されています。

$$
u_t = Q_t(a) + c \sqrt{ \frac{\log t}{ N_t(a)}}
$$

  • $${t}$$は時刻（ステップ数）

  • $${u_t}$$は時刻tのスコア

  • $${Q_t(a)}$$は行動$${a}$$の平均報酬など価値を計算したもの

  • $${N_t(a)}$$は行動$${a}$$が選ばれた数

  • $${c}$$はハイパーパラメータで探索が行われる度合いを調節します。

右辺２項目は行動aが選ばれた数$${N_t(a)}$$が増えないと、$${t}$$が増えるので全体のスコアが徐々に上がっていきます。つまり、時間が経ってもあまり選択されていない行動があればそれが優先されるようになっています。

ただし、$${\log t}$$はステップ数が増えるに従って増加率が減るのである程度時間が立つと、スコアがステップ数によって増える割合が小さくなり探索が減るようになっています。

マルコフ決定過程モデル

マルコフ性（Markov property）とは強化学習でよく使われる仮定で、将来の状態$${s_{t+1}}$$は現在の状態$${s_t}$$にのみ依存するというものです。つまり、以前の状態$${s_{t−1}}$$、$${s_{t−2}}$$、…などは考慮する必要がなくなります。

逆に言うと、状態$${s_t}$$には「現在と過去の状態から将来の状態$${s_{t+1}}$$を予測するのに必要な全ての情報」が入っていなければならないことになります。

このような仮定ができないケースでは強化学習モデルが非常に複雑になってしまいます。

マルコフ性により、状態遷移の確率は現在状態と選択された行動で決まるので長期にわたっての予測ができるようになります。このような予測に従って行動選択する手法をマルコフ決定過程（Markov decision process）と呼びます。

価値関数

これまで、最適な行動を選ぶための方策という観点から強化学習を見てきました。これはある状態における行動の確率分布を学ぶ手法です。代わって、状態を評価し価値の高い状態に遷移する行動を選ぶ手法があります。

まず、状態を評価するものとして状態価値関数(state-value function）があり、$${V(s_t)}$$と表記します。例えば、ある状態ststから将来にわたって期待される累積報酬$${R_t}$$をその状態の価値とします。

$$
V(s_t) = E(R_t|s_t)
$$

ただし、ある状態$${s_t}$$では異なる方策を選べるので、ある方策$${\pi}$$に従って得られる状態価値関数を$${V^{\pi}(s_t)}$$を書きます。

$$
V^{\pi}(s_t) = E(R_t|s_t, \pi)
$$

これはあくまでも期待値であって偶然の要素によって実際に得られる値は上下します。しかし、ある状態$${s_t}$$で常に最大の価値を出す方策ππを選べばそれが最善の方策になります。

$$
V^∗(s_t) = \max\limits_{\pi} E(R_t|s_t, \pi)
$$

この最適な状態価値関数を使って、常に次の状態の価値が最大になるような行動を選べれば良いわけです。そのため、行動価値関数（action-value function）を考えると便利です。

$$
Q^{\pi}(s_t,a_t) = E(R_t|s_t,a_t, \pi)
$$

これは状態ststから将来にわたって方策$${\pi}$$に従って行動するとして、状態$${s_t}$$で行動$${a_t}$$を選んだ場合の価値を与えるもので、Q関数と呼びます。また、Q関数が返す値をQ値と呼びます。

常にQ値が最大になるように方策を選んだとすると最善なQ関数が定義できます。

$$
Q^∗(s_t,a_t) = \max\limits_{\pi} E(R_t|s_t,a_t, \pi)
$$

以上の理論から、最適化されたQ関数を求められれば、最適な方策も決まってくることになります。

そのための手法として、Q学習（Q-Learning）とSARSA（State–action–reward–state–action）があります。

Q学習もSARSAもQ関数を学習する手法ですが、Q関数を更新する方法が異なります。

方策勾配

方策勾配法（policy gradient method）とは、方策を決める関数のパラメータを累積報酬の期待値が最大となるように学習する手法です。

方策関数とはある状態sにおいて行動aを選ぶ確率分布π(a|s)です。よって、ある状態sにおける累積報酬の期待値は、

$$
V(s) = \sum_a \pi(a|s) Q(s,a)
$$

となります。ここで方策$${\pi(a|s)}$$がパラメータ$${\theta}$$に依存するならば、$${V(s)}$$と$${Q(s,a)}$$も$${\theta}$$に依存します。よって、累計報酬が大きくなる方向（方策関数$${\pi(s|a)}$$の勾配）へパラメータを調節していけば累積報酬の期待値を最大化することができます。

方策勾配法の手法としてREINFORCE（REward Increment ＝ Non-negative Factor x Offset Reinforcement x Characteristic Eligibility）があり、AlphaGoにも使われました。

Actor-Critic

Actor-Criticは価値関数と方策勾配の両方を組み合わせたものです。Actorは方策を決め、Criticは状態と行動の価値を計算します。Criticは実際に得た報酬のサンプルから価値予測の精度を上げるように学習し、ActorはCriticから高い評価を得られるように学習します。

Actor-Criticの手法としてA3C（Asynchronous Advantage Actor-Critic）があります。

いいなと思ったら応援しよう！