【笔记】强化学习的数学原理

发表于 分类于 阅读次数： Valine：

分享一下学习这门课程时的笔记

\(\S 1\) 基本概念

State: 智能体的状态。State space: \(S=\{s_i\}^9_{i=1}\).

Action: 可进行的动作。Action space of a state: 与 \(s_i\)有关的集合。\(A(s_i)=\{a_k\}^5_{k=1}\).

State transition: 进行动作后，智能体从一个状态转移到另一个状态的过程。State transition probability: \(p(s_i|s_j,a_k)=\text{prob}\).

Policy: 指导智能体在某一状态下采取某一措施。数学表示：条件概率 \(\pi(a_i|s_j)=\text{prob}.\)

Reward: 在做出一个动作后得到的一个标量。正为鼓励，负为惩罚。数学表示 \(p(r=c|s_i,a_j)=\text{prob}.\)

Trajectory: 一条 state-action-reward 链。

Return: 一条路径的reward的和。

Discounted rate: \(\gamma \in (0,1)\), discounted return = \(\sum_{i=0}^{\infty}\gamma^ir_i\)，\(\gamma\) 越小，智能体越近视，反之越远视。

Episode: 从开始到结束的trajectory。

到达目标后如何停下来？将目标状态视为一种一般状态并制定一种策略，使得智能体仍可离开目标状态，并在进入目标状态时获得\(r = +1\)的奖励。我们无需将目标状态与其他状态区分开来，可将其视为一种正常状态。

Markov decision process (MDP)

MDP的要素：

  1. 集合（Sets）: State\(S\), Action\(A(s)\), Reward\(R(s,a)\)

  2. 概率分布（Probability distribution）：

    状态转移概率（State transition probability）: 在state \(s\), 选择action \(a\), 转移到state \(s'\) 的概率记为\(p(s'|s,a)\).

    奖励概率（Reward probability）: 在state \(s\), 选择action \(a\), 得到奖励 \(r\) 的概率记为 \(p(r|s, a)\).

  3. 策略（Poicy）: 在state\(s\)，选择action \(a\) 的可能性\(\pi(a|s)\).

MDP性质：memoryless property 与历史无关 \[ \begin{align} p(s_{t+1}|a_{t+1},s_t,...,a_1,s_0)=p(s_{t+1}|a_{t+1},s_t)\\ p(r_{t+1}|a_{t+1},s_t,...,a_1,s_0)=p(r_{t+1}|a_{t+1},s_t) \end{align} \] 当Policy确定时，马尔科夫随机过程变成马尔科夫过程。

\(\S 2\) 贝尔曼公式

计算return的方法

使用\(v_i\)表示从\(s_i\)出发的return。

例：

直接用定义计算： \[ \begin{align} &v_1=r_1+\gamma r_2+\gamma^2r_3+...\\ &v_2=r_2+\gamma r_3+\gamma^2r_4+...\\ &... \end{align} \] 使用Bootstrapping（自举法）: \[ \begin{align} &v_1=r_1+\gamma (r_2+\gamma r_3+...)&=r_1+\gamma v_2\\ &v_2=...&=r_2+\gamma v_3\\ &v_3=...&=r_3+\gamma v_4\\ &v_4=...&=r_4+\gamma v_1 \end{align} \]

将上式转化成矩阵形式：

\[ \underbrace{\left[\begin{array}{c}v_{1}\\ v_{2}\\ v_{3}\\ v_{4}\end{array}\right]}_{\mathbf{v}} = \left[\begin{array}{c}r_{1}\\ r_{2}\\ r_{3}\\ r_{4}\end{array}\right] + \left[\begin{array}{c}\gamma v_{2}\\\gamma v_{3}\\\gamma v_{4}\\\gamma v_{1}\end{array}\right] = \underbrace{\left[\begin{array}{c}r_{1}\\ r_{2}\\ r_{3}\\ r_{4}\end{array}\right]}_{\mathbf{r}} + \gamma\underbrace{\left[\begin{array}{cccc}0 &1&0&0\\ 0&0&1&0\\ 0&0&0&1\\ 1&0&0&0\end{array}\right]}_{\mathbf{P}} \underbrace{\left[\begin{array}{c}v_{1}\\ v_{2}\\ v_{3}\\ v_{4}\end{array}\right]}_{\mathbf{v}} \]

化简得到贝尔曼公式的特殊形式：

\[ \mathbf{v} = \mathbf{r} + \gamma\mathbf{P}\mathbf{v} \]

求解： \[ \mathbf{v}=(I-\gamma\mathbf{P})^{-1}\mathbf{r} \] 核心思想：一个状态的value依赖其它状态的value。

State value

首先引入一些符号：

单步过程分析

考虑以下单步过程：

\[ S_t \xrightarrow{A_t} R_{t + 1}, S_{t + 1} \]

关键要素

  • 时间点： \(t, t + 1\) 为离散时间点
  • 状态： \(S_t\) 表示 \(t\) 时刻的状态
  • 动作： \(A_t\) 表示在状态 \(S_t\) 下采取的动作
  • 奖励： \(R_{t + 1}\) 表示采取动作 \(A_t\) 后获得的即时奖励
  • 转移状态： \(S_{t + 1}\) 表示执行动作 \(A_t\) 后转移到的下一状态

注意：\(S_t\)、\(A_t\)、\(R_{t + 1}\) 均为随机变量。

概率控制模型

该过程由以下概率分布控制：

  1. 策略函数： \(\pi(A_t = a \mid S_t = s)\) 控制从状态 \(S_t\) 选择动作 \(A_t\) 的策略
  2. 奖励函数：\(p(R_{t + 1} = r \mid S_t = s, A_t = a)\) 控制状态-动作对 \((S_t, A_t)\) 生成奖励 \(R_{t + 1}\) 的概率
  3. 状态转移函数：\(p(S_{t + 1} = s' \mid S_t = s, A_t = a)\)控制从 \((S_t, A_t)\) 转移到下一状态 \(S_{t + 1}\) 的动态特性

假设：当前已知所有概率分布（即已知模型）。

多步动态过程可表示为： \[ S_{t}\xrightarrow{A_{t}} R_{t+1},S_{t+1}\xrightarrow{A_{t+1}} R_{t+2},S_{t+2}\xrightarrow{A_{t+2}} R_{t+3},\ldots \]

折扣回报 \(G_t\) 的定义：未来奖励的加权和 \[ G_{t} = R_{t+1} + \gamma R_{t+2} + \gamma^{2} R_{t+3} + \ldots\\ =R_{t+1}+\gamma G_{t+1} \] \(G_t\) 也是随机变量。

State value 的定义： \(G_t\)的期望 \[ v_{\pi}(s)=\mathbb{E}\left[G_{t} \mid S_{t} = s\right] \] 说明：

与策略有关，不同的策略有不同的state value。

return与state value 的区别和联系是：return 针对单个trajectory，而state value针对多个可能的trajectory的return再求平均值。

贝尔曼公式的推导

贝尔曼公式描述了不同状态的state value 之间的关系。 \[ \begin{aligned} &v_\pi(s)=\mathbb{E}[G_t|S_t=s]=\mathbb{E}[R_t+\gamma G_{t+1}|S_t=s]\\ &=\mathbb{E}[R_t|S_t=t]+\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'}p(s'|s,a)\mathbb{E}[G_{t+1}|S_{t+1}=s']\\ &=\sum_a \pi(a|s)\left[\sum_r p(r|s,a)r+\gamma \sum_{s'}p(s'|s,a)v_\pi(s')\right] \end{aligned} \]

最后一行即为贝尔曼公式。

贝尔曼公式的矩阵—向量形式

贝尔贝尔曼公式对任意的\(s \in S\)都成立，这意味着我们有\(|S|\)个方程，这些方程可以组成线性方程组。

将贝尔曼公式写成如下形式： \[ v_{\pi}(s)=r_{\pi}(s)+\gamma\sum_{s'}p_{\pi}(s'|s)v_{\pi}(s') \] 其中 \[ r_{\pi}(s)\triangleq\sum_{a}\pi(a|s)\sum_{r}p(r|s,a)r,\qquad p_{\pi}(s'|s)\triangleq\sum_{a}\pi(a|s)p(s'|s,a) \] 将所有的状态编号为\(s_i(i=1,...,n)\)

将所有这些状态方程组合在一起，并重写为矩阵-向量形式： \[ v_{\pi}=r_{\pi}+\gamma P_{\pi} v_{\pi} \] 其中：

\(v_{\pi}=[v_{\pi}(s_{1}),...,v_{\pi}(s_{n})]^{T}\in\mathbb{R}^{n}\)，

\(r_{\pi}=[r_{\pi}(s_{1}),...,r_{\pi}(s_{n})]^{T}\in\mathbb{R}^{n}\)，

\(P_{\pi}\in\mathbb{R}^{n\times n}\)，其中 \([P_{\pi}]_{ij}=p_{\pi}(s_{j}|s_{i})\)，是状态转移矩阵。

直观的例子

如果有4个状态： \[ \underbrace{\left[\begin{array}{l} v_{\pi}(s_{1}) \\ v_{\pi}(s_{2}) \\ v_{\pi}(s_{3}) \\ v_{\pi}(s_{4}) \end{array}\right]}_{v_{\pi}} = \underbrace{\left[\begin{array}{l} r_{\pi}(s_{1}) \\ r_{\pi}(s_{2}) \\ r_{\pi}(s_{3}) \\ r_{\pi}(s_{4}) \end{array}\right]}_{r_{\pi}} + \gamma \underbrace{\left[\begin{array}{llll} p_{\pi}(s_{1}|s_{1}) & p_{\pi}(s_{2}|s_{1}) & p_{\pi}(s_{3}|s_{1}) & p_{\pi}(s_{4}|s_{1}) \\ p_{\pi}(s_{1}|s_{2}) & p_{\pi}(s_{2}|s_{2}) & p_{\pi}(s_{3}|s_{2}) & p_{\pi}(s_{4}|s_{2}) \\ p_{\pi}(s_{1}|s_{3}) & p_{\pi}(s_{2}|s_{3}) & p_{\pi}(s_{3}|s_{3}) & p_{\pi}(s_{4}|s_{3}) \\ p_{\pi}(s_{1}|s_{4}) & p_{\pi}(s_{2}|s_{4}) & p_{\pi}(s_{3}|s_{4}) & p_{\pi}(s_{4}|s_{4}) \end{array}\right]}_{P_{\pi}} \underbrace{\left[\begin{array}{l} v_{\pi}(s_{1}) \\ v_{\pi}(s_{2}) \\ v_{\pi}(s_{3}) \\ v_{\pi}(s_{4}) \end{array}\right]}_{v_{\pi}} \]

贝尔曼公式的求解

可以直接求逆矩阵，但开销较大。

考虑迭代法： \[ v_{k+1}=r_{\pi}+\gamma P_{\pi}v_k \] 从而得到数列\(\{v_0,v_1,v_2,...\}\)，且有 \[ v_k \to v_{\pi} = (I-\gamma P_{\pi})^{-1}r_{\pi}, k\to \infty \]

Action value

State value：从某个state出发，智能体可以得到的平均return。

Action value：从某个state出发并选择某个action，智能体可以得到的平均return。

引入Action value是为了知道那个action更好。

Action value的定义： \[ q_{\pi}(s,a) = \mathbb{E}[G_t|S_t=s,A_t=a] \] 性质：

\(q_{\pi}(s,a)\)是关于state-action对\((s,a)\)的方程，且由\(\pi\)决定。

由于 \[ \underbrace{\mathbb{E}[G_{t}\mid S_{t}=s]}_{v_{\pi}(s)}=\sum_{a}\underbrace{\mathbb{E}[G_{t}\mid S_{t}=s,A_{t}=a]}_{q_{\pi}(s,a)}\pi(a\mid s) \] 我们得到： \[ v_{\pi}(s)=\sum_{a}\pi(a\mid s)q_{\pi}(s,a) \qquad(1) \] 之前推导的state value表达式为：

\[ v_{\pi}(s)=\sum_{a}\pi(a\mid s)\left[\underbrace{\sum_{r}p(r\mid s,a)r+\gamma\sum_{s'}p\left(s^{\prime}\mid s,a\right)v_{\pi}(s^{\prime})}_{q_{\pi}(s,a)}\right] \qquad(2) \]

对比(1)(2)，我们你可以得出action-value的方程：

\[ q_{\pi}(s,a)=\sum_{r}p(r\mid s,a)r+\gamma\sum_{s'}p\left(s^{\prime}\mid s,a\right) v_{\pi}(s^{\prime}) \qquad(3) \]

（1）用来从action value推state value。

（3）用来从state value推action value。

总结

为什么需要状态值？因为需要评价一个策略的好坏。

怎么得到状态值？求解贝尔曼方程。

为什么要关注不被策略\(\pi\)选择的动作的价值？因为策略\(\pi\)不一定最好，我们要关注所有的动作，来探索更优的策略。

\(\S 3\) 最优状态值与贝尔曼最优方程

引入

强化学习的最终目标：寻找最优策略。

本章的核心概念：最优状态值。基于最优状态值可以定义最优策略。

本章的核心工具：贝尔曼最优方程。可以用来求解最优状态值和最优策略。贝尔曼最优方程是一个特殊的贝尔曼方程。

最优策略（optimal policy）与最优状态值

定义：对于策略\(\pi ^*\)，若对任意状态\(s\in S\) 和其他任意的策略\(\pi\)，都有\(v_{\pi^*}(s)\ge v_{\pi}(s)\)，那么\(\pi ^*\)是一个最优策略，且其对应的状态是是最优状态值。

贝尔曼最优方程（BOE）

表达式： \[ v(s) = \max_{\pi(s) \in \Pi(s)} \sum_{a \in \mathcal{A}} \pi(a \mid s) \left( \sum_{r \in \mathcal{R}} p(r \mid s, a) r + \gamma \sum_{s^{\prime} \in \mathcal{S}} p\left(s^{\prime} \mid s, a\right) v\left(s^{\prime}\right) \right) \] \[ = \max_{\pi(s) \in \Pi(s)} \sum_{a \in \mathcal{A}} \pi(a \mid s) q(s, a), \] 其中

\[ q(s, a) \doteq \sum_{r \in \mathcal{R}} p(r \mid s, a) r + \gamma \sum_{s^{\prime} \in \mathcal{S}} p\left(s^{\prime} \mid s, a\right) v\left(s^{\prime}\right) . \]

这里 \(v(s)\), \(v\left(s^{\prime}\right)\) 是待求解的未知量；\(\pi(s)\) 表示状态 \(s\) 的策略；\(\Pi(s)\) 是在状态 \(s\) 所有可能策略的集合。

（持续更新中）