地表最强-强化学习笔记

视频学习：
莫凡视频教程
 李宏毅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打分。就像一个先知，能告诉你每个action的平均回报

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

强化学习的目标是学习 $\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)$

Policy Gradient with Baseline (Reinforce)

在策略梯度中加入baseline，降低方差，使得收敛更快。baseline可以是任何东西，且与 $A$ 无关

如果b选的比较好，和

Q_\pi

很近似，那么会减小方差，实际计算中会用蒙特卡洛对期望求近似

用 $V_\pi$ 当做b

细节待补充

A2C Advantage Actor-Critic

本质上就是在actor-critic的基础上加上了baseline

复习actor-critic，注意这里用的状态价值网络v作为critic，与之前的q不一样

A2C的训练过程

数学推导待补充

A2C vs. Reinforce

连续控制

Deterministic policy gradient (DPG)

确定策略梯度

Stochastic policy network

最后编辑于：2022.08.14 20:43:48

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 220,548评论 6赞 513
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 94,069评论 3赞 396
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 166,985评论 0赞 357
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 59,305评论 1赞 295
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 68,324评论 6赞 397
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 52,030评论 1赞 308
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,639评论 3赞 420
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 39,552评论 0赞 276
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 46,081评论 1赞 319
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 38,194评论 3赞 340
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 40,327评论 1赞 352
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 36,004评论 5赞 347
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,688评论 3赞 332
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 32,188评论 0赞 23
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 33,307评论 1赞 272
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 48,667评论 3赞 375
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 45,337评论 2赞 358

地表最强-强化学习笔记

术语

Policy Gradient Ascent

主要设计思路

策略网络

四种设定

部分可观测

纳什均衡 Nash Equilibrium

Multi-Agent 学习的难点

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

A2C的训练过程

Deterministic policy gradient (DPG)

Stochastic policy network

推荐阅读更多精彩内容

纳什均衡 `Nash Equilibrium`

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