A Clustering-Based Graph Laplacian Framework for Value Function Approximation in Reinforcement LearningIEEE TRANSACTIONS ON CYBERNETICS, VOL. 44, NO. 12, DECEMBER 20141. 介绍2. 模型3. 分析和讨论1. 介绍p 强化学习是一类机器学习方法，求解可以描述为MDPs的 序贯决策问题。通过与未知环境的交互，智能体学习动 作策略来最大化累计回报。 强化学习已被认为是求解模型不确定的学习控制或自适 应最优控制问题的重要框架。 早期研究主要集中在具有离散的状态和动作空间的MDPs 。 但在很多实际应用中，需要用强化学习求解具有大规模 或连续状态空间的MDPs。n 针对这个问题，近似强化学习方法在近年来得到了广泛 研究，如策略搜索、值函数估计（VFA）、actorcritic方 法、分层强化学习、迁移学习等。1. 介绍p 在很多强化学习应用中，值函数估计一直处于核心地位 ，有线性估计结构和非线性估计结构。线性估计结构可 以保证收敛性和稳定性，而非线性估计结构虽然可能具 有更好的估计能力，但却难以进行严格的理论分析。p 几个线性估计算法：线性Sarsa学习、最小二乘策略迭 代、基于核的最小二乘策略迭代等。p 之前的VFA算法的一个共同的缺点是，基函数通常需要 人为确定，而不是基于状态空间来自动构造。p 近来，有文献提出了一种称为原型值值函数（proto-value function，PVF）的VFA方法。通过对自伴拉普拉斯算子 的特征分析来构造PVFs，即将拉普拉斯矩阵对角化后， 通过计算最小的特征值和对应的光滑特征向量来生成基 函数。1. 介绍p 基于这种思想，相关文献提出了一类近似策略迭代算法 representation policy iteration (RPI)。p 针对大规模或连续状态空间MDPs，RPI中一个重要的问 题就是二次抽样。因为收集的样本数量可能会很大，需 要选取合适的样本子集来构造图。文献研究了一种随机 二次抽样方法和一种基于轨迹的二次抽样方法。但针对 大规模或连续状态空间的MDPs时，RPI的性能需要进一 步提高。p 围绕特征表示和值函数估计（VFA），本文提出了一种基 于聚类的图拉普拉斯框架。p 基于聚类技术，也即K-means clustering 或fuzzy C- means clustering，采用二次抽样构建了具有连续状态空 间的MDPs的图拉普拉斯。通过对图拉普拉斯的特征分析 ，自动生成VFA中的基函数。1. 介绍u基于聚类的图拉普拉斯结合了RPI，本文所提出的新的学 习控制算法称为基于聚类的RPI（CRPI）。p 在CRPI中，二次抽样的目的是过滤掉那些不必要的点， 这些点所包含的状态空间的基本流形特征的信息很少， 从而用具有代表性的点来学习一个有效的基函数集。p 经过聚类分析后，同一聚集中的所有点呈现出最大的相 似性。中心即为同一聚集中所有点的平均或权重平均。 基于所有聚集的中心所构造的图能更准确地表示状态空 间的基本流形。p 仿真和实验表明，相比较之前的方法，本文提出的基于 聚类的图拉普拉斯方法只需要很少的样本就可得到有效 的基函数集，且CRPI的性能要比RPI好很多。A. MDP M: X, A ,R, PX 状态空间， A 动作空间，R=R(x,a) 回报函数，P 状态转移概率 策略：从状态空间到动作空间概率分布的映射；2. 模型基于聚类的图拉普拉斯框架与之前的图拉普拉斯方法相比，本文的方法具有如下特点： 一是构造图拉普拉斯时的子集选择。在基于聚类的框架下 ，用基于聚类的方法选择的数据点更具有代表性。本文提 供两种基于聚类的二次抽样方法。 在RPI中，随着所收集的样本的增加，用于构造图的子集 的规模也在增加，使得图越来越复杂。而基于聚类的拉普 拉斯框架能避免这种情形，因为在整个学习过程中，二次 抽样的数目和聚集数总是一样的。2. 模型B . 基于聚类的图拉普拉斯框架 最主要的优点是在构造图时可以通过选择合适的二次抽样 来增强基函数的估计能力。 在连续域内，通常使用Nystrm extension method将已检测 点的特征函数扩展到未检测点，也可以看作是整个状态空 间基函数的估计。 依据基于聚类的图拉普拉斯框架，提出了CRPI算法。 在CRPI中，样本是随机收集的，或者通过一个初始策略 收集。样本收集之后，采用基于聚类的方法从原始样本集 中选取二次抽样样本。通过连接样本子集中的任意两个点 得到边，并给所有边赋予权重，从而可以构造图。使用组 合或标准拉普拉斯计算拉普拉斯特征函数。则基函数由图 拉普拉斯的最小特征值对应的最光滑的特征向量构成。2. 模型2. 模型(公式6)sigmaphilamda2. 模型(公式9)(公式8)(公式7)gammaphi 为了对具有连续状态和 n 个离散动作的MDPs的动作值函 数进行估计，对每个动作重复以上基函数 是指标函数, 如果 , 否则 从而对于策略 的动作值函数 估计为 其中 是基函数的维数， 是 的第 i 个 元素， 是第 i 个系数。2. 模型(公式10)(公式11)psi 令 这里 是从策略 收集到的样本集，其中 是由 决定的， t 为迭代 数，其初始化为0。 则可以通过下式得到策略估计的最小二乘定解和对应的改 进策略2. 模型(公式13)(公式12)phipsi2. 模型2. 模型CRPI中，聚类方法用来从所收集的样本集中选择一个子 集，该子集的规模通常远远小于原始样本集。论文提供了 两个基于聚类的二次抽样方法，分别使用了K-均值聚类算 法和FCM算法。 所提方法的一个特性是：输出不是聚集的质心或权重质心 ，而是聚集中离质心或权重质心最近的样本点。 聚类方法中采用两点间的欧式距离作为度量。2. 模型C . CRPI中基于聚类的二次抽样算法 对收集的样本集 ，K-均值算法将 每个点分配到K 个聚集的某一个中，从而最小化聚集方差 其中 是 的第 k 个子集， 是聚集 k 的质心 其中 是 中点的数目。2. 模型C-1 . 使用K-均值聚类的二次抽样-算法描述(公式15)(公式14) 聚集中心产生后，通过选择那些最接近聚集中心的点，每 个聚集都产生了一个子集。 在使用K-均值聚类的二次抽样算法中，初始中心的选择始 终不是随机的。如果学习策略的性能足够好的话，最后生 成的子集中的 K 个点将作为下一次迭代的初始质心。2. 模型C-1 . 使用K-均值聚类的二次抽样-算法描述2. 模型 通过最小化类内方差 FCM算法将给定的数据集 X 划分成 c 个模糊集。式中b 为权重指数， ， 是 X 的模糊c-划分 ，满足如下条件 是中心向量集合， 是 是第 k 个聚集中心， 是 上的诱导A-范数。具体 算法中用单位矩阵代替A 。2. 模型C-2 . 使用 FCM 聚类的二次抽样-算法描述(公式16)(公式17)2. 模型 在连续状态的MDPs中，为了学习近似最优策略，有必要 基于存在样本的特征函数去计算那些新的未检测点的特征 函数。 在RPI中，运用了 Nystrm extension 方法，同时结合迭代 更新和随机算法，以实现 low-rank 逼近。 用组合拉普拉斯算子 来做性能分析。其迹可以 表示为 也即 L 的特征值之和等于 W 的除对角线之外的元素之 和。3. 分析和讨论A. 性能分析 令 和 分别为用基于聚类的方法和基于轨迹的方法构 造的算子， 和 是对应于边 的权重， 和 是 和 的特征值。则有 上式说明，相比RPI中基于轨迹的二次抽样方法，基于聚 类的图拉普拉斯具有更小的特征值。因此，有利于CRPI算 法寻找更光滑的基函数。3. 分析和讨论下面分析 Nystrm extension 方法的估计误差。 按照Nystrm extension误差，CRPI和RPI的性能分析将基 于构造图所选择的子集的质量来进行。 令L为一个图算子，它是用基于聚类的二次抽样方法得到 的子集而构造的。H表示由所有样本生成的图算子矩阵。 Nystrm extension方法实现了将基于部分状态计算的L的 特征向量向全部状态的插入。 设 H 为一个需要估计的 对称半正定矩阵（SPSD ）。选择 H 的一个 最重要的子矩阵，将 H 分块 如下其中 L 为 SPSD矩阵。3. 分析和讨论B. 误差分析 对应多指标集 考虑划分。H 和 L的特征分解如下 其中 为对角阵， 为 H 的特征值，U 是正交矩阵，其列为 H 的特征向量。 Nystrm extension 是对 U 中 N 个特征向量的估计，如下 3. 分析和讨论B. 误差分析 运用两个估计 和 ，H 的另一个估计表示为 这里 称为 H 关于 的 Nystrm 估计。 估计误差为 可见在基于聚类的框架下，使用子集的估计误差，其上界 为 H 的 个最小特征值之和。3. 分析和讨论B. 误差分析