めも

メモ.

バンディットアルゴリズムの復習4:Contextual Bandit

書きかけ、後ほど各アルゴリズムの説明や実験など追加予定。 →水曜夜あたり→土日あたり

前回

UCB,その前はε-greedy+softmax。

Contextual Bandit

スライド

www.slideshare.net

リクルートの方のスライド。

説明

それぞれのアーム・もしくはアームを引く人に特徴ベクトルがついた multi-armed bandit problem と見て取れる。問題設定の積報酬の最大化はこれまでと同じ。アイテムのレコメンドの文脈では 商品=アーム、ユーザー=アームを引く人(それぞれが年齢などのコンテクストを持つ)といった形式。

時刻tにk個の行動を選択する環境の下で、コンテキスト(特徴と呼ばれる時もある)X_t が与えられる時のバンディットでありざっくり以下のように書ける。

for t:
  - コンテキストX_tを取得
  - Contextual banditのアルゴリズムに X_t を入力し取るアーム a を決定
  - a を引いて報酬 r を得る
  - (a, r, X_t)を用いてアルゴリズムの内部状態を更新

各アルゴリズム外観

少ししか調べてない+全くの専門外なので漏れがあるかも、という言い訳します。

EXP4

Auer, Peter, et al. "Gambling in a rigged casino: The adversarial multi-armed bandit problem." Foundations of Computer Science, 1995. Proceedings., 36th Annual Symposium on. IEEE, 1995.

Epoch-Greedy

Langford, John, and Tong Zhang. "The epoch-greedy algorithm for multi-armed bandits with side information." Advances in neural information processing systems. 2008.

LinUCB

Chu, Wei, et al. "Contextual Bandits with Linear Payoff Functions." AISTATS. Vol. 15. 2011.

Thompson sampling for Contextual Bandits

Thompson, William R. "On the likelihood that one unknown probability exceeds another in view of the evidence of two samples". Biometrika, 25(3–4):285–294, 1933.

Agrawal, Shipra, and Navin Goyal. "Thompson Sampling for Contextual Bandits with Linear Payoffs." ICML (3). 2013.

HyperTS・HyperTSFB

Tang, Liang, et al. "Ensemble contextual bandits for personalized recommendation." Proceedings of the 8th ACM Conference on Recommender Systems. ACM, 2014.

次回

一旦上記のどれかを実装してから、combinatorial bandits。

プライバシーポリシー

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