Skip to content

AU3323 人工智能基础

Uninformed

Method Description Fringe Completeness Optimality Time Space
BFS FIFO Yes Yes (cost = 1) \(O(b^d)\) \(O(b^d)\)
UCS 相当于 Dijkstra 优先扩展累计代价和较小的 Yes Yes (BFS 的扩展) \(O(b^{1+[C^*/\varepsilon]})\) \(O(b^{1+[C^*/\varepsilon]})\)
DFS LIFO Yes (Avoid Duplication) No \(O(b^m)\) \(O(bm)\)
IDS 用限制深度的 DFS =DFS Yes Yes (cost = 1) \(O(b^d)\) \(O(bd)\)
ILS 用限制累计 cost 的UCS =UCS Yes Yes =UCS \(O(b[C^*/\varepsilon])\)

Informed

Method Description Fringe Completeness Optimality Time Space
GBFS 只使用 \(h(n)\) 按 \(f(n)=h(n)\) 排序 Yes No \(O(b^m)\) worst \(O(b^m)\)
Beam Search Top K 进行扩展
A* UCS+GBFS 按照 \(f(n)=h(n)+g(n)\) 排序 Yes Yes(Admissble \(h(n)\))

Ch2 Game

Ch3 CSP

Ch4 MDP

MDP 建立在事先知道转移函数 \(T(s,a,s')\)（也叫 \(P(s'|s,a)\)）的基础上，通俗来说就是知道采取特定 Action 后环境的可能变化以及转变的概率。也叫做 Model based.

定义 $$ Q_{\pi}(s_t,a_t)=\mathbb E_{S_{t+1},A_{t+1},\cdots,S_{n},A_n}[U_t |S_t=s_t,A_t=a_t] $$ 根据策略 \(\pi(a|s)\) 确定。 $$ Q^*(s_t,a_t)=\max_{\pi} Q_{\pi}(s_t,a_t) $$

\(Q^*\) 为采取最佳策略的动作价值函数。

\[ \pi^*=\arg \max_{\pi} Q_{\pi}(s_t,a_t) \]

\(\pi^*\) 为当前动作价值函数 \(Q_{\pi}\) 可以推出的最佳策略。

\[ V_\pi(s_t)=\mathbb E_{A_t}[Q_\pi(s_t,A_t)] \]

\(V\) 为当前状态下的折扣回报的期望

\[ V^*(s_t)=\max_a Q^*(s_t,a) \]

\(V^*\) 为当前状态下采取最好策略的折扣回报。

Bellman Equation $$ Q_{\pi}(s_t,a_t)=\mathbb E_{S_{t+1},A_{t+1}}[R_t+\gamma Q_{\pi}(S_{t+1},A_{t+1})] $$

走两步：SARSA

变体（本质描述的事情还是 Bellman 方程） $$ Q_{\pi}(s_t,a_t)=\mathbb E_{S_{t+1}}[R_t+\gamma V_{\pi}(S_{t+1})] $$

\[ Q^*(s_t,a_t)=\mathbb E_{S_{t+1}}[R_t+\gamma \max_a Q^*(S_{t+1},a)] \]

用于 Value Iteration

\[ V_{\pi}(s_t)=\mathbb E_{A_t,S_{t+1}}[R_t+\gamma V_{\pi}(S_{t+1})] \]
\[ V^*(s_t)=\max_a \mathbb E_{S_{t+1}}[R_t+\gamma V^*(S_{t+1})] \]

用于 Value Iteration

Value Iteration 流程

  1. 对所有状态，设 \(V^*(s)=0\)；
  2. 根据上述两个 Value Iteration 的公式进行迭代；
  3. 重复以上流程，直到 \(V^*\) 收敛。

也可以将迭代过程看成深度依次递增的搜索。

Value Iteration 效率

单次迭代 \(O(S^2 A)\) 因为 \(O(S)\) 次求 \(V^*\)，每次求值时间复杂度 \(O(SA)\).

Policy Iteration 流程

Policy Improvement 过程: $$ \pi'=\arg \max_a Q_{\pi}(s_t,a) $$ 总流程：

  1. 给定初始策略 \(\pi\)；
  2. 通过 Policy Evaluation 得到 \(Q_{\pi}\) 和 \(V_{\pi}\)；
  3. 基于 Policy Improvement 得到新的策略 \(\pi'\)；
  4. 重复 2,3 直到收敛。

单次迭代 \(O(S^2+SA)\)

On policy 和 Off policy

通过迭代逼近 \(V^*\) 和 \(Q^*\)，从而间接求取 \(\pi^*\)，称为 off-policy；基于策略 \(\pi\)，通过迭代逼近 \(V_{\pi}\) 和 \(Q_{\pi}\) 称为 on-policy. 计算 \(V_{\pi}\) 和 \(Q_{\pi}\) 时 \(\pi\) 不变。

Ch5 RL

不知道转移函数（Model free）很难去求 \(\mathbb E_{S_{t+1}}\). 将 Value Iteration 的公式写成样本均值的形式： $$ V_{\pi}(s_t)\approx \frac{1}{N}\sum_{i=1}^N [r_t(s_t,a,s_i)+\gamma V_{\pi}(s_i)] $$ 问题在于还是不知道 \(V_{\pi}(s_i)\).

Direct Evaluation/Monte Carlo

需要走完一个完整的 Episode 采集过程。

Temporal Difference 技巧

即进行加权如下所示： $$ V_{\pi}(s_t) \gets (1-\alpha)V_{\pi}(s_t)+\alpha(r(s_t,a,s_i)+\gamma V_{\pi}(s_i)) $$ 理解 1：加权，理解 2：梯度下降更新

SARSA

需要更新 \(Q_{\pi}(s,a)\)，即 $$ Q_{\pi}(s_t,a_t)\gets(1-\alpha)Q_{\pi}(s_t,a_t)+\alpha(r(s_t,a_t,s_{t+1})+\gamma Q_{\pi}(s_{t+1},a_{t+1})) $$ SARSA 流程：

  1. 给定策略 \(\pi\)，初始化 \(Q_{\pi}(s,a)\)
  2. 根据 TD 公式更新 \(Q_{\pi}\)
  3. 重复步骤 2 直到收敛
  4. 通过 Policy Improvement 公式提升 \(\pi\)，回到 2.
  5. \(\pi\) 收敛则算法结束。

多步 TD

$$ Q_{\pi}(s_t,a_t)\gets (1-\alpha)Q_{\pi}(s_t,a_t)+\alpha \left(\sum_{i=0}^{m-1}\gamma^i r_{t+i}+\gamma^mQ_{\pi}(s_{t+m},a_{t+m})\right) $$ 若 \(m\) 很大，则变为蒙特卡洛算法

Q-learning $$ Q^(s_t,a_t)\gets (1-\alpha ) Q^(s_t,a_t) +\alpha \left(r_{t}(s_t,a_t,s_{t+1})+\gamma \max_aQ^*(s_{t+1},a)\right) $$ （接下来采取的是最好的策略）

Behaviour Policy 和 Target Policy

\(\boldsymbol {Q_{\pi}}\) 和 \(\boldsymbol{Q^*}\) 的参数化表达

将 \(Q\) 表达为 $$ Q(s,a)=\sum_{i=1}^N w_i f_i(s,a) $$ 得到观测 \(q\)，希望尽可能接近当前观测 \(q\)，用梯度下降更新（链式求导可得） $$ W\gets W+\alpha (q-Q(s,a)) \underbrace{\nabla Q(s,a;W)}{=f_i(s,a)} $$ 即 $$ w_i \gets w_i+\alpha \left(q-\sum{i=1}^N w_i f_i(s,a)\right)f_i(s,a) $$