# 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 Propertystate历史：$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
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ |
