在环境 environment 中，智能体 agent 处于某个状态 state，它以一定概率 $\pi (a|s)$ 执行不同行为 action，每次执行行为都有概率 $p(r|s,a)$ 获得奖励 reward，并有概率 $p(s^{\prime }|s,a)$ 变成为下一个状态。为了获得最大奖励，智能体通过估计从每个状态出发或执行每个行为能获得的未来奖励总和 value，来更新它的行为决策概率分布 policy。这就是强化学习的过程。

价值计算

智能体执行一系列行为后，可以得到一条路径：

$$S_t\stackrel{A_t}{\to }{S}_{t+1}\stackrel{A_{t+1}}{\to }{S}_{t+2}\stackrel{A_{t+2}}{\to }...$$

为了估计价值 value，我们把每次行为获得的奖励相加：

$$R_{t+1}+R_{t+2}+R_{t+3}+...$$

由于智能体可以进行无数次行为，求得奖励总和是无穷大。所以引入折扣因子，即赋予最近的奖励更大的权重：

$$G_t=R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\cdots$$

由于智能体每次都可能执行不同行为，进而得到不同的奖励总和 $G_t$，所以使用期望值表示状态价值，其中 $s$ 表示初始状态：

$$v_{\pi }(s)=\mathbb{E}[G_t|S_t=s]$$

为了理解不同状态间的关系，将 $v(s)$ 拆分为及时奖励和未来奖励：

$$\begin{array}{rl}{v}_{\pi }(s)& =\mathbb{E}[R_{t+1}+\gamma G_{t+1}|S_t=s]\\ & =\mathbb{E}[R_{t+1}|S_t=s]+\gamma \mathbb{E}[G_{t+1}|S_t=s]\\ & =\sum _a\pi (a|s)\sum _{r}p(r|s,a)r+\gamma \sum _a\pi (a|s)\sum _{s^{\prime }}p(s^{\prime }|s,a)v_{\pi }(s^{\prime })\\ & =\sum _a\pi (a|s)[\sum _{r}p(r|s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }|s,a)v_{\pi }(s^{\prime })]\end{array}$$

这就得到了贝尔曼方程。

INFO

如果我们更关心采取什么行为能获得最大奖励，那就需要计算行为价值 $q(s,a)$，它表示在状态 $s$ 下执行行为 $a$ 后获得的奖励总和：

$$\begin{array}{rl}{q}_{\pi }(s,a)& =\mathbb{E}[G_t|S_t=s,A_t=a]\\ & =\sum _{r}p(r|s,a)r+\sum _{s^{\prime }}p(s^{\prime }|s,a)v_{\pi }(s^{\prime })\end{array}$$

由此得到 $q_{\pi }(s,a)$ 和 $v_{\pi }(s)$ 的关系：

$$v_{\pi }(s)=\sum _a\pi (a|s)q_{\pi }(s,a)$$

Bellman equation, 贝尔曼方程

$$v_{\pi }(s)=\sum _a\pi (a|s)[\sum _{r}p(r|s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }|s,a)v_{\pi }(s^{\prime })]$$

贝尔曼方程中有两种概率分布：$\text{Policy}$ 和 $\text{Model}$，策略决定行为，环境模型决定奖励和状态转移。

对方程进一步简化得到，其中 $s_i$ 表示初始状态，$s_j$ 表示下一个状态：

$$v_{\pi }(s_i)=r_{\pi }(s_i)+\gamma \sum _{s_j}p(s_j|s_i)v_{\pi }(s_j),i,j=1,2,3,\cdots$$

进而得到矩阵形式：

$$\begin{array}{rl}\left[\begin{array}{c}{v}_{\pi }(s_1)\\ v_{\pi }(s_2)\\ ⋮\\ v_{\pi }(s_n)\end{array}\right]& =\left[\begin{array}{c}{r}_{\pi }(s_1)\\ r_{\pi }(s_2)\\ ⋮\\ r_{\pi }(s_n)\end{array}\right]+\gamma \left[\begin{array}{cccc}p(s_1|s_1)& p(s_2|s_1)& \cdots & p(s_n|s_1)\\ p(s_1|s_2)& p(s_2|s_2)& \cdots & p(s_n|s_2)\\ ⋮& ⋮& \ddots & ⋮\\ p(s_1|s_n)& p(s_2|s_n)& \cdots & p(s_n|s_n)\end{array}\right]\left[\begin{array}{c}{v}_{\pi }(s_1)\\ v_{\pi }(s_2)\\ ⋮\\ v_{\pi }(s_n)\end{array}\right]\\ \\ v_{\pi }& =r_{\pi }+\gamma P_{\pi }{v}_{\pi }\end{array}$$

其中 $P_{\pi }$ 表示状态转移矩阵。通过这个方程我们发现任意策略 $\pi$ 都对应唯一的状态价值向量 $v_{\pi }$，表示在策略 $\pi$ 下执行无数次行为后在各状态获得的奖励总和：

$$v_{\pi }=(I-\gamma P_{\pi }{)}^{-1}{r}_{\pi }$$

Bellman optimality equation, 贝尔曼最优方程

最优策略 ${\pi }^{\ast }$ 指其状态价值向量 $v_{{\pi }^{\ast }}$ 中的每一项都比其他策略 $\pi$ 状态价值向量 $v_{\pi }$ 中的对应项都更大。

找最优策略就是求解贝尔曼最优方程，它表示最优策略 ${\pi }^{\ast }$ 对应的贝尔曼方程：

$$v=\underset{\pi }{max}(r_{\pi }+\gamma P_{\pi }v)$$$$v(s)=\underset{\pi }{max}\sum _a\pi (a|s)q(s,a),s\in S$$

可以发现 $v(s)$ 是 $q(s,a)$ 的加权平均，其中权重由 $\pi (a|s)$ 决定。所以一个最优策略一定只会选择 $q(s,a)$ 最大的行为 $a^{\ast }$，即为 $a^{\ast }$ 权重赋 1。

根据贝尔曼最优公式的性质，通过不断迭代可以获得最优策略。

参考资料

• huggingface Deep RL Course
• 西湖大学赵世钰《强化学习的数学原理》github、bilibili