Value function approximation
Value function approximation
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：[https://blog.csdn.net/Solo95/article/details/102777091](https://blog.csdn.net/Solo95/article/details/102777091) 前面的一篇博客:Model-free control：如何从经验中学习一个好的策略
到目前为止，我们都假设了可以将价值函数或state-action价值(即Q函数)表示成向量或者矩阵
- 表格表示法
很多现实世界的问题会有巨大的状态空间 和/或 动作空间
表格表示法是不够用(insufficient)的
回顾：强化学习包括
- Optimization(优化)
- Delayed consequence(效果迟延)
- Exploration(探索)
- Generalization(泛化)
Value Function Approximation (VFA)
使用一个参数化的函数来表示一个(state-action/state)价值函数而不是一张表格
w可以是一个网络或者多项式。
Motivation for VFA
不希望对每一个状态a都要显式的学习或储存
- 动态模型或回报模型
- 价值
- state-action价值(Q值)
- 策略
希望有更完备的表示，能在状态和状态之间或者状态-动作和状态-动作之间泛化
Benefits of Generalization
- 降低存储需要的存储空间 (P,R)/V/Q/π(P,R)/V/Q/\pi(P,R)/V/Q/π
- 降低计算量(P,R)/V/Q/π(P,R)/V/Q/\pi(P,R)/V/Q/π
- 降低寻找一个好的(P,R)(P,R)(P,R)所需要的经验 (P,R)/V/Q/π(P,R)/V/Q/\pi(P,R)/V/Q/π
- 等价于需要的数据
可能不是非常好的近似，可能不会使得你能够表示一个好的策略。这会是一个bias-variance的权衡(trade-off)在加上一个函数近似权衡。你有一个非常小的表示，不需要大量数据来拟合，但它同样不会有好的容量去表示复杂的价值或策略。
Function Approximators
在函数近似这方面，有大量可选的函数近似器，我们该选择哪一个？
- 大量可能的函数近似器包括
- 特征的线性组合
- 神经网络
- 决策树
- 近邻算法
- Fourier / wavelet bases在这篇博文里我们关注可微的函数近似器(想想看，为什么)- 两类非常流行的可微函数近似器(in RL)
- 线性特征表示(here)
- 神经网络(可能会写到下一篇博文)线性特征表示是前几年研究的最多的近似器。
Value Function Approximation for Policy Evaluation with an Oracle
- 首先假定我们可以查询任何状态s并且有一个黑盒能返回给我们Vπ(s)V^\pi(s)Vπ(s)的真实值
- 目标是给定一个特定的参数化函数找到最佳的VπV^\piVπ的近似表示
应用于价值函数的随机梯度下降
∇wJ(w)=Eπ2(Vπ(s)−V~(s,w))∇wV\nabla_w J(w)=E_\pi2(V^\pi(s)-\tilde{V}(s,w)) \nabla_w V∇wJ(w)=Eπ2(Vπ(s)−V~(s,w))∇wV
Δw=α(Vπ(s)−V~(s,w))∇wV(s)\Delta w=\alpha(V^\pi(s)-\tilde{V}(s,w)) \nabla_w V(s)Δw=α(Vπ(s)−V~(s,w))∇wV(s)
updating w
Model Free VFA Policy Evaluation
当然，现实中我们没有能力去分辨任何状态s的Vπ(s)V^\pi(s)Vπ(s)
现在考虑如何做model-free的价值函数近似用于在没有模型的条件下进行预测/评估/策略评估
Model Free VFA Prediction / Policy Evaluation
- 遵循一个固定的策略(或者能够访问之前的数据)
- 目标是估计VπV^\piVπ和/或QπQ^\piQπ
维护一张可查表来存储VπV^\piVπ和/或QπQ^\piQπ的估计
在每一个周期结束之后更新这些估计(蒙特·卡罗尔方法)或每一步之后(TD方法)
现在：在价值函数近似，更改估计更新的步骤把拟合函数近似器包括进去
Feature Vector
使用一个特征向量来表示一个状态s
x(s)={x1(s)x1(s)...xn(s) x(s)= \begin{cases} x_1(s) \ x_1(s) \ ... \ x_n(s) \ \end{cases} x(s)=⎩⎪⎪⎪⎨⎪⎪⎪⎧x1(s)x1(s)...xn(s)
这个特征向量非常原始，非常简单，可能不是马尔科夫的，但是合理的。
特征表示的选择非常重要。
Linear Value Function Approximation for Prediction With an Oracle
用一个加权的线性组合来表示一个特定策略的价值函数(或者state-action价值函数)
V^(s:w)=∑j=1nxj(s)wj=x(s)Tw\hat{V}(s:w)=\sum_{j=1}^nx_j(s)w_j=x(s)^{\Tau} \bf{w}V^(s:w)=j=1∑nxj(s)wj=x(s)Tw
目标函数是
J(w)=Eπ(Vπ(s)−V^(s;w))2J(\textbf{w})=\mathbb{E}_\pi(V^\pi(s)-\hat{V}(s;\textbf{w}))^2J(w)=Eπ(Vπ(s)−V^(s;w))2
权重更新是
Δw=−12α∇2J(w)\Delta \textbf{w} = -\frac{1}{2}\alpha \nabla_{\textbf{2}}J(\textbf{w})Δw=−21α∇2J(w)
即
Δw=−12α(2(Vπ(s)−Vπ(a;w)^))x(s)\Delta \textbf{w} =-\frac{1}{2}\alpha(2(V^\pi(s)-\hat{V^\pi(a;w)}))x(s)Δw=−21α(2(Vπ(s)−Vπ(a;w)^))x(s)
线性函数近似有一个优点，可以清晰直观地理解为
Update = step-size * prediction * feature value
三部分对应上面公式的三部分