1. はじめに

　逆強化学習の手法についてはこちらを御覧ください。本記事では逆強化学習の手法については解説していません。
　逆強化学習は、エキスパートの行動から報酬を推定する手法です。例として下図のようなことを実現することが可能になります。

(K.Kitani, et al., 2012, Activity Forecasting, ECCV)

この例では、逆強化学習によって人の行動の報酬を推定し、経路予測をしています。

一般的に、強化学習ではエージェントが環境から報酬を得ることで最適な行動を学習します。エージェントは環境に行動という形で働きかけ、環境はそれによって変化した状態と状態の価値である報酬をエージェントに渡します。この一連の相互作用を何度も繰り返し、報酬の最大化を目指します。

　強化学習の課題として、多くのタスクでこの報酬をはっきりと定義することが難しい点が挙げられます。例えば、「車を上手に運転する」というタスクを考えてみます。上手な運転の条件として、適切な車間距離や駐車がスムーズなどがありますが、「適切な」や「スムーズ」は定義が曖昧で状況によって変化します。報酬の定義が曖昧な状態で、強化学習を応用することは困難になります。

　逆強化学習では、エキスパートの行動から報酬を推定することで強化学習の課題を解決します。「上手な運転」自体は優秀なドライバーの運転を記録することでその行動履歴を知ることができます。逆強化学習では、収集可能な「上手な運転」から報酬の推定、つまりドライバーの行動基準を数値化することを目指します。その行動基準から、エージェントに最適な行動を学習させます。さらに行動基準はエキスパートが何を目的に行動していたかの理解に役立ちます。

　本記事では、逆強化学習を理解するために、強化学習の基礎について説明します。この記事では強化学習の目的と定式化、そして強化学習における良い行動について定義してきます。最後にValue Iterationというアルゴリズムを使って、良い行動を学習させます。

2. 理論

逆強化学習を理解する前に必要な強化学習の基礎理論を以下の3つに分けて解説します。

2.1. 強化学習の目的
2.2. 強化学習のモデル化
2.3. モデルの学習

2.1 強化学習の目的

　強化学習の目的は、環境における報酬を最大化するようにエージェントの行動を学習することです。エージェントとは行動の主体であり、環境は働きかけられる対象のことです。報酬はエージェントが行動を取るたびに、環境から与えられる(行動の結果遷移した)状態の良さです。エージェントは高い報酬が得られる行動だけを選択していると局所解に陥ります。報酬はある時点での行動の結果の良さであって、長期的に見た行動の良さではありません。報酬が最大化される行動を取り続けても、最終的に得られる報酬が最大になるとは限らないのです。つまり、強化学習は一時的に報酬が減ったとしても、最終的な報酬が最大になると想定される行動をエージェントに学習させます。

強化学習の目的について、マリオを例にして詳しく説明してきます。マリオにおいて、{環境、エージェント、行動}は以下のようになります。

環境: ステージ
エージェント: マリオ
行動: {上，下，左，右}移動

ステージをクリアすると報酬を得ることができますが、敵にやられたり、穴に落ちたら報酬は減ってしまいます。またその過程の行動に報酬は与えられません。強化学習の目的は最終的な報酬を最大化です。敵にやられたり，穴に落ちたりすることを恐れて動かずにいると一時的に報酬が高くなることが考えられますが、この行動では報酬は最大化できません。エージェントはこのような行動を避け、クリアすることで報酬の最大化を目指さなければなりません。

2.2 強化学習のモデル化

下図のシンプルな迷路を例に強化学習のモデル化を考えてみます。

迷路上でエージェントが選択可能な行動は↑,↓,←,→の4つです。これらの行動を組み合わせ、緑のブロックにたどり着けば報酬は$+1$、赤のブロックなら$-1$となります。赤のブロックを避けつつ緑のブロックに辿り着く行動の戦略(方策)を学習することが強化学習の目的です。

この迷路ではエージェントの思った行動とその結果は必ずしも一致しません。この制約を図に表すと、以下のようになります。

例えば、エージェントは80%の確率で上に移動できますが、10%の確率で左か右に移動してしまいます。

これまでの迷路の問題設定を数式にまとめると以下のようになります。

状態: $s \in \cal S$
- 迷路の取りうる状態を表し、迷路上のすべての位置になります。
行動: $a \in \cal A$
- エージェントが取りうる行動、今回の例では4種類の行動があります。
遷移確率: $P(s'|s,a)$
- ある状態$s$である行動$a$を取ったときに、別の状態$s'$に遷移する確率を表しています。
報酬: $R(s)$
- ある状態$s$に辿り着いたときに、エージェントが得るスカラー値です。
方策: $\pi(a|s)$
- 強化学習の目的でもある行動の戦略です。

この定式化をマルコフ決定過程(Markov Decision Process;MDP)と呼びます。強化学習では、マルコフ決定過程で定義される環境で、エージェントの方策の最適化を行います。

エージェントの方策の最適化を行う際、次式の割引報酬和$G_t$で方策の良さを評価します。

$$
G_t =R_{t+1}+\gamma R_{t+2}+\gamma^2 R_{t+3}+\cdots= \sum_{\tau=0}^{\infty} \gamma^{\tau} R_{t+1+\tau}
$$

割引報酬和は、ある時点$t$からの報酬を$\gamma^{\tau}$で重み付けをしながら足し合わせたものです。割引率$\gamma(0 \le \gamma \le 1)$によって未来の時点での報酬をどのように見積もるかを決めます。割引率が低い場合、短期的な報酬を高く評価するようになります。高い場合は長期的な報酬を高く評価するようになります。割引率は、タスクの特性に応じて決定します。割引報酬和が高くなる方策が、強化学習で求めたい方策になります。

しかし、実際の強化学習では割引報酬和ではなく状態価値によって方策の評価を行います。状態価値とは、割引報酬和の期待値のことです。エージェントの状態は遷移確率$P(s'|s,a)$や方策$\pi(a|s)$によって確率的に変化するので、割引報酬和も確率的に変化する値になります。方策を評価する際に、確率的に変化する値は扱いづらいので、割引報酬和の期待値である状態価値を用います。ある方策$\pi$に従って行動したときの状態価値は、

$$
V^{\pi}(s)=\mathbb{E}^{\pi}\big[G_t|s_t=s\big]=\mathbb{E}_{\pi}\bigg[\sum_{\tau=0}^{\infty} \gamma^{\tau} R_{t+1+\tau}|s_t=s\bigg]
$$

となります。状態価値$V$は割引報酬和$G$の期待値であるので、$V^{\pi}$を次のように変形します。

$$
V^{\pi}(s)=\mathbb{E}^{\pi}\big[R(s) + \gamma V^{\pi}(s')|s_t=s\big]
$$

割引報酬和$G$を状態$s$で得られた報酬$R(s)$と次の状態$s'$の状態価値$V(s')$の和で表しています。

状態価値関数に基づく最適な方策は、状態価値の期待値が最大になるように行動を選択することです。すなわち、

$$
\pi^*(s) = {\rm arg~max}_a \mathbb{E}_{P(s'|a,s)} \big[ R(s) + \gamma V^*(s')|s_t=s \big]
$$

と表せます。$\mathbb{E}_{P(s'|a,s)} \big[ R(s) + \gamma V^*(s')|s_t=s \big]$は状態$s$である行動を選択したときの、次の状態における状態価値の期待値を表しています。${\rm arg~max}_a$を取っているので、状態価値の期待値を最大化する行動$a$を選択することになります。

2.3 モデルの学習

モデルの学習を行うValue Iterationは、最適な状態価値関数$V^*(s)$を求めるアルゴリズムです。具体的なアルゴリズムは以下のようになります。

Value Iteration
1: $V_0(s)$をすべての状態について初期化する。
2: すべての状態$s$について$V(s)$を更新式に従って更新する。$$V_{i+1}(s) := \max_a \sum_{s'} P(s'|a,s)\bigl(R(s) + \gamma V_i(s')\bigr)$$
3: $V_{i+1}(s)$と$V_i(s)$の変化がなくなるまで繰り返す。

ステップの2では、ある状態$s$で取ることのできるすべて行動$a$に対して、状態価値$\sum_{s'} P(s'|a,s)\bigl(R(s) + \gamma V_i(s')\bigr)$を計算します。そして、その状態価値のうち最大となる値で、状態価値関数を更新しています。

3. 実装

Value Iterationを実装し、最適な状態価値関数$V^*(s)$を計算します。コードは以下になります。

value_iteration.py

def __call__(self, gamma, epslion, reward_function=None):
    probs = self.probs
    n_states = self.n_states
    n_actions = self.n_actions
    V = np.zeros(n_states)

    def compute_action_value(state):
        A = np.zeros(self.n_actions)
        for action in range(n_actions):
            for prob, next_state, reward, done in probs[state][action]:
                reward = reward if reward_function is None else reward_function(state)
                A[action] += prob * (reward + gamma * V[next_state])
        return A

    while True:
        delta = 0
        for state in range(n_states):
            A = compute_action_value(state)
            best_action_value = A.max()
            delta = max(delta, np.abs(best_action_value - V[state]))
            V[state] = best_action_value
        if delta < epslion:
            break

    policy = np.zeros([n_states, n_actions])
    for state in range(n_states):
        A = compute_action_value(state)
        policy[state] = A
    policy -= policy.max(axis=1, keepdims=True)
    max_values = np.broadcast_to(policy.max(axis=1, keepdims=True), policy.shape)
    policy = np.where(policy == max_values, policy, np.NINF)
    policy = np.exp(policy) / np.exp(policy).sum(axis=1, keepdims=True)
    return V, policy

状態価値関数を0で初期化: V = np.zeros(n_states)
whileで状態価値関数$V$を繰り返し更新: while True:
3. forで各状態の状態価値関数$V(s)$を更新: for state in range(n_states):
1. 変数stateはある状態$s$を表し、各行動$a \in \cal A$を取ったときの$\sum_{s'} P(s'|a,s)\bigl(R(s) + \gamma V_i(s')\bigr)$を計算: A = compute_expected_reward(state)
2. 最大の状態価値を計算: best_action_value = A.max()
3. 3の値で、状態価値関数$V$を更新: self.V[state] = best_action_value

Value Iterationによって状態価値関数を最適化する実装は以上です。全体のコードはyasufumy/python_irlにアップロードしています。

4. おわりに

本記事では、逆強化学習を理解するために、必要な強化学習の基礎として、マルコフ決定過程によるモデル化、Value Iterationでの学習を解説しました。次の記事では、逆強化学習の手法について理論と実装についての解説です。よろしければ御覧ください。