训练部分 - how to

时序差分算法

用于评估价值函数，$alpha$ 为常数，和蒙特卡洛一样是基于采样。优点在于，每采样一步就可以更新状态估计。
同样会收敛。

下式中 $t$ 为模拟的时间步。

1
$$V(s_t) <- V(s_t) + alpha [r_t + gamma V(s_(t + 1)) - V(s_t)]$$

Sarsa

用于求解最优策略。
时序差分能估计 $V$，但没法直接拿到策略.
然而时序差分算法也可以用来估计动作价值函数 $Q(s_t, a_t)$ :
以 $1 - epsilon$ 概率采样动作价值最大的动作，剩下概率随机选一个
每次采样步更新：$Q(s, a) <- Q(s, a) + alpha [r + gamma Q(s^prime, a^prime) - Q(s, a)]$
- 字母定义见下代码
最后通过 Q table 的最大值获取策略

1
每个时间步（已知 s 和动作 a）：
2
    得到环境反馈 r, s'
3
    e-greedy 选一个 a'
4
    Q(s, a) <- Q(s, a) + alpha[r + gamma Q(s', a') - Q(s, a)]
5
    s, a = s', a'

1
# 训练部分
2
for i_episode in num_episodes:
3
    state = env.reset()
4
    action = agent.take_action(state)
5
    done = False
6
    while not done:
7
        next_state, reward, done = env.step(action)
8
        next_action = agent.take_action(next_state)
9
        agent.update(state, action, reward, next_state, next_action)
10
        state = next_state
11
        action = next_action
12

13
# 原文 Q-learning 处的写法似乎更好
14
...
15
    state = env.reset()
25 collapsed lines
16
    done = False
17
    while not done:
18
        action = agent.take_action(state)
19
        next_state, reward, done = env.step(action)
20
        agent.update(state, action, reward, next_state)
21
        state = next_state
22

23

24
class CliffWalkingEnv:
25
    def step(self, action):
26
        ...
27
        return next_state, reward, done
28

29

30
class Sarsa:
31
    def update(self, s0, a0, r, s1, a1):
32
        td_error = r + self.gamma * self.Q_table[s1, a1] - self.Q_table[s0, a0]
33
        self.Q_table[s0, a0] += self.alpha * td_error
34

35
    def take_action(self, state):
36
        if np.random.random() < self.epsilon:
37
            action = np.random.randint(self.n_action)
38
        else:
39
            action = np.argmax(self.Q_table[state])
40
        return action

效果：采取比较原理悬崖的方式抵达目标。

n 步 Sarsa

采样到至少 $n$ 步后，对最近 $n$ 步实施类似蒙特卡洛的反向更新。

1
class Sarsa:
2
    def update(self, s0, a0, r, s1, a1, done):
3
        self.state_list.append(s0)
4
        self.action_list.append(a0)
5
        self.reward_list.append(r)
6
        if len(self.state_list) == self.n:  # 若保存的数据可以进行n步更新
7
            G = self.Q_table[s1, a1]  # 得到Q(s_{t+n}, a_{t+n})
8
            for i in reversed(range(self.n)):
9
                G = self.gamma * G + self.reward_list[i]  # 不断向前计算每一步的回报
10
                # 如果到达终止状态,最后几步虽然长度不够n步,也将其进行更新
11
                if done and i > 0:
12
                    s = self.state_list[i]
13
                    a = self.action_list[i]
14
                    self.Q_table[s, a] += self.alpha * (G - self.Q_table[s, a])
15
            s = self.state_list.pop(0)  # 将需要更新的状态动作从列表中删除,下次不必更新
8 collapsed lines
16
            a = self.action_list.pop(0)
17
            self.reward_list.pop(0)
18
            # n步Sarsa的主要更新步骤
19
            self.Q_table[s, a] += self.alpha * (G - self.Q_table[s, a])
20
        if done:  # 如果到达终止状态,即将开始下一条序列,则将列表全清空
21
            self.state_list = []
22
            self.action_list = []
23
            self.reward_list = []

训练部分不变会传入一个环境产生的 done.

效果：采取更保守的策略，更原理悬崖边。

Q-learning

$$Q(s_t, a_t) <- Q(s_t, a_t) + alpha [r + gamma max_a Q(s_(t + 1), a) - Q(s, a)]$$

更新 Q 的公式不同，但采样过程可以用 $epsilon$ 贪心走到下一步。

1
class QLearning:
2
    def update(self, s0, a0, r, s1):
3
        td_error = r + self.gamma * self.Q_table[s1].max(
4
        ) - self.Q_table[s0, a0]
5
        self.Q_table[s0, a0] += self.alpha * td_error

效果：生成的策略更激进，策略回报也更优。但是交互过程采用 $epsilon$ 贪婪，常会掉进悬崖，训练过程中采样的回报较差。

在线策略和离线策略

原文声称，on-policy 指模拟采样策略（行为策略）和更新公式（目标策略）一致的策略。例如 Sarsa.
- 在线策略的目标就是老老实实最小化采样回报。而离线策略采样回报和严格按照策略执行的回报会不一致。
不一致则为离线策略

done.