n本腕バンディット問題 (n-armed bandit problem)

昼間に @tsubosaka さんが「なんか bandit arm が面白そう」って言っていたのを聞いて、僕は「何かで読んだことあるよな」と思ってました。家に帰って本棚をあさったら「強化学習」の冒頭にありました。

強化学習

[Amazonで詳細を見る]


強化学習は専門ではないので教科書を見ながらメモを書いてみます。


n本腕バンディット問題 (n-armed bandit problem) の原型


目的は貰える合計報酬の期待値を最大化すること。
プレイヤーはn種類の異なる行動選択肢から1つを選択する動作を繰り返す。
各選択の後は毎回、選択した行動に依存する定常確率分布から選ばれた値がプレイヤーの報酬として与えられる。
限られた実行回数の中で合計報酬の期待値の最大化を目指す。

名前の由来


「片腕のバンディット」と呼ばれている一本腕のスロットマシンから。
ただし扱う問題はn本のレバー。

具体例1:プレイヤーが医者の場合


医者は、自らの治療手法の選択によって、患者の寿命の期待値の最大化を目指す。

具体例2:商品の推薦システム


システムは、アイテムを様々な観点でランキングし表示することで、ユーザが表示されたアイテムをクリックする期待値を最大化する。

行動の価値(Value)、の定義


n-armed bandit problemでは、各行動が選択された場合の報酬の期待値・平均値が定まっている。
この値を、価値Valueと呼ぶ。

仮定


行動の価値は、事前に確実に知られているわけではない。とする。
行動の価値が分かっているなら、簡単に合計報酬の期待値の最大化を目指せる。

探査と知識利用


グリーディな行動

行動価値の推定値を常に盛っている場合、どの時点でも価値の推定値を最大とするような行動が少なくとも1つは見つかる。この行動を「グリーディ(greedy)な行動」と呼ぶ。
この場合、行動価値について「現在の知識を利用している」という。

グリーディでない行動

グリーディでない行動を選択する場合、その価値の推定値を改良できる可能性がある。
なので、グリーディでない行動を選択することを「探査(explore)」

探査と知識のバランスをとりたい


バランシングすると、知識利用だけをした場合よりも、はるかに高い性能をだせるようだ。
バランシング自体が興味深い課題のようだ。




ということで、どういう問題の定義なのか少し分かってきました。

システムを運用するときに、こういう手法に関する知見があると、表示内容の適切なランキングとかが出来そう。こういうのを勉強するのは楽しいです。

強化学習は実装をほとんどしたことがないので実装したいです。


投稿者:としのり  日時:23:59:59 | コメント | トラックバック |
blog comments powered by Disqus