强化学习定义
强化学习是学习一个最优策略 (policy)，可以让智能体(agent) 在特定环境 (environment) 中，根据当前的状态(state)，做出行动(action)，从而获得最大回报 Gain。
有限马尔卡夫决策过程
找到最优价值
\[\text{Reinforcement Learning} \doteq \pi_* \\ \quad \updownarrow \\ \pi_* \doteq \{\pi(s) \}, \ s \in \mathcal{S} \\ \quad \updownarrow \\ \begin{cases} \pi(s) = \underset{a}{argmax} \ v_{\pi}(s' | s, a), \ s' \in S(s), \quad \text{or} \\ \pi(s) = \underset{a}{argmax} \ q_{\pi}(s, a) \\ \end{cases} \\ \quad \updownarrow \\ \begin{cases} v_*(s), \quad \text{or} \\ q_*(s, a) \\ \end{cases} \\ \quad \updownarrow \\ \text{approximation cases:} \\ \begin{cases} \hat{v}(s, \theta) \doteq \theta^T \phi(s), \quad \text{state value function} \\ \hat{q}(s, a, \theta) \doteq \theta^T \phi(s, a), \quad \text{action value function} \\ \end{cases} \\ where \\ \theta \text{- value function's weight vector} \\ \]
有限马尔卡夫决策过程的基本概念
\(S, s\) state 状态
\(A, a\) action 行动
\(R, r\) reward 奖赏
\(G_t\) gain 回报
\(p(s' | s, a)\) 表示在状态 \(s\) 下，执行行动 \(a\)，状态变成\(s'\) 的可能性，也就是前文的 \(P_{ss'}^a\)
\(p(s', r | s, a)\) 表示在状态 \(s\) 下，执行行动 \(a\)，状态变成\(s'\)，并获得奖赏\(r\) 的可能性
\(r(s, a)\) 在状态 \(s\) 下，执行行动 \(a\) 的期望奖赏 \[r(s,a) \doteq \mathbb{E}[R_{t+1} | S_t = s, A_t = a] = \sum_{r \in \mathcal{R}} r \sum_{s' \in \mathcal{S}} p(s', r|s,a) \]
\(r(s, a, s')\) 在状态 \(s\) 下，执行行动 \(a\)，状态变成\(s'\) 的期望奖赏 \[r(s,a,s') \doteq \mathbb{E}[R_{t+1} | S_t = s, A_t = a, S_{t+1} = s'] = \frac{\sum_{r \in \mathcal{R}} r p(s',r|s,a)}{p(s'|s,a)} \]
\(\pi\) 策略
\[\pi = [\pi(s_1), \cdots, \pi(s_n)] \]
\(v_{\pi}(s)\) 策略 \(\pi\) 的状态价值函数 \[v_{\pi}(s) \doteq \mathbb{E}[G_t | S_t = s] = \mathbb{E}_{\pi} \left [\sum_{k=0}^{\infty} \gamma^k R_{t+k+1} | S_t = s \right ] \\ \]
\(q_{\pi}(s, a)\) 策略 \(\pi\) 的行动价值函数
\[q_{\pi}(s,a) \doteq \mathbb{E}[G_t | S_t = s, A_t = a] = \mathbb{E}_{\pi} \left [\sum_{k=0}^{\infty} \gamma^k R_{t+k+1} | S_t = s, A_t = a \right ] \\ \]
\(v_{*}(s)\) 最优状态价值函数 \[v_*(s) \doteq \underset{\pi}{max} \ v_{\pi}(s), \forall s \in \mathcal{S} \]
\(q_{*}(s, a)\) 最优行动价值函数 \[q_*(s, a) \doteq \underset{\pi}{max} \ q_{\pi}(s, a), \ \forall s \in \mathcal{S} \ and \ a \in \mathcal{A}(s) \\ \]
强化学习术语
学习任务
- 情节性任务(episodic tasks)
指（强化学习的问题）会在有限步骤下结束。比如：围棋。 - 连续性任务(continuing tasks)
指（强化学习的问题）有无限步骤。一个特征是：没有结束。比如：让一个立在指尖上的长棍不倒。
学习方法
- online-policy
评估的策略和优化的策略是同一个 边学边干 - offline-policy
优化策略使用来自外部的模拟数据 先学再干
学习的东西
- 预测算法
计算每个状态的价值 \(v(s)\)。然后预测(可以得到最大回报的) 最优行动。 - 控制算法
计算每个状态下每个行动的价值\(q(s,a)\)
学习的算法
- 列表方法
表格存储每个状态 / 状态 - 行动的价值 - 近似方法
用一个函数计算状态 / 状态 - 行动的价值 - 模型
环境的模型 - 基于模型的方法
通过模型来模拟，获得状态或行动的价值 - 无模型的方法
使用试错法来获得状态或行动的价值 - 引导性
（状态或者行动）价值是根据其它的（状态或者行动）价值计算得到的 - 取样性
（状态或者行动）价值，或者部分值（比如：奖赏）是取样得到的。
强化学习算法的分类
| 算法类别 | 需要模型 | 引导性 | 情节性任务 | 连续性任务 |
|---|---|---|---|---|
| 动态规划方法 | Y | Y | - | - |
| 蒙特卡罗方法 | N | N | Y | N |
| 时序差分方法 | N | Y | Y | Y |
| 策略梯度方法 | N | Y | Y | Y |
如何选择算法
动态规划方法：如果有一个模型，可以获得价值函数 \(v(s)\) 或者 \(q(s, a)\) 的值
蒙特卡罗方法：如果可以模拟一个完整的情节
时序差分方法：如果需要在模拟一个情节中间就要学习策略
\(\lamdba \sum return\) ——用来优化近似方法中的误差。 资格迹——用来优化近似方法中价值函数的微分。
预测方法——求状态价值方法 \(v(s)\) 或者\(\hat{v}(s, \theta)\)。
控制方法——求行动价值方法 \(q(s, a)\) 或者\(\hat(q)(s, a, \theta)\)。
策略梯度——求策略方法 \(\pi(a|s, \theta)\)
算法列表
动态规划
- 使用随机策略 \(\pi (a|s)\) 来迭代计算\(v(s)\)
- 通过使用迭代策略 \(\pi(s)\) 来优化了计算 \(v(s)\) 部分，但是还是使用了期望值
- 优化了整个流程，直接用行动的最大回报作为 \(v(s)\) 的值
蒙特卡罗方法
- 在每个情节中，记录状态 \(s\) 第一个\(G\)。 \[v(s) = avg(G(s)) \]
- 从一个特定起始点的蒙特卡洛方法，变成了计算 \(q(s, a)\)
- 在探索中使用 \(\epsilon-soft\) 策略
- 支持 off-policy
- 使用了贪婪策略来支持 off-policy
时序差分方法
- 在一个情节进行过程中学习。
- 视为蒙特卡罗方法的通用化。蒙特卡罗方法是步数为完成情节的 TD 算法。
多步时序差分方法
基于模型的算法
近似预测方法
近似控制方法
\(\lamdba-return\) 和资格迹
策略梯度方法
策略梯度方法就是求 \(\pi(a | s, \theta)\)
\[\text{Reinforcement Learning} \doteq \pi_* \\ \quad \updownarrow \\ \pi_* \doteq \{\pi(s) \}, \ s \in \mathcal{S} \\ \quad \updownarrow \\ \pi(s) = \underset{a}{argmax} \ \pi(a|s, \theta) \\ where \\ \pi(a|s, \theta) \in [0, 1] \\ s \in \mathcal{S}, \ a \in \mathcal{A} \\ \quad \updownarrow \\ \pi(a|s, \theta) \doteq \frac{exp(h(s,a,\theta))}{\sum_b exp(h(s,b,\theta))} \\ \quad \updownarrow \\ exp(h(s,a,\theta)) \doteq \theta^T \phi(s,a) \\ where \\ \theta \text{- policy weight vector} \\ \]