Multi armed bandits 多臂老虎机

首先来定义模型（model）：

个臂（arms）：，对每个臂 有 ，其中 对参与人未知：

不失一般性，假设：

多臂老虎机问题的求解思想就是通过不断地尝试慢慢发现最好的臂

• 目标（Goal）：找到最好的臂，这是 与 之间的权衡的优化
• 悔值最小化（Regret minimization）：总共的奖励最小化
• 
• 这里的 是 horizon， 是在时间 根据策略 选择行动
• 问题：，最小化 等价于：
• 

---

下面介绍 -Probably Approximate Correct（PAC）算法

目标：令 为由算法返回的臂，希望有：

均匀采样（uniform sampling）

1. 拉每个臂 次
2. 返回
   这里 指的是经验均值

场景1：
场景2：

正确性（Correctness）：

Hoeffding's inequality
假设 ，彼此独立，则

所以根据 union bound，得：

当该事件发生时，令 ，有

采样复杂度（sample complexity）：
lower bound：

---

Exploration-and-commit for regret minimization

算法：

1. US 纯探索，参数为 和 （探索步 exploration step）
2. 持续拉臂直到时间 （开发步 exploitation step）

分析：

total 悔值：
取