読者です 読者をやめる 読者になる 読者になる

強化学習の資料メモ2:多腕バンディット問題

論文・資料・スライド集 機械学習 強化学習 バンディット

Sutton本の2章、多腕バンディット問題関係の資料。 アドテクで使いそうなのでたくさん資料がありそう。

基本の内容

各種定式化

pdf: 知識の探索と活用のジレンマと多腕バンディット問題

この本 の著者である東京大学の本多淳也先生のスライドを参照。つまるところ簡単なバンディット問題は...

  • アームを引いた後に得られる報酬の性質
    • 確率的
    • 敵対的
    • 定常・非定常(アームの確率分布は時間につれて少しずつ変化していく)
  • 目的関数
    • 引いたアームすべてから得られる報酬の和の最大化
    • 期待値がもっとも高いアームの判定(をなるべく少ない回数で決める)
  • その他の拡張
    • linear bandit
    • matroid bandit
    • contextual bandit
    • etc ...

のような分類があって、多分検索してすぐに出てくるのは確率的で期待値がもっとも高いアームの判定をするものが多い印象?

Exploration/Exploitation Dilemma

Deepmindの方の講義映像を下の記事にてリンク。もっとも単純には。いくつかランダムに探索した後で常にもっとも良かったアームばかり引いていては最適なアームを見つけられない。一方で、常に探索しているだけだと損失が大きくなってしまうということ。

paper.hatenadiary.jp

Stationary Problem(定常なケース)

Action-Value Methods

Richard Sutton 氏による資料。

web: 2.2 Action-Value Methods

行動選択の戦略

greedy(貪欲)

最も単純だけどそれなりに強い。 過去の経験から最も良かったアームを常に選択する。

ε-Greedy

貪欲な戦略だと最適解でないのにアームを引き続ける可能性があるから、εの確率でランダムな選択をすることでこれを避けていく。

Soft-max action selection

ε-Greedyの悪い点はランダムに探索するときに残りのアームをすべて同じ確率でランダムに選択してしまうところ。 直感的には、良さそうなアームに割合を多めに振った方がこれまでの履歴から貪欲に選択したアームよりは良いアームがある可能性が高い。 temperatureパラメータを導入して、 temperatureが高いほど「試す価値がある」状態となる。つまり temperature=0だと貪欲法と同じ。

Non-stationary Problem(非定常なケース)

スタンフォードビジネススクールの資料、てかこんなのやるんですね。

Optimal Exploration-Exploitation in a Multi-Armed-Bandit Problem with Non-stationary Rewards | Stanford Graduate School of Business

アームの行動戦略

Gradient-Bandit

確率勾配法をバンディットに当てはめたケース。あまり踏み込まなくても良さそう。

Flaxman, Abraham D., Adam Tauman Kalai, and H. Brendan McMahan. "Online convex optimization in the bandit setting: gradient descent without a gradient." Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 2005.

All Moves As Fist(AMAF)

AMAF について:http://www.yss-aya.com/cgf20080412.html#top9

昔も AMAFとUCBを組み合わせた戦略でコンピュータ囲碁は戦略を組み立てていたとかいないとか。

AlphaGoはUCB+deep learning?

追記:日本語のAlphaGoの解説スライドがありました。ありがたいです。

pdf: http://home.q00.itscom.net/otsuki/20160415AlphaGopublic.pdf

Upper Confidence Bound (UCB) action selection

時間が経つほど探索を少なくしていく、各行動の後の報酬のupper boundを予測してupper boundが最大になるような行動を選択する手法。このupper boundが最大というのは「あまり良くわかっていない腕を積極的に試していく」とも取れる。

追記:A/Bテストよりすごい?バンディットアルゴリズムとは一体何者か - Qiita

次回

paper.hatenadiary.jp


バンディット問題の理論とアルゴリズム (機械学習プロフェッショナルシリーズ)

バンディット問題の理論とアルゴリズム (機械学習プロフェッショナルシリーズ)