多腕バンディット問題とUCB

スポンサードリンク

多腕バンディット問題とUCBアルゴリズム

多腕バンディット問題というと
頭が痛くなりそうなので…簡単に解説します。

 

簡単に言うと
スロットマシンが複数台あった時にどのマシンが一番報酬が多いのかを探る方法です。
多腕バンディット問題とUCB

探る方法

皆さんなら次のような場合はどうしますか。

設定
コインが1,000枚あるとします。
スロットマシンが5台あるとします。

 

方法1:均等に200枚ずつ

方法としてまず考えられるのが
均等に200枚ずつコインを使う方法です。

 

でもこれでは全然だめですね。
統計を使えばもっとよくなります。

 

方法2:最初に50枚だけ使ってみる

最初に50枚ずつコインを使ってみて、
良かったマシンに残りの750枚を使う。

 

そうすれば、
もしかすると方法1よりも良い結果になるかもしれません。

 

方法3:UCBというものを使う

学術的にUCBというマシンの選択方法があります。
方法2をもっと細かく見ていく方法だと思ってください。

 

ちょっとずつ検証していくイメージです。

 

例えば、全マシンに1回ずつ試した場合は検証回数が全然足りませんよね?
ですので、何回か試してやるわけです。
【探検】といいます。

 

ある程度試すと、そのマシンの傾向が見えてきます。
ですので、統計的にみて沢山コインを出してくれるマシンを優先的に回す。
【収穫】といいます。

 

これを
【収穫と探検のジレンマ】といいます。

 

聞いたことありませんか?

 

この問題を解決するための数学式がUCBだと思ってください。

 

【続き】UCT探索

スポンサードリンク

多腕バンディット問題とUCB関連ページ

モンテカルロ法
天頂の囲碁、銀星囲碁、最強の囲碁の3つの囲碁ソフトが使っているモンテカルロ法について解説します。
思考ゲームへの応用
コンピュータ囲碁へのモンテカルロ法の応用方法を紹介します。
強くなった理由
モンテカルロ法を使用して、コンピュータ囲碁が強くなった真の理由を歴史と共にお話します。
UCT探索
コンピュータ囲碁におけるUCT探索について簡単に紹介します。
学習によるシミュレーション改良
コンピュータ囲碁(モンテカルロ法)の改良として学習によるシミュレーションの改良などが行われています。ELOレーティング・Bradley-Terryモデル・パターン学習など。
並列化
コンピュータ囲碁の並列化に関する簡単なお話です。
定石データベース・詰碁探索
コンピュータ囲碁に使われている定石データベースや詰碁探索についてお話します。

logo logo logo