報酬成形

報酬成形とは

報酬成形は、強化学習において、MDP(マルコフ決定過程)が本来与える報酬に加えて、学習の過程を導くための追加の報酬を学習エージェントに与える手法です。ねらいは、良い方策、できれば最適な方策を、より速く学習できるよう学習アルゴリズムを手助けすることにあります。

変換されたMDPとしての捉え方

Ng、Harada、Russellの論文(ICML 1999)は、報酬成形を次のように定式化しました。学習アルゴリズムを元のMDP Mで走らせる代わりに、変換されたMDP M'で走らせると考えます。M'の報酬関数はR'=R+Fで、Fは成形報酬関数と呼ばれる有界な実数値関数です。元のMDPで状態sから行動aによって状態s'へ遷移したときに報酬R(s,a,s')を受け取っていたなら、M'では同じ遷移でR(s,a,s')+F(s,a,s')を受け取ります。

成形報酬の例として、論文は2つの形を挙げています。1つはゴールへ近づくことを促すもので、遷移先の状態s'が遷移前の状態sよりゴールに近いときにF(s,a,s')=r(rは正の報酬)とし、それ以外は0とします。もう1つは、ある状態の集合S0の中で特定の行動a1をとることを促すもので、a=a1かつsがS0に含まれるときだけF(s,a,s')=rとし、それ以外は0とします。

最適方策を保つ条件

論文の中心は、報酬関数を変えても最適方策が変わらない条件の解明です。効用理論でおなじみの正の線形変換に加えて、任意のポテンシャル関数を状態に適用した値の差として表せる報酬を、状態間の遷移に加えてもよいことが示されました。定理では、実数値関数Phiが存在して、すべてのs、a、s'についてF(s,a,s')=gamma*Phi(s')-Phi(s)と書けるとき、Fをポテンシャルベースの成形関数と呼び、これが最適方策との整合性を保証するための必要十分条件であるとしています。必要条件でもあるため、元のMDPの遷移確率や報酬について追加の前提を置かない限り、ほかの形の変換では最適でない方策が学習されるおそれがあります。

よく知られたバグと実用上の効果

ポテンシャルベースでない成形報酬を使うと、エージェントが状態を循環して成形報酬を稼ぎ続けるといった、報酬成形の実践でよく知られたバグが起こりえます。論文は、こうしたバグがポテンシャルベースでない報酬から生じることを示しました。一方で、距離に基づくヒューリスティックやサブゴールに基づくヒューリスティックに対応する成形ポテンシャルの作り方も示し、そうしたポテンシャルによって学習時間を大幅に短縮できることを報告しています。