TD法

ベルマン方程式は以下でした。

$$ V_{\pi}(s) = \sum_{a} \pi(a|s) \sum_{s'}p(s'|s,a) \Big( r(s,a,s') + \gamma V_{\pi}(s')\Big) $$

ここで実際にサンプリングした結果を元に価値を予測する手法がTD法となります。
説明用に真の価値を $V_{\pi}^*$ 、予測した価値を $V_{\pi}$、サンプリングした結果得た価値を $V_{\mu}^{'}$ と表します。
（ $\mu$ はサンプリング時に使用した方策となります）

あるステップ $t$ でサンプリングした結果得た価値は以下となります。

$$
V_{\mu}^{'}(s_t) = r_{t+1} + \gamma V_{\pi}(s_{t+1})
$$

ここでサンプリングの価値 $V_{\mu}^{'}$ と予測価値 $V_{\pi}$ の差をTD誤差(Temporal Difference Error) $\delta$ と言います。

$$
\delta = V_{\mu}^{'}(s_t) - V_{\pi}(s_t)
$$

TD誤差が少なくなるように予測値を修正する事で、真の価値を予測する手法がTD法になります。

$$
V_{\pi}^*(s_t) \approx V_{\pi}(s_t) \leftarrow V_{\pi}(s_t) + \alpha \delta
$$

$\alpha$ は学習率です。
更新式はよく展開されて書かれるのでそちらも書いておきます。

$$
V_{\pi}(s_t) \leftarrow V_{\pi}(s_t) + \alpha ( r_{t+1} + \gamma V_{\pi}(s_{t+1}) - V_{\pi}(s_t))
$$

モンテカルロ法

簡単なのでついでに説明をしておきます。
TD法では次の状態の価値を予測値で代用していましたが、最後まで展開して計算する手法をモンテカルロ法と言います。
また、最後までではなくnステップ展開する手法を MultiStep-Learning といいます。

TD法
$$
V_{\mu}^{'}(s_t) = r_{t+1} + \gamma V_{\pi}(s_{t+1})
$$
MultiStep-Learning(2step)
$$
V_{\mu}^{'}(s_t) = r_{t+1} + \gamma r_{t+2} + \gamma^2 V_{\pi}(s_{t+2})
$$
モンテカルロ法

$$
V_{\mu}^{'}(s_t) = r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + ... + \gamma^{T-1} r_{T}
$$

TD法は1ステップの即時報酬で計算できますが、モンテカルロ法は1エピソード分の報酬が必要になります。
（その代わり予測値を使う必要がなくなります）

Q学習

TD法において行動価値を予測し、方策をQ値の最大値に固定したものがQ学習になります。

$$
Q_{\mu}^{'}(s_t,a_t) = r_{t+1} + \gamma \max_{a_{t+1}} Q_{\pi}(s_{t+1}, a_{t+1})
$$

簡単な例を見てみます。
今以下のQテーブルがあったとします。

状態	アクション	Q
s0	a0	0.1
s0	a1	1
s0	a2	3
s1	a0	0
s1	a1	2
s1	a2	0

ここで (s0,a0) のアクションを取り、次の状態s1、即時報酬1だった場合を考えます。
まずは実際に得た価値ですが、以下となります。（割引率 $\gamma$ を0.9としています）

\begin{align}
Q_{\mu}^{'}(s0, a0) &= r + \gamma \max_{a'} Q_{\pi}(s1, a') \\
&=1 + 0.9 \times \max \{ 0,2,0 \} \\
&=1 + 0.9 \times 2 \\
&=2.8 \\
\end{align}

次の状態の予測値はQテーブルを見て、s1で一番値を採用しています。
この情報を元に予測値を修正します。(学習率 $\alpha$ は0.1としています)

\begin{align}
Q_{\pi}(s0, a0) &= Q_{\pi}(s0, a0) + \alpha( Q_{\mu}(s0, a0) - Q_{\pi}(s0, a0))\\
&= 0.1 + 0.1 (2.8 - 0.1)\\
&= 0.37
\end{align}

更新後のQテーブルは以下です。

状態	アクション	Q
s0	a0	0.37
s0	a1	1
s0	a2	3
s1	a0	0
s1	a1	2
s1	a2	0

これを繰り返す手法がQ学習となります。
無限回繰り返すと最適な価値に収束する事が証明されているらしいです。

探索のアクションについて

新しい土地に引っ越した場合何をするでしょうか？
まずは探索ですね、逆に長年住んでいた土地では出かける場所も決まっていることが多いでしょう。
これはトレードオフの関係になっており、探索（Exploration）と活用（Exploitation）のトレードオフといいます。

Q学習ではQ値が最大値のアクションを選ぶのでこのままでは活用しかありません。
（これをgreedyな行動といいます）
ですので、探索用のアクションを混ぜる必要があります。
探索方法はいくつかありますが、一番有名なのはε-greedy法です。
ε-greedy法はεが探索率となっており、ε以下ならランダムに移動を行うアルゴリズムです。

実装

関係ある個所を抜粋して書いています。
フレームワーク上の実装はgithubを見てください。

Config(ハイパーパラメータ)

ハイパーパラメータは以下です。

@dataclass
class Config(DiscreteActionConfig):
    epsilon: float = 0.1     # 学習時の探索率
    test_epsilon: float = 0  # テスト時の探索率
    discount: float = 0.9    # 割引率
    lr: float = 0.1          # 学習率

RemoteMemory

経験したデータを順番に取り出すだけなのでまだ意識する必要はありません。

Parameter

Qテーブルを定義します。
Qテーブルは辞書型にして状態は文字列で格納します。
Qテーブルにない状態は新しく作成する事で柔軟に格納できるようにしています。

class Parameter(RLParameter):
    def __init__(self, *args):

        # Q学習用のテーブル
        self.Q = {}

    # Q値を取得する関数
    def get_action_values(self, state: str):
        # Q値がない場合は新しく作る
        # self.config.action_num に環境側の取りうるアクション数が入っています
        # Q値の初期値は0にしています。（ランダムでも問題ありません）
        if state not in self.Q:
            self.Q[state] = [0 for a in range(self.config.action_num)]
        return self.Q[state]

Trainer

学習部分です。

class Trainer(RLTrainer):
    def train(self):
        batchs = self.remote_memory.sample()
        for batch in batchs:
            # 1stepで得た経験
            state = batch["state"]
            next_state = batch["next_state"]
            action = batch["action"]
            reward = batch["reward"]
            done = batch["done"]

            q = self.parameter.get_action_values(state)
            next_q = self.parameter.get_action_values(next_state)

            # 実際に得た価値を計算
            # doneの場合は次の状態がないので即時報酬のみとなる
            if done:
                target_q = reward
            else:
                target_q = reward + self.config.discount * max(next_q)

            # TD誤差
            td_error = target_q - q[action]

            # Qテーブル更新
            self.parameter.Q[state][action] += self.config.lr * td_error

Worker

ε-greedy法の実装部分です。
また、経験をメモリーに送っています。

class Worker(DiscreteActionWorker):
    def call_policy(self, state: np.ndarray, invalid_actions: List[int]) -> int:
        # Qテーブル用に状態を文字列にする
        self.state = str(state.tolist())

        # 学習時とテスト時で探索率を変える
        if self.training:
            epsilon = self.config.epsilon
        else:
            epsilon = self.config.test_epsilon

        if random.random() < epsilon:
            # epsilonより低いならランダムに移動
            self.action = random.randint(0, self.config.action_num - 1)
        else:
            # 最大のアクションを選択（複数あればランダム）
            q = self.parameter.get_action_values(self.state)
            q = np.asarray(q)
            self.action = random.choice(np.where(q == q.max())[0])

        return self.action

    def call_on_step(
        self,
        next_state: np.ndarray,
        reward: float,
        done: bool,
        next_invalid_actions: List[int],
    ) -> Dict:
        if not self.training:
            return {}
        
        # 得た経験をメモリに送る
        batch = {
            "state": self.state,
            "next_state": str(next_state.tolist()),
            "action": self.action,
            "reward": reward,
            "done": done,
        }
        self.remote_memory.add(batch)
        return {}

学習結果

本フレームワーク内にある Grid という環境を学習した結果は以下です。
コードは github を見てください。

参考までにこの環境における真の行動価値は以下となります。

------------------------------------------------------------
    0.523    |    0.650    |    0.801    |    0.000    |
 0.498  0.610| 0.537  0.766| 0.648  0.928| 0.000  0.000|
    0.435    |    0.650    |    0.554    |    0.000    |
------------------------------------------------------------
    0.487    |    0.000    |    0.585    |    0.000    |
 0.399  0.399| 0.000  0.000| 0.503 -0.686| 0.000  0.000|
    0.317    |    0.000    |    0.224    |    0.000    |
------------------------------------------------------------
    0.374    |    0.267    |    0.428    |   -0.753    |
 0.307  0.273| 0.288  0.327| 0.286  0.187| 0.189  0.017|
    0.292    |    0.267    |    0.314    |    0.151    |
------------------------------------------------------------

学習後の結果

Average reward for 100 episodes: 0.7500000051409006
### 0, action 3, rewards [0.], next 0
env   None
work0 None
......
.   G.
. . X.
.P   .
......


 ←  : 0.32245
 ↓  : 0.30091
 →  : 0.21025
*↑  : 0.37087

### 1, action 3, rewards [-0.04], next 0
env   {}
work0 {}
......
.   G.
.P. X.
.    .
......


 ←  : 0.40331
 ↓  : 0.30318
 →  : 0.40381
*↑  : 0.48817

### 2, action 2, rewards [-0.04], next 0
env   {}
work0 {}
......
.P  G.
. . X.
.    .
......


 ←  : 0.48795
 ↓  : 0.42966
*→  : 0.61292
 ↑  : 0.51955

### 3, action 2, rewards [-0.04], next 0
env   {}
work0 {}
......
. P G.
. . X.
.    .
......


 ←  : 0.57070
 ↓  : 0.66015
*→  : 0.80146
 ↑  : 0.64181

### 4, action 2, rewards [-0.04], next 0
env   {}
work0 {}
......
.  PG.
. . X.
.    .
......


 ←  : 0.63329
 ↓  : 0.58249
*→  : 0.96238
 ↑  : 0.77159

### 5, action 2, rewards [1.], done(env), next 0
env   {}
work0 {}
......
.   P.
. . X.
.    .
......