Apprenticeship-pub

中川研機械学習勉強会 2007/6/7
Apprenticeship Learning via
Inverse Reinforcement Learning
by
Pieter Abbeel and Andrew Y. Ng
(ICML 2004)
吉田稔
強化学習
Reinforcement Learning
• 環境と、そこで行動するエージェントがいるとき、
「エージェントがどのような行動をとればいいか」
を学習する。
– 「状態」と、それを遷移させる「行動」がある。
– Policy（方策、行動則）: 「状態」に応じた「行動」を決め
る。
– Reward function（報酬関数）：状態が望ましいか否か
をスコア付けする。
– Value function（価値関数）：その状態から、最終的に
望ましい結果になるかどうかをスコア付けする
• 現時点の状態のみならず、将来の状態も視野に入れる。
しかし…
• 実際には、Reward functionを定義することす
ら難しい場面も多い。
– （例）車の運転…「右のレーンにいること」は30点、
「前の車との距離が50ｍ以下」なら-20点、…？
• Apprenticeship Learning: エキスパート（人間）
の行動を与えるだけで、（Reward functionが
与えられなくても）、行動が学習できるような
アルゴリズムが欲しい！
Apprenticeship Learning via
Inverse Reinforcement Learning
• Reward functionがわからない⇒
– 従来のアプローチ：エキスパートの行動を直接真似
する
• ロバスト性に問題
– エキスパートが行わない行動をどうする？
– 本論文の提案：可能なすべてのReward functionに
ついて、「エキスパートとほぼ同等かそれ以上」の
パフォーマンスが出せるようにする
問題設定
•
•
•
•
•
「状態」 s
「状態遷移確率」 Psa
「減衰定数」 γ （0以上1未満）
「素性関数」φ(s)
「報酬関数」reward function：本研究では、素
性と重みベクトルの内積
– 真のreward function:
• 「行動則」policy π: 各「状態」における、「行
動」の確率分布（どの行動をとりやすいか？）
問題設定
• Policy πの価値は、
• また、素性期待値
を定義する。
減衰定数に注意！
問題設定
• 2つ以上のpolicyがあったとき、その素性期待
値の線形補間をとることができることに注意
する。
• エキスパートのpolicyを πE とする。
問題設定
• μどうしの距離をε以下にすれば、価値の差も
ε以下になることに注意する。
アルゴリズム
アルゴリズム
• STEP-1(初期化): 適当なPolicyを選び、π(0)とお
く。
アルゴリズム
• STEP-2: 「エキスパートのPolicyが、今まで作ら
れたどのPolicyよりも、少なくとも t 以上は良
い」となるような最大の t を選ぶ。
– STEP-3: Marginがεより小さくなれば、終了。
アルゴリズム
• STEP-4: 新たな w により新たにReward
functionを構成し、そのReward functionのもと
での最適Policyを求める。
– STEP-5,6: 新たにμを追加し、STEP-2に戻る。
アルゴリズム
• STEP-2は、以下と等価。
• t≦εで停止すれば、
– あとは、適切なμ(i), π(i)を人手で選べばよい。
アルゴリズム
• 人手で選びたくない場合は…
• を解けばよい。
– このとき、w|μE-μ|は必ずε以下になる。
– （そうでなければ、停止条件と矛盾するので。）
アルゴリズム
• STEP-2は、以下のようにも解釈できる。
– M(i) : i番目までのμまたはその線形補間。
より簡単なアルゴリズム
• STEP-2を、以下で置き換える。
従来のアルゴリズム
より簡単なアルゴリズム
Theorem 1
• apprenticeship learning algorithmにおいて、
t≦εとなるまでのiterationの回数は、多くとも
• である。
Theorem 2
• エキスパートの行動則が正確にわからない
場合
– エキスパートの行動を、m回サンプリング
• 「少なくとも1-δの確率で」「最大でもn回以内
に」
となるためのmの条件は、
Lemma 3
• μ~(i+1)を、
「μE^の、μ(i+1)とμ’(i)を結ぶ直線への射影」
• と定義すると、
＿
√
=
Lemma 3：証明
Lemma 3：証明
差を取れば、
平方完成できる
Lemma 3：証明
分母－分子を評価するため、
分母から分子の値を取り出す
Lemma 3：証明
必ず非負
∵μ(i+1)は、評価関数wに基づく最適値
Lemma 3：証明
・ありうる最大距離は
√k/(1-γ）
・featureの値は0～1
・γ：discount factor（遷移するごとに、
featureの値にγが掛っていく）
Theorem 1
• apprenticeship learning algorithmにおいて、
t≦εとなるまでのiterationの回数は、多くとも
• である。
Theorem 1:証明
tの可能な最大値
＿
=
√
Theorem 1:証明
t ≦ ε となるためには…
Theorem 2
• エキスパートの行動則が正確にわからない
場合
– エキスパートの行動を、m回サンプリング
• 「少なくとも1-δの確率で」「最大でもn回(see
Theorem 1)以内に」
となるためのmの条件は、
Theorem2:証明
• Hoeffdingの不等式を使う。
Theorem2:証明
Theorem2:証明

Download Report