Post | RLG

简介

第九章基于函数逼近的同轨策略预测：
用函数来拟合价值函数，关注于一个预测问题
第十章：

关注点：对动作价值函数进行参数化逼近的控制问题

$\hat q(s,a,\textbf{w}) \approx q_*(s,a)$

情况：
分幕式任务：第九章内容到策略控制的自然延伸
持续性任务：“平均收益”的形式来定义控制问题

10.1 分幕式半梯度控制

近似目标

近似动作价值函数与近似状态函数是一致的，我们需要近似动作价值函数$\hat q \approx q_\pi$，表示为具有权值向量$\mathbf w$的参数化函数形式，其近似目标可以写为：
$\overline{\mathbf{VE}}(\mathbf w)\doteq \sum_{s\in S} \mu(s)[q_\pi(s,a)-\hat q(s,\mathbf w)]^2$
在近似动作价值函数需要考虑形如$S_t,A_t \mapsto U_t$的样本，可以利用不同的近似值$U_t$去近似$q_\pi(s,a)$，比如完整的蒙特卡洛回报（$G_t$）或者n步Sarsa回报：
$G_{t:t+n} \dot{=} R_{t+1} + \gamma R_{t+2}+…+ \gamma^{n-1}R_{t+n} + \gamma^{n}Q_{t+n-1}(S_{t+n},A_{t+n})$
随机梯度下降更新的一般形式可以写为：
$\mathbf{w}_{t+1} \dot{=} \mathbf w_t+\alpha[U_t-\hat q(S_t,A_t,\mathbf w_t)]\nabla\hat q(S_t,A_t,\mathbf w_t)$

分幕式半梯度Sarsa方法

根据随机梯度下降的一般形式，半梯度单步Sarsa方法的更新可以表示为：
$\mathbf{w}_{t+1} \dot{=} \mathbf w_t+\alpha[R_{t+1}+\gamma\hat q(S_{t+1},A_{t+1},\mathbf w_t)-\hat q(S_t,A_t,\mathbf w_t)]\nabla\hat q(S_t,A_t,\mathbf w_t)$
对于一个固定的策略，这个方法的收敛情况与TD(0)一样，具有相同的误差边界。

为了得到控制方法，我们需要将这种动作价值函数预测与策略改进及动作选择结合起来。也就是说，我们对于当前状态$S_t$中的每个可能动作a能够计算$\hat q(S_t,a,\mathbf w_t)$，然后贪心地选择动作：
$A_t^*=\arg\max_a\hat q(S_{t+1},A_{t+1},\mathbf w_t)$
但是对于复杂函数（连续动作或大型离散集合）找到其最大值对应的动作是很困难的，现在还没有完美的解决方案。假设我们能够从一个较小的离散空间中选出最大值动作，那么通过将估计策略变为贪心策略的一个柔性近似，如$\epsilon$-greedy策略，那么可以得到如下的半梯度Sarsa控制方法：

例10.1 高山行车问题

图片.png

问题描述：把一辆汽车驾驶上陡峭的山顶，难点在于汽车在底部全力冲刺也无法达到目标，只能先向反方向的斜坡后退然后再全油门向目标冲。事情需要先变得更糟才能变得更好。
具体设置：
收益在所有时刻都为-1，除了山顶的目标位置，汽车到达目标回合结束
可能动作：全油门前进(+1)，全油门后退(-1)，零油门
位置和速度更新：bound限制了位置和速度的大小

图片.png

每一回合从[-0.6,-0.4)随机位置和零速度开始
瓦片编码：使用如下图所示的网格覆盖，使用8个瓦片，每个瓦片盖住每个维度的边界距离的1/8，对每一个“状态-动作”对使用瓦片编码产生特征向量$\mathbf{x}(s,a)$，并与参数向量的线性组合来逼近动作价值函数：

$\hat q(s,a,\mathbf w)\dot = \mathbf{w}^\mathsf T\mathbf x(s,a) = \sum_{i=1}^dw_ix_i(s,a)$
图片.png

# estimate the value of given state and action
def value(self, position, velocity, action):
    if position == POSITION_MAX:
        return 0.0
    active_tiles = self.get_active_tiles(position, velocity, action)
    return np.sum(self.weights[active_tiles])

# learn with given state, action and target
def learn(self, position, velocity, action, target):
    active_tiles = self.get_active_tiles(position, velocity, action)
    estimation = np.sum(self.weights[active_tiles]) # \sum_{i=1}^dw_ix_i(s,a)
    delta = self.step_size * (target - estimation) # UPDATE
    for active_tile in active_tiles:
        self.weights[active_tile] += delta # CHART UPDATE

def semi_gradient_n_step_sarsa(value_function, n=1): # 可实现半梯度n步Sarsa
    # start at a random position around the bottom of the valley
    current_position = np.random.uniform(-0.6, -0.4)
    # initial velocity is 0
    current_velocity = 0.0
    # get initial action
    current_action = get_action(current_position, current_velocity, value_function)

    # track previous position, velocity, action and reward
    positions = [current_position]
    velocities = [current_velocity]
    actions = [current_action]
    rewards = [0.0]

    # track the time
    time = 0

    # the length of this episode
    T = float('inf')
    while True:
        # go to next time step
        time += 1

        if time < T:
            # take current action and go to the new state
            new_position, new_velocity, reward = step(current_position, current_velocity, current_action)
            # choose new action
            new_action = get_action(new_position, new_velocity, value_function)

            # track new state and action
            positions.append(new_position)
            velocities.append(new_velocity)
            actions.append(new_action)
            rewards.append(reward)

            if new_position == POSITION_MAX:
                T = time

        # get the time of the state to update
        update_time = time - n
        if update_time >= 0:
            returns = 0.0
            # calculate corresponding rewards
            for t in range(update_time + 1, min(T, update_time + n) + 1): # R_t+1 + R_t+2 + .....R_t+n
                returns += rewards[t]
            # add estimated state action value to the return
            if update_time + n <= T:  # Q_t+n-1
                returns += value_function.value(positions[update_time + n],
                                                velocities[update_time + n],
                                                actions[update_time + n])
            # update the state value function
            if positions[update_time] != POSITION_MAX:
                value_function.learn(positions[update_time], velocities[update_time], actions[update_time], returns)
        if update_time == T - 1:
            break
        current_position = new_position
        current_velocity = new_velocity
        current_action = new_action

    return time

实验与结果：
显示单次运行中学习的价值函数的负值（代价函数）。最初的动作价值函数都是0，乐观初始化，这使得即使探索Epsilon为0也能引起广泛的探索。
左一：车子在山谷里沿着状态空间的弧形轨迹来回摆动，经常访问的状态价值函数都比未试探到的状态低。
改变步长对比：

图片.png

10.2 半梯度n步Sarsa

将更新目标$U_t$更换为n步回报就能得到分幕式半梯度Sarsa的n步版本
$G_{t:t+n} \dot{=} R_{t+1} + \gamma R_{t+2}+…+ \gamma^{n-1}R_{t+n} + \gamma^{n}\hat q (S_{t+n},A_{t+n},\mathbf{w_{t+f-1}}),t+n<T$
其更新公式为：
$\mathbf{w_{t+n}} \dot = \mathbf{w_{t+n+1}}+\alpha[G_{t:t+n}-\hat q(S_t,A_t,\mathbf{w_{t+n+1}})]\nabla\hat q(S_t,A_t,\mathbf w_{t+n-1}),0 \le t <T$
分幕式半梯度n步Sarsa方法流程图：
图片.png

性能验证：使用中等程度的自举法往往能够获得最好的性能，在上面的例子中对比：
单步与n步Sarsa对比：

图片.png

练习

在本章中并没有明确地讨论任何MC方法，为什么？它们在高山行车问题上有怎样的表现？

a. MC方法在复杂场景下因其巨大的计算复杂度导致其不实际。在高山行车问题中，随机策略只有完整地完成一个回合后才能开始学习，就算能够完成，庞大的数据量也会使计算代价变得巨大。相比之下，SARSA和其他TD方法能够在回合过程中学习能够更快地收敛。
b. MC可以看作是TD方法的变体，其伪代码的变化仅仅是n步SARSA的n=T

给出用于控制问题的半梯度单步期望Sarsa伪代码

图片.png

为什么较大的n比较小的n有更高的标准差：

图片.png 高山行车每幕步长在前50回合和每运行 100次取平均值
较大的n会倾向于使用更“旧”的奖励并且在早期时加强方差，这是因为在训练初期的轨迹一般都是混乱且随机的。较小的n比如n=1只会用到下一个状态，尽管作出一些混乱的随机的选择，它的影响也会被平均掉，因为它指挥提供信息给St

10.3 平均收益：持续性任务中的新的问题设定

平均收益

持续性问题：智能体与环境之间的交互一直持续而没有对应的终止或开始状态
平均收益：不考虑任何折扣，智能体对于延迟收益的重视程度与即时收益相同：

$r(\pi)\dot=\lim_{h \rightarrow \infty} {1 \over h}\sum^h_{t=1}\mathbb{E}[R_t|S_0,A_{0:t-1} \sim \pi] \\ =\lim_{t\rightarrow \infty} \mathbb{E}[R_t|S_0,A_{0:t-1} \sim \pi]\\ =\sum_s\mu_\pi(s)\sum_a\pi(a|s)\sum_{s’,r}p(s’,r|s,a)r$

期望根据初始状态$S_0$和遵循策略产生的动作序列$A_{0:t-1}$来决定的
遍历性：$\mu_\pi$是一个稳态分布，假设对于每一个$\pi$都存在并独立于$S_0$,则$\mu_\pi(s) \dot = \lim_{t \rightarrow \infty}\Pr\{S_t=s|A_{0:t-1} \sim \pi\}$
一个状态的期望只与策略本身以及MDP的转移概率相关
在大多数没有折扣的持续性任务中，根据平均收益，简单地对策略排序就足够了，认为所有达到$r(\pi)$最大值的策略都是最优的

差分回报

差分回报：在平均收益的设定中，回报根据即时收益和平均收益的差来定义：

$G_t \dot= R_{t+1} - r(\pi) +R_{t+2}-r(\pi)+…$

差分价值函数：把所有的折扣因子去掉，用即时收益和真实平均收益之间的差来代替原来的即时收益：

图片.png

差分TD误差：$\overline R_t$是时刻t对平均收益$r(\pi)$的估计，大多数算法和理论结果都不需要改变，可以适用于平均收益设定。

图片.png

example：半梯度Sarsa的平均收益版本：

$\mathbf{w_{t+1}} \dot = \mathbf{w_t}+\alpha \delta_t \nabla\hat q(S_t,A_t,\mathbf w_t)$
图片.png

练习

给出半梯度Q学习的差分版本的伪代码

Q学习在每一步选择greedy action来对最优动作价值函数直接近似，作为学习目标：
图片.png

一个MDP包含三个环状的状态ABC，状态确定地沿着环转移。到达A时获得收益+1,其他情况收益为0。对应三个状态的差分价值是多少？

这样的MDP会产生确定的收益序列：+1,0,0,+1,0,0…直到永远，这违背了遍历性，不存在稳态极限分布$\mu_\pi$但是这种情况下平均收益式是良好定义的，书上转而定义一个状态的价值为：
$v_\pi(s)\dot = \lim_{\gamma \rightarrow 1} \lim_{h \rightarrow \infty} \sum_{t=0}^h \gamma^t(\mathbb{E}[R_{t+1}|S_0=s]-r(\pi))$
图片.png

差分半梯度Sarsa算法使用$\delta_t$作为误差来更新$\overline{R_{t+1}}$，而不是简单地用$R_{t+1}-\overline{R_{t+1}}$来更新，用上一个例子来说明，平均收益的估计值应该趋向于它的真实值1/3。加入已经达到这个值并且保持固定：
误差$R_{t}-\overline{R_{t}}$的序列为：2/3,-1/3,-1/3......
误差$\delta_t$的序列为：2/3+0-2/3 = 0, -1/3+1/3-0 = 0, -1/3+2/3-1/3 = 0 ......

我们能发现当平均收益收敛时，b类方法不会更新平均收益，因为我们已经得到了精确差分价值和平均收益。这个方法能够给到更稳定的估计，因为它会在接近收敛时自动地减少振荡。

例10.2 访问控制队列任务

四个优先级不同的客户到达一个队列，客户访问服务器，会根据优先级向服务器支付不同的收益（1 2 4 8）。每个时刻队列头的客户要么被接受，分配给一个服务器；要么被拒绝，将其从队列中移除。每一个服务器在每一时刻都有0.06的概率变得空闲。任务需要在每个时刻根据优先级和空闲服务器的数量决定是否接受或拒绝下一个客户来最大化无折扣的长期收益。
状态：队列中空闲服务器的数量+客户的优先级
动作：接受 or 拒绝
方法：差分半梯度Sarsa：（服务器数量：10）

# Value functions
    def value(self, free_servers, priority, action):
        active_tiles = self.get_active_tiles(free_servers, priority, action)
        return np.sum(self.weights[active_tiles])

    # learn with given sequence
    def learn(self, free_servers, priority, action, new_free_servers, new_priority, new_action, reward):
        active_tiles = self.get_active_tiles(free_servers, priority, action)
        estimation = np.sum(self.weights[active_tiles])
        delta = reward - self.average_reward + self.value(new_free_servers, new_priority, new_action) - estimation
        # update average reward
        self.average_reward += self.beta * delta
        delta *= self.alpha
        for active_tile in active_tiles:
            self.weights[active_tile] += delta


def differential_semi_gradient_sarsa(value_function, max_steps):
    current_free_servers = NUM_OF_SERVERS
    current_priority = np.random.choice(PRIORITIES)
    current_action = get_action(current_free_servers, current_priority, value_function)
    # track the hit for each number of free servers
    freq = np.zeros(NUM_OF_SERVERS + 1)

    for _ in tqdm(range(max_steps)):
        freq[current_free_servers] += 1
        new_free_servers, new_priority, reward = take_action(current_free_servers, current_priority, current_action)
        new_action = get_action(new_free_servers, new_priority, value_function)
        value_function.learn(current_free_servers, current_priority, current_action,
                             new_free_servers, new_priority, new_action, reward)
        current_free_servers = new_free_servers
        current_priority = new_priority
        current_action = new_action
    print('Frequency of number of free servers:')
    print(freq / max_steps)

图片.png 价值函数以及策略

10.4 弃用折扣

持续性的带折扣问题的公式化表达在表格型情况下十分有用，每个状态的回报可以被分别识别和取平均。
考虑一个没有开始或者结束的无限长的收益序列，也没有清晰的可区分的状态。在评估性能时一种方法为通过计算较长时间间隔的收益的平均来进行性能的评估——平均收益。使用折扣时，每一步都能计算折后回报，有些回报大有些回报小，需要在足够大的时间间隔内进行平均。这样做需要折后回报的均值与平均回报成正比。
对于策略$\pi$，折后回报的均值为$r(\pi)/(1-\gamma)$，本质上即为平均收益$r(\pi)$
证明：
思想为在有折扣时，第$t$个收益会无折扣的出现在$t-1$个回报中，在$t-2$中打一次折扣并依此类推。第$t$个收益的权重为$1+\gamma+\gamma^2+\gamma^3+…=1/(1-\gamma)$。所有状态都是这个权重，回报的平均值则为$r(\pi)/(1-\gamma)$
一般性证明：

在一个同轨策略分布上优化折后价值函数，其效果与优化一个无折扣的平均收益相同，$\gamma$的实际值对策略排序结果没有影响。表明折扣在使用函数逼近的控制问题定义中不起作用。

10.5 差分半梯度n步sarsa

$n$步回报的差分形式，使用函数逼近：
$G_{t:t+n}=R_{t+1}-\overline R_{t+1}+R_{t+2}-\overline R_{t+2}+…+R_{t+n}-\overline R_{t+n}+\hat q(S_{t+n},A_{t+n},w_{t+n-1})$
其中$\overline R$为对$r(\pi)$的估计，$n\geq 1,t+n<T$
$n$步TD误差：
$\delta _t=G_{t:t+n}-\hat q(S_{t},A_{t},w_{t})$

核心三个步骤：