强化学习笔记（周博磊）

 
# Lecture 1：概括与基础
和 supervised learning 的区别：
* 强化学习是Sequential data作为input，每次输入并不是独立同分布
* 没有ground truth, learner不会被告知什么action是正确的。需要不断去尝试
* Trail-and-error exploration（balance between explioration and exploitation）
* reward signal是延迟的

rollout：sample actions

Full observation: $O_t=S_t^e=S_t^a$
Partial observation: Partially observation Markov decision process(POMDP)

Agent: Policy, Value function, Model(agent对世界的理解)
Stochastic policy： $/pi (a|s)=P[A_t=a|S_t=s]$
Deterministic policy：$a*=/mathop{/arg/max}_{a}/pi(a|s)$

Value-function:
$$v_{/pi}(s)/equiv/mathbb{E}_{/pi}[G_t|S_t=s]=/mathbb{E}_{/pi}[/sum/limits_{k=0}^{/infty}/gamma^kR_{t+k+1}|S_t=s], s/in/mathcal{S}$$
Q-function:
$$q_{/pi}/equiv/mathbb{E}_{/pi}[G_t|S_t=s, A_t=a]=/mathbb{E}_{/pi}[/sum/limits_{k=0}^{/infty}/gamma^kR_{t+k+1}|S_t=s, A_t=a]$$

## Model
预测下一步环境将会怎么做
$$/mathcal{P}_{ss’}^{a}=/mathbb{P}[S_{t+1}=s’|S_t=s, A_t=a]$$
$$/mathcal{P}_{s}^a=/mathbb{E}[R_{t}| S_t=s, A_t=a]$$

## 不同的表征：
* Value-based agent: 显式输出value，隐式输出policy

* Policy-based agent: 显式输出policy， 没有value function

* Actor-Critic agent：策略函数和价值函数都学习了

* Model based: 显式学习model

* Model free：没有model，显式学习value和policy function


# Lecture2: Markov
## Markov Property
state历史：$h_t=/{s_1, s_2, …, s_t/}$
称一个 $s_t$ 是Markovian，当且仅当：$$p(s_{t+1}|s_t)=p(s_{t+1}|h_t)$$$$p(s_{t+1}|s_t, a_t)=p(s_{t+1}|h_t,a_t)$$

## Markov Process/Markov Chain
* 使用状态转移矩阵$P$来描述: $P_{s,s’}(s_{t+1}=s’|s_t=s)$
* 思考：如何通过sample一些trajectory来还原$P$?直接根据出现频率计算即可（利用Markov Property）

## Markov Reward Process
* 奖励是state的函数
* 随波逐流的小船
* Horizon：一个episode中最大的步数（可以是$/infty$）
* Return:$$G_t=R_{t+1}+/gamma R_{t+2}+…+/gamma^{T-t-1}R_T$$
为什么用折扣因子？
（1）防止有环
（2）未来有不确定性，尽可能尽快获得奖励
（3）对人来说，也是希望尽可能尽快收获奖励
（4）当然也可以设置成0或者1
* Value Function:$$V_t(s)=/mathbb{E}[G_t|s_t=s]$$
Bellman equation：$$V(s)=R(s)+/gamma /sum/limits_{s’/in S}P(s’|s)V(s’)$$
如何计算？
（1）蒙特卡洛：直接sample足够多的trajectory
（2）动态规划：不断迭代Bellman方程直到收敛

## Markov Decision Process
* MDP可以由确定。加入action之后的变化：
$$P(s_{t+1}=s’|s_t=s,a_t=a)// R(s,a)=R(s_t=s,a_t=a)=/mathbb{E}[r_t|s_t=s,a_t=a]$$
* 策略和MDP是独立的，是属于agent的一部分。因此，给定一个MDP：$(S,A,P,R,/gamma)$ 和 $/pi$，就可以将MDP转化为Markov Reward Process：$(S,P^{/pi},R^{/pi},/gamma)$，其中：$$P^{/pi}(s’|s)=/sum/limits_{a/in A}/pi(a|s)P(s’|s,a)// R^{/pi}(s)=/sum/limits_{a/in A}/pi(a|s)R(s,a)$$
* 加入action之后，相当于状态转移加入了agent的行为，因此在计算期望时的采样也会受到策略的影响，因此：$$v^/pi(s)=/mathbb E_/pi[G_t|s_t=s]// q^/pi(s,a)=/mathbb E_/pi[G_t|s_t=s,A_t=a]// v^/pi(s)=/sum/limits_{a/in A}/pi(a|s)q^/pi(s,a)$$
* Backup：当前状态是下一状态的线性组合
$$v^/pi(s)=/sum/limits_{a /in A}/pi(a|s)R(s,a)+/gamma/sum/limits_{a /in A}/pi(a|s)P(s’|s,a)v^/pi(s’) // q^/pi(s,a)=R(s,a)+/gamma/sum/limits_{s’/in S}P(s’|s,a)/sum/limits_{a’/in A}/pi(a’|s’)q^/pi(s’,a’)$$

#### Policy Evaluation（Prediction）：根据 $/pi$ 求 $v^/pi$
> $/textbf{Synchronous backup}$
$$v_{t+1}=/sum/limits_{a/in /mathcal{A}}/pi(a|s)R(s,a)+/gamma /sum/limits_{s’/in/mathcal{S}}/pi(a|s)P(s’|s,a)v_t(s’)$$不断迭代直到收敛
[动态演示](https://cs.stanford.edu/people/karpathy/reinforcejs/gridworld_dp.html)
#### Control: 输入MDP，输出最优价值函数和最优policy
$$/pi^*(a|s)=/left/{
/begin{array}{lll}
1 & a=/argmax/limits_{a/in/mathcal{A}}q^*(s,a) //
0 & else
/end{array}
/right.$$

> $/textbf{Value Iteration Algorithm}$
Initialize $k=1$ and $v_0(s)=0$ for all state s
$For/ k=1:H$
$/ / / / / For/ each/ state/ s:$$$q_{k+1}(s,a)=R(s,a)+/gamma/sum/limits_{s’/in/mathcal{S}}P(s’|s,a)v_k(s’)//v_{k+1}(s’)=/max/limits_{a}q_{k+1}(s, a)$$
$/ / / / / k/larr k+1 $
To get optimal policy:$$/pi(s)=/argmax/limits_{a}R(s, a)+/gamma/sum/limits_{s’/in/mathcal{S}}P(s’|s,a)v_{k+1}(s’)$$

# 第三讲 无模型的价值函数估计和控制
前提：不知道MDP的模型
什么是已知MDP？已知R和P

### Monto-Carlo算法：
##### 特点：
* 不需要知道reward和转移概率，只需要sample足够多的trajectory然后进行平均来估计价值函数。
* booststrap：一种非参数统计方法：
在原有样本中通过重抽样（有放回的抽取，完全独立同分布）抽取一定数量的新样本，每次得到一个统计量，将这些统计量进行平均即可近似算出总体的参数估计值
* no bootstrapping（DP用的就是bootstrapping）
* 不假设是MArkov的
* 使用empirical mean return而不是expected return
* 只能应用于episodic MDPs（each episode terminates）

##### Empirical Mean：
* $/mu_t = /frac{1}{t}/sum_i x_i=/frac{1}{t}(x_t+/sum_{i=0}^{t-1} x_i)=/frac{1}{t}(x_t+(t-1)/mu_{t-1})=/mu_{t-1}+/frac{1}{t}(x_t-/mu_{t-1})$

##### 算法：

##### Running Mean
忘记old带来的影响
$v(S_{t})=v(S_t)+/alpha(G_t-v(S_t))$
$/alpha$越大新的带来的影响越大，大于$/frac{1}{n}$将会有遗忘效果

### Temporal-Difference（TD）Learning
特点：
* 直接从trajectory经验中学习
* model-free：不需要知道R和P
* 可以从incomplete episodes中学习，通过bootstrapping