价值的定义与计算-贝尔曼方程

字数统计: 2.3k字 | 阅读时长: 9分

2022-03-15

摘要: 贝尔曼方程初探

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章强化学习环境框架-从一个迷宫环境看MDP的要点中，我们总结了强化学习的基本概念，以及作为强化学习机制的 MDP，并且以 grid 为例实现了 MDP 环境的代码框架。

有了 MDP 环境之后，我们就要解决如何在其中选择最优行动的问题，也就是 MDP 环境的代码框架中的 agent.policy 方法的实现，具体来说就是价值的计算方法(价值近似)和基于价值近似的行动选择方法(策略)。

当 MDP 环境的迁移函数 transit_func 和奖励函数 reward_func 已知的时候，就可以使用动态规划法来求解。

这种基于迁移函数和奖励函数来学习行动的方法称为基于模型的学习方法。

当不知道迁移函数和奖励函数的情况下，也可以使用这种基于模型的学习方法对这两种函数进行推算，后面我们有机会再探究这种用法。此外，也可以使用无模型的学习方法，这块同样后面再探究。

使用动态规划求解最有行动有两大类方法

价值迭代: 一个是基于动态规划的价值近似的学习
策略迭代: 一个是基于动态规划的策略的学习

具体来说就是价值的计算方法(价值近似)和基于价值近似的行动选择方法(策略)。

不论使用那种方法，首先都需要先说清楚价值是如何定义和计算的，本文就解决这个问题。首先从理论上推导贝尔曼方程，然后通过一个例子理解贝尔曼方程。

价值的定义的两个问题及其解决

在文章强化学习环境框架-从一个迷宫环境看MDP的要点中，我们其实定义过价值，如下

$G_{t} = r_{t+1} + \gamma r_{t+2} + ... + \gamma^{T-t-1}r_{T} = \sum\limits_{k=0}\limits^{T-t-1}\gamma^{k}r_{t+k+1}$

但是这个价值的定义有两个问题

必须知道将来的立即奖励 $r_{t+1}, r_{t+2}, …, r_{T}$ 是多少
这个将来的立即奖励必须是能够通过计算得到的，例如抛硬币，未来某个时刻抛出正面反面是可预测的，但是实际情况是如果不实际进行投掷，就无法知道立即奖励(正面/反面)是多少。

因此直接用以上定义式计算价值是非常困难的。

(1) 递归(记忆化)

对于第一个问题，我们可以通过递归的方式解决，也就是将定义式改写如下

$G_{t} = r_{t+1} + \gamma G_{t+1}$

使用这种递归形式之后，就可以把将来的立即奖励 $G_{t+1}$ 留待之后进行。首先赋予 $G_{t+1}$ 一个适当的值，就能计算 $G_{t}$ 了。这样一来就不用知道将来的立即奖励了。

这里先赋予适当值，然后经过多次计算，值的精度会逐渐提高，接近最优解，后面的 $V(s)$ 也是这个逻辑，具体的证明看本文最后提到的参考资料。

这种通过动态规划使用过去计算的值来得到将来的立即奖励 $G_{t+1}$ 的方法称为记忆化。

(2) 行动结果的立即奖励乘以行动概率 = 期望值

对于第二个问题，可以通过对立即奖励乘以概率(立即奖励的期望)解决。例如投掷骰子，正面获得 100，反面失去 10，则正反面概率均为 0.5 的时候，期望值为 0.5 * 100 + 0.5 * 10 = 45。

难点在于如何定义行动概率，只要能定义行动概率，那么让根据行动结果得到的立即奖励乘以行动概率，即可得到期望值。

贝尔曼方程的导出

前面我们了解到，价值的定义的第二个问题是可以解决的，但是需要能够定义行动的概率。我们要先定义清楚智能体如何选择行动，然后才能进一步得到行动的概率。

有两种定义智能体行动的方法

智能体基于策略进行行动选择
智能体基于价值最大化进行行动选择

这两种方法是对强化学习分类的重要依据。

第 1 个称为基于策略的方法，根据策略决定行动，在评价和更新时才用到行动的评价方法。

第 2 个称为基于价值的方法，只学习行动的评价方法，根据评价来决定行动。

(1) 基于策略 $\pi$ 选择行动

假设当前状态为 s，行动是 a，那么行动概率就是 $\pi(a|s)$，从迁移函数得到 $T(s’|s, a)$，然后就可以得到迁移后的状态 $s’$。如下图所示

从状态 s 开始，基于策略 $\pi$ 做行动选择，得到的价值为 $V_{\pi}(s)$

这个 $V_{\pi}(s)$ 与价值 $G_{t}$ 一样，可以通过递归的形式定义。

$V_{\pi}(s_{t}) = E_{\pi}[r_{t+1} + \gamma V_{\pi}(s_{t+1})]$

上式中，将 $s_{t}$ 记为 s，$s_{t+1}$ 记为 $s’$，也就是在状态 s 时，采取了某个行动，到达了状态 $s’$。

奖励为 $R(s, s’)$，行动 a 的概率为 $\pi(a|s)$，迁移概率为 $T(s’|s,a)$。

将期望符号打开，那么 $V_{\pi}(s)$ 可以写为

$$ V_{\pi}(s) = \sum\limits_{a}\pi(a|s)\sum\limits_{s'}T(s'|s,a)[R(s, s') + \gamma V_{\pi}(s')] $$

这种通过把价值以递归以及期望值的方式表示，我们解决了前面提到的价值 $G_{t}$ 定义的两个问题。这个数学式称为贝尔曼方程。

$v(s) = R(s) + \gamma \max\limits_{a}\sum\limits_{s'}T(s'|s, a)V(s')$

(2) 基于价值最大化选择行动

基于价值最大化选择行动的情况下，将贝尔曼方程进行变换即可

$$ V(s) = \max\limits_{a}\sum\limits_{s'}T(s'|s,a)[R(s, s') + \gamma V(s')] $$

当奖励仅取决于 s 时(强化学习环境框架-从一个迷宫环境看MDP的要点中的迷宫环境框架就属于这一种)，价值公式可以写为

实现贝尔曼方程

下面看一下如何代码实现上面的 $V(s)$ 的计算过程。

V 的定义与公式中一样，其中

奖励函数 R 在回合结束(“happy_end”, “bad_end”)时返回 1, -1，其余时候返回 0
max_V_on_next_state 计算所有行动对应的价值(values)，并返回最大值 max(values)
价值 v 的计算与公式中一样，为迁移概率乘以迁移后的价值(prob * V(next_state))

def V(s, gamma=0.99):
    V = R(s) + gamma * max_V_on_next_state(s)
    return V


def R(s):
    if s == "happy_end":
        return 1
    elif s == "bad_end":
        return -1
    else:
        return 0


def max_V_on_next_state(s):
    # 如果游戏结束，则期望值是0
    if s in ["happy_end", "bad_end"]:
        return 0

    actions = ["up", "down"]
    values = []
    for a in actions:
        transition_probs = transit_func(s, a)
        v = 0
        for next_state in transition_probs:
            prob = transition_probs[next_state]
            v += prob * V(next_state)
        values.append(v)
    return max(values)

计算迁移概率的函数如下。

反复执行 up 和 down，5 次后行动结束。在结束时，如果 up 次数大于等于 HAPPY_END_BORDER，则返回 “happy_end”，否则返回 “bad_end”。

选择的行动被执行的概率为 MOVE_PROB，执行相反行动的概率为 1 - MOVE_PROB。

def transit_func(s, a):
    """
    通过合并行动字符串与状态，来生成下一个状态
    Make next state by adding action str to state.
    ex: (s = 'state', a = 'up') => 'state_up'
        (s = 'state_up', a = 'down') => 'state_up_down'
    """

    actions = s.split("_")[1:] # 历史行动
    LIMIT_GAME_COUNT = 5
    HAPPY_END_BORDER = 4
    MOVE_PROB = 0.9

    def next_state(state, action):
        return "_".join([state, action])

    if len(actions) == LIMIT_GAME_COUNT:
        up_count = sum([1 if a == "up" else 0 for a in actions])
        state = "happy_end" if up_count >= HAPPY_END_BORDER else "bad_end"
        prob = 1.0
        return {state: prob}
    else:
        opposite = "up" if a == "down" else "down"
        return {
            next_state(s, a): MOVE_PROB,
            next_state(s, opposite): 1 - MOVE_PROB
        }

实验

if __name__ == "__main__":
    print(V("state_down_down"))
    print(V("state"))
    print(V("state_up_down"))
    print(V("state_down_up"))
    print(V("state_up_up"))
    print(V("state_up_up_up_down"))

当前状态 s 持有的是历史的行动记录。由于 R(s) 中，最终 up 数量较多时对整体奖励有益。因此当前状态 s 的 up 数量较多时，得分变高，参考上面实验的执行结果，如下。

-0.96059601
0.7880942034605892
0.43995297258
0.43995297258
0.9068026334400001
0.78408

动态规划

回顾 V(s) 的计算公式

$V(s) = R(s) + \gamma\max\limits_{a}\sum\limits_{s'}T(s'|s,a)V(s')$

注意在计算 V(s) 时，V(s’) 必须已经算完，但是当状态较多的时候，这样一个一个地计算很困难。

动态规划的意思是先给 V(s’) 设定一个适当值，然后经过多次计算，值的精度会逐渐提高，接近最优解，这一点可以证明。可以参考 UCL Course on RL 中的 Lecture 3。

潮汐朝夕的生活实验室 \Doge 陪伴一个算法工程师的职业生涯

AI模型强化学习