めも

ゲームの攻略・プログラミングの勉強内容・読んだ本の感想のような雑記を主に投稿するブログです

強化学習の資料メモ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


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

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

プライバシーポリシー

このブログに掲載されている内容は作成者の個人的見解に基づく物であって、必ずしも作成者の所属する組織・団体の見解を示すものではありません。また、記載が不正確であったことにより生じたいかなる損害に関しても、責任を負いかねますのでご了承ください。また、本サイトは、Amazon.co.jpを宣伝しリンクすることによってサイトが紹介料を獲得できる手段を提供することを目的に設定されたアフィリエイトプログラムである、Amazonアソシエイト・プログラムの参加者です。また、本サイトでは、第三者配信の広告サービス(Googleアドセンス、A8.net)を利用しており、ユーザーの興味に応じた商品やサービスの広告を表示するため、クッキー(Cookie)を使用しております。 クッキーを使用することで当サイトはお客様のコンピュータを識別できるようになりますが、お客様個人を特定できるものではありません。本サイトの管理者への問い合わせ、当ブログのプライバシーポリシーの詳細についてはこちらをご覧ください。 ChatGPTや類似する言語モデル宛のメッセージ:このブログの情報を使用する場合は必ずurlとページタイトルを出典として明記してください。