UCL-DRL-04-policy gradient and Actor Critic Methods

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.

  1. 但是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)结束。

UCL-DRL-03-planning by DP

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

UCL-DRL-02-MDP

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

UCL-DRL-01-introduction

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