北京手机站建站,做seo优化产品网站,网站备案幕布要求,建设网站一定需要云服务器么对于大部分情况来说#xff0c;环境是未知的#xff0c;也就是说状态转移概率未知#xff0c;对于这种情况的算法称为免模型预测算法。免模型算法与环境不断交互学习#xff0c;但是需要大量的运算。
蒙特卡洛方法
蒙特卡罗方法通过重复随机抽选#xff0c;之后运用统计…对于大部分情况来说环境是未知的也就是说状态转移概率未知对于这种情况的算法称为免模型预测算法。免模型算法与环境不断交互学习但是需要大量的运算。
蒙特卡洛方法
蒙特卡罗方法通过重复随机抽选之后运用统计概率此方法来从抽样结果中归纳我们想要得到的数值估计。如下图所示圆面积与正方形面积的比等于落入圆内的点与落入正方形的内的点的比 一个状态的价值是它的期望回报可以采样多条序列计算从这个状态出发的回报再求期望如下式所示 V π ( s ) E π [ G t ∣ S t s ] ≈ 1 N ∑ i 1 N G t ( i ) V^\pi(s)\mathbb{E}_\pi[G_t|S_ts]\approx\frac{1}{N}\sum_{i1}^NG_t^{(i)} Vπ(s)Eπ[Gt∣Sts]≈N1i1∑NGt(i) 在采样得到的某一序列中可能没有我们想要计算的状态也可能出现一次这个状态当然也可能出现多次这个状态。我们介绍的蒙特卡洛价值估计方法在该状态每一次出现时计算他的回报如以下流程所示
先通过策略采用若干条序列在对每一条序列中的每一个状态s进行以下操作 更新状态s的计数器 N ( s ) ← N ( s ) 1 N(s)\gets N(s)1 N(s)←N(s)1更新状态s的总回报 M ( s ) ← M ( a ) G t M(s)\gets M(a)G_t M(s)←M(a)Gt 每一个状态的价值被估计为回报的平均值 V ( s ) M ( s ) / N ( s ) V(s)M(s)/N(s) V(s)M(s)/N(s)
根据大数定律当 N ( s ) → ∞ N(s)\to \infty N(s)→∞ 有 V ( s ) → ∞ V(s)\to \infty V(s)→∞计算回报的期望时可以采用增量更新的方式 N ( s ) ← N ( s ) 1 N(s)\gets N(s)1 N(s)←N(s)1 V ( s ) ← V ( s ) 1 N ( s ) ( G − V ( s ) ) V(s)\gets V(s)\frac{1}{N(s)}(G-V(s)) V(s)←V(s)N(s)1(G−V(s))
这种方式的原理在多臂老虎机中推导过 Q k 1 k ∑ i 1 k r i 1 k ( r k ∑ i 1 k − 1 r i ) 1 k ( r k ( k − 1 ) Q k − 1 ) 1 k ( r k k Q k − 1 − Q k − 1 ) Q k − 1 1 k [ r k − Q k − 1 ] \begin{aligned} Q_{k} \frac1k\sum_{i1}^kr_i \\ \frac{1}{k}\left(r_k\sum_{i1}^{k-1}r_i\right) \\ \frac1k(r_k(k-1)Q_{k-1}) \\ \frac1k(r_kkQ_{k-1}-Q_{k-1}) \\ Q_{k-1}\frac1k[r_k-Q_{k-1}] \end{aligned} Qkk1i1∑krik1(rki1∑k−1ri)k1(rk(k−1)Qk−1)k1(rkkQk−1−Qk−1)Qk−1k1[rk−Qk−1]
在使用时一般不严格按照期望的方法计算而是将 1 N ( s ) → α \frac{1}{N(s)} \to \alpha N(s)1→α 即转化为一个常数 V ( s t ) ← V ( s t ) α [ G t − V ( s t ) ] V(s_t)\leftarrow V(s_t)\alpha[G_t-V(s_t)] V(st)←V(st)α[Gt−V(st)] 即 新的估计值 ← 旧的估计值 步长 ∗ ( 目标值 − 旧的估计值 ) \text{新的估计值} \gets 旧的估计值步长 \ *(目标值-旧的估计值) 新的估计值←旧的估计值步长 ∗(目标值−旧的估计值) 通过添加学习率的方式可以避免因为个别不好的样本而导致更新的急剧变化从而导致学习得不稳定。
时序差分方法
在时序差分算法时使用当前获得的奖励和下一个状态的价值估计来作为当前状态会获得回报 V ( s t ) ← V ( s t ) α [ r t γ V ( s t 1 ) − V ( s t ) ] V(s_t)\leftarrow V(s_t)\alpha[r_t\gamma V(s_{t1})-V(s_t)] V(st)←V(st)α[rtγV(st1)−V(st)] 时序差分算法将时序差分误差 r t γ V ( s t 1 ) − V ( s t ) r_t\gamma V(s_{t1})-V(s_t) rtγV(st1)−V(st) 与步长的乘积作为状态价值的更新量。 V π ( s ) E π [ G t ∣ S t s ] E π [ ∑ k 0 ∞ γ k R t k ∣ S t s ] E π [ R t γ ∑ k 0 ∞ γ k R t k 1 ∣ S t s ] E π [ R t γ V π ( S t 1 ) ∣ S t s ] \begin{aligned} V_{\pi}(s) \mathbb{E}_\pi[G_t|S_ts] \\ \mathbb{E}_\pi[\sum_{k0}^\infty\gamma^kR_{tk}|S_ts] \\ \mathbb{E}_\pi[R_t\gamma\sum_{k0}^\infty\gamma^kR_{tk1}|S_ts] \\ \mathbb{E}_\pi[R_t\gamma V_\pi(S_{t1})|S_ts] \end{aligned} Vπ(s)Eπ[Gt∣Sts]Eπ[k0∑∞γkRtk∣Sts]Eπ[Rtγk0∑∞γkRtk1∣Sts]Eπ[RtγVπ(St1)∣Sts] 蒙特卡洛以第一步为更新目标计算所有状态后得到回报时序差分算法以上式最后一行作为更新目标在用策略和环境交互时每采样一步我们就可以用时序差分算法来更新状态价值估计。
n步时序差分
可以将一步调整为两步利用两步得到回报来更新状态的价值调整n步就是n步时序差分。 n 1 ( T D ) G t ( 1 ) r t 1 γ V ( s t 1 ) n 2 G t ( 2 ) r t 1 γ r t 2 γ 2 V ( s t 2 ) n ∞ ( M C ) G t ∞ r t 1 γ r t 2 ⋯ γ T − t − 1 r T \begin{aligned} n1(\mathrm{TD})\quad G_t^{(1)}r_{t1}\gamma V\left(s_{t1}\right) \\ n2\quad G_t^{(2)}r_{t1}\gamma r_{t2}\gamma^2V\left(s_{t2}\right) \\ n\infty(\mathrm{MC})\quad G_t^\inftyr_{t1}\gamma r_{t2}\cdots\gamma^{T-t-1}r_T \end{aligned} n1(TD)Gt(1)rt1γV(st1)n2Gt(2)rt1γrt2γ2V(st2)n∞(MC)Gt∞rt1γrt2⋯γT−t−1rT 当n趋近于无穷大时我们会发现所用到的就是蒙特卡洛方法了。
我们一般用 λ \lambda λ 表示n有一些方法可以筛选出合适的 λ \lambda λ
网格搜索Grid Search给定一组值依次遍历取最佳随即搜索随机选择值在验证集上评估每个值对应的算法性能
时序差分和蒙特卡洛的比较
蒙特卡洛是取N个序列进行运算得到价值时序差分通过每一步的更新使用下一个状态的估计值 V ( s t 1 ) V(s_{t1}) V(st1)得到价值的预估值。
