老虎机是赌场常见设备，每次摇动都可能后悔或者获得一定额度的奖励。可以选择不同的老虎机臂最大化自己利益，属于强化学习问题reinforcement learning。

问题描述

假设有一个K臂老虎机，每一个臂(action)的回报率(reward)固定，但是agent并不知道这个回报率，如何在T回合内最大化自己的回报。（T>>K）

应用

广告投放，用户对每一个广告有固定的点击率，平台需要选择最优策略来显示广告，达到最大收益。

方法

image.png

exploitation&&exploration

仅利用exploitation-only
使用到目前为止最优到摇臂，action1

仅探索exploration-only
所有尝试机会给每个摇臂；吧每个摇臂各自吐币概率作为奖赏期望到近似估计

ϵ-greedy策略
有1-ϵ概率使用纯贪婪算法；
有ϵ概率使用探索策略
缺点：上图act1效果远远好于act2，仍然用一定概率探索act2

Thompson Sampling
将每一个action看为beta分布，给定先验概率参数alpha和beta
beta分布性质，当观察次数增多，分布的置信区间越窄

Thompson Sampling

变种：

1 需要做先验估计，可以预先对分布做估计，再利用Thompson采样
2 非平稳过程：a利用最新数据建模；btime decay方法
3 上下文特征：对先验建模，结合ts实验
4 RL方法

参考

1 https://lilianweng.github.io/lil-log/2018/01/23/the-multi-armed-bandit-problem-and-its-solutions.html
2 http://kuaibao.qq.com/s/20180209G067E900?refer=cp_1026
3 多臂赌博机与TS.pdf