Algorithms for Inverse Reinforcement Learning

[usajpn]

Andrew Ng, Stuart Russel
https://ai.stanford.edu/~ang/papers/icml00-irl.pdf

概要

逆強化学習の元祖論文。手法の主要アプリケーションである模倣学習について触れたのち、3つのアルゴリズムについて少しずつ拡張しながら説明する。特に逆強化学習の根本問題の一つである"degeneracy(縮退)" = "最適な戦略に対して報酬がたくさん存在してしまう問題"について強く言及している。

IRLの問題設定

入力: エキスパートのデモンストレーション、(環境の情報 (状態遷移確率など))
出力: 報酬関数

アプリケーション

1. 生物学などの理論説明
   蜜蜂🐝の採餌モデルの説明など。
2. 模倣学習 (Imitation Learning, Apprenticeship Learning)
   デモンストレーションを見せられて、それを真似する行動シーケンスを学習する。

IRL in Finite State Spaces

まずは超重要定理から。

つまり何を言っているかというのはこの式を見てもわからないが、導出を見るとわかりやすい。

まず、Value Functionをマトリックスフォームで表現する。

これを式変形すると以下に。

Value FunctionはRewardに対してTransition Matrixの逆行列っぽいものを掛け合わせたもの。

一番重要なのはここで、戦略において、最適なactionをa1としたときにそのactionはQ-Functionのargmaxをとったもの。
つまりそれはa1行動をとった場合のQ-Functionはほかの行動をとった場合のQ-Functionと同値または値が大きいことを言える。

これをまた式変形していくと、最終的に定理式に辿りつく。
しかし、この式には問題がある。

1. R=0が答えとなり得る。
2. Rの答えが複数あることがあり得る。

これを解決しようというのが以降の条件付け。

一つは、一番良い行動をとったときのQ-Functionと二番目に良い行動をとったときのQ-Functionの差を最大化しようという考え。

もう一つは、Rが大きく発散しないような制約をつけること。

つまり�、どういう最適化問題に落ち着くかというと、1番目によいQ-Functionと2番目に良いQ-Functionの差分を最大化するが、その際のRは大きくなりすぎないようにペナルティー項を加える。
先の定理を条件とする。

Linear Function Approximation in Large State Spaces

どうやって大きい状態空間でも対応できるようにするかが次の問題。

Φは状態空間から特徴空間への写像。
報酬関数は特徴空間Φと重み係数αの線形結合と考えることで状態空間全てに対して考慮しなくてよい。
そもそも報酬は状態一つ一つを見ているのではなく、特徴に対して付与されているものだろうと考えのもとこのような式が建てられている。特徴写像はResNetとかでもいいし単なるOne-Hot Vectorでもよい。

次に報酬関数はValue FunctionとはLinearな関係にあるので、以下のように表せる。

Value Funtionの期待値で先の式を表すことで、無限状態空間においても有効であることを示す。

IRL from Sampled Trajectories

エキスパート戦略が既知でなく、サンプルのみが取れる場合はサンプルをベースにValue Functionの差分を最大化する。