はじめに
強化学習で最も基礎となるQ学習についてアルゴリズムを解説します。
ゲームをコンピューターに学習させてクリアさせたり、囲碁を学習させて囲碁世界チャンプに勝つなど、コンピューターにゲームやらせることを聞いた人は多いと思います。世の中ではAIなんて呼ばれていますね。
このようなタイプの機械学習は強化学習とよばれています。SVMやランダムフォレスト、ニューラルネットワークとは違うタイプの機械学習です。今回はそんな強化学習について説明します。
強化学習での用語
強化学習を犬の調教を例に考えます。
犬に芸を仕込むときは餌を使います。例えば「お手」の場合は飼い主が「お手!」と発声して、お手が出来たら餌を与えます。何もしない、或いは違う芸をした場合は何も与えない、更には棒で叩くなど懲罰を与えるかもしれません。強化学習ではまさにコレをコンピューターで行うのです。
先の犬の調教例をもとに、実際に使われる強化学習の用語を説明します。
- Agent( エージェント )
- 犬
- State ( 状態)
- 「犬が部屋にいる状態でお座りと発声する」等
- Action( 行動 )
- お手をする、お代わりをする、伏せをする、おすわりする等
- Reward( 報酬 )
- おやつを上げる
- Penalty( ペナルティ )
- なにもしない、棒で叩く等
State数はかなり膨大な数となります。例えば「犬が伏せている状態でお手」と「犬がおすわりしている状態でお手」は違う状態だからです。
Action数も同様に数が多くなります。
注意ですがActionはエージェントである犬の行動のみに注目するのに注意してください。人間の「お手!」と発声する行為はActionではありません。Agentの行動ではないためです。お手の発声はStateの一つということになります。
Q学習(Q-learning)
強化学習の実装には色々なアルゴリズムがありますが、最も有名でかつ一番はじめに知るべきアルゴリズムはQ学習です。様々なアルゴリズムはQ学習がベースに作られています。
Q学習ではQ関数というものを用いていますが、この関数の改良版だったりするのが、最新のアルゴリズムであったりします。そのため、まずは本Q学習の仕組みを見ていきます。
Q学習とは
現在の状態から最善のアクションを見つけ出す学習アルゴリズムです。Q学習のQとはQulaityのQであり、ここでいうQualityとは特定のアクションをした際に得られる高い報酬クオリティをもらう、という意味からきています。
今見てもさっぱりだと思いますが、Q学習の数式をみてみます。
Q({\small state}, {\small action}) \leftarrow (1 - \alpha) Q({\small state}, {\small action}) + \alpha \Big({\small reward} + \gamma \max_{a} Q({\small next \ state}, {\small all \ actions})\Big)上記式は次のようにも表されます。上式と下式は実は展開しているだけで中身は全く同じです。
Q(state,action) \leftarrow Q(state,action) + \alpha \bigl(R(state,action) + \gamma \max_{action' \in A(state')} Q(state', action') -Q(state,action) \bigr)数式がどういう意味かは後述します。今は深く見ません。とりあえず上記式の中で最も重要なQ( state, action )に着目します。この関数さえわかればQ学習がわかってきます。このQ( state, action )はQ関数、Q-tableとも呼ばれています。
Q関数(Q-table)とは
Q関数はStateとActionという2つの変数からなる関数です。
Q関数はテーブルで表され、値Q-valueを保持しています。このQ-valueを正しく返していくように学習(更新)していくことが今回のQ学習の目的です。
Q関数(Q-table)は次のように表されています。
Q-table | Action 0 | Action 1 | ….. | Action N |
State 0 | 0 | 0 | …. | 0 |
State 1 | 0 | 0 | …. | 0 |
…. | 0 | 0 | …. | 0 |
State N | 0 | 0 | …. | 0 |
Q関数は最初は0で初期化します。ランダムで初期化するという書かれているサイトもありますが、通常は0で初期化します。エージェントは基本的にはこのQ-tableが最大値を選択するように行動します。
Q関数はState, Actionの2変数をとる説明しましたが、引数であるStateは、例えば「お手」「おすわり」の発声、犬の位置(x,y)、発声社の位置(x,y)など様々な変数が関わります。プログラム的に書けば次のようになるでしょう。
State[ dog_state ][ dog_posx ][ dog_posy ][ owner_action ][ owner_posx ][ owner_posy ] …..
上記のように多次元配列の形となったりします。Actionも同様です。実装方法によってはQ-table自体が複数の変数で表現されているケースもあります。これは皆さん実装する上で決定します。
なお、Q-valueの値が報酬であるというように記載されているサイトがありますが間違いです。厳密には報酬ではなく、今までの獲得報酬量や他の行動からの影響値などの合計値となっています。
報酬は、犬の例で言えばおやつを上げる、というものです。
Q-valueには今まで獲得したペナルティーの値も入っていたりします。Q-valueは次にとるべき行動の指針として利用されるものです。
Q-table(Q値)の更新
Q-tableの更新には2つの方法があります。
- Explore(探索)
- Exploit(活用)
ExploitではQテーブルを参照し、与えられた状態からすべての取りうるアクションを検討するという手法です。すなわち、Q-tableの高い値をもとに行動をすすめます。
一方でExploreは探索、冒険するという意味です。先のExploitでは知り得た情報をもとに次の行動を決定していましたが、そうした情報を気にせず、行動するという意味になります。Exploreでは次のステートをランダムで決定します。
Exploreは非常に重要です。Q-tableを常に見るExploit戦略では、一番最初に値が更新されたとしたら、テーブルでは最初に0で初期化されているため、次の学習からは常にそこの探索しかしなくなることになります。新しい探索をしなければ永遠に同じ行動しか起こらなくなり、Q-tableの更新が行われないのです。
Exploit か Exploreか。どちらかを決定するために、よくイプシロン(ε)という変数を用いてどのような間隔でExploitかExploreを採用すべきかを決定することができます。例えば30%の確率でランダムにExploreするコードは次のようになります。ただのIF文です。実はε-greedy行動選択なんてかっこいい呼び方がありますが、ただのIF文ですので何も難しいことはありません。実際に次のようなコードが利用されています。
epsilon = 0.3 if random.random() < epsilon: // Explore else: // Exploit
Q値の更新は都度実施されます。スーパーマリオブラザーズで例えれば、右に行ったり、ジャンプする、ノコノコを踏んづける、ステージクリア、マリオが落ちて死ぬ、あるいは全クリするなどの終了条件です。これをエピソード単位(任天堂のスーパーマリオブラザーズでいうところのマリオの機数)で回していきます。エピソードは何回やるか決めておきます。一つのエピソードが終わるのは終了条件に達したときとなります。終了条件は全クリやマリオが落ちたときなど、自由に決めておきます。多くのエピソードをぶん回し、さまざまなエピソードでQ-tableを学習させていくのがQ学習です。
なお、終了条件をヒットしたものに関しては報酬がマイナスを取るなどの低い値をわたします。これがペナルティです。エピソードが進んでいけばいくほど、エージェントは学習していきます。
数式をもう一度
Q関数が理解できたところで、数式をもう一度見返してみます。
Q({\small state}, {\small action}) \leftarrow (1 - \alpha) Q({\small state}, {\small action}) + \alpha \Big({\small reward} + \gamma \max_{a} Q({\small next \ state}, {\small all \ actions})\Big)αはQ値の新しい値と古い値をどちらを優先するのかという比率を表します。
γは割引率と良い、将来のQ値の値を左右します。割引率は通常 0.8 から 0.99をとります。
rewardは何か特定の値をしたときの報酬となります。この報酬は別途テーブルで持っておきます。特定の条件で与えて良いのですが、それは自分で決めていきます。もちろんPenaltyも同様です。上記式にPenaltyは無いですが Reward = Penalty + Rewardと考えてください。
max(Q(next state,all actions))という部分ですが、これは、次のStateに遷移した際に、取り得るアクションをすべて実施し、最も高かったアクションを選択するという意味となります。なお、一番はじめにスタートした際には、Q-tableは全てゼロでした。そのため最初はQ(next state,all actions)は必ず0が返却されることになるでしょう。再帰的にすすんでいくのかな、とか考える人も多いのですが、まったくその必要はなく純粋にテーブルの値だけ見て勧めていきます。
流れのまとめ
3ステップでQ学習は実施されます
- Agent は state (s1) からはじめ、action (a1) を実施し、 reward (r1)をうけとります。
- Agent 次のアクションを Q-tableから最も高い値をしめすものを選択肢実施する もしくは ランダムに行動します(epsilon, ε)
- q-valueをアップデートします。
こうしてみると意外と簡単な作業だったんだな、と理解ができます。
Deep Q-learning
ここでは深く話しませんが、簡単にいえばQ-tableを学習でなんとかもとめちゃう、という話です。時間やリクエストがあれば記事を書いていきます。
参考文献
- https://towardsdatascience.com/simple-reinforcement-learning-q-learning-fcddc4b6fe56
- https://products.sint.co.jp/aisia/blog/vol1-12
- https://www.tcom242242.net/entry/2019/08/01/%E3%80%90%E5%BC%B7%E5%8C%96%E5%AD%A6%E7%BF%92%E3%80%81%E5%85%A5%E9%96%80%E3%80%91q%E5%AD%A6%E7%BF%92_%E8%BF%B7%E8%B7%AF%E3%82%92%E4%BE%8B%E3%81%AB/