探索と活用のトレードオフ

この記事では、探索と活用のトレードオフ(exploration-exploitation trade-off)と呼ばれる、強化学習において重要な考え方を説明します。

多腕バンディット問題

多腕バンディット問題(multi-armed bandit proble)とは、複数のスロットマシンから、どれか1つのスロットマシンのアームを選んで報酬を受け取る操作を複数回実行するときの、最適なスロットマシンの選択方法(=行動方法)について考えた問題です。

スロットマシン

多腕バンディット問題の説明の前に、スロットマシンについて説明します。

スロットマシン(下図)は、様々な絵が描き込まれているリールと、それを回転させるアームから構成されていて、3つのリールが停止したときに、どの絵が出たかに依存して、得られる報酬が異なるゲーム機です。プレイヤーは、アームを引く操作のみが実行可能で、スロットマシンは、内部にもつ報酬の確率分布に従って確率的に報酬を出力します。

多腕バンディット問題

それぞれ、スロットマシンには報酬の確率分布があります。ここで、以下の図のように、3つのスロットマシンA、B、Cを考えます。それぞれ、報酬の確率分布は異なります。

説明で使用するスロットマシンは、+1、+2、+3の3種類の報酬を出力するものとし、マシンAは、確率0.5で+1の報酬を、確率0.4で+2の報酬を、確率0.1で+3の報酬を出力するような確率分布を持つものとします。マシンB、マシンCが持つ報酬の確率分布は図の通りです。

ここで、次のような問題を考えます。

スロットマシンから得られる報酬の確率分布を知らないプレイヤーが、1回のゲームで引くことができるアームは1つだけという制約のもと、100回のゲームをプレイした後における総収益を最大化するようなスロットマシンの選択方法を獲得したい。

確率分布が既知のとき

先に、報酬の確率分布が既知の場合について、最適なスロットマシンの選択方法について説明します。最適な選択方法は、各スロットマシンから得られる報酬の期待値を計算して、期待値が最大のスロットマシンを選び続けることです。図のような期待値を仮定したときの各スロットマシンの報酬の期待値は以下のようになります。

マシンAの報酬の期待値： 0.5×(+1)+0.4×(+2)+0.1×(+3)=1.6
マシンBの報酬の期待値： 0.3×(+1)+0.4×(+2)+0.3×(+3)=2.0
マシンCの報酬の期待値： 0.2×(+1)+0.7×(+2)+0.1×(+3)=1.9

よって、最適な選択は、マシンBを選び続けることです。

確率分布が未知のとき

各スロットマシンの報酬の確率分布が未知のとき、どのスロットマシンを選択するのが最適か分からないため、選択方法のルールを考える必要があります。

最初は、ランダムに動いてみることにします。このとき、結果として得られた報酬は経験としてプレイヤーは内部に持っておくことができるとします。100回のうち1回目はマシンAを選んで、アームを引きました。このとき、+3の報酬が得られました。さて、プレイヤーは、マシンAから報酬+3が獲得できることを学んだわけですが、この経験を利用して、残りの99回全てにおいて、マシンAのアームを引くべきでしょうか、それとも、マシンBやCを試すべきでしょうか。

この問題のように3台しかない場合は試すべきでしょう。なぜなら、マシンAから得られる報酬の期待はBやCに比べて小さい上、100回試す前に、統計的に、各マシンから得られる報酬を予測できるようになり、最適なマシンの選択ができるようになるからです、

マシンAは、偶然、確率が低い報酬+3を出力したのですが、何回か試行すれば、マシンAからの+3の報酬が稀であることが学習されるでしょう。

2回目には、マシンBのアームを引くことにしました。このとき、+2の報酬が得られました。3回目は・・・と続きます。

もし、スロットマシンが100台あったらどうでしょうか。100回しかアームを引け中で、100台全てを試すのは適切でしょうか？

この場合は、一度もアームを引いていないマシンを試すのではなく、得られた報酬の経験に従って、過去に引いたマシンを再度選択する方が、賢い選択と言えるでしょう。

ここで言いたいことは、総収益を最大化するには、

高い報酬を出す確率が高いマシンを探索する必要がある
過去の経験を活用し、高い報酬が得られたマシンを再選択する必要がある

ということです。探索ばかりだと、高い報酬を出す確率が高いマシンに出会えなかった場合に、総収益が最大になりません(=過去の経験を活用すべきだった)。また、過去の経験ばかりを活用して、探索を行わなければ、過去に使用したマシンより、高い報酬を出す確率が高いマシンが仮にあったとしても、それを利用できないので、総収益は最大になりません(=探索すべきだった)。これは、トレードオフの関係にあり、探索と活用のトレードオフと呼ばれます。