Reinforcement Learning Chapter2

本文参考《Reinforcement Learning：An Introduction（2nd Edition）》Sutton

K臂赌博机

问题描述：你有k个选择，每个选择对应一个奖励，收益由所选动作决定的平稳概率分布产生，目标为最大化某段时间内的总收益期望。

联系我们在chapter1中提到的reward，value， action等概念，我们在这个K臂赌博机上可以这样思考：

在时刻t， 我们基于现有策略，选择了action（a），带来了即时奖励（reward）R（s,a）,根据R（s,a）我们自然的修正了对于动作a的value估计与对于状态s的value估计，从而更新了我们的策略。

对于K臂赌博机，我们不需要考虑状态价值，因为每一次的选择与下一次的收益无关（非Markov过程），所以我们应当着重考虑如何根据我们的reward来进行对于a的value估计，同时策略q在这个问题中并不重要，一个显然的事实就是，最优策略是若确定了所有a的value，我们每次都将选择价值最高的a，这个一定能达到目标。然而我们并不能确定，所以需要靠估计。

此时出现了一个困境：如果持续对动作的价值进行估计，则对任意时刻t总有至少一个动作的value估计是最高的，这时不妨称这种动作为贪心动作，那么如果我们直接在不确定所有a的value的情况下直接套用最优策略，每次都选择当前最优a，那么很可能发生的情况是，若此时有一个a的动作收益是确定的，另几个a‘的收益与a相差不多但是有很大的不确定性（收益由所选动作决定的平稳概率分布产生），这种不确定性足够使得至少有一个动作实际上会好于贪心动作，但是如果你一直选择贪心动作你将无法发现这个更优的动作。所以该如何平衡“探索”还是“贪心”？这个问题是RL中的一个经典问题。

接下来我们从对动作的价值估计算法谈起：

一种自然的方法是计算实际收益的平均值来估计动作价值：在k-armed bandit问题上使用他是有其适用性的，我们的每次选择不随时间状态改变其收益的概率分布，所以根据大数定律，在足够次的采样之后，实际收益的平均值将收敛于实际动作价值。

 Q_t(a) -> q_*(a)当采样次数足够大；

那么现在我们在上述方法的基础上考虑如何选择动作：在上文已经说明我们陷入了“探索”与“贪心”的困境，针对于这个困境，一种比较显然的方法是我们在大部分时间表现的比较贪心，偶尔随机探索，这种方法被称为ε-greedy方法。具体而言是这样的，在每一步我们以1-ε概率选择贪心策略，以ε概率独立于动作价值估计等概率地随机选择所有动作之一。这个方法在时刻足够长的时候将把每一动作无限采样，得到对所有动作的准确价值估计，从而使得选择最优动作的概率收敛到1-ε。

import random
import matplotlib.pyplot as plt

k = 10
base_reward = [round(random.uniform(0,1),3) for i in range(k)] # k=10 10-armed Bandit 
print(base_reward)

reward_expectancy=[0 for i in range(k)]
print(reward_expectancy)

steps = 1000
current_cumulative_value = [[0,0] for i in range(k)]
for i in range(steps):
    epsilon_reward = random.uniform(-0.2,0.2)
    choice = random.randint(0, 9)
    current_cumulative_value[choice][0] += base_reward[choice] + epsilon_reward
    current_cumulative_value[choice][1] += 1
    
for i in range(k):
    print(f"{i} value is {current_cumulative_value[i][0]/current_cumulative_value[i][1]} and {base_reward[i]}")

print("********************************")

#action_value_method
greedy_epsilon = 0.1
steps = 10000
current_cumulative_value = [[0,0] for i in range(k)]
correct_rate = []
correct_choice_num = 0
for i in range(steps):
    epsilon_reward = random.uniform(-0.2,0.2)
    if (random.uniform(0,1) > greedy_epsilon):
        choice = reward_expectancy.index(max(reward_expectancy))
        current_cumulative_value[choice][0] += base_reward[choice] + epsilon_reward
        current_cumulative_value[choice][1] += 1
        reward_expectancy[choice] = current_cumulative_value[choice][0]/current_cumulative_value[choice][1]
    else:
        choice = random.randint(0, 9)
        current_cumulative_value[choice][0] += base_reward[choice] + epsilon_reward
        current_cumulative_value[choice][1] += 1
        reward_expectancy[choice] = current_cumulative_value[choice][0]/current_cumulative_value[choice][1]
    if choice == base_reward.index(max(base_reward)):
        correct_choice_num += 1
    correct_rate.append(correct_choice_num/(i+1))
        
for i in range(k):
    print(f"{i} value is {reward_expectancy[i]} and {base_reward[i]}")
plt.plot(correct_rate)

上述为10-armed bandit的一个模拟，读者可以尝试修改其中的参数如steps、epsilon甚至是对动作价值初始化的方式来更好感受RL。

上述代码在更新动作价值估计的部分仍有可以优化的地方，这里可以考虑使用一种叫做增量式更新的方法（这种方法很重要，在后面的许多章节会持续提到）：

 在这个问题中对第n次更新：stepsize = 1/n，target=R_n，oldEstimate=Qn
对于一个收益分布不随时间概率变化的bandit问题，下述算法是一种解决方法

然而，事实上很多RL问题的收益分布是动态的，上述的方法并不适用，此时又该如何？

这里需要引入EMA的概念，指数移动平均：读者不妨参考这篇blog：【炼丹技巧】指数移动平均（EMA）的原理及PyTorch实现 - 知乎 (zhihu.com)，简而言之EMA相比于之前的直接平均的好处在于它更关注近期数据，为他们赋予了更高的平均权重，从而减轻了数据噪声的影响。所以我们可以得到新的Q_n的恒定步长更新公式：

这里值得一提的是，从数学上看若要Qn以概率1收敛于真实值时，需要有:

但显然EMA不满足上述式子，所以所得的Q的估计也会随最近的收益而变化，不过这不恰好对应了动态收益分布的特征吗？

读者不难发现我们对Q的更新算法或多或少都依赖于其初始化的值，对采样平均法而言这种初始化的偏差会在每个动作都被尝试后消失， 对恒定步长的方法而言则是会随时间逐渐减小。

那么如何让恒定步长也能避免偏差？我们尝试为恒定步长引入修正系数，并且这个修正系数应当不依赖于初始值：

联系Q的更新式即可发现此时Q_n与Q₁无关。

诚然ε-greedy是一种有效的方法去平衡试探-贪心；但是对ε-greedy而言，任何状态的action只分两类：最优和普通，它将所有非当前最优action等同对待，试探时随机从中抽取动作，这显然是一种盲目的选择。一种比较自然的做法是在探索时选择那些更有潜力成为最优的动作（简单而言就是当前方差比较大但是当前对该action的估计与最优足够接近），所以基于UCB(置信度上界)的方法被提出了，公式如下：

N_t(a)：动作a在t时刻前被选择的次数；c：试探程度，当c=0时，UCB退化为greedy（不是ε-greedy！），当N_t(a)=0时自动认为a是满足最大化条件的动作（即直接选择采用动作a），这样基本可以保证任何可能动作在学习过程中都被选取过。而且随着t不断增大，若动作a价值估计低（Q_t(a)太小）或者被选择太多次（N_t(a)太大），则动作a被选择的概率将下降。

UCB是一种很有效的算法，但也有其局限之处：1、上述式子一般由于平稳奖励分布，非平稳情况UCB方法的复杂度较高；2、对于较大的状态空间，UCB目前没有很好的近似手段；

以上两种方法都是基于动作价值的估计来选择动作，但这并不是唯一的方向；动作之间的关系不仅可以用动作价值这样的具体数值来表示，也可以相互比较来进行衡量；

这里我们基于随机梯度上升思想提出了一种算法：

首先定义偏好函数：

逻辑很简单，就是拿当前的收益和之前选择该动作的收益的估计（这里是均值的形式）做比较，如果当前收益大就增大偏好函数值使得下一次选择更有可能选到这个动作，其他动作则是相应减少，但保持总概率之和不变；理论推导读者自行阅读教材（可参考：梯度赌博机算法：公式推导 - 知乎 (zhihu.com)）

注意一点，这里对于该动作的收益估计有很多种方式可以做到，取均值只是为了方便实践并且简单，但它对算法的最终效果无太大影响，只是影响收敛的速度。

还有一种算法叫关联搜索，就是为动作与状态构建一个动作-状态对，进而学习任务相关的动作策略，之后我们将进一步讨论它。