概要
強化学習理論の基礎4の続きです。
5の範囲は、探索と搾取についてであり、最後になります。
今まで多くの強化学習アルゴリズムを学習しましたが、基本的でありながら重要なRLの課題である探索と搾取について、シンプルな問題を利用してより深く学びます。
そして、それを実践的なRLに適用する方法を学びます。(しかし、ほぼBandits問題についてです)
探索と搾取のジレンマ
強化学習の中で、エピソードの中でアクションを決める際、必ず探索(exploration)と搾取(exploitation)のジレンマが問題となる。
「探索」は多くの情報を集めるように行動することを意味し、「搾取」は今持っている情報を元にした時に最大の報酬が得られる行動をとることを意味する。
長いスパンで考えると、最終的に最も多くの報酬を得るためには、学習の中で最大報酬が一時的に下がる = 最大報酬が得られると考えられる行動以外を取る = 探索する必要がある。
全体として最適な決断を下していくには、対象に関して十分な情報を得なければならない。
探索を行う手法は、以下のように大きく分けて3つある。
- Naive Exploration：greedy policyにノイズを付加する(例：ε-greddy, softmax)
- Optimism in the Face of Uncertainty：最も不確実性が高いアクションを選択するる
- Information State Space：エージェントの持つ情報を状態の一部であるとし、ある状態やアクションを選ぶことがどの程度の情報(価値)につながるかを先読みし、より多くの情報につながるアクションを選択する
Information State Spaceは最も効果的だが、状態が多い場合や学習が進むに連れて計算量が膨大になってしまう。
また、何を探索の対象とするか、という点でも2種類に分けられる。
1つ目は、State-action explorationである。これは、できるだけ多くの状態とアクションを見つけることを目的としており、直感的に理解しやすい。
2つ目が、Parameter explorationである。
方策をパラメータ化($\pi (A|S, \mu )$)し、あるパラメータを試してみて、今度は別のパラメータを試して...というように、異なるパラメータを見つける = 多くの方策を見つけることを目的とする。
Parameter explorationは、固定したパラメータで一定時間学習を行うことで長いスパンでの学習ができる。
しかし、状態とアクションについては一切感知できない(一度訪れた状態かどうかもわからない)ため、ブラックボックス的な環境の中を一般的に最適なパラメータを探すことになる。
対象的に、State-action explorationは環境をより詳細に理解するように動く。
今回は、State-action explorationに絞って学習する。
Multi-Armed Bandits
Multi-Armed Banditsとは
まず、Banditとは、ゲームセンターにある、レバーを引くと当たりか外れが出る古いゲームである。
Multi-armed Banditsを簡単に表すと、Multi-armedなので、たくさんあるBanditのレバーを１つずつ引いて、どのBanditからより高い確率で当たりが出るかを学習していくようなイメージである。
すると、既に知っている中で最も多くの当たりが出るBanditを選ぶか、新しいBanditを試してみるか、という単純な探索と搾取の問題が再現される。
Multi-armed Banditsは、アクションの集合と報酬の集合(タプル$〈A,R〉$)で表される。(状態はない)
Aは全て既知である、m個のアクション(レバーを引くので腕(arm)とも言える)の集合である。
Rは報酬関数であり、報酬の未知の確率分布とも言え、このように表せる。
R^a (r) = P[R = r|A = a]
そして、エージェントは、タイムステップ(t)ごとに１つのアクションを選択する。($a_t \in A$)
エージェントのアクションを受け、環境は報酬を生成する。($r_t \sim R^{a_t}$)
以上をイメージに直すと、ある一定の時間(t)ごとに全てのBandits(A)から1つ($a_t$)を選びレバーを引いた時の当たり($r_t$)は、$R^{a_t}$の確率分布に従う。
そして、Multi-armed Banditsの目的は、累積報酬$\sum ^t _{T=1} r_t$を最大化することである。
以上より、Multi-armed Banditsは、状態が1つの1ステップMDPと同じものであるとも言える。
後悔
Multi-armed Banditsの学習では、Regret(後悔)という概念を使い、累積後悔の最小化というアプローチを行う。
後悔とは、1ステップあたりの機会損失である。
簡単にいうと、そのステップで取得可能と予測される報酬の中で最大の報酬と実際に取得した報酬の差である。
以上から、累積後悔の最小化 = 累積報酬の最大化ということがわかる。
後悔を実際に定義してみる。
まず、行動価値の定義は、アクション$a$を取った時の報酬の平均とする。
q(a) = E[R|A = a]
最適価値$v_*$は、全てのアクションの中で最善(最大の行動価値を持つ)のアクションの行動価値と等しい。
v_* = q(a^*) = max _{a \in A} q(a)
常に$a^* $を選択すればよいが、それが何かわからないため、より低い行動価値しか持たないアクション$A_t$を選択することがある。
そして、後悔$l_t$とはその行動価値の予測差分となる。(= 機会損失)
ここで、$v_*$を知らないというのは問題なのだが、この問題については後で解決する。
l_t = E[v_* - q(A_t)]
そして、累積後悔$L_t$は1ステップごとの後悔の合計なので、以下のようになる。
L_t = E \Bigl[\sum ^t _{T=1} v_* - q(A_t)\Bigr]
t回アクションを選択し、累積後悔を計算する。
これを繰り返すことで、累積後悔が最小化するように学習していくのである。
ここで、後悔を定義し直すことで、このアルゴリズムの利点と問題点について理解する。
まず、エピソードの中で、あるアクション$a$を選択した回数(count)を$N_t(a)$と定義する。
そして、最適な行動$a^* $と$a$の行動価値の差(gap)を$\Delta a$と定義する。($\Delta _a$ = v* - q(a))
すると、累積後悔$L_t$は、各アクションの$N_t(a)$と$\Delta _a$の関数として定義できる。
\begin{align}
L_t &= E \Bigl[\sum ^t _{T=1} v_* - q(A_t)\Bigr] \\
&= \sum _{a \in A} E[N_t(a)](v_* - q(a)) \\
&= \sum _{a \in A} E[N_t(a)] \Delta _a
\end{align}
この定義からわかることは、このアルゴリズムはgapが大きいアクションを選択する回数が少なくなることを保証するということである。
gapが大きい場合、累積後悔を増やす方向への影響が大きいため、そのアクションを選択する数 = countを少なくするように学習するためである。
反対にまだ大きな問題があることもわかる。それは、$v_* $を知らないということである。
$v_* $がわからなければ、gapの計算ができないため、学習できないことになる。
Naive Exploration
Multi-armed Banditsに、greedyやε-greedyといった方策を採用した場合、累積後悔はどのように変化するのかを確認する。
結論から言うと、greedyやε-greedyを採用した場合、累積後悔は線形的に増加していく。
理由は簡単で、greedyは常に知っている行動価値の中から最大のものを選ぶだけなので(一切探索しない)、どんなに時間をかけても最適な行動を学習できない。
反対にε-greedyは一定の割合で常に探索し続けるため、累積後悔は一定の割合で増加し続けることになる。
それぞれをより詳しく確認する。
まずgreedyである。
ここでは、各アクションをの価値をそのアクションの結果として得た報酬の平均と想定する($Q_t(a) \approx q(a) $)、シンプルなMonte-Carlo evaluationを想定する。
Q_t(a) = \frac{1}{N_t(a)} \sum ^T _{t=1} 1(A_t= a) R_t
greedyでは、最も価値の高いアクションを選択する。($A_t = max_{a \in A} Q_t(a)$)
そのため、永遠に現在の予測価値は低いが情報の乏しいアクションを選択するような行動はせず、永遠に局所解にとどまることになる。(同じ間違いを繰り返すようなイメージ)
そのため、greedyを採用した場合、累積後悔は線形に増加し続ける。
greedyな方策の改善として、Optimistic Initialisationをgreedyに適用してみる(Optimistic greedy)。
まず全アクションの中で最大価値を予測し、その値で全ての価値を初期化する。($Q(a) = r_{max}$)
そして、greedyにアクションを選択するだけである。($A_t = max_{a \in A} Q_t(a)$)
このアルゴリズムの良い点は、未知の価値集合の中でも探索を推奨できることである。
しかし、同時にたまたま悪い結果が重なったが、実は良い価値を持つアクションは、永遠に選択肢から外されてしまう。
その結果、Optimistic greedyも、線形的に累積後悔を増大させることになる。
次にε-greedyについて考える。
ε-greedyは、一定の割合で永遠に探索を続ける。
1-εの割合で、$max_{a \in A} Q_t(a)$を選択肢、εの割合でランダムなアクションを選択する。
εの値は永遠に変わらないため、εの割合だけ一定の後悔を生み出し続けることになる。
l_t \geq \frac{\epsilon }{A} \sum _{a \in A} \Delta _a
ε-greedyの問題点は、常に一定の割合で探索を行うことが原因だった。
しかし、探索を全くしなければ最適なアクションを永遠に見つけることができない(greedy)。
そこで、学習を進めると同時に探索の割合(ε)を小さくするアルゴリズム(Decaying-$\epsilon _t$)について考察する。
ここでは$v_* $を既に知っていることを前提にする、最もシンプルなアルゴリズムについて考える。(数式はあくまで1つのパターンのため重要ではない)
各ステップを実行するごとに、全てのアクションごとのgapを計算し、gapが最小となるアクションdを求める。
d = min_{a|\Delta _a > 0} \Delta _a
ここでdは、最適なアクションに最も近い価値を持つアクション = 2番目に良いアクションとなる。
dを使って、タイムステップtごとの$\epsilon _t$を計算する。(cは0以上であり、自分で適切な値を選択する必要がある)
\epsilon _t = min \bigl( 1, \frac{c|A|}{d^2 t} \bigr)
このアルゴリズムでは、累積後悔が線形的に増加するのではなく、対数漸近的な線を描く。
しかし、これでゴールとはならない。
ここでも、gapを使っている = $v_* $(答え)を事前に知っている必要がある。
そこで最終的なゴールは、答えを知らずに学習でき、劣線系な累積後悔を達成するようなアルゴリズムを見つけることとなる。
Upper Confidence Bound
次にUpper Confidence Boundについて学ぶが、そのための準備として、先にlower bound(下界)とOptimism in the Face of Uncertaintyについて学習する。
下界
Bandits問題の前提として、累積後悔には下界が存在し、下界に近づくほどより良いアルゴリズムと言える。
まず、累積後悔の下界を求めるために、Bandits問題の難しさについて考えてみる。
Bandits問題の難しさは、最適なアクションとその他のアクションの価値の差の大きさによって決まる。
差が大きければ簡単に学習ができ、差が小さければ学習は難しくなる。
また、報酬関数は確率分布であるため、各アクションが似たような確率分布である場合にも学習は難しくなる。
以上より、学習の難しさはgap($\Delta _a$)と報酬関数の類似具合(KL情報量($KL(R^a|R^{a^*})$))によって決定される。
これを具体的な定理として表したのが、以下である。(Lai and Robbinsによって1985年に紹介された)
\lim_{t \to \infty} L_t \geq \log t \sum_{a|\Delta _a > 0} \frac{\Delta _a}{KL(R^a|R^{a^*})}
$\sum $以降は、問題の難しさを表している。
分子である$\Delta _a$が大きいほど困難さは増し、分母のKL情報量は確率分布同士の距離とも言えるため、小さければ小さいほど、問題の難しさは大きくなる。
そのため、上記の式は「ステップ数を無限に取った時、漸近的な累積後悔は、必ずステップ数と難しさを掛けた値の対数以上となる(= 下界)」ことを表している。
Optimism in the Face of Uncertainty
Optimism in the Face of Uncertaintyの主要な考え方は、現在分かっている最適なアクションではなく、最適となる可能性があり(optimism)、価値についての不確かさ(uncertainty)が大きいアクションを次に選択するということである。
アクションによる平均値(現在予想している行動価値)を頂上とした正規分布として考えた場合、急な山となっているアクションは既に価値について一定の確かさを持っており、平坦な山となっているアクションは価値についての不確かさが大きい。
イメージとしては、平坦な山のアクションを選択し、徐々に幅を狭めて急な山にしていく作業のようなものとなる。
Upper Confidence Bounds
Upper Confidence Bounds(UCB)とは、山の頂上をそのアクションの予測価値として考えた時、頂上から上方の値を取る尾の部分の値の範囲を表す。(統計学の信頼区間の片側みたいなもの)
UCBをどのくらい先まで取るのかは、信頼する確率(95%など)と分布による。
平坦な山なら尾の先っぽは削られ、急な山であればほとんど山の半分と同じ形が切り出される。
次にアルゴリズムについて確認する。
まず、各ステップごとに、UCB($U_t (a)$)を各アクション(行動価値)について予測する。
この時、本当の行動価値$q(a)$が予測値$Q_t (a)$と$U_t (a)$を足し合わせた値よりも高くなる可能性は、とても小さいことが明らかであるため、その値をそのアクションの行動価値の取りうる最大値とみなす。
また、UCBはそのアクションを選択した回数$N(a)$によって変わる。
$N_t(a)$が小さい時、そのアクションの行動価値は不確かであるため、$U_t (a)$は大きくなる = 山が平坦である。
$N_t(a)$が大きい時、そのアクションの行動価値の予測値は正確であるため、$U_t (a)$は小さくなる = 山が急である。
そのため、そのアクションを選択する回数が増えれば増えるほど、$Q_t (a)$と$U_t (a)$を足し合わせた値と$Q_t (a)$が近くなっていく = $U_t (a)$が0に近づく。
次に、予測値$Q_t (a)$とU_t (a)を足し合わせた値が最も大きなアクションを選択する。
A_t = argmax_{a\in A} \: Q_t (a) + U_t (a)
これは、正にOptimism in the Face of Uncertaintyのアイディアを再現していることがわかる。
次に、UCBをどのようにして得るのかということを考慮する。
そのために、まず以下のHoeffdingの不等式について学習する。
この不等式の前提として、[0,1]の間の数値をランダムにt回サンプリングし($X_1, \cdots ,X_t$)、$\bar{X}_t$はサンプルの加算平均とする($\bar{X} _t = \frac{1}{t} \sum ^t _{T=1} X_T$)。
P [E[X] > \bar{X} _t + u] \leq e^{-2tu^2}
左辺は、サンプルの平均値にある値uを足したものが、Xの期待値よりも小さくなる確率を表している。
そして、$E[X]$を$q(a)$、$\bar{X} _t$を$Q_t (a)$、uを$U_t (a)$に置き換えることで、Bandits問題の報酬に適用することができる。(報酬は0から1の間にする)
P [q(a) > Q_t (a) + U_t (a)] \leq e^{-2N_t(a)U_t (a)^2}
この時、右辺は$Q_t (a)$と$U_t (a)$を足し合わせた値よりも$q(a)$が大きくなる確率(pと置く)を表している。
e^{-2N_t(a)U_t (a)^2} = p \\
U_t(a) = \sqrt{\frac{- log \: p}{2N_t(a)}}
上の式より、アクションaを選択する回数$N_t(a)$が大きくなればなるほど、$U_t(a)$が小さくなることがわかる。
そして次に、タイムステップを重ねるごとにpを小さくする。(例えば$p = t^{-4}$)
これは、タイムステップを重ねることで$U_t(a)$が小さくなることに合わせ、$U_t(a)$の範囲を広げることを意味する。(例としては、95%から初めて100%に近づけていく)
その結果、タイムステップを無限に試行した場合($t \rightarrow \infty$)、以下の式を得る。
U_t(a) = \sqrt{\frac{2 \: log \: t}{N_t(a)}}
これを先ほどのアクション選択の式に代入するとこのようになる。
A_t = argmax_{a\in A} \: Q_t (a) + \sqrt{\frac{2 \: log \: t}{N_t(a)}}
これは、UCB1と呼ばれるアルゴリズムである。
式を再度確認すると、計算に必要なのはタイムステップtとアクションaを選択した回数$N_t(a)$だけである。
UCBを使ったアルゴリズムをLai and Robbinsの定理に当てはめて確認すると以下のようになり、累積後悔が対数関数の漸近線となることが示される。
\lim_{t \to \infty} L_t \leq 8\log t \sum_{a|\Delta _a > 0} \Delta _a
Bayesian Bandits
今までは確率分布の予測を使ったアプローチについて学習してきた(頻度主義統計)。
次にベイズ的な手法を使ったアプローチについて学習する(ベイズ統計)。
今までは報酬関数Rについての情報を一切持たない状態から学習を始めた。
ここでは、事前にRについて何らかの情報$p[R^a]$を持っていると仮定し、それを活用することで学習する方法について考える。
Bayesian Banditsは、パラメータwによってパラメータ化された行動価値関数Qの分布$p[Q|w]$を保持し、wを更新することで学習する。
正規分布の場合、wはアクションごとの平均値と分散となる。(アクションを[1,k]とすると、$w = [\mu _1, \sigma ^2 _1, \cdots , \mu _k, \sigma ^2 _k]$)
正規分布で平均と分散が分かっているということは、今まで見てきた確率分布の山の情報を持っていることになる。
以上より、Bayesian Banditsは事後分布を使ってアクションを選択して学習することになる。($p[w|R_1, \cdots , R_t] $)
事後分布を使って探索を行う方法は2つある。
1つは先ほど学習したUCBを使う方法、もう1つはProbability matchingと呼ばれる手法である。
そして、Bayesian Banditsの学習効率は、事前情報の正確さに大きく左右される。
Bayesian UCB
UCBを使う方法は、ベイズの定理を使ってパラメータwの事後分布$p[w|R_1, \cdots , R_{t-1}] $を計算する。
そして、ベイズの定理を使ってwの事後分布からQの事後分布を計算する。
p[Q(a)|R_1, \cdots , R_{t-1}] = p[Q(a)|w] p[w|R_1, \cdots , R_{t-1}]
そして、$p(Q(a)|w)$の標準偏差$\sigma (a)$からUCBを予測する。($U_t(a) = c\sigma (a)$、cは任意の定数)
あとは、以前確認した通り、$Q_t(a) + c\sigma (a)$が最大値となるアクションを各タイムステップで選択する。
Thompson Sampling
次にProbability matchingを使った方法について学習する。
Probability matchingは、アクションの選択を、そのアクションが最適なアクションである確率によって選択する。
\pi (a) = P[Q(a) = max_{a'} \hat{Q} (a')|R_1, \cdots , R_{t-1}]
これの良い点は、不確かさが高いアクションは最適である確率が高くなるので、Optimism in the Face of Uncertaintyを自動的に満たすことになることである。
Bandits問題を解くアルゴリズムで最も古く、しかし効果的なThompson samplingという手法は、サンプルを元にしたProbability matchingを採用している。
\pi (a) = P[1(Q(a) = max_{a'} \hat{Q} (a'))|R_1, \cdots , R_{t-1}]
まず、Bayesian UCBを同じようにベイズの定理を使って事後分布を計算する。($p_w (Q|R_1, \cdots , R_{t-1})$)
次に、各行動価値関数($Q(a)$)の事後分布から1つづつランダムにサンプルを取得し、その中でもっとも価値が高い = 最適な行動に近いと考えられるアクションを実行する。($A_t = argmax_{a \in A} \, Q(a)$)
シンプルな手法であるが、Bayesian UCBで必要だった偏差に掛け合わせるパラメータなどは、Thompson samplingには必要ない。
そして、Banditsの確率分布がベルヌーイ分布に従う時、Thompson samplingはlai and Robbinsの定理の累積後悔の下界を取ることができる。
Information State Search
今まで、ランダムに選択する手法、UCBを使う手法、ベイズ的な手法を学んだが、次にInformation State Spaceを利用した探索法を学習する。
情報の価値
探索は新しい情報を収集できる。
その情報の価値とは何で、その価値を定量的に測ることはできないか。
もし、情報の価値を定量的に測ることができれば、より高い価値を持つ情報を優先的に取得することでより効率的に学習ができるようになる。
ここで価値は、その探索を行うことで、将来的にどのくらいの報酬に繋がるのかということである。
価値に影響するのは、その情報を得るためにどのくらいの報酬を犠牲にするかに左右される。
言い換えると、情報取得後の長期的な累積報酬と即時報酬を比較することになる。
あるアクションaは100の報酬がもらえることがわかっており、もう1つのアクションbは70の報酬がもらえると予想しているとする。
もし、残りの試行回数が3回しかない場合、aを実行する(搾取)ことがより良い選択となるのは明白である。
bがより良い報酬をもらえるアクションとわかったところで、bを選択する回数はもう残っていないからである。
もし、残りの試行回数が100万回の場合、bを実行する(探索する)価値はより高くなることになる。
また、情報はより不確かな状態から多く取得できる。
もし情報の価値を知っているのであれば、探索と搾取のトレードオフを最適に行うことができる。
Information State Space
ここで、Bandits問題を1ステップMDPとして定義し直す。
このMDPの構成要素について確認する。
まず、今まで蓄積した全情報を集約するinformation state($\tilde{S} $)が各ステップに存在する。
例えば、今までアクションaを5回、アクションbを7回実施したといった情報である。
そして、アクションAを実行することで新たな情報が手に入る。
新しい情報を入手するということは、ある確率で新しいinformation state($\tilde{S'} $)に遷移するということを意味する。($\tilde{P} ^A _{\tilde{S} , \tilde{S'} } $)
先ほどの例では、アクションbを新たに実施した場合、{アクションa：5回、アクションb：7回}から{アクションa：5回、アクションb：8回}というinformation stateに遷移する。
以上より、このMDPは、以下のように表せる。
\tilde{M} = 〈\tilde{S} , A, \tilde{P} , R, \gamma〉
最もシンプルな例でこのMDPを確認する。
Bernoulli Banditsを想定するが、これは全てのbanditがベルヌーイ分布に従うことを想定する。
あるbanditのレバーを引くことをアクションaと置くと、報酬関数は$R^a = B(\mu _a)$と表せる。
これは$\mu _a$の確率で当たり(1)が出て、それ以外の場合$1 - \mu _a$は全て外れ(0)となることを意味する。
そのため、学習の目的は、より高い$\mu _a$を持つアクションを見つけることになる。
ここでinformation state($\tilde{S}$)は、$〈\alpha , \beta 〉$と表せる。
$\alpha _a$はアクションaを実行し報酬が0だった回数、$\beta _a$はアクションaを実行し報酬が1だった回数を表す。
Bayes-adaptive Reinforcement Learning
Bandits問題をinformation stateによって構成される、無限MDPと考えることで、RLによって解くことができるようになる。
例えば、Model-Free RLのQ学習やベイズ的アプローチをModel-Based RLに適用した(Bayes-adaptive RL)Gittins indicesなどである。
Bayes-adaptive RLは、information statesを事後情報によって特徴付けすることが特徴である。
Gittins indicesは、Dynamic Programmingのアルゴリズムをinformation stateに適用したものである。(DPのため、遷移確率や報酬についての情報を持っている)
ここでもBernoulli Banditsを想定して、Bayes-adaptive RLの学習例を確認する。
まず報酬関数$R^a $の事前情報として、$Beta(\alpha _a, \beta _a)$を持っており(探索木の根となるノード)、そこから学習を開始する。(aは各アクション)
アクションaを実行するたびに$R^a $に対する事後分布は変化する。
もしアクションaの実行によって得た報酬が0であれば、$Beta(\alpha _a + 1, \beta _a)$、
もしアクションaの実行によって得た報酬が1であれば、$Beta(\alpha _a, \beta _a + 1)$となる。
事後分布の変化 = information stateの遷移となるため、これをBayes-adaptive MDPの遷移関数$\tilde{P}$と定義できる。
これらによって探索木が構成でき、現在の状態から先読みして探索木の最適なパスを探し出していく。
各information state($〈\alpha , \beta 〉$)はモデル$Beta (\alpha, \beta)$に相当し、各information
stateの遷移はモデルの更新と考えることができる。
以上より、新しい情報の影響がモデルの更新の要因として含まれていることが分かるため、このBayes-adaptive MDPを解くことは、情報価値を考慮に入れた探索を行うと考えることができる。
また、Gittins indicesではDPを使って探索を行うが、MCTSなどの他のプランニングアルゴリズムにも適用可能である。
Contextual Bandits
今まで学習した、Multi-armed Banditsをはアクションの集合と報酬の集合(タプル$〈A,R〉$)で表された。
Contextual Banditsでは、そこにSが追加され、$〈A,S,R〉$)で表される。
Sは未知の状態分布であり、$P[S]$とも表せる。(これをcontextsとも言う)
Rは、報酬に関する未知の確率分布であり、SとAに依存する。($R^a _s (r) = P[R = r|S = s, A = a]$)
各タイムステップtにおいて、環境は状態を生成し($S_t \sim S$)、エージェントはアクションを選択する($a \in A$)。
そして、アクションの結果から環境はエージェントに報酬を与える($R_t \sim R^{A_t} _{S_t}$)。
学習の目的は、いつも通り累積報酬の最大化である。
Contextual BanditsをLinear UCB(Linear Function ApproximatorをUCBに適用)で学習する例については、講義資料を参照。
MDPへの適用
今回学んだ探索と搾取のアルゴリズムをどのようにRLに取り入れるかという問題について考える。
Model-Free RLとUCBの組み合わせについて考えると、UCBが最大のアクションを選ぶように学習すれば良いだけである。
A_t = argmax_{a \in A} Q(S_t, a) + U_t(S_t, a)
しかし、これは不完全なものである。
RLでは、現在の方策を行動価値関数の更新によって評価し、より良い方策に更新することで、行動価値関数はさらに良くなっていく。
そのため、行動価値関数の不確かさだけを考慮するのではなく、方策の更新による不確かさも考慮しなければならないが、この方法では方策の更新についての不確かさは考慮できていないのである。
この問題を解決するのはとても困難である。
Model-basedアルゴリズムとoptimism in the face of uncertaintyの組み合わせは、良いアプローチとなる。
まず、問題となるMDPのモデルを構築する。
構築にあたり、まだ未知の状態や学習が進んでいない状態の価値関数を報酬の最大値とする。
そして構築した(optimisticな)MDPを、プランニングアルゴリズムによって解く。(RMaxアルゴリズムなどがある)
最後に、Information State SpaceをMDPに適用する。
この方法としては、従来の状態Sにinformation stateを加えて$\tilde{S} = 〈S, I〉$とすることで、MDPを拡張する。
SはMDPを元から構成する状態、Iは蓄積された情報である。
この拡張されたMDPはとても複雑で膨大な状態空間を必要とするが、RLのアルゴリズムに組み込むことが可能である。
例えば、MCTSに組み込んだ場合、とても効率的であることがわかっている。
また、この拡張されたMDPを解くことは、探索と搾取のバランスにおいて最適な学習が可能になる。
最後に
社会人になって再学習したとはいえ、数学を高校2年でやめた、強化学習独学の文系人が書いているので、間違っているところも多いと思います。
間違いを見つけた際には、私自身の学びのためにも、ご指摘いただけると大変ありがたいです。
参考資料
An Introduction to Reinforcement Learning(訳本は出版されてますが、有料です)
http://incompleteideas.net/book/bookdraft2017nov5.pdf
Algorithms for Reinforcement Learning
https://sites.ualberta.ca/~szepesva/papers/RLAlgsInMDPs.pdf