对于Env来说,属于MP,但是不是参数已知的MDP
比如元组中a、s、P的关系不确定 or 未知
Prediction -> Control
Evaluation -> Optimization
蒙特卡洛法 Monte-Carlo learning
基于大数定律:
(V(s) -> V_pi(s)) as (N(s)->infty)
均值累计计算:
[
egin{aligned}
mu_{k} &=frac{1}{k} sum_{j=1}^{k} x_{j} \
&=frac{1}{k}left(x_{k}+sum_{j=1}^{k-1} x_{j}
ight) \
&=frac{1}{k}left(x_{k}+(k-1) mu_{k-1}
ight) \
&=mu_{k-1}+frac{1}{k}left(x_{k}-mu_{k-1}
ight)
end{aligned}
]
类似于PID的P 增益
改写计算方式,用(alpha)代替(frac{1}{N(s_t)})
(V(S_t) leftarrow V(S_t)+alpha(G_t - V(S_t)))
可以看到这里的(alpha)和机器学习里面用的学习率是一个符号
差分法Temporal-Difference learning
- 直接从episodes 的经验学习
- model-free:不知道MDP的Transition转移和Reward回报
- Bootstrapping自举学习,从部分例子学习
Goal:学习(v_{pi}) 的值,under policy (pi)
TD(0)方法:
[
Vleft(S_{t}
ight) leftarrow Vleft(S_{t}
ight)+alphaleft(R_{t+1}+gamma Vleft(S_{t+1}
ight)-Vleft(S_{t}
ight)
ight)
]
TD target 是
与MC方法区别
项目 | MC | TD |
---|---|---|
不完整片段学习能力 | 无 | 有 |
在线学习(every step)能力 | update until the end | 有 |
loop环境学习能力 | 无,必须terminating | 有 |
收敛性好 | 是 | |
初值敏感 | 否 | 是 |
偏差bias | zero | some |
方差variance | high | low |
对于最优估计
- MC方法:最小化均方根MSE
[
sum_{k=1}^{K} sum_{t=1}^{T_{k}}left(G_{t}^{k}-Vleft(s_{t}^{k} ight) ight)^{2}
] - TD(0)方法:最大似然估计 max likelihood Markov model
Solution to the MDP (langlemathcal{S}, mathcal{A}, hat{mathcal{P}}, hat{mathcal{R}}, gamma angle) that best fits the data
[
hat{mathcal{P}}_{s, s^{prime}}^{a} =frac{1}{N(s, a)} sum_{k=1}^{K} sum_{t=1}^{T_{k}} 1left(s_{t}^{k}, a_{t}^{k}, s_{t+1}^{k}=s, a, s^{prime} ight) ]
[
hat{mathcal{R}}_{s}^{a} =frac{1}{N(s, a)} sum_{k=1}^{K} sum_{t=1}^{T_{k}} 1left(s_{t}^{k}, a_{t}^{k}=s, a ight) r_{t}^{k}
]
总结:DP、MC、TD
- Bootstrapping自举:利用自己估计值update
- Sampling采样 :更新样本期望
项目 | 动态规划DP | 蒙特卡洛MC | 差分TD |
---|---|---|---|
自举Bootstrapping | 1 | 0 | 1 |
采样Sampling | 0 | 1 | 1 |
TD用了Markov特性,因此在MP过程高效
MC相反,统计规律,非MP过程更高效
TD((lambda))法
扩展TD(0),视野扩展到N个step,N=全过程时,变为MC
TD(N)推导
对于某个问题来说,没有那个N值是最优的
因此,用几何加权的方法来对视野做平均
Forward
(lambda):对视野的平均
for iteration: t -> t+1
update value function
引入权重概念,前面的重要,指数衰减
Backward
Credit assignment:
引入 Eligibility Traces:关于状态s的权重
当s重复出现,E值升高,不出现,指数下降
(E_{0}(s)=0)
(E_{t}(s)=gamma lambda E_{t-1}(s)+mathbf{1}left(S_{t}=s
ight))
Backward步骤:
- 对每个状态s 创建 迹值
- 对每个状态s 更新 V(s)
- 与 TD-error((delta_t)) 和 Eligibility trace (E_t(s)) 成比例
[
egin{aligned}
delta_{t} &=R_{t+1}+gamma Vleft(S_{t+1}
ight)-Vleft(S_{t}
ight) \
V(s) & leftarrow V(s)+alpha delta_{t} E_{t}(s)
end{aligned}
]
[
sum_{t=1}^{T} alpha delta_{t} E_{t}(s)=sum_{t=1}^{T} alphaleft(G_{t}^{lambda}-Vleft(S_{t}
ight)
ight) 1left(S_{t}=s
ight)
]
对于(lambda in [0,1]),满足TD error = (lambda-error)
对于online 的updates来说,TD((lambda))前后向视图稍有不同,引入Exact online TD((lambda))
总结
TD(0) 向后看一步
TD((lambda)) 视野距离按(lambda)指数衰减,叠加
TD(1) 视野不按指数衰减
对于离线更新来说:
TD(0) = TD((lambda)) = TD(1)
对于在线更新,引入Exact online TD((lambda))