论文笔记——Thompson Sampling for Contextual Bandits with Linear Payoffs(线性收益)
Thompson Sampling for Contextual Bandits with Linear Payoffs(线性收益)
参考论文：
Agrawal S , Goyal N . Thompson Sampling for Contextual Bandits with Linear Payoffs[J]. 2012.
摘要
有关Thompson Sampling理论性能的许多问题仍未解决
本文设计和分析
- Thompson Sampling algorithm
- 随机 contextual multi-armed bandit 问题（上下文信息由自适应的adversary提供）
- 线性收益函数
Introduction
MAB问题主要用于为许多顺序决策问题中固有的勘探/开发权衡建模。
1. contextual MAB
在这个问题中，在每轮T轮中，一个learner会从N个action中选择一个最好的，N个action称为N个arms。
在选择要哪个arms之前，learner会看到与每个arm i相 关联的d维特征向量bi，称为“上下文”。
learner将这些特征向量与她过去使用过的arm的特征向量和reward一起使用，以选择在当前回合中要选择的arm。
随着时间的流逝，learner的目标是收集有关特征向量和reward如何相互关联的足够信息，以便她可以确定地通过观察特征向量来预测哪条arm可能会提供最佳reward。
learner与一类预测变量竞争，其中每个预测变量都接受特征向量并预测哪条arm会获得最佳回报。如果learner可以保证在事后预测中所做的工作与最佳预测者的预测几乎一样（即，regret很低——用于评判该learner（算法）的有效性），那么该learner可以成功地与该类竞争。
pridictor由d为参数
μ
ˉ
\bar{\mu}
μˉ来定义，然后根据
b
i
T
μ
ˉ
b_{i}^{T} \bar{\mu}
biTμˉ来将arms排序
即：假设有个未知参数
μ
\mu
μ，则每个arm对应的reward为
b
i
T
μ
ˉ
b_{i}^{T} \bar{\mu}
biTμˉ，学习者的目标就是学习该未知参数
μ
\mu
μ
2. Thompson sampling(TS)
基本思想是：假设每个arm的reward分布的基础参数具有简单的先验分布，并且在每个时间步长，根据该先验分布成为最佳arm的后验概率来选择arm
主要包含以下参数：
- 一组参数 μ \mu μ
- 关于这些参数的先验分布 p ( μ ˉ ) p(\bar{\mu}) p(μˉ)
- 过去的观察结果D，由t-1时刻的上下文b，奖励r组成
- 似然函数
P
(
r
∣
b
,
μ
~
)
P(\mathcal{r} |b, \tilde{\mu})
P(r∣b,μ~)
，即给定上下文b和参数 μ \mu μ的情况下得到奖励的概率 - 后验分布 P ( μ ~ ∣ D ) ∝ P ( D ∣ μ ~ ) P ( μ ~ ) P(\tilde{\mu} | \mathcal{D}) \propto P(\mathcal{D} | \tilde{\mu}) P(\tilde{\mu}) P(μ~∣D)∝P(D∣μ~)P(μ~)，其中 P ( D ∣ μ ~ ) P(\mathcal{D} | \tilde{\mu}) P(D∣μ~)是似然函数
在每一轮中，TS根据具有最好参数的后验概率来选择arm。
一种简单的方法是使用后验分布为每个arm生成参数样本，然后选择生成最佳样本的arm。
使用高斯先验和高斯似然函数
在本文中，我们使用基于鞅的分析技术（novel martingale-based analysis techniques）来证明TS对具有线性收益函数的随机contextual bandits实现了高概率，接近最优的regret界限。
3.问题设置和算法描述
3.1 问题设置
- N个arms,每个arm i
- 时间t
- 上下文向量 b i T ( t ) b_{i}^{T}(t) biT(t)
- 要学习的参数 μ \mu μ
- 时间t内选择的动作 a ( t ) a(t) a(t)
- 历史信息 H t − 1 = { a ( τ ) , r a ( τ ) ( τ ) , b i ( τ ) , i = 1 , … , N , τ = 1 , … , t − 1 } \mathcal{H}_{t-1}=\left\{a(\tau), r_{a(\tau)}(\tau), b_{i}(\tau), i=1, \ldots, N, \tau=1, \ldots, t-1\right\} Ht−1={a(τ),ra(τ)(τ),bi(τ),i=1,…,N,τ=1,…,t−1}，包括t-1时刻之前已经选择的arm及其对应的rewards,和t-1时刻观察到的上下文向量 b i ( τ ) b_{i}(\tau) bi(τ)
给定
b
i
(
t
)
b_{i}(t)
bi(t)，时间t内arm i 的奖励是通过平均量
b
i
T
(
t
)
b_{i}^{T}(t)
biT(t)的（未知）分布生成的，其中
μ
ˉ
∈
R
d
\bar{\mu} \in \mathbb{R}^{d}
μˉ∈Rd是一个固定但未知的参数：
E [ r i ( t ) ∣ { b i ( t ) } i = 1 N , H t − 1 ] = E [ r i ( t ) ∣ b i ( t ) ] = b i ( t ) T μ \mathbb{E}\left[r_{i}(t) |\left\{b_{i}(t)\right\}_{i=1}^{N}, \mathcal{H}_{t-1}\right]=\mathbb{E}\left[r_{i}(t) | b_{i}(t)\right]=b_{i}(t)^{T} \mu E[ri(t)∣{bi(t)}i=1N,Ht−1]=E[ri(t)∣bi(t)]=bi(t)Tμ
- 时间t内最优的arm a ∗ ( t ) a^*(t) a∗(t), a ∗ ( t ) = a r g m a x i b i ( t ) T μ a^*(t)=argmax_ib_i(t)^T\mu a∗(t)=argmaxibi(t)Tμ
- Δ i ( t ) \Delta_i(t) Δi(t) 为时间t时最优arm和arm i的平均reward之间的差值：
Δ
i
(
t
)
=
b
a
∗
(
t
)
(
t
)
T
μ
−
b
i
(
t
)
T
μ
\Delta_i(t)=b_{a^*(t)}(t)^T\mu-b_i(t)^T\mu
Δi(t)=ba∗(t)(t)Tμ−bi(t)Tμ
则时间t内的regret定义为：
r
e
g
r
e
t
(
t
)
=
Δ
a
(
t
)
(
t
)
regret(t)=\Delta_{a(t)}(t)
regret(t)=Δa(t)(t)
r
e
g
r
e
t
(
t
)
=
r
a
∗
(
t
)
(
t
)
−
r
a
(
t
)
(
t
)
regret(t)=r_{a^*(t)}(t)-r_{a(t)}(t)
regret(t)=ra∗(t)(t)−ra(t)(t)
算法的目标是最小化时间T内总的regret
且假设（对所有t和i）：
∥
b
i
(
t
)
∥
≤
1
,
∥
μ
∥
≤
1
,
and
Δ
i
(
t
)
≤
1
\left\|b_{i}(t)\right\| \leq 1,\|\mu\| \leq 1, \text { and } \Delta_{i}(t) \leq 1
∥bi(t)∥≤1,∥μ∥≤1, and Δi(t)≤1
使得regret界限无标度。
3.2 Thompson Sampling 算法
使用高斯似然函数和高斯先验设计汤普森采样算法。
更精确地，假设在给定上下文 b i ( t ) b_{i}(t) bi(t)和参数 μ \mu μ的情况下，在时间t处：
- r i ( t ) r_i(t) ri(t)的似然由高斯分布 N ( b i ( t ) T μ , v 2 ) \mathcal{N}\left(b_{i}(t)^{T} \mu, v^{2}\right) N(bi(t)Tμ,v2)的概率密度函数给出。（v是给定的值）
令：
B ( t ) = I d + ∑ τ = 1 t − 1 b a ( τ ) ( τ ) b a ( τ ) ( τ ) T μ ^ ( t ) = B ( t ) − 1 ( ∑ τ = 1 t − 1 b a ( τ ) ( τ ) r a ( τ ) ( τ ) ) \begin{aligned} B(t) &=I_{d}+\sum_{\tau=1}^{t-1} b_{a(\tau)}(\tau) b_{a(\tau)}(\tau)^{T} \\ \hat{\mu}(t) &=B(t)^{-1}\left(\sum_{\tau=1}^{t-1} b_{a(\tau)}(\tau) r_{a(\tau)}(\tau)\right) \end{aligned} B(t)μ^(t)=Id+τ=1∑t−1ba(τ)(τ)ba(τ)(τ)T=B(t)−1(τ=1∑t−1ba(τ)(τ)ra(τ)(τ))
- μ \mu μ 的先验分布服从~ N ( μ ^ ( t ) , v 2 B ( t ) − 1 ) \mathcal{N}\left(\hat\mu(t) , v^{2}B(t)^{-1}\right) N(μ^(t),v2B(t)−1),则TS算法需要从 N ( μ ^ ( t ) , v 2 B ( t ) − 1 ) \mathcal{N}\left(\hat\mu(t) , v^{2}B(t)^{-1}\right) N(μ^(t),v2B(t)−1)分布中采样，得到采样值 μ ~ ( t ) \tilde{\mu}(t) μ~(t); μ ^ ( t ) \hat{\mu}(t) μ^(t)是要学习的参数 μ \mu μ在时间t内的均值。
- 则t+1时刻的后验分布可根据 P r ( μ ~ ∣ r i ( t ) ) ∝ P r ( r i ( t ) ∣ μ ~ ) P ( μ ~ ) Pr(\tilde{\mu} | r_i(t)) \propto Pr(r_i(t) | \tilde{\mu}) P(\tilde{\mu}) Pr(μ~∣ri(t))∝Pr(ri(t)∣μ~)P(μ~)计算得出。
1）算法一
是对每个时间t内的所有arm，从所给分布采样整体的参数miu
然后再对每个arm i 求reward：
b
i
(
t
)
T
μ
~
(
t
)
b_i(t)^T\tilde{\mu}(t)
bi(t)Tμ~(t)
2)算法二
是在每个时隙t内，针对每个arm t 直接根据奖励的分布采样得到每个arm的奖励采样值。
3）算法三
首先所有上下文向量以及要学习的参数都是独立于每个arm i的，有新的定义：
即不同的arm会有不同的参数
μ
\mu
μ,该算法会为每个arm i 的均值
μ
i
(
t
)
\mu_i(t)
μi(t)和
B
i
(
t
)
B_i(t)
Bi(t)维持单独的估计。