ゆるふわめも

東京か京都にいます。

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

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

前回

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

Contextual Bandit

スライド

www.slideshare.net

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

説明

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

各アルゴリズム外観

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

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。