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

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

$ 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: at state \(s\), taking action \(a\), the probability to transit to state \(s'\) is \(p(s'|s,a)\).
   • Reward probability: at state \(s\), taking action \(a\), the probability to get reward \(r\) is \(p(r|s, a)\).
3. Poicy: At \(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} \]

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

（持续更新中）