构建技能树（CST）是一种分层强化学习算法，它从演示中获得的一组样本解决方案轨迹中自动构建技能树。该算法由George Konidaris、Scott Kuindersma、Andrew Barto和Roderic Grupen于2010年提出。该算法识别演示行为中可重复使用的子技能，并将其组织成树状结构，使智能体能够通过重用已学习的组件更高效地解决新任务。
CST通过使用增量最大后验（MAP）变点检测算法，将每个演示轨迹分割为离散技能。然后，这些技能在轨迹间进行对齐和合并，形成技能树，其中每个节点代表一个技能，边表示时间或层次关系。该方法设计为在线运行，可增量处理演示，无需预先获取所有数据。
算法概述
CST算法由三个主要组件组成：变点检测、对齐和合并。核心重点是在线变点检测，它使用折扣奖励总和作为目标回归变量，将数据分割为技能。每个检测到的技能被赋予适当的抽象，粒子滤波器控制计算复杂度。
变点检测算法处理时间t在T中的数据，给定一组模型Q及其先验概率p(q)。它使用模型q拟合从时间j+1到t的段，基于具有高斯噪声的线性回归模型计算拟合概率P(j,t,q)。噪声先验均值为零，方差遵循InverseGamma分布，而每个权重先验遵循正态分布。
拟合概率使用涉及矩阵行列式和伽马函数的特定公式计算。CST随后使用Viterbi算法计算时间j处模型q的变点概率，结合风险函数g及其累积分布G来建模段长度。
变点检测细节
对于每个潜在变点，CST计算P_t(j,q)作为生存概率、拟合概率、模型先验和时间j处MAP概率的乘积。MAP概率P_j^MAP通过最大化先前变点和模型（由风险函数加权）来确定。这种递归公式允许高效的在线处理。
回归模型使用折扣奖励作为目标变量，使算法能够专注于导致更高累积奖励的技能。粒子滤波器维护一组候选变点，即使在长轨迹下也能保持计算成本可控。
技能对齐与合并
在变点检测之后，CST在不同演示轨迹间对齐技能。表现出相似时间模式和奖励动态的技能被分组在一起。对齐过程使用拟合的回归参数来匹配可能代表相同底层技能的段。
合并随后将对齐的技能集成到技能树中。当多个演示包含相似技能时，它们被组合成具有相关统计信息的单个节点。树结构捕获顺序依赖关系（哪些技能跟随其他技能）和层次关系（由子技能组成的技能）。
应用与意义
CST已应用于机器人学习领域，其中来自人类操作员或远程操作的演示用于引导自主行为。生成的技能树通过重用先前获取的技能，实现更快地学习新任务，减少广泛探索的需求。
该算法为更广泛的分层强化学习领域做出贡献，该领域旨在将复杂任务分解为可管理的子问题。与某些需要预定义任务层次的方法不同，CST直接从数据中发现结构，使其适用于手动分解不切实际的领域。
CST的在线特性使其区别于批处理算法，允许其随着新演示的到来而适应。这一特性在交互式学习场景中很有价值，其中机器人或智能体接收增量反馈。贝叶斯变点检测的使用提供了一种原则性的方式来平衡模型复杂度与拟合质量，避免过度分割。
相关概念
CST与机器学习和强化学习中利用演示的其他方法相关，例如课程学习，它逐步构建训练。该算法对统计模型的使用与贝叶斯推断和时间序列分析的更广泛工作相联系。在现代人工智能的背景下，CST的层次分解思想与学习分层表示的深度学习架构产生共鸣，尽管CST操作于符号技能抽象而非原始感官数据。
技能发现的研究继续在机器人学和自主智能体等领域进行，其中高效重用已学习行为至关重要。CST对在线、增量学习的关注与持续适应环境的终身学习系统趋势一致。虽然与大型语言模型研究没有直接联系，但从演示中构建可重用组件的原则在现代AI系统中的提示工程和工具使用方面具有相似之处。
局限性与扩展
原始CST算法假设在演示期间可访问奖励信号，这并非总是可用。扩展已探索在奖励稀疏时使用替代分割标准。线性回归模型限制了可表示技能的复杂性，尽管该框架可以通过适当修改适应非线性模型。
粒子滤波器引入近似误差，风险函数的选择影响分割粒度。研究人员已调查自适应参数设置，以提高跨不同任务领域的鲁棒性。尽管存在这些局限性，CST仍然是分层技能学习的基础性贡献，影响了后续关于选项发现和强化学习中层次抽象的研究。