policy gradient

basic

Deriving Policy Gradients and Implementing REINFORCE 这篇博客详细推导了 policy gradients 的过程，虽然公式很多，但其实还算简单。

最终的结论就是，从公式(1)推导为公式(2):

$$J(\theta)=\mathbb{E}[\sum_{t=0}^{T-1}r_{t+1}|\pi_{\theta}]=\sum_{t=1}^{T-1}P(s_t, a_t|\tau)r_{t+1}\quad(1)$$

$$\nabla_{\theta}J(\theta)=\sum_{t=0}^{T-1}\nabla_{\theta}log\pi_{\theta}(a_t|s_t)(\sum_{t’=t+1}^T\gamma^{t’-t-1}\gamma_{t’})\quad(2)$$

其中 $Gt=\sum_{t’=t+1}^T\gamma^{t’-t-1}\gamma_{t’}$

公式(2)可简化为:

$$\nabla_{\theta}J(\theta)=\sum_{t=0}^{T-1}\nabla_{\theta}log\pi_{\theta}(a_t|s_t)G_t$$

之后就是针对 policy gradient 的各种改进。接下来的公式参数是根据李宏毅老师课程来的。所以符号与上面的有差异。

add baseline

$$\nabla{\overline R}{\theta}=\dfrac{1}{N}\sum{n=1}^N\sum_{t=1}^{T_n}(R(\tau^n)-b)\nabla logp_{\theta}(a_t^n|s_t^n)$$

assign suitable credit

$$\nabla{\overline R}{\theta}=\dfrac{1}{N}\sum{n=1}^N\sum_{t=1}^{T_n}(\sum_{t’=t}^{T_n}r_{t’}^n-b)\nabla logp_{\theta}(a_t^n|s_t^n)$$

add discount factor

advantage function

action $a_t$ 的好是相对的，而不是绝对的。它可以是 state-dependent.

on-policy and off-policy

importance sampling

issue of importance sampling:

采用 importance sampling，会导致sample 得到的action的分布方差发生变化。因此要保证action的分布尽可能与

on-policy to off-policy

PPO(proximal policy optimization)

add constraint:

$\theta, \theta’$ 并不是distribution，而是参数。那么这里的 $kl(\theta, \theta’)$ 到底是什么？

这里的kl divergence 实际上是行为上的差距，也就是 action 分布的距离。那这个意思就是我们还是得用 $\theta$ 去求出 action 的 distribution，但是我们不用去sample出样本了。可以继续需要用 $\theta’$ sample出来的样本，但是需要给reward乘以系数 $\dfrac{p_{\theta}(a_t|s_t)}{p_{\theta’}(a_t|s_t)}$.

PPO2

因为 $kl(\theta, \theta’)$ 的计算还是蛮复杂的，所以用ppo2来代替。方法也是很直接，用clip的方式代替原来的正则项。

总结一下ppo：

1. 首先它是off-policy的，为什么将on-policy转换成off-policy呢，因为on-policy速度太慢了。在policy iteration的时候先sample尽可能多的(state, action)pairs，然后计算对应的reward，再基于policy gradient来更新policy的参数 $\theta$.这是一次迭代。再然后基于updated policy生成新的(state, action) pairs或者新的example吧，依次迭代。。。这个过程中，得到action的分布，然后sample得到尽可能多的actions，这一步是非常耗时的，而且每次迭代都需要重新生成样本。

2. off-policy改进的就是搞一个近似于当前policy $\theta$ 的 $\theta’$. 用这个 $\theta’$ 去采样 $(state, action)$ 样本，这个 $\theta’$ 并不是随着 policy $\theta$ 的更新而更新的，所以它sample出来的样本可以用很久。

3. 但是policy $\theta$ 更新之后，其对应的 action 的分布也是变换的，这也是我们想要的。所以怎么减小 $\theta’$ 和 $\theta$ 对应的action分布的差异，就有了ppo公式的第一项，也就是 importance sampling.

4. 但是importance sampling得到的action的分布存在偏差（方差不一致)，所以需要尽可能保证 $\theta, \theta’$ 采样得到的action分布尽可能接近。于是有了ppo,ppo2的方法。

Critic

state-value function

$V_{\pi}(s)$ 表示的是当到达某个状态 s 之后，如果接下来一直按着策略 $\pi$ 来行动，能够获得的期望收益.

action value function

$Q_{\pi}(s,a)$ 表示的是当达到某个状态 s 之后，如果强制采取行动 a ，接下来再按照策略 $\pi$ 来行动，能获得的期望收益。

显然地，状态价值函数和行动价值函数之间有关系:

$$V_{\pi}(s)=\sum_a\pi(a|s)Q_{\pi}(s,a)$$

MC v.s. TD

sample同样的结果，采用 MC 和 TD最终计算的结果也是不一样的。

MC考虑的是，当前state $s_a$ 对未来的 state $s_b$ 可能也是有影响的. 所以MC实际上是要计算到整个游戏（episode）结束。

Planning by Dynamic Programming

Introduction

what is dynamic programming?

动态规划是一种方法/思想，将复杂问题分解成子问题，并解决子问题。

DP 是具有以下两种特质的问题常用的解决方法：

• 具有可优化的子结构

  • 优化问题可以分解成子问题

• 重叠子问题

  • 子问题重复出现很多次

  • 子问题的solution可以被缓存和reuse

马尔可夫决策过程就具有这两种特质：

• Bellman 公式给出了迭代分解的方式

• value funvtion 用来存储和再利用子solutions

Bellman 公式的含义分为两部分，第一部分是目前的一步是最优的行为，第二部分是余下来的其他步骤也是最优的行为。

动态规划需要的输入：

• MDP $<S,A,P,R,\gamma>$ and policy $\pi$

• or MDP $<S,P^{\pi},R^{\pi},\gamma>$

输出： value function $v_{\pi}$

DP 适用的一些场景。比较熟悉的 sequence alignment, shortest path algorithms, viterbi algorithm.

Policy evaluation

Iterative policy evaluation

$v_{k+1}(s)=\sum_{a\in A}\pi(a|s)(R_s^a+\gamma\sum_{s’\in S}P^a_{ss’}v_k(s’))$

example

• 方块中任意一个状态到另一个状态的 reward 是 -1.

• 每迭代一步有 north, east, south, weat 4种选择。

• k=0. 初始状态下，所有的方块累计的 reward 都是 0. 所以在这个状态下是 random policy.

• k=1, 迭代一步之后，除了 terminal squares, 其他的 reward 都是 1. 如果采用 greedy policy，就能确定部分路径了。

• k=2, 在 random policy 策略下，我们来看下 1.75 怎么得到的：

$$1+(1+1+1)/4=1.75$$

• k=3, 在 random policy 策略下，我们来看 2.4, 2.9 怎么得到的：

$$(1+2.7+3+3)/4=2.425$$

$$(2.7+3+3+3)/4=2.925$$

这里的 k 是迭代的次数，并不是时间.

policy iteration

迭代方式：

• policy evaluation

• policy improvement: greedy

policy improvement

$$v_{\pi}(s)=E[R_{t+1}+\gamma R_{t+2}+….|S_t=s]$$

improve the policy by acting greedily.

当前最优 policy:

$${\pi}^{‘}(s)=greedy(v_{\pi})=argmax_{a\in A}q_{\pi}(s,a)$$

$q_{\pi}(s,a)$ 是 action-value function.

这页ppt中最后的公式实际证明了：采用 greedy policy 至少能保证 $v_{\pi^{‘}}\ge v_{\pi}(s)$.

modified policy iteration

value iteration

优化的定理：

任何优化策略都可以分解成两部分：

• 最优化的 action A

• 后继状态 S’ 下的最优化策略 policy

example:

summary of DP algorithms

In-Place Dynamic Programming

Prioritised Sweeping

Real-Time Dynamic Programming

Extensions to dynamic programming

Markov Process

Introduction to MDPs

马尔可夫决策过程：

• 环境完全可观测

• 当前状态能完整的描述这个过程

• 绝大多数 RL 问题都可以形式化为 MDPs:

  • 优化控制问题

  • 部分可观测问题可转化为 MDPs

  • Bandits（老虎机问题）

multi-armed bandits problems

Markov property

一旦当前状态确定后，所有的历史信息都可以扔掉了。这个状态足够去预测 future.

state transition matrix

状态转移矩阵定义了所有的从某一个状态到另一个状态的概率。所以每一行相加为 1.

Markov chain

马尔可夫链可以看做是 一个 tuple(S, P)

• S 是有穷的状态的集合

• P 是状态转移矩阵

$$P_{ss’}=P[S_{t+1}=s’|S_t=s]$$

example:

简单的马尔可夫链，没有 reward, action 等。

Markov reward process

在 Markov chain 基础上增加了 reward function.

return

折扣因子 $\gamma \in [0,1]$

越接近0， 意味着越短视

越接近1, 意味着有远见

Why discount

• 数值计算方便

• 避免无限循环

• 对未来的不确定性

• 如果reward是经济的，即刻的reward能获得更多的利益相比之后的reward

• 动物/人更倾向于即刻的奖励

• 有时候也会使用 undiscounted 马尔可夫奖励过程

value function

因为 future 有很多中不确定性，所以需要采样. sample 得到的 $G_t$ 的期望，也就是 value

$$v(s)=E[G_t|S_t=s]$$

上图中 $v_1$ 应该是 $g_1$.

$$G_1=R_2+\gamma R_3+…+\gamma^{T-2}R_T$$

也就是计算从 t 时刻开始到结束，整个过程可能的奖励值。因为未来可能有很多中情况，所以需要 sample. 印象中，好像 alpha go 就是用的蒙特卡洛模拟。

Bellman Equation for MRPs

动态规划。。

这里容易理解错的一点就是： $R_s$ 实际上就是 $R_{t+1}$, s 表示 v(s) 中的当前状态。

$P_{ss’}$ 是状态转移的概率， 从 s 到 后继状态 s’ 的概率。

所以：

$$\gamma v(S_{t+1}|S_t=s) = \gamma\sum_{s’\in S} P_{ss’}v(s’)$$

转换成矩阵形式：

事实上: 系数矩阵 P 就是 状态转移矩阵，有 n 中状态，那就是 $n\times n$ matrix.

solving bellman problems

直接计算是 $O(n^3)$, 因为 n 个状态，P 的计算就是 $O(n^2)$

对于很复杂的 MRPs，可以采用：

• dynamic programming

• monte-carlo evalution

• temporal-difference learning

Markov Decision Process

想对于 Markov reward process 增加了 decision.

$P_{ss’}^a$ 是状态转移矩阵，但是这里的状态之间的转移概率不再是确定好了的。而是取决于 当前状态，以及当前状态下的 action.

$$P_{ss’}^a=P[S_{t+1=s’}|S_t=s, A_t=a]$$

因此 R reward function：

$$R_s^a=E[R_{t+1}|S_t=s,A_t=a]$$

可以发现，与之前的区别是，state 到 state 之间是通过 action 决定的。比如 第一个 state 下，可以是 study or facebook.

policy

这个决策就是想对于 Markov reward process 多出来的一部分，你需要自己去做决策。只不过在每一个状态下，其决策也是一个 distribution

$$\pi(a|s)=P[A_t=a|S_t=s]$$

事实上 Markov decision process 也可以转换成 Markov reward process, 从状态 s 到 s’ 的概率：

$$P_{s,s’}^{\pi}=\sum_{a\in A}\pi(a|s)P_{ss’}^a$$

value function

value 是当前状态 s 下的 reward $G_t$ 的期望。

Bellman expectation Equation

$v_{\pi}$ 基于 $q_{\pi}$ 的表示

state-value $v_{\pi}$ 是 action-value $q_{\pi}$ 基于 action 的期望。

$$v_{\pi}(s)=\sum_{a\in A}\pi(a|s)q_{\pi}(s, a)\quad \text{(1)}$$

$q_{\pi}$ 基于 $v_{\pi}$ 的表示

action-value：

$$q_{\pi}(s,a)=R_s^a+\gamma\sum_{s’\in S}P_{ss’}^av_{\pi}(s’)\quad \text{(2)}$$

从状态 s 到 s’， 基于 statetransition probability matrix $P_{ss’}^a$.

$v_{\pi}$ 基于 $v_{\pi}$ 的表示

将 （2）带入（1）可得：

$$v_{\pi}(s)=\sum_{a\in A}\pi(a|s)(R_s^a+\gamma\sum_{s’\in S}P_{ss’}^av_{\pi}(s’))\quad \text{(3)}$$

这里得到的是 state-value 的表达式。第二个类和符号是 从状态 s 到 s’ 所有可能的后继状态 s’。第一个类和符号是 状态 s 下所有可能的 action.

这里的类和都是表示期望。

$q_{\pi}$ 基于 $q_{\pi}$ 的表示

将 （1） 带入 （2）可得：

$$q_{\pi}(s,a) = R_s^a+\gamma\sum_{s’\in S}P_{ss’}^a\sum_{a\in A}\pi(a’|s’)q_{\pi}(s’,a’)$$

这里得到的是 action-value 的表达式。第一个类和符号是在 action a 下，所有可能的后继状态 s’ 的类和。i第二个类和符号是 后继状态 s’ 下所有的 action 的类和。

example：

Matrix form

类似于前面 Markov reward process 的表示，但是这里的状态转移矩阵变成了 $P^{\pi}$, reward 变成了 $R^{\pi}$.

个人理解： Markov decision process 与 reward process 的区别在于原本在一个 state s 到下一个 state s’ 的概率是给定了的。但是在 decision process，并不存在这个概率，而是取决于 action，而在当前 state s 下，每一个 action 的概率取决于 policy $\pi$.

optimal value function

optimal policy

Solving the Bellman Optimality Equation

最优 policy 就是找到 $v_{* }(s)$ 和 $q_{* }(s,a)$

推导过程与前面类似，通过 bellman optimally equation 得到：

$$v_*(s)=max_{a}q_*(s,a)$$

$$q_*(s,a)=R_s^a+\gamma\sum_{s’\in S}P_{ss’}^av_*(s’)$$

$$v_*(s)={max}{a}(R_s^a+\gamma\sum{s’\in S}P_{ss’}^av_*(s’))$$

$$q_*(s,a)=R_s^a+\gamma\sum_{s’\in S}P_{ss’}^aq_*(s’,a’)$$

state-value function optimal

action-value function optimal

Extension to MDP

About reinforcement learning

强化学习的特性：

不同于有监督学习，没有 supervisor, 只有一个 reward signal.

The reinforcement learning problem

reward

强化学习就是基于 奖励假设(reward hypothesis).

决策的选择是为了获得更大的 future reward.

environments

state

history and state

state 是 history 的函数：

$$S_t = f(H_t)$$

environment state

环境状态对于 agent 可以是可见的，也可以是不可见的。即使是可见的，也不一定是有用的信息。

Agent state

代理状态就是 agent 的中间表示。

information state 又称 Markov state.

看做是马尔可夫链，当前状态包含了过去所有的信息。那么之前的 history 就可以扔掉了。

Markov decision process

马尔可夫决策过程条件：环境 state 与 agent state 一样

Agent state = environment state = information state

partially observable environments(POMDP)

agent 并不能直接观察环境：

• 机器人具有摄像头的视觉信息，但不知道自己的绝对位置

• trading agent 只能观察到当前价格

• 扑克牌选手只能看到公开的卡牌

agent state $\ne$ environment state

agent 必须重新构建自己的状态表示 $S_t^a$:

比如循环神经网络就是 POMDP

$$S_t^a=tanh(s_{t-1}^aW_s+O_tW_o)$$

Inside An RL Agent

在一个 agent 内部具体有什么呢?我们怎么去定义一个 agent:

• policy: agent’s behaviour function

• value function: how good is each state and/or action

• model: agent’s representation of the environment

policy

策略 policy： 就是将 state 映射到 action.

value function

如何设计 value function 来计算 future reward 感觉是个难度呀～

model

模型：用来预测环境如何变化，也就是模拟环境吧。比如 RNN 模型，就是用神经网络模拟序列变化。

Problems with Reinforcement Learning

Learning and planning

学习和规划的区别

• environment 是否 known

• agent 与 environment 是否有 interaction

Exploration and Exploitation

探索与开发：之前在三星听在线学习的讲座时，通过 多臂老虎机 和 在线广告 讨论过这个问题

• Exploration（探索） finds more information about the environment

• Exploitation（开发） exploits known information to maximise reward

• It is usually important to explore as well as exploit

这是一个需要权衡或博弈的问题。

prediction and control