强化学习从入门到放弃

杂谈

我们不一样？

• no supervisor , only reward

• feedback is delayed. 当前行为产生的实际价值可能要很久才能知道

reward hypothesis

All goals can be described by the maximisation of expected cumulative reward

History and State

• 历史就是一系列的观察，反馈，动作，\(H_t = O_1,R_1,A_1,\dots ,O_t,R_t,A_t\)

• 状态就是决定将来发生事情的信息，\(S_t = f(H_t)\)

• information state :包含历史中所有有用的信息

  • Markov:\(P[S_{t+1} | S_t ] = P[S_{t+1} | S_1, ..., S_t ]\)

    • \(H_{1:t}\to S_t\to H_{t+1:∞}\)

observability and state

直接观察env,获得环境状态MDP

观察受限，部分状态POMDP

RL AGENT major components

• Policy

• Value Function

• Model

Policy

a map from state to action

• deterministic: \(a =\pi(s)\)
• stochastic:\(\pi(a|s) = P[A_t=a|S_t=a]\)

value function

a prediction of future reward

\(v_{\pi}(s) = E_{\pi}[R_{t+1} + γR_{t+2 }+ γ^2R_{t+3} + ... | S_t = s]\)

model

model predicts what env will do next.

• \(P_{SS'}^a=P[S_{t+1}=s'|S_t=s,A_t=a]\)

• \(R_S^a = E[R_{t+1}|S_t=s,A_t=a]\)

Categorizing RL agents

基于什么？

• value based: value function

• policy based: Policy

• actor critic: both

是否需要model

• Model Free
  • Policy and/or value function
• Model based
  • 相比model free多建一个model

两个方面:

• 不了解Model, RL
• 了解model,planning

Exploration and Exploitation

探索，去探索未知，降低不确定性。期望未知给我们带来更好的效果

利用，安于现状，现在最好的就是最好的

Prediction and Control

预测，给定policy,估计未来

控制，找到最好的policy

MDP

MP

A state \(S_t\) is Markov if and only if \(P [S_{t+1} | S_t ] = P [S_{t+1} | S_1, ..., S_t ]\)

A Markov Process (or Markov Chain) is a tuple <S,P>

MRP

MRP 是带reward的MP

A Markov Reward Process is a tuple \(<S,P, R, γ>\)

Return

\(G_t = R_{t+1}+\gamma R_{t+2}+\dots=\sum_{k=0}^{\infty} \gamma^kR_{t+k+1}\)

reward是状态转移之后才能判断的，延迟一个时间步

value function

\(v(s_t) = E[G_t|S_t]\)

Bellman Equation

\(v(s) = E[G_t|S_t=s]=E[R_{t+1}+\gamma v(s_{t+1})|S_{t=s}]\)

矩阵格式\(v = R + γPv\)

MDP

Policy:

\(π(a|s) = P [A_t = a | S_t = s]\) 时间无关

MDP>MRP

\(P^π_{s,s'} = \sum_{a∈A} π(a|s)P^a_{ss'}\)

\(R^π_{s} = \sum_{a∈A} π(a|s)R^a_{s}\)

value function,action-value function

• \(v_π(s) = E_π [G_t | S_t = s]\)

• \(q_π(s, a) = E_π [G_t | S_t = s, A_t = a]\)

Bellman Expectation equation

• \(v_π(s) = E_π [R_{t+1} + γv_π(S_{t+1}) | S_t = s]\)

• \(q_π(s, a) = E_π [R_{t+1} + γq_π(S_{t+1}, A_{t+1}) | S_t = s, A_t = a]\)

• \(v_π(s) = \sum_{a∈A} π(a|s)q_π(s, a)\)

• \(q_π(s, a) = R^a_s + γ \sum_{ s'∈S} P^a_{ss'}v_π(s')\)

• \(v_π(s) = \sum_{a∈A} π(a|s) R^a_s + γ \sum_{ s'∈S} P ^a_{ ss'}v_π(s' )\)

• \(q_π(s, a) = R^a_s + γ \sum_ {s'∈S} P^a_{ss'} \sum_{a'∈A}π(a'|s')q_π(s' ,a' )\)

  

矩阵格式

\(v_π = R_π + γP_π v_π\)

\(v_π = (I ? γP_π )^{ ?1} R_π\)

Optimal Value Function

\(v_?(s) = \underset{π}{max}\, v_π(s)\)

\(q_?(s, a) = \underset{\pi}max\, q_π(s, a)\)

Optimal policy

\(π≥π'\) if $ v_π(s) ≥ v_{π‘}(s), ?s$

Theorem:

每个MDP存在最优策略

最优策略\(v_{π?} (s) = v_?(s)\),\(q_{π?} (s, a) = q_?(s, a)\)

if we know $q_\star $,we know the best policy

Bellman Optimality Equation

• \(v_\star(s) = \underset{a}{max}\, q_{\star}(s, a)\)

• \(q_\star(s, a) = R^a_s + γ \sum_{ s'∈S} P^a_{ss'}v_\star(s')\)

• \(v_\star(s) = \underset{a}{max}R^a_s + γ \sum_{ s'∈S} P ^a_{ ss'}v_\star(s' )\)

• \(q_\star(s, a) = R^a_s + γ\sum_ {s'∈S} P^a_{ss'} \underset{a'}{max}\,q_\star(s' ,a' )\)

Planning by Dynamic Programming

Requirements for Dynamic Programming

• 最优子结构
• 重复的子问题

MDP满足，Bellman方程给了迭代的方程，value function stores，reuses

For prediction:

• Input:
  • \(MDP<S,A,P,R,γ>\) and policy π
  • or: \(MRP<S,P^π ,R^π ,γ>\)
• Output:
  • value function \(v_π\)

for control:

• Input:

• \(MDP <S, A,P, R, γ>\)

• Output:

  • optimal value function \(v_?\) and: optimal policy \(π_?\)

iterative policy evaluation

给定policy \(\pi\) 计算使用该policy的value function.

bellman expectation equation

\[v_π^{k+1}(s) = \sum_{a∈A} π(a|s) (R^a_s + γ \sum_{ s'∈S} P ^a_{ ss'}v_π^k(s' ))\]

policy iteration

policy evalution 不必真的收敛到\(v_\pi\) .因为我们真正需要的是基于价值函数产生的一个better Policy.

value iteration

如果policy evaluation只迭代一次，那么就是value iteration

如果我们有一个子问题的最优解，我们就能够回溯求解父问题的最优解，这就是动态规划里的一个很常见的思想

Bellman Optimality Equation

\(v^{k+1}_\star(s)= \underset{a}{max}R^a_s + γ \sum_{ s'∈S} P ^a_{ss'}v_\star^k(s')\)

value function 跟新过程的中间值不和任何策略有关

可以有一些优化动态规划的方法，inplace，只维护一个v, 每一步只更新受影响的state

如果规模太大backup无法使用

期望不能求，只能采样求均值，采样数据是\(<s,a,r,s'>\),这样就不需要MDP中\(R,P\)。

这样就是model free了

contraction mapping theoremcontraction mapping theorem

\(T^π(v) = R^π + γP^πv\)

\(T^\pi\)满足压缩映射定理，不动点是最优的v,收敛到不动点

蒙特卡洛 and TD

这一节只讲 prediction

Monte-Carlo Policy Evaluation

episodes :must terminate不然没有办法计算Goal

under policy \(\pi\),采样

\(S_1,A_1,R_2,\dots ,S_k \sim \pi\)

\(v_π(s) = E_π [G_t| S_t = s]\)

现如今，没了model,就没办法算期望，

First-visit MCPE

for each in episodes:
    if state s is visited first time in each at time step t:
        N(s)+=1
        S(s)+=G_t
        mean value V(s) = S(s)/N(s)

大数定理，保驾护航

EVERY-visit MCPE

for each in episodes:
    if state s is visited in each at time step t:
        N(s)+=1
        S(s)+=G_t
        mean value V(s) = S(s)/N(s)

first 跟every的区别TODO

求均值可以用累进更新

\(V(s) =V(s)+ \frac{1}{N(t)}(G(t)-V(s))\)

\(N(t)\)是没必要的，换成\(\alpha\)

Robbins-Monro sequence of step-sizes \(α_t\)

• \(\sum_{t=1}^{\infty}\alpha_t=\infty\)

• \(\sum_{t=1}^{\infty}\alpha_t^2=0\)

==更新== 之所以用\(\alpha\) 替换\(1/N(t)\)是因为我们的model不一定是稳定的，所以如果用均值就说明，过去的影响跟现在的影响是一样的，但是我们更关注现在的影响所以用了一个固定的\(\alpha\) 这样影响是指数衰减的。

满足RM的才收敛，所以均值是收敛的，固定alpha是不收敛的（第二项不满足），但是仅仅是理论而已,并且不稳定的环境，收敛个毛

\(V(s) =V(s)+ \alpha(G(t)-V(s))\)

牺牲了一点点精度，换来速度上的提升，我们也可以拥有主动权

TD：Temporal-Difference Learning

MC的一个问题就是\(G(t)\)这玩意太烦人，需要一个完整的终止的episode

G(t)是采样后我们算到的获得的goal.我们可以自己猜一个

TD(0)

\(V(S_t) ← V(S_t) + α (R_{t+1} + γV(S_{t+1}) ? V(S_t))\)

\(R_{t+1}+\gamma V(S_{t+1})\)被称之为TD target

\(\delta = R_{t+1} + γV(S_{t+1}) ? V(S_t)\) is TD error

理想与现实之间的差距，迫使我们磨平棱角，调整我们的理想，但是现实也不真的

是现实，只是眼前的现实加上远方的想象，但是我们偏偏要认为他是现实

TD 可以online 学习，不必要最后的outcome

MC 高方差，无偏差unbias.

TD 低方差，有bias

MC就是把原来的期望换成了采样之后的均值的近似值。实际上没有利用马尔科夫性质

• Bootstrapping: update involves an estimate
  • MC does not bootstrap
  • DP bootstraps
  • TD bootstraps
• Sampling: update samples an expectation
  • MC samples
  • DP does not sample
  • TD samples

TD可以向前look 1 step也可以look n steps,看到底就是MC

\(V(S_t) ← V(S_t) + α(G^{(n)}_t ? V(S_t))\)

我们也可以结合向前看\({n_1,n_2}\)step的均值

产生了TD(\(\lambda\))

$\frac{1}{1-\lambda} =\sum_{i=1}^{\infty}\lambda^i $

\(G^λ_t = (1 ? λ)\sum^∞_{n=1}λ^{n?1}G_t(n)\)

\(V(S_t) ← V(S_t) + α(G^λ_t ? V(S_t))\)

Eligibility Traces(资格迹)

\(E_0(s) = 0\)
\(E_t(s) = γλE_{t?1}(s) + 1(S_t = s)\)

Backward View TD(λ)

\(δ_t = R_{t+1} + γV(S_{t+1}) ? V(S_t)\)
\(V(s) ← V(s) + αδ_tE_t(s)\)

\(TD(\lambda=0)=TD(0)\)

MODEL FREE control

on-policy: learn on the job. learn about policy \(\pi\) form experience sampled from \(\pi\)

off-policy: learn about policy \(\pi\) form experience sampled from \(\mu\)

套路跟MDP control是一样的

首先基于V求greedy \(\pi\)

\(π'(s) = \underset{a\in A}{argmax}R^a_s + P^a_{ss'}V(s')\)

我们不知道P,所以换成

\(π'(s) = \underset{a\in A}{argmax}Q(s,a)\)

问题是：由于只是采样，只采用greedy的方式，可能会陷入局部最优。

\(\epsilon\)-Greedy Exploration

每一步都有\(\epsilon\)的概率随机，确保足够的探索

\(\epsilon\)-greedy is GLIE if \(\epsilon\) reduces to zero at \(\epsilon_k=\frac{1}{k}\)

• 每个（s,a）都可以被探索到

• 策略最终收敛到一个greedy策略：

GLIE MC Control

根据\(\pi\) 采样

$ {S_1, A_1, R_2, ..., S_T }$ ～ π

\(N(S_t, A_t) ← N(S_t, A_t) + 1\)

\(Q(S_t, A_t) ← Q(S_t, A_t) + \frac{1}{N(S_t, A_t)}(G_t ? Q(S_t, A_t))\)

\(\epsilon ← 1/k\)
\(π ← \epsilon-greedy(Q)\)

Updating Action-Value Functions with Sarsa

\(Q(S,A)←Q(S, A) + α(R + γQ(S', A')?Q(S, A))\)

Convergence of Sarsa

\(Q(s, a) → q_?(s, a)\)需要满足两个条件

• \(\pi_t(a|s)\)满足GLIE条件

• Robbins-Monro sequence of step-sizes \(α_t\)

  • \(\sum_{t=1}^{\infty}\alpha_t=\infty\)

  • \(\sum_{t=1}^{\infty}\alpha_t^2=\infty\)

MDP, TD 上面的n-step,lambda技术都可以用到这里

sarsa lambda算法

Off Policy

evaluate target policy \(π(a|s)\) to compute \(v_π(s)\) or \(q_π(s, a)\)
While following behaviour policy \(μ(a|s)\)
\({S_1, A_1, R_2, ..., S_T } ～ μ\)

IS importance sampling

\(E_{X～P}[f(X)]=\sum P(X)f(X)=\sum Q(X)\frac{P(X)}{Q(X)}f(X)= E_{X～Q}[\frac{P(X)}{Q(X)}f(X)]\)

期望是一样的，但是抽样时会不一样

最后是由梯度反推原函数、

划掉的，可以认为差不多，毕竟不会算。

问题来了，两个分布不能差太多？

off policy MC

Off-Policy TD

Q-learning

\(Q(S,A)←Q(S,A)+α(R+γ \,\underset{a'}{max} Q(S', a')?Q(S, A))\)

Value Function Approximation

能力越大 ，责任越大，value function or action-value function 需要更多的责任，需要更大的能力，lookup table 不能够满足要求。所以需要运用函数近似，或者概率分布学习。

自古以来，我们的一个目标就是要让我们的policy 尽可能的接近最优的policy

\(J(w) = E_π[(v_π(S)?\overset{?}{v}(S, w))^2]\)

梯度下降法，寻找局部最小

\(?w=?\frac{1}{2}α?_wJ(w)=αE_π[(v_π(S)?\overset{?}{v}(S,w))?_w\overset{?}{v}(S,w)]\)

SGD

\(?w=α(v_π(S)?\overset{?}{v}(S,w))?_w\overset{?}{v}(S,w)\)

feature vector

linear value function approximation

\(\overset{?}{v}(S,w)=x(S)^Tw=\sum^n_{j=1}x_j(S)w_j\)

\(?w =α(v_π(S) ? \overset{?}{v}(S,w))x(S)\)

table lookup features 就是特殊的feature vector

回到SGD的公式，我们没有\(v_\pi(s)\)

MC，TD有要上场了

MC: \(?w =α(G_t?\overset{?}{v}(S_t, w))?_w\overset{?}{v}(S_t, w)\)

TD(0):\(?w = α(R_{t+1} + γ\overset{?}{v}(S_{t+1}, w) ? \overset{?}{v}(S_t, w))?_w\overset{?}{v}(S_t, w)\)

backward TD-lambda

\(δ_t = R_{t+1} + γ\overset{?}{v}(S_{t+1}, w) ? \overset{?}{v}(S_t, w)\)

\(E_t = γλE_{t?1} + x(S_t)\) 状态的积累和衰减
\(?w = αδ_tE_t\)

因为model free，实际上使用action-value

Batch methods

可以从过去的状态中采样，使用batch的方法，计算

DQN

• experience replay and fixed Q-target

  

一套网络结构，target中用的是比较old的参数。因为更加稳定，不然就是自己追自己，两个乱晃。

我们的目的是让努力接近我们的target,目标定好了才好追。

DQN 变种很多，这里不讲。

Linear Least Squares Prediction 神经网络收敛不容易

\(\overset{?}{v}(s, w) = x(s)^Tw\)

同样需要用各种方法近似\(v_t^\pi\)

Policy Gradient

value-based 的方式，太硬，不好。

下面是李宏毅的推倒

约等于那一步省了个状态转移矩阵\(P_{ss'}\)，还有从\(R(\tau)\) 换成了\(R(\tau^n)\),这一步没有讲。

需要看cs294。相当于直接推过来的梯度下降公式是按照轨迹算的，也就这个轨迹的梯度按照这个轨迹的sum_reward来更改，显然轨迹上的每一点应该分别算。所以看下面的公式。

这玩意和极大似然很像，就是多了一个量而已，代码里也很好实现。

\(上面的\)\(R(t^n)\) 需要换成\(Q(s,a)\)，不能用整个轨迹的return作用到分别的action上，各算各的

policy based 中策略\(\pi\) 可以看做是\(π_θ(s,a)=P[a|s,θ]\)

目标很明确，获取最大的Reward，

三种

• 让初始状态的return 期望最大：\(?_θJ_1(θ)=v_{\pi_\theta}(s_1)=E_{\pi_\theta}[v_1]\)
• 连续环境，平均值最大：\(J_{avV}(θ)=\sum_{s}d^{π_θ}V^{π_θ}(s)\)
• 每个时间步的Reward平均值最大\(JavR(θ) = \sum_{s}d^{π_θ}(s)\sum_aπ_θ(s, a)R^a_s\)

\(d^{\pi_\theta}\) 马尔科夫链对\(\pi_\theta\)的平稳分布(stationary distribution) ==TODO==

所以policy based 的RL是一个优化问题，找到\(\theta\) 让\(J(\theta)\) 最大

很多种方法，这里关注梯度下降法

》大力出奇迹法：

在$\theta $的每个向量分量中微调，算梯度，更新累死人

score function is \(?_θlog π_θ(s, a)\)

常用的两种plicy

• softmax policy

  • weight actions using \(\phi(s,a)^T\theta\)
  • \(\pi_\theta(s,a) ∝ e^{\phi(s,a)^T\theta}\)
  • score function:\(?_θlog {π_θ}(s,a)=\phi(s,a)?E_{π_θ}[\phi(s,·)]\)

• gaussian policy

  • mean :\(\mu(s)=\phi(s)^T \theta\),\(\sigma^2\) can be fixed

  • \(a\sim N(\mu(s),\sigma^2)\)

  • score function:\(?_θlogπ_θ(s,a)=\frac{(a ? μ(s))\phi(s)}{σ^2}\)

for any of the policy objective functions \(J= J_1\), \(JavR\), or $\frac{1}{1?γ}J_{avV} $

三种方式的导数都可以如下表示：\(?_θJ(θ)=E_{π_θ}[?_θlogπ_θ(s, a)Q_{π_θ}(s, a)]\)

压力来到了\(Q_{\pi_\theta}(s,a)\)上

蒙特卡洛 policy gradient(REINFORCE)

用\(v_t\) 作为\(Q^{\pi_\theta}(s_t,a_t)\)的一个无偏采样

on-policy的缺点，取样的参数只能用一次，太浪费了。

下面就是off-policy的

PPO

actor-critic

我们自然而然的想到了利用value based的方法计算\(Q_w(s,a)\),来替换原来公式的\(Q^{\pi_\theta}(s,a)\)

\(?_θJ(θ) ≈ E_{π_θ}[?_θlog π_θ(s,a)Q_w(s,a)]\)
\(?θ = α?_θlogπ_θ(s,a)Q_w (s, a)\)

• Monte-Carlo policy evaluation
• Temporal-Difference learning
• TD(λ)

都可以解决

引入偏差，佛祖说不好，不好

偏差 Compatible Function Approximation Theorem ==TODO==

方差也需要减小

（后面求和为1，导数为0）\(B(s)=V^{\pi_\theta}(s)\)

\(A^{\pi_\theta}(s,a)=Q^{\pi_\theta}(s)-v^{\pi_\theta}(s)\)

DDPG

ddpg适用于连续的action space.就是连续版AC ,其中actor直接给出s对应最优a,critic根据s,a计算他们的value.

critic根据使用td的方式。actor更新的是想让Q值更大的a出现在actor的预测中的概率最大

TD3

TD3主要是对AC算法的改进，也可以说是对DDPG的改进

改进分为三点，

• 因为target_critic容易高估，所以用了两个Q用较小的那个更新critic
• 更新policy的时候也用延迟更新，更新d次critic然后跟新一次actor.价值函数准确，policy更好
• 使用policy smoothing，让价值函数在action上更平滑

Natural Policy Gradient(TODO)

Integrating Learning and Planning(Model based)

从经验中建立一个model

model free :learn

model based: plan

model based RL

Dyna

• Learn a model from real experience
• Learn and plan value function (and/or policy) from real and simulated experience
  

Simulation-Based Sear

1.forward search

从当前状态开始解决一个sub-MDP问题

2.Simulation-Based Search

从当前状态开始采样，然后使用，model-free方法

Simple Monte-Carlo Search 就是算出来样本中平均return最大的那个a

MCTS 蒙特卡洛树搜索

先采样，用样本建树，然后评估。

TD-search

采样，sarsa方法

Dyna-2

Exploration and Exploitation

多臂赌博机，n个杆，每次只能拉一个，拉完有reward,每个杆都有自己未知的分布，怎么选让Reward最大

后悔值:我曾经离最好的你究竟有多远？

\(Q(a) = E [r|a]\)

\(V^? = Q(a^?)= \underset{a∈A}{max}Q(a)\)

\(L_t = E[\sum_{τ=1}^{t}V^??Q(a_τ)]\)

gap:\(?a =V^??Q(a)\)

\(L_t=\sum_{a∈A}E[N_t(a)]?a\)

gaps are unknown

If an algorithm forever explores it will have linear total regret
If an algorithm never explores it will have linear total regret

to be or not to be, this is a question

upper bound确定

所以最好的就是log形式的

1. naive exploration:\(\epsilon\)-greedy 随机的部分永远有gap

   可以用decaying \(\epsilon\)-greedy.

   \(\epsilon = min[1,\frac{c|A|}{d^2t}]\),\(d=\underset{a|\Delta_a>0}{min}\Delta_{i},c>0\)

   log形式的regret ,Problem:不知道gap

2. Optimistic Initialisation: 再被证明之前，认为他是最好的。

   Simple and practical idea: initialise Q(a) to high value

   这样算法自然认为那些未知的是最好的，因为已知的不够好。但是不稳定的model仍然不行，因为这只是改边了开始而已，对于不稳定的model没有所谓的开始

3. Optimism in the Face of Uncertainty： 更喜欢不确定的

   我们选择的策略可以分两部分，一部分是均值，一部分是根据分布的不确定性

   \(a_t = \underset{a\in A}{argmax}\overset{?}{Q_t}(a)+\overset{?}{U_t}(a)\)
   

   \(e^{?2N_t(a)U_t(a)^2}=p\)

   \(U_t(a)= \sqrt{\frac{-log p}{2N_t(a)}}\)

   随着更多的观察，我们需要p越来越小，这样我们的置信度越来越高，不确定程度也会越来越小。比如让\(p=t^{-4}\)

   \(U_t(a)= \sqrt{\frac{2log\, t}{N_t(a)}}\)

   公式可以很好的让不确定程度逐渐减小

   \(a_t = \underset{a\in A}{argmax}{Q_t}(a)+\sqrt{\frac{2log\, t}{N_t(a)}}\)

   \(lmt_{t→∞}L_t ≤ 8 log\, t \sum_{a|?a>0}?_a\) UCB算法对数渐进

4. Probability Matching：根据概率分布来选

我们可以使用贝叶斯的思想，使用P(R)的先验知识、上面我们只是假设reward有界

这叫做 Bayesian bandits

比如使用贝叶斯UCB假设分布是独立的高斯分布\(a_t = \underset{a∈A}{argmax}\, μ_a + cσ_a/\sqrt{N(a)}\)

另外就是\(π(a|h_t)=P[Q(a)>Q(a'),?a'\neq a|h_t]\)

从历史中算出来一个a是最好的a的概率，但是很显然不好算

1. Information State Search：结合信息来选

探索之所以有用是因为带来了信息，如何衡量信息的大小

\(\overset{\sim}{M} = <\overset{\sim}S, A,\overset{\sim}{P}, R, γ>\)

\(\overset{\sim}s=f(h_t)\).

把伯努利赌博机，变成了一个infinite的MDP

可以用model-free 的Q-learning的方法

也可以用Bayesian model based 的RL方法

==TODO==