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