强化学习

课程：上海交大张伟楠老师《动手学强化学习》配套网课

第一讲 初探强化学习

一、两种机器学习类型

1.预测型
- 有监督学习：根据数据，预测所需输出。
- 无监督学习：生成数据实例。

2.决策型
- 强化学习：在动态环境中采取行动。
- 转变到新的状态
- 获得即时奖励
- 随着时间的推移，最大化累计奖励
- 行动引起环境改变，因此针对多步决策，需要进一步进行思考和规划，在动态环境中优化决策，使得累计奖励最大化。
- 强调序贯决策(sequential decision making)，决策往往会带来后果，决策者需要为未来负责，并需要在未来时间点进行进一步决策。

二、强化学习定义

1.定义：通过从交互中学习，来实现目标的计算方法。
- 观察
- 奖励
- 智能体
- 行动

2.三个方面
- 感知：在某种程度上感知环境的状态。
- 行动：采取行动，影响状态或达到目标。
- 目标：随着时间推移，最大化累积奖励。

三、强化学习的交互过程

1.每一时间步\(t\)智能体的行为
- 获得观察\(O_t\)
- 获得奖励\(R_t\)
- 执行行动\(A_t\)

2.环境
- 获得行动\(A_t\)
- 给出观察\(O_{t + 1}\)
- 给出奖励\(R_{t + 1}\)

3.在“环境”步骤，时间步\(t\)增加。

四、强化学习系统要素

1.历史：过去各个时间步，观测\(O_i\)、行动\(A_i\)、奖励\(R_i\)的序列。
- \(H_t = O_1, A_1, R_1, \cdots, O_{t - 1}, A_{t - 1}, R_{t - 1}, O_t, R_t\)
- 历史即一直到时间\(t\)为止，所有可观测变量。
- 根据历史决定未来发生的事件
- 智能体：选择行动\(A_t\)
- 环境：选择观察\(O_{t + 1}\)、奖励\(A_{t + 1}\)

2.状态：用于确定未来行动、观察和奖励事件的序列。
- 状态\(S_t\)是关于历史\(H_t\)的函数：\(S_t = f(H_t)\)

3.策略(policy)：智能体在特定时间的行为方式。
- 策略：状态\(\rightarrow\)行动的映射
- 确定型策略(deterministic policy)：\(a = \pi (x)\)
- 随机策略(stochastic policy)：\(\pi(a|s) = P(A_t =a|s_t = s)\)
- 基于状态\(s\)，策略\(a\)的选择服从条件概率分布\(\pi(a|s)\)。
- 状态集可能为离散或连续空间，相应地，条件分布可划分为离散型、连续型。

4.奖励(reward)
- 定义强化学习目标，一般为标量。
- 来自环境的即时奖励信号，能立即感知什么是“好”的。

5.价值函数(value function)
- 整体回报：整个交互过程中，各轮获得的奖励信号进行累加，形成智能体的整体回报。
- 价值：整体回报的期望。
- 状态价值：标量，定义从长期角度考虑，什么是“好”的。
- 价值函数：预测未来的累积奖励，用于评估在给定策略之下，状态的好坏。
- \(v_{\pi}(s) = \mathbb{E}_{\pi}[R_{t + 1} + \gamma R_{t + 2} + \gamma^{2}R_{t + 3} + \cdots | S_t = s]\)
- \(\gamma\)表示衰减因子

6.环境模型(model)
- 环境模型(environment model)：用于模拟环境行为。
- 作用一：预测下一个状态
- \(P_{ss'}^{a} = \mathbb{P}[S_{t + 1} = s'|S_t = s, A_t = a]\)
- 作用二：预测下一个即时奖励
- \(R_{s}^{a} = \mathbb{E}[R_{t + 1}|S_t = s, A_t = a]\)

【例1】迷宫行走
- 状态：智能体位置
- 行动：东、南、西、北。
- 状态转移
- 行动方向为墙：不动
- 奖励
- 每多走一步，直接给定\(-1\)的奖励，用以刺激智能体尽快走出迷宫。
- 状态价值：距离出口越远的状态，基于策略\(\pi\)的状态价值\(v_{\pi}(s)\)越低。

五、强化学习智能体分类

1.基于模型的强化学习
- 策略 和/或 价值函数
- 环境模型
- 举例：迷宫、围棋
- 特点：已知环境信息，可以专注地对策略进行思考。

2.模型无关的强化学习
- 策略 和/或 价值函数
- 没有环境模型
- 举例：Atari游戏通用策略
- 特点：真正意义的强化学习。

【例2】Atari游戏
- 游戏规则未知
- 从交互游戏中进行学习
- 通过操纵杆选择行动，查看分数（奖励）和像素画面。

3.基于价值
- 完全集中于价值函数的估计，没有显式策略，策略隐含在价值函数之中。
- 根据状态价值函数\(v(s)\)，以及动作价值函数\(Q(s, a)\)，进行策略\(\pi(s)\)的选择。

4.基于策略
- 专注于策略学习，没有价值函数。
- 直接学习\(\pi(s)\)，而状态价值函数\(v(s)\)，以及动作价值函数\(Q(s, a)\)是“潜移默化”得到的。

5.Actor-Critic
- 同时学习策略和价值函数。
- Actor即策略，Critic即价值函数，相辅相成。

六、强化学习中的数据

1.训练数据来源
- 强化学习的训练数据，来自于智能体与环境交互的过程。

2.强化学习数据特点
- 若智能体不采取某个动作，则该动作对应的数据永远无法被观测到。
- 智能体的策略不同，与环境交互产生的数据分布也不同。

3.占用度量(occupancy measure)
- 作用：衡量智能体在和动态环境进行交互的过程中，采样到一个具体的状态动作对(state-action pair)的概率分布。
- 性质：给定两个策略，以及这两个策略与同一个动态环境交互得到的两个占用度量，策略相同，当且仅当两个占用度量相同。
- 奖励建立于状态-动作对，故一个策略对应的价值，实质上就是一个占用度量下对应奖励的期望。
- 寻找最优策略，对应于寻找最优占用度量。

第二讲 多臂老虎机(MAB, Multi-Armed Bandit)问题

一、探索与利用

1.探索与利用的区别：基于目前策略，获取最优效益；还是尝试不同决策。
- 利用(exploitation)：执行能够获得已知收益的决策，不一定是全局最优。
- 探索(exploration)：尝试更多可能的决策，不一定是最优收益。

2.探索的形式化
- 已有策略集合：\(\epsilon_{t} = \{\pi_{t}^{i}|i = 1, 2, \cdots, n\}\)
- 探索后的策略集合：\(\epsilon_{t + 1} = \epsilon_{t} = \{\pi_{t}^{i}|i = 1, 2, \cdots, n\} \cup \{\pi_{e}^{j}|j = 1, \cdots, m\}\)
- 后者表示第\(t + 1\)时间步新得到的策略。

3.探索的作用：可能发现更好的策略。
- \(\exists V^*(\cdot | \pi_{t}^{i} \sim \epsilon_{t}) \le V^*(\cdot | \pi_{t + 1}^{i} \sim \epsilon_{t + 1}), \pi_{t + 1}^{i} \sim \{\pi_{e}^{i}|i = 1, 2, \cdots, m\}\)

【例1】
选择餐厅：选择常去餐厅、探索新餐厅。

二、策略探索的基本原则

1.朴素方法(Naive Exploration)
- \(\epsilon\)-贪心法：添加策略噪声

2.积极初始化(Optimistic Initialization)
- 对于各个动作，使用较为乐观的价值进行初始化，以使得所有动作都能被探索得更充分。

3.基于不确定性的度量(Uncertainty Measurement)
- 尝试具有不确定性的策略，可能带来更高收益

4.概率匹配(Probability Measurement)
- 基于概率，选择最佳策略

5.状态搜索(State Searching)
- 探索后续状态，可能带来更高的收益

三、多臂老虎机

1.定义
- 每个老虎机拉动一次拉杆，分别按照各自的概率，可能给出奖励，也可能无奖励，不同老虎机奖励概率不同，对于智能体是未知的。
- 动作集合\(a^{i} \in \mathscr{A}, i = 1, 2, \cdots, K\)
- \(K\)为老虎机个数，动作\(a^{i}\)表示拉动老虎机\(i\)一次。
- 收益函数分布：\(R(r | a^{i}) = \mathbb{P}(r|a^{i})\)

2.目标
- 最大化累计时间的收益：\(max \sum_{t = 1}^{T}r_t, r_t \sim R(\cdot | a)\)

3.关键问题
- 对于不确定的奖励函数，只能通过有限次观测，计算均值实现估计。

4.收益估计
- 动作价值函数：\(Q_{n}(a^{i}) = \frac{r_1 + \cdots + r_{n - 1}}{n - 1}\)
- 增量计算：\(Q_{n + 1}(a^{i}) = \frac{1}{n}\sum_{i = 1}^{n}r_i \newline = \frac{1}{n}(r_{n} + \frac{n - 1}{n - 1}\sum_{i = 1}^{n - 1}r_i) = \frac{1}{n}r_n + \frac{n - 1}{n}Q_n = Q_n + \frac{1}{n}(r_n - Q_n)\)
- 上述增量计算的空间复杂度为\(O(1)\)。

5.多臂老虎机算法

二、悔值函数

1.悔值函数
- 决策的期望收益：\(Q(a^{i}) = \mathbb{E}_{r \sim \mathbb{P}(r | a^i)}[r|a^i]\)
- 最优收益：\(Q^* = max_{a^i \in \mathscr{A}}Q(a^i)\)
- 悔值即实际决策与最优决策的收益之差：\(R(a^i) = Q^* - Q(a^i)\)
- 总计悔值(total regret)：\(\sigma_{R} = \mathbb{E}_{a \sim \pi}[\sum_{t = 1}^T R(a_t^i)]\)
- 等价性：\(min \sigma_{R} = max \sum_{t = 1}^T R(a_t^i)\)

2.探索与时间的关系
- 随时间推移，总计悔值需要逐渐减小，因此探索的次数最好能够随时间衰减。

3.悔值函数的特性