Q学習の実戦と理論

#はじめに
強化学習の基本となるQ学習について復習も兼ねて書く。
#理論
Q学習とは強化学習手法TD学習の一つで、Q値(状態行動価値)をエージェントが行動するたびに更新する手法である。時刻$t$での状態を$s_t$、行動を$a_t$、状態$s_t$のもとで行動$a_t$を起こすことによって得られる報酬を$r_t$とする。また、Q値$Q(s_t,a_t)$とはある状態$s_t$においてある行動$a_t$を取った時の価値のことである。価値の更新は以下のように行われる。
$$
Q(s_t,a_t) \leftarrow Q(s_t,a_t) + \alpha(r_{t+1}+\gamma \max_{a_{t+1}}Q(s_{t+1},a_{t+1})-Q(s_t,a_t))
$$
$\alpha$は学習の大きさを制御するパラメーターで0~1の値を取る。$\gamma$は将来の価値をどれほど考慮するかのパラメータで0~1をとる。$\max_{a_{t+1}}Q(s_{t+1},a_{t+1})$は状態$s_{t+1}$において得られる最大の価値である。この式は$Q(s_t,a_t)$、$\alpha(r_{t+1}-Q(s_t,a_t))$、$\alpha\gamma\max_{a_{t+1}}Q(s_{s_{t+1}}{a_{t+1}})$に分けて考えると理解しやすい。第一式は前回の価値であり、基準と考える。つまり第二式、第三式によって更新の程度が決まる。第二式は前回の価値と報酬の差をなくすように更新している。単に差を加算するだけではその時偶然得た報酬に過剰に依存してしまうため$\alpha$によって制御している。第三式は将来の価値について見積もっている。次に得られる最大の価値を将来の価値として考えており、$\alpha\gamma$によって制御されている。$\alpha$は第二式と同様の制御、$\gamma$は見積もりの不確かさによる割引率である。

#実戦(具体例)
具体例として2腕バンディット問題について考える。0~2000の数字がランダムに出てくる山Aと0~1000の数字がランダムに出てくる山Bがあるとする。どちらか一方の山から数字を取得とするとき、より大きな数字(報酬)を得ることができる可能性が高い山を選択できるようなモデルを作成する。更新回数$t$(更新回数$t$は理論での時刻$t$とは異なることに注意)での山A、山Bの価値を$Q_t(A),Q_t(B)$とし、その初期値はどちらも0とする。更新するごとに価値を元とに生成した確率で山を選択し、出た数字によって選択した山に対する価値を更新する。選択した山から出た数字は$r_t$とする。確率は$P_t(A),P_t(B)$とし、$$P_{t+1}(A)=\frac{\exp(\beta Q_t(A))}{\exp(\beta Q_t(A))+\exp(\beta Q_t(B))}$$で計算する。価値の更新は$Q_{t+1}(X)=Q_t(X)+\alpha(r_t-Q_t(X))$によって行う。(時間発展はない系を考えているため理論で扱った第三項はない)
$\alpha=0.05,\beta=0.004$として、以上の設定を100回更新をした。価値は以下のように更新された。
![value.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/591069/1068c008-b661-f040-c185-7e101d592f49.png)
それぞれ山を選ぶ確率は以下のように更新された。
![prob.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/591069/5e0d4432-f633-fe4e-4328-85aca0261a87.png)

## コード
```python
import numpy as np
import matplotlib.pyplot as plt

# seed値固定
np.random.seed(71)

#　引いた総数
N = 100

# 山A:0~2000
pileA = np.array([i for i in range(2001)])
# 山B:0~1000
pileB = np.array([i for i in range(1001)])

# パラメーター
alpha = 0.05
beta = 0.004

"""
変数
Q_A: (時間ごと)山Aの価値
Q_A: (時間ごと)山Bの価値
P_A: (時間ごと)山Aを引く確率
P_B: (時間ごと)山Bを引く確率
select_pile: (時間ごと)選択した山
"""
Q_A = [0]
Q_B = [0]
P_A = []
P_B = []
select_pile = []

for i in range(N):
    P_A.append(np.exp(beta * Q_A[i]) / (np.exp(beta * Q_A[i]) + np.exp(beta * Q_B[i])))
    P_B.append(np.exp(beta * Q_B[i]) / (np.exp(beta * Q_A[i]) + np.exp(beta * Q_B[i])))
    if P_A[i] >= np.random.rand():
        select_pile.append(1)
        Q_A.append(Q_A[i] + alpha * (np.random.choice(pileA, 1)[0] - Q_A[i]))
        Q_B.append(Q_B[i])
    else:
        select_pile.append(0)
        Q_A.append(Q_A[i])
        Q_B.append(Q_B[i] + alpha * (np.random.choice(pileB, 1)[0] - Q_B[i]))

# 時間
t = np.array([i for i in range(N)])

plt.scatter(t, Q_A[1:], c="blue", marker="o", label="A")
plt.scatter(t, 1000*np.ones(N), c="black", marker=".", s=3)
plt.scatter(t, Q_B[1:], c="red", marker="o", label="B")
plt.scatter(t, 500*np.ones(N), c="black", marker=".", s=3)
plt.title("Q")
plt.legend()
plt.savefig("value.png")
plt.show()

plt.scatter(t, select_pile, c="green", marker="s", s=10)
plt.plot(t, P_A, color=(1,0,0), marker="o", label="A")
plt.plot(t, P_B, color=(0,0,1), marker="o", label="B")
plt.title("prob")
plt.legend()
plt.savefig("prob.png")
plt.show()
```
時間発展のある系ではコードが大量になるのでここでは紹介しなかった。「cartpole qlearning」などで検索すると多くの記事が出てくるので気になる方はそこを見ていただきたい。
# 参考
理論:[Sutton, Richard S. (1998). Reinforcement Learning: An Introduction.](http://incompleteideas.net/book/RLbook2018trimmed.pdf)
問題引用:[データ分析のための数理モデル](http://incompleteideas.net/book/RLbook2018trimmed.pdf)