从0单排强化学习原理（二）

炼丹笔记

发布于 2021-05-14 16:02:17

3130

发布于 2021-05-14 16:02:17

文章被收录于专栏：炼丹笔记

简要回顾

距离上一期更新有点久（抱歉拖更太久，后面保证每周至少一期

），我们先做个简要回顾。上期我们提到马尔可夫决策过程，定义如下:

\left ( S,A,P,R,\gamma \right )

S: 有限状态集

A: 有限动作集合

P: 状态转移概率

R: 回报函数

\gamma: 为折扣因子，用来计算累计回报

我们需要求解最优策略:

\pi \left ( a|s \right ) = P\left ( A_t = a | S_t = s \right )

求解策略，我们需要知道每个状态的期望收益，通过值函数进行计算，值函数定义如下:

V_\pi \left ( s \right )=\sum _{a\in A}\pi \left ( a|s \right )q_\pi \left ( s,a \right )

既然本篇叫动态规划求解，那就可由“子问题”求解，即上篇介绍过的公式:

V_\pi \left ( s \right )=\sum _{a\in A}\pi \left ( a|s \right )\left ( R_s^a +\gamma \sum_{s'}P^a_{ss'}V_{\pi} \left(s' \right) \right )

基于模型的动态规划方法

现在回归本篇正文，先解读下什么叫基于模型的动态规划？基于模型指的是全部已知，未知的只有。虽然我们不知道，但是我们可以随机初始化一个，就像我们随机初始化一个神经网络参数一样，先通过这套参数算出loss，再优化这套参数。当已知时，就可以通过动态规划，用去计算。

为什么要去计算?当我们算出后，就可以通过下式去更新了：

\pi \left ( s \right )= \mathop{\arg\max}_{a} R_s^a + \gamma\sum _{s'\in S}P_{ss'}^av(s')

有没有一种坐标下降法既视感，确定，更新，确定，再回来更新，如此反复，直到收敛。但是我们看下面一个简化场景，已知，求:

，，得出结论。这...

下面介绍高斯-塞德尔迭代法(参考百度百科)，本质就是把线性方程组，通过不断迭代的方式进行求解，设线性方程组为：

高斯-赛德尔迭代法的迭代公式为：

这个和求解有啥关系呢？上式没看明白没关系，其实就是初始化所有，即在0时刻s状态的值函数计算结果是0，然后通过下式求解:

V_{\pi}^{t}(s) = f(V_{\pi}^{t-1}(s))

V_{\pi}(s) = \lim_{t\rightarrow \infty } V_{\pi}^t(s)

求解的过程叫策略评估（计算loss），通过改善的过程叫策略改善（梯度下降），不断迭代这两个过程就能得到最优解，伪代码如下:

# 策略迭代算法
input P,R,y
init all V(s) = 0, 策略
for i in range(1000000):
    find V(s)
    update 策略
    if 策略变化<阈值:
        break
输出最优策略

还有另一种算法，和策略迭代算法一样能得到解，区别就是值函数收敛后直接进行策略改善，求得最优策略，本质都是通过策略改善和策略评估求最优解。

举栗子?

如果上面还是看的一知半解，就看这个例子(看完包会

)。假设有个机器人，它电量有限，现在把它放到下图S点，需要它走到E点，我们肯定不希望机器人S->p1->S->p1->...来回横跳，这样电量耗完了都到不了E点。

因为机器人开始并不知道怎么走到E点，所以初始化。即机器人在任何state都等概率的选择一条路。我们再初始化，这样设置的原因是，机器人无论在哪，走一步都会耗一点的电量（带来损失），所以机器人必须尽快到达E点，才能使得损失最小。接下来看代码：

class robot:
    def __init__(self):
        # S
        self.states = ['S', 'P1', 'P2', 'E']
        # A : 'S_P1'表示从S点到P1点的动作，到E点就停止了，所以一共6种行为
        self.actions = ['S_P1', 'S_P2', 'P1_S', 'P1_E', 'P2_S', 'P2_E']
        # R 初始化为-1，任何action都会带来-1的收益
        self.R = -1
        # y 初始化为 1
        self.y = 1
        # init v
        self.v = {}
        self.v[0] = {}
        # v 在0时刻S,P1,P2,E状态的值函数值为0
        self.v[0]['S'] = 0.0
        self.v[0]['P1'] = 0.0
        self.v[0]['P2'] = 0.0
        self.v[0]['E'] = 0.0
        self.iter_num = 100
        # init pi
        self.pi = {}
        for act in self.actions:
            self.pi[act] = 0.5

    # 策略评估
    def policy_eval(self, t):
        if t not in self.v:
            self.v[t] = {}
        for state in self.states:
            # 筛选可行的行为
            reasonable_actions = [item for item in self.actions if item.startswith(state)]
            self.v[t][state] = 0
            for act in reasonable_actions:
                # 采取act后处于的state
                s_ = act.split('_')[1]
                self.v[t][state] += self.pi[act] * (self.R + self.y * self.v[t-1][s_])

    # 策略改善
    def policy_improve(self, t):
        for state in self.states:
            if state == 'E': continue
            # 筛选可行的行为
            reasonable_actions = [item for item in self.actions if item.startswith(state)]
            # 收益最大的action
            best_action = None
            best_R = -999999
            for act in reasonable_actions:
                # 采取act后处于的state
                s_ = act.split('_')[1]
                if best_R < self.R + self.y * self.v[t-1][s_]:
                    best_R = self.R + self.y * self.v[t-1][s_]
                    best_action = act
                self.pi[act] = 0
            # 把当前状态能带来收益最大的行为概率置为1
            self.pi[act] = 1

    def run_algo(self):
        for i in range(self.iter_num):
            self.policy_eval(i + 1)
            # 这里可以加个条件，比如v[t] - v[t-1] < thres 就跳出循环
        self.policy_improve(self.iter_num)

    def debug(self):
        print ('********debug log********')
        for i in range(0, self.iter_num + 1, 10):
            print ('t:%d V(S):%f V(P1):%f V(P2):%f' % (i, self.v[i]['S'], self.v[i]['P1'], self.v[i]['P2']))

    def get_best_action(self):
        print ('********best action********')
        for a in self.pi:
            print ('action:%s prob:%f' % (a, self.pi[a]))

我们运行debug函数，结果如下所示:

rb = robot()
rb.run_algo()
rb.debug()

********debug log********
t:0 V(S):0.000000 V(P1):0.000000 V(P2):0.000000
t:10 V(S):-3.875000 V(P1):-2.906250 V(P2):-2.906250
t:20 V(S):-3.996094 V(P1):-2.997070 V(P2):-2.997070
t:30 V(S):-3.999878 V(P1):-2.999908 V(P2):-2.999908
t:40 V(S):-3.999996 V(P1):-2.999997 V(P2):-2.999997
t:50 V(S):-4.000000 V(P1):-3.000000 V(P2):-3.000000
t:60 V(S):-4.000000 V(P1):-3.000000 V(P2):-3.000000
t:70 V(S):-4.000000 V(P1):-3.000000 V(P2):-3.000000
t:80 V(S):-4.000000 V(P1):-3.000000 V(P2):-3.000000
t:90 V(S):-4.000000 V(P1):-3.000000 V(P2):-3.000000
t:100 V(S):-4.000000 V(P1):-3.000000 V(P2):-3.000000

我们发现，到第40轮的时候就收敛了，看下值函数，因为S离E最远，所以值函数计算出来的最低，P1和P2离E相同近，所以值函数相等。再输出下最优决策：

rb.get_best_action()
********best action********
action:S_P1 prob:0.000000
action:S_P2 prob:1.000000
action:P1_S prob:0.000000
action:P1_E prob:1.000000
action:P2_S prob:0.000000
action:P2_E prob:1.000000

这就是robot最终学到的最优策略，即使开始把robot放到P1，也不用担心他会往S点走了。