強化学習・モンテカルロ法
強化学習
強化学習(Reinforcement Learning) とは，自律的に行動するプログラム（ エージェント ）がある環境において， 観測した現在の状態を基に，最適な行動を選択可能にするための学習方法です． DeepMind社が開発した囲碁プログラムの AlphaGo や， Atari社のビデオゲームをプレイする DQN(Deep Q-Network) などが強化学習の成果としてよく知られています． また，強化学習には，次に挙げるような手法が存在します．
- モンテカルロ法（Monte Carlo Methods）
- TD学習(Temporal Difference Learning)
- Q学習(Q-Learning)
ここでは，シンプルなトランプゲームを題材に強化学習の基本を学び， 最後に強化学習のツールキットであるGymを利用してQ学習を実装してみます．
ノートブックの作成
Google Colaboratory を起動し，新規にノートブックを作成してください． ノートブックのタイトルは AI-12 とします． ノートブックの作成方法は第1回の資料を参照してください．
完成したノートブックの確認
トランプゲーム
次に示す2つのルールを考えます． いずれのルールもゲームに勝てば100円を獲得し，負ければ100円が没収されます． ルール1には引き分けがないことに注意してください．
ルール1
同じ絵柄のトランプから2枚のカードを順に引き，カードの数字を比較する．
1枚目のカードの数字が，2枚目のカードの数字より大きいとき，報酬として100円が与えられる．
逆に小さいときは，ペナルティとして100円が没収される(同じ数字になることはない)．
ルール2
2人のプレイヤーが同じ絵柄のトランプから2枚のカードを順に引き，2枚のカードの数字を合計する．
2枚のカードの合計が，相手より大きいとき，報酬として100円が与えられ，逆に小さいときはペナルティとして100円が没収される（合計が同じ場合は引き分け）．
ただし，1枚目のカードを引いた時点で，ゲームから降りることを決めることができる．
実装
乱数を生成するrandom，数値計算のためのnumpyに加え，
プログレスバーを表示するtqdm.notebookをインポートします．
import random
import numpy as np
from tqdm.notebook import tqdm
ルール1の実装
それでは，ルール1を実装しましょう．
同じ絵柄のトランプを使用するため，カードの数字は$1,2,\cdots,13$の13種類です．
このカードから，random.sample()でランダムに2枚を選択し，1枚目のカードの数字の方が大きければ100円を獲得し，
逆に小さければ100円を没収されます．
# トランプ
cards = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
def game():
# 2枚のカードを引く
my_cards = random.sample(cards, 2)
card1 = my_cards[0]
card2 = my_cards[1]
if card1 > card2:
return (card1, 100) # You win
else:
return (card1, -100) # You lose
このゲームを10回繰り返してみます． この結果，勝ちは4回，負けは6回だったため，-600円が所持金となりました．
# 所持金
money = 0
for i in range(10):
card, reward = game()
print(f"{i}: card={card} reward={reward}")
money += reward
print(f"Your money: {money}")
0: card=5 reward=-100
1: card=8 reward=100
2: card=9 reward=100
3: card=5 reward=-100
4: card=6 reward=-100
5: card=5 reward=-100
6: card=3 reward=-100
7: card=3 reward=-100
8: card=3 reward=-100
9: card=3 reward=-100
Your money: -600
カードの数字に応じて，得られる報酬の期待値（価値）が異なります． そこで，強化学習の考えに基づき，カードの数字の価値を求めてみましょう． カードの数字は 状態$s$ として定義され，13種類の状態が存在します．
$$ S = \{ s_1, s_2, \cdots, s_{13} \} $$
また，勝負の結果，獲得または没収される金額を 報酬r と定義します． 報酬$r$は勝利したとき100，負けたとき-100となります． このとき，状態$s_x$の価値$V(s_x)$は，次の式を繰り返し適用することで求めることができます（得られる値は近似値）． ここで，$\alpha$は学習率と呼ばれ，$0<\alpha<1$の値を取ります．
$$ V’(s_x) = (1 - \alpha) \cdot V(s_x) + \alpha \cdot r $$
最初に，カードの数字の価値を$0$で初期化します．
# カードの数字の価値（報酬の期待値）
values = {
1: 0,
2: 0,
3: 0,
4: 0,
5: 0,
6: 0,
7: 0,
8: 0,
9: 0,
10: 0,
11: 0,
12: 0,
13: 0
}
次に，ゲームを100,000回繰り返して，上記の式を適用します． このとき，学習率$\alpha$は$0.001$に設定しています．
# 学習率
alpha = 0.001
for i in tqdm(range(100000)):
card, reward = game()
values[card] = (1 - alpha) * values[card] + alpha * reward
for card in values:
print(f"card={card} value={values[card]:.2f}")
この結果，次に示す状態の価値$V(s_x)$が算出されました． $s_1$は常に負けるため価値は約$-100$，一方，$s_{13}$は常に勝利するため価値は約$100$になっています． また，$s_7$は，50%の確率で勝利し，50%の確率で負けるため，その価値は約$0$になっています．
このように，ランダムにゲームを繰り返し，状態の価値（報酬の期待値）を推定する手法を モンテカルロ法 と呼びます．
card=1 value=-99.95
card=2 value=-83.49
card=3 value=-64.86
card=4 value=-50.15
card=5 value=-28.72
card=6 value=-19.50
card=7 value=2.72
card=8 value=17.22
card=9 value=32.62
card=10 value=48.44
card=11 value=66.18
card=12 value=84.95
card=13 value=99.96
ルール2の実装
それでは，ルール2を実装しましょう． 上述と同じように モンテカルロ法 で状態の価値を算出します． プレイヤーのそれぞれが同じ絵柄のトランプを利用します（プレイヤーAは クラブ，プレイヤーBは ダイヤ）． プレイヤーは2枚のカードを引き，それらの合計を求めます． この合計が多い方が100円を獲得します（合計が同じ場合は0円の獲得）．
# トランプ
cards = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
def game():
# 2枚のカードを引く
my_cards = random.sample(cards, 2)
rival_cards = random.sample(cards, 2)
card1 = my_cards[0]
card2 = my_cards[1]
# カードの値を合計
my_sum = np.sum(my_cards)
rival_sum = np.sum(rival_cards)
if my_sum > rival_sum:
return (card1, card2, my_sum, 100) # You win
elif my_sum == rival_sum:
return (card1, card2, my_sum, 0) # Draw
else:
return (card1, card2, my_sum, -100) # You lose
このゲームを10回繰り返してみます． この結果，勝ちは5回，負けは4回，引き分けは1回だったため，100円が所持金となりました．
# 所持金
money = 0
for i in range(10):
card1, card2, sum, reward = game()
print(f"{i}: card1={card1} card2={card2} sum={sum} reward={reward}")
money += reward
print(f"Your money: {money}")
0: card1=13 card2=7 sum=20 reward=100
1: card1=13 card2=4 sum=17 reward=100
2: card1=5 card2=9 sum=14 reward=100
3: card1=4 card2=3 sum=7 reward=-100
4: card1=1 card2=12 sum=13 reward=0
5: card1=13 card2=1 sum=14 reward=100
6: card1=12 card2=4 sum=16 reward=100
7: card1=4 card2=1 sum=5 reward=-100
8: card1=11 card2=6 sum=17 reward=-100
9: card1=4 card2=11 sum=15 reward=-100
Your money: 100
カードの数字の合計を 状態$s$ と定義します． 最小値は$1+2=3$，最大値は$12+13=25$であり，23種類の状態が存在します．
$$ S = \{ s_3, s_4, \cdots, s_{25} \} $$
先程と同様に，状態$s_x$の価値$V(s_x)$を算出してみます． 最初に，カードの数字の合計の価値を$0$で初期化します．
# 数字の合計の価値（報酬の期待値）
sum_values = {
3: 0,
4: 0,
5: 0,
6: 0,
7: 0,
8: 0,
9: 0,
10: 0,
11: 0,
12: 0,
13: 0,
14: 0,
15: 0,
16: 0,
17: 0,
18: 0,
19: 0,
20: 0,
21: 0,
22: 0,
23: 0,
24: 0,
25: 0
}
次に，ゲームを500,000回繰り返して，価値を算出する式を適用します． このとき，学習率$\alpha$は$0.001$に設定しています．
# 学習率
alpha = 0.001
for i in tqdm(range(500000)):
card1, card2, sum, reward = game()
sum_values[sum] = (1 - alpha) * sum_values[sum] + alpha * reward
for sum in sum_values:
print(f"sum={sum} value={sum_values[sum]:.2f}")
この結果，次に示す状態の価値$V(s_x)$が算出されました．$s_3$は，引き分けを除き，その他の全ての合計値に負けるため価値は約-100， 一方，$s_{25}$は，引き分けを除き，その他の全ての合計値に勝利するため価値は約100になっています（正確には100より少し小さい）． また，$s_{14}$は，50%の確率で勝利し，50%の確率で負けるため，その価値は約$0$になっています．
sum=3 value=-98.37
sum=4 value=-96.56
sum=5 value=-92.11
sum=6 value=-89.50
sum=7 value=-81.11
sum=8 value=-71.71
sum=9 value=-64.69
sum=10 value=-54.91
sum=11 value=-43.56
sum=12 value=-27.25
sum=13 value=-16.98
sum=14 value=0.36
sum=15 value=16.55
sum=16 value=30.30
sum=17 value=44.61
sum=18 value=53.65
sum=19 value=62.89
sum=20 value=73.66
sum=21 value=78.19
sum=22 value=86.03
sum=23 value=91.78
sum=24 value=95.24
sum=25 value=98.67
ここで，ゲームのルールを思い出してみましょう．
「ただし，1枚目のカードを引いた時点で，ゲームから降りることを決めることができる．」
つまり，1枚目を引いた時点でのカードの価値がわかれば無理に勝負をする必要はないことになります． そこで，1枚目のカードの価値を算出してみましょう．
1枚目のカードの数字は 状態$t$ として定義し，13種類の状態が存在します．
$$ T = \{ t_1, t_2, \cdots, t_{13} \} $$
状態$t_x$の価値$V(t_x)$は，次の式を繰り返し適用することで求めることができます． 報酬$r$が，カードの合計値の価値$V(s_x)$に置き換わっていることがわかります． このように，将来の状態の価値を基に，現在の状態の価値を更新する方法を ブートストラップ型学習 と呼びます．
$$ V’(t_x) = (1 - \alpha) \cdot V(t_x) + \alpha \cdot V(s_x) $$
# 1枚目のカードの価値（報酬の期待値）
card_values = {
1: 0,
2: 0,
3: 0,
4: 0,
5: 0,
6: 0,
7: 0,
8: 0,
9: 0,
10: 0,
11: 0,
12: 0,
13: 0
}
ゲームを500,000回繰り返して，ブートストラップ型学習で1枚目のカードの価値を算出します． このとき，学習率$\alpha$は$0.001$に設定しています．
# 学習率
alpha = 0.001
for i in tqdm(range(500000)):
card1, card2, sum, reward = game()
sum_values[sum] = (1 - alpha) * sum_values[sum] + alpha * reward
card_values[card1] = (1 - alpha) * card_values[card1] + alpha * sum_values[sum]
for card in card_values:
print(f"card={card} value={card_values[card]:.2f}")
この結果，次に示す状態の価値$V(t_x)$が算出されました． $t_1$の価値は約$-60$となり負ける可能性が高く， $t_{13}$の価値は約$60$となり勝つ可能性が高いことを示しています．
card=1 value=-60.76
card=2 value=-51.00
card=3 value=-41.24
card=4 value=-32.77
card=5 value=-19.22
card=6 value=-9.60
card=7 value=0.58
card=8 value=9.65
card=9 value=18.31
card=10 value=33.06
card=11 value=40.74
card=12 value=51.62
card=13 value=62.09
課題
ルール2を変更し，合計値が同じであったら1000円を獲得し，それ以外の場合は-100円を没収することにする． このとき，$V(s_x)$と$V(t_x)$はどのような値になるか示せ．
Google Colaboratoryで作成した AI-12.ipynb を保存し， ノートブック（.ipynb） をダウンロードして提出しなさい． 提出の前に必ず下記の設定を行うこと．
- ノートブックの設定で「セルの出力を除外する」のチェックを外す
- ノートブックの変更内容を保存して固定