Skip to content

5 时序差分算法

时序差分算法

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

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

$$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 的最大值获取策略
每个时间步（已知 s 和动作 a）：
    得到环境反馈 r, s'
    e-greedy 选一个 a'
    Q(s, a) <- Q(s, a) + alpha[r + gamma Q(s', a') - Q(s, a)]
    s, a = s', a'

# 训练部分
for i_episode in num_episodes:
    state = env.reset()
    action = agent.take_action(state)
    done = False
    while not done:
        next_state, reward, done = env.step(action)
        next_action = agent.take_action(next_state)
        agent.update(state, action, reward, next_state, next_action)
        state = next_state
        action = next_action

# 原文 Q-learning 处的写法似乎更好
...
    state = env.reset()
    done = False
    while not done:
        action = agent.take_action(state)
        next_state, reward, done = env.step(action)
        agent.update(state, action, reward, next_state)
        state = next_state


class CliffWalkingEnv:
    def step(self, action):
        ...
        return next_state, reward, done


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

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

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

n 步 Sarsa

  • 采样到至少 $n$ 步后，对最近 $n$ 步实施类似蒙特卡洛的反向更新。
class Sarsa:
    def update(self, s0, a0, r, s1, a1, done):
        self.state_list.append(s0)
        self.action_list.append(a0)
        self.reward_list.append(r)
        if len(self.state_list) == self.n:  # 若保存的数据可以进行n步更新
            G = self.Q_table[s1, a1]  # 得到Q(s_{t+n}, a_{t+n})
            for i in reversed(range(self.n)):
                G = self.gamma * G + self.reward_list[i]  # 不断向前计算每一步的回报
                # 如果到达终止状态,最后几步虽然长度不够n步,也将其进行更新
                if done and i > 0:
                    s = self.state_list[i]
                    a = self.action_list[i]
                    self.Q_table[s, a] += self.alpha * (G - self.Q_table[s, a])
            s = self.state_list.pop(0)  # 将需要更新的状态动作从列表中删除,下次不必更新
            a = self.action_list.pop(0)
            self.reward_list.pop(0)
            # n步Sarsa的主要更新步骤
            self.Q_table[s, a] += self.alpha * (G - self.Q_table[s, a])
        if done:  # 如果到达终止状态,即将开始下一条序列,则将列表全清空
            self.state_list = []
            self.action_list = []
            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)]$$

image.png

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

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

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

在线策略和离线策略

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

done.