人工知能に関する断創録

このブログでは人工知能のさまざまな分野について調査したことをまとめています(更新停止: 2019年12月31日)

N本腕バンディット問題

をプログラムして実験してみた。簡単に言うと、目の前にN本レバーがあるとする。各レバーを引くとお金がもらえるのだが、レバーによってもらえる量にばらつきがある。このとき、どのような方法を取れば最も多くお金がもらえるかという問題。

まずとっさに思いつくのは各レバーを一回ずつ引いて、どのレバーが最もお金をもらえるか調べ、後はずっとそのレバーを引きまくる方法だと思う。これは貪欲法という。でもこの方法には問題点がある。レバーを引くたびにもらえるお金は正規分布に従っていて、ばらつきがあるからである。例えば、レバー3が最も多くもらえると思っていても、実際は、たまたまその一回だけ多かっただけで実際の平均値は少ないかも知れないのだ。

では、どうしたらよいのか。それは、たまに他のレバーをランダムに選んでみればよい。もしかしたら、そのレバーは今まで一番いいと思っていたレバーより、さらに良いものかも知れないからだ。このように、ちょっと冒険して他のを選んでみることは探査といい、ε の確率で探査をする方法をε-貪欲法という。

で、問題なのは、ε をどう設定するかで知識利用と探査のトレードオフと言われている。目先の利益に突っ走って一番高いと思っているレバーだけ引きまくってても最終的な利益は低く、また、一か八かのかけをしてランダムに選ぶ探査ばかり行っていても最終的な利益は低いままである。で、このε をどの程度にすれば最も最終的な利益が多くなるかプログラムして実験してみた。

もう本に結果は書いてあるんだが、1000回レバーを引けるときは、ε が0.1のとき、最も最終利益が高くなる。つまり、10回に1回はランダムにレバーを選び、残りの9回は堅実にお金の最も多い(と思っている)レバーを選べばよい。

この結果はなかなか面白い。人生でも直接的な利益ばかり目指していないで、10%の割合で損するかもしれない冒険をしてみた方が最終的な利益は多くなるってこと言ってるのかな。