精华内容
下载资源
问答
  • 价值函数近似

    2019-10-18 10:15:13
    价值函数逼近 在传统TD算法、Q-leanring中,V价值和Q价值通常是用表格存储,不适用于大规模问题。可以采用近似器来拟合真实的价值函数。 Q(s,a,θ)≈Qπ(s,a)Q(s,a,\theta) ≈Q_π(s,a)Q(s,a,θ)≈Qπ​(s,a) V(s,θ...

    价值函数逼近

    在传统TD算法、Q-leanring中,V价值和Q价值通常是用表格存储,不适用于大规模问题。可以采用近似器来拟合真实的价值函数。
    Q(s,a,θ)Qπ(s,a)Q(s,a,\theta) ≈Q_π(s,a)
    V(s,θ)Vπ(s)V(s,\theta) ≈V_π(s)
    用一个带θ\theta参数的函数近似器,来代替真实的价值函数,通过训练,找到合适的参数θ\theta,使得两者的误差尽可能小。(θ\theta是一系列参数的总称,不是指只有一个参数,θT=[θ1,θ2,...]\theta^T=[\theta_1,\theta_2,...])
    常用的近似器有线性模型神经网络、决策树、最近邻法等。
    强化学习的样本数据是非静态的,且非独立同分布(后一个状态往往与前一个状态有很强的关联性),因此要求近似器也要适用于非静态、非独立同分布的数据。

    价值函数近似求解

    找到了合适的价值函数的近似器V(s,θ)V(s,\theta),如何找到合适的θ\theta,使得近似器能够真正代替真实Vπ(s)V_π(s)。建立一个两者的平方误差函数,
    J(θ)=E[(Vπ(s)(V(s,θ))2]J(\theta)=E[(V_π(s)-(V(s,\theta))^2]
    转化成求函数J(θ)J(\theta)的优化问题,即找到θ\theta使得J(θ)J(\theta)值最小。常用梯度下降法进行求优。(其他优化算法还有,牛顿法,批量梯度下降,动量梯度下降,RMSprop,Nesterov, Adagrad,Adam)

    梯度下降

    在这里插入图片描述
    对目标函数J(θ)=E[(Vπ(s)V(s,θ))2]J(\theta)=E[(V_π(s)-V(s,\theta))^2]
    求梯度,θJ(θ)=E[2(Vπ(s)V(s,θ))θV(s,θ)]\nabla_\theta J(\theta) =-E[2(V_π(s)-V(s,\theta))\nabla_\theta V(s,\theta)]
    沿着梯度负方向,更新θ\theta
    θ=θ12αθJ(s,θ)\theta=\theta-{1\over 2}\alpha \nabla_\theta J(s,\theta)
    θ=θ+αE[(Vπ(s)V(s,θ))θV(s,θ)]\theta=\theta+\alpha E[(V_π(s)-V(s,\theta))\nabla_\theta V(s,\theta)]
    但是期望EE需要知道状态ss的概率分布才能计算,而在强化学习中,这个分布是不知道呢,只能通过采样数据,进行替代,就变成了随机梯度下降,通过大量的采样进行梯度下降,最终可以收敛到局部最优。因此,实际应用时,是采用随机梯度下降。θ=θ+α(Vπ(s)V(s,θ))θV(s,θ)\theta=\theta+\alpha (V_π(s)-V(s,\theta))\nabla_\theta V(s,\theta)

    价值函数近似增量求解算法

    采用随机梯度下降,θ=θ+α(Vπ(s)V(s,θ))θV(s,θ)\theta=\theta+\alpha (V_π(s)-V(s,\theta))\nabla_\theta V(s,\theta)
    这里,把Vπ(s)V_π(s)当成是已知的,才能用随机梯度下降,进行更新迭代,然而实际真实Vπ(s)V_π(s)是不知道的,只有样本的奖励值是知道,因此采用样本的奖励值代替真实的Vπ(s)V_π(s)
    1.MC算法
    Vπ(s)V_π(s)GtG_t代替,
    θ=θ+α(Gt(s)V(s,θ))θV(s,θ)\theta=\theta+\alpha (G_t(s)-V(s,\theta))\nabla_\theta V(s,\theta)
    2.TD(0)
    Vπ(st)V_π(s_t)Rt+1+γV(st+1,a,θ)R_{t+1}+\gamma V(s_{t+1},a,\theta)代替,
    θ=θ+α(Rt+1+γV(st+1,a,θ)V(s,θ))θV(s,θ)\theta=\theta+\alpha (R_{t+1}+\gamma V(s_{t+1},a,\theta)-V(s,\theta))\nabla_\theta V(s,\theta)
    3.TD(λ\lambda)
    Vπ(st)V_π(s_t)Gt(λ)G_t^{(\lambda)}代替,
    θ=θ+α(Gt(λ)V(s,θ))θV(s,θ)\theta=\theta+\alpha (G_t^{(\lambda)}-V(s,\theta))\nabla_\theta V(s,\theta)

    训练求解

    通过agent与环境进行交互,采样得到一系列的样本,<s1G1>,<s2G2><s1G2>...<s_1,G_1>,<s_2,G_2><s_1,G_2>...就可以通过监督这个学习方法,继续迭代训练,得到最终要的参数θ\theta
    同样对于Q(s,a,θ)Q(s,a,\theta)也是这个套路。

    参考

    https://zhuanlan.zhihu.com/p/54189036

    展开全文
  • 【强化学习纲要】4 价值函数近似4.1 价值函数近似基本原理4.1.1 Introduction: Scaling up RL4.2 价值函数近似for prediction4.3 价值函数近似for control4.4 Deep Q networks 周博磊《强化学习纲要》 学习笔记 课程...

    周博磊《强化学习纲要》
    学习笔记
    课程资料参见:https://github.com/zhoubolei/introRL.
    教材:Sutton and Barton
    Reinforcement Learning: An Introduction

    4.1 价值函数近似基本原理

    4.1.1 Introduction: Scaling up RL

    之前我们遇到的都是状态很少的小规模问题,然后实际生活中很多问题都是大规模问题,如象棋(104710^{47}states),围棋(1017010^{170}states),那么怎么用model-free的方法去估计和控制这些大规模问题的价值函数呢?

    • 用查表的方式展现
      • Q table,横轴是所有状态,纵轴是所有的action,通过查表,我们找到某列最大值的action是需要采取的action。但是如果状态非常多,table会非常大。
      • 挑战:状态或者action太多;很难单独学习每个状态
    • 怎样避免用一个table表征每个状态的模式?
      • reward function or dynamics function
      • value function, state-action function
      • policy function
        都是需要表示每一个状态的。
    • 解决方案:用函数近似的方法估计
      在这里插入图片描述
      给定一个价值函数,我们可以用带参数的近似函数去近似它,如式子中用ww来拟合真实的价值函数。
    • 好处:可以把见到的状态泛化到没有见到的状态,如果状态非常多,我们采样的状态是非常有限的。因此我们引入一个近似函数,通过插值的方法,把中间没有见到的函数估计出来。
    • 用MC或TD learning的方法近似估计参数ww

    价值函数的类别

    在这里插入图片描述
    类别1:输入是一种状态,输出是价值函数的值
    类别2:对于q函数,将state和action作为输入,然后输出是给定状态和action的价值是多少
    类别3:对于q函数,输入是状态,输出是对于所有哦action可能的q值,然后再输出后取argmax,就可以把最可能的action选出来

    函数估计

    多种表示形式:

    1. Linear combinations of features。把特征用线性的形式叠加出来。
    2. 神经网络。
    3. 决策树
    4. Nearest neighbors
      主要使用前两类,因为是可微分的,我们可以很方便的优化近似函数里面的参数。

    4.1.2 梯度下降法

    在这里插入图片描述

    • 有一个objective function J(w)J(w),怎样优化参数ww能够极小化J(w)J(w)
    • 定义 J(w)J(w)关于参数ww的梯度:
      在这里插入图片描述
    • Adjust ww in the direction of the negative gradient, α\alpha是step-size(步长),得到极小值
      在这里插入图片描述

    Value Function Approximation with an Oracle

    价值函数估计的时候也是用的梯度下降法。如果已知每个状态,应该如何优化价值函数?

    • Oracle真值函数,假设我们知道真实的价值函数vπ(s)v^{\pi}(s)是多少,就可以去拟合逼近它。
    • 因此可以把J(w)J(w)写成通过优化ww可以使得mean squared error极小化。
      在这里插入图片描述
    • 直接计算gradient,通过gradient descend可以迅速迭代然后找到可以极小化对应客观函数的ww
      在这里插入图片描述

    用特征向量描述状态

    在这里插入图片描述
    比如:

    • Mountain Car
      特征:车的位置,和速度
    • Cart Pole
      特征:位置,速度,木杆的角度,旋转的角度
    • AlphaGo
      特征:棋子位置,…每一个特征都是19*19的feature map,48个feature map叠加起来作为alphago的输入特征,传给价值函数
      在这里插入图片描述

    4.1.3 线性价值函数近似

    • 用特征的线性叠加表示价值函数
      在这里插入图片描述
      状态转化成特征向量x(s)x(s),参数为ww
    • 优化objective function,使得线性加和的函数和真实的函数尽量的接近,mean square loss尽量的小
      在这里插入图片描述
    • 取一个gradient
      在这里插入图片描述
      Update = StepSize × PredictionError × FeatureValue
      这个形式只有线性模型近似价值函数的时候才有
    • Stochastic gradient descent(随机梯度下降SGD)可以达到一个global optimum(全局优化)的值,因为是线性的,得到的local optimum(局部优化)接近global optimum(全局优化)。因此可以找到一个最佳的拟合价值函数vπ(s)v^{\pi}(s)的模型。

    Linear Value Function Approximation with Table Lookup Feature

    • Table lookup feature是one-hot vector。
      在这里插入图片描述
      向量基本上都是0,只有一个元素是1,当前状态等于某一个状态,对应的那个元素会变成1,除了那个状态其他都是0.

    • one-hot vector用线性模型来表示
      在这里插入图片描述
      参数向量w1w_1wnw_n乘以状态state的feature

    • 由于是one-hot vector,可以得到拟合价值函数就等于当前对应于某个位置的wkw_k;因此现在优化的就是去估计wkw_k
      在这里插入图片描述

    4.2 价值函数近似for prediction

    • 实际上,如果没有oracle(真值函数)如何去拟合价值函数呢?
    • 回顾model-free prediction
      • 给定一个policy,估计每个状态它的价值是多少。
      • 使用MC或TD的方法来优化价值函数
    • 可以再model-free的过程中,把函数近似放到loop里面去,同时进行优化:一边优化价值函数,一边利用优化好的价值函数优化价值函数的近似。

    4.2.1 Incremental VFA(价值函数近似) Prediction Algorithms

    • 假设我们有真值vπ(s)v^{\pi}(s)的话,可以计算gradient:
      在这里插入图片描述
    • 但是实际情况是并没有真值,并没有oracle,只有reward
    • 因此我们直接用target来替代真值
      • 对于MC,用GtG_t去替代
        在这里插入图片描述
      • 对于TD(0),用TD target来替代,由两部分组成:实际走完这一步的reward;bootstrapping估计得到下一个状态的近似价值函数
        在这里插入图片描述

    4.2.2 Monte-Carlo Prediction with VFA

    • 因为MC是采样得到的,因此GtG_tunbiased无偏值的,但是对于真值是noisy sample
    • unbiased的意思是:取GtG_t的期望是可以直接等于真值的,是noisy的,要采样很多次。
      在这里插入图片描述
    • 因此可以通过MC的方法得到很多状态,每一个状态得到对应的return,这样就得到很多的training pair
      在这里插入图片描述
    • 得到training pair后,使用类似于监督的方法产生gradient;如果是线性的话,可以提出特征x(st)x(s_t)
      在这里插入图片描述
    • 利用MC产生的gradient可以对价值函数估计参数进行优化,这样就可以得到一个近似的价值函数。

    4.2.3 TD Prediction with VFA

    • TD target是biased偏置
      在这里插入图片描述
    • 因为如果取target的期望的话是不等于vπ(st)v^{\pi}(s_t)的,因为TD target是包含了正在优化的参数ww
      在这里插入图片描述
    • 也可以产生一些training pair
      在这里插入图片描述
    • 同样放入gradient里面
      在这里插入图片描述
      也叫做semi-gradient,不是真实的gradient,因为它包含优化的参数ww,不同的时刻ww不同所以gradient不一定很准。
    • TD(0)如果采取的是线性特征x(s)x(s),得到的是全局最优解。

    4.3 价值函数近似for control

    通过Generalized policy iteration达到
    在这里插入图片描述

    • Policy evaluation:approximate近似 policy evaluation,将q table用一个带参数ww的函数来近似
      在这里插入图片描述
    • Policy improvement:采用ϵ\epsilon-greedy 改进算法

    4.3.1 Action-Value Function Approximation

    • 用一个函数去拟合价值函数
      在这里插入图片描述
    • 假设是知道ture action-value(oracle) qπ(s,a)q^{\pi}(s,a)的,因此可以比较容易的写出objective function
      在这里插入图片描述
    • 写出gradient,可以优化找到local minimum
      在这里插入图片描述

    Linear Action-Value Function Approximation

    • 定义特征,给定状态和行为,定义一些对应的特征向量,来刻画状态是怎么被描述的
      在这里插入图片描述
    • 用线性拟合,定义好特征以后直接可以加和,元素的强度wjw_j是我们需要学习的参数
      在这里插入图片描述
    • 这样我们就可以用gradient descent写出来
      在这里插入图片描述
      gradient等于step-size乘以估计的差异乘以特征向量

    4.3.2 Incremental Control Algorithm

    实际上,这里没有oracle,因此

    • 用MC的return GtG_t去替代oracle
      在这里插入图片描述
    • 对于Sarsa,可以用Sarsa TD target去替代oracle
      在这里插入图片描述
    • 对于Q-learning,用Q-learning TD target去替代oracle,与Sarsa不同的是TD target是取一个max,估计q函数的近似并对应下一步的状态st+1s_{t+1}并取对应得a(action这个值)最大得值作为target一部分
      在这里插入图片描述

    这样就可以得到gradient,然后用这个gradient去更新q函数近似函数的参数。

    Semi-gradient Sarsa for VFA Control

    在这里插入图片描述
    开始的时候初始化需要优化的ww;如果是结束状态的话就用return;如果不是结束状态的话就往前走一步,采样出A’,构造出它的TD target作为oracle,然后算出它的gradient;每往前走一步更新一次ww;S和A都更新。

    4.3.3 Mountain Car Example

    在这里插入图片描述

    • 目标:控制车能够到达🚩的位置
      • 可以控制的:油门,油门的前后,以及不踩油门
    • 定义状态,state feature actor描述状态特征
      • 把2D平面画格子,看当前位置,落在哪个格子就用哪个格子的index来作为它的特征来描述它
        在这里插入图片描述
    • 构造出特征后,q函数的近似:
      在这里插入图片描述
      用线性函数近似它,把构造的特征weightTweight^T 求和。
    • 可视化q函数的变化
      拟合形式:cost-to-go function
      在这里插入图片描述
      得到拟合的q函数后,在每一个action取最大值表示出来。
      随着training的过程,episode越来越多,会得到一个螺旋上升的形状。表示在某一个位置(position)以及velocity,action最大的值是多少。
      在这里插入图片描述
      学到q函数后,可以进行插值把形状表示出来。
    • 代码:(如何构造特征函数,以及怎么把特征函数放到q-learning里面的)
      https://github.com/cuhkrlcourse/RLexample/blob/master/modelfree/q_learning_mountaincar.py

    Convergence收敛的问题

    • 对于Sarsa和Q-learning这两种gradient:
      • Sarsa:
        在这里插入图片描述
      • Q-learning:
        在这里插入图片描述
    • TD这个方法如果是有VFA(价值函数估计)的话,它的gradient是不正确的,因为它的gradient本身包含了ww
    • 并且update包含了两个近似过程:Bellman backup和underlying value function。两个近似都会引入很多的噪声。
    • 因此TD方法用off-policy或者用non-linear function approximation拟合的时候,优化过程不是很稳定,这也是强化学习为什么不稳定容易crash,相对于监督学习非常不稳地,因为它并没有一个值可以收敛。
    • Off-policy control的挑战:behavior policy(采集数据的策略)和target policy(实际优化的策略)并不相同,导致价值函数估计也非常不准确。

    The Deadly Triad(死亡三角) for the Danger of Instability and Divergence

    潜在不确定因素:

    1. Function approximation:当利用一个函数来近似价值函数或者q函数时,因为用了近似,就会引入误差,这样就会导致很多问题。
    2. Bootstrapping:TD方法采取bootstrapping,基于之前的估计来估计当前的函数,这样也是引入了噪声,有时会使网络over confident;MC方法相对于TD方法好一些,因为MC使用的实际的return,且是unbiased,期望总是等于真值。
    3. Off-policy training:采集的data是用behavior policy采集的,但是优化的函数又是用的另一个函数,引入了不确定因素。
      这也是前言研究想要克服的问题。

    控制算法的收敛性问题

    在这里插入图片描述

    • MDP是小规模的,状态有限的时候,用Lookup table来表示它,对于MC,Sarsa,Q-learning都是可以找到一个最优解的;
    • 如果MDP是比较大规模的,采取的方法是线性特征拟合的话,MC和Sarsa是可以找到一个近似最优解的价值函数,Q-learning不行;
    • 如果选取的是非线性函数近似,比如神经网络,这三种算法都很难保证最后得到的解是最优解。

    4.3.4 Batch Reinforcement Learning

    • 前面的算法都是单步的强化学习算法,但实际的优化过程中,单步的incremental gradient descent是效率很低的。
    • 因此有了Batch的方法,有了training batch,直接优化整个batch里面所有样本,使得函数可以拟合。

    Least Square Prediction

    • 假设有一个数据库(experience DD)里面包含了采集到的pair <s1,v1π><s_1,{v_1}^{\pi}> ,value可以用return或者TD target来替换
      在这里插入图片描述
    • 目标:优化ww来拟合整个采集到的数据DD,使得在这个数据库里面每个pair都极小化。
    • 实际是想得到ww^*这样极小化的值
      在这里插入图片描述
      得到一个ww^*使得可以在数据集DD上面mean square loss极小化

    Stochastic Gradient Descent(采样) with Experience Replay

    • 如果DD集合非常大的话,数据没法全部放进来,因此可以采用采样的办法。
      在这里插入图片描述
    • 一个Batch包含10个或者20个样本,这些样本是从pair中随机采样如20个样本
      在这里插入图片描述
    • 可以把这20个样本的gradient算出来,用gradient优化函数
      在这里插入图片描述
      然后重复,随机采样,优化…
    • 通过这个迭代的办法,最后可以收敛到mean square solution
      在这里插入图片描述
      通过迭代的方法得到的ww和直接一步优化得到的ww是一样的。

    4.4 Deep Q networks

    如何用非线性函数来拟合价值函数?

    线性价值函数拟合

    • 先定义好特征函数,当给定状态的时候用x(s)x(s)这个函数可以提取出对应的特征,然后把线性价值叠加来估计vv值。
      在这里插入图片描述
    • Objection function
      在这里插入图片描述
    • 梯度
      在这里插入图片描述
    • 不同的MC或TD方法可以把真值vπ(s)v^{\pi}(s)替换
      • MC,用sample return作为target
        在这里插入图片描述
      • TD,用one- step的奖励和bootstrap的vv值作为target算它的梯度进行优化
        在这里插入图片描述

    线性vs非线性价值函数拟合

    • 线性价值函数拟合需要人为设计好的特征,但是这是非常困难的一件事情。
    • 用非线性价值函数拟合,可以把特征提取和价值函数学习结合起来。
    • 神经网络是非常常用的方法。

    4.4.1 Deep Neural Networks

    在这里插入图片描述

    • Multiple layers of linear functions, with non-linear operators between layers
      在这里插入图片描述
    • 优化神经网络参数的时候,用的chain rule(链式法则)的方法backpropagate(反向传播)将梯度传回,将每一个参数都进行优化。
      在这里插入图片描述

    卷积神经网络

    在这里插入图片描述

    4.4.2 Deep Reinforcement Learning

    深度学习和强化学习的结合。

    • 用神经网络来拟合强化学习的各个参数,如:
      • 价值函数(value function)
      • 策略函数(policy function)
      • 环境模型(world model)
    • 损失函数常用stochastic gradient descent(sGD随机梯度下降)来进行优化
    • 挑战:
      • 有很多模型参数要优化
      • “死亡三角”
        • 非线性拟合
        • Bootstrapping
        • Off-policy training

    4.4.3 Deep Q-Networks(DQN)

    • 2015年DeepMind提出的网络结构,发表到Nature的论文:Human-level control through deep reinforcement learning
    • 用神经网络来拟合Q 函数
    • 在Atari游戏有很好的效果
      在这里插入图片描述
      4 Atari Games: Breakout, Pong, Montezuma’s Revenge, Private Eye

    回顾:Action-Value Function Approximation

    • 参数ww,拟合q函数
      在这里插入图片描述
    • 构造出MSE(mean-square error)去优化,使得函数可以近似q函数
      在这里插入图片描述
    • 用sGD(随机梯度下降法)优化找到局部最优值
      在这里插入图片描述

    回顾:Incremental Control Algorithm

    在这里插入图片描述

    DQN for Playing Atari Games

    • 用神经网络来拟合q函数;
    • 游戏页面连续的4帧的pixel作为输入;
    • 输出是18个操作
    • 奖励是游戏的增减分数
      在这里插入图片描述

    Q-learning with Value Function Approximation

    • 两个要克服的问题
      • 样本之间的相关性(correlation)。在强化学习里面收集的数据是一个时序的玩游戏的序列,如果是在像素级别,关联性是很高的,因为很可能只有很小的一部分有变化,其他都很类似。所以不同时序之间的correlation是非常高的,这样就使得学习非常困难。
      • Non-stationary targets。因为target里面已经自带了模型的参数,使得训练变得困难。
    • Deep Q-learning用了两种方法克服:
      • 针对第一个问题,采用Experience replay的方法。
      • 针对第二个问题,采用Fixed Q targets的方法。使得TD target在构建的时候,用第二个网络来构建,另外还有一个学习的网络,这样就有两个网络,就会有一些时间差。

    4.4.4 DQNs: Experience Replay(经验回放)

    • 采用一个容器(container)作为一个replay memory DD,在replay memory里面存了很多不同环节得到的sample。
      在这里插入图片描述
      每一个格子存的sample叫做transition tuple,包含四个变量(st,at,rt,st+1)(s_t,a_t,r_t,s_{t+1}),分别是当前的位置(状态)、采取的某个行为、得到的奖励、下一个状态。把每一个tuple打散存在replay memory里面。
    • 在做experience replay(经验回放),在训练的过程中:
      • 有一个网络一直在玩游戏,采集新的tuple,然后把tuple放到容器里面;另一方面,为了训练这个网络,有一个采样的过程,如在replay buffer里面进行随机的采样,因此每次采集到的sample都有可能是在不同的episode里面出现的。
        在这里插入图片描述
      • 这样就得到了相关度比较低的tuple后,构建q-learning的target
        在这里插入图片描述
      • 有了TD target以后,就可以构造出q函数拟合函数的Δw
        在这里插入图片描述

    4.4.5 DQNs: Fixed Targets

    • 为了提高稳定性,target网络有确定的weights,或者target network和实际优化的网络之间存在一定时间差。
    • target里面的权重用ww^-来表征,ww则用来更新。
    • 产生target的过程
      • 先从replay buffer里面采集一些transition tuple,相关度较低
        在这里插入图片描述
      • 然后target network用ww^-来产生
        在这里插入图片描述
      • 然后进行优化,得到Δw
        在这里插入图片描述
        ww^-ww有一定的时间差,在很多时候都是不同的,ww^-更新的要慢一些,这就使得TD target和实际的不同。

    Why fixed target

    • 例子:想要优化一个网络使得它能够更好的估计出它的q target。猫是q优化的过程,猫要能够追上(预测)到q target(老鼠)
    • 开始的时候猫可能离老鼠很远,但是猫追老鼠的同时老鼠也在动,因为q target与模型是相关的,在每次优化后,随着网络的更新,q target也会改变。
      在这里插入图片描述
    • 导致猫和老鼠都在动,在优化空间里面乱动
      在这里插入图片描述
    • 这样就会产生非常奇怪的优化轨迹,相当于使得整个训练过程非常不稳定
      在这里插入图片描述
    • 因此修复这个问题的方法是可以固定target,让老鼠动的不是那么频繁,如让它每5步动一次,这样猫就有足够的时间去接近target,逐渐距离会越来越小,这样就可以最终拟合得到最好的q network。这就是为什么需要fixed target。

    DQNs在Atari上的结果
    在这里插入图片描述
    Abalation Study on DQNs

    在这里插入图片描述

    4.4.6 Demo of DQNs

    Code of DQN in PyTorch:

    Imports

    import gym
    from gym import wrappers
    
    import torch
    import torch.nn as nn
    import torch.optim as optim
    import torch.nn.functional as F
    
    import numpy as np
    
    from IPython.display import clear_output
    from matplotlib import pyplot as plt
    %matplotlib inline
    
    import random
    from timeit import default_timer as timer
    from datetime import timedelta
    import math
    from utils.wrappers import make_atari, wrap_deepmind, wrap_pytorch
    
    from utils.hyperparameters import Config
    from agents.BaseAgent import BaseAgent
    

    Hyperparameters

    config = Config()
    
    config.device = torch.device("cuda" if torch.cuda.is_available() else "cpu")
    
    #epsilon variables
    config.epsilon_start = 1.0
    config.epsilon_final = 0.01
    config.epsilon_decay = 30000
    config.epsilon_by_frame = lambda frame_idx: config.epsilon_final + (config.epsilon_start - config.epsilon_final) * math.exp(-1. * frame_idx / config.epsilon_decay)
    
    #misc agent variables
    config.GAMMA=0.99
    config.LR=1e-4
    
    #memory
    config.TARGET_NET_UPDATE_FREQ = 1000
    config.EXP_REPLAY_SIZE = 100000
    config.BATCH_SIZE = 32
    
    #Learning control variables
    config.LEARN_START = 10000
    config.MAX_FRAMES=1000000
    

    Replay Memory

    class ExperienceReplayMemory:
        def __init__(self, capacity):
            self.capacity = capacity
            self.memory = []
    
        def push(self, transition):
            self.memory.append(transition)
            if len(self.memory) > self.capacity:
                del self.memory[0]
    
        def sample(self, batch_size):
            return random.sample(self.memory, batch_size)
    
        def __len__(self):
            return len(self.memory)
    

    Network Declaration

    class DQN(nn.Module):
        def __init__(self, input_shape, num_actions):
            super(DQN, self).__init__()
            
            self.input_shape = input_shape
            self.num_actions = num_actions
    
            self.conv1 = nn.Conv2d(self.input_shape[0], 32, kernel_size=8, stride=4)
            self.conv2 = nn.Conv2d(32, 64, kernel_size=4, stride=2)
            self.conv3 = nn.Conv2d(64, 64, kernel_size=3, stride=1)
    
            self.fc1 = nn.Linear(self.feature_size(), 512)
            #输出action
            self.fc2 = nn.Linear(512, self.num_actions)
            
        def forward(self, x):
            x = F.relu(self.conv1(x))
            x = F.relu(self.conv2(x))
            x = F.relu(self.conv3(x))
            x = x.view(x.size(0), -1)
            x = F.relu(self.fc1(x))
            x = self.fc2(x)
    
            return x
        
        def feature_size(self):
            return self.conv3(self.conv2(self.conv1(torch.zeros(1, *self.input_shape)))).view(1, -1).size(1)
    

    Agent

    class Model(BaseAgent):
        def __init__(self, static_policy=False, env=None, config=None):
            super(Model, self).__init__()
            self.device = config.device
    
            self.gamma = config.GAMMA
            self.lr = config.LR
            self.target_net_update_freq = config.TARGET_NET_UPDATE_FREQ
            self.experience_replay_size = config.EXP_REPLAY_SIZE
            self.batch_size = config.BATCH_SIZE
            self.learn_start = config.LEARN_START
    
            self.static_policy = static_policy
            self.num_feats = env.observation_space.shape
            self.num_actions = env.action_space.n
            self.env = env
    
            self.declare_networks()
            #构造target model  
            self.target_model.load_state_dict(self.model.state_dict())
            self.optimizer = optim.Adam(self.model.parameters(), lr=self.lr)
            
            #move to correct device
            #原来的model
            self.model = self.model.to(self.device)
            #target model
            self.target_model.to(self.device)
    
            if self.static_policy:
                self.model.eval()
                self.target_model.eval()
            else:
                self.model.train()
                self.target_model.train()
    
            self.update_count = 0
    
            self.declare_memory()
            
    
        def declare_networks(self):
            self.model = DQN(self.num_feats, self.num_actions)
            self.target_model = DQN(self.num_feats, self.num_actions)
    
        def declare_memory(self):
            self.memory = ExperienceReplayMemory(self.experience_replay_size)
    
        def append_to_replay(self, s, a, r, s_):
            self.memory.push((s, a, r, s_))
    
    
        def prep_minibatch(self):
            # random transition batch is taken from experience replay memory
            transitions = self.memory.sample(self.batch_size)
            
            batch_state, batch_action, batch_reward, batch_next_state = zip(*transitions)
    
            shape = (-1,)+self.num_feats
    
            batch_state = torch.tensor(batch_state, device=self.device, dtype=torch.float).view(shape)
            batch_action = torch.tensor(batch_action, device=self.device, dtype=torch.long).squeeze().view(-1, 1)
            batch_reward = torch.tensor(batch_reward, device=self.device, dtype=torch.float).squeeze().view(-1, 1)
            
            non_final_mask = torch.tensor(tuple(map(lambda s: s is not None, batch_next_state)), device=self.device, dtype=torch.uint8)
            try: #sometimes all next states are false
                non_final_next_states = torch.tensor([s for s in batch_next_state if s is not None], device=self.sdevice, dtype=torch.float).view(shape)
                empty_next_state_values = False
            except:
                non_final_next_states = None
                empty_next_state_values = True
    
            return batch_state, batch_action, batch_reward, non_final_next_states, non_final_mask, empty_next_state_values
    
        def compute_loss(self, batch_vars):
            batch_state, batch_action, batch_reward, non_final_next_states, non_final_mask, empty_next_state_values = batch_vars
    
            #estimate
            current_q_values = self.model(batch_state).gather(1, batch_action)
            
            #产生target的过程
            with torch.no_grad():
            #构造 max_next_q_values
                max_next_q_values = torch.zeros(self.batch_size, device=self.device, dtype=torch.float).unsqueeze(dim=1)
                if not empty_next_state_values:
                    max_next_action = self.get_max_next_state_action(non_final_next_states)
                    #构造max_next_q_values的时候是使用target network,
                    #把上一帧的状态放到target network里面,然后取max action
                    max_next_q_values[non_final_mask] = self.target_model(non_final_next_states).gather(1, max_next_action)
                    
                expected_q_values = batch_reward + (self.gamma*max_next_q_values)
    
    		#loss
            diff = (expected_q_values - current_q_values)
            loss = self.huber(diff)
            loss = loss.mean()
    
            return loss
    
        def update(self, s, a, r, s_, frame=0):
            if self.static_policy:
                return None
    
            self.append_to_replay(s, a, r, s_)
    
            if frame < self.learn_start:
                return None
    
            batch_vars = self.prep_minibatch()
    
            loss = self.compute_loss(batch_vars)
    
            # Optimize the model
            self.optimizer.zero_grad()
            loss.backward()
            for param in self.model.parameters():
                param.grad.data.clamp_(-1, 1)
            self.optimizer.step()
    
    		#每个一段时间更新一次target model,把优化的model copy到target里面来,
    		#这样开始两个network就一致,然后又让target network慢一些再更新一下
            self.update_target_model()
            self.save_loss(loss.item())
            self.save_sigma_param_magnitudes()
    
    
        def get_action(self, s, eps=0.1):
            with torch.no_grad():
                if np.random.random() >= eps or self.static_policy:
                    X = torch.tensor([s], device=self.device, dtype=torch.float)
                    a = self.model(X).max(1)[1].view(1, 1)
                    return a.item()
                else:
                    return np.random.randint(0, self.num_actions)
    
        def update_target_model(self):
            self.update_count+=1
            self.update_count = self.update_count % self.target_net_update_freq
            if self.update_count == 0:
                self.target_model.load_state_dict(self.model.state_dict())
    
        def get_max_next_state_action(self, next_states):
            return self.target_model(next_states).max(dim=1)[1].view(-1, 1)
    
        def huber(self, x):
            cond = (x.abs() < 1.0).to(torch.float)
            return 0.5 * x.pow(2) * cond + (x.abs() - 0.5) * (1 - cond)
    

    Plot Results

    def plot(frame_idx, rewards, losses, sigma, elapsed_time):
        clear_output(True)
        plt.figure(figsize=(20,5))
        plt.subplot(131)
        plt.title('frame %s. reward: %s. time: %s' % (frame_idx, np.mean(rewards[-10:]), elapsed_time))
        plt.plot(rewards)
        if losses:
            plt.subplot(132)
            plt.title('loss')
            plt.plot(losses)
        if sigma:
            plt.subplot(133)
            plt.title('noisy param magnitude')
            plt.plot(sigma)
        plt.show()
    

    Training Loop

    start=timer()
    
    env_id = "PongNoFrameskip-v4"
    env    = make_atari(env_id)
    env    = wrap_deepmind(env, frame_stack=False)
    env    = wrap_pytorch(env)
    model = Model(env=env, config=config)
    
    episode_reward = 0
    
    observation = env.reset()
    for frame_idx in range(1, config.MAX_FRAMES + 1):
        epsilon = config.epsilon_by_frame(frame_idx)
    
        action = model.get_action(observation, epsilon)
        prev_observation=observation
        observation, reward, done, _ = env.step(action)
        observation = None if done else observation
    
        model.update(prev_observation, action, reward, observation, frame_idx)
        episode_reward += reward
    
        if done:
            observation = env.reset()
            model.save_reward(episode_reward)
            episode_reward = 0
            
            if np.mean(model.rewards[-10:]) > 19:
                plot(frame_idx, model.rewards, model.losses, model.sigma_parameter_mag, timedelta(seconds=int(timer()-start)))
                break
    
        if frame_idx % 10000 == 0:
            plot(frame_idx, model.rewards, model.losses, model.sigma_parameter_mag, timedelta(seconds=int(timer()-start)))
    
    model.save_w()
    env.close()
    

    DQNs总结

    • DQN uses experience replay and fixed Q-targets
    • Store transition (st,at,rt+1,st+1)(s_t ,a_ t ,r_{t+1} ,s_{t+1}) in replay memory D
    • Sample random mini-batch of transitions (s,a,r,s)(s,a,r,s') from D
    • Compute Q-learning targets w.r.t. old, fixed parameters ww^−
    • Optimizes MSE between Q-network and Q-learning targets using stochastic gradient descent

    改进DQN

    • Double DQN: Deep Reinforcement Learning with Double Q-Learning.Van Hasselt et al, AAAI 2016
    • Dueling DQN: Dueling Network Architectures for Deep Reinforcement Learning. Wang et al, best paper ICML 2016
    • Prioritized Replay: Prioritized Experience Replay. Schaul et al, ICLR 2016
    • 技术实现:
      https://github.com/cuhkrlcourse/DeepRL-Tutorials

    March 31, 2020: Agent57
    五年内的改进集合
    https://deepmind.com/blog/article/Agent57-Outperforming-the-human-Atari-benchmark
    在这里插入图片描述

    Optional Homework

    展开全文
  • 强化学习&基础1.9 | 动作价值函数

    千次阅读 2019-04-15 10:38:08
    价值函数的基础之上,动作价值函数是在状态S下选择动作a然后遵循这个策略的值,下图左边的定义是价值函数,右边是动作价值函数。 在动作价值函数的基础上,原来每个格子的值需要考虑动作的行为(上下左右),这样...

    在价值函数的基础之上,动作价值函数是在状态S下选择动作a然后遵循这个策略的值,下图左边的定义是价值函数,右边是动作价值函数。
    在这里插入图片描述
    在动作价值函数的基础上,原来每个格子的值需要考虑动作的行为(上下左右),这样格子的值被分为4块
    在这里插入图片描述

    下图是计算动作价值函数的过程,从第一列第二行格子方开始沿着红色路线采取动作最终达到终点,可得到在这个格子下采取向上动作的value为1
    在这里插入图片描述
    计算所有可以得到动作状态值
    在这里插入图片描述
    其中在最优策略下,最优动作价值函数用q*表示。
    在这里插入图片描述
    那么,通过和环境交互后,已知最优动作价值函数的情况下,如何知道最优策略呢?只要取得每个格子的最大动作价值函数就可以了,在最左边第二行三个1的情况下,采取哪一个动作都会产生最优策略。
    在这里插入图片描述
    如何得到最优动作价值函数是接下来的问题。

    展开全文
  • 价值函数的近似表示近似价值函数 Value Function Approximation递增方法(Incremental Methods)梯度下降预测--递增算法MC应用于状态价值函数近似TD应用于状态价值函数近似TD(λ)应用于状态价值函数近似控制--递增算法...

    之前的内容都是讲解一些强化学习的基础理论,这些知识只能解决一些中小规模的问题,很多价值函数需要用一张大表来存储,获取某一状态或行为价值的时候通常需要一个查表操作(Table Lookup),这对于那些状态空间或行为空间很大的问题几乎无法求解,而许多实际问题都是这些拥有大量状态和行为空间的问题,本讲开始的内容就主要针对如何解决实际问题。
    本讲主要解决各种价值函数的近似表示和学习,在实际应用中,对于状态和行为空间都比较大的情况下,精确获得各种v(S)和q(s,a)几乎是不可能的。这时候需要找到近似的函数,具体可以使用线性组合、神经网络以及其他方法来近似价值函数:
    v(S)v(S,w) v ( S ) \approx v ( S , w )
    ww是引入的参数,通常是一个矩阵或至少是一个向量。
    通过函数近似,可以用少量的参数w来拟合实际的各种价值函数。各种近似方法分为两大类,一类是“递增方法”,针对每一步,近似函数得到一些信息,立即优化近似函数,主要用于在线学习;另一类是“批方法”,针对一批历史数据集中进行近似。两类方法没有明显的界限,相互借鉴。

    近似价值函数 Value Function Approximation

    到目前为止,我们使用的是查表(Table Lookup)的方式,这意味着每一个状态或者每一个状态行为对对应一个价值数据。对于大规模问题,这么做需要太多的内存来存储,而且有的时候针对每一个状态学习得到价值也是一个很慢的过程。
    对于大规模问题,解决思路可以是这样的:

    1. 通过函数近似来估计实际的价值函数:
      V^(s,w)vπ(s)q^(s,a,w)qπ(s,a) \begin{array} { c } \hat { V } ( \boldsymbol { s } , \mathbf { w } ) \approx v _ { \pi } ( s ) \\ \hat { q } ( s , a , \mathbf { w } ) \approx q _ { \pi } ( s , a ) \end{array}
    2. 把从已知的状态学到的函数通用化推广至那些未碰到的状态中。
    3. 使用MC或TD学习来更新函数参数。

    针对强化学习,近似函数根据输入和输出的不同,可以有以下三种架构:
    在这里插入图片描述

    1. 针对状态本身,输出这个状态的近似价值;
    2. 针对状态行为对,输出状态行为对的近似价值;
    3. 针对状态本身,输出一个向量,向量中的每一个元素是该状态下采取一种可能行为的价值。

    所有和机器学习相关的一些算法都可以应用到强化学习中来,其中线性回归和神经网络在强化学习里应用得比较广泛,主要是考虑这两类方法是一个针对状态可导的近似函数。
    强化学习应用的场景其数据通常是非静态、非独立均匀分布的,因为一个状态数据是可能是持续流入的,而且下一个状态通常与前一个状态是高度相关的。因此,我们需要一个适用于非静态、非独立均匀分布的数据的训练方法来得到近似函数。

    递增方法(Incremental Methods)

    梯度下降

    假定J(w)是一个关于参数w的可微函数,定义J(w)的梯度如下:
    wJ(w)=(J(w)w1J(w)wn) \nabla _ { \mathbf { w } } J ( \mathbf { w } ) = \left( \begin{array} { c } \frac { \partial J ( \mathbf { w } ) } { \partial w _ { 1 } } \\ \vdots \\ \frac { \partial J ( \mathbf { w } ) } { \partial \mathbf { w } _ { n } } \end{array} \right)
    调整参数超朝着负梯度的方向,寻找J(w)的局部最小值:
    Δw=12αwJ(w) \Delta \mathbf { w } = - \frac { 1 } { 2 } \alpha \nabla _ { \mathbf { w } } J ( \mathbf { w } )
    目标:找到参数向量w,最小化近似函数 v^(S,w)\hat{v}(S,w) 与实际函数vπ(s)v_\pi({s}) 的均方差:
    J(w)=Eπ[(vπ(S)v^(S,w))2] J ( \mathbf { w } ) = \mathbb { E } _ { \pi } \left[ \left( v _ { \pi } ( S ) - \hat { v } ( S , \mathbf { w } ) \right) ^ { 2 } \right]
    使用随机梯度下降对梯度进行更新,来近似差的期望
    Δw=α(vπ(S)v^(S,w))wv^(S,w) \Delta \mathbf { w } = \alpha \left( v _ { \pi } ( S ) - \hat { v } ( S , \mathbf { w } ) \right) \nabla _ { \mathbf { w } } \hat { v } ( S , \mathbf { w } )
    即用vπ(s)v_\pi(s)来引导估计的价值函数v^(S,w)\hat{v}(S,w)的优化方向。

    预测–递增算法

    事实上,之前所列的公式都不能直接用于强化学习,因为公式里都有一个实际价值函数vπ(s)v_\pi(s)。或者是一个具体的数值,而强化学习没有监督数据,因此不能直接使用上述公式。强化学习里只有即时奖励,没有监督数据。我们要找到能替代 vπ(s)v_\pi(s) 的目标值,以便来使用监督学习的算法学习到近似函数的参数。
    对于MC算法,目标值就是收获:
    Δw=α(Gtv^(St,w))wv^(St,w) \Delta \mathbf { w } = \alpha \left( G _ { t } - \hat { v } \left( S _ { t } , \mathbf { w } \right) \right) \nabla _ { \mathbf { w } } \hat { v } \left( S _ { t } , \mathbf { w } \right)
    对于TD(0),目标值就是TD目标:
    Δw=α(Rt+1+γv^(St+1,w)v^(St,w))wv^(St,w) \Delta \mathbf { w } = \alpha \left( R _ { t + 1 } + \gamma \hat { v } \left( S _ { t + 1 } , \mathbf { w } \right) - \hat { v } \left( S _ { t } , \mathbf { w } \right) \right) \nabla _ { \mathbf { w } } \hat { v } \left( S _ { t } , \mathbf { w } \right)
    对于TD(λ),目标值是λ收获:
    Δw=α(Gtλv^(St,w))wv^(St,w) \Delta \mathbf { w } = \alpha \left( G _ { t } ^ { \lambda } - \hat { v } \left( S _ { t } , \mathbf { w } \right) \right) \nabla _ { \mathbf { w } } \hat { v } \left( S _ { t } , \mathbf { w } \right)

    MC应用于状态价值函数近似

    收获 GtG_t是真实价值vπ(s)v_\pi(s)的有噪声、无偏采样,可以把它看成是监督学习的标签数据带入机器学习算法进行学习,这样训练数据集可以是:
    S1,G1,S2,G2,,ST,GT \left\langle S _ { 1 } , G _ { 1 } \right\rangle , \left\langle S _ { 2 } , G _ { 2 } \right\rangle , \ldots , \left\langle S _ { T } , G _ { T } \right\rangle
    如果使用线性蒙特卡洛策略迭代,那么每次参数的修正值则为:
    Δw=α(Gtv^(St,w))wv^(St,w)=α(Gtv^(St,w))x(St) \begin{aligned} \Delta \mathbf { w } & = \alpha \left( G _ { t } - \hat { v } \left( S _ { t } , \mathbf { w } \right) \right) \nabla _ { \mathbf { w } } \hat { v } \left( S _ { t } , \mathbf { w } \right) \\ & = \alpha \left( G _ { t } - \hat { v } \left( S _ { t } , \mathbf { w } \right) \right) \mathbf { x } \left( S _ { t } \right) \end{aligned}
    结论:蒙特卡洛策略迭代使用线性函数近似时也是收敛至一个局部最优解。

    TD应用于状态价值函数近似

    TD目标值是真实价值的有噪声、有偏采样。此时的训练数据集是:
    S1,R2+γv^(S2,w),S2,R3+γv^(S3,w),,ST1,RT \left\langle S _ { 1 } , R _ { 2 } + \gamma \hat { v } \left( S _ { 2 } , \mathbf { w } \right) \right\rangle , \left\langle S _ { 2 } , R _ { 3 } + \gamma \hat { v } \left( S _ { 3 } , \mathbf { w } \right) \right\rangle , \dots , \left\langle S _ { T - 1 } , R _ { T } \right\rangle
    例如使用线性近似的TD(0)方法:
    Δw=α(R+γv^(S,w)v^(S,w))wv^(S,w)=αδx(S) \begin{aligned} \Delta \mathbf { w } & = \alpha \left( R + \gamma \hat { v } \left( S ^ { \prime } , \mathbf { w } \right) - \hat { v } ( S , \mathbf { w } ) \right) \nabla _ { \mathbf { w } } \hat { v } ( S , \mathbf { w } ) \\ & = \alpha \delta \mathbf { x } ( S ) \end{aligned}
    结论:线性的TD(0)方法将会收敛到全局最优。
    注:这里梯度只作用于v^(S,w)\hat{v}(S,w)并不作用于v^(S,w)\hat{v}(S',w)按照Silver的解释,如果作用于目标那就有点类似于时光倒流,与现实情况不符。

    TD(λ)应用于状态价值函数近似

    TD(λ)目标值是真实价值的有噪声、有偏采样。此时的训练数据集是:
    S1,G1λ,S2,G2λ,,ST1,GT1λ \left\langle S _ { 1 } , G _ { 1 } ^ { \lambda } \right\rangle , \left\langle S _ { 2 } , G _ { 2 } ^ { \lambda } \right\rangle , \ldots , \left\langle S _ { T - 1 } , G _ { T - 1 } ^ { \lambda } \right\rangle
    如果使用线性TD(λ)学习,从前向认识看,有:
    Δw=α(Gtλv^(St,w))wv^(St,w)=α(Gtλv^(St,w))x(St) \begin{aligned} \Delta \mathbf { w } & = \alpha \left( G _ { t } ^ { \lambda } - \hat { v } \left( S _ { t } , \mathbf { w } \right) \right) \nabla _ { \mathbf { w } } \hat { v } \left( S _ { t } , \mathbf { w } \right) \\ & = \alpha \left( G _ { t } ^ { \lambda } - \hat { v } \left( S _ { t } , \mathbf { w } \right) \right) \mathbf { x } \left( S _ { t } \right) \end{aligned}
    从反向认识看,有:
    δt=Rt+1+γv^(St+1,w)v^(St,w)Et=γλEt1+x(St)Δw=αδtEt \begin{aligned} \delta _ { t } & = R _ { t + 1 } + \gamma \hat { v } \left( S _ { t + 1 } , \mathbf { w } \right) - \hat { v } \left( S _ { t } , \mathbf { w } \right) \\ E _ { t } & = \gamma \lambda E _ { t - 1 } + \mathbf { x } \left( S _ { t } \right) \\ \Delta \mathbf { w } & = \alpha \delta _ { t } E _ { t } \end{aligned}
    对于一个完整的Episode,TD(λ)的前向认识和反向认识对于w的改变是等效的。

    控制–递增算法

    使用强化学习进行不基于模型控制需要两个条件。如何把近似函数引入到控制过程中呢?我们需要能够近似状态行为对的价值函数近似而不是仅针对状态的价值函数近似。
    在这里插入图片描述
    从一系列参数开始,得到一个近似的状态行为对价值函数,在Ɛ-greedy执行策略下产生一个行为,执行该行为得到一个即时奖励,以此数据计算目标值,进行近似函数参数的更新。再应用这个策略得到后续的状态和对应的目标值,每经历一次状态就更新依次参数,如此反复进行策略的优化,同时逼近最优价值函数。

    策略评估:是一个近似策略评估q^(,,w)qπ\hat{q}(·,·,w) \approx q_\pi,特别是早期误差会较大,而且这种近似无法最终收敛于最优策略对应的行为价值函数,只能在其周围震荡,后文将讲述改进方法。
    策略改善:使用Ɛ-greedy执行。

    行为价值函数近似表示为:
    q^(S,A,w)qπ(S,A) \hat { q } ( S , A , \mathbf { w } ) \approx q _ { \pi } ( S , A )
    最小化均方差:
    J(w)=Eπ[(qπ(S,A)q^(S,A,w))2] J ( \mathbf { w } ) = \mathbb { E } _ { \pi } \left[ \left( q _ { \pi } ( S , A ) - \hat { q } ( S , A , \mathbf { w } ) \right) ^ { 2 } \right]
    使用随机梯度下降来寻找局部最优解:
    12wJ(w)=(qπ(S,A)q^(S,A,w))wq^(S,A,w)Δw=α(qπ(S,A)q^(S,A,w))wq^(S,A,w) \begin{array} { c } - \frac { 1 } { 2 } \nabla _ { w } J ( \mathbf { w } ) = \left( q _ { \pi } ( S , A ) - \hat { q } ( S , A , \mathbf { w } ) \right) \nabla _ { w } \hat { q } ( S , A , \mathbf { w } ) \\ \Delta \mathbf { w } = \alpha \left( q _ { \pi } ( S , A ) - \hat { q } ( S , A , \mathbf { w } ) \right) \nabla _ { w } \hat { q } ( S , A , \mathbf { w } ) \end{array}

    收敛性分析

    对于预测问题而言:

    MC使用的是实际价值的有噪声无偏估计,虽然很多时候表现很差,但总能收敛至局部或全局最优解。TD性能通常更加优秀,是否意味着TD也是一直收敛的呢?答案是否定的。原讲义给出了一个TD学习不收敛的例子,这里不再详述,这里给出各种算法在使用不同近似函数进行预测学习时是否收敛的小结:
    在这里插入图片描述
    从表中可以看出,没有函数近似时,各种算法都收敛;线性函数近似时现时策略学习可以收敛,但离线策略时仅有MC收敛;非线性函数近似时无论采用现时策略还是离线策略只有MC收敛。而MC算法在实际中是很少使用的。这给强化学习的实际应用带来的挑战。好在我们有一些改善TD算法的办法。

    对于控制问题而言的收敛性:
    在这里插入图片描述
    针对控制学习算法,大多数都能得到较好的策略,但是理论上只要存在函数近似,就都不是严格收敛的,比较常见的是在最优策略上下震荡,逐渐逼近然后突然来一次发散,再逐渐逼近等。使用非线性函数近似的效果要比近似函数要差很多,实际也是如此。

    批方法 Batch Methods

    前面所说的递增算法都是基于数据流的,经历一步,更新算法后,我们就不再使用这步的数据了,这种算法简单,但有时候不够高效。与之相反,批方法则是把一段时期内的数据集中起来,通过学习来使得参数能较好地符合这段时期内所有的数据。这里的训练数据集“块”相当于个体的一段经验。

    最小二乘法预测

    假设存在一个价值函数的近似:
    v^(s,w)vπ(s) \hat { v } ( s , \mathbf { w } ) \approx v _ { \pi } ( s )
    以及一段时期的、包含<状态、价值>的经历D:
    D={s1,v1π,s2,v2π,,sT,vTπ} \mathcal { D } = \left\{ \left\langle s _ { 1 } , v _ { 1 } ^ { \pi } \right\rangle , \left\langle s _ { 2 } , v _ { 2 } ^ { \pi } \right\rangle , \ldots , \left\langle s _ { T } , v _ { T } ^ { \pi } \right\rangle \right\}
    最小平方差算法要求找到参数w,使得下式值最小:
    LS(w)=t=1T(vtπv^(st,w))2=ED[(vπv^(s,w))2] \begin{aligned} L S ( \mathbf { w } ) & = \sum _ { t = 1 } ^ { T } \left( v _ { t } ^ { \pi } - \hat { v } \left( s _ { t } , \mathbf { w } \right) \right) ^ { 2 } \\ & = \mathbb { E } _ { \mathcal { D } } \left[ \left( v ^ { \pi } - \hat { v } ( s , \mathbf { w } ) \right) ^ { 2 } \right] \end{aligned}
    这就相当于经历重现(Experience Replay),把一段时期内的经历重新过一遍,更新参数。这种算法实现起来不是很难,只要重复:

    1. 从经历中取出一个<s,v>:
      s,vπD \left\langle s , v ^ { \pi } \right\rangle \sim \mathcal { D }
    2. 应用随机梯度下降来更新参数:
      Δw=α(vπv^(s,w))wv^(s,w) \Delta \mathbf { w } = \alpha \left( v ^ { \pi } - \hat { v } ( s , \mathbf { w } ) \right) \nabla _ { w } \hat { v } ( s , \mathbf { w } )
      这将收敛至针对这段经历最小平方差的参数:
      wπ=argminwLS(w) \mathbf { w } ^ { \pi } = \underset { \mathbf { w } } { \operatorname { argmin } } L S ( \mathbf { w } )

    批方法应用于DQN

    先前说过TD方法结合非线性的神经网络函数近似可能不会收敛,但DQN使用experience replay和固定的Q目标值能做到收敛而且保持很好的鲁棒性。在解释其收敛之前先要介绍DQN算法的要点:

    1. 依据ϵgreedy\epsilon-greedy执行策略产生t时刻的行为;
    2. 将大量经历数据(例如百万级的)以(st,at,rt+1,st+1)(s_t,a_t,r_{t+1},s_{t+1})存储在内存里,作为D大块;
    3. 从D大块中随机抽取小块(例如64个样本数据)数据(s,a,r,s)(s,a,r,s')
    4. 维护两个神经网络DQN1,DQN2,一个网络固定参数专门用来产生目标值,目标值相当于标签数据。另一个网络专门用来评估策略,更新参数。
    5. 优化关于Q网络和Q目标值之间的最小平方差:
      Li(wi)=Es,a,r,sDi[(r+γmaxaQ(s,a;wi)Q(s,a;wi))2] \mathcal { L } _ { i } \left( w _ { i } \right) = \mathbb { E } _ { s , a , r , s ^ { \prime } \sim \mathcal { D } _ { i } } \left[ \left( r + \gamma \max _ { a ^ { \prime } } Q \left( s ^ { \prime } , a ^ { \prime } ; w _ { i } ^ { - } \right) - Q \left( s , a ; w _ { i } \right) \right) ^ { 2 } \right]
      式中:ww^-在batch的学习过程中是固定的,wiw_i则是动态更新的参数。
    6. 用随机梯度下降的方式更新参数。

    首先,随机采样打破了状态之间的联系;第二个神经网络会暂时冻结参数,我们从冻结参数的网络而不是从正在更新参数的网络中获取目标值,这样增加了算法的稳定性。经过一次批计算后,把冻结参数的网络换成更新的参数再次冻结产生新一次迭代时要用的目标值。

    最小平方差控制

    使用最小平方差进行策略迭代的原理和结局如图所示:
    在这里插入图片描述
    策略评估使用 最小平方差Q学习,策略改善使用:Greedy 搜索策略。如果使用最小平方差方法进行策略控制,我们必须要设计针对行为价值函数的线性近似:
    q^(s,a,w)=x(s,a)wqπ(s,a) \hat { q } ( s , a , \mathbf { w } ) = \mathbf { x } ( s , a ) ^ { \top } \mathbf { w } \approx q _ { \pi } ( s , a )
    使用下列经历,最小化q^(s,a,w)\hat{q}(s,a,w)qπ(s,a)q_\pi(s,a)的平方差:
    D={(s1,a1),v1π,(s2,a2),v2π,,(sT,aT),vTπ} \mathcal { D } = \left\{ \left\langle \left( s _ { 1 } , a _ { 1 } \right) , v _ { 1 } ^ { \pi } \right\rangle , \left\langle \left( s _ { 2 } , a _ { 2 } \right) , v _ { 2 } ^ { \pi } \right\rangle , \ldots , \left\langle \left( s _ { T } , a _ { T } \right) , v _ { T } ^ { \pi } \right\rangle \right\}
    对于策略评估我们希望改善策略,使用类似Q学习的方法,进行离线策略学习。

    展开全文
  • 基于价值函数的二维小波变换小波脊提取算法.pdf,条纹图存在噪声干扰时,将二维小波变换系数模的最大值作为小波脊,会产生较大误差。针对这一问题,提出了基于价值函数的二维小波变换小波脊提取算法。首先,提取二维...
  • 价值函数近似(VFA) ​ 原因:状态太多,算力存储能力有限。只能通过插值的办法(神经网络)近似求得无法算到的状态价值函数值或状态动作价值函数值,或者是策略。如下: ​ 方法:线性拟合,神经网络,决策树,...
  • 创建策略和价值函数表示行动者和评论者表示 强化学习策略是一种映射,用于根据对环境的观察来选择智能体采取的行动。 在训练期间,智能体会调整其策略表示的参数以最大化预期的累积长期奖励。 强化学习智能体使用...
  • 文章目录强化学习——概述组成策略:行为函数价值函数:状态和行为的得分模型:整个世界的表达 强化学习——概述 组成 策略:行为函数 ​ 分为两种: ​ 概率型策略:从策略π\piπ中,按照概率π(a∣s)=P(at=a∣st...
  • 这一篇关注于价值函数的近似表示和Deep Q-Learning算法。  DeepQ-Learning这一篇对应Sutton书的第11章部分和UCL强化学习课程的第六讲。 1. 为何需要价值函数的近似表示  在之前讲到了强化学习求解方法,无论是...
  • 强化学习系列之五:价值函数近似

    千次阅读 2018-01-16 10:31:37
    因为算法估算价值函数 (v(s)) 或者 (q(s,a)),保存这些价值函数意味着保存所有状态。而实际问题中,状态的数目非常巨大,遍历一遍的事情就别想了。比如,围棋的状态总数是(3^{19}),听说比宇宙的总原子数还多,23333...
  • 强化学习&基础1.7 | 状态价值函数

    千次阅读 2019-04-14 11:10:56
    先创建一个环境,其中左上角的智能体想到达右下角的目标点,每走一步reward为-1...我们可以把每一个方格的值作为价值函数,定义是在每一个状态,它都生成当智能体从该状态开始,然后在所有时间步都遵循这个策略时所...
  • 价值函数的近似表示 之前的内容都是讲解一些强化学习的基础理论,这些知识只能解决一些中小规模的问题。很多价值函数需要用一张大表来存储。当获取某一状态或行为的价值的时候,通常需要一个查表操作(Table Lookup...
  • 最优价值函数 最优状态价值函数v∗(s)v_*(s)v∗​(s) optimal state-value function是所有状态价值函数中的最大值 最优行动价值函数q∗(s,a)q_*(s,a)q∗​(s,a) optimal action-value function是所有行动价值函数...
  • 这一篇关注于价值函数的近似表示和Deep Q-Learning算法。 Deep Q-Learning这一篇对应Sutton书的第11章部分和UCL强化学习课程的第六讲。 文章目录1. 为何需要价值函数的近似表示2. 价值函数的近似表示方法3. Deep Q-...
  • 前言 本章之前的内容介绍的多是规模比较小的强化学习问题,生活中有许多实际问题要复杂得多,有些是属于状态数量巨大甚至是连续的,有些行为数量较大或者是连续的。...对于带参数的价值函数,只要参数确定了,对于一个
  • 价值函数的近似表示0. 前言1. 价值近似的意义2. 目标函数与梯度下降3. 常用近似函数3.1 线性近似3.2 神经网络4. DQN算法和DDQN算法5. 编程实践 本文未经许可,禁止转载,如需转载请联系笔者 0. 前言 本章之前的内容...
  • 之前的内容都是讲解一些强化学习的基础理论,这些知识只能解决一些中小规模的问题,很多价值函数需要用一张大表来存储,获取某一状态或行为价值的时候通常需要一个查表操作(Table Lookup),这对于那些状态空间或...
  • 之前的内容都是讲解一些强化学习的基础理论,这些知识只能解决一些中小规模的问题,很多价值函数需要用一张大表来存储,获取某一状态或行为价值的时候通常需要一个查表操作(Table Lookup),这对于那些状态空间或...
  • 通过广义价值函数引出两种辅助任务强化学习和基于option的强化学习。
  • 价值函数的近似表示 通过强化学习的基础理论,只能解决一些中小规模的问题,很多价值函数需要用一张大表来存储,获取某一状态或行为价值的时候通常需要一个查表操作(Table Lookup),这对于那些状态空间或行为空间...
  • base RL,第二张图是我们的model-free RL,这里呢,可以看到model-base RL是没有和环境的一个交互,换句话说呢没有实际的交互,因为那个环境中的转移概率P我们是已知的,R也是已知的,我们只需要按照价值函数期望...
  • [梳理]两种价值函数

    2021-04-10 15:22:52
    定义最优状态价值函数:所有策略下产生的众多状态价值函数中的最大者 v ∗ ( s ) = m a x π v π ( s ) v_*(s)=\mathop{max}\limits_\pi v_\pi(s) v∗​(s)=πmax​vπ​(s) 定义最优(状态-动作)价值函数:所有...
  •   这个-1.7是怎么得出来的呢,书乱码了,谢谢! <p><img alt="" height="461" src="https://img-ask.csdnimg.cn/upload/1607613692785.png" width="648" /></p>
  • 上篇文章强化学习——时序差分 (TD) 控制算法 Sarsa 和 Q-Learning我们主要介绍了 Sarsa 和 Q-Learning 两种时序差分控制算法,在这两种算法内部都要维护一张 Q 表格,对于...一、函数逼近介绍 我们知道限制 Sarsa 和
  • (2)强化学习的动作,除了像这个游戏这种离散的,也可能是连续的,reward函数也可能是连续函数。 (3)强化学习的状态集可能比这个游戏所有的大的多,如何保证在大的状态集上表现良好(具备很强的泛化能力),...
  • 求解贝尔曼方程有两种方法:一种是解析解的形式,一种是迭代解的形式。
  • 在排序完成后,进入下一个函数groupby( ),这个函数通过key=lambda _: _[0]声明进行聚合,聚合结果是一个字典,它大概长这个样子 {‘月份’:[本月出现的所有收盘值], ‘x2’:[…],‘x3’:[…] },这时候就通过月来划分...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 8,670
精华内容 3,468
关键字:

价值函数