地表最强-强化学习笔记

作者: 音符纸飞机 | 来源:发表于2021-08-25 15:58 被阅读0次

地表最强-强化学习笔记
地表最强
【地表最强】
【地表最强】
最强地表
强化学习读书笔记 - 01 - 强化学习的问题
地表最强——LBJ
地表最强，嗯？
地表最强老爸
地表最强-伦敦

视频学习：
莫凡视频教程
 李宏毅2018强化学习视频教程
 马尔科夫决策过程
 https://github.com/wangshusen/DeepLearning
Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms
An Introduction to Deep Reinforcement Learning

术语

注：所有小写字母表示已观测到的值，大写字母表示未观测到的（随机变量）

state 当前的场景、状态
action 动作
agent 做动作的主体、可翻译成智能体
policy $\pi$ 状态s下，各种动作的概率密度函数
reward 奖励 $R_i$ 和 $S_i, A_i$ 有关
状态转移 state i → state i+1通常是随机的
条件概率密度函数

强化学习的随机性来源主要有两个

action是随机的 $P[A=a|S=s] = \pi(a|s)$
状态转移（新状态）是随机的 $P[S'=s'|S=s, A=a]=p(s'|s,a)$

强化学习状态轨迹：
$[(state, action, reward)]$ $(s_1,a_1,r_1), ..., (s_T,a_T,r_T)$

Return 回报，未来的累计奖励
$U_t = R_t+R_{t+1}+R_{t+2} +...$
Discounted Return折扣回报， $\gamma$ 是折扣率
$U_t = R_t+ \gamma R_{t+1}+ \gamma^2 R_{t+2}+...$
显然在给定的 $s_t$ 下 $U_t$ 依赖于 $A_t,A_{t+1},...S_{t+1},S_{t+2},...$
Action-Value Function 动作价值函数 $Q(s,a)$

U_t的条件期望
含义：如果用policy函数

\pi

，在s_t状态下做动作

a_t

的好坏，是否明智

求期望就是对

A_{t+1},A_{t+2},...S_{t+1},S_{t+2},...

求积分

最优动作价值函数 $Q^{*}(s_t,a_t)=\max_{\pi}Q_{\pi}(s_t,a_t)$
含义：在s_t状态下做动作 $a_t$ 好不好，就像一个先知，能告诉你每个action的平均回报

State-Value Function状态价值函数 $V(s)$
$V_{\pi}(s_t)=\mathbb{E}_{A}[Q_{\pi}(s_t,A)]$
对A求积分，含义：当前局势好不好

强化学习的目标是学习 $\pi$ 或者 $Q^*$

强化学习的几种思路

Value-based learning
用神经网络（DQN）近似 $Q^*$ ，参数学习利用了temporal different (TD) 算法
Policy-based learning
用神经网络（DQN）近似 $\pi$ ，参数学习利用了policy gradient梯度上升
Actor-critic method
以上两种的结合

Value-based learning

如果我们知道 $Q^*(s,a)$ ，就能当前最好的action
$a^* = \argmax_{a}Q^*(s,a)$

本质：用神经网络 $Q(s,a;w)$ 近似 $Q^*(s,a)$

神经网络的输入是s，输出是很多数值，表示对所有可能动作的打分，根据观测到的奖励来更新参数

TD算法
如何训练DQN？实际场景中，完成任务需要很多步的action，如果全部action都结束了，再来更新模型，效果一定很差，那么如何走一步更新一下呢？
TD target : 实际已经得到的奖励和模型预测未来的奖励之和。
越接近结束，TD target越准
用TD target(y)和全部都是模型预测的奖励Q(w)计算loss
$L=\frac{1}{2}(Q(w)-y)^2$
其中 $Q(w)-y$ 被称为TD Error，换个角度，去掉相同的部分，其实就是实际奖励和预测奖励的误差。
最后用梯度下降更新模型参数，不需要打完游戏再来更新参数。

$Q(s_t,a_t;w) \approx r_t+\gamma \cdot Q(s_{t+1},a_{t+1};w)$
$t$ 时刻未来奖励总和的期望约等于 $t$ 时刻的奖励加上 $t+1$ 时刻未来奖励总和的期望

Policy-based learning

本质：用神经网络 $\pi(a|s;\theta)$ 近似策略函数 $\pi(a|s)$

比如超级玛丽，输入是当前状态，输出是每个操作的概率分布

$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(s_t;\theta) = \sum_{a}\pi(a|s_t;\theta)\cdot Q_{\pi}(s_t,a)$

给定状态 $s_t$ ，策略网络越好， $V$ 的值越大
目标函数 $J(\theta)=\mathbb{E}_S[V(S;\theta)]$ 越大越好，利用policy gradient ascent更新参数

Policy Gradient Ascent

观测到状态s，计算策略梯度 $\frac{\partial V(s;\theta))}{\partial \theta}$ ，更新模型参数
$\theta \leftarrow \theta+\beta \cdot \frac{\partial V(s;\theta))}{\partial \theta}$

如何求策略梯度？

整个算法过程：

Actor-Critic Methods

$V_{\pi}(s)=\sum_{a}\pi(a|s)\cdot Q_{\pi}(s,a)\approx \sum_{a}\pi(a|s;\theta)\cdot q_{\pi}(s,a;w)$
Actor是策略网络，可以看成是运动员。用神经网络 $\pi(a|s;\theta)$ 近似策略函数 $\pi(a|s)$
Critic是价值网络，可以看成裁判员，给运动员打分。用神经网络 $q(s,a;w)$ 近似价值函数 $Q_{\pi}(s,a)$

策略网络

价值网络

训练过程

观测当前状态 $s_t$
根据策略网络得到当前action $a_t$
实施 $a_t$ ，然后观察 $s_{t+1}$ 和 $r_{t}$
用TD算法更新价值网络参数 $w$
用策略梯度更新策略网络参数 $\theta$

总结：

AlphaGo

主要设计思路

棋谱大小19x19，一共361个点，所以action的数量一共是361个。可以用19x19x2的矩阵代表黑白棋子的状态state

策略网络

状态矩阵：1表示有棋子，0表示没有，黑白棋子分别记录最近8个状态，所以一共是16，还有一个表示当前是黑棋下还是白棋下（全0或者全1）

策略网络

训练三步走

Behavior cloning 通过对人类棋谱有监督的学习（16w局）是一个分类任务，初步学习策略网络（这一步可有可无）
- 网络只会对见过的state表现比较好，所以想要战胜它，只需要做一些出乎寻常的操作就行了

强化学习进一步学习这个网络，自我博弈（利用策略梯度）
- 一个模型参数需要更新的策略网络作为player，上一个策略网络作为opponent
- 进行一局比赛得到 $s_1,a_1,s_2,a_2, ..., s_T, a_T$
- 奖励 $u_1=u_2=...=u_T$ , 赢了全为1，否则全为-1
- 计算策略梯度 $g_\theta = \sum_{t=1}^{T} \frac{\partial \log \pi (a_t|s_t, \theta)}{\partial \theta } \cdot u_t$
- 更新策略网络 $\theta \leftarrow \theta+\beta \cdot g_\theta$
利用策略网络训练一个价值网络
- 用神经网络 $v(s;w)$ 近似 $V_\pi(s)$
  两个网络共享卷积层
- 进行一场比赛
- 奖励 $u_1=u_2=...=u_T$ , 赢了全为1，否则全为-1
- 计算Loss: $L = \sum_{t=1}^{T} \frac{1}{2} [v(s_t;w)-u_t]^2$
- 更新模型参数

执行的时候用的是Monto Carlo Tree Search (MCTS),利用策略网络和价值网络指导搜索（人类高手在下棋的时候会往前看好几步）
- 搜索的主要思想
  1. 根据策略网络，在分数高的action中随机选择一个
  2. 自我博弈，根据胜负和价值函数给该动作打分
  3. 选择打分最高的那个action

1.Selection	2.Expansion	3.Evaluation	4.Backup
$score(a)=Q(a) + \eta \cdot \frac {\pi (a\|s_t; \theta)}{1+N(a)}$		$V(s_{t+1}) = \frac{1}{2}(v(s_{t+1};w)+r_(T))$	$Q(a_t)=mean(Records)$ $a_t=\argmax_{a}N(a)$
其中 $Q(a)$ 是动作价值，初始值都为0，N(a)表示动作 $a$ 已经被选择的次数	$s_{t+1}$ 是根据策略函数随机采样模拟动作之后的状态后面就是自我博弈，根据最终的胜负计算奖励 $r_{T}$	综合考虑奖励和价值函数，对状态 $s_{t+1}$ 打分Record，分数越高胜算越大	计算动作的Q值，循环很多次之后选择被选中次数最多的动作

蒙特卡洛

一种数值算法，靠随机样本对目标做近似
待补充

TD Learning 之 Sarsa算法

用来学习动作价值函数 $Q_\pi (s,a)$
TD target: $y_t=r_t+\gamma \cdot Q_\pi (s_{t+1},a_{t+1})$
Sarsa方法来更新价值网络（critic）

TD Leaning 之 Q-Learning

用来学习 $Q^*(s,a)$
TD target: $y_t=r_t+\gamma \max_{a} Q^*(s_{t+1},a)$

Multi-Step TD Target

多个action之后再更新参数，相当于有累计多次奖励
m-step TD target for Sarsa
$y_t=\sum_{i=0}^{m-1} \gamma ^i \cdot r_{t+i}+\gamma ^m \cdot Q_\pi (s_{t+m},a_{t+m})$

Experience Replay

经验回放

定义：

A transition： $(s_t,a_t,r_t,s_{t+1}), \delta_t$
Experience: 所有的transition

之前训练方式的缺点：

每个 $r_t$ 只是用了一次，相当于对经验的浪费
$s_t$ 和 $s_{t+1}$ 之间的相关性太强，理论上打乱顺序更好

replay buffer: 最近n个transition，训练的时候每个batch从replay buffer中随机选k个transition 做随机梯度下降

一种对经验回放的改进Prioritized Experience Replay:用非均匀抽样代替均匀抽样

用TD error $\delta_t$ 判断transition的重要性
用不同的学习率 $(np_t)^{-\beta}$ 抵消不同样本抽样频率的不用，其中 $p_t$ 是抽样概率， $\beta \in [0,1]$ ，实战中先比较小，然后慢慢变大。

Target Network 和 Double DQN

TD target: $y_t=r_t+\gamma \cdot \max_aQ(s_{t+1},a;w)$
TD error : $\delta_t = Q(s_t,a_t;w)-y_t$
SGD: $w \leftarrow w - \alpha \cdot \delta_t \cdot \frac{\partial Q(s_t,a_t;w)}{\partial w} = w - \alpha \cdot ( Q(s_t,a_t;w) - y_t) \cdot \frac{\partial Q(s_t,a_t;w)}{\partial w}$
我们发现在t时刻更新参数的时候，计算梯度的时候用到了 $y_t$ ，而 $y_t$ 又包含了对t+1时刻的预测，就出现了bootstapping的问题，自己把自己举起来了

DQN的高估问题

原因一：计算TD target的时候会最大化价值函数
原因二：上面提到的bootstrapping

结论：DQN对价值的高估是非均匀的，非常有害

解决方案：

用target network来计算TD targets
DQN： $Q(s,a;w)$ ，用来控制agent
target network: $Q(s,a,w^-)$ 用来计算TD targets $y_t=r_t+\gamma \cdot \max_aQ(s_{t+1},a;w^-)$
结构一样，参数不一样
用double DQN 缓解高估的问题

selection: $a^* = \argmax_{a}Q^*(s_{t+1},a;w)$
evaluation: $y_t=r_t+\gamma \cdot Q(s_{t+1},a^*;w^-)$

compute TD target	selection	evaluation
naive	DQN	DQN
using target network	Target Network	Target Network
Double DQN	DQN	Target Network

Dueling Network

Optimal advantage function
$A^*(s,a) = Q^*(s,a) - V^*(s)$
以最优状态函数为基准，最优动作价值函数的优势
Dueling Network
$Q^*(s,a) = V^*(s) + A^*(s,a) - \max_{a}A^*(s,a)$

Dueling Network

实际实验中发现把max换成mean效果更好
$Q^*(s,a;w) = V(s;w^V) + A(s,a;w^A) - mean_{a}A(s,a;w^A)$

数学原理待补充

Multi-Agent 强化学习

四种设定

合作关系 共同的目标，奖励一致，如多个工业机器人协同装配汽车
竞争关系 一方的收益是另外一方的损失，如零和博弈，拳击比赛
合作竞争混合 足球比赛，星际争霸
利己主义 股票自动交易系统，无人车

假设有n个agent， $S$ 是状态， $A^i$ 第i个agent的动作，
那么状态转移方程为（条件概率密度函数）： $p(s'|s,a^1,...,a^n)=\mathbb{P}(S'=s'|S=s,A^1=a1,...,A^n=a^n)$

假设 $R^i$ 表示第i个agent的奖励（Reward），那么
合作关系 $R^1=R^2=···=R^n$
竞争关系 $R^1 \propto -R_2$

假设 $R_{t}^{i}$ 表示第i个agent在t时刻的奖励（reward）
那么回报（return） $U_t^i = R_{t}^i + R_{t+1}^i + R_{t+2}^i + ···$
折扣回报 $U_t^i = R_{t}^i + \gamma R_{t+1}^i + \gamma ^2 R_{t+2}^i + ···$

每个agent有自己的策略网络 $\pi(a^i|s;\theta^i)$ ，不同agent的参数 $\theta^i$ 可以相同（比如自动驾驶）也可以不相同（比如机器人足球队）

状态价值函数 $V^i(s_t;\theta^1,···,\theta^n)=\mathbb{E}[U_t^i|S_t=s_t]$ ，依赖于所有策略网络

部分可观测

multi-agent通常假设agent只能看到状态 $s$ 的一部分 $o^i$ ， $o^i \neq s$

纳什均衡 `Nash Equilibrium`

纳什均衡用来判断多个agent的策略网络收敛的标准。
当其他所有agent的策略保持不变，单独优化某一个agent的策略不会得到更好的回报

Multi-Agent 学习的难点

如果直接把single-agent学习的方法直接用到multi-agent上的话，收敛会很困难
原因是一个agent的策略更新会导致其他所有agent策略网络的目标函数 $J$ 发生变化
所以在训练一个agent策略网络的时候最好能拿到其他agent的信息 (通信)

中心化`centralized`与去中心化`decentralized`通信方式

Fully decentralized
agent之间完全没用通信，其实就是上文说的
每个agent都是一个actor-critic，一个策略网络和一个价值网络
Fully centralized
所有agent把所有信息（observation, actions, rewards）发送给中央控制器central controller，由中央控制器来决定每个agent的action
agent没有策略网络和价值网络，中央控制器学习n个策略网络、n个价值网络
主要的问题是执行速度慢，不能实时做决策

Centralized training and decentralized execution
- 中央控制器帮助训练策略网络，运行的时候直接由agent决定action
- 每个agent有自己的策略网络（actor） $\pi(a^i|o^i;\theta^i)$ ，中央控制器有n个价值网络（critic） $q(\textbf {o} | \textbf {a} ;w^i)$