スキルツリー構築（CST）は、デモンストレーションから得られた一連のサンプル解軌跡からスキルツリーを自動的に構築する階層的強化学習アルゴリズムである。これは2010年にジョージ・コニダリス、スコット・クインデルスマ、アンドリュー・バート、ロデリック・グルーペンによって導入された。このアルゴリズムは、デモンストレーションされた行動内の再利用可能なサブスキルを識別し、それらをツリー構造に整理することで、エージェントが学習済みコンポーネントを再利用して新しいタスクをより効率的に解決できるようにする。
CSTは、各デモンストレーション軌跡を、増分最大事後確率（MAP）変化点検出アルゴリズムを用いて個別のスキルに分割することで動作する。これらのスキルは、軌跡間で整列・統合され、スキルツリーを形成する。各ノードはスキルを表し、エッジは時間的または階層的な関係を示す。このアプローチはオンラインで動作するように設計されており、すべてのデータを事前に必要とせず、デモンストレーションを増分的に処理する。
アルゴリズム概要
CSTアルゴリズムは、変化点検出、整列、統合の3つの主要コンポーネントで構成される。中心的な焦点はオンライン変化点検出であり、割引報酬の合計をターゲット回帰変数としてデータをスキルに分割する。検出された各スキルには適切な抽象化が割り当てられ、粒子フィルタが計算複雑性を制御する。
変化点検出アルゴリズムは、事前確率p(q)を持つモデル集合Qが与えられた場合、時間t∈Tのデータを処理する。モデルqを使用して時間j+1からtまでのセグメントを適合させ、線形回帰モデルとガウスノイズに基づいて適合確率P(j,t,q)を計算する。ノイズ事前分布は平均ゼロで、分散は逆ガンマ分布に従い、各重み事前分布は正規分布に従う。
適合確率は、行列行列式とガンマ関数を含む特定の式を使用して計算される。CSTは次に、ハザード関数gとその累積分布Gを使用してセグメント長をモデル化し、ビタビアルゴリズムを使用して時間jとモデルqでの変化点の確率を計算する。
変化点検出の詳細
各潜在的な変化点について、CSTは生存確率、適合確率、モデル事前分布、および時間jでのMAP確率の積としてP_t(j,q)を計算する。MAP確率P_j^MAPは、ハザード関数で重み付けされた以前の変化点とモデルを最大化することによって決定される。この再帰的定式化により、効率的なオンライン処理が可能になる。
回帰モデルはターゲット変数として割引報酬を使用し、アルゴリズムがより高い累積報酬につながるスキルに焦点を当てることを可能にする。粒子フィルタは候補変化点のセットを維持し、長い軌跡でも計算コストを管理可能に保つ。
スキルの整列と統合
変化点検出後、CSTは異なるデモンストレーション軌跡間でスキルを整列させる。類似した時間的パターンと報酬ダイナミクスを示すスキルはグループ化される。整列プロセスは、適合回帰パラメータを使用して、同じ基盤となるスキルを表す可能性が高いセグメントを一致させる。
統合は、整列されたスキルをスキルツリーに統合する。複数のデモンストレーションに類似したスキルが含まれる場合、それらは関連する統計とともに単一のノードに結合される。ツリー構造は、順序依存関係（どのスキルが他のスキルに続くか）と階層関係（サブスキルで構成されるスキル）の両方を捉える。
応用と意義
CSTはロボット学習領域に応用されており、人間のオペレーターや遠隔操作からのデモンストレーションが自律行動をブートストラップするために使用される。結果として得られるスキルツリーは、以前に獲得したスキルを再利用することで新しいタスクの学習を高速化し、広範な探索の必要性を減らす。
このアルゴリズムは、複雑なタスクを管理可能なサブ問題に分解することを目指す階層的強化学習の広範な分野に貢献する。事前定義されたタスク階層を必要とする一部の方法とは異なり、CSTはデータから直接構造を発見するため、手動分解が非現実的な領域に適している。
CSTのオンライン性はバッチアルゴリズムと区別され、新しいデモンストレーションが到着するにつれて適応できる。この特性は、ロボットやエージェントが増分フィードバックを受け取るインタラクティブな学習シナリオで価値がある。ベイズ変化点検出の使用は、モデル複雑性と適合品質のバランスを取る原理的な方法を提供し、過分割を回避する。
関連概念
CSTは、機械学習や強化学習におけるデモンストレーションを活用する他のアプローチ、例えばトレーニングを段階的に構造化するカリキュラム学習と関連している。このアルゴリズムの統計モデルの使用は、ベイズ推論や時系列解析の広範な研究と結びついている。現代の人工知能の文脈では、CSTの階層的分解のアイデアは、層状表現を学習する深層学習アーキテクチャと共鳴するが、CSTは生の感覚データではなく象徴的なスキル抽象化で動作する。
スキル発見の研究は、学習済み行動の効率的な再利用が重要であるロボティクスや自律エージェントなどの領域で続けられている。CSTのオンラインで増分的な学習への焦点は、継続的に適応する生涯学習システムへのトレンドと一致する。大規模言語モデル研究に直接結びついてはいないが、デモンストレーションから再利用可能なコンポーネントを構築する原則は、現代のAIシステムにおけるプロンプトエンジニアリングやツール使用に類似点がある。
制限と拡張
元のCSTアルゴリズムは、デモンストレーション中の報酬信号へのアクセスを前提としており、これは常に利用可能とは限らない。報酬が疎な場合の代替分割基準を探る拡張が研究されている。線形回帰モデルは表現可能なスキルの複雑性を制限するが、フレームワークは適切な修正で非線形モデルに対応できる。
粒子フィルタは近似誤差を導入し、ハザード関数の選択は分割の粒度に影響する。研究者は、異なるタスク領域での堅牢性を向上させるための適応パラメータ設定を調査している。これらの制限にもかかわらず、CSTは階層的スキル学習への基礎的な貢献であり、強化学習におけるオプション発見と階層的抽象化に関するその後の研究に影響を与えている。