一、长期回报
对于问题的简化,采用理想的MDP,简化问题到具有马尔科夫性,对于马尔科夫决策过程而言,在理想状态下,每一个行动都要为最终的目标最大化长期回报 而努力。
maxt∑rt
但是很多情况下,仿真的时间维度较大,步数较多,甚至可以无限循环下去,这样的情况下我们需要引入一个可以和收敛的无穷数列,来替代我们最原始的长期回报公式。即对未来的回报乘以一个折扣率,使得长期回报变得更有意义:
t=0∑γtrt(γ<1)
由此我们引出长期回报的概念,即从当前状态开始对之后的所有回报,运用上式进行累加的折扣率计算:
Rett=k=0∑γkrt+k+1
但是长期回报需要知道未来的行动情况,我们需要对上式进行一个合理的估计,因而我们定义了策略的价值。
二、值函数
由于环境的原因,MDP中的状态转移概率有时候并不能够确定,因而需要基于状态转移来估计长期回报的期望。τ是从某个状态s出发,根据策略与状态转移概率采样得到的序列(trajectory)。那么价值函数可以表示为:
vπ(st)=Es,a∼τ[k=0∑γkrt+k+1]=τ∑p(τ)k=0∑∞γkrt+k+1
根据MDP模型的形式,值函数一般分为两种:
-
状态值函数 vπ(s): 已知当前状态s,按照某种策略行动产生的长期回报期望;
- **状态-动作值函数 ** qπ(s,a): 已知当前状态s及动作a,按照某种策略行动产生的长期回报期望。
由于符合马尔科夫性,我们可以将值函数的形式进行马尔科夫展开,其中π(at∣st)表示,在st状态下选择策略π的概率,策略π将产生行动at,p(st+1∣st,at)表示在策略π的情况下,从st,at到达st+1的概率。
vπ(st)=(st,at,...)∼τ∑π(at∣st)p(st+1∣st,at)...k=0∑∞γkrt+k+1
三、贝尔曼方程
- 状态值函数的贝尔曼方程
通过代换消元,可以将上式整理为状态值函数的贝尔曼方程:
vπ(st)=at∑π(at∣st)st+1∑p(st+1∣st,at)[rt+1+γvπ(st+1)]
更直观一点可以将贝尔曼方程描述为一种DP的形式,即当前状态s下,选择策略π的长期回报期望。
vπ(st)=at,st+1∑π(at∣st)E[rt+1+γvπ(st+1)]
按Sutton的书表示:
vπ(s)=Eπ[rt+1+γvπ(st+1)∣st=s]
- 状态-动作值函数的贝尔曼方程
类似地,可以定义状态-动作值函数的贝尔曼方程:
qπ(st,at)=st+1∑p(st+1∣st,at)at+1∑p(at+1∣st+1)[rt+1+γqπ(st+1,at+1)]
按Sutton的书表示:
qπ(s,a)=E[rt+1+γqπ(st+1,at+1)∣st=s,at=a]
- Bellman optimality equation
v∗(s)=E[rt+1+γmaxπv(st+1)∣st=s]
q∗(s,a)=E[rt+1+γmaxat+1q(st+1,at+1)∣st=s,at=a]
四、Monte-Carlo与Time Difference
- MC 方差较大,需要较深的探索获取回报
- TD 方差较小,偏差较大,可设定探索深度(1-step, n-step), Q-Learning, SARSA都属于TD
【参考】https://zhuanlan.zhihu.com/p/25239682
Monte-Carlo method适用于“情节式任务”(情节任务序列有终点,与“情节式任务”相对应的是“连续型任务”)。Q(s,a)就是整个序列的期望回报。MC增量更新中的Monte-Carlo error (R−Q(st,at)):
Q(st,at)⇐Q(st,at)+α(R−Q(st,at))
TD(Time Difference) method,是MC和DP 方法的一个结合。相比MC方法,TD除了能够适用于连续任务外,和MC的差异从下图可以清楚看到。MC需要回退整个序列更新Q值,而TD只需要回退1步或n步更新Q值。因为MC需要等待序列结束才能训练,而TD没有这个限制,因此TD收敛速度明显比MC快,目前的主要算法都是基于TD。下图是TD和MC的回退图,很显然MC回退的更深。
![强化学习专题笔记(一) 强化学习基础 强化学习专题笔记(一) 强化学习基础](/default/index/img?u=aHR0cHM6Ly93czEuc2luYWltZy5jbi9sYXJnZS8wMDZnQ2JDSGx5MWZ4MG8zM3lkaGtqMzB5aTA3dW15bS5qcGc=)
![强化学习专题笔记(一) 强化学习基础 强化学习专题笔记(一) 强化学习基础](/default/index/img?u=aHR0cHM6Ly9waWFuc2hlbi5jb20vaW1hZ2VzLzYxMC8wOTE0MmE5YTcyOWI5MzUyZGY3YjdmNzdiOWE0MDlmMi5wbmc=)
1-step TD error: (rt+1+γQ(st+1at+1−Q(st,at)):
Q(st,at)⇐Q(st,at)+α(rt+1+γQ(st+1,at+1)−Q(st,at))
n-steps TD error:
![强化学习专题笔记(一) 强化学习基础 强化学习专题笔记(一) 强化学习基础](/default/index/img?u=aHR0cHM6Ly93d3cuemhpaHUuY29tL2VxdWF0aW9uP3RleD1SJTVFJTdCJTI4biUyOSU3RCUzRHJfJTdCdCUyQjElN0QlMkIlNUNnYW1tYStyXyU3QnQlMkIyJTdEJTJCLi4uJTJCJTVDZ2FtbWErJTVFJTdCbi0yJTdEcl8lN0J0JTJCbi0xJTdEJTJCJTVDZ2FtbWErJTVFJTdCbi0xJTdEUSUyOHNfJTdCdCUyQm4lN0QlMkMrYV8lN0J0JTJCbiU3RCUyOSsr)
TD(λ) error:
![强化学习专题笔记(一) 强化学习基础 强化学习专题笔记(一) 强化学习基础](/default/index/img?u=aHR0cHM6Ly93d3cuemhpaHUuY29tL2VxdWF0aW9uP3RleD1SJTVFJTdCJTI4JTVDbGFtYmRhKyUyOSU3RCUzRCUyODEtJTVDbGFtYmRhKyUyOSU1Q3N1bV8lN0JuJTdEJTVFJTdCaSUzRDElN0QlN0IlNUNsYW1iZGErJTVFJTdCaSU3RFIlNUUlN0IlMjhpJTI5JTdEJTdEKw==)
事实上,MC error可以视为一个情节任务的max-step TD error。另外,一般来说,在TD error中,n越大,用到的真实回报信息更多,收敛也会越快。
五、推荐文章
[强化学习(四)用蒙特卡罗法(MC)求解]
强化学习(五)用时序差分法(TD)求解