【学习笔记】强化学习基本概念
为了加强理解，我们以《超级玛丽》游戏为例，让 AI 使用强化学习，操作马里奥走动和跳跃，完成通关任务。
术语
Agent
用强化学习驱动的作用对象，也就是下面 Action 的作用对象。在《超级玛丽》游戏中，这个 Agent 就是 AI 控制的马里奥。
State
当前系统状态，用 \(s\) 表示。
Action
作用对象执行的操作或动作，用 \(a\) 表示。例如，在《超级玛丽》游戏中，所有的操作包括往左走 (left)、往右走 (right)、往上走 (up)。那么，
\[ a \in \{left, right, up\} \]
Policy
策略函数，用 \(\pi\) 表示。策略函数是根据当前观测到的状态，控制 Agent 如何从动作库（Action）中选择一种动作来执行。策略函数是一个条件概率密度函数，即 \(\pi :(s, a) \mapsto [0, 1]\)
\[ \pi (a | s) = \mathbb{P}(A = a | S = s) \]
例如,
\(\pi(left | s) = 0.5\)
\(\pi(right | s) = 0.3\)
\(\pi(up | s) = 0.2\)
强化学习就是学习出这个策略函数。基于策略函数，控制 Agent 每一步选择出一个最优动作，完成目标。
Reward
奖励，用 \(R\) 表示。Agent 每做一次动作，系统就会给与一定的奖励。奖励定义的好坏非常影响强化学习的结果。例如，在《超级玛丽》游戏中，
搜集到一个金币：\(R = +1\)
赢得比赛：\(R = +10000\)
输掉比赛：\(R = -10000\)
什么都没发生：\(R = 0\)
强化学习的目标，是获得的奖励总和要尽量高。
State Transition
状态转移。在执行了一个动作后，系统从一个状态变成另一个状态的过程，就是状态转移。用下面的图表示：
graph LR
A[old state]--action--->B[new state]
状态转移可以是随机的。这种随机性来源于环境 (Environment)。状态转移满足如下的公式：
\[ p(s'|s, a) = \mathbb{P}(S' = s' | S = s, A = a) \]
强化学习的随机性来源
Action 有随机性
State Transition 有随机性
执行流程
graph TD
S1["s(1)"]-->A1{"a(1)"}
A1-->S2["s(2)"]
A1-.->R1("r(1)")
S2-->A2{"a(2)"}
A2-->S3["s(3)"]
A2-.->R2("r(2)")
S3--"……"--->ST["s(T)"]
ST-->AT{"a(T)"}
AT-->ST1["s(T+1)"]
AT-.->RT("r(T)")
形成 (state, action, reward) 的轨迹 (trajectory): \[
(s_1,a_1,r_1), (s_2,a_2,r_2), \dots , (s_T, a_T, r_T)
\]
Return
回报，未来的累计奖励 (Cumulative future reward)。\(t\) 时刻的未来累计回报用 \(U_t\) 表示，有如下公式：
\[ U_t = R_t + R_{t+1} + R_{t+2} + R_{t+3} + \dots \]
从经验来看，未来的奖励 (reward) 有时不如当下的奖励来得有价值。 例如，当下的 100 元比一年后的 100 元更有价值。 为了体现这一点，我们可以给未来的每一项奖励乘上一个取值范围是 [0, 1] 的因子，变成
\[ U_t = R_t + \gamma^{1}R_{t+1} + \gamma^{2}R_{t+2} + \gamma^{3}R_{t+3} + \dots \]
形成折扣回报 (Discounted return，即 Cumulative discounted future reward)。其中 \(\gamma\) 是介于 0 到 1 之间的折扣率 (discount rate)。 折扣率是一项超参数 (Hyper-parameter)，可以在训练时被调优。
\(t\) 时刻的回报是随机的，这是因为回报依赖于未来的奖励；而未来的奖励则依赖于未来的动作和状态。 后两者都具有随机性，这也使得回报必然具有随机性。用数学公式再来整理一遍：
由于：
- 动作具有随机性: \[\mathbb{P}(A = a | S = s) = \pi (a | s)\]
- 状态转移具有随机性: \[\mathbb{P}(S' = s' | S = s, A = a) = p(s'|s, a)\]
对于任意的 \(i \ge t\)，奖励 \(R_i\) 依赖于 \(S_i\) 和 \(A_i\)。因此，给定 \(S_t\), 回报 \(U_t\) 应依赖于随机变量：\(A_t, A_{t+1}, A_{t+2}, \dots\) 和 \(S_t, S_{t+1}, S_{t+2}, \dots\)
Value Functions
Action-Value Function
动作价值函数，是在某一时刻 \(t\)，对给定的策略函数 \(\pi\)，输出某个动作 \(a_t\)，得到未来回报期望的函数。用 \(Q\) 表示。即
\[ Q_{\pi}(s_t, a_t) = \mathbb{E}[U_t|S_t=s_t, A_t=a_t] \]
\(U_t\) 是\(a_t, a_{t+1}, a_{t+2}, \dots\) 和 \(s_t, s_{t+1}, s_{t+2}, \dots\) 的函数。
\[ U_t = U(a_t, a_{t+1}, a_{t+2}, \dots, s_t, s_{t+1}, s_{t+2}, \dots) \]
计算期望时，所有的\(a_{t+1}, a_{t+2}, \dots\) 和 \(s_{t+1}, s_{t+2}, \dots\) 都应被积分（或累加）掉，最后只保留 \(a_t\) 和 \(s_t\)。
\(t\) 时刻对不同的策略函数分别求期望，找出期望值最大的那个动作价值函数，即可得到最优动作价值函数 (Optimal action-value function)。 \[ Q^*(s_t, a_t) = \max_{\pi}Q_{\pi}(s_t, a_t) \]
\(Q^*\) 与 \(\pi\) 无关。
State-Value Function
对所有的动作 \(A\)，计算 \(Q\) 的期望，可得到状态价值函数（State-value function)。用下面公式表示：
\[ V_{\pi}(s_t) = \mathbb{E}_A[Q_{\pi}(s_t, A)] \]
因为 \(A\) 服从策略函数定义的概率分布，即 \(A \sim \pi(\cdot|s_t)\)，因此上式也可以写成
（动作是离散的情况） \[ V_{\pi}(s_t) = \mathbb{E}_A[Q_{\pi}(s_t, A)] = \sum_a \pi(a|s_t)\cdot Q_{\pi}(s_t, a) \] （动作是连续的情况） \[ V_{\pi}(s_t) = \mathbb{E}_A[Q_{\pi}(s_t, A)] = \int_a \pi(a|s_t)\cdot Q_{\pi}(s_t, a) da \]
两种价值函数的作用
动作价值函数评估的是，对于给定的策略函数 \(\pi\)，Agent 处在状态 \(s\) 时，选择动作 \(a\) 的好坏。
状态价值函数评估的是，对于给定的策略函数 \(\pi\)，Agent 处在状态 \(s\) 的好坏。
如果要评估策略函数本身的好坏，可以对所有状态 \(S\) 求状态价值函数的期望，即 \[ \mathbb{E}_S[V_{\pi}(S)] \]
AI 如何控制 Agent
假设我们有一个好的策略函数 \(\pi(a|s)\)，那么我们只需要基于当前时刻的状态 \(s_t\)，随机采样一个动作即可: \[ a_t \sim \pi(\cdot|s_t) \]
假设我们知道最优动作价值函数 \(Q^*(s, a)\)，那么我们只需要基于当前时刻的状态 \(s_t\)，选择一个可以最大化动作价值函数的动作即可：
\[ a_t = \arg\max_a Q^*(s_t, a) \]
由此可见，强化学习的目标既可以是策略函数 \(\pi(a|s)\)，也可以是最优动作价值函数 \(Q^*(s, a)\)。