[論文紹介]Bayesian Inverse Reinforcement Learning

#Bayesian Inverse Reinforcement Learning

逆強化学習（以下IRL）をベイズの枠組で定式化した論文(2007年)の概要を紹介します。

"Bayesian Inverse Reinforcement Learning"
https://www.aaai.org/Papers/IJCAI/2007/IJCAI07-416.pdf

IRLにベイズの定理を導入した最初の論文です。
本論文では、IRLのタスクである、

　・reward learning(報酬関数の推定)
　・apprenticeship learning(見習い学習)

についてベイズのアプローチから取り組んでいます。

この論文について、ポイントの和訳と説明を記載します。

なお、定理やその証明、実験結果などについては省略しています。
そちらは上記リンクの原文をご確認ください。

また不備である箇所を見つけたら修正します。

##Abstract

----------------------------------------------------------------
IRLは、システムのダイナミクスとエキスパートの行動を前提として、
MDPの基礎となる報酬関数を学習する問題である。

IRLは報酬関数の知識それ自体がゴールである場合(=reward learning)と、
見習い学習（エキスパートから方策を学習する）(=apprenticeship learning)
によって動機づけられる。

この論文では、事前知識とエキスパートの行動を組み合わせて、報酬関数の
確率分布を導出する方法を示す。

実験結果は、以前のヒューリスティックベースのアプローチよりも我々の手法が
大幅に改善されていることを示す。

----------------------------------------------------------------


##1 Introduction

IRLの問題は下記の通り定義されている。[Russell, 1998]

 　Determine ：報酬関数
　 Given  ：
  　1)エージェントの振る舞い
  　2)エージェントの入力
  　3)環境がMDPであり、エージェントのポリシーと状態空間のダイナミクスからエージェントの報酬関数の決定が可能であること。

また、IRLの解くべきタスクとしては、2種類のタスクがあげられる。

・reward learning
 　報酬関数を求めることそれ自体がゴールである場合
・apprenticeship learning
 　見習い学習（エキスパートから方策を学習する）

本論文では、上記のIRLのタスクをベイズの文脈から捉えて解く。
エキスパートの行動を、報酬関数の事前知識を更新する尤度として捉え、報酬関数の事前確率を更新する。
これらのタスクを、MCMC法に手を加えた手法("modiﬁed Markov Chain Monte Carlo (MCMC) algorithm.")を用いて解く。


##2 Preliminaries 
省略：原文をご確認ください。
MDPとReinforcement Learningの定義および定理について記載されています。


##3 Bayesian IRL 

(説明：報酬関数を確率分布で表す必要性を主張しています)

IRLは現在、エージェントの振る舞いを説明する単一の報酬関数を推定する問題とみなされている。ただし、一般的なIRLの問題には情報が少なすぎて1つの答えしか得られない。

Figure 1の例では$s_0$からの最適な行動$a_1$は確率的に選択されている。
したがって、報酬関数の不確実性を表すには確率分布で示す必要がある。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/367093/4e5a8950-fd12-a2e9-ab83-242d7a5f3509.png)


（※Figure 1の説明では、$s_1$の行動$a_1$とありますが、$s_0$の行動$a_1$だと思います）



###3.1 Evidence from the Expert 

(説明：エキスパートの軌跡から尤度を求めます)


・MDP $M =(S,A,T,γ)$
・agent $\chi$ (以下、エキスパート$\chi$)はMDPの環境にいる
・エキスパート$\chi$の報酬関数$R$は前提知識である事前分布$P_R$から生成されると仮定
・IRL agent はエキスパート$\chi$の振る舞い $O_\chi = {(s_1,a_1),(s_2,a_2)...(s_k,a_k)}$を観測する。

エキスパート$\chi$の振る舞いには下記の仮定を置き、定式化する。

1. エキスパート$\chi$は$R$に基づいて累積報酬の合計を最大化しようとする。 
たとえば, 環境の探索のためにepsilon greedyの方策を選択しない。

2. エキスパート$\chi$は定常のポリシーを実行する。つまり、前のステップで行われた行動と観測値により変化しない。

エキスパート$\chi$のポリシーは定常なので、次の仮定を立てることができる。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/367093/f1f455c0-d937-3241-1aae-102defcdafd9.png)

エキスパート$\chi$のゴールは累積報酬を最大化することであり、これは各状態において$Q^*$が最大になる行動を見つけることと同じ。

$Q^∗(s,a)$が大きいほど、エキスパート$\chi$が状態$s$で行動$a$を選択する可能性が高くなる。 この可能性は、エキスパート$\chi$の能力に信頼(conﬁdent)があるほど増加する。

（$s_i$、$a_i$）の尤度の指数分布によって、これを$Q^*$の潜在的な関数としてモデル化する。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/367093/74151699-8e45-07d0-723e-725b1dc8811a.png)

ここで、$\alpha_{\chi}$は、高い価値をもつ行動を選択するエキスパート$\chi$の能力に対する信頼度を表すパラメータ。

尤度は

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/367093/d412202a-2192-dea7-9f73-ebdea92a8b7d.png)

ここで、$E（O_{\chi}, R）= \sum_i Q^* （s_i,a_i,R）$および$Z$は適切な正規化定数。この尤度関数は、エネルギー$E（OX, R）$および温度$\frac{1}{\alpha_{\chi}}$のボルツマン分布と考えることがでる。

ここで、ベイズの定理を適用して報酬関数$R$の事後確率を計算する。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/367093/1cca69cf-f3fc-a7bc-3aa6-efef72b8cd73.png)


正規化定数$Z'$の計算は困難。
ただし、推論に使用するサンプリングアルゴリズムは、2つの密度の比率のみ？を
必要とするためこれは問題ではない。
（説明：後述のMCMC法を用いてこれを推定する）

###3.2 Priors 

(説明：報酬関数の事前分布についてパターン分けをしています)

エキスパートの軌跡以外の情報が与えられていない場合、マックスエントロピー定理より報酬関数はi.i.dと仮定する。さらに、問題の特性により報酬関数の事前分布は使い分ける。

1.問題に関して無知　　　　　　　　　：一様分布
2.ほとんどの状態で少ない報酬　　　　：ガウスまたはラプラシアン分布
3.プランニング問題（ほとんどの状態で少ない報酬で、少数の状態で高い報酬）	：ベータ分布


##4 Inference

3章で伝えたモデルをreward learning と apprenticeship learningの
二つのタスクに使用する。

###4.1 Reward Learning 

Reward　learningは推論タスクである。
推論問題の損失関数は、線形および二乗誤差損失関数。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/367093/414a67dc-9de7-66f9-829e-3cea33064853.png)

それぞれ、$R$は真の報酬、$\hat{R}$は推測した報酬。
$R$は式(3)の事後分布から求められる場合、
$L_{SE}(R, \hat{R})$ は、$\hat{R}$が報酬関数$R$の事後分布の平均値の時に最小になる。

###4.2 Apprenticeship Learning 

ポリシー$\pi$を学習するために、方策の損失関数(policy loss functions)を定義。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/367093/59efd98d-b32a-8408-3224-5a1f4dcd0022.png)

ここで、$V^*(R)$は$R$の最適な方策によって達成される各状態の最適値のベクトルであり、$p$はあるノルムの値。

方策の損失関数の最小化は、報酬関数$R$の平均値を与えられたときの
最適な方策を見つければよい。(証明略)


##5 Sampling and Rapid Convergence 

reward learningとapprenticeship learningにおいて、報酬関数$R$の事後分布の平均を計算する必要がある。しかし、一様分布のような単純な事前分布でさえも、事後分布は複雑で平均の分析的に導くことは困難。
そこで、 MCMC algorithm GridWalk ([Vempala, 2005])を使用する。
領域$\mathbb{R}^{|S|}$の長さ$\delta$のグリッドの交点にマルコフ連鎖を生成する（$\mathbb{R}^{|S|}/\delta$と表記）。

ただし、報酬関数$R$の事後分布を計算するには、$R$の最適なQ関数を計算する必要があるがこれは高度な処理のため、GridWalkを修正したPolicyWalk(Figure 3) を使用する。

(説明：MCMC法は3.(C)で使われています)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/367093/b1d60bb0-2532-9ab0-aa54-5cccaae525af.png)



##6 Experiments, 7 Related Work 

省略：原文をご確認ください。


##8 Conclusions and Future Work 

IRLをベイズの問題として捉えることにより、IRLの新しい改善された解決策を提示した。しかし、いくつかの未解決の課題が残っている。

1.知識を使用して、特定のIRL問題のためのより有益な事前分布を見つけることができるか。

2.どの程度IRLは一般化されているか。
　仮に、actorとlearnerの状態遷移関数が異なる場合、
　learnerの状態空間に関して、どのように報酬関数や方策をactorから学ぶか。