マルコフ決定過程
マルコフ決定過程（Markov Decision Process; MDP）は、「状態遷移にマルコフ性をもつ確率システムの動的最適化」に用いられる数学モデルです。マルコフ性とは、現在の状態（state）\(s_t\in\mathcal{S}\)と行動（action）\(a_t\in\mathcal{A}\)だけによって、次状態\(s_{t+1}\in\mathcal{S}\)が決定される性質のことです。MDPにおける強化学習では最適方策の獲得が保証されており、一般に強化学習ではMDPを仮定します。
MDPの構成要素は、タプル\(\langle\mathcal{S},\mathcal{A},\mathcal{P},\mathcal{R}\rangle\)で表現されます。ここで、\(\mathcal{S}\)は状態集合、\(\mathcal{A}\)は行動集合、\(\mathcal{P}\)は状態遷移確率（state transition probability）、\(\mathcal{R}\)は報酬関数（reward function）です。
任意の状態\(s\)と行動\(a\)に対して、遷移可能な次状態\(s’\)への状態遷移確率\(P^a_{ss’}\)は下式で表現されます。
$$P^a_{ss’}=\text{Pr}\left\{s_{t+1}=s’|s_t=s,a_t=a\right\}$$
同様に、任意の状態\(s\)と行動\(a\)に対して次状態\(s’\)に遷移したときの報酬関数\(R^a_{ss’}\)は下式で表現されます。
$$R^a_{ss’}=E\left\{r_{t+1}|s_t=s,a_t=a,s_{t+1}=s’\right\}$$
強化学習と最適方策
方策\(\pi(a|s)\)とは、状態\(s\)において行動\(a\)を選択する確率の写像であり、意思決定主体であるエージェントによる行動選択の指針となります。
以上で強化学習の説明に必要な要素が出揃ったので、強化学習の概念を説明します。強化学習とは、意思決定主体であるエージェントと、制御対象である環境が相互作用することにより、最適な制御則である最適方策を学習する手法です。なお、一般に環境にはMDPを仮定します。相互作用の流れとしては、まず時刻\(t\)においてエージェントが状態\(s_t\in\mathcal{S}\)を環境から観測し、自身の方策\(\pi_t\)に基づいて行動\(a\in\mathcal{A}\)を選択します。続いて時刻\(t+1\)では、環境に渡された\(s_t,a_t\)に基づいて決定される状態遷移確率\(P(s_t,a_t)\)によって次状態\(s_{t+1}\)に遷移し、報酬\(r_{t+1}\in\mathcal{R}\)を獲得します。エージェントは、獲得報酬に基づいてより望ましい方策\(\pi_{t+1}\)に更新し、これらの操作を繰り返すことで最適方策への収束を目指します。
状態価値関数
最適方策をより具体的に説明すると、各状態において将来獲得できる報酬の期待値（累積期待報酬）を最大化する方策であり、各状態に対してそれ以降の累積期待報酬を返す関数を状態価値関数（state-value function）といいます。MDPが成り立つ環境においてエージェントが方策\(\pi\)に従うとき、状態価値関数\(V^{\pi}(s)\)は下式で定義されます。
$$V^{\pi}(s)=E_{\pi}\left\{\sum_{k=0}^{\infty}\gamma^{k}r_{t+k+1}|s_t=s\right\}$$
上式で定義する状態価値関数は、無限時間タスク（ex. プラント内を定温に保ち続ける温度制御タスク）を前提としており、有限時間タスク（ex. 目的地までの自動運転におけるエネルギーロスを最小化するタスク）の場合は総和演算子の上部が\(\infty\)から終端時刻\(T\)に置き換わります。なお、これ以降の説明では特に断りがない限り無限時間タスクを前提とします。
MDPを仮定した強化学習の目的は、各状態において状態価値関数を最大化する方策\(\pi:\ \mathcal{S}\rightarrow\mathcal{A}\)、つまり最適方策（optimal policy）\(\pi^{\ast}\)を獲得することです。このとき、最適方策に基づいた行動選択によって最大化された状態価値関数を最適状態価値関数（optimal state-value function）\(V^{\ast}(s)\)といい、下式で定義されます。
$$V^{\ast}(s)=\max_{a}\sum_{s’}P^a_{ss’}\left[R^a_{ss’}+{\gamma}V^{\ast}(s’)\right],\ \ \ {\forall}s\in\mathcal{S}$$
上式は、\(V^{\ast}\)に対するBellman最適方程式（Bellman optimality equation）と呼ばれます。なお、最適状態価値関数\(V^{\ast}(s)\)に関する最適方策\(\pi^{\ast}\)は、各状態\(s\)から遷移可能な次状態\(s’\)における最適状態価値関数\(V^{\ast}(s’)\)を最大化する行動\(a\)を選択する方策です。つまり、最適方策\(\pi^{\ast}\)は下式で表現されます。
$$\pi^{\ast}(s)=\underset{a}{\text{arg max}}V^{\ast}(s’),\ \ \ s’\in\mathcal{S},\ P^a_{ss’} >0$$
行動価値関数
同様に、エージェントが方策\(\pi\)に従い、任意の状態\(s\)において行動\(a\)を選択する場合を考えます。このとき、状態行動対\((s,a)\)に対してそれ以降の累積期待報酬を返す関数を行動価値関数（action-value function）\(Q^{\pi}(s,a)\)といい、下式で定義されます。
$$Q^{\pi}(s,a)=E_{\pi}\left\{\sum_{k=0}^{\infty}{\gamma}^{k}r_{t+k+1}|s_t=s,a_t=a\right\}$$
また、最適方策に基づいた行動選択によって最大化された行動価値関数を\(Q^{\ast}(s,a)\)といい、下式で定義されます。
$$Q^{\ast}(s,a)=\sum_{s’}P_{ss’}^a\left[R_{ss’}^a+{\gamma}\underset{a’}{\text{arg max}}Q^{\ast}(s’,a’)\right]$$
上式は、\(Q^{\ast}\)に対するBellman最適方程式と呼ばれます。なお、最適行動価値関数\(Q^{\ast}(s,a)\)に関する最適方策\(\pi^{\ast}\)は、任意の状態\(s\)に対して\(Q^{\ast}(s,a)\)を最大化する方策であり、下式で表現されます。
$$\pi^{\ast}(s)=\underset{a}{\text{arg max}}Q^{\ast}(s,a)$$
最適方策は一意に定まるとは限らず、二つ以上存在する場合もありますが、それらすべての最適方策を\(\pi^{\ast}\)と表現します。
行動選択
強化学習における行動選択は一般に、現在の状態\(s\)において方策\(\pi\)に従い、行動価値\(Q(s,a)\)が最大となる行動\(a\)を選択します。しかし、エージェントにとって環境の情報（状態遷移確率\(\mathcal{P}\)や報酬関数\(\mathcal{R}\)）は未知であるため、現在の方策に基づく行動選択だけでは局所解に陥る可能性があります。したがって、強化学習において行動選択する際には、方策に基づく行動選択に相当する「知識利用（exploitation）」と方策に基づかない試行錯誤的な行動選択に相当する「探索（exploration）」のトレードオフを考慮する必要があります。
\(\epsilon\)-greedy選択
まず、知識利用だけを前提とした行動選択方法をgreedy選択といい、各状態\(s\)において行動\(a=\underset{a\in\mathcal{A}}{\text{arg max}}Q(s,a)\)を選択します。そこで、greedy選択に対して探索のバランスをとるために、確率\(\epsilon(0\leq\epsilon\leq)\)でランダムに行動選択し、確率\(1-\epsilon\)でgreedy選択をする行動選択方法を\(\epsilon\)-greedy選択といいます。greedy選択では、学習初期の行動価値関数によっては局所会に陥る可能性があります。一方で\(\epsilon\)-greedy選択では、ランダム性をもつ行動選択をするため、十分な学習を行えば最適方策に収束可能となります。
Boltzmann選択
Boltzmann選択は、各状態行動対の行動価値に対して指数比例した行動選択確率を割り当てる行動選択方法です。つまり、Boltzmann選択における行動選択確率\(P(a|s)\)は下式で表現されます。
$$P(a|s)=\frac{\exp(Q(s,a)/\tau)}{\sum_{a’\in\mathcal{A}}\exp(Q(s,a’)/\tau)}$$
ここで、温度パラメータ\(\tau\)は行動選択のランダム性を表現するパラメータであり、\(\tau\rightarrow\infty\)の場合はランダムな行動選択、\(\tau\rightarrow0\)の場合はgreedyな行動選択となります。
参考文献
Richard S. Sutton and Andrew G. Barto. Reinforcement learning: An Introduction. The MIT Press, 1998.